वेरिएबल-लेंथ कोड: Difference between revisions

Revision as of 02:51, 17 July 2023

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

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

प्रसिद्ध चर-लंबाई कोडिंग रणनीतियों के कुछ उदाहरण हफ़मैन कोडिंग, लेम्पेल-ज़िव कोडिंग, अंकगणितीय कोडिंग और संदर्भ-अनुकूली चर-लंबाई कोडिंग होती हैं।

कोड और उनके एक्सटेंशन

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

औपचारिक भाषा सिद्धांत से शब्दों का उपयोग करते हुए, स्पष्ट गणितीय परिभाषा इस प्रकार है: मान ले की $S$ और $T$ दो परिमित समुच्चय होता है, जिन्हें क्रमशः स्रोत और लक्ष्य वर्णमाला कहा जाता है। संकेतवाली $C:S\to T^{*}$ संपूर्ण कार्य होता है^[1] जो प्रत्येक प्रतीक $S$ से $T$ पर प्रतीकों के अनुक्रम को मानचित्रित करता है, और $C$ का विस्तार औपचारिक भाषा सिद्धांत में समरूपता और ई-मुक्त समरूपता $S^{*}$ में $T^{*}$ किया जाता, जो स्वाभाविक रूप से स्रोत प्रतीकों के प्रत्येक अनुक्रम को लक्ष्य प्रतीकों के अनुक्रम में मानचित्रित करता है, इसे इसके विस्तार के रूप में जाना जाता है।

चर-लंबाई कोड की कक्षाएं

चर-लंबाई कोड को गैर-एकवचन कोड, विशिष्ट रूप से डिकोड करने योग्य कोड और उपसर्ग कोड के रूप में घटती व्यापकता के क्रम में कठोरता से नेस्ट किया जा सकता है। उपसर्ग कोड सदैव विशिष्ट रूप से डिकोड करने योग्य होते हैं, और बदले में ये सदैव गैर-एकवचन होते हैं।

गैर-एकवचन कोड

एक कोड गैर-एकवचन होता है यदि प्रत्येक स्रोत प्रतीक को भिन्न गैर-रिक्त बिट स्ट्रिंग में मानचित्रित किया जाता है, अर्थात् स्रोत प्रतीकों से बिट स्ट्रिंग्स तक मानचित्रित इंजेक्टिव होता है।

उदाहरण के लिए, मानचित्रित किये गये $M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}$ गैर-एकवचन नहीं होते है क्योंकि a और b दोनों ही बिट स्ट्रिंग 0 पर मानचित्रित करते हैं; इस मानचित्रि का प्रत्येक विस्तार हानिपूर्ण (गैर-दोषरहित) कोडिंग उत्पन्न करता है। ऐसी एकल कोडिंग तब भी उपयोगी हो सकती है जब जानकारी का कुछ नुकसान स्वीकार्य हो (उदाहरण के लिए जब ऐसे कोड का उपयोग ऑडियो या वीडियो संपीड़न में किया जाता है, जहां हानिपूर्ण कोडिंग स्रोत परिमाणीकरण (सिग्नल प्रोसेसिंग) के समान्तर हो जाती है)।
यघपि , मानचित्रित किये गये $M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}$ गैर-एकवचन होता है; इसका विस्तार दोषरहित कोडिंग उत्पन्न करता है, जो सामान्य डेटा स्थानान्तरण के लिए उपयोगी होता है (यघपि इस सुविधा की सदैव आवश्यकता नहीं होती है)। ध्यान दें कि गैर-एकवचन कोड का स्रोत से अधिक कॉम्पैक्ट होना आवश्यक नहीं होता है (और कई अनुप्रयोगों में, बड़ा कोड उपयोगी होता है, उदाहरण के लिए एन्कोडिंग या स्नथानातंरण त्रुटियों का पता लगाने और/या पुनर्प्राप्त करने के विधि के रूप में, या किसी स्रोत को अज्ञात हस्तक्षेप से बचाने के लिए सुरक्षा अनुप्रयोग)।

विशिष्ट रूप से डिकोड करने योग्य कोड

