डिकोडिंग विधियाँ: Difference between revisions

From Vigyanwiki
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[[[कोड]]िंग सिद्धांत]] में, डिकोडिंग प्राप्त संदेशों को किसी दिए गए कोड के [[ कूटशब्द |कूटशब्द]] में अनुवाद करने की प्रक्रिया है। संदेशों को कोडवर्ड में मैप करने की कई सामान्य विधियाँ मौजूद हैं। इनका उपयोग अक्सर शोर वाले चैनल, जैसे कि [[द्विआधारी सममित चैनल]], पर भेजे गए संदेशों को पुनर्प्राप्त करने के लिए किया जाता है।
 
कोडिंग सिद्धांत में, '''डिकोडिंग''' प्राप्त संदेशों को किसी दिए गए कोड के कोडवर्ड में अनुवाद करने की प्रक्रिया है। संदेशों को कोडवर्ड में मानचित्र करने की अनेक सामान्य विधियाँ उपस्थित हैं। इनका उपयोग अधिकांशतः ध्वनि वाले चैनल, जैसे कि बाइनरी सममित चैनल, पर भेजे गए संदेशों को पुनर्प्राप्त करने के लिए किया जाता है।


==नोटेशन==
==नोटेशन==
<math>C \subset \mathbb{F}_2^n</math> लंबाई के साथ एक [[बाइनरी कोड]] माना जाता है <math>n</math>; <math>x,y</math> के तत्व होंगे <math>\mathbb{F}_2^n</math>; और <math>d(x,y)</math> उन तत्वों के बीच की दूरी है.
<math>C \subset \mathbb{F}_2^n</math> को लंबाई <math>n</math>; <math>x,y</math> के साथ एक बाइनरी कोड माना जाता है, जो <math>\mathbb{F}_2^n</math>के तत्व होंगे; और <math>d(x,y)</math> उन तत्वों के बीच की दूरी है।


==आदर्श पर्यवेक्षक डिकोडिंग==
==आदर्श पर्यवेक्षक डिकोडिंग                                                                                                       ==
किसी को सन्देश दिया जा सकता है <math>x \in \mathbb{F}_2^n</math>, फिर आदर्श पर्यवेक्षक डिकोडिंग कोडवर्ड उत्पन्न करता है <math>y \in C</math>. इस प्रक्रिया के परिणामस्वरूप यह समाधान मिलता है:
किसी को संदेश <math>x \in \mathbb{F}_2^n</math> दिया जा सकता है, फिर आदर्श पर्यवेक्षक डिकोडिंग कोडवर्ड <math>y \in C                                                                                                                                                                                                                
                                                                                                                                                                                                                                                        </math> उत्पन्न करता है। प्रक्रिया के परिणामस्वरूप यह समाधान मिलता है:


:<math>\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})</math>
:<math>\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})</math>
उदाहरण के लिए, कोई व्यक्ति कोडवर्ड चुन सकता है <math>y</math> इसके संदेश के रूप में प्राप्त होने की सबसे अधिक संभावना है <math>x</math> प्रसारण के बाद.
उदाहरण के लिए, कोई व्यक्ति कोडवर्ड y चुन सकता है जिसके ट्रांसमिशन के बाद संदेश x के रूप में प्राप्त होने की सबसे अधिक संभावना है।


===डिकोडिंग कन्वेंशन===
===डिकोडिंग कन्वेंशन===
प्रत्येक कोडवर्ड में अपेक्षित संभावना नहीं होती है: प्राप्त संदेश में परिवर्तन की समान संभावना वाले एक से अधिक कोडवर्ड हो सकते हैं। ऐसे मामले में, प्रेषक और प्राप्तकर्ता को डिकोडिंग कन्वेंशन पर समय से पहले सहमत होना होगा। लोकप्रिय सम्मेलनों में शामिल हैं:
प्रत्येक कोडवर्ड में अपेक्षित संभावना नहीं होती है: प्राप्त संदेश में परिवर्तन की समान संभावना वाले एक से अधिक कोडवर्ड हो सकते हैं। ऐसे स्थिति में, प्रेषक और प्राप्तकर्ता को डिकोडिंग कन्वेंशन पर समय से पहले सहमत होना होगा। लोकप्रिय सम्मेलनों में सम्मिलित हैं:


