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

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

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

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

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

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

औपचारिक भाषा सिद्धांत से शब्दों का उपयोग करते हुए, सटीक गणितीय परिभाषा इस प्रकार है: चलो $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: Prefix code

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

• उदाहरण मानचित्रण $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