संयोजित त्रुटि सुधार कोड: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
[[कोडिंग सिद्धांत]] में, संयोजित कोड त्रुटि-सुधार करने वाले कोड का वर्ग बनाते हैं जो आंतरिक कोड और बाहरी कोड के संयोजन से प्राप्त होते हैं। उनकी कल्पना 1966 में [[डेव फोर्नी]] द्वारा ऐसे कोड को खोजने की समस्या के समाधान के रूप में की गई थी जिसमें बढ़ती ब्लॉक लंबाई और बहुपद-समय डिकोडिंग [[कम्प्यूटेशनल जटिलता सिद्धांत]] के साथ त्रुटि की संभावना तेजी से कम हो रही है।<ref name="Forney">
[[कोडिंग सिद्धांत]] में, '''संयोजित कोड''' त्रुटि-सुधार करने वाले कोड का वर्ग बनाते हैं जो आंतरिक कोड और बाहरी कोड के संयोजन से प्राप्त होते हैं। उनकी कल्पना 1966 में [[डेव फोर्नी]] द्वारा ऐसे कोड को खोजने की समस्या के समाधान के रूप में की गई थी इस प्रकार जिसमें बढ़ती ब्लॉक लंबाई और बहुपद-समय डिकोडिंग [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल काम्प्लेक्स सिद्धांत]] के साथ त्रुटि की संभावना तेजी से कम हो रही है।<ref name="Forney">
{{cite journal
{{cite journal
|author=G. D. Forney
|author=G. D. Forney
Line 8: Line 8:
|year=1967
|year=1967
}}
}}
</ref>
</ref> इस प्रकार 1970 के दशक में अंतरिक्ष संचार में कॉनटेनेटेड कोड का व्यापक रूप से उपयोग किया जाने लगा था।
1970 के दशक में अंतरिक्ष संचार में कॉनटेनेटेड कोड का व्यापक रूप से उपयोग किया जाने लगा।


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


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