:# अनुरोध है कि कोडवर्ड पुनः भेजा जाए{{snd}} [[स्वचालित दोहराव-अनुरोध]]।
:# अनुरोध है कि कोडवर्ड पुनः भेजा जाए{{snd}} [[स्वचालित दोहराव-अनुरोध]]।
:# सबसे संभावित कोडवर्ड के सेट में से कोई भी यादृच्छिक कोडवर्ड चुनें जो उसके करीब हो।
:# सबसे संभावित कोडवर्ड के सेट में से कोई भी यादृच्छिक कोडवर्ड चुनें जो उसके समीप हो।
:# यदि त्रुटि सुधार कोड को जोड़ा गया है, तो कोडवर्ड के अस्पष्ट बिट्स को मिटाने के रूप में चिह्नित करें और आशा करें कि बाहरी कोड उन्हें स्पष्ट कर दे।
:# यदि त्रुटि सुधार कोड को जोड़ा गया है, तो कोडवर्ड के अस्पष्ट बिट्स को मिटाने के रूप में चिह्नित करें और आशा करें कि बाहरी कोड उन्हें स्पष्ट कर दे।


==अधिकतम संभावना डिकोडिंग==
==अधिकतम संभावना डिकोडिंग                                                   ==
{{Further|Maximum likelihood}}
{{Further|अधिकतम संभाव्यता}}
 


एक प्राप्त वेक्टर दिया गया <math>x \in \mathbb{F}_2^n</math> अधिकतम संभावना डिकोडिंग एक कोडवर्ड चुनती है <math>y \in C</math> वह [[अनुकूलन (गणित)]] एस
प्राप्त सदिश <math>x \in \mathbb{F}_2^n</math> को देखते हुए अधिकतम संभावना डिकोडिंग एक कोडवर्ड <math>y \in C</math> चुनती है जो अधिकतम करता है


:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,
:<math>\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})</math>,


यानी कोडवर्ड <math>y</math> इससे इसकी संभावना अधिकतम हो जाती है <math>x</math> प्राप्त हुआ था, [[सशर्त संभाव्यता]] <math>y</math> भेजा था। यदि सभी कोडवर्ड भेजे जाने की समान संभावना है तो यह योजना आदर्श पर्यवेक्षक डिकोडिंग के बराबर है।
अर्थात्, कोडवर्ड y जो कि x प्राप्त होने की संभावना को अधिकतम करता है, यह देखते हुए कि y भेजा गया था। यदि सभी कोडवर्ड भेजे जाने की समान संभावना है तो यह योजना आदर्श पर्यवेक्षक डिकोडिंग के समान है। वास्तव में, बेयस प्रमेय द्वारा,
वास्तव में, [[बेयस प्रमेय]] द्वारा,


:<math>
:<math>
Line 33: Line 35:
\end{align}
\end{align}
</math>
</math>
ठीक करने पर <math>\mathbb{P}(x \mbox{ received})</math>, <math>x</math> का पुनर्गठन किया गया है और
 
<math>\mathbb{P}(y \mbox{ sent})</math> स्थिर है क्योंकि सभी कोडवर्ड भेजे जाने की समान संभावना है।
 
इसलिए,
 
<math>
<math>\mathbb{P}(x \mbox{ received})</math> को ठीक करने पर, x को पुनर्गठित किया जाता है और <math>\mathbb{P}(y \mbox{ sent})</math> स्थिर होता है क्योंकि सभी कोडवर्ड भेजे जाने की समान संभावना होती है। इसलिए, <math>
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})  
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})  
</math>
</math> को वेरिएबल y के एक फलन के रूप में अधिकतम किया जाता है, ठीक उसी समय जब <math>
चर के एक फलन के रूप में अधिकतम किया जाता है <math>y</math> बिल्कुल कब
<math>
\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} )  
\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} )  
</math>
</math>को अधिकतम किया जाता है, और प्रमाण इस प्रकार होता है।
अधिकतम किया गया है, और दावा इस प्रकार है।
 
आदर्श पर्यवेक्षक डिकोडिंग की तरह, गैर-अद्वितीय डिकोडिंग के लिए एक सम्मेलन पर सहमति होनी चाहिए।


अधिकतम संभावना डिकोडिंग समस्या को [[पूर्णांक प्रोग्रामिंग]] समस्या के रूप में भी तैयार किया जा सकता है।<ref name="Feldman_2005"/>
अधिकतम संभावना डिकोडिंग समस्या को [[पूर्णांक प्रोग्रामिंग]] समस्या के रूप में भी तैयार किया जा सकता है।<ref name="Feldman_2005"/>