कोड विशिष्ट रूप से डिकोड करने योग्य होता है यदि उसका विस्तार § गैर-एकवचन होता है। क्या कोई दिया गया कोड विशिष्ट रूप से डिकोड करने योग्य होता है, इसका निर्णय सार्डिनस-पैटरसन कलन विधि से किया जा सकता है।

मानचित्रण $M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}$ विशिष्ट रूप से डिकोड करने योग्य होते है (इसे मानचित्र में प्रत्येक लक्ष्य बिट स्ट्रिंग के बाद फॉलो-समूह को देखकर प्रदर्शित किया जा सकता है, क्योंकि जैसे ही हम 0 बिट देखते हैं, प्रत्येक बिटस्ट्रिंग समाप्त हो जाती है जो लंबे समय तक वैध कोड बनाने के लिए किसी भी उपस्थित कोड का पालन नहीं कर सकती है। मानचित्र, यघपि स्पष्ट रूप से नया कोड प्रारंभ करता है)।
कोड $M_{2}$ पर फिर पिछले अनुभाग से विचार करें।^[1] यह कोड विशिष्ट रूप से डिकोड करने योग्य नहीं होते है, क्योंकि स्ट्रिंग 011101110011 की व्याख्या कोडवर्ड 01110 - 1110 - 011 के अनुक्रम के रूप में की जा सकती है, लेकिन कोडवर्ड 011 - 1 - 011 - 10011 के अनुक्रम के रूप में भी की जा सकती है। इस एन्कोडेड स्ट्रिंग के दो संभावित डिकोडिंग सीडीबी और बेब द्वारा दिए गए हैं। यघपि , ऐसा कोड तब उपयोगी होता है जब सभी संभावित स्रोत प्रतीकों का समूह पूरी तरह से ज्ञात और सीमित होता है, या जब प्रतिबंध होते हैं (उदाहरण के लिए औपचारिक वाक्यविन्यास) जो यह निर्धारित करते हैं कि इस एक्सटेंशन के स्रोत तत्व स्वीकार्य हैं या नहीं। इस तरह के प्रतिबंध मूल संदेश को डिकोड करने की अनुमति देते हैं, यह जांच कर कि समान प्रतीक पर मानचित्रित किए गए संभावित स्रोत प्रतीकों में से कौन सा उन प्रतिबंधों के अनुसार मान्य होता है।

उपसर्ग कोड

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

उदाहरण मानचित्रण $M_{3}$ पिछले पैराग्राफ में कोई उपसर्ग कोड नहीं होता है क्योंकि बिट स्ट्रिंग 0 को पढ़ने के बाद हम नहीं जानते हैं कि क्या यह स्रोत प्रतीक को एन्कोड करता है, या यदि यह बी या सी प्रतीकों के एन्कोडिंग का उपसर्ग होता है।
उपसर्ग कोड का उदाहरण नीचे दिखाया गया है।

Symbol	Codeword
a	0
b	10
c	110
d	111

एन्कोडिंग और डिकोडिंग का उदाहरण:

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabacdab

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

उपसर्ग कोड का और विशेष स्थति चर-लंबाई मात्रा कोड होता है, जो अनैतिक विधि से बड़े पूर्णांकों को ऑक्टेट के अनुक्रम के रूप में एन्कोड करता है - अर्थात्, प्रत्येक कोडवर्ड 8 बिट्स का गुणक होता है।

लाभ

वैरिएबल-लंबाई कोड का लाभ यह है कि असंभावित स्रोत प्रतीकों को लंबे कोडवर्ड निर्दिष्ट किए जा सकते हैं और संभावित स्रोत प्रतीकों को छोटे कोडवर्ड निर्दिष्ट किए जा सकते हैं, इस प्रकार कम अपेक्षित मूल्य कोडवर्ड लंबाई प्राप्त होती है। उपरोक्त उदाहरण के लिए, यदि (ए, बी, सी, डी) की $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ संभावनाएं थीं, उपरोक्त कोड का उपयोग करके स्रोत प्रतीक का प्रतिनिधित्व करने के लिए उपयोग की जाने वाली बिट्स की अपेक्षित संख्या होगी:

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

