त्रुटि सुधार कोड

x

"इंटरलीवर" redirects here. For फाइबर ऑप्टिक डिवाइस, see ऑप्टिकल इंटरलीवर.

कम्प्यूटिंग, दूरसंचार, सूचना सिद्धांत और संकेतन सिद्धांत में, कभी-कभी त्रुटि सुधार कोड, (ईसीसी) का उपयोग अविश्वसनीय या मुखरसंचार चैनलों पर डेटा में त्रुटियों को नियंत्रित करने के लिए किया जाता है। केंद्रीय विचार यह है कि प्रेषक ईसीसी के रूप में अनावश्यक जानकारी के साथ संदेश को कूटबद्ध करता है। अतिरेक रिसीवर को सीमित संख्या में त्रुटियों का पता लगाने की अनुमति देता है, जो संदेश में कहीं भी हो सकते हैं, और अक्सर इन त्रुटियों को बिना पुनर्प्रसारण के ठीक करने के लिए किया जा सकता है। अमेरिकी गणितज्ञ रिचर्ड हैमिंग ने 1940 के दशक में इस क्षेत्र का नेतृत्व किया और 1950 में पहली त्रुटि-सुधार कोड का आविष्कार किया: हैमिंग (7,4) कोड

ईसीसी त्रुटि का पता लगाने के विपरीत है, जिसमें सामने आने वाली त्रुटियों को केवल पता ही नहीं लगाया जा सकता है, इसे ठीक भी किया जा सकता है। लाभ यह है कि ईसीसी का उपयोग करने वाली प्रणाली को त्रुटि होने पर डेटा के पुन: प्रसारण का अनुरोध करने के लिए रिवर्स चैनल की आवश्यकता नहीं होती है। नकारात्मक पक्ष यह है कि ये एक निश्चित ओवरहेड है जो संदेश में जोड़ा जाता है, जिससे उच्च अग्रेषण-चैनल बैंडविड्थ की आवश्यकता होती है। इसलिए ईसीसी उन स्थितियों में लागू किया जाता है, जहां पुन: प्रसारण महंगा या असंभव होता है, जैसे कि एक तरफ़ा संचार लिंक और जब बहुस्त्र्पीय में कई रिसीवरों को प्रेषित किया जाता है। लंबे समय तक चलने वाले कनेक्शन से भी फ़ायदा होता है; यूरेनस के चारों ओर परिक्रमा करने वाले उपग्रह के स्थितियों में, त्रुटियों के कारण पुन: प्रसारण में पांच घंटे की देरी हो सकती है। ईसीसी जानकारी को सामान्यतः बड़े पैमाने पर भंडारण उपकरणों में जोड़ा जाता है जिससे की दूषित डेटा की पुनर्प्राप्ति को सक्षम किया जा सके, मोडेम में व्यापक रूप से उपयोग किया जाता है, और इसका उपयोग उन प्रणालियों पर किया जाता है जहां प्राथमिक मेमोरी ईसीसी मेमोरी होती है।

एक रिसीवर में ईसीसी प्रसंस्करण एक डिजिटल बिटस्ट्रीम या डिजिटल रूप से संग्राहक वाहक के विमॉडुलन में लागू किया जा सकता है। उत्तरार्द्ध के लिए, ईसीसी रिसीवर में प्रारंभिक एनालॉग-टू-डिजिटल रूपांतरण का एक अभिन्न अंग है। विटरबी डिकोडर एक त्रुटि सुधार कोड एनालॉग सिग्नल से डिजिटल डेटा को डीमॉड्यूलेट करने के लिए मृदु निर्णय एल्गोरिदम को लागू करता है। कई ईसीसी एनकोडर/डिकोडर बिट त्रुटि दर (बीईआर) सिग्नल भी उत्पन्न कर सकते हैं, जिसका उपयोग एनालॉग रिसीविंग इलेक्ट्रॉनिक्स को ठीक करने के लिए प्रतिपुष्टि के रूप में किया जा सकता है।

त्रुटियों या विलुप्त बिट्स के अधिकतम अंश जिन्हें ठीक किया जा सकता है, ईसीसी कोड डिज़ाइन द्वारा निर्धारित किए जाते हैं, इसलिए विभिन्न स्थितियों के लिए अलग-अलग त्रुटि सुधार कोड उपयुक्त होते हैं। सामान्यतः, एक मजबूत कोड अधिक अतिरेक उत्पन्न करता है, जिसे उपलब्ध बैंडविड्थ का उपयोग करके प्रसारित करने की आवश्यकता होती है, जो प्राप्त प्रभावी सिग्नल-टू-नॉइस अनुपात में सुधार करते हुए प्रभावी बिट-दर को कम करता है। क्लाउड शैनन के नॉइस-चैनल संकेतन प्रमेय का उपयोग किसी अधिकतम स्वीकार्य त्रुटि संभावना के लिए अधिकतम प्राप्त करने योग्य संचार बैंडविड्थ की गणना के लिए किया जा सकता है। यह कुछ दिए गए आधार रव प्रबलता स्तर के साथ एक चैनल की सैद्धांतिक अधिकतम सूचना अंतरण दर पर सीमा स्थापित करता है। चूँकि, प्रमाण रचनात्मक नहीं है, और इसलिए क्षमता प्राप्त करने वाले कोड को बनाने के तरीके की कोई अंतर्दृष्टि नहीं देता है। वर्षों के शोध के बाद, 2016 तक कुछ उन्नत ईसीसी प्रणालियां सैद्धांतिक अधिकतम के बहुत करीब आ गए है।

आगे त्रुटि सुधार

दूरसंचार, सूचना सिद्धांत और संकेतन सिद्धांत में, आगे की त्रुटि सुधार (एफईसी) या चैनल संकेतन एक ऐसी तकनीक है जिसका उपयोग अविश्वसनीय या नॉइस संचार चैनलों पर डेटा ट्रांसमिशन में त्रुटियों को नियंत्रित करने के लिए किया जाता है। केंद्रीय विचार यह है कि ईसीसी का उपयोग करके प्रेषक संदेश को निरर्थक तरीके से एन्कोड करता है ।