अधिकतम संभावना डिकोडिंग एल्गोरिदम एक उत्पाद फ़ंक्शन समस्या को हाशिए पर रखने का एक उदाहरण है जिसे सामान्यीकृत वितरण कानून को लागू करके हल किया जाता है।<ref name="Aji-McEliece_2000"/>
अधिकतम संभावना डिकोडिंग एल्गोरिदम एक उत्पाद फलन समस्या को मार्जिन पर रखने का एक उदाहरण है जिसे सामान्यीकृत वितरण नियम को प्रयुक्त करके हल किया जाता है।<ref name="Aji-McEliece_2000"/>
 
 
==न्यूनतम दूरी डिकोडिंग==
==न्यूनतम दूरी डिकोडिंग==
एक प्राप्त कोडवर्ड दिया गया <math>x \in \mathbb{F}_2^n</math>, न्यूनतम दूरी डिकोडिंग एक कोडवर्ड चुनती है <math>y \in C</math> [[हैमिंग दूरी]] को कम करने के लिए:
प्राप्त कोडवर्ड <math>x \in \mathbb{F}_2^n</math> को देखते हुए, न्यूनतम दूरी डिकोडिंग हैमिंग दूरी को कम करने के लिए एक कोडवर्ड <math>y \in C</math> चुनती है:


:<math>d(x,y) = \# \{i : x_i \not = y_i \}</math>
:<math>d(x,y) = \# \{i : x_i \not = y_i \}</math>
यानी कोडवर्ड चुनें <math>y</math> वह जितना संभव हो उतना करीब है <math>x</math>.
अथार्त वह कोडवर्ड <math>y</math> चुनें जो <math>x</math> के जितना समीप हो सकता है ।


ध्यान दें कि यदि [[असतत स्मृतिहीन चैनल]] पर त्रुटि की संभावना है <math>p</math> सख्ती से आधे से कम है, तो न्यूनतम दूरी डिकोडिंग अधिकतम संभावना डिकोडिंग के बराबर है, क्योंकि यदि
ध्यान दें कि यदि असतत मेमोरी रहित चैनल <math>p                                                                                                                                                                         </math> पर त्रुटि की संभावना सख्ती से आधे से कम है, तो न्यूनतम दूरी डिकोडिंग अधिकतम संभावना डिकोडिंग के समान है, क्योंकि यदि


:<math>d(x,y) = d,\,</math>
:<math>d(x,y) = d,\,</math>
तब:
जब:


:<math>
:<math>
Line 71: Line 66:
जो (चूँकि p आधे से भी कम है) d को न्यूनतम करके अधिकतम किया जाता है।
जो (चूँकि p आधे से भी कम है) d को न्यूनतम करके अधिकतम किया जाता है।


न्यूनतम दूरी डिकोडिंग को निकटतम पड़ोसी डिकोडिंग के रूप में भी जाना जाता है। इसे [[मानक सरणी]] का उपयोग करके सहायता या स्वचालित किया जा सकता है। न्यूनतम दूरी डिकोडिंग एक उचित डिकोडिंग विधि है जब निम्नलिखित शर्तें पूरी होती हैं:
न्यूनतम दूरी डिकोडिंग को निकटतम समीप डिकोडिंग के रूप में भी जाना जाता है। इसे [[मानक सरणी]] का उपयोग करके सहायता या स्वचालित किया जा सकता है। न्यूनतम दूरी डिकोडिंग एक उचित डिकोडिंग विधि है जब निम्नलिखित नियम पूरी होती हैं:


:#संभावना <math>p</math> कोई त्रुटि उत्पन्न होना प्रतीक की स्थिति से स्वतंत्र है।
:#संभावना <math>p</math> कोई त्रुटि उत्पन्न होना प्रतीक की स्थिति से स्वतंत्र है।
:#त्रुटियाँ स्वतंत्र घटनाएँ हैं{{snd}} संदेश में एक स्थान पर त्रुटि अन्य पदों को प्रभावित नहीं करती है।
:#त्रुटियाँ स्वतंत्र घटनाएँ हैं{{snd}} संदेश में एक स्थान पर त्रुटि अन्य पदों को प्रभावित नहीं करती है।


ये धारणाएँ बाइनरी सममित चैनल पर प्रसारण के लिए उचित हो सकती हैं। वे डीवीडी जैसे अन्य मीडिया के लिए अनुचित हो सकते हैं, जहां डिस्क पर एक खरोंच कई पड़ोसी प्रतीकों या कोडवर्ड में त्रुटि का कारण बन सकती है।
ये धारणाएँ बाइनरी सममित चैनल पर प्रसारण के लिए उचित हो सकती हैं। वे डीवीडी जैसे अन्य मीडिया के लिए अनुचित हो सकते हैं, जहां डिस्क पर एक खरोंच अनेक समीप प्रतीकों या कोडवर्ड में त्रुटि का कारण बन सकती है।


