डिकोडिंग विधियाँ

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

नोटेशन

$C\subset \mathbb {F} _{2}^{n}$ को लंबाई $n$; $x,y$ के साथ एक बाइनरी कोड माना जाता है, जो $\mathbb {F} _{2}^{n}$के तत्व होंगे; और $d(x,y)$ उन तत्वों के बीच की दूरी है।

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

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

$\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})$

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

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

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

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

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

Further information: अधिकतम संभाव्यता

प्राप्त सदिश $x\in \mathbb {F} _{2}^{n}$ को देखते हुए अधिकतम संभावना डिकोडिंग एक कोडवर्ड $y\in C$ चुनती है जो अधिकतम करता है

$\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})$,

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

${\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}$

$\mathbb {P} (x{\mbox{ received}})$ को ठीक करने पर, x को पुनर्गठित किया जाता है और $\mathbb {P} (y{\mbox{ sent}})$ स्थिर होता है क्योंकि सभी कोडवर्ड भेजे जाने की समान संभावना होती है। इसलिए, $\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})$ को वेरिएबल y के एक फलन के रूप में अधिकतम किया जाता है, ठीक उसी समय जब $\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})$को अधिकतम किया जाता है, और प्रमाण इस प्रकार होता है।

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

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

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

प्राप्त कोडवर्ड $x\in \mathbb {F} _{2}^{n}$ को देखते हुए, न्यूनतम दूरी डिकोडिंग हैमिंग दूरी को कम करने के लिए एक कोडवर्ड $y\in C$ चुनती है:

$d(x,y)=\#\{i:x_{i}\not =y_{i}\}$

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

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

$d(x,y)=d,\,$

जब:

${\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}$

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

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

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

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

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

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

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

मान लीजिए कि $C\subset \mathbb {F} _{2}^{n}$ समता-जाँच आव्यूह $H$ के साथ लंबाई $n$ और न्यूनतम दूरी $d$ का एक रैखिक कोड है। तो स्पष्ट रूप से $C$ तक सही करने में सक्षम है

$t=\left\lfloor {\frac {d-1}{2}}\right\rfloor$

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

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

$d(c,z)\leq d(y,z)$

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

$Hx=0$

सभी के लिए $x\in C$. प्राप्त का सिंड्रोम $z=x+e$ परिभाषित किया गया है:

$Hz=H(x+e)=Hx+He=0+He=He$

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

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

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

${\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}$

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

Main article: सूची डिकोडिंग

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

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

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

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

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

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

Main article: पीआरएमएल

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

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

Main article: विटरबी डिकोडर

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

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

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

यह भी देखें

• डोंट केयर अलार्म
• एरर डिटेक्शन और करेक्शन
• फोर्बिडन इनपुट

अग्रिम पठन

• Hill, Raymond (1986). A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. ISBN 978-0-19-853803-5.
• Pless, Vera (1982). Introduction to the theory of error-correcting codes. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons. ISBN 978-0-471-08684-0.
• van Lint, Jacobus H. (1992). Introduction to Coding Theory. Graduate Texts in Mathematics (GTM). Vol. 86 (2 ed.). Springer-Verlag. ISBN 978-3-540-54894-2.