अतिरेक रिसीवर को सीमित संख्या में त्रुटियों का पता लगाने की अनुमति देता है जो संदेश में कहीं भी हो सकती हैं, और अक्सर इन त्रुटियों को पुनः प्रसारण के बिना ठीक करने के लिए एफईसी रिसीवर डेटा को पुन: प्रसारण का अनुरोध करने के लिए एक रिवर्स चैनल की आवश्यकता के बिना त्रुटियों को ठीक करने की क्षमता देता है, लेकिन एक निश्चित, उच्च फॉरवर्ड चैनल बैंडविड्थ की कीमत पर। इसलिए एफईसी उन स्थितियों में लागू किया जाता है, जहां पुन: प्रसारण असंभव होता है, जैसे कि एकतरफा संचार लिंक और मल्टीकास्ट में कई रिसीवरों को प्रेषित करते समय एफईसी सामान्यतः बड़े पैमाने पर भंडारण (चुंबकीय, ऑप्टिकल और ठोस क्षेत्र /फ्लैश आधारित) उपकरणों में जोड़ा जाता है, ताकि विकृत डेटा की पुनर्प्राप्ति को सक्षम करने के लिए, मोडेम में व्यापक रूप से उन प्रणालियों पर उपयोग किया जा सके, जहां प्राथमिक मेमोरी ईसीसी मेमोरी और प्रसारण स्थितियों में होती है, और जहां रिसीवर के पास पुन: प्रसारण का अनुरोध करने की क्षमता नहीं होती है, या ऐसा करने से महत्वपूर्ण विलंबता उत्पन्न होती है। उदाहरण के लिए, यूरेनस की परिक्रमा करने वाले उपग्रह के मामले में, डिसंकेतन त्रुटियों के कारण पुन: प्रसारण से कम से कम 5 घंटे का विलंब होता है।

एक रिसीवर में एफईसी प्रसंस्करण एक डिजिटल बिट स्ट्रीम या डिजिटल रूप से संग्राहक वाहक के विमॉडुलनमें लागू किया जा सकता है। बाद के लिए, एफईसी रिसीवर में प्रारंभिक एनालॉग-टू-डिजिटल रूपांतरण का एक अभिन्न अंग है। विटरबी डिकोडर एक सॉफ्ट-डिसीजन एल्गोरिथम को लागू करता है, जो नॉइस से दूषित एनालॉग सिग्नल से डिजिटल डेटा को डिमॉड्यूलेट करता है। कई एफईसी कोडर्स एक बिट-एरर रेट (बीइआर) सिग्नल भी उत्पन्न कर सकते हैं, जिसका उपयोग एनालॉग प्राप्त इलेक्ट्रॉनिक्स को ठीक करने के लिए प्रतिपुष्टि के रूप में किया जा सकता है।

त्रुटियों या विलुप्त बिट्स का अधिकतम अनुपात जिसे ठीक किया जा सकता है, ईसीसी के डिजाइन द्वारा निर्धारित किया जाता है, इसलिए विभिन्न स्थितियों के लिए अलग-अलग त्रुटि सुधार कोड उपयुक्त होते हैं। सामान्यतः, एक मजबूत कोड अधिक अतिरेक उत्पन्न करता है जिसे उपलब्ध बैंडविड्थ का उपयोग करके प्रसारित करने की आवश्यकता होती है, जो प्राप्त प्रभावी सिग्नल-टू-नॉइस अनुपात में सुधार करते हुए प्रभावी बिट-दर को कम करता है। क्लाउड शैनन में नॉइस-चैनल संकेतन प्रमेय इस सवाल का जवाब देता है कि डिसंकेतन त्रुटि संभावना को शून्य करने वाले सबसे कुशल कोड का उपयोग करते हुए डेटा संचार के लिए कितना बैंडविड्थ बचा सकता है। यह कुछ दिए गए आधार पर नॉइस स्तर के साथ एक चैनल की सैद्धांतिक अधिकतम सूचना अंतरण दर पर सीमा स्थापित करता है। उनका प्रमाण रचनात्मक नहीं है, और इसलिए क्षमता प्राप्त करने वाले कोड को कैसे बनाया जाए, इसकी कोई जानकारी नहीं देता है। , वर्षों के शोध के बाद, कुछ उन्नतएफईसी प्रणालियाँ जैसे ध्रुवीय कोड (संकेतन सिद्धांत) अनंत लंबाई के फ्रेम की परिकल्पना के तहत शैनन चैनल क्षमता प्राप्त करता है ।

यह कैसे काम करता है

एल्गोरिथम का उपयोग करके प्रेषित सूचना में अतिरेक (सूचना सिद्धांत) जोड़कर ईसीसी को पूरा किया जाता है। एक निरर्थक बिट कई मूल सूचना बिट्स का एक जटिल कार्य हो सकता है। मूल जानकारी एन्कोडेड आउटपुट में शाब्दिक रूप से प्रकट हो भी सकती है और नहीं भी; कोड जो आउटपुट में अपरिवर्तित इनपुट शामिल करते हैं, ये व्यवस्थित कोड होते हैं, जबकि जो गैर-व्यवस्थित नहीं होते हैं।

ईसीसी का एक सरल उदाहरण प्रत्येक डेटा बिट को 3 बार प्रसारित करना है, जिसे (3,1) पुनरावृत्ति कोड के रूप में जाना जाता है। एक नॉइस चैनल के माध्यम से, एक रिसीवर आउटपुट के 8 संस्करण देख सकता है, नीचे दी गई तालिका देखें।

Triplet received	Interpreted as
000	0 (error-free)
001	0
010	0
100	0
111	1 (error-free)
110	1
101	1
011	1

यह तीन नमूनों में से किसी एक में त्रुटि को बहुसंख्यक वोट या लोकतांत्रिक मतदान द्वारा ठीक करने की अनुमति देता है। इस ईसीसी की सुधार क्षमता है:

• त्रुटि में 1 बिट ट्रिपलेट तक, या
• ट्रिपलेट के 2 बिट तक छोड़े गए (मामलों को तालिका में नहीं दिखाया गया है)।