अन्य डिकोडिंग विधियों की तरह, गैर-अद्वितीय डिकोडिंग के लिए एक सम्मेलन पर सहमति होनी चाहिए।
अन्य डिकोडिंग विधियों की तरह, गैर-अद्वितीय डिकोडिंग के लिए एक सम्मेलन पर सहमति होनी चाहिए।
Line 82: Line 77:
==सिंड्रोम डिकोडिंग==
==सिंड्रोम डिकोडिंग==


सिंड्रोम डिकोडिंग एक ''शोर चैनल'' पर एक [[रैखिक कोड]] को डिकोड करने का एक अत्यधिक कुशल तरीका है, यानी जिस चैनल पर त्रुटियां होती हैं। संक्षेप में, सिंड्रोम डिकोडिंग एक कम लुकअप तालिका का उपयोग करके ''न्यूनतम दूरी डिकोडिंग'' है। यह कोड की रैखिकता द्वारा अनुमत है।<ref name="Beutelspacher-Rosenbaum_1998"/>
सिंड्रोम डिकोडिंग एक ''ध्वनि चैनल'' पर एक [[रैखिक कोड]] को डिकोड करने का एक अत्यधिक कुशल विधि है, अथार्त जिस चैनल पर त्रुटियां होती हैं। संक्षेप में, सिंड्रोम डिकोडिंग एक कम लुकअप तालिका का उपयोग करके ''न्यूनतम दूरी डिकोडिंग'' है। यह कोड की रैखिकता द्वारा अनुमत है।<ref name="Beutelspacher-Rosenbaum_1998"/>


लगता है कि <math>C\subset \mathbb{F}_2^n</math> लंबाई का एक रैखिक कोड है <math>n</math> और न्यूनतम दूरी <math>d</math> [[समता-जांच मैट्रिक्स]] के साथ <math>H</math>. फिर स्पष्ट रूप से <math>C</math> तक ठीक करने में सक्षम है
मान लीजिए कि <math>C\subset \mathbb{F}_2^n</math> समता-जाँच आव्यूह <math>H</math> के साथ लंबाई <math>n</math> और न्यूनतम दूरी <math>d</math> का एक रैखिक कोड है। तो स्पष्ट रूप से <math>C</math> तक सही करने में सक्षम है


:<math>t = \left\lfloor\frac{d-1}{2}\right\rfloor</math>
:<math>t = \left\lfloor\frac{d-1}{2}\right\rfloor</math>
चैनल द्वारा की गई त्रुटियाँ (यदि इससे अधिक नहीं)। <math>t</math> त्रुटियां की जाती हैं तो न्यूनतम दूरी डिकोडिंग अभी भी गलत तरीके से प्रसारित कोडवर्ड को सही ढंग से डिकोड करेगी)।
चैनल द्वारा की गई त्रुटियाँ (यदि इससे अधिक नहीं)। <math>t</math> त्रुटियां की जाती हैं तो न्यूनतम दूरी डिकोडिंग अभी भी गलत विधि से प्रसारित कोडवर्ड को सही रूप से डिकोड करेगी)।


अब मान लीजिए कि एक कोडवर्ड <math>x \in \mathbb{F}_2^n</math> चैनल और त्रुटि पैटर्न पर भेजा जाता है <math>e \in \mathbb{F}_2^n</math> घटित होना। तब <math>z=x+e</math> प्राप्त होता है। सामान्य न्यूनतम दूरी डिकोडिंग वेक्टर को देखेगी <math>z</math> आकार की एक तालिका में <math>|C|</math> निकटतम मिलान के लिए - यानी एक तत्व (जरूरी नहीं कि अद्वितीय) <math>c \in C</math> साथ
अब मान लीजिए कि एक कोडवर्ड <math>x \in \mathbb{F}_2^n</math> चैनल पर भेजा जाता है और त्रुटि पैटर्न <math>e \in \mathbb{F}_2^n</math> घटित होना। तब <math>z=x+e</math> प्राप्त होता है। सामान्य न्यूनतम दूरी डिकोडिंग वेक्टर <math>z</math> को <math>|C|</math> आकार की तालिका में देखेगी निकटतम मिलान के लिए - अर्थात एक तत्व (आवश्यक नहीं कि अद्वितीय) <math>c \in C</math> के साथ है


