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

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

पृष्ठभूमि

चैनल कोडिंग का क्षेत्र किसी दिए गए संचार चैनल पर उच्चतम संभव दर पर डेटा की एक धारा भेजने और फिर एन्कोडिंग और डिकोडिंग एल्गोरिदम का उपयोग करके रिसीवर पर मूल डेटा को विश्वसनीय रूप से डिकोड करने से संबंधित है जो किसी दिए गए तकनीक में लागू करने के लिए संभव है।

शोर-चैनल कोडिंग प्रमेय|शैनन के चैनल कोडिंग प्रमेय से पता चलता है कि कई सामान्य चैनलों पर चैनल कोडिंग योजनाएं मौजूद हैं जो सभी दरों पर विश्वसनीय रूप से डेटा संचारित करने में सक्षम हैं $R$ एक निश्चित सीमा से कम $C$, दिए गए चैनल की चैनल क्षमता कहलाती है। वास्तव में, डिकोडिंग त्रुटि की संभावना को ब्लॉक की लंबाई के रूप में तेजी से कम किया जा सकता है $N$ कोडिंग योजना अनंत तक जाती है। हालाँकि, एक सरल इष्टतम डिकोडिंग योजना की जटिलता जो कि प्रत्येक संभावित संचरित कोडवर्ड की संभावना की गणना करती है, तेजी से बढ़ जाती है $N$, इसलिए ऐसा इष्टतम डिकोडर तेजी से अव्यवहार्य हो जाता है।

अपने डॉक्टरेट थीसिस में, डेव फोर्नी ने दिखाया कि क्षमता से कम सभी डेटा दरों पर तेजी से घटती त्रुटि संभावनाओं को प्राप्त करने के लिए संयोजित कोड का उपयोग किया जा सकता है, डिकोडिंग जटिलता के साथ जो केवल बहुपद के साथ बढ़ती है कोड ब्लॉक की लंबाई.

विवरण

एक आंतरिक कोड और एक बाहरी कोड पर निर्मित संयोजित कोड का योजनाबद्ध चित्रण।

फ़ाइल: रीड का संयोजन-Solomon code with Hadamard code.svg|thumb|400px|यह एक कोड संयोजन का सचित्र प्रतिनिधित्व है, और, विशेष रूप से, n=q=4 और k=2 के साथ रीड-सोलोमन कोड का उपयोग बाहरी कोड के रूप में किया जाता है और n=q और k=log q के साथ हैडामर्ड कोड का उपयोग आंतरिक कोड के रूप में किया जाता है। कुल मिलाकर, संयोजित कोड एक है $[q^{2},k\log q]$-कोड.

चलो सी_in एक [एन, के, डी] कोड हो, यानी, लंबाई एन, आयाम (वेक्टर स्पेस) के, न्यूनतम हैमिंग दूरी डी, और कोड दर आर = के/एन का एक ब्लॉक कोड, वर्णमाला ए पर:

$C_{in}:A^{k}\rightarrow A^{n}$

चलो सी_out |B| के साथ वर्णमाला B पर एक [N, K, D] कोड हो = |ए|^क प्रतीक:

$C_{out}:B^{K}\rightarrow B^{N}$

