कोडिंग थ्योरी

हैमिंग दूरी का द्वि-आयामी दृश्य, कोडिंग सिद्धांत में एक महत्वपूर्ण उपाय।

कोडिंग थ्योरी विशिष्ट अनुप्रयोगों के लिए कोड के गुणों और उनकी उपयुक्तता का अध्ययन है। कोड का उपयोग डेटा संपीड़न, क्रिप्टोग्राफी, त्रुटि का पता लगाने और सुधार, डेटा ट्रांसमिशन और डेटा भंडारण के लिए किया जाता है। कुशल और विश्वसनीय डेटा ट्रांसमिशन विधियों की रचना करने के उद्देश्य से विभिन्न वैज्ञानिक विषयों जैसे सूचना सिद्धांत, विद्युत अभियन्त्रण, गणित, भाषा विज्ञान और कंप्यूटर विज्ञान द्वारा कोड का अध्ययन किया जाता है। इसमें आमतौर पर अतिरेक को हटाना और संचरित डेटा में त्रुटियों का सुधार या पता लगाना सम्मिलित है।

कोडिंग चार प्रकार की होती है:

1. डेटा संपीड़न (या स्रोत कोडिंग)
2. त्रुटि नियंत्रण (या माध्यम कोडिंग)
3. क्रिप्टोग्राफी
4. लाइन कोड

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

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

कोडिंग थ्योरी का इतिहास

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

बाइनरी भाषा में कोड 1949 में विकसित किया गया था। यह एक त्रुटि-सुधार कोड है जो प्रत्येक 24-बिट शब्द में तीन त्रुटियों को ठीक करने और चौथे का पता लगाने में सक्षम है।

रिचर्ड हैमिंग ने 1968 में बेल लैब्स में संख्यात्मक तरीकों, स्वचालित कोडिंग सिस्टम, और त्रुटि-पता लगाने और त्रुटि-सुधार कोड में अपने काम के लिए ट्यूरिंग अवार्ड जीता। उन्होंने हैमिंग कोड, हैमिंग विंडो, हैमिंग नंबर और हैमिंग दूरी के रूप में जानी जाने वाली अवधारणाओं का आविष्कार किया।

1972 में, एन. अहमद ने असतत कोज्या परिवर्तन (डीसीटी) का प्रस्ताव रखा, जिसे उन्होंने 1973 में टी. नटराजन और के.आर. राव के साथ विकसित किया। डीसीटी सबसे व्यापक रूप से इस्तेमाल किया जाने वाला लॉसी संपीड़न एल्गोरिदम है, जो जेपीईजी, एमपीईजी और एमपी3 जैसे मल्टीमीडिया प्रारूपों का आधार है।

स्रोत कोडिंग

Main article: आधार - सामग्री संकोचन

बेचा

Main article: आधार - सामग्री संकोचन

स्रोत कोडिंग का उद्देश्य स्रोत डेटा लेना और उसे छोटा करना है।

परिभाषा

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

डेटा वर्णमाला $\Sigma$ पर स्ट्रिंग्स (शब्दों) द्वारा एन्कोड किया गया है|

कोड एक फलन है

$C:{\mathcal {X}}\to \Sigma ^{*}$ (या $\Sigma ^{+}$ अगर खाली स्ट्रिंग वर्णमाला का हिस्सा नहीं है)।

$C(x)$ से जुड़ा कोड वर्ड $x$ है |

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

$l(C(x)).$

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

$l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].$

कूट शब्दों का योग $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$.

खाली स्ट्रिंग का कोड शब्द ही खाली स्ट्रिंग है:

$C(\epsilon )=\epsilon$

गुण

1. $C:{\mathcal {X}}\to \Sigma ^{*}$ गैर-एकवचन अगर अंत:क्षेपक है।
2. $C:{\mathcal {X}}^{*}\to \Sigma ^{*}$विशिष्ट रूप से डिकोड करने योग्य कोड यदि अंत:क्षेपक है।
3. $C:{\mathcal {X}}\to \Sigma ^{*}$ तात्कालिक यदि $C(x_{1})$, $C(x_{2})$का उपसर्ग नहीं है (और इसके विपरीत भी)।

थ्योरी

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

डेटा संपीड़न जो स्पष्ट रूप से एक विशेष अनुमानित संभाव्यता मॉडल के अनुसार संदेशों की औसत लंबाई को कम करने की कोशिश करता है, एन्ट्रापी एन्कोडिंग कहलाता है।

स्रोत कोडिंग योजनाओं द्वारा उपयोग की जाने वाली विभिन्न तकनीकें स्रोत की एन्ट्रापी की सीमा को प्राप्त करने का प्रयास करती हैं। C(x) ≥ H(x), जहां H(x) स्रोत (बिटरेट) की एन्ट्रापी है, और C(x) संपीड़न के बाद बिटरेट है। विशेष रूप से, स्रोत की एंट्रॉपी से बेहतर कोई स्रोत कोडिंग योजना नहीं हो सकती है।

उदाहरण

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

माध्यम कोडिंग

Main article: त्रुटि का पता लगाना और सुधार

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

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

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

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

रैखिक कोड

Main article: रैखिक कोड

बीजगणितीय कोडिंग थ्योरी शब्द कोडिंग थ्योरी के उप-क्षेत्र को दर्शाता है जहां कोड के गुणों को बीजगणितीय पदों में व्यक्त किया जाता है और फिर आगे शोध किया जाता है।

बीजगणितीय कोडिंग थ्योरी को मूल रूप से दो प्रमुख प्रकार के कोड में विभाजित किया गया है:

• रैखिक ब्लॉक कोड
• कोंवोलुशनल कोड

यह कोड के निम्नलिखित तीन गुणों का विश्लेषण करता है - मुख्य रूप से:

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

रैखिक ब्लॉक कोड

Main article: ब्लॉक कोड

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

रेखीय ब्लॉक कोड को उनके प्रतीक अक्षर (जैसे, बाइनरी या टर्नरी) और पैरामीटर (n,m,d_min) द्वारा संक्षेपित किया जाता है जहाँ पर

1. n कोडवर्ड की लंबाई है, प्रतीकों में,
2. m स्रोत प्रतीकों की संख्या है जो एक बार में एन्कोडिंग के लिए उपयोग की जाएगी,
3. d_min कोड के लिए न्यूनतम हैमिंग दूरी है।

कई प्रकार के रैखिक ब्लॉक कोड हैं, जैसे

1. चक्रीय कोड (जैसे, हैमिंग कोड)
2. पुनरावृत्ति कोड
3. समतुल्य कोड
4. बहुपद कोड (जैसे, बीसीएच कोड)
5. रीड-सोलोमन कोड
6. बीजगणितीय ज्यामितीय कोड
7. रीड-मुलर कोड
8. संपन्न कोड

ब्लॉक कोड स्फीयर पैकिंग समस्या से जुड़े हैं, जिस पर पिछले कुछ वर्षों में कुछ ध्यान दिया गया है। दो आयामों में, कल्पना करना आसान है। टेबल पर सिक्कों का गुच्छा लें और उन्हें एक साथ बिखेर दें। नतीजा मधुमक्खी के घोंसले की तरह एक हेक्सागोन पैटर्न है। लेकिन ब्लॉक कोड अधिक आयामों पर निर्भर करते हैं जिन्हें आसानी से नहीं देख