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

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

नोटेशन

$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: Maximum likelihood

एक प्राप्त वेक्टर दिया गया $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}$ लंबाई का एक रैखिक कोड है $n$ और न्यूनतम दूरी $d$ समता-जांच मैट्रिक्स के साथ $H$. फिर स्पष्ट रूप से $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}$, मानचित्रण $He$ को $e$.

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

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

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

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

Main article: List decoding

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

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

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

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

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

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

Main article: PRML

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

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

Main article: Viterbi decoder

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

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

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

यह भी देखें

• चिंता मत करो अलार्म
• त्रुटि का पता लगाना और सुधार करना
• निषिद्ध इनपुट

अग्रिम पठन

• 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.