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

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

पृष्ठभूमि

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

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

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

विवरण

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

यह कोड संयोजन का सचित्र प्रतिनिधित्व है, और, विशेष रूप से, n=q=4 और k=2 के साथ रीड-सोलोमन कोड का उपयोग बाहरी कोड के रूप में किया जाता है और इस प्रकार n=q और k=log q के साथ हैडामर्ड कोड का उपयोग आंतरिक कोड के रूप में किया जाता है। कुल मिलाकर, संयोजित कोड $[q^{2},k\log q]$-कोड है

मान लीजिए C_in एक [n, k, d] कोड है जो लंबाई n आयाम k, न्यूनतम हैमिंग दूरी d और वर्णमाला A पर दर r = k/n का एक ब्लॉक कोड है:

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

मान लीजिए C_out |B| के साथ वर्णमाला B पर एक [N, K, D] कोड है = |A| के प्रतीक है:

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

आंतरिक कोड C_in |A|^K = |B| में से एक लेता है संभावित इनपुट A ट्रांसमिट पर N-टुपल में एनकोड होता है, और |B| में से एक में डीकोड होता है संभावित आउटपुट. हम इसे एक (सुपर) चैनल के रूप में मानते हैं जो वर्णमाला B से एक प्रतीक को प्रसारित कर सकता है। हम इस चैनल का उपयोग N प्रतीकों में से प्रत्येक को कोउट के कोडवर्ड में प्रसारित करने के लिए N बार करते हैं। C_out (बाहरी कोड के रूप में) का Cin (आंतरिक कोड के रूप में) के साथ संयोजन, जिसे C_out∘C_in कहा जाता है, इस प्रकार वर्णमाला A पर लंबाई N का एक कोड है:

$C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}$

यह प्रत्येक इनपुट संदेश m = (m₁, m₂, ..., m_K) को एक कोडवर्ड (C_in(m'₁), C_in(m'₂), ..., C_in(m'_N)) पर मैप करता है जहां (m'₁, m'₂, ..., m'_N) = C_out(m₁, m₂, ..., m_K) है।

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

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

गुण

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

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

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

इस प्रकार कम से कम D स्थितियाँ हैं जिनमें कोडवर्ड C_out(m¹) और C_out(m²) के N प्रतीकों का क्रम भिन्न है। इन पदों के लिए मेरे पास निरूपित 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. यदि C_out और C_in रैखिक ब्लॉक कोड हैं तो C_out∘C_in भी एक रैखिक ब्लॉक कोड है।

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

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

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

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

1. आंतरिक कोड शब्दों y' = (y'₁, ..., y'_N) के एक सेट को y'_i = MLDC_{in(yi) 1 ≤ i ≤ N के साथ फिर से बनाने के लिए आंतरिक कोड Cin के MLD का उपयोग करें।}
2. C_out y'' के लिए अद्वितीय डिकोडिंग एल्गोरिदम चलाएँ।

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

टिप्पणियाँ

ऊपर वर्णित डिकोडिंग एल्गोरिदम का उपयोग dD/4 से कम संख्या तक की सभी त्रुटियों को ठीक करने के लिए किया जा सकता है। इस प्रकार न्यूनतम दूरी डिकोडिंग का उपयोग करके, बाहरी डिकोडर त्रुटि में D/2 प्रतीकों से कम वाले सभी इनपुट y' को सही कर सकता है। इसी प्रकार, यदि d/2 से कम आंतरिक प्रतीक गलत हैं तो आंतरिक कोड विश्वसनीय रूप से इनपुट y_i को सही कर सकता है। इस प्रकार, आंतरिक डिकोडिंग के पश्चात् बाहरी प्रतीक y'_i के गलत होने के लिए कम से कम d/2 आंतरिक प्रतीकों में त्रुटि होनी चाहिए, और बाहरी कोड के विफल होने के लिए कम से कम D/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