चूँकि इस स्रोत की एन्ट्रापी 1.7500 बिट प्रति प्रतीक होती है, यह कोड स्रोत को यथासंभव संपीड़ित करता है जिससे स्रोत को शून्य त्रुटि के साथ पुनर्प्राप्त किया जा सकता है।

यह भी देखें

कंप्यूटिंग में परिवर्तनीय-लंबाई निर्देश समूह

संदर्भ

↑ ^1.0 ^1.1 This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.

अग्रिम पठन

Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001. Draft available online

[:0-1] 1.0 ^1.1 This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.

[1]

@@ Line 1: / Line 1: @@
 {{short description|Code which maps information to a variable number of bits}}
-[[[[कोड]]िंग सिद्धांत]] में,  वेरिएबल-लेंथ कोड  कोड होता है जो स्रोत प्रतीकों को [[ अंश |अंश]] ्स की ''वैरिएबल'' संख्या में मैप करता है।
+[[कोड|कोडिंग]]  सिद्धांत में, '''वेरिएबल-लेंथ कोड''' एक कोड होता है जो स्रोत प्रतीकों को [[ अंश |बिट्स]] की ''वैरिएबल'' संख्या में मानचित्रित करता है।
-परिवर्तनीय-लंबाई कोड स्रोतों को डेटा संपीड़न और ''शून्य'' त्रुटि ([[दोषरहित डेटा संपीड़न]]) के साथ विघटित करने की अनुमति दे सकते हैं और फिर भी प्रतीक द्वारा वापस पढ़ा जा सकता है। सही कोडिंग रणनीति के साथ  [[स्वतंत्र और समान रूप से वितरित यादृच्छिक चर]] | स्वतंत्र और समान रूप से वितरित स्रोत को इसकी [[सूचना एन्ट्रापी]] के करीब मनमाने ढंग से संपीड़ित किया जा सकता है। यह निश्चित-लंबाई कोडिंग विधियों के विपरीत है, जिसके लिए डेटा संपीड़न केवल डेटा के बड़े ब्लॉक के लिए संभव है, और संभावनाओं की कुल संख्या के लघुगणक से परे कोई भी संपीड़न विफलता की  सीमित (हालांकि शायद मनमाने ढंग से छोटी) संभावना के साथ आता है।
+परिवर्तनीय-लंबाई कोड स्रोतों को डेटा संपीड़न और ''शून्य'' त्रुटि ([[दोषरहित डेटा संपीड़न]]) के साथ विघटित करने की अनुमति दे सकते हैं और फिर भी प्रतीक द्वारा पुनः पढ़ा जा सकता है। सही कोडिंग रणनीति के साथ  [[स्वतंत्र और समान रूप से वितरित यादृच्छिक चर|स्वतंत्र और समान रूप से वितरित]] स्रोत को इसकी [[सूचना एन्ट्रापी]] के समीप अनैतिक विधि से संपीड़ित किया जा सकता है। यह निश्चित-लंबाई कोडिंग विधियों के विपरीत होता है, जिसके लिए डेटा संपीड़न मात्र डेटा के बड़े ब्लॉक के लिए संभव होता है, और संभावनाओं की कुल संख्या के लघुगणक से परे कोई भी संपीड़न विफलता की  सीमित (यघपि संभवतया अनैतिक विधि से छोटी) संभावना के साथ आता है।
-प्रसिद्ध चर-लंबाई कोडिंग रणनीतियों के कुछ उदाहरण [[हफ़मैन कोडिंग]], लेम्पेल-ज़िव|लेम्पेल-ज़िव कोडिंग, [[अंकगणितीय कोडिंग]] और [[संदर्भ-अनुकूली चर-लंबाई कोडिंग]] हैं।
+प्रसिद्ध चर-लंबाई कोडिंग रणनीतियों के कुछ उदाहरण [[हफ़मैन कोडिंग]], लेम्पेल-ज़िव कोडिंग, [[अंकगणितीय कोडिंग]] और [[संदर्भ-अनुकूली चर-लंबाई कोडिंग]] होती हैं।
 == कोड और उनके एक्सटेंशन ==