आंतरिक कोड सी_in |ए| में से एक लेता है^क = |बी| संभावित इनपुट, ए पर एन-ट्यूपल में एनकोड करता है, ट्रांसमिट करता है, और |बी| में से किसी एक में डिकोड करता है। संभावित आउटपुट. हम इसे एक (सुपर) चैनल के रूप में मानते हैं जो वर्णमाला बी से एक प्रतीक को प्रसारित कर सकता है। हम इस चैनल का उपयोग सी के कोडवर्ड में प्रत्येक एन प्रतीक को प्रसारित करने के लिए एन बार करते हैं।_out. सी का संयोजन_out (बाहरी कोड के रूप में) सी के साथ_in (आंतरिक कोड के रूप में), सी दर्शाया गया है_out∘C_in, क्या यह वर्णमाला A के ऊपर N लंबाई की एक राग है::$C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}$ यह प्रत्येक इनपुट संदेश m = (m) को मैप करता है₁, एम₂, ..., एम_K) एक कोडवर्ड के लिए (सी_in(एम<नोविकी>'</नोविकी>₁), सी_in(एम<नोविकी>'</नोविकी>₂), ..., सी_in(एम<नोविकी>'</नोविकी>_N)), कहाँ (m'₁, म'₂, ..., म<नोविकी>'</नोविकी>_N) = सी_out(एम₁, एम₂, ..., एम_K).

इस दृष्टिकोण में मुख्य अंतर्दृष्टि यह है कि यदि सी_in अधिकतम संभावना डिकोडिंग|अधिकतम-संभावना दृष्टिकोण का उपयोग करके डिकोड किया जाता है (इस प्रकार बढ़ती लंबाई के साथ तेजी से घटती त्रुटि संभावना दिखाई देती है), और सी_out लंबाई N = 2 वाला एक कोड है^nr जिसे N के बहुपद समय में डिकोड किया जा सकता है, फिर संयोजित कोड को उसकी संयुक्त लंबाई n2 के बहुपद समय में डिकोड किया जा सकता है^nr = O संकेतन(N⋅log(N)) और तेजी से घटती त्रुटि संभावना को दर्शाता है, भले ही C_in इसमें घातीय डिकोडिंग जटिलता है।इस पर अनुभाग #डिकोडिंग संयोजित कोड में अधिक विस्तार से चर्चा की गई है।

उपरोक्त संयोजन के सामान्यीकरण में, एन संभावित आंतरिक कोड सी हैं_in,i और C के कोडवर्ड में i-th प्रतीक_out i-वें आंतरिक कोड का उपयोग करके आंतरिक चैनल में प्रसारित किया जाता है। जस्टसेन कोड सामान्यीकृत संयोजित कोड के उदाहरण हैं, जहां बाहरी कोड रीड-सोलोमन कोड है।

गुण

1. संयोजित कोड C की दूरी_out∘C_in कम से कम dD है, अर्थात, यह D' ≥ dD के साथ एक [nN, kK, D'] कोड है।

सबूत: दो अलग-अलग संदेशों पर विचार करें एम¹≠ मी²∈बी^क मान लीजिए Δ दो कोडवर्ड के बीच की दूरी को दर्शाता है। तब

$\Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.$

इस प्रकार, कम से कम डी स्थितियाँ हैं जिनमें कोडवर्ड सी के एन प्रतीकों का क्रम है_out(एम¹) और सी_out(एम²) भिन्न। इन पदों के लिए, निरूपित i, हमारे पास है

$\Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.$

नतीजतन, वर्णमाला A से लिए गए n⋅N प्रतीकों के अनुक्रम में कम से कम d⋅D स्थितियाँ हैं जिनमें दो कोडवर्ड भिन्न हैं, और इसलिए

$\Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.$

2. यदि सी_out और सी_in रैखिक ब्लॉक कोड हैं, फिर C_out∘C_in यह एक रैखिक ब्लॉक कोड भी है।

सी के जनरेटर मैट्रिक्स के संदर्भ में संयोजित कोड के लिए जनरेटर मैट्रिक्स को परिभाषित करने के विचार के आधार पर इस संपत्ति को आसानी से दिखाया जा सकता है।_out और सी_in.

संघटित कोडों को डिकोड करना

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

विस्तार से, मान लीजिए कि डिकोडर का इनपुट वेक्टर y = (y) है₁, ..., और_N) ∈ (एⁿ)^एन. फिर डिकोडिंग एल्गोरिदम दो चरणों वाली प्रक्रिया है:

1. आंतरिक कोड सी के एमएलडी का उपयोग करें_in आंतरिक कोड शब्दों के एक सेट को फिर से बनाने के लिए y' = (y'₁, ..., y'_N), y' के साथ_i = अरब_{Cin</उप>(औरi), 1 ≤ मैं ≤ एन.}
2. C के लिए अद्वितीय डिकोडिंग एल्गोरिदम चलाएँ_out y' पर।