हालांकि लागू करने में सरल और व्यापक रूप से उपयोग किया जाता है, यह ट्रिपल मॉड्यूलर अतिरेक अपेक्षाकृत अक्षम ईसीसी है। बेहतर ईसीसी कोड सामान्यतः पिछले कई दसियों या यहां तक ​​कि पहले प्राप्त बिट्स के पिछले कई सैकड़ों की जांच करते हैं ताकि यह निर्धारित किया जा सके कि वर्तमान छोटे मुट्ठी भर बिट्स (सामान्यतः 2 से 8 बिट्स के समूह में) को कैसे डिकोड किया जाए।

त्रुटियों को कम करने के लिए औसत नॉइस

ईसीसी को नॉइस के औसत से काम करने के लिए कहा जा सकता है; चूंकि प्रत्येक डेटा बिट कई संचरित प्रतीकों को प्रभावित करता है, नॉइस द्वारा कुछ प्रतीकों का भ्रष्टाचार आम तौर पर मूल उपयोगकर्ता डेटा को दूसरे से निकालने की अनुमति देता है, अनियंत्रित प्राप्त प्रतीक जो समान उपयोगकर्ता डेटा पर भी निर्भर करते हैं।

• इस जोखिम-पूलिंग प्रभाव के कारण, ईसीसी का उपयोग करने वाली डिजिटल संचार प्रणालियां एक निश्चित न्यूनतम सिग्नल-टू-नॉइस अनुपात से ऊपर अच्छी तरह से काम करती हैं और इसके नीचे बिल्कुल नहीं।
• यह ऑल-ऑर-नथिंग प्रवृत्ति - चट्टान प्रभाव - अधिक स्पष्ट हो जाता है क्योंकि मजबूत कोड का उपयोग किया जाता है जो सैद्धांतिक शैनन सीमा के अधिक निकट होते हैं।
• इंटरलीविंग ईसीसी कोडेड डेटा प्रेषित ईसीसी कोड के सभी या कुछ भी गुणों को कम कर सकता है जब चैनल त्रुटियां फटने में होती हैं। चूंकि , इस पद्धति की सीमाएँ हैं; यह नैरोबैंड डेटा पर सबसे अच्छा उपयोग किया जाता है।

अधिकांश दूरसंचार प्रणालियां एक निश्चित चैनल कोड का उपयोग करती हैं जिसे अपेक्षित सबसे खराब स्थिति वाली बिट त्रुटि दर को सहन करने के लिए डिज़ाइन किया गया है, और यदि बिट त्रुटि दर कभी भी खराब हो तो बिल्कुल भी काम करने में विफल रहती है। चूंकि , कुछ सिस्टम दिए गए चैनल त्रुटि स्थितियों के अनुकूल होते हैं: हाइब्रिड ऑटोमैटिक रिपीट-रिक्वेस्ट के कुछ उदाहरण एक निश्चित ईसीसी विधि का उपयोग करते हैं, जब तक कि ईसीसी त्रुटि दर को संभाल सकता है, तब स्वचालित रिपीट अनुरोध पर स्विच करें जब त्रुटि दर बहुत अधिक हो जाती है; अनुकूली मॉडुलन और संकेतन ईसीसी दरों की एक किस्म का उपयोग करता है, प्रति पैकेट अधिक त्रुटि-सुधार बिट्स जोड़ता है जब चैनल में उच्च त्रुटि दर होती है, या जब उनकी आवश्यकता नहीं होती है तो उन्हें बाहर निकाल दिया जाता है।

ईसीसी के प्रकार

Main articles: ब्लॉक कोड and संवादात्मक कोड

त्रुटि सुधार कोड का संक्षिप्त वर्गीकरण

ईसीसी कोड की दो मुख्य श्रेणियां ब्लॉक कोड और दृढ़ कोड हैं।

• ब्लॉक कोड बिट्स या पूर्व निर्धारित आकार के प्रतीकों के निश्चित आकार के ब्लॉक (पैकेट) पर काम करते हैं। प्रैक्टिकल ब्लॉक कोड सामान्यतः बहुपद समय में उनकी ब्लॉक लंबाई में हार्ड-डीकोड किए जा सकते हैं।
• संवादात्मक कोड मनमाना लंबाई के बिट या प्रतीक धाराओं पर काम करते हैं। वे अक्सर विटरबी एल्गोरिथ्म के साथ सॉफ्ट डीकोडेड होते हैं,चूँकि अन्य एल्गोरिदम कभी-कभी उपयोग किए जाते हैं। विटरबी डिसंकेतन असम्बद्ध रूप से इष्टतम डिसंकेतन दक्षता की अनुमति देता है, जो दृढ़ संहिता की बढ़ती बाधा लंबाई के साथ है, लेकिन घातीय समय बढ़ती जटिलता की कीमत पर। एक कनवल्शनल कोड जिसे टर्मिनेट किया जाता है, वह भी एक 'ब्लॉक कोड' होता है, जिसमें यह इनपुट डेटा के एक ब्लॉक को एनकोड करता है, लेकिन एक कन्वेन्शनल कोड का ब्लॉक आकार आम तौर पर मनमाना होता है, जबकि ब्लॉक कोड का एक निश्चित आकार होता है जो उनके बीजगणितीय विशेषताओं द्वारा निर्धारित होता है। कनवल्शनल कोड्स के टर्मिनेशन के प्रकारों में टेल-बाइटिंग और बिट-फ्लशिंग शामिल हैं।

कई प्रकार के ब्लॉक कोड हैं; रीड-सोलोमन त्रुटि सुधार|रीड-सोलोमन संकेतन कॉम्पैक्ट डिस्क, डीवीडी और हार्ड डिस्क ड्राइव#त्रुटि दर और हैंडलिंग में इसके व्यापक उपयोग के लिए उल्लेखनीय है। शास्त्रीय ब्लॉक कोड के अन्य उदाहरणों में गोले कोड (बहुविकल्पी), बीसीएच कोड, बहुआयामी समानता-जांच कोड और हैमिंग कोड शामिल हैं।

हैमिंग ईसीसी का उपयोग सामान्यतः एनएएनडी फ्लैश मेमोरी त्रुटियों को ठीक करने के लिए किया जाता है। यह सिंगल-बिट एरर करेक्शन और 2-बिट एरर डिटेक्शन प्रदान करता है। हैमिंग कोड केवल अधिक विश्वसनीय एकल-स्तरीय सेल (SLC) NAND के लिए उपयुक्त हैं। सघन बहु-स्तरीय सेल (एमएलसी) एनएएनडी बीसीएच या रीड-सोलोमन जैसे बहु-बिट सुधार ईसीसी का उपयोग कर सकता है। NOR Flash सामान्यतः किसी त्रुटि सुधार का उपयोग नहीं करता है।

शास्त्रीय ब्लॉक कोड सामान्यतः हार्ड-डिसीजन एल्गोरिदम का उपयोग करके डिकोड किए जाते हैं, जिसका अर्थ है कि प्रत्येक इनपुट और आउटपुट सिग्नल के लिए एक कठिन निर्णय लिया जाता है चाहे वह एक या शून्य बिट के अनुरूप हो। इसके विपरीत, विटरबी, एमएपी या बीसीजेआर एल्गोरिदम जैसे सॉफ्ट-डिसीजन एल्गोरिदम का उपयोग करके कन्वेन्शनल कोड को सामान्यतः डिकोड किया जाता है, जो एनालॉग सिग्नल को प्रोसेस (विघटित) करता है, और जो हार्ड-डिसीजन डिसंकेतन की तुलना में बहुत अधिक त्रुटि-सुधार प्रदर्शन की अनुमति देता है।

लगभग सभी शास्त्रीय ब्लॉक कोड परिमित क्षेत्रों के बीजगणितीय गुणों को लागू करते हैं। इसलिए शास्त्रीय ब्लॉक कोड को अक्सर बीजगणितीय कोड कहा जाता है।

शास्त्रीय ब्लॉक कोड के विपरीत जो अक्सर त्रुटि-पता लगाने या त्रुटि-सुधार करने की क्षमता निर्दिष्ट करते हैं, कई आधुनिक ब्लॉक कोड जैसे एलडीपीसी कोड में ऐसी गारंटी नहीं होती है। इसके बजाय, आधुनिक कोड का मूल्यांकन उनकी बिट त्रुटि दरों के संदर्भ में किया जाता है।

अधिकांश आगे त्रुटि सुधार कोड केवल बिट-फ्लिप को सही करते हैं, लेकिन बिट-इंसर्शन या बिट-डिलीशन को नहीं। इस सेटिंग में, बिट त्रुटि दर को मापने के लिए हैमिंग दूरी उपयुक्त तरीका है। मार्कर कोड और वॉटरमार्क कोड जैसे बिट-प्रविष्टि और बिट-विलोपन को ठीक करने के लिए कुछ अग्रेषित त्रुटि सुधार कोड डिज़ाइन किए गए हैं। ऐसे कोड का उपयोग करते समय बिट त्रुटि दर को मापने के लिए लेवेनशेटिन दूरी एक अधिक उपयुक्त तरीका है।

== कोड-दर और विश्वसनीयता और डेटा दर == के बीच तालमेल

See also: Bit rate § Information rate

ईसीसी का मूल सिद्धांत डिकोडर को ट्रांसमीटर द्वारा एन्कोड किए गए सही संदेश को खोजने में मदद करने के लिए अनावश्यक बिट्स जोड़ना है। किसी दिए गए ईसीसी सिस्टम की कोड-दर को दिए गए संचार पैकेज में सूचना बिट्स की संख्या और बिट्स की कुल संख्या (यानी, सूचना प्लस अतिरेक बिट्स) के बीच के अनुपात के रूप में परिभाषित किया गया है। कोड-दर इसलिए एक वास्तविक संख्या है। शून्य के करीब एक कम कोड-दर एक मजबूत कोड का अर्थ है जो एक अच्छा प्रदर्शन प्राप्त करने के लिए कई अनावश्यक बिट्स का उपयोग करता है, जबकि 1 के करीब एक बड़ी कोड-दर एक कमजोर कोड का संकेत देती है।

अनावश्यक बिट्स जो जानकारी की रक्षा करते हैं उन्हें उसी संचार संसाधनों का उपयोग करके स्थानांतरित किया जाना चाहिए जिसकी वे रक्षा करने का प्रयास कर रहे हैं। यह विश्वसनीयता और डेटा दर के बीच एक मौलिक व्यापार का कारण बनता है। एक चरम में, एक मजबूत कोड (कम कोड-दर के साथ) प्रभावी डेटा दर को कम करने की कीमत पर, बिट त्रुटि दर को कम करने वाले रिसीवर एसएनआर (सिग्नल-टू-नॉइस-अनुपात) में एक महत्वपूर्ण वृद्धि को प्रेरित कर सकता है। दूसरी चरम पर, किसी भी ईसीसी (यानी, 1 के बराबर एक कोड-दर) का उपयोग नहीं करने से बिट्स को बिना किसी अतिरिक्त सुरक्षा के छोड़ने की कीमत पर सूचना हस्तांतरण उद्देश्यों के लिए पूर्ण चैनल का उपयोग किया जाता है।

एक दिलचस्प सवाल निम्नलिखित है: सूचना हस्तांतरण के मामले में एक ईसीसी कितना कुशल हो सकता है जिसमें नगण्य डिसंकेतन त्रुटि दर हो? इस प्रश्न का उत्तर क्लॉड शैनन ने अपने दूसरे प्रमेय के साथ दिया, जो कहता है कि चैनल क्षमता किसी भी ईसीसी द्वारा प्राप्त की जाने वाली अधिकतम बिट दर है जिसकी त्रुटि दर शून्य हो जाती है: उनका प्रमाण गाऊसी यादृच्छिक संकेतन पर निर्भर करता है, जो वास्तविक दुनिया के अनुप्रयोगों के लिए उपयुक्त नहीं है। शैनन के काम द्वारा दी गई ऊपरी सीमा ने ईसीसी को डिजाइन करने में लंबी यात्रा को प्रेरित किया जो अंतिम प्रदर्शन सीमा के करीब आ सकता है। विभिन्न कोड आज लगभग शैनन सीमा प्राप्त कर सकते हैं।चूँकि , ईसीसी हासिल करने की क्षमता सामान्यतः लागू करने के लिए बेहद जटिल होती है।