:<math>d(c,z) \leq d(y,z)</math>
:<math>d(c,z) \leq d(y,z)</math>
सभी के लिए <math>y \in C</math>. सिंड्रोम डिकोडिंग समता मैट्रिक्स की संपत्ति का लाभ उठाती है:
सभी <math>y \in C</math> के लिए सिंड्रोम डिकोडिंग समता आव्यूह की संपत्ति का लाभ उठाती है:


:<math>Hx = 0</math>
:<math>Hx = 0</math>
Line 98: Line 93:


:<math>Hz = H(x+e) =Hx + He = 0 + He = He</math>
:<math>Hz = H(x+e) =Hx + He = 0 + He = He</math>
बाइनरी सममित चैनल में #अधिकतम_संभावना_डिकोडिंग करने के लिए, किसी को आकार की पूर्व-गणना की गई तालिका को देखना होगा <math>2^{n-k}</math>, मानचित्रण <math>He</math> को <math>e</math>.
बाइनरी सममित चैनल में एमएल डिकोडिंग करने के लिए, किसी को <math>2^{n-k}</math> आकार की एक पूर्व-गणना की गई तालिका को देखना होगा, जिसमें हे को <math>e</math> पर मानचित्र किया जाएगा।


ध्यान दें कि यह मानक सरणी की तुलना में पहले से ही काफी कम जटिलता वाला है।
ध्यान दें कि यह मानक सरणी की तुलना में पहले से ही अधिक कम कॉम्प्लेक्सिटी वाला है।


हालाँकि, इस धारणा के तहत कि इससे अधिक नहीं <math>t</math> ट्रांसमिशन के दौरान त्रुटियां हुईं, तो रिसीवर मूल्य देख सकता है <math>He</math> आकार की एक और कम तालिका में
चूँकि इस धारणा के अनुसार कि ट्रांसमिशन के समय t से अधिक त्रुटियाँ नहीं की गईं, रिसीवर आकार की एक और कम तालिका में <math>He</math> का मान देख सकता है


:<math>
:<math>
Line 109: Line 104:
\end{matrix}
\end{matrix}
</math>
</math>
== सूची डिकोडिंग ==
== सूची डिकोडिंग ==
{{Main|List decoding}}
{{Main|सूची डिकोडिंग}}


== सूचना सेट डिकोडिंग ==
== सूचना सेट डिकोडिंग ==


यह [[ लास वेगास एल्गोरिथ्म |लास वेगास एल्गोरिथ्म]] -संभाव्य विधियों का एक परिवार है जो इस अवलोकन पर आधारित है कि सभी त्रुटि-स्थितियों का अनुमान लगाने की तुलना में पर्याप्त त्रुटि-मुक्त स्थितियों का अनुमान लगाना आसान है।
यह [[ लास वेगास एल्गोरिथ्म |लास वेगास एल्गोरिथ्म]] -संभाव्य विधियों का एक वरग है जो इस अवलोकन पर आधारित है कि सभी त्रुटि-स्थितियों का अनुमान लगाने की तुलना में पर्याप्त त्रुटि-मुक्त स्थितियों का अनुमान लगाना सरल है।
 
सबसे सरल रूप प्रेंज के कारण है: लेट <math>G</math> हो <math>k \times n</math> जनरेटर मैट्रिक्स का <math>C</math> एन्कोडिंग के लिए उपयोग किया जाता है। चुनना <math>k</math> के कॉलम <math>G</math> यादृच्छिक रूप से, और द्वारा निरूपित करें <math>G'</math> के संगत सबमैट्रिक्स <math>G</math>. उचित संभावना के साथ <math>G'</math> पूर्ण रैंक होगी, जिसका अर्थ है कि यदि हम जाने देंगे <math>c'</math> किसी भी कोडवर्ड के संबंधित पदों के लिए उप-वेक्टर बनें <math>c = mG</math> का <math>C</math> एक संदेश के लिए <math>m</math>, हम ठीक हो सकते हैं <math>m</math> जैसा <math>m = c' G'^{-1}</math>. इसलिए, अगर हम भाग्यशाली थे कि ये <math>k</math> प्राप्त शब्द की स्थिति <math>y</math> इसमें कोई त्रुटि नहीं है, और इसलिए भेजे गए कोडवर्ड की स्थिति बराबर है, फिर हम डिकोड कर सकते हैं।
 