अब, पहले चरण की समय जटिलता O संकेतन(N⋅exp(n)) है, जहां n = O(log(N)) आंतरिक ब्लॉक लंबाई है। दूसरे शब्दों में, यह एन है^O(1) (यानी, बहुपद-समय) बाहरी ब्लॉक लंबाई N के संदर्भ में। चूंकि चरण दो में बाहरी डिकोडिंग एल्गोरिदम को बहुपद समय में चलने के लिए माना जाता है, इसलिए समग्र डिकोडिंग एल्गोरिदम की जटिलता भी बहुपद-समय है।

टिप्पणियाँ

ऊपर वर्णित डिकोडिंग एल्गोरिदम का उपयोग dD/4 से कम संख्या तक की सभी त्रुटियों को ठीक करने के लिए किया जा सकता है। न्यूनतम दूरी डिकोडिंग का उपयोग करके, बाहरी डिकोडर D/2 से कम प्रतीकों y' के साथ सभी इनपुट y' को सही कर सकता है।_i ग़लती में। इसी प्रकार, आंतरिक कोड किसी इनपुट y को विश्वसनीय रूप से सही कर सकता है_i यदि d/2 से कम है तो आंतरिक प्रतीक गलत हैं। इस प्रकार, एक बाहरी प्रतीक के लिए y'_i आंतरिक डिकोडिंग के बाद गलत होने के लिए कम से कम डी/2 आंतरिक प्रतीकों में त्रुटि होनी चाहिए, और बाहरी कोड के विफल होने के लिए कम से कम डी/2 बाहरी प्रतीकों के लिए ऐसा होना चाहिए। नतीजतन, संयोजित कोड के विफल होने के लिए गलत तरीके से प्राप्त होने वाले आंतरिक प्रतीकों की कुल संख्या कम से कम d/2⋅D/2 = dD/4 होनी चाहिए।

यदि आंतरिक कोड अलग-अलग हैं, तो एल्गोरिदम भी काम करता है, उदाहरण के लिए, जस्टेसन कोड के लिए। फ़ोर्नी द्वारा विकसित सामान्यीकृत न्यूनतम दूरी डिकोडिंग का उपयोग dD/2 त्रुटियों तक को ठीक करने के लिए किया जा सकता है। यह बाहरी कोड के प्रदर्शन को बेहतर बनाने के लिए आंतरिक कोड से मिटाने का कोड जानकारी का उपयोग करता है, और नरम-निर्णय डिकोडिंग का उपयोग करने वाले एल्गोरिदम का पहला उदाहरण था।

अनुप्रयोग

हालाँकि 1971 मेरिनर 8 मार्स ऑर्बिटर मिशन के लिए एक सरल संयोजन योजना पहले ही लागू कर दी गई थी,वोयाजर कार्यक्रम के साथ डीप स्पेस नेटवर्क संचार के लिए नियमित रूप से संयोजित कोड का उपयोग किया जाने लगा, जिसने 1977 में दो अंतरिक्ष जांच लॉन्च कीं। तब से, संयोजित कोड कुशल त्रुटि सुधार कोडिंग के लिए वर्कहॉर्स बन गए, और कम से कम टर्बो कोड और एलडीपीसी कोड के आविष्कार तक बने रहे।

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

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

टर्बो कोड: एक समानांतर संयोजन दृष्टिकोण

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

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

यह भी देखें

• जस्टसेन कोड
• ज़ायब्लोव बाध्य
• सिंगलटन बाध्य
• गिल्बर्ट-वार्शमोव बाध्य

अग्रिम पठन

• Shu Lin; Daniel J. Costello Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. pp. 278–280. ISBN 978-0-13-283796-5.
• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 307–316. ISBN 978-0-444-85193-2.

बाहरी संबंध

• Dave Forney (ed.). "Concatenated codes". Scholarpedia.
• University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra