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

Error creating thumbnail:

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

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

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

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

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

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

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

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

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

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

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

स्रोत कोडिंग

Main article: Data compression

बेचा

Main article: Data compression

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

परिभाषा

डेटा को एक यादृच्छिक चर के रूप में देखा जा सकता है $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: Error detection and correction

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

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

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

रैखिक कोड

Main article: Linear code

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