सबसे लोकप्रिय ईसीसी में प्रदर्शन और कम्प्यूटेशनल जटिलता के बीच एक समझौता है। सामान्यतः, उनके पैरामीटर संभावित कोड दरों की एक श्रृंखला देते हैं, जिन्हें परिदृश्य के आधार पर अनुकूलित किया जा सकता है। सामान्यतः, यह अनुकूलन डेटा दर पर प्रभाव को कम करते हुए कम डिसंकेतन त्रुटि संभावना प्राप्त करने के लिए किया जाता है। कोड दर के अनुकूलन के लिए एक अन्य मानदंड संचार की ऊर्जा लागत के क्रम में कम त्रुटि दर और पुन: प्रसारण संख्या को संतुलित करना है।

बेहतर प्रदर्शन के लिए जुड़े हुए ईसीसी कोड

Main article: Concatenated error correction codes

क्लासिकल (बीजगणितीय) ब्लॉक कोड और कन्वेन्शनल कोड अक्सर समेकित संकेतन योजनाओं में संयुक्त होते हैं जिसमें एक छोटी बाधा-लंबाई विटरबी-डीकोडेड कनवल्शनल कोड अधिकांश काम करता है और एक ब्लॉक कोड (सामान्यतः रीड-सोलोमन) बड़े प्रतीक आकार और ब्लॉक लंबाई के साथ कनवल्शनल डिकोडर द्वारा की गई किसी भी त्रुटि को मिटा देता है। त्रुटि सुधार कोड के इस परिवार के साथ एकल पास डिसंकेतन बहुत कम त्रुटि दर प्राप्त कर सकता है, लेकिन लंबी दूरी की संचरण स्थितियों (जैसे गहरे स्थान) के लिए पुनरावृत्त डिसंकेतन की सिफारिश की जाती है।

कनेक्टेड कोड उपग्रह और गहरे अंतरिक्ष संचार में मानक अभ्यास रहे हैं क्योंकि वायेजर कार्यक्रम ने पहली बार यूरेनस के साथ 1986 की मुठभेड़ में तकनीक का उपयोग किया था। गैलीलियो (अंतरिक्ष यान) शिल्प ने असफल एंटीना होने के कारण बहुत उच्च त्रुटि दर स्थितियों की भरपाई के लिए पुनरावृत्त संघटित कोड का उपयोग किया।

लो-डेंसिटी पैरिटी-चेक (LDPC)

Main article: Low-density parity-check code

कम-घनत्व समता-चेक कोड | लो-डेंसिटी पैरिटी-चेक (LDPC) कोड अत्यधिक कुशल रैखिक ब्लॉक का एक वर्ग है कई एकल समानता जांच (एसपीसी) कोड से बने कोड। वे अपनी ब्लॉक लंबाई के संदर्भ में रैखिक समय जटिलता पर पुनरावृत्त नरम-निर्णय डिसंकेतन दृष्टिकोण का उपयोग करके शैनन सीमा (सैद्धांतिक अधिकतम) के बहुत करीब प्रदर्शन प्रदान कर सकते हैं। व्यावहारिक कार्यान्वयन समानांतर में घटक SPC कोड को डिकोड करने पर बहुत अधिक निर्भर करता है।

एलडीपीसी कोड सबसे पहले 1960 में रॉबर्ट जी. गैलागर ने अपनी पीएचडी थीसिस में पेश किए थे, लेकिन एनकोडर और डिकोडर को लागू करने और रीड-सोलोमन कोड की शुरूआत में कम्प्यूटेशनल प्रयास के कारण, 1990 के दशक तक उन्हें ज्यादातर नजरअंदाज किया गया था।

LDPC कोड अब हाल के कई हाई-स्पीड संचार मानकों में उपयोग किए जाते हैं, जैसे DVB-S2 (डिजिटल वीडियो ब्रॉडकास्टिंग - सैटेलाइट - सेकेंड जेनरेशन), WiMAX (माइक्रोवेव संचार के लिए IEEE 802.16e मानक), हाई-स्पीड वायरलेस LAN (IEEE 802.11n) ), 802.3an#10GBASE-T|10GBase-T ईथरनेट (802.3an) और G.hn|G.hn/G.9960 (बिजली लाइनों, फोन लाइनों और समाक्षीय केबल पर नेटवर्किंग के लिए ITU-T मानक)। अन्य LDPC कोड 3GPP MBMS के भीतर वायरलेस संचार मानकों के लिए मानकीकृत हैं (मानकों में फाउंटेन कोड#फाउंटेन कोड देखें)।

टर्बो कोड

Main article: Turbo code

टर्बो कोड एक पुनरावर्तित सॉफ्ट-डिसंकेतन योजना है जो दो या दो से अधिक अपेक्षाकृत सरल कनवल्शनल कोड और एक इंटरलीवर को एक ब्लॉक कोड बनाने के लिए जोड़ती है जो शैनन सीमा के डेसिबल के एक अंश के भीतर प्रदर्शन कर सकता है। व्यावहारिक अनुप्रयोग के संदर्भ में एलडीपीसी कोड से पहले, वे अब समान प्रदर्शन प्रदान करते हैं।

टर्बो संकेतन के शुरुआती व्यावसायिक अनुप्रयोगों में से एक CDMA2000 (TIA IS-2000) डिजिटल सेलुलर तकनीक थी जिसे क्वालकॉम द्वारा विकसित किया गया था और वेरिज़ॉन वायरलेस, स्प्रिंट नेक्सटल और अन्य वाहकों द्वारा बेचा गया था। इसका उपयोग CDMA2000 1x के विकास के लिए विशेष रूप से इंटरनेट एक्सेस, Evolution-Data Optimized|1xEV-DO (TIA IS-856) के लिए भी किया जाता है। 1x की तरह, EV-DO क्वालकॉम द्वारा विकसित किया गया था, और वेरिज़ोन वायरलेस, स्प्रिंट नेक्स्टल और अन्य वाहकों द्वारा बेचा जाता है (1xEV-DO के लिए वेरिज़ोन का मार्केटिंग नाम ब्रॉडबैंड एक्सेस है, स्प्रिंट के उपभोक्ता और 1xEV-DO के लिए व्यावसायिक मार्केटिंग नाम पावर विजन हैं और मोबाइल ब्रॉडबैंड, क्रमशः)।

स्थानीय डिसंकेतन और कोड का परीक्षण

Main articles: Locally decodable code and Locally testable code

कभी-कभी केवल संदेश के एक बिट को डिकोड करना आवश्यक होता है, या यह जांचने के लिए कि क्या दिया गया संकेत एक कोडवर्ड है, और पूरे सिग्नल को देखे बिना ऐसा करें। यह एक स्ट्रीमिंग सेटिंग में समझ में आ सकता है, जहां कोडवर्ड बहुत तेजी से पर्याप्त रूप से डिकोड किए जाने के लिए बहुत बड़े हैं और जहां संदेश के केवल कुछ बिट्स अभी के लिए रुचि के हैं। साथ ही ऐसे कोड कम्प्यूटेशनल जटिलता सिद्धांत में एक महत्वपूर्ण उपकरण बन गए हैं, उदाहरण के लिए, संभाव्य रूप से जांच योग्य प्रमाणों के डिजाइन के लिए।

स्थानीय रूप से डिकोड करने योग्य कोड त्रुटि-सुधार करने वाले कोड होते हैं, जिसके लिए कोडवर्ड के कुछ स्थिर अंशों पर कोडवर्ड के दूषित होने के बाद भी कोडवर्ड की स्थिति की एक छोटी (निरंतर) संख्या को देखते हुए संदेश के एकल बिट्स को संभाव्य रूप से पुनर्प्राप्त किया जा सकता है। स्थानीय रूप से परीक्षण योग्य कोड त्रुटि-सुधार करने वाले कोड होते हैं, जिसके लिए यह संभाव्य रूप से जांचा जा सकता है कि सिग्नल की स्थिति की एक छोटी संख्या को देखते हुए सिग्नल कोडवर्ड के करीब है या नहीं।

इंटरलीविंग

"Interleaver" redirects here. For the fiber-optic device, see optical interleaver.

इंटरलीविंग विचार का एक छोटा उदाहरण

आगे त्रुटि सुधार कोड के प्रदर्शन को बेहतर बनाने के लिए इंटरलीविंग का उपयोग अक्सर डिजिटल संचार और भंडारण प्रणालियों में किया जाता है। कई संचार चैनल मेमोरीलेस नहीं होते हैं: सामान्यतः त्रुटियाँ स्वतंत्र रूप से होने के बजाय फटने वाली त्रुटियों में होती हैं। यदि किसी कोड शब्द में त्रुटियों की संख्या त्रुटि-सुधार कोड की क्षमता से अधिक है, तो यह मूल कोड शब्द को पुनर्प्राप्त करने में विफल रहता है। इंटरलीविंग कई कोड शब्दों में स्रोत प्रतीकों को फेरबदल करके इस समस्या को दूर करता है, जिससे त्रुटियों का अधिक समान वितरण (निरंतर) बनता है। इसलिए, इंटरलीविंग का व्यापक रूप से फट त्रुटि सुधार कोड | बर्स्ट एरर-करेक्शन के लिए उपयोग किया जाता है।

आधुनिक पुनरावृत्त कोड का विश्लेषण, जैसे टर्बो कोड और एलडीपीसी कोड, सामान्यतः त्रुटियों का एक स्वतंत्र वितरण मानते हैं। एलडीपीसी कोड का उपयोग करने वाले सिस्टम सामान्यतः कोड वर्ड के भीतर प्रतीकों में अतिरिक्त इंटरलीविंग को नियोजित करते हैं। टर्बो कोड के लिए, एक इंटरलीवर एक अभिन्न अंग है और अच्छे प्रदर्शन के लिए इसका उचित डिज़ाइन महत्वपूर्ण है। पुनरावृत्त डिसंकेतन एल्गोरिथ्म सबसे अच्छा काम करता है जब डिकोडर का प्रतिनिधित्व करने वाले कारक ग्राफ में छोटे चक्र नहीं होते हैं; छोटे चक्रों से बचने के लिए इंटरलीवर को चुना जाता है।

इंटरलीवर डिज़ाइन में शामिल हैं:

• आयताकार (या एकसमान) इंटरलीवर्स (ऊपर वर्णित स्किप कारकों का उपयोग करने वाली विधि के समान)
• दृढ़ इंटरलीवर
• यादृच्छिक इंटरलीवर (जहां इंटरलीवर एक ज्ञात यादृच्छिक क्रमपरिवर्तन है)
• एस-यादृच्छिक इंटरलीवर (जहां इंटरलीवर एक ज्ञात यादृच्छिक क्रमपरिवर्तन है जिसमें बाधा है कि दूरी एस के भीतर कोई इनपुट प्रतीक आउटपुट में एस की दूरी के भीतर दिखाई नहीं देता है)।
• एक विवाद-मुक्त द्विघात क्रमचय बहुपद (QPP)। उपयोग का एक उदाहरण 3GPP लॉन्ग टर्म इवोल्यूशन मोबाइल दूरसंचार मानक में है।

मल्टी-वाहक संकेत कम्युनिकेशन सिस्टम में, फ्रीक्वेंसी विविधता योजना प्रदान करने के लिए कैरियर्स के बीच इंटरलीविंग को नियोजित किया जा सकता है, उदाहरण के लिए, आवृत्ति-चयनात्मक लुप्त होती या नैरोबैंड इंटरफेरेंस को कम करने के लिए।

उदाहरण

बिना इंटरलीविंग के ट्रांसमिशन:

त्रुटि रहित संदेश:                                 aaaabbbbccccddddeeeeffffgggg

