कोडिंग थ्योरी: Difference between revisions

[[File:Hamming.jpg|thumb|[[हैमिंग दूरी]] का द्वि-आयामी दृश्य, कोडिंग सिद्धांत में एक महत्वपूर्ण उपाय।]][[कोड]]िंग सिद्धांत विशिष्ट अनुप्रयोगों के लिए कोड के गुणों और उनकी उपयुक्तता का अध्ययन है। कोड का उपयोग डेटा संपीड़न, [[क्रिप्टोग्राफी]], त्रुटि का पता लगाने और सुधार, [[डेटा ट्रांसमिशन]] और [[आधार सामग्री भंडारण]] के लिए किया जाता है। कुशल और विश्वसनीय डेटा ट्रांसमिशन विधियों को डिजाइन करने के उद्देश्य से विभिन्न वैज्ञानिक विषयों-जैसे [[सूचना सिद्धांत]], [[विद्युत अभियन्त्रण]], गणित, [[भाषा विज्ञान]] और [[कंप्यूटर विज्ञान]] द्वारा कोड का अध्ययन किया जाता है। इसमें आमतौर पर अतिरेक को हटाना और संचरित डेटा में त्रुटियों का सुधार या पता लगाना शामिल है।

# त्रुटि का पता लगाने और सुधार (या चैनल कोडिंग)

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

त्रुटि का पता लगाने और सुधार ट्रांसमिशन चैनल पर मौजूद गड़बड़ी के लिए ट्रांसमिशन को अधिक मजबूत बनाने के लिए स्रोत से डेटा में उपयोगी [[अतिरेक (सूचना सिद्धांत)]] जोड़ता है। त्रुटि सुधार का उपयोग करने वाले कई अनुप्रयोगों के बारे में सामान्य उपयोगकर्ता को पता नहीं हो सकता है। एक विशिष्ट [[कॉम्पैक्ट डिस्क डिजिटल ऑडियो]] (सीडी) खरोंच और धूल को ठीक करने के लिए रीड-सोलोमन कोड का उपयोग करता है। इस एप्लिकेशन में ट्रांसमिशन चैनल सीडी ही है। उच्च आवृत्ति रेडियो प्रसारण के लुप्त होने और शोर को ठीक करने के लिए सेल फोन भी कोडिंग तकनीकों का उपयोग करते हैं। डेटा मोडेम, टेलीफोन प्रसारण, और [[नासा डीप स्पेस नेटवर्क]] सभी बिट्स प्राप्त करने के लिए चैनल कोडिंग तकनीकों को नियोजित करते हैं, उदाहरण के लिए [[टर्बो कोड]] और [[एलडीपीसी कोड]]।<!--Kvng RTH-->

 

 

== कोडिंग सिद्धांत का इतिहास ==

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