अगर <math>t</math> त्रुटियाँ हुईं, स्तंभों के ऐसे भाग्यशाली चयन की संभावना दी गई है <math>\textstyle\binom{n-t}{k}/\binom{n}{k}</math>.


इस पद्धति में विभिन्न तरीकों से सुधार किया गया है, उदा. स्टर्न द्वारा<ref name="Stern_1989"/>और [[ऐनी कैंटौट]] और सेंड्रिएर।<ref name="Ohta_1998"/>
अधिक सरल रूप प्रेंज के कारण है: मान लीजिए <math>G</math> एन्कोडिंग के लिए उपयोग किया जाने वाला <math>C</math> का <math>k \times n</math> जनरेटर आव्यूह है। यादृच्छिक रूप से <math>G</math> के <math>k</math> स्तम्भ का चयन करें, और <math>G</math> के संगत उपआव्यूह को <math>G'</math> से निरूपित करें। उचित संभावना के साथ <math>G'</math> की पूर्ण श्रेणी होगी, जिसका अर्थ है कि यदि हम <math>c'</math> को किसी भी कोडवर्ड के संबंधित पदों के लिए उप-वेक्टर बनाते हैं। संदेश <math>m</math> के लिए <math>C</math> का <math>c = mG</math> हम m को <math>m = c' G'^{-1}</math> के रूप में पुनर्प्राप्त कर सकते हैं। इसलिए, यदि हम भाग्यशाली थे कि प्राप्त शब्द <math>y</math> की इन <math>k</math> स्थितियों में कोई त्रुटि नहीं थी, और इसलिए भेजे गए कोडवर्ड की स्थिति समान थी, तो हम डिकोड कर सकते हैं।


यदि <math>t</math> त्रुटियाँ हुईं, स्तंभों के ऐसे भाग्यशाली चयन की संभावना <math>\textstyle\binom{n-t}{k}/\binom{n}{k}</math> दी गई है


इस पद्धति में विभिन्न विधियों से सुधार किया गया है, उदा. स्टर्न द्वारा<ref name="Stern_1989"/>और कैंट्यूट और सेंड्रिएर।<ref name="Ohta_1998"/>
==आंशिक प्रतिक्रिया अधिकतम संभावना==
==आंशिक प्रतिक्रिया अधिकतम संभावना==
{{Main|PRML}}
{{Main|पीआरएमएल}}


आंशिक प्रतिक्रिया अधिकतम संभावना ([[पीआरएमएल]]) चुंबकीय डिस्क या टेप ड्राइव के हेड से कमजोर एनालॉग सिग्नल को डिजिटल सिग्नल में परिवर्तित करने की एक विधि है।
आंशिक प्रतिक्रिया अधिकतम संभावना ([[पीआरएमएल]]) चुंबकीय डिस्क या टेप ड्राइव के हेड से अशक्त एनालॉग सिग्नल को डिजिटल सिग्नल में परिवर्तित करने की एक विधि है।


==विटरबी डिकोडर==
==विटरबी डिकोडर==
{{Main|Viterbi decoder}}
{{Main|विटरबी डिकोडर}}


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


== इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए) ==
== इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए) ==
असममित TWRC प्रणाली के लिए इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए)।{{Clarify|date=January 2023}}<ref>{{Citation |title= Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system; |author1=Siamack Ghadimi|publisher=Universal Journal of Electrical and Electronic Engineering|date=2020}}</ref>
असममित टीडब्ल्यूआरसी प्रणाली के लिए इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए)।<ref>{{Citation |title= Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system; |author1=Siamack Ghadimi|publisher=Universal Journal of Electrical and Electronic Engineering|date=2020}}</ref>
 
==यह भी देखें                                                                                                                             ==
 
* डोंट केयर अलार्म
==यह भी देखें==
*[[त्रुटि का पता लगाना और सुधार करना|एरर डिटेक्शन और करेक्शन]]
* चिंता मत करो अलार्म
* [[निषिद्ध इनपुट|फोर्बिडन इनपुट]]
*[[त्रुटि का पता लगाना और सुधार करना]]
* [[निषिद्ध इनपुट]]


==संदर्भ==
==संदर्भ==
Line 165: Line 153:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 09:45, 24 November 2023

कोडिंग सिद्धांत में, डिकोडिंग प्राप्त संदेशों को किसी दिए गए कोड के कोडवर्ड में अनुवाद करने की प्रक्रिया है। संदेशों को कोडवर्ड में मानचित्र करने की अनेक सामान्य विधियाँ उपस्थित हैं। इनका उपयोग अधिकांशतः ध्वनि वाले चैनल, जैसे कि बाइनरी सममित चैनल, पर भेजे गए संदेशों को पुनर्प्राप्त करने के लिए किया जाता है।