फट त्रुटि के साथ संचरण: aaaabbbbccc____deeeeffffgggg यहां, एक ही अक्षर का प्रत्येक समूह 4-बिट एक-बिट त्रुटि-सुधार कोडवर्ड का प्रतिनिधित्व करता है। कोडवर्ड cccc एक बिट में बदल दिया गया है और इसे ठीक किया जा सकता है, लेकिन कोडवर्ड dddd तीन बिट्स में बदल दिया गया है, इसलिए या तो इसे डीकोड नहीं किया जा सकता है या यह झूठा हो सकता है।

इंटरलीविंग के साथ:

त्रुटि रहित कूट शब्द:                              aaaabbbbccccddddeeeeffffgggg

इंटरलीव्ड: abcdefgabcdefgabcdefgabcdefg फट त्रुटि के साथ संचरण: abcdefgabcd____bcdefgabcdefg डीइंटरलीविंग के बाद प्राप्त कोड शब्द: aa_abbbbccccdddde_eef_ffg_gg प्रत्येक कोडवर्ड मेंaaaa,eeee,ffff, औरgggg, केवल एक बिट बदला गया है, इसलिए एक-बिट त्रुटि-सुधार कोड सब कुछ सही ढंग से डिकोड करेगा।

बिना इंटरलीविंग के ट्रांसमिशन:

मूल प्रेषित वाक्य:                      ThisIsAnExampleOfInterleaving

बर्स्ट त्रुटि के साथ वाक्य प्राप्त हुआ: ThisIs______pleOfInterleaving अवधिAnExampleज्यादातर समझ से बाहर और सही करने के लिए मुश्किल समाप्त होता है।

इंटरलीविंग के साथ:

प्रेषित वाक्य:                               ThisIsAnExampleOfInterleaving...

त्रुटि रहित संचरण: TIEpfeaghsxlIrv.iAaenli.snmOten. बर्स्ट त्रुटि के साथ वाक्य प्राप्त हुआ: TIEpfe______Irv.iAaenli.snmOten. deinterleaving के बाद सजा मिली: T_isI_AnE_amp_eOfInterle_vin_... कोई भी शब्द पूरी तरह से खोया नहीं है और कम से कम अनुमान के साथ विलुप्त अक्षरों को पुनर्प्राप्त किया जा सकता है।

इंटरलीविंग के नुकसान

इंटरलीविंग तकनीकों का उपयोग कुल विलंब को बढ़ाता है। ऐसा इसलिए है क्योंकि पैकेट को डिकोड किए जाने से पहले पूरे इंटरलीव्ड ब्लॉक को प्राप्त किया जाना चाहिए। साथ ही इंटरलीवर त्रुटियों की संरचना को छिपाते हैं; इंटरलीवर के बिना, अधिक उन्नत डिसंकेतन एल्गोरिदम त्रुटि संरचना का लाभ उठा सकते हैं और इंटरलीवर के साथ संयुक्त सरल डिकोडर की तुलना में अधिक विश्वसनीय संचार प्राप्त कर सकते हैं।. ऐसे एल्गोरिदम का एक उदाहरण तंत्रिका नेटवर्क पर आधारित है संरचनाएं।

त्रुटि-सुधार कोड के लिए सॉफ्टवेयर

सॉफ़्टवेयर में त्रुटि-सुधार कोड (ईसीसीs) के व्यवहार का अनुकरण करना ईसीसीs को डिज़ाइन, मान्य और बेहतर बनाने के लिए एक सामान्य अभ्यास है। आगामी वायरलेस 5G मानक सॉफ्टवेयर ईसीसी के लिए अनुप्रयोगों की एक नई श्रेणी को बढ़ाता है: क्लाउड रेडियो एक्सेस नेटवर्क (C-RAN) एक सॉफ्टवेयर-परिभाषित रेडियो | सॉफ्टवेयर-परिभाषित रेडियो (SDR) संदर्भ में। विचार सीधे संचार में सॉफ्टवेयर ईसीसी का उपयोग करना है। उदाहरण के लिए 5जी में, सॉफ्टवेयर ईसीसी क्लाउड में स्थित हो सकते हैं और एंटेना इस कंप्यूटिंग संसाधनों से जुड़े हुए हैं: इस तरह संचार नेटवर्क के लचीलेपन में सुधार और अंततः सिस्टम की ऊर्जा दक्षता में वृद्धि।

इस संदर्भ में, विभिन्न उपलब्ध ओपन-सोर्स सॉफ़्टवेयर नीचे सूचीबद्ध हैं (गैर संपूर्ण)।

• AFF3CT(एक फास्ट फॉरवर्ड एरर करेक्शन टूलबॉक्स): C++ में एक पूर्ण संचार श्रृंखला (टर्बो, एलडीपीसी, पोलर कोड आदि जैसे कई समर्थित कोड), बहुत तेज और विशिष्ट चैनल संकेतन (अनुकरण के लिए एक कार्यक्रम के रूप में या एसडीआर के लिए एक पुस्तकालय के रूप में इस्तेमाल किया जा सकता है)।
• IT++: रैखिक बीजगणित, संख्यात्मक अनुकूलन, सिग्नल प्रोसेसिंग, संचार और सांख्यिकी के लिए कक्षाओं और कार्यों की एक C++ लाइब्रेरी।
• OpenAir: विकसित पैकेट कोर नेटवर्क से संबंधित 3GPP विनिर्देशों का कार्यान्वयन (C में)।

त्रुटि-सुधार कोड की सूची

दूरी	कोड
2 (एकल त्रुटि का पता लगाने)	समानता
3 (एकल-त्रुटि सुधार)	ट्रिपल मॉड्यूलर अतिरेक
3 (एकल-त्रुटि सुधार)	सही हैमिंग जैसे हैमिंग (7,4)
4 (सेकंडेड)	विस्तारित हैमिंग
5 (दोहरी त्रुटि सुधार)
6 (डबल-त्रुटि सही-/ट्रिपल त्रुटि डिटेक्ट)	नॉर्डस्ट्रॉम-रॉबिन्सन कोड
7 (तीन-त्रुटि सुधार)	सही बाइनरी गोलय कोड
8 (टीईसीएफईडी)	विस्तारित बाइनरी गोलय कोड