-कोड का विस्तार परिमित लंबाई के स्रोत अनुक्रमों की परिमित लंबाई बिट स्ट्रिंग्स की मैपिंग है, जो मूल कोड द्वारा उत्पादित संबंधित कोडवर्ड को स्रोत अनुक्रम के प्रत्येक प्रतीक के लिए संयोजित करके प्राप्त किया जाता है।
+कोड का विस्तार परिमित लंबाई के स्रोत अनुक्रमों की परिमित लंबाई बिट स्ट्रिंग्स की मानचित्र होते है, जिसको मूल कोड द्वारा उत्पादित संबंधित कोडवर्ड को स्रोत अनुक्रम के प्रत्येक प्रतीक के लिए संयोजित करके प्राप्त किया जाता है।
-[[औपचारिक भाषा सिद्धांत]] से शब्दों का उपयोग करते हुए, सटीक गणितीय परिभाषा इस प्रकार है: चलो <math>S</math> और <math>T</math> दो परिमित सेट हों, जिन्हें क्रमशः स्रोत और लक्ष्य [[वर्णमाला (कंप्यूटर विज्ञान)]] कहा जाता है।  संकेतवाली <math>C: S \to T^*</math>  संपूर्ण कार्य है<ref name=":0" />प्रत्येक प्रतीक को मैप करना <math>S</math>  वर्ड (डेटा प्रकार) पर <math>T</math>, और का विस्तार <math>C</math> औपचारिक भाषा सिद्धांत में  समरूपता#समरूपता और ई-मुक्त समरूपता <math>S^*</math> में <math>T^*</math>, जो स्वाभाविक रूप से स्रोत प्रतीकों के प्रत्येक अनुक्रम को लक्ष्य प्रतीकों के अनुक्रम में मैप करता है, इसे इसके विस्तार के रूप में जाना जाता है।
+[[औपचारिक भाषा सिद्धांत]] से शब्दों का उपयोग करते हुए, स्पष्ट गणितीय परिभाषा इस प्रकार है:  मान ले की <math>S</math> और <math>T</math> दो परिमित समुच्चय होता है, जिन्हें क्रमशः स्रोत और लक्ष्य [[वर्णमाला (कंप्यूटर विज्ञान)|वर्णमाला]] कहा जाता है। '''संकेतवाली''' <math>C: S \to T^*</math>  संपूर्ण कार्य होता है<ref name=":0" /> जो प्रत्येक प्रतीक <math>S</math> से <math>T</math> पर प्रतीकों के अनुक्रम को मानचित्रित करता है, और <math>C</math> का विस्तार औपचारिक भाषा सिद्धांत में  समरूपता और ई-मुक्त समरूपता <math>S^*</math> में <math>T^*</math> किया जाता, जो स्वाभाविक रूप से स्रोत प्रतीकों के प्रत्येक अनुक्रम को लक्ष्य प्रतीकों के अनुक्रम में मानचित्रित  करता है, इसे इसके विस्तार के रूप में जाना जाता है।
 == चर-लंबाई कोड की कक्षाएं ==
-चर-लंबाई कोड को गैर-एकवचन कोड, विशिष्ट रूप से डिकोड करने योग्य कोड और उपसर्ग कोड के रूप में घटती व्यापकता के क्रम में सख्ती से नेस्ट किया जा सकता है। उपसर्ग कोड हमेशा विशिष्ट रूप से डिकोड करने योग्य होते हैं, और बदले में ये हमेशा गैर-एकवचन होते हैं:
+चर-लंबाई कोड को गैर-एकवचन कोड, विशिष्ट रूप से डिकोड करने योग्य कोड और उपसर्ग कोड के रूप में घटती व्यापकता के क्रम में कठोरता से नेस्ट किया जा सकता है। उपसर्ग कोड सदैव विशिष्ट रूप से डिकोड करने योग्य होते हैं, और बदले में ये सदैव गैर-एकवचन होते हैं।
 === गैर-एकवचन कोड ===