नोटेशन

को लंबाई ; के साथ एक बाइनरी कोड माना जाता है, जो के तत्व होंगे; और उन तत्वों के बीच की दूरी है।

आदर्श पर्यवेक्षक डिकोडिंग

किसी को संदेश दिया जा सकता है, फिर आदर्श पर्यवेक्षक डिकोडिंग कोडवर्ड उत्पन्न करता है। प्रक्रिया के परिणामस्वरूप यह समाधान मिलता है:

उदाहरण के लिए, कोई व्यक्ति कोडवर्ड y चुन सकता है जिसके ट्रांसमिशन के बाद संदेश x के रूप में प्राप्त होने की सबसे अधिक संभावना है।

डिकोडिंग कन्वेंशन

प्रत्येक कोडवर्ड में अपेक्षित संभावना नहीं होती है: प्राप्त संदेश में परिवर्तन की समान संभावना वाले एक से अधिक कोडवर्ड हो सकते हैं। ऐसे स्थिति में, प्रेषक और प्राप्तकर्ता को डिकोडिंग कन्वेंशन पर समय से पहले सहमत होना होगा। लोकप्रिय सम्मेलनों में सम्मिलित हैं:

  1. अनुरोध है कि कोडवर्ड पुनः भेजा जाए – स्वचालित दोहराव-अनुरोध
  2. सबसे संभावित कोडवर्ड के सेट में से कोई भी यादृच्छिक कोडवर्ड चुनें जो उसके समीप हो।
  3. यदि त्रुटि सुधार कोड को जोड़ा गया है, तो कोडवर्ड के अस्पष्ट बिट्स को मिटाने के रूप में चिह्नित करें और आशा करें कि बाहरी कोड उन्हें स्पष्ट कर दे।

अधिकतम संभावना डिकोडिंग


प्राप्त सदिश को देखते हुए अधिकतम संभावना डिकोडिंग एक कोडवर्ड चुनती है जो अधिकतम करता है

,

अर्थात्, कोडवर्ड y जो कि x प्राप्त होने की संभावना को अधिकतम करता है, यह देखते हुए कि y भेजा गया था। यदि सभी कोडवर्ड भेजे जाने की समान संभावना है तो यह योजना आदर्श पर्यवेक्षक डिकोडिंग के समान है। वास्तव में, बेयस प्रमेय द्वारा,


को ठीक करने पर, x को पुनर्गठित किया जाता है और स्थिर होता है क्योंकि सभी कोडवर्ड भेजे जाने की समान संभावना होती है। इसलिए, को वेरिएबल y के एक फलन के रूप में अधिकतम किया जाता है, ठीक उसी समय जब को अधिकतम किया जाता है, और प्रमाण इस प्रकार होता है।

अधिकतम संभावना डिकोडिंग समस्या को पूर्णांक प्रोग्रामिंग समस्या के रूप में भी तैयार किया जा सकता है।[1]

अधिकतम संभावना डिकोडिंग एल्गोरिदम एक उत्पाद फलन समस्या को मार्जिन पर रखने का एक उदाहरण है जिसे सामान्यीकृत वितरण नियम को प्रयुक्त करके हल किया जाता है।[2]

न्यूनतम दूरी डिकोडिंग

प्राप्त कोडवर्ड को देखते हुए, न्यूनतम दूरी डिकोडिंग हैमिंग दूरी को कम करने के लिए एक कोडवर्ड चुनती है:

अथार्त वह कोडवर्ड चुनें जो के जितना समीप हो सकता है ।

ध्यान दें कि यदि असतत मेमोरी रहित चैनल पर त्रुटि की संभावना सख्ती से आधे से कम है, तो न्यूनतम दूरी डिकोडिंग अधिकतम संभावना डिकोडिंग के समान है, क्योंकि यदि

जब:

जो (चूँकि p आधे से भी कम है) d को न्यूनतम करके अधिकतम किया जाता है।

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

  1. संभावना कोई त्रुटि उत्पन्न होना प्रतीक की स्थिति से स्वतंत्र है।
  2. त्रुटियाँ स्वतंत्र घटनाएँ हैं – संदेश में एक स्थान पर त्रुटि अन्य पदों को प्रभावित नहीं करती है।

