वेरिएबल-लेंथ कोड

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

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

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

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

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

औपचारिक भाषा सिद्धांत से शब्दों का उपयोग करते हुए, स्पष्ट गणितीय परिभाषा इस प्रकार है: मान ले की $S$ और $T$ दो परिमित समुच्चय होता है, जिन्हें क्रमशः स्रोत और लक्ष्य वर्णमाला कहा जाता है। संकेतवाली $C:S\to T^{*}$ संपूर्ण कार्य होता है जो प्रत्येक प्रतीक $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}$ पर फिर पिछले अनुभाग से विचार करें। यह कोड विशिष्ट रूप से डिकोड करने योग्य नहीं होते है, क्योंकि स्ट्रिंग 011101110011 की व्याख्या कोडवर्ड 01110 - 1110 - 011 के अनुक्रम के रूप में की जा सकती है, लेकिन कोडवर्ड 011 - 1 - 011 - 10011 के अनुक्रम के रूप में भी की जा सकती है। इस एन्कोडेड स्ट्रिंग के दो संभावित डिकोडिंग सीडीबी और बेब द्वारा दिए गए हैं। यघपि , ऐसा कोड तब उपयोगी होता है जब सभी संभावित स्रोत प्रतीकों का समूह पूरी तरह से ज्ञात और सीमित होता है, या जब प्रतिबंध होते हैं (उदाहरण के लिए औपचारिक वाक्यविन्यास) जो यह निर्धारित करते हैं कि इस एक्सटेंशन के स्रोत तत्व स्वीकार्य हैं या नहीं। इस तरह के प्रतिबंध मूल संदेश को डिकोड करने की अनुमति देते हैं, यह जांच कर कि समान प्रतीक पर मानचित्रित किए गए संभावित स्रोत प्रतीकों में से कौन सा उन प्रतिबंधों के अनुसार मान्य होता है।

उपसर्ग कोड

Main article: उपसर्ग कोड

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

• उदाहरण मानचित्रण $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 बिट प्रति प्रतीक होती है, यह कोड स्रोत को यथासंभव संपीड़ित करता है जिससे स्रोत को शून्य त्रुटि के साथ पुनर्प्राप्त किया जा सकता है।

यह भी देखें

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

अग्रिम पठन

• 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