एलियास गामा कोडिंग
एलियास कोड या एलियास गामा कोड पीटर एलियास द्वारा विकसितएक सार्वभौमिक कोड एन्कोडिंग सकारात्मक पूर्णांक है।[1]: 197, 199 इसका उपयोग सबसे अधिक तब किया जाता है जब पूर्णांक कोडिंग होती है जिनके ऊपरी-बाध्य को पहले से निर्धारित नहीं किया जा सकता है।
एनकोडिंग
किसी संख्या को x ≥ 1 कोड करने के लिए:
- मान लीजिए कि इसमें 2 की उच्चतम शक्ति है, इसलिए 2एन ≤ x <2एन+1 है।
- फिर शून्य बिट्स लिखें
- के बाइनरी रूप को जोड़ें, एक बाइनरी संख्या।
उसी प्रक्रिया को व्यक्त करने का एक समकक्ष तरीका:
- यूनरी में को एनकोड करें; यही है, जैसे कि शून्य के बाद एक है।
- के शेष द्विआधारी अंकों को के इस प्रतिनिधित्व के लिए में जोड़ें।
एक संख्या का प्रतिनिधित्व करने के लिए , इलियास गामा (γ) बिट्स का उपयोग करता है। [1]: 199
कोड शुरू होता है (कोड के लिए निहित संभाव्यता वितरण स्पष्टता के लिए जोड़ा जाता है):
Number | Binary | γ encoding | Implied probability |
---|---|---|---|
1 = 20 + 0 | 1 |
1 |
1/2 |
2 = 21 + 0 | 1 0 |
0 1 0 |
1/8 |
3 = 21 + 1 | 1 1 |
0 1 1 |
1/8 |
4 = 22 + 0 | 1 00 |
00 1 00 |
1/32 |
5 = 22 + 1 | 1 01 |
00 1 01 |
1/32 |
6 = 22 + 2 | 1 10 |
00 1 10 |
1/32 |
7 = 22 + 3 | 1 11 |
00 1 11 |
1/32 |
8 = 23 + 0 | 1 000 |
000 1 000 |
1/128 |
9 = 23 + 1 | 1 001 |
000 1 001 |
1/128 |
10 = 23 + 2 | 1 010 |
000 1 010 |
1/128 |
11 = 23 + 3 | 1 011 |
000 1 011 |
1/128 |
12 = 23 + 4 | 1 100 |
000 1 100 |
1/128 |
13 = 23 + 5 | 1 101 |
000 1 101 |
1/128 |
14 = 23 + 6 | 1 110 |
000 1 110 |
1/128 |
15 = 23 + 7 | 1 111 |
000 1 111 |
1/128 |
16 = 24 + 0 | 1 0000 |
0000 1 0000 |
1/512 |
17 = 24 + 1 | 1 0001 |
0000 1 0001 |
1/512 |
डिकोडिंग
एलियास गामा-कोडित पूर्णांक को डीकोड करने के लिए:
- स्ट्रीम से 0 को पढ़ें और गिनें जब तक आप पहले 1 तक नहीं पहुंच जाते। शून्य की इस गिनती को N कहते हैं।
- 2N के मान के साथ, पूर्णांक के पहले अंक तक पहुंचने वाले अंक को ध्यान में रखते हुए, पूर्णांक के शेष N अंकों को पढ़ें।
उपयोग
गामा कोडिंग का उपयोग उन अनुप्रयोगों में किया जाता है जहां सबसे बड़ा एन्कोडेड मान समय से पहले ज्ञात नहीं होता है, या डेटा को संपीड़न करने के लिए जिसमें छोटे मान बड़े मूल्यों की तुलना में बहुत अधिक होते हैं।
गामा कोडिंग एलियास डेल्टा कोड में एक बिल्डिंग ब्लॉक है।
सामान्यीकरण
गामा कोडिंग शून्य या नकारात्मक पूर्णांकों कोड नहीं करती है। शून्य को संभालने का एक तरीका कोडिंग से पहले 1 जोड़ना और फिर डिकोडिंग के बाद 1 घटाना है। एक अन्य तरीका प्रत्येक नॉनज़ीरो कोड को 1 के साथ उपसर्ग करना है और फिर कोड शून्य को एकल 0 के रूप में जोड़ना है।
सभी पूर्णांकों को कोड करने का एक तरीका कोडिंग से पहले (1, 2, 3, 4, 5, 6, 7, ...) के लिए एक बीज, मानचित्रण पूर्णांक (0, −1, 1, −2, 2, −3, 3, ...) सेट करना है। सॉफ़्टवेयर में, यह गैर-नकारात्मक इनपुट को विषम आउटपुट में मैप करके और यहां तक कि आउटपुट में नकारात्मक इनपुट को मैप करके सबसे आसानी से किया जाता है, इसलिए कम से कम महत्वपूर्ण बिट एक उल्टा संकेत बिट बन जाता है:
घातीय-गोलोम्ब कोडिंग गामा कोड को एक चापलूसी पावर-लॉ वितरण के साथ पूर्णांकों में सामान्यीकृत करती है, जैसे गोलोम्ब कोडिंग यूनरी कोड को सामान्यीकृत करती है। इसमें संख्या को एक सकारात्मक विभाजक से विभाजित करना सम्मिलित है, आमतौर पर 2 की शक्ति, भागफल से एक अधिक के लिए गामा कोड लिखना और शेष को एक साधारण बाइनरी कोड में लिखना।
यह भी देखें
- एलियास डेल्टा (δ) कोडिंग
- एलियास ओमेगा (ω) कोडिंग
- सकारात्मक (संख्या प्रारूप)
संदर्भ
- ↑ 1.0 1.1 Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.
अग्रिम पठन
- Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Lossless Compression Handbook. Elsevier. ISBN 978-0-12-620861-0.