• एएन कोड
• बीसीएच कोड, जिसे प्रति कोड ब्लॉक किसी भी मनमानी संख्या में त्रुटियों को ठीक करने के लिए डिज़ाइन किया जा सकता है।
• रडार, टेलीमेट्री, अल्ट्रा साउंड, वाईफाई, डीएसएसएस मोबाइल फोन नेटवर्क, जीपीएस आदि के लिए इस्तेमाल किया जाने वाला बार्कर कोड।
• बर्जर कोड
• नियत भार कोड
• संवलनात्मक कोड
• प्रसारक कोड
• समूह कोड
• गोलय कोड, जिनमें से बाइनरी गोलय कोड व्यावहारिक रुचि का है
• मैकएलीस क्रिप्टोसिस्टम में इस्तेमाल किया जाने वाला गोप्पा कोड
• हैडमार्ड कोड
• हैगलबर्गर कोड
• हैमिंग कोड
• गैर-श्वेत शोर के लिए लैटिन वर्ग आधारित कोड (उदाहरण के लिए पावरलाइन पर ब्रॉडबैंड में प्रचलित)
• लेक्सिकोग्राफिक कोड
• रैखिक नेटवर्क संकेतन, बिंदु से बिंदु लिंक के बजाय पूरे नेटवर्क में एक प्रकार का मिटाने वाला कोड
• लंबा कोड
• कम-घनत्व समता-चेक कोड, जिसे गैलेजर कोड के रूप में भी जाना जाता है, विरल ग्राफ कोड के लिए मूलरूप के रूप में
• एलटी कोड, जो लगभग इष्टतम रेटलेस इरेज़र करेक्टिंग कोड (फाउंटेन कोड) है
• एन कोड का एम
• नॉर्डस्ट्रॉम-रॉबिन्सन कोड, ज्यामिति और समूह सिद्धांत में प्रयुक्त
• ऑनलाइन कोड, एक निकट-इष्टतम रेटलेस इरेज़र करेक्टिंग कोड
• ध्रुवीय कोड (संकेतन सिद्धांत)
• रैप्टर कोड, एक निकट-इष्टतम फाउंटेन कोड
• रीड-सोलोमन त्रुटि सुधार
• रीड-मुलर कोड
• दोहराएँ-संचय कोड
• पुनरावृत्ति कोड, जैसे ट्रिपल मॉड्यूलर अतिरेक
• स्पाइनल कोड, छद्म-यादृच्छिक हैश फ़ंक्शंस पर आधारित एक रेटलेस, नॉनलाइनियर कोड
• बवंडर कोड, एक निकट-इष्टतम विलोपन कोड, और फाउंटेन कोड का अग्रदूत
• टर्बो कोड
• वॉल्श-हैडमार्ड कोड
• चक्रीय अतिरेक जाँच (सीआरसी) संदेशों के लिए अधिक से अधिक 1-बिट त्रुटियों को ठीक कर सकते हैं $2^{n-1}-1$ डिग्री के इष्टतम जनरेटर बहुपदों के लिए बिट लंबा $n$, चक्रीय अतिरेक जाँच #बिटफ़िल्टर का गणित देखें

यह भी देखें

• कोड दर
• इरेज़र कोड
• शीतल-निर्णय डिकोडर
• बर्स्ट एरर-करेक्टिंग कोड
• त्रुटि का पता लगाने और सुधार
• प्रतिक्रिया के साथ त्रुटि-सुधार कोड

आगे की पढाई

• MacWilliams, Florence Jessiem; Sloane, Neil James Alexander (2007) [1977]. Written at AT&T Shannon Labs, Florham Park, New Jersey, USA. The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Vol. 16 (digital print of 12th impression, 1st ed.). Amsterdam / London / New York / Tokyo: North-Holland / Elsevier BV. ISBN 978-0-444-85193-2. LCCN 76-41296. (xxii+762+6 pages)
• Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2.
• Arazi, Benjamin (1987). Swetman, Herb (ed.). A Commonsense Approach to the Theory of Error Correcting Codes. MIT Press Series in Computer Systems. Vol. 10 (1 ed.). Cambridge, Massachusetts, USA / London, UK: Massachusetts Institute of Technology. ISBN 0-262-01098-4. LCCN 87-21889. (x+2+208+4 pages)
• Wicker, Stephen B. (1995). Error Control Systems for Digital Communication and Storage. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-200809-2.
• Wilson, Stephen G. (1996). Digital Modulation and Coding. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-210071-1.
• "Error Correction Code in Single Level Cell NAND Flash memories" 2007-02-16
• "Error Correction Code in NAND Flash memories" 2004-11-29
• Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 2012-02-26
• Sphere Packings, Lattices and Groups, By J. H. Conway, Neil James Alexander Sloane, Springer Science & Business Media, 2013-03-09 – Mathematics – 682 pages.

इस पेज में विलुप्त आंतरिक लिंक की सूची

• बातचीत का माध्यम
• विपुल भंडारण
• ईसीसी मेमोरी
• गलती पहचानना
• विटरबी डिकोडर
• नॉइस अनुपात करने के लिए संकेत
• अनुकूली मॉड्यूलेशन और संकेतन
• स्वचालित दोहराव अनुरोध
• नैंड फ्लैश
• बहुआयामी समता-चेक कोड
• गले में कोड (बहुविकल्पी)
• बहुपदी समय फलन
• बहु स्तरीय सेल
• यात्रा कार्यक्रम
• संभाव्य रूप से जाँच योग्य प्रमाण
• स्थानीय रूप से डिकोडेबल कोड
• फटने की त्रुटि
• क्रमपरिवर्तन बहुपद
• मिथ्या
• कोड दोहराएं-जमा करें
• चक्रीय अतिरेक की जाँच
• मिटा कोड
• त्रुटि का पता लगाना और सुधार

बाहरी कड़ियाँ

• Morelos-Zaragoza, Robert (2004). "The Correcting Codes (ECC) Page". Retrieved 5 March 2006.
• lpdec: library for LP decoding and related things (Python)