अपने [https://web.archive.org/web/20121012080412/http://mitpress.mit.edu/catalog/item/default.asp?tid=5813&ttype=2 डॉक्टरेट थीसिस] में, डेव फोर्नी ने दिखाया कि क्षमता से कम सभी डेटा दरों पर तेजी से घटती त्रुटि संभावनाओं को प्राप्त करने के लिए संयोजित कोड का उपयोग किया जा सकता है, डिकोडिंग जटिलता के साथ जो केवल बहुपद के साथ बढ़ती है कोड ब्लॉक की लंबाई.
 
अपने [https://web.archive.org/web/20121012080412/http://mitpress.mit.edu/catalog/item/default.asp?tid=5813&ttype=2 डॉक्टरेट थीसिस] में, डेव फोर्नी ने दिखाया कि क्षमता से कम सभी डेटा दरों पर तेजी से घटती त्रुटि संभावनाओं को प्राप्त करने के लिए संयोजित कोड का उपयोग किया जा सकता है, डिकोडिंग काम्प्लेक्स के साथ जो कोड ब्लॉक लंबाई के साथ केवल बहुपद रूप से बढ़ती है।


==विवरण==
==विवरण==
[[File:Concatenated codes diagram.png|thumb|upright=2|एक आंतरिक कोड और बाहरी कोड पर निर्मित संयोजित कोड का योजनाबद्ध चित्रण।]]फ़ाइल: रीड का संयोजन-Solomon code with Hadamard code.svg|thumb|400px|यह कोड संयोजन का सचित्र प्रतिनिधित्व है, और, विशेष रूप से, n=q=4 और k=2 के साथ रीड-सोलोमन कोड का उपयोग बाहरी कोड के रूप में किया जाता है और n=q और k=log q के साथ [[हैडामर्ड कोड]] का उपयोग आंतरिक कोड के रूप में किया जाता है। कुल मिलाकर, संयोजित कोड है <math>[q^2,k \log q]</math>-कोड.
[[File:Concatenated codes diagram.png|thumb|upright=2|एक आंतरिक कोड और बाहरी कोड पर निर्मित संयोजित कोड का योजनाबद्ध चित्रण।]]'''फ़ाइल: रीड का संयोजन-Solomon code with Hadamard code.svg|thumb|400px|'''


चलो सी<sub>''in''</sub> [एन, के, डी] कोड हो, यानी, लंबाई एन, आयाम (वेक्टर स्पेस) के, न्यूनतम [[हैमिंग दूरी]] डी, और [[कोड दर]] आर = के/एन का [[ब्लॉक कोड]], वर्णमाला ए पर:
 
यह कोड संयोजन का सचित्र प्रतिनिधित्व है, और, विशेष रूप से, n=q=4 और k=2 के साथ रीड-सोलोमन कोड का उपयोग बाहरी कोड के रूप में किया जाता है और इस प्रकार n=q और k=log q के साथ [[हैडामर्ड कोड]] का उपयोग आंतरिक कोड के रूप में किया जाता है। कुल मिलाकर, संयोजित कोड <math>[q^2,k \log q]</math>-कोड है
 
 
मान लीजिए C<sub>''in''</sub> एक [n, k, d] कोड है जो लंबाई n आयाम k, न्यूनतम [[हैमिंग दूरी]] d और वर्णमाला A पर दर r = k/n का एक [[ब्लॉक कोड]] है:
:<math>C_{in}: A^k \rightarrow A^n</math>
:<math>C_{in}: A^k \rightarrow A^n</math>
चलो सी<sub>''out''</sub> |B| के साथ वर्णमाला B पर [N, K, D] कोड हो = |ए|<sup>क</sup> प्रतीक:
मान लीजिए C<sub>''out''</sub> |B| के साथ वर्णमाला B पर एक [N, K, D] कोड है = |A| के प्रतीक:
:<math>C_{out}: B^K \rightarrow B^N</math>
:<math>C_{out}: B^K \rightarrow B^N</math>
आंतरिक कोड सी<sub>''in''</sub> |ए| में से लेता है<sup>क</sup> = |बी| संभावित इनपुट, ए पर एन-ट्यूपल में एनकोड करता है, ट्रांसमिट करता है, और |बी| में से किसी में डिकोड करता है। संभावित आउटपुट. हम इसे (सुपर) चैनल के रूप में मानते हैं जो वर्णमाला बी से प्रतीक को प्रसारित कर सकता है। हम इस चैनल का उपयोग सी के कोडवर्ड में प्रत्येक एन प्रतीक को प्रसारित करने के लिए एन बार करते हैं।<sub>''out''</sub>. सी का संयोजन<sub>''out''</sub> (बाहरी कोड के रूप में) सी के साथ<sub>''in''</sub> (आंतरिक कोड के रूप में), सी दर्शाया गया है<sub>''out''</sub>∘C<sub>''in''</sub>, क्या यह वर्णमाला A के ऊपर N लंबाई की राग है:<ref name="Forney"/>:<math>C_{out} \circ C_{in}: A^{kK} \rightarrow A^{nN}</math>
आंतरिक कोड C<sub>''in''</sub> |A|<sup>K</sup> = |B| में से एक लेता है संभावित इनपुट A ट्रांसमिट पर N-टुपल में एनकोड होता है, और |B| में से एक में डीकोड होता है संभावित आउटपुट. हम इसे एक (सुपर) चैनल के रूप में मानते हैं जो वर्णमाला B से एक प्रतीक को प्रसारित कर सकता है। हम इस चैनल का उपयोग N प्रतीकों में से प्रत्येक को कोउट के कोडवर्ड में प्रसारित करने के लिए N बार करते हैं। C<sub>''out''</sub> (बाहरी कोड के रूप में) का Cin (आंतरिक कोड के रूप में) के साथ संयोजन, जिसे C<sub>''out''</sub>∘C<sub>''in''</sub> कहा जाता है, इस प्रकार वर्णमाला A पर लंबाई N का एक कोड है:<ref name="Forney" />
यह प्रत्येक इनपुट संदेश m = (m) को मैप करता है<sub>1</sub>, एम<sub>2</sub>, ..., एम<sub>K</sub>) कोडवर्ड के लिए (सी<sub>''in''</sub>(एम<नोविकी>'</नोविकी><sub>1</sub>), सी<sub>''in''</sub>(एम<नोविकी>'</नोविकी><sub>2</sub>), ..., सी<sub>''in''</sub>(एम<नोविकी>'</नोविकी><sub>N</sub>)),
कहाँ (m<nowiki>'</nowiki><sub>1</sub>, म<nowiki>'</nowiki><sub>2</sub>, ..., म<नोविकी>'</नोविकी><sub>N</sub>) = सी<sub>''out''</sub>(एम<sub>1</sub>, एम<sub>2</sub>, ..., एम<sub>K</sub>).


इस दृष्टिकोण में मुख्य अंतर्दृष्टि यह है कि यदि सी<sub>''in''</sub> [[अधिकतम संभावना डिकोडिंग]]|अधिकतम-संभावना दृष्टिकोण का उपयोग करके डिकोड किया जाता है (इस प्रकार बढ़ती लंबाई के साथ तेजी से घटती त्रुटि संभावना दिखाई देती है), और सी<sub>''out''</sub> लंबाई N = 2 वाला कोड है<sup>nr</sup> जिसे N के बहुपद समय में डिकोड किया जा सकता है, फिर संयोजित कोड को उसकी संयुक्त लंबाई n2 के बहुपद समय में डिकोड किया जा सकता है<sup>nr</sup> = O संकेतन(N⋅log(N)) और तेजी से घटती त्रुटि संभावना को दर्शाता है, भले ही C<sub>''in''</sub> इसमें घातीय डिकोडिंग जटिलता है।<ref name="Forney"/>इस पर अनुभाग #डिकोडिंग संयोजित कोड में अधिक विस्तार से चर्चा की गई है।
<math>C_{out} \circ C_{in}: A^{kK} \rightarrow A^{nN}</math>


उपरोक्त संयोजन के सामान्यीकरण में, एन संभावित आंतरिक कोड सी हैं<sub>''in'',''i''</sub> और C के कोडवर्ड में i-th प्रतीक<sub>''out''</sub> i-वें आंतरिक कोड का उपयोग करके आंतरिक चैनल में प्रसारित किया जाता है। [[जस्टसेन कोड]] सामान्यीकृत संयोजित कोड के उदाहरण हैं, जहां बाहरी कोड रीड-सोलोमन कोड है।
यह प्रत्येक इनपुट संदेश ''m'' = (''m''<sub>1</sub>, ''m''<sub>2</sub>, ..., ''m''<sub>K</sub>) को एक कोडवर्ड (''C<sub>in</sub>''(''m''<nowiki/>'<sub>1</sub>), ''C<sub>in</sub>''(''m''<nowiki/>'<sub>2</sub>), ..., ''C<sub>in</sub>''(''m''<nowiki/>'<sub>N</sub>)) पर मैप करता है जहां (''m''<nowiki/>'<sub>1</sub>, ''m''<nowiki/>'<sub>2</sub>, ..., ''m''<nowiki/>'<sub>N</sub>) = ''C<sub>out</sub>''(''m''<sub>1</sub>, ''m''<sub>2</sub>, ..., ''m''<sub>K</sub>) है।
 
 
इस डिकोडिंग में मुख्य अंतर्दृष्टि यह है कि यदि C<sub>''in''</sub> को अधिकतम-संभावना डिकोडिंग का उपयोग करके डिकोड किया जाता है (इस प्रकार बढ़ती लंबाई के साथ तेजी से घटती त्रुटि संभावना दिखाई देती है) और C<sub>''out''</sub> लंबाई N = 2<sup>nr</sup> वाला एक कोड है जिसे N के बहुपद समय में डिकोड किया जा सकता है संयोजित कोड को उसकी संयुक्त लंबाई n2<sup>nr</sup> = O(N⋅log(N)) के बहुपद समय में डिकोड किया जा सकता है और इस प्रकार C<sub>''in''</sub> में घातीय डिकोडिंग काम्प्लेक्स होने पर भी त्रुटि की संभावना तेजी से घटती हुई दिखाई देती है।<ref name="Forney" /> इस पर अनुभाग डिकोडिंग संयोजित कोड में अधिक विस्तार से चर्चा की गई है।
 
उपरोक्त संयोजन के सामान्यीकरण में N संभावित आंतरिक कोड C<sub>''in'',''i''</sub> हैं और C<sub>''out''</sub> के कोडवर्ड में i-th प्रतीक को i-th आंतरिक कोड का उपयोग करके आंतरिक चैनल में प्रसारित किया जाता है। [[जस्टसेन कोड]] सामान्यीकृत संयोजित कोड के उदाहरण हैं, जहां बाहरी कोड रीड-सोलोमन कोड है।


==गुण==
==गुण==
1. संयोजित कोड ''C'' की दूरी<sub>''out''</sub>∘C<sub>''in''</sub> कम से कम dD है, अर्थात, यह D<nowiki>'</nowiki> ≥ dD के साथ [nN, kK, D<nowiki>'</nowiki>] कोड है।
1. संयोजित कोड C<sub>''out''</sub>∘C<sub>''in''</sub> की दूरी कम से कम dD है, अर्थात यह D' ≥ dD वाला एक [nN, kK, D'] कोड है।


सबूत:
प्रमाण: दो अलग-अलग संदेशों पर विचार करें m<sup>1</sup> ≠ m<sup>2</sup> ∈ B''<sup>K</sup>''। मान लीजिए Δ दो कोडवर्ड के बीच की दूरी को दर्शाता है। तब
दो अलग-अलग संदेशों पर विचार करें एम<sup>1</sup>≠ मी<sup>2</sup>∈बी<sup>क</sup> मान लीजिए Δ दो कोडवर्ड के बीच की दूरी को दर्शाता है। तब
:<math>\Delta(C_{out}(m^1), C_{out}(m^2)) \ge D.</math>
:<math>\Delta(C_{out}(m^1), C_{out}(m^2)) \ge D.</math>
इस प्रकार, कम से कम डी स्थितियाँ हैं जिनमें कोडवर्ड सी के एन प्रतीकों का क्रम है<sub>''out''</sub>(एम<sup>1</sup>) और सी<sub>''out''</sub>(एम<sup>2</sup>) भिन्न। इन पदों के लिए, निरूपित i, हमारे पास है
इस प्रकार कम से कम D स्थितियाँ हैं जिनमें कोडवर्ड C<sub>''out''</sub>(m<sup>1</sup>) और C<sub>''out''</sub>(m<sup>2</sup>) के N प्रतीकों का क्रम भिन्न है। इन पदों के लिए मेरे पास निरूपित i है
 
:<math>\Delta(C_{in}(C_{out}(m^1)_i), C_{in}(C_{out}(m^2)_i)) \ge d.</math>
:<math>\Delta(C_{in}(C_{out}(m^1)_i), C_{in}(C_{out}(m^2)_i)) \ge d.</math>
नतीजतन, वर्णमाला A से लिए गए n⋅N प्रतीकों के अनुक्रम में कम से कम d⋅D स्थितियाँ हैं जिनमें दो कोडवर्ड भिन्न हैं, और इसलिए
परिणाम स्वरुप, वर्णमाला A से लिए गए n⋅N प्रतीकों के अनुक्रम में कम से कम d⋅D स्थितियाँ हैं जिनमें दो कोडवर्ड भिन्न हैं, और इसलिए
:<math>\Delta(C_{in}(C_{out}(m^1)), C_{in}(C_{out}(m^2))) \ge dD.</math>
:<math>\Delta(C_{in}(C_{out}(m^1)), C_{in}(C_{out}(m^2))) \ge dD.</math>
2. यदि ''सी''<sub>''out''</sub> और सी<sub>''in''</sub> [[रैखिक ब्लॉक कोड]] हैं, फिर C<sub>''out''</sub>∘C<sub>''in''</sub> यह रैखिक ब्लॉक कोड भी है।
2. यदि C<sub>''out''</sub> और C<sub>''in''</sub> [[रैखिक ब्लॉक कोड]] हैं तो C<sub>''out''</sub>∘C<sub>''in''</sub> भी एक रैखिक ब्लॉक कोड है।


सी के [[जनरेटर मैट्रिक्स]] के संदर्भ में संयोजित कोड के लिए जनरेटर मैट्रिक्स को परिभाषित करने के विचार के आधार पर इस संपत्ति को आसानी से दिखाया जा सकता है।<sub>''out''</sub> और सी<sub>''in''</sub>.
 
C<sub>''out''</sub> और सी<sub>''in''</sub> के [[जनरेटर मैट्रिक्स]] के संदर्भ में संयोजित कोड के लिए जनरेटर मैट्रिक्स को परिभाषित करने के विचार के आधार पर इस संपत्ति को सरलता से दिखाया जा सकता है।


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


संयोजित कोड के लिए डिकोडिंग एल्गोरिदम की प्राकृतिक अवधारणा पहले आंतरिक कोड और फिर बाहरी कोड को डिकोड करना है। एल्गोरिदम के व्यावहारिक होने के लिए अंतिम ब्लॉक लंबाई में बहुपद-समय होना चाहिए। विचार करें कि बाहरी कोड के लिए बहुपद-समय अद्वितीय डिकोडिंग एल्गोरिदम है। अब हमें आंतरिक कोड के लिए बहुपद-समय डिकोडिंग एल्गोरिदम ढूंढना होगा। यह समझा जाता है कि यहां बहुपद चलने का समय का अर्थ है कि अंतिम ब्लॉक लंबाई में चलने का समय बहुपद है। मुख्य विचार यह है कि यदि आंतरिक ब्लॉक की लंबाई को बाहरी कोड के आकार में लघुगणक के रूप में चुना जाता है तो आंतरिक कोड के लिए डिकोडिंग एल्गोरिदम आंतरिक ब्लॉक की लंबाई के [[घातीय समय]] में चल सकता है, और इस प्रकार हम आंतरिक कोड के लिए घातीय-समय लेकिन इष्टतम डिकोडिंग विधियों # अधिकतम संभावना डिकोडिंग (एमएलडी) का उपयोग कर सकते हैं।
संयोजित कोड के लिए डिकोडिंग एल्गोरिदम की प्राकृतिक अवधारणा पहले आंतरिक कोड और फिर बाहरी कोड को डिकोड करना है। इस प्रकार एल्गोरिदम के व्यावहारिक होने के लिए अंतिम ब्लॉक लंबाई में बहुपद-समय होना चाहिए। विचार करें कि बाहरी कोड के लिए बहुपद-समय अद्वितीय डिकोडिंग एल्गोरिदम है। अब हमें आंतरिक कोड के लिए बहुपद-समय डिकोडिंग एल्गोरिदम खोजना होता है। यह समझा जाता है कि यहां बहुपद चलने का समय का अर्थ है कि अंतिम ब्लॉक लंबाई में चलने का समय बहुपद है। मुख्य विचार यह है कि यदि आंतरिक ब्लॉक की लंबाई को बाहरी कोड के आकार में लघुगणक के रूप में चुना जाता है तो आंतरिक कोड के लिए डिकोडिंग एल्गोरिदम आंतरिक ब्लॉक की लंबाई के [[घातीय समय]] में चल सकता है, और इस प्रकार हम आंतरिक कोड के लिए घातीय-समय किन्तु इष्टतम डिकोडिंग विधियों या अधिकतम संभावना डिकोडिंग (एमएलडी) का उपयोग कर सकते हैं।
 
विस्तार से, मान लीजिए कि डिकोडर का इनपुट वेक्टर y = (y<sub>1</sub>, ..., y''<sub>N</sub>'') ∈ (A<sup>n</sup>)<sup>n</sup> है। फिर डिकोडिंग एल्गोरिदम दो चरणों वाली प्रक्रिया है:
#आंतरिक कोड शब्दों y' = (y'<sub>1</sub>, ..., y'<sub>''N''</sub>) के एक सेट को y'<sub>''i''</sub> = MLDC<sub><sub>in</sub>(y<sub>''i''</sub>) 1 ≤ i ≤ N के साथ फिर से बनाने के लिए आंतरिक कोड C<sub><sub>in</sub> के MLD का उपयोग करें।
#C<sub>out</sub> y<nowiki>'</nowiki>' के लिए अद्वितीय डिकोडिंग एल्गोरिदम चलाएँ।


विस्तार से, मान लीजिए कि डिकोडर का इनपुट वेक्टर y = (y) है<sub>1</sub>, ..., और<sub>''N''</sub>) ∈ (ए<sup>n</sup>)<sup>एन</sup>. फिर डिकोडिंग एल्गोरिदम दो चरणों वाली प्रक्रिया है:
अब, पहले चरण की समय काम्प्लेक्स O संकेतन(N⋅exp(n)) है, जहां n = O(log(N)) आंतरिक ब्लॉक लंबाई है। दूसरे शब्दों में, यह N है<sup>O(1)</sup> (अर्थात, बहुपद-समय) बाहरी ब्लॉक लंबाई N के संदर्भ में। चूंकि चरण दो में बाहरी डिकोडिंग एल्गोरिदम को बहुपद समय में चलने के लिए माना जाता है, इसलिए समग्र डिकोडिंग एल्गोरिदम की काम्प्लेक्स भी बहुपद-समय है।
# आंतरिक कोड सी के एमएलडी का उपयोग करें<sub>in</sub> आंतरिक कोड शब्दों के सेट को फिर से बनाने के लिए y<nowiki>'</nowiki> = (y<nowiki>'</nowiki><sub>1</sub>, ..., y<nowiki>'</nowiki><sub>''N''</sub>), y<nowiki>'</nowiki> के साथ<sub>''i''</sub> = अरब<sub>''C''<sub>in</sub></उप>(और<sub>i</sub>), 1 ≤ मैं ≤ एन.
# C के लिए अद्वितीय डिकोडिंग एल्गोरिदम चलाएँ<sub>out</sub> y<nowiki>'</nowiki> पर।


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


===टिप्पणियाँ===
===टिप्पणियाँ===


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


यदि आंतरिक कोड अलग-अलग हैं, तो एल्गोरिदम भी काम करता है, उदाहरण के लिए, जस्टेसन कोड के लिए। फ़ोर्नी द्वारा विकसित [[सामान्यीकृत न्यूनतम दूरी डिकोडिंग]] का उपयोग dD/2 त्रुटियों तक को ठीक करने के लिए किया जा सकता है।<ref name="gmd">
यदि आंतरिक कोड अलग-अलग हैं, तो एल्गोरिदम भी काम करता है, उदाहरण के लिए, जस्टेसन कोड के लिए फ़ोर्नी द्वारा विकसित [[सामान्यीकृत न्यूनतम दूरी डिकोडिंग]] का उपयोग dD/2 त्रुटियों तक को ठीक करने के लिए किया जा सकता है।<ref name="gmd">
{{cite journal
{{cite journal
|first=G. David
|first=G. David
Line 73: Line 83:
|doi=10.1109/TIT.1966.1053873
|doi=10.1109/TIT.1966.1053873
}}</ref>
}}</ref>
यह बाहरी कोड के प्रदर्शन को बेहतर बनाने के लिए आंतरिक कोड से [[मिटाने का कोड]] जानकारी का उपयोग करता है, और [[ नरम-निर्णय डिकोडिंग |नरम-निर्णय डिकोडिंग]] का उपयोग करने वाले एल्गोरिदम का पहला उदाहरण था।<ref>{{cite journal
 
यह बाहरी कोड के प्रदर्शन को उत्तम बनाने के लिए आंतरिक कोड से [[मिटाने का कोड|विलोपन कोड]] जानकारी का उपयोग करता है, और इस प्रकार सॉफ्ट-डिसीजन डिकोडिंग का उपयोग करने वाले एल्गोरिदम का पहला उदाहरण था।<ref>{{cite journal
|first1=Christopher C.H.
|first1=Christopher C.H.
|last1=Yu
|last1=Yu
Line 99: Line 110:
|s2cid=8338433
|s2cid=8338433
}}</ref>
}}</ref>




==अनुप्रयोग==
==अनुप्रयोग==
हालाँकि 1971 [[मेरिनर 8]] मार्स ऑर्बिटर मिशन के लिए सरल संयोजन योजना पहले ही लागू कर दी गई थी,<ref name="McEliece"/>वोयाजर कार्यक्रम के साथ [[डीप स्पेस नेटवर्क]] संचार के लिए नियमित रूप से संयोजित कोड का उपयोग किया जाने लगा, जिसने 1977 में दो अंतरिक्ष जांच लॉन्च कीं।<ref name="deep-space-codes">K. Andrews et al., ''The Development of Turbo and LDPC Codes for Deep-Space Applications'', Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.</ref> तब से, संयोजित कोड कुशल त्रुटि सुधार कोडिंग के लिए वर्कहॉर्स बन गए, और कम से कम [[टर्बो कोड]] और [[एलडीपीसी कोड]] के आविष्कार तक बने रहे।<ref name="McEliece"/><ref name="deep-space-codes"/>
चूँकि 1971 [[मेरिनर 8]] मार्स ऑर्बिटर मिशन के लिए सरल संयोजन योजना पहले ही प्रयुक्त कर दी गई थी,<ref name="McEliece"/> वोयाजर प्रोग्राम के साथ [[डीप स्पेस नेटवर्क]] संचार के लिए नियमित रूप से संयोजित कोड का उपयोग किया जाने लगा था, जिसने 1977 में दो अंतरिक्ष अन्वेषण लॉन्च कीं थी।<ref name="deep-space-codes">K. Andrews et al., ''The Development of Turbo and LDPC Codes for Deep-Space Applications'', Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.</ref> तब से, संयोजित कोड कुशल त्रुटि सुधार कोडिंग के लिए वर्कहॉर्स बन गए, और कम से कम [[टर्बो कोड]] और [[एलडीपीसी कोड]] के आविष्कार तक बने रहे थे।<ref name="McEliece"/><ref name="deep-space-codes"/>


आमतौर पर, आंतरिक कोड ब्लॉक कोड नहीं है, बल्कि [[ नरम-निर्णय डिकोडर |नरम-निर्णय डिकोडर]] है|<ref name="Odenwalder">
सामान्यतः, आंतरिक कोड ब्लॉक कोड नहीं है, किन्तु [[ नरम-निर्णय डिकोडर |सॉफ्ट-डिसीजन कन्वेन्शनल विटरबी-डिकोडेड]] है |<ref name="Odenwalder">
{{cite journal
{{cite journal
|author=J. P. Odenwalder
|author=J. P. Odenwalder
Line 111: Line 123:
|year=1970
|year=1970
}}
}}
</ref>
</ref> बाहरी कोड के लिए, लंबा हार्ड-डिसीजन ब्लॉक कोड, अक्सर आठ-बिट प्रतीकों वाला [[रीड-सोलोमन कोड]] का उपयोग किया जाता है।<ref name="Forney"/><ref name="McEliece">
बाहरी कोड के लिए, लंबा हार्ड-डिसीजन ब्लॉक कोड, अक्सर आठ-बिट प्रतीकों वाला [[रीड-सोलोमन कोड]] का उपयोग किया जाता है।<ref name="Forney"/><ref name="McEliece">
{{cite journal
{{cite journal
|author1=Robert J. McEliece
|author1=Robert J. McEliece
Line 122: Line 133:
}}
}}
</ref>
</ref>
बड़ा प्रतीक आकार बाहरी कोड को [[त्रुटि विस्फोट]]ों के प्रति अधिक मजबूत बनाता है जो चैनल की खराबी के कारण हो सकता है, और इसलिए भी क्योंकि कन्वेन्शनल कोड का गलत आउटपुट स्वयं फट जाता है।<ref name="Forney"/><ref name="McEliece"/>एक फॉरवर्ड एरर करेक्शन#इंटरलीविंग को आम तौर पर दो कोडों के बीच जोड़ा जाता है ताकि एरर बर्स्ट को व्यापक रेंज में फैलाया जा सके।<ref name="McEliece"/>


बाहरी रीड-सोलोमन कोड (जिसे आरएसवी कोड के रूप में जाना जाता है) के साथ आंतरिक विटर्बी कनवल्शनल कोड का संयोजन पहली बार वोयाजर 2 में इस्तेमाल किया गया था,<ref name="McEliece"/><ref>R. Ludwig, J. Taylor, [http://descanso.jpl.nasa.gov/DPSummary/Descanso4--Voyager_new.pdf Voyager Telecommunications Manual], [[JPL]] DESCANSO ''(Design and Performance Summary Series)'', March 2002.</ref> और यह अंतरिक्ष क्षेत्र के भीतर और बाहर दोनों जगह लोकप्रिय निर्माण बन गया। यह आज भी [[उपग्रह संचार]] के लिए विशेष रूप से उपयोग किया जाता है, जैसे [[डीवीबी-एस]] [[डिजिटल टेलीविजन]] प्रसारण मानक।<ref>[http://www.etsi.org/deliver/etsi_en/300400_300499/300421/01.01.02_60/en_300421v010102p.pdf Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services], [[ETSI]] EN 300 421, V1.1.2, August 1997.</ref>
बड़ा प्रतीक आकार बाहरी कोड को [[त्रुटि विस्फोट]] के प्रति अधिक सशक्त बनाता है जो चैनल की अस्तव्यस्तता के कारण हो सकता है, और इसलिए भी क्योंकि कन्वेन्शनल कोड का गलत आउटपुट स्वयं फट जाता है।<ref name="Forney" /><ref name="McEliece" /> एक फॉरवर्ड एरर करेक्शन या इंटरलीविंग को आम तौर पर दो कोडों के बीच जोड़ा जाता है जिससे एरर बर्स्ट को व्यापक रेंज में विस्तृत किया जा सकता था।<ref name="McEliece" />
शिथिल अर्थ में, दो या दो से अधिक कोड के किसी भी (क्रमिक) संयोजन को संयोजित कोड के रूप में संदर्भित किया जा सकता है। उदाहरण के लिए, [[DVB-S2]] मानक के भीतर, अत्यधिक कुशल LDPC कोड को बीजगणितीय बाहरी कोड के साथ जोड़ा जाता है ताकि आंतरिक LDPC कोड में अंतर्निहित त्रुटि स्तर के कारण बची हुई किसी भी लचीली त्रुटि को दूर किया जा सके।<ref>[http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_60/en_302307v010201p.pdf Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)], [[ETSI]] EN 302 307, V1.2.1, April 2009.</ref>
 
कॉम्पैक्ट डिस्क (सीडी) पर सरल संयोजन योजना का भी उपयोग किया जाता है, जहां विभिन्न आकारों के दो रीड-सोलोमन कोड के बीच इंटरलीविंग परत विभिन्न ब्लॉकों में त्रुटियां फैलाती है।
बाहरी रीड-सोलोमन कोड (जिसे आरएसवी कोड के रूप में जाना जाता है) के साथ आंतरिक विटर्बी कनवल्शनल कोड का संयोजन पहली बार वोयाजर 2 में इस्तेमाल किया गया था,<ref name="McEliece" /><ref>R. Ludwig, J. Taylor, [http://descanso.jpl.nasa.gov/DPSummary/Descanso4--Voyager_new.pdf Voyager Telecommunications Manual], [[JPL]] DESCANSO ''(Design and Performance Summary Series)'', March 2002.</ref> और यह अंतरिक्ष क्षेत्र के अन्दर और बाप्रत्येक दोनों जगह लोकप्रिय निर्माण बन गया था। यह आज भी [[उपग्रह संचार|सैटेलाइट संचार]] के लिए विशेष रूप से उपयोग किया जाता है, जैसे [[डीवीबी-एस]] [[डिजिटल टेलीविजन]] प्रसारण मानक <ref>[http://www.etsi.org/deliver/etsi_en/300400_300499/300421/01.01.02_60/en_300421v010102p.pdf Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services], [[ETSI]] EN 300 421, V1.1.2, August 1997.</ref> शिथिल अर्थ में, दो या दो से अधिक कोड के किसी भी (क्रमिक) संयोजन को संयोजित कोड के रूप में संदर्भित किया जा सकता है। उदाहरण के लिए, [[DVB-S2]] मानक के अन्दर, अत्यधिक कुशल LDPC कोड को बीजगणितीय बाहरी कोड के साथ जोड़ा जाता है जिससे आंतरिक LDPC कोड में अंतर्निहित त्रुटि स्तर के कारण बची हुई किसी भी नमी त्रुटि को दूर किया जा सकता था।<ref>[http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_60/en_302307v010201p.pdf Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)], [[ETSI]] EN 302 307, V1.2.1, April 2009.</ref>
 
इस प्रकार कॉम्पैक्ट डिस्क (सीडी) पर सरल संयोजन योजना का भी उपयोग किया जाता है, इस प्रकार जहां विभिन्न आकारों के दो रीड-सोलोमन कोड के बीच इंटरलीविंग परत विभिन्न ब्लॉकों में त्रुटियां विस्तृत होती है।
 
== [[टर्बो कोड]]: समानांतर संयोजन डिकोडिंग ==
उपरोक्त विवरण उस चीज़ के लिए दिया गया है जिसे अब क्रमिक रूप से संयोजित कोड कहा जाता है। इस प्रकार टर्बो कोड, जैसा कि पहली बार 1993 में वर्णित किया गया था, जिसने दो कन्वेन्शनल कोड के समानांतर संयोजन को प्रयुक्त किया था, जिसमें दो कोड के बीच इंटरलीवर और पुनरावृत्त डिकोडर था जो कोड के बीच जानकारी को आगे और पीछे भेजता था।<ref name="deep-space-codes" /> इस डिज़ाइन का प्रदर्शन पहले से कल्पित किसी भी संयोजित कोड से उत्तम है।


== [[टर्बो कोड]]: समानांतर संयोजन दृष्टिकोण ==
चूँकि, टर्बो कोड का प्रमुख पहलू उनका पुनरावृत्त डिकोडिंग डिकोडिंग है। इस प्रकार उच्च कोडिंग लाभ प्राप्त करने के लिए पुनरावृत्त डिकोडिंग को अब क्रमिक संयोजनों पर भी प्रयुक्त किया जाता है, जैसे कि क्रमिक रूप से संयोजित कनवल्शनल कोड (एससीसीसी) के अन्दर [[गैलीलियो (अंतरिक्ष यान)|गैलीलियो अंतरिक्ष यान]] के गैलीलियो कोड में दो से पांच पुनरावृत्तियों के साथ पुनरावृत्त डिकोडिंग का प्रारंभिक रूप प्रयुक्त किया गया था।<ref name="McEliece" />
उपरोक्त विवरण उस चीज़ के लिए दिया गया है जिसे अब क्रमिक रूप से संयोजित कोड कहा जाता है। टर्बो कोड, जैसा कि पहली बार 1993 में वर्णित किया गया था, ने दो कन्वेन्शनल कोड के समानांतर संयोजन को लागू किया, जिसमें दो कोड के बीच इंटरलीवर और पुनरावृत्त डिकोडर था जो कोड के बीच जानकारी को आगे और पीछे भेजता था।<ref name="deep-space-codes"/>इस डिज़ाइन का प्रदर्शन पहले से कल्पित किसी भी संयोजित कोड से बेहतर है।


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




Revision as of 11:30, 31 July 2023

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

पृष्ठभूमि

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

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


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

विवरण

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

फ़ाइल: रीड का संयोजन-Solomon code with Hadamard code.svg|thumb|400px|


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


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

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

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

यह प्रत्येक इनपुट संदेश m = (m1, m2, ..., mK) को एक कोडवर्ड (Cin(m'1), Cin(m'2), ..., Cin(m'N)) पर मैप करता है जहां (m'1, m'2, ..., m'N) = Cout(m1, m2, ..., mK) है।


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

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

गुण

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

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

इस प्रकार कम से कम D स्थितियाँ हैं जिनमें कोडवर्ड Cout(m1) और Cout(m2) के N प्रतीकों का क्रम भिन्न है। इन पदों के लिए मेरे पास निरूपित i है

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

2. यदि Cout और Cin रैखिक ब्लॉक कोड हैं तो Cout∘Cin भी एक रैखिक ब्लॉक कोड है।


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

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

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

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

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

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

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

टिप्पणियाँ

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

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

यह बाहरी कोड के प्रदर्शन को उत्तम बनाने के लिए आंतरिक कोड से विलोपन कोड जानकारी का उपयोग करता है, और इस प्रकार सॉफ्ट-डिसीजन डिकोडिंग का उपयोग करने वाले एल्गोरिदम का पहला उदाहरण था।[3][4]


अनुप्रयोग

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

सामान्यतः, आंतरिक कोड ब्लॉक कोड नहीं है, किन्तु सॉफ्ट-डिसीजन कन्वेन्शनल विटरबी-डिकोडेड है |[7] बाहरी कोड के लिए, लंबा हार्ड-डिसीजन ब्लॉक कोड, अक्सर आठ-बिट प्रतीकों वाला रीड-सोलोमन कोड का उपयोग किया जाता है।[1][5]

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

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

इस प्रकार कॉम्पैक्ट डिस्क (सीडी) पर सरल संयोजन योजना का भी उपयोग किया जाता है, इस प्रकार जहां विभिन्न आकारों के दो रीड-सोलोमन कोड के बीच इंटरलीविंग परत विभिन्न ब्लॉकों में त्रुटियां विस्तृत होती है।

टर्बो कोड: समानांतर संयोजन डिकोडिंग

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

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


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 G. D. Forney (1967). "Concatenated codes". Cambridge, Massachusetts: MIT Press. {{cite journal}}: Cite journal requires |journal= (help)
  2. ↑ Forney, G. David (April 1966). "Generalized Minimum Distance Decoding". IEEE Transactions on Information Theory. 12 (2): 125–131. doi:10.1109/TIT.1966.1053873.
  3. ↑ Yu, Christopher C.H.; Costello, Daniel J. (March 1980). "Generalized Minimum Distance Decoding for Qary Output Channels". IEEE Transactions on Information Theory. 26 (2): 238–243. doi:10.1109/TIT.1980.1056148.
  4. ↑ Wu, Yingquan; Hadjicostis, Christoforos (January 2007). "Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification". IEEE Transactions on Information Theory. 53 (1): 387–393. doi:10.1109/tit.2006.887478. S2CID 8338433.
  5. ↑ 5.0 5.1 5.2 5.3 5.4 5.5 5.6 Robert J. McEliece; Laif Swanson (20 August 1993). "Reed–Solomon Codes and the Exploration of the Solar System". JPL. {{cite journal}}: Cite journal requires |journal= (help)
  6. ↑ 6.0 6.1 6.2 K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
  7. ↑ J. P. Odenwalder (1970). "Optimal decoding of convolutional codes". U.C.L.A., Systems Science Dept. (dissertation). {{cite journal}}: Cite journal requires |journal= (help)
  8. ↑ R. Ludwig, J. Taylor, Voyager Telecommunications Manual, JPL DESCANSO (Design and Performance Summary Series), March 2002.
  9. ↑ Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services, ETSI EN 300 421, V1.1.2, August 1997.
  10. ↑ Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2), ETSI EN 302 307, V1.2.1, April 2009.


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संयोजित_त्रुटि_सुधार_कोड&oldid=246309’