-कोड गैर-एकवचन होता है यदि प्रत्येक स्रोत प्रतीक को  अलग गैर-रिक्त बिट स्ट्रिंग में मैप किया जाता है, यानी स्रोत प्रतीकों से बिट स्ट्रिंग्स तक मैपिंग [[ इंजेक्शन |इंजेक्शन]] है।
+एक कोड '''गैर-एकवचन''' होता है यदि प्रत्येक स्रोत प्रतीक को भिन्न गैर-रिक्त बिट स्ट्रिंग में मानचित्रित किया जाता है, अर्थात् स्रोत प्रतीकों से बिट स्ट्रिंग्स तक मानचित्रित [[ इंजेक्शन |इंजेक्टिव]] होता है।
-* उदाहरण के लिए, मैपिंग <math>M_1 = \{\, a\mapsto 0, b\mapsto 0, c\mapsto 1\,\}</math> गैर-एकवचन नहीं है क्योंकि a और b दोनों  ही बिट स्ट्रिंग 0 पर मैप करते हैं; इस मैपिंग का कोई भी विस्तार हानिपूर्ण (गैर-दोषरहित) कोडिंग उत्पन्न करेगा। ऐसी एकल कोडिंग तब भी उपयोगी हो सकती है जब जानकारी का कुछ नुकसान स्वीकार्य हो (उदाहरण के लिए जब ऐसे कोड का उपयोग ऑडियो या वीडियो संपीड़न में किया जाता है, जहां  हानिपूर्ण कोडिंग स्रोत [[ परिमाणीकरण (सिग्नल प्रोसेसिंग) |परिमाणीकरण (सिग्नल प्रोसेसिंग)]] के बराबर हो जाती है)।
+* उदाहरण के लिए, मानचित्रित किये गये  <math>M_1 = \{\, a\mapsto 0, b\mapsto 0, c\mapsto 1\,\}</math> गैर-एकवचन नहीं होते है क्योंकि a और b दोनों ही बिट स्ट्रिंग 0 पर मानचित्रित करते हैं; इस मानचित्रि का प्रत्येक विस्तार हानिपूर्ण (गैर-दोषरहित) कोडिंग उत्पन्न करता है। ऐसी एकल कोडिंग तब भी उपयोगी हो सकती है जब जानकारी का कुछ नुकसान स्वीकार्य हो (उदाहरण के लिए जब ऐसे कोड का उपयोग ऑडियो या वीडियो संपीड़न में किया जाता है, जहां  हानिपूर्ण कोडिंग स्रोत [[ परिमाणीकरण (सिग्नल प्रोसेसिंग) |परिमाणीकरण (सिग्नल प्रोसेसिंग)]] के समान्तर हो जाती है)।
-* यघपि , मैपिंग <math>M_2 = \{\, a \mapsto 1, b \mapsto 011, c\mapsto 01110, d\mapsto 1110, e\mapsto 10011, f\mapsto0\}</math> गैर-एकवचन है; इसका विस्तार दोषरहित कोडिंग उत्पन्न करेगा, जो सामान्य डेटा ट्रांसमिशन के लिए उपयोगी होगा (लेकिन इस सुविधा की हमेशा आवश्यकता नहीं होती है)। ध्यान दें कि गैर-एकवचन कोड का स्रोत से अधिक कॉम्पैक्ट होना आवश्यक नहीं है (और कई अनुप्रयोगों में,  बड़ा कोड उपयोगी होता है, उदाहरण के लिए एन्कोडिंग या ट्रांसमिशन त्रुटियों का पता लगाने और/या पुनर्प्राप्त करने के तरीके के रूप में, या किसी स्रोत को अज्ञात छेड़छाड़ से बचाने के लिए सुरक्षा अनुप्रयोग)।
+* यघपि , मानचित्रित किये गये  <math>M_2 = \{\, a \mapsto 1, b \mapsto 011, c\mapsto 01110, d\mapsto 1110, e\mapsto 10011, f\mapsto0\}</math> गैर-एकवचन होता है; इसका विस्तार दोषरहित कोडिंग उत्पन्न करता है, जो सामान्य डेटा स्थानान्तरण के लिए उपयोगी होता है (यघपि इस सुविधा की सदैव आवश्यकता नहीं होती है)। ध्यान दें कि गैर-एकवचन कोड का स्रोत से अधिक कॉम्पैक्ट होना आवश्यक नहीं होता है (और कई अनुप्रयोगों में,  बड़ा कोड उपयोगी होता है, उदाहरण के लिए एन्कोडिंग या स्नथानातंरण त्रुटियों का पता लगाने और/या पुनर्प्राप्त करने के विधि के रूप में, या किसी स्रोत को अज्ञात हस्तक्षेप से बचाने के लिए सुरक्षा अनुप्रयोग)।
 === विशिष्ट रूप से डिकोड करने योग्य कोड ===
