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

From Vigyanwiki
(Created page with "{{Use dmy dates|date=July 2014}} कोडिंग सिद्धांत में, संयोजित कोड त्रुटि-सुधार करने व...")
 
No edit summary
Line 1: Line 1:
{{Use dmy dates|date=July 2014}}
[[कोडिंग सिद्धांत]] में, संयोजित कोड त्रुटि-सुधार करने वाले कोड का वर्ग बनाते हैं जो आंतरिक कोड और बाहरी कोड के संयोजन से प्राप्त होते हैं। उनकी कल्पना 1966 में [[डेव फोर्नी]] द्वारा ऐसे कोड को खोजने की समस्या के समाधान के रूप में की गई थी जिसमें बढ़ती ब्लॉक लंबाई और बहुपद-समय डिकोडिंग [[कम्प्यूटेशनल जटिलता सिद्धांत]] के साथ त्रुटि की संभावना तेजी से कम हो रही है।<ref name="Forney">
[[कोडिंग सिद्धांत]] में, संयोजित कोड त्रुटि-सुधार करने वाले कोड का एक वर्ग बनाते हैं जो एक आंतरिक कोड और एक बाहरी कोड के संयोजन से प्राप्त होते हैं। उनकी कल्पना 1966 में [[डेव फोर्नी]] द्वारा एक ऐसे कोड को खोजने की समस्या के समाधान के रूप में की गई थी जिसमें बढ़ती ब्लॉक लंबाई और बहुपद-समय डिकोडिंग [[कम्प्यूटेशनल जटिलता सिद्धांत]] के साथ त्रुटि की संभावना तेजी से कम हो रही है।<ref name="Forney">
{{cite journal
{{cite journal
|author=G. D. Forney
|author=G. D. Forney
Line 13: Line 12:


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


शोर-चैनल कोडिंग प्रमेय|शैनन के चैनल कोडिंग प्रमेय से पता चलता है कि कई सामान्य चैनलों पर चैनल कोडिंग योजनाएं मौजूद हैं जो सभी दरों पर विश्वसनीय रूप से डेटा संचारित करने में सक्षम हैं <math>R</math> एक निश्चित सीमा से कम <math>C</math>, दिए गए चैनल की [[चैनल क्षमता]] कहलाती है। वास्तव में, डिकोडिंग त्रुटि की संभावना को ब्लॉक की लंबाई के रूप में तेजी से कम किया जा सकता है <math>N</math> कोडिंग योजना अनंत तक जाती है। हालाँकि, एक सरल इष्टतम डिकोडिंग योजना की जटिलता जो कि प्रत्येक संभावित संचरित कोडवर्ड की संभावना की गणना करती है, तेजी से बढ़ जाती है <math>N</math>, इसलिए ऐसा इष्टतम डिकोडर तेजी से अव्यवहार्य हो जाता है।
शोर-चैनल कोडिंग प्रमेय|शैनन के चैनल कोडिंग प्रमेय से पता चलता है कि कई सामान्य चैनलों पर चैनल कोडिंग योजनाएं मौजूद हैं जो सभी दरों पर विश्वसनीय रूप से डेटा संचारित करने में सक्षम हैं <math>R</math> निश्चित सीमा से कम <math>C</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|यह कोड संयोजन का सचित्र प्रतिनिधित्व है, और, विशेष रूप से, n=q=4 और k=2 के साथ रीड-सोलोमन कोड का उपयोग बाहरी कोड के रूप में किया जाता है और n=q और k=log q के साथ [[हैडामर्ड कोड]] का उपयोग आंतरिक कोड के रूप में किया जाता है। कुल मिलाकर, संयोजित कोड है <math>[q^2,k \log q]</math>-कोड.


चलो सी<sub>''in''</sub> एक [एन, के, डी] कोड हो, यानी, लंबाई एन, आयाम (वेक्टर स्पेस) के, न्यूनतम [[हैमिंग दूरी]] डी, और [[कोड दर]] आर = के/एन का एक [[ब्लॉक कोड]], वर्णमाला ए पर:
चलो सी<sub>''in''</sub> [एन, के, डी] कोड हो, यानी, लंबाई एन, आयाम (वेक्टर स्पेस) के, न्यूनतम [[हैमिंग दूरी]] डी, और [[कोड दर]] आर = के/एन का [[ब्लॉक कोड]], वर्णमाला ए पर:
:<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> प्रतीक:
चलो सी<sub>''out''</sub> |B| के साथ वर्णमाला B पर [N, K, D] कोड हो = |ए|<sup>क</sup> प्रतीक:
:<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>
आंतरिक कोड सी<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>
यह प्रत्येक इनपुट संदेश 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 = (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>).
कहाँ (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"/>इस पर अनुभाग #डिकोडिंग संयोजित कोड में अधिक विस्तार से चर्चा की गई है।
इस दृष्टिकोण में मुख्य अंतर्दृष्टि यह है कि यदि सी<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"/>इस पर अनुभाग #डिकोडिंग संयोजित कोड में अधिक विस्तार से चर्चा की गई है।


उपरोक्त संयोजन के सामान्यीकरण में, एन संभावित आंतरिक कोड सी हैं<sub>''in'',''i''</sub> और C के कोडवर्ड में i-th प्रतीक<sub>''out''</sub> i-वें आंतरिक कोड का उपयोग करके आंतरिक चैनल में प्रसारित किया जाता है। [[जस्टसेन कोड]] सामान्यीकृत संयोजित कोड के उदाहरण हैं, जहां बाहरी कोड रीड-सोलोमन कोड है।
उपरोक्त संयोजन के सामान्यीकरण में, एन संभावित आंतरिक कोड सी हैं<sub>''in'',''i''</sub> और C के कोडवर्ड में i-th प्रतीक<sub>''out''</sub> i-वें आंतरिक कोड का उपयोग करके आंतरिक चैनल में प्रसारित किया जाता है। [[जस्टसेन कोड]] सामान्यीकृत संयोजित कोड के उदाहरण हैं, जहां बाहरी कोड रीड-सोलोमन कोड है।


==गुण==
==गुण==
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<nowiki>'</nowiki> ≥ dD के साथ [nN, kK, D<nowiki>'</nowiki>] कोड है।


सबूत:
सबूत:
Line 44: Line 43:
नतीजतन, वर्णमाला 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. यदि ''सी''<sub>''out''</sub> और सी<sub>''in''</sub> [[रैखिक ब्लॉक कोड]] हैं, फिर C<sub>''out''</sub>∘C<sub>''in''</sub> यह रैखिक ब्लॉक कोड भी है।


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


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


विस्तार से, मान लीजिए कि डिकोडर का इनपुट वेक्टर y = (y) है<sub>1</sub>, ..., और<sub>''N''</sub>) ∈ (ए<sup>n</sup>)<sup>एन</sup>. फिर डिकोडिंग एल्गोरिदम दो चरणों वाली प्रक्रिया है:
विस्तार से, मान लीजिए कि डिकोडर का इनपुट वेक्टर y = (y) है<sub>1</sub>, ..., और<sub>''N''</sub>) ∈ (ए<sup>n</sup>)<sup>एन</sup>. फिर डिकोडिंग एल्गोरिदम दो चरणों वाली प्रक्रिया है:
# आंतरिक कोड सी के एमएलडी का उपयोग करें<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 ≤ मैं ≤ एन.
# आंतरिक कोड सी के एमएलडी का उपयोग करें<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> पर।
# C के लिए अद्वितीय डिकोडिंग एल्गोरिदम चलाएँ<sub>out</sub> y<nowiki>'</nowiki> पर।


Line 60: Line 59:
===टिप्पणियाँ===
===टिप्पणियाँ===


ऊपर वर्णित डिकोडिंग एल्गोरिदम का उपयोग 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<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/2 त्रुटियों तक को ठीक करने के लिए किया जा सकता है।<ref name="gmd">
यदि आंतरिक कोड अलग-अलग हैं, तो एल्गोरिदम भी काम करता है, उदाहरण के लिए, जस्टेसन कोड के लिए। फ़ोर्नी द्वारा विकसित [[सामान्यीकृत न्यूनतम दूरी डिकोडिंग]] का उपयोग dD/2 त्रुटियों तक को ठीक करने के लिए किया जा सकता है।<ref name="gmd">
Line 74: Line 73:
|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 103: Line 102:


==अनुप्रयोग==
==अनुप्रयोग==
हालाँकि 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 113: Line 112:
}}
}}
</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 125: Line 124:
बड़ा प्रतीक आकार बाहरी कोड को [[त्रुटि विस्फोट]]ों के प्रति अधिक मजबूत बनाता है जो चैनल की खराबी के कारण हो सकता है, और इसलिए भी क्योंकि कन्वेन्शनल कोड का गलत आउटपुट स्वयं फट जाता है।<ref name="Forney"/><ref name="McEliece"/>एक फॉरवर्ड एरर करेक्शन#इंटरलीविंग को आम तौर पर दो कोडों के बीच जोड़ा जाता है ताकि एरर बर्स्ट को व्यापक रेंज में फैलाया जा सके।<ref name="McEliece"/>
बड़ा प्रतीक आकार बाहरी कोड को [[त्रुटि विस्फोट]]ों के प्रति अधिक मजबूत बनाता है जो चैनल की खराबी के कारण हो सकता है, और इसलिए भी क्योंकि कन्वेन्शनल कोड का गलत आउटपुट स्वयं फट जाता है।<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>
बाहरी रीड-सोलोमन कोड (जिसे आरएसवी कोड के रूप में जाना जाता है) के साथ आंतरिक विटर्बी कनवल्शनल कोड का संयोजन पहली बार वोयाजर 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>
शिथिल अर्थ में, दो या दो से अधिक कोड के किसी भी (क्रमिक) संयोजन को संयोजित कोड के रूप में संदर्भित किया जा सकता है। उदाहरण के लिए, [[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"/>इस डिज़ाइन का प्रदर्शन पहले से कल्पित किसी भी संयोजित कोड से बेहतर है।
उपरोक्त विवरण उस चीज़ के लिए दिया गया है जिसे अब क्रमिक रूप से संयोजित कोड कहा जाता है। टर्बो कोड, जैसा कि पहली बार 1993 में वर्णित किया गया था, ने दो कन्वेन्शनल कोड के समानांतर संयोजन को लागू किया, जिसमें दो कोड के बीच इंटरलीवर और पुनरावृत्त डिकोडर था जो कोड के बीच जानकारी को आगे और पीछे भेजता था।<ref name="deep-space-codes"/>इस डिज़ाइन का प्रदर्शन पहले से कल्पित किसी भी संयोजित कोड से बेहतर है।


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




Line 153: Line 152:
* {{scholarpedia|title=Concatenated codes|urlname=Concatenated_codes|curator=[[Dave Forney]]}}
* {{scholarpedia|title=Concatenated codes|urlname=Concatenated_codes|curator=[[Dave Forney]]}}
* [https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
* [https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
{{CCSDS|state=collapsed}}


{{DEFAULTSORT:Concatenated Error Correction Codes}}[[Category: त्रुटि का पता लगाना और सुधार करना]] [[Category: कोडिंग सिद्धांत]] [[Category: परिमित क्षेत्र]] [[Category: सूचना सिद्धांत]]  
{{DEFAULTSORT:Concatenated Error Correction Codes}}[[Category: त्रुटि का पता लगाना और सुधार करना]] [[Category: कोडिंग सिद्धांत]] [[Category: परिमित क्षेत्र]] [[Category: सूचना सिद्धांत]]  

Revision as of 10:19, 31 July 2023

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

पृष्ठभूमि

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

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

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

विवरण

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

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

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

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

आंतरिक कोड सीin |ए| में से लेता हैक = |बी| संभावित इनपुट, ए पर एन-ट्यूपल में एनकोड करता है, ट्रांसमिट करता है, और |बी| में से किसी में डिकोड करता है। संभावित आउटपुट. हम इसे (सुपर) चैनल के रूप में मानते हैं जो वर्णमाला बी से प्रतीक को प्रसारित कर सकता है। हम इस चैनल का उपयोग सी के कोडवर्ड में प्रत्येक एन प्रतीक को प्रसारित करने के लिए एन बार करते हैं।out. सी का संयोजनout (बाहरी कोड के रूप में) सी के साथin (आंतरिक कोड के रूप में), सी दर्शाया गया हैout∘Cin, क्या यह वर्णमाला A के ऊपर N लंबाई की राग है:[1]: यह प्रत्येक इनपुट संदेश m = (m) को मैप करता है1, एम2, ..., एमK) कोडवर्ड के लिए (सीin(एम<नोविकी>'</नोविकी>1), सीin(एम<नोविकी>'</नोविकी>2), ..., सीin(एम<नोविकी>'</नोविकी>N)), कहाँ (m'1, म'2, ..., म<नोविकी>'</नोविकी>N) = सीout(एम1, एम2, ..., एमK).

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

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

गुण

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

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

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

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

2. यदि सीout और सीin रैखिक ब्लॉक कोड हैं, फिर Cout∘Cin यह रैखिक ब्लॉक कोड भी है।

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

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

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

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

  1. आंतरिक कोड सी के एमएलडी का उपयोग करेंin आंतरिक कोड शब्दों के सेट को फिर से बनाने के लिए y' = (y'1, ..., 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 त्रुटियों तक को ठीक करने के लिए किया जा सकता है।[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=246308’