ये धारणाएँ बाइनरी सममित चैनल पर प्रसारण के लिए उचित हो सकती हैं। वे डीवीडी जैसे अन्य मीडिया के लिए अनुचित हो सकते हैं, जहां डिस्क पर एक खरोंच अनेक समीप प्रतीकों या कोडवर्ड में त्रुटि का कारण बन सकती है।

अन्य डिकोडिंग विधियों की तरह, गैर-अद्वितीय डिकोडिंग के लिए एक सम्मेलन पर सहमति होनी चाहिए।

सिंड्रोम डिकोडिंग

सिंड्रोम डिकोडिंग एक ध्वनि चैनल पर एक रैखिक कोड को डिकोड करने का एक अत्यधिक कुशल विधि है, अथार्त जिस चैनल पर त्रुटियां होती हैं। संक्षेप में, सिंड्रोम डिकोडिंग एक कम लुकअप तालिका का उपयोग करके न्यूनतम दूरी डिकोडिंग है। यह कोड की रैखिकता द्वारा अनुमत है।[3]

मान लीजिए कि समता-जाँच आव्यूह के साथ लंबाई और न्यूनतम दूरी का एक रैखिक कोड है। तो स्पष्ट रूप से तक सही करने में सक्षम है

चैनल द्वारा की गई त्रुटियाँ (यदि इससे अधिक नहीं)। त्रुटियां की जाती हैं तो न्यूनतम दूरी डिकोडिंग अभी भी गलत विधि से प्रसारित कोडवर्ड को सही रूप से डिकोड करेगी)।

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

सभी के लिए सिंड्रोम डिकोडिंग समता आव्यूह की संपत्ति का लाभ उठाती है:

सभी के लिए . प्राप्त का सिंड्रोम परिभाषित किया गया है:

बाइनरी सममित चैनल में एमएल डिकोडिंग करने के लिए, किसी को आकार की एक पूर्व-गणना की गई तालिका को देखना होगा, जिसमें हे को पर मानचित्र किया जाएगा।

ध्यान दें कि यह मानक सरणी की तुलना में पहले से ही अधिक कम कॉम्प्लेक्सिटी वाला है।

चूँकि इस धारणा के अनुसार कि ट्रांसमिशन के समय t से अधिक त्रुटियाँ नहीं की गईं, रिसीवर आकार की एक और कम तालिका में का मान देख सकता है

सूची डिकोडिंग

सूचना सेट डिकोडिंग

यह लास वेगास एल्गोरिथ्म -संभाव्य विधियों का एक वरग है जो इस अवलोकन पर आधारित है कि सभी त्रुटि-स्थितियों का अनुमान लगाने की तुलना में पर्याप्त त्रुटि-मुक्त स्थितियों का अनुमान लगाना सरल है।

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

यदि त्रुटियाँ हुईं, स्तंभों के ऐसे भाग्यशाली चयन की संभावना दी गई है

इस पद्धति में विभिन्न विधियों से सुधार किया गया है, उदा. स्टर्न द्वारा[4]और कैंट्यूट और सेंड्रिएर।[5]

आंशिक प्रतिक्रिया अधिकतम संभावना

आंशिक प्रतिक्रिया अधिकतम संभावना (पीआरएमएल) चुंबकीय डिस्क या टेप ड्राइव के हेड से अशक्त एनालॉग सिग्नल को डिजिटल सिग्नल में परिवर्तित करने की एक विधि है।

विटरबी डिकोडर

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

इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए)

असममित टीडब्ल्यूआरसी प्रणाली के लिए इष्टतम निर्णय डिकोडिंग एल्गोरिदम (ओडीडीए)।[6]

यह भी देखें

संदर्भ

  1. Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). "Using Linear Programming to Decode Binary Linear Codes". IEEE Transactions on Information Theory. 51 (3): 954–972. doi:10.1109/TIT.2004.842696. S2CID 3120399.
  2. Aji, Srinivas M.; McEliece, Robert J. (March 2000). "The Generalized Distributive Law" (PDF). IEEE Transactions on Information Theory. 46 (2): 325–343. doi:10.1109/18.825794.
  3. Beutelspacher, Albrecht; Rosenbaum, Ute (1998). Projective Geometry. Cambridge University Press. p. 190. ISBN 0-521-48277-1.
  4. Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. Springer-Verlag. pp. 106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.
  5. Ohta, Kazuo; Pei, Dingyi, eds. (1998). Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp. 187–199. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.
  6. Siamack Ghadimi (2020), Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;, Universal Journal of Electrical and Electronic Engineering


अग्रिम पठन