-कोड विशिष्ट रूप से डिकोड करने योग्य होता है यदि उसका विस्तार #नॉन-सिंगुलर कोड|§ नॉन-सिंगुलर हो। क्या कोई दिया गया कोड विशिष्ट रूप से डिकोड करने योग्य है, इसका निर्णय सार्डिनस-पैटरसन एल्गोरिदम से किया जा सकता है।
+कोड '''विशिष्ट रूप से डिकोड''' करने योग्य होता है यदि उसका विस्तार § गैर-एकवचन होता है। क्या कोई दिया गया कोड विशिष्ट रूप से डिकोड करने योग्य होता है, इसका निर्णय सार्डिनस-पैटरसन कलन विधि से किया जा सकता है।
-* मानचित्रण <math>M_3 = \{\, a\mapsto 0, b\mapsto 01, c\mapsto 011\,\}</math> विशिष्ट रूप से डिकोड करने योग्य है (इसे मानचित्र में प्रत्येक लक्ष्य बिट स्ट्रिंग के बाद फॉलो-सेट को देखकर प्रदर्शित किया जा सकता है, क्योंकि जैसे ही हम 0 बिट देखते हैं, प्रत्येक बिटस्ट्रिंग समाप्त हो जाती है जो लंबे समय तक वैध कोड बनाने के लिए किसी भी मौजूदा कोड का पालन नहीं कर सकती है। मानचित्र, लेकिन स्पष्ट रूप से  नया कोड प्रारंभ करता है)।
+* मानचित्रण <math>M_3 = \{\, a\mapsto 0, b\mapsto 01, c\mapsto 011\,\}</math> विशिष्ट रूप से डिकोड करने योग्य होते है (इसे मानचित्र में प्रत्येक लक्ष्य बिट स्ट्रिंग के बाद फॉलो-समूह को देखकर प्रदर्शित किया जा सकता है, क्योंकि जैसे ही हम 0 बिट देखते हैं, प्रत्येक बिटस्ट्रिंग समाप्त हो जाती है जो लंबे समय तक वैध कोड बनाने के लिए किसी भी उपस्थित कोड का पालन नहीं कर सकती है। मानचित्र, यघपि स्पष्ट रूप से  नया कोड प्रारंभ करता है)।
-* कोड पर फिर से विचार करें <math>M_2</math> पिछले अनुभाग से.<ref name=":0">This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.</ref> यह कोड विशिष्ट रूप से डिकोड करने योग्य नहीं है, क्योंकि स्ट्रिंग ''011101110011'' की व्याख्या कोडवर्ड ''01110 - 1110 - 011'' के अनुक्रम के रूप में की जा सकती है, लेकिन कोडवर्ड ''011 - 1 - 011 - 10011'' के अनुक्रम के रूप में भी की जा सकती है। '. इस एन्कोडेड स्ट्रिंग के दो संभावित डिकोडिंग ''सीडीबी'' और ''बेब'' द्वारा दिए गए हैं। यघपि , ऐसा कोड तब उपयोगी होता है जब सभी संभावित स्रोत प्रतीकों का सेट पूरी तरह से ज्ञात और सीमित होता है, या जब प्रतिबंध होते हैं (उदाहरण के लिए  औपचारिक वाक्यविन्यास) जो यह निर्धारित करते हैं कि इस एक्सटेंशन के स्रोत तत्व स्वीकार्य हैं या नहीं। इस तरह के प्रतिबंध मूल संदेश को डिकोड करने की अनुमति देते हैं, यह जांच कर कि समान प्रतीक पर मैप किए गए संभावित स्रोत प्रतीकों में से कौन सा उन प्रतिबंधों के तहत मान्य है।
+* कोड <math>M_2</math> पर फिर  पिछले अनुभाग से विचार करें।<ref name=":0">This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.</ref> यह कोड विशिष्ट रूप से डिकोड करने योग्य नहीं होते है, क्योंकि स्ट्रिंग ''011101110011'' की व्याख्या कोडवर्ड ''01110 - 1110 - 011'' के अनुक्रम के रूप में की जा सकती है, लेकिन कोडवर्ड ''011 - 1 - 011 - 10011'' के अनुक्रम के रूप में भी की जा सकती है। इस एन्कोडेड स्ट्रिंग के दो संभावित डिकोडिंग ''सीडीबी'' और ''बेब'' द्वारा दिए गए हैं। यघपि , ऐसा कोड तब उपयोगी होता है जब सभी संभावित स्रोत प्रतीकों का समूह पूरी तरह से ज्ञात और सीमित होता है, या जब प्रतिबंध होते हैं (उदाहरण के लिए  औपचारिक वाक्यविन्यास) जो यह निर्धारित करते हैं कि इस एक्सटेंशन के स्रोत तत्व स्वीकार्य हैं या नहीं। इस तरह के प्रतिबंध मूल संदेश को डिकोड करने की अनुमति देते हैं, यह जांच कर कि समान प्रतीक पर मानचित्रित  किए गए संभावित स्रोत प्रतीकों में से कौन सा उन प्रतिबंधों के अनुसार मान्य होता है।
 === उपसर्ग कोड ===
