जब आप अद्वितीय रूप से डिकोड कर सकते हैं?

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

उपसर्ग-मुक्त स्थिति

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

उदाहरण उपसर्ग-मुक्त कोड {s1, s2, s3, s4} के लिए: s1 = 0, s2 = 10, s3 = 110, s4 = 111।

सत्यापित करें: 0 10, 110, या 111 का उपसर्ग नहीं है। 10 110 या 111 का उपसर्ग नहीं है (10 के बाद अधिक बिट्स 100... या 101... देते हैं, जिनमें से कोई भी 110 या 111 से शुरू नहीं होता है)। कोड योग्य है।

डिकोडिंग प्रक्रिया: ट्री का अनुसरण करें, प्रत्येक आने वाले बिट पर शाखा करें, जब आप एक पत्ती से टकराएं तो प्रतीक उत्सर्जित करें, रूट पर वापस जाएं।

Kraft असमानता

किसी भी उपसर्ग-मुक्त बाइनरी कोड के लिए कोडवर्ड लंबाई l_1, l_2, ..., l_n के साथ:

Σ 2^(−l_i) ≤ 1

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

Kraft असमानता लागू करना

कोडवर्ड लंबाई को देखते हुए, Kraft को सत्यापित करें: Σ 2^(−l_i) ≤ 1।

{s1=0, s2=10, s3=110, s4=111} के लिए: लंबाई 1, 2, 3, 3 हैं।

Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1। ✓

Shannon एन्ट्रॉपी

एक परिवर्तनीय-लंबाई कोड की औसत कोड लंबाई: L = Σ p_i · l_i, जहां p_i प्रतीक s_i की संभावना है और l_i इसकी कोड लंबाई है।

L कितना छोटा हो सकता है? Shannon का उत्तर: स्रोत एन्ट्रॉपी से कम नहीं।

Shannon एन्ट्रॉपी: H = −Σ p_i · log₂(p_i) (इकाई: बिट्स/प्रतीक)

एन्ट्रॉपी प्रत्येक प्रतीक के औसत सूचना को मापता है। उच्च एन्ट्रॉपी का मतलब है कि प्रतीक लगभग समान रूप से संभावित हैं (अधिकतम अप्रत्याशितता)। कम एन्ट्रॉपी का मतलब है कि कुछ प्रतीक प्रबल हैं (उच्च पूर्वानुमेयता, अधिक संपीड़ित)।

शोरहीन कोडिंग प्रमेय

किसी भी उपसर्ग-मुक्त कोड के लिए, H(स्रोत) ≤ L ≤ H(स्रोत) + 1।

कोई भी कोड एन्ट्रॉपी को हरा नहीं सकता। Huffman कोडिंग (अगला अध्याय) ऊपरी सीमा को प्राप्त करता है: L < H + 1। n प्रतीकों पर ब्लॉक कोड के लिए, सीमा सख्त होती है: H ≤ L/n < H + 1/n।

एन्ट्रॉपी सैद्धांतिक संपीड़न सीमा भी है: आप सूचना खोए बिना किसी स्रोत को H बिट्स प्रति प्रतीक से कम में संपीड़ित नहीं कर सकते।

एन्ट्रॉपी की गणना करना

उदाहरण: 4 प्रतीक संभावनाओं के साथ p = [1/2, 1/4, 1/8, 1/8]।

H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)

= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3

= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 बिट्स/प्रतीक

और Huffman कोड {0, 10, 110, 111} L = 1.75 = H को बिल्कुल प्राप्त करता है।

एन्ट्रॉपी क्यों एक निचली सीमा है

शोरहीन कोडिंग प्रमेय की निचली सीमा केवल एक सूत्र नहीं है - यह सूचना के बारे में कुछ गहरा दर्शाता है: आप जो पहले से ही अधिकतम अप्रत्याशित है उसे संपीड़ित नहीं कर सकते।

जब सभी प्रतीक समान रूप से संभावित हों (समान वितरण), एन्ट्रॉपी H = log₂(n) n प्रतीकों के लिए। log₂(n) बिट्स की ब्लॉक कोड बिल्कुल H को प्राप्त करता है। कोई भी कोड बेहतर नहीं कर सकता।

जब एक प्रतीक प्रबल हो (कहो, p(A) = 0.99, p(B) = 0.01), H छोटा है - 0 के करीब। एक परिवर्तनीय-लंबाई कोड A को बहुत संक्षिप्त कोड निर्दिष्ट कर सकता है, धारा को बहुत कुशलता से एन्कोड कर सकता है।

व्यावहारिक निष्कर्ष: बड़े संपीड़न लाभ केवल तब मौजूद होते हैं जब प्रतीक संभावनाएं काफी भिन्न होती हैं। यदि स्रोत पहले से 'समान' है (यादृच्छिक दिखता है), Huffman कोडिंग कुछ नहीं हासिल करता है।