1972 में, एन. अहमद ने असतत कोज्या परिवर्तन (DCT) का प्रस्ताव रखा, जिसे उन्होंने 1973 में टी. नटराजन और के.आर. राव के साथ विकसित किया।<ref name="Ahmed">{{cite web|url=https://www.scribd.com/doc/52879771/DCT-History|title=मैं असतत कोसाइन परिवर्तन के साथ कैसे आया|author=Nasir Ahmed|publisher = Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5|author-link=N. Ahmed}}</ref> डीसीटी सबसे व्यापक रूप से इस्तेमाल किया जाने वाला हानिकारक संपीड़न एल्गोरिदम है, जो [[जेपीईजी]], [[बेचा]]ईजी और एमपी 3 जैसे मल्टीमीडिया प्रारूपों का आधार है।

{{main|Data compression}}

डेटा को एक यादृच्छिक चर के रूप में देखा जा सकता है <math>X:\Omega\to\mathcal{X}</math>, कहाँ पे <math>x \in \mathcal{X}</math> संभावना से प्रकट होता है <math>\mathbb{P}[X=x]</math>.

डेटा एक [[वर्णमाला (कंप्यूटर विज्ञान)]] पर स्ट्रिंग्स (शब्दों) द्वारा एन्कोड किया गया है <math>\Sigma</math>.

एक कोड एक कार्य है

<math>C(x)</math> से जुड़ा कोड वर्ड है <math>x</math>.

कूट शब्द की लंबाई के रूप में लिखा जाता है

एक कोड की अपेक्षित लंबाई है

# <math>C:\mathcal{X}\to\Sigma^*</math> चर-लंबाई कोड है # गैर-एकवचन कोड | गैर-एकवचन अगर [[इंजेक्शन समारोह]]

# <math>C:\mathcal{X}^*\to\Sigma^*</math> विशिष्ट रूप से डिकोड करने योग्य कोड है # विशिष्ट रूप से डिकोड करने योग्य कोड यदि इंजेक्टिव है।

# <math>C:\mathcal{X}\to\Sigma^*</math> चर-लंबाई कोड है # उपसर्ग कोड यदि <math>C(x_1)</math> का उपसर्ग नहीं है <math>C(x_2)</math> (और इसके विपरीत)।

=== सिद्धांत ===

किसी स्रोत की एन्ट्रापी (सूचना सिद्धांत) सूचना का माप है। मूल रूप से, स्रोत कोड स्रोत में मौजूद अतिरेक को कम करने का प्रयास करते हैं, और कम बिट्स वाले स्रोत का प्रतिनिधित्व करते हैं जो अधिक जानकारी रखते हैं।

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

== चैनल कोडिंग ==

{{main|Error detection and correction}}

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

डिस्क पर डेटा को फैलाने के लिए सीडी क्रॉस-इंटरलीव्ड रीड-सोलोमन कोडिंग का उपयोग करती हैं।<ref>

अन्य कोड विभिन्न अनुप्रयोगों के लिए अधिक उपयुक्त हैं। गहरे अंतरिक्ष संचार रिसीवर के [[थर्मल शोर]] से सीमित होते हैं जो एक फटने वाली प्रकृति की तुलना में निरंतर प्रकृति का अधिक होता है। इसी तरह, नैरोबैंड मोडेम टेलीफोन नेटवर्क में मौजूद शोर से सीमित होते हैं और निरंतर गड़बड़ी के रूप में भी बेहतर तरीके से तैयार किए जाते हैं।{{Citation needed|date=July 2008}} सेल फोन तेजी से लुप्त होती के अधीन हैं। उपयोग की जाने वाली उच्च आवृत्तियाँ सिग्नल के तेजी से लुप्त होने का कारण बन सकती हैं, भले ही रिसीवर कुछ इंच आगे बढ़ जाए। फिर से चैनल कोड का एक वर्ग है जो लुप्त होती का मुकाबला करने के लिए डिज़ाइन किया गया है।{{Citation needed|date=July 2008}}

बीजगणितीय कोडिंग सिद्धांत को मूल रूप से दो प्रमुख प्रकार के कोड में विभाजित किया गया है:{{Citation needed|date=July 2008}}

* संवादात्मक कोड

यह कोड के निम्नलिखित तीन गुणों का विश्लेषण करता है - मुख्य रूप से:{{Citation needed|date=July 2008}}

* मुख्य रूप से हैमिंग [[दूरी]] का उपयोग करते हुए दो वैध कोड शब्दों के बीच न्यूनतम दूरी, कभी-कभी [[ली दूरी]] जैसी अन्य दूरी भी

{{Main|Block code}}

रैखिक ब्लॉक कोड में [[रैखिकता]] का गुण होता है, अर्थात किन्हीं दो कोडवर्ड का योग भी एक कोड शब्द होता है, और उन्हें ब्लॉक में स्रोत बिट्स पर लागू किया जाता है, इसलिए नाम रैखिक ब्लॉक कोड होता है। ऐसे ब्लॉक कोड हैं जो रैखिक नहीं हैं, लेकिन यह साबित करना मुश्किल है कि इस संपत्ति के बिना एक कोड अच्छा है।<ref name=terras/>

रेखीय ब्लॉक कोड को उनके प्रतीक अक्षर (जैसे, बाइनरी या टर्नरी) और पैरामीटर (एन, एम, डी) द्वारा संक्षेपित किया जाता है_min)<ref name=blahut/>कहाँ पे

# एम स्रोत प्रतीकों की संख्या है जो एक बार में एन्कोडिंग के लिए उपयोग की जाएगी,

# डी_minकोड के लिए न्यूनतम हैमिंग दूरी है।

# [[समता द्वियक]]

# [[बहुपद कोड]] (जैसे, BCH कोड)

# रीड-सोलोमन त्रुटि सुधार|रीड-सोलोमन कोड

# [[हैमिंग बाध्य]]

ब्लॉक कोड [[गोलाकार पैकिंग]] समस्या से जुड़े हैं, जिस पर पिछले कुछ वर्षों में कुछ ध्यान दिया गया है। दो आयामों में, कल्पना करना आसान है। टेबल पर पेनीज़ का एक गुच्छा लें और उन्हें एक साथ धकेलें। नतीजा मधुमक्खी के घोंसले की तरह एक हेक्सागोन पैटर्न है। लेकिन ब्लॉक कोड अधिक आयामों पर निर्भर करते हैं जिन्हें आसानी से नहीं देखा जा सकता है। गहरे अंतरिक्ष संचार में प्रयुक्त शक्तिशाली (24,12) बाइनरी गोले कोड 24 आयामों का उपयोग करता है। यदि एक बाइनरी कोड के रूप में उपयोग किया जाता है (जो कि यह आमतौर पर होता है) तो आयाम कोडवर्ड की लंबाई को संदर्भित करते हैं जैसा कि ऊपर परिभाषित किया गया है।

कोडिंग का सिद्धांत एन-आयामी क्षेत्र मॉडल का उपयोग करता है। उदाहरण के लिए, टेबलटॉप पर एक सर्कल में कितने पैसे पैक किए जा सकते हैं, या 3 आयामों में कितने मार्बल्स ग्लोब में पैक किए जा सकते हैं। अन्य विचार एक कोड की पसंद दर्ज करते हैं। उदाहरण के लिए, एक आयताकार बॉक्स की बाधा में हेक्सागोन पैकिंग कोनों पर खाली जगह छोड़ देगी। जैसे-जैसे आयाम बड़े होते जाते हैं, रिक्त स्थान का प्रतिशत छोटा होता जाता है। लेकिन कुछ आयामों पर, पैकिंग सभी जगह का उपयोग करती है और ये कोड तथाकथित सही कोड होते हैं। पैरामीटर संतोषजनक (2<sup>आर</सुप> - 1, 2^r - 1 - r, 3), और [23,12,7] बाइनरी और [11,6,5] टर्नरी गोले कोड।<ref name=terras>

{{cite book | title = Fourier Analysis on Finite Groups and Applications |first=Audrey |last=Terras |author-link=Audrey Terras| publisher = [[Cambridge University Press]] | year = 1999 | isbn = 978-0-521-45718-7 | url = https://archive.org/details/fourieranalysiso0000terr | url-access = registration | page = [https://archive.org/details/fourieranalysiso0000terr/page/195 195] }}</ref><ref name=blahut>{{cite book |title = डेटा ट्रांसमिशन के लिए बीजगणितीय कोड|first=Richard E. |last=Blahut | publisher = Cambridge University Press | year = 2003 | isbn = 978-0-521-55374-2 | url = https://books.google.com/books?id=n0XHMY58tL8C&pg=PA60}}

एक अन्य कोड गुण पड़ोसियों की संख्या है जो एक एकल कोडवर्ड हो सकता है।<ref name=schlegel>

  }}</ref>

एक उदाहरण के रूप में फिर से पेनीज़ पर विचार करें। पहले हम पैसे को एक आयताकार ग्रिड में पैक करते हैं। प्रत्येक पेनी में 4 निकटवर्ती पड़ोसी होंगे (और 4 कोनों पर जो दूर हैं)। एक षट्भुज में, प्रत्येक पैसे में 6 निकट पड़ोसी होंगे। जब हम आयाम बढ़ाते हैं तो निकट पड़ोसियों की संख्या बहुत तेजी से बढ़ती है। नतीजा यह है कि रिसीवर को पड़ोसी चुनने के लिए शोर के तरीकों की संख्या (इसलिए एक त्रुटि) भी बढ़ती है। यह ब्लॉक कोड और वास्तव में सभी कोड की मूलभूत सीमा है। किसी एक पड़ोसी के लिए त्रुटि करना कठिन हो सकता है, लेकिन पड़ोसियों की संख्या काफी बड़ी हो सकती है, इसलिए कुल त्रुटि संभावना वास्तव में पीड़ित होती है।<ref name=schlegel/>

कई अनुप्रयोगों में रैखिक ब्लॉक कोड के गुणों का उपयोग किया जाता है। उदाहरण के लिए, रेखीय ब्लॉक कोड के सिंड्रोम-कोसेट विशिष्टता गुण का उपयोग ट्रेलिस को आकार देने में किया जाता है,<ref>{{cite journal |first=G.D. Jr. |last=Forney |author-link=Dave Forney |title=ट्रेलिस को आकार देना|journal=IEEE Transactions on Information Theory |volume=38 |issue=2 Pt 2 |pages=281–300 |date=March 1992 |doi=10.1109/18.119687 |s2cid=37984132 }}</ref> सबसे प्रसिद्ध [[आकार देने वाले कोड]]ों में से एक।

==== संवादात्मक कोड ====

{{Main|Convolutional code}}

इसलिए हम आम तौर पर सिस्टम कन्वेन्शनल एनकोडर का