-{{Main|Prefix code}}
+{{Main|उपसर्ग कोड}}
-यदि मैपिंग में कोई लक्ष्य बिट स्ट्रिंग नहीं है तो  कोड  उपसर्ग कोड है, जो उसी मैपिंग में  अलग स्रोत प्रतीक के लक्ष्य बिट स्ट्रिंग का उपसर्ग है। इसका मतलब यह है कि प्रतीकों को उनका संपूर्ण कोडवर्ड प्राप्त होने के तुरंत बाद डिकोड किया जा सकता है। इस अवधारणा के लिए आमतौर पर उपयोग किए जाने वाले अन्य नाम उपसर्ग-मुक्त कोड, तात्कालिक कोड या संदर्भ-मुक्त कोड हैं।
+यदि मानचित्रित में कोई लक्ष्य बिट स्ट्रिंग नहीं होती है तो एक कोड एक '''उपसर्ग कोड''' होता है, जो उसी मानचित्रित में  अलग स्रोत प्रतीक के लक्ष्य बिट स्ट्रिंग का उपसर्ग होता है। इसका अर्थ यह है कि प्रतीकों को उनका संपूर्ण कोडवर्ड प्राप्त होने के तुरंत बाद डिकोड किया जा सकता है। इस अवधारणा के लिए सामान्यतः उपयोग किए जाने वाले अन्य नाम '''उपसर्ग-मुक्त कोड''', '''तात्कालिक कोड''' या '''संदर्भ-मुक्त कोड''' होता हैं।
-* उदाहरण मानचित्रण <math>M_3</math> पिछले पैराग्राफ में कोई उपसर्ग कोड नहीं है क्योंकि बिट स्ट्रिंग 0 को पढ़ने के बाद हम नहीं जानते हैं कि क्या यह स्रोत प्रतीक को एन्कोड करता है, या यदि यह बी या सी प्रतीकों के एन्कोडिंग का उपसर्ग है।
+* उदाहरण मानचित्रण <math>M_3</math> पिछले पैराग्राफ में कोई उपसर्ग कोड नहीं होता है क्योंकि बिट स्ट्रिंग 0 को पढ़ने के बाद हम नहीं जानते हैं कि क्या यह स्रोत प्रतीक को एन्कोड करता है, या यदि यह बी या सी प्रतीकों के एन्कोडिंग का उपसर्ग होता है।
 * उपसर्ग कोड का  उदाहरण नीचे दिखाया गया है।
 {| class="wikitable" style="text-align:center; position: relative; left: 1in;" |
@@ Line 45: / Line 45: @@
 ::: {{not a typo|aabacdab}} → 00100110111010 → |0|0|10|0|110|111|0|10| → {{not a typo|aabacdab}}
-उपसर्ग कोड का  विशेष मामला [[ब्लॉक कोड]] है। यहां सभी कोडवर्ड की लंबाई समान होनी चाहिए। उत्तरार्द्ध डेटा संपीड़न के संदर्भ में बहुत उपयोगी नहीं हैं, लेकिन अक्सर [[चैनल कोडिंग]] के संदर्भ में आगे की त्रुटि सुधार के रूप में कार्य करते हैं।
+उपसर्ग कोड का  विशेष स्थिति [[ब्लॉक कोड]] होता है। यहां सभी कोडवर्ड की लंबाई समान होनी चाहिए। उत्तरार्द्ध डेटा संपीड़न के संदर्भ में बहुत उपयोगी नहीं  होता हैं, परन्तु अधिकांशतः [[चैनल कोडिंग]] के संदर्भ में आगे की त्रुटि सुधार के रूप में कार्य करते हैं।
-उपसर्ग कोड का  और विशेष मामला चर-लंबाई मात्रा कोड है, जो मनमाने ढंग से बड़े पूर्णांकों को ऑक्टेट के अनुक्रम के रूप में एन्कोड करता है - यानी, प्रत्येक कोडवर्ड 8 बिट्स का  गुणक है।
+उपसर्ग कोड का और विशेष स्थति चर-लंबाई मात्रा कोड होता है, जो अनैतिक विधि से बड़े पूर्णांकों को ऑक्टेट के अनुक्रम के रूप में एन्कोड करता है - अर्थात्, प्रत्येक कोडवर्ड 8 बिट्स का गुणक होता है।
 == लाभ ==
-वैरिएबल-लंबाई कोड का लाभ यह है कि असंभावित स्रोत प्रतीकों को लंबे कोडवर्ड निर्दिष्ट किए जा सकते हैं और संभावित स्रोत प्रतीकों को छोटे कोडवर्ड निर्दिष्ट किए जा सकते हैं, इस प्रकार कम अपेक्षित मूल्य कोडवर्ड लंबाई मिलती है। उपरोक्त उदाहरण के लिए, यदि (ए, बी, सी, डी) की संभावनाएं थीं <math>\textstyle\left(\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right)</math>, उपरोक्त कोड का उपयोग करके स्रोत प्रतीक का प्रतिनिधित्व करने के लिए उपयोग की जाने वाली बिट्स की अपेक्षित संख्या होगी:
+वैरिएबल-लंबाई कोड का लाभ यह है कि असंभावित स्रोत प्रतीकों को लंबे कोडवर्ड निर्दिष्ट किए जा सकते हैं और संभावित स्रोत प्रतीकों को छोटे कोडवर्ड निर्दिष्ट किए जा सकते हैं, इस प्रकार कम अपेक्षित मूल्य कोडवर्ड लंबाई प्राप्त होती है। उपरोक्त उदाहरण के लिए, यदि (ए, बी, सी, डी) की <math>\textstyle\left(\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right)</math>संभावनाएं थीं, उपरोक्त कोड का उपयोग करके स्रोत प्रतीक का प्रतिनिधित्व करने के लिए उपयोग की जाने वाली बिट्स की अपेक्षित संख्या होगी:
 :: <math>1\times\frac{1}{2}+2\times\frac{1}{4}+3\times\frac{1}{8}+3\times\frac{1}{8}=\frac{7}{4}</math>.
-चूँकि इस स्रोत की एन्ट्रापी 1.7500 बिट प्रति प्रतीक है, यह कोड स्रोत को यथासंभव संपीड़ित करता है ताकि स्रोत को शून्य त्रुटि के साथ पुनर्प्राप्त किया जा सके।
+चूँकि इस स्रोत की एन्ट्रापी 1.7500 बिट प्रति प्रतीक होती है, यह कोड स्रोत को यथासंभव संपीड़ित करता है जिससे स्रोत को शून्य त्रुटि के साथ पुनर्प्राप्त किया जा सकता है।
 == यह भी देखें ==
-* कंप्यूटिंग में परिवर्तनीय-लंबाई निर्देश सेट
+* कंप्यूटिंग में परिवर्तनीय-लंबाई निर्देश समूह
 == संदर्भ ==

Anonymous

Search

वेरिएबल-लेंथ कोड: Difference between revisions

Namespaces

More

Page actions

Revision as of 02:51, 17 July 2023

Contents

कोड और उनके एक्सटेंशन