फाइबोनैचि कोडिंग

गणित और कंप्यूटिंग में फाइबोनैचि कोडिंग एक यूनिवर्सल कोड के रूप में डेटा संपीड़न है जो धनात्मक पूर्णांकों को बाइनरी कोड शब्दों में कूटबद्ध करता है। यह फाइबोनैचि संख्याओं के आधार पर पूर्णांकों के प्रतिनिधित्व के रूप में एक उदाहरण है। प्रत्येक कोड शब्द 11 के साथ समाप्त होता है और इसमें अंत से पहले 11 का कोई अन्य उदाहरण नहीं होता है।

फाइबोनैचि कोड ज़ेकेंडोर्फ प्रतिनिधित्व के रूप में निकटता से संबंधित है, एक स्थितीय अंक प्रणाली जो ज़ेकेंडोर्फ के प्रमेय के रूप में उपयोग करता है और इसमें यह गुण होता है कि किसी भी संख्या का प्रतिनिधित्व लगातार 1s के रूप में नहीं होता है। किसी विशेष पूर्णांक के लिए फाइबोनैचि कोड शब्द वास्तव में पूर्णांक का ज़ेकेंडोर्फ प्रतिनिधित्व है जिसके अंकों का क्रम उलटा होता है और इसमें अंत में एक अतिरिक्त "1" जोड़ दिया जाता है।

परिभाषा

एक नंबर के लिए $N\!$, यदि $d(0),d(1),\ldots ,d(k-1),d(k)\!$ प्रतिनिधित्व करने वाले कोड शब्द के अंकों को निरूपित करते हैं और इस प्रकार $N\!$ के रूप में होते है

$N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!$

जहाँ F(i) है iवें फाइबोनैचि संख्या है और इसी प्रकार F(i+2) iवीं विशिष्ट फाइबोनैचि संख्या से प्रारंभ होती है $1,2,3,5,8,13,\ldots$. अंतिम बिट $d(k)$ यह निरंतर 1 का एक संलग्न बिट के रूप में होता है और इसमें स्थानीय मान नहीं होता है।

यह दिखाया जा सकता है कि ऐसी कोडिंग अद्वितीय होती है और किसी भी कोड शब्द में 11 की एकमात्र घटना अंत में होती है अर्थात d(k−1) और d(k) अंतिम बिट सबसे महत्वपूर्ण बिट के रूप में होता है और पहला बिट सबसे कम महत्वपूर्ण बिट होता है। इसके अतिरिक्त अग्रणी शून्यों को छोड़ा नहीं जा सकता है, जैसा कि उदाहरण के रूप में दशमलव संख्या में कर सकते हैं।

पहले कुछ फाइबोनैचि कोड नीचे दिखाए गए हैं और उनके तथाकथित यूनिवर्सल कोड डेटा संपीड़न व्यावहारिक संपीड़न के रूप में होते है और प्रत्येक संख्या का मान जिसमें फाइबोनैचि कोडिंग में न्यूनतम रचना कोड के रूप में होते है।

प्रतीक	फाइबोनैचि प्रतिनिधित्व	फाइबोनैचि कोड शब्द	निहित संभावना
1	$F(2)$	11	1/4
2	$F(3)$	011	1/8
3	$F(4)$	0011	1/16
4	$F(2)+F(4)$	1011	1/16
5	$F(5)$	00011	1/32
6	$F(2)+F(5)$	10011	1/32
7	$F(3)+F(5)$	01011	1/32
8	$F(6)$	000011	1/64
9	$F(2)+F(6)$	100011	1/64
10	$F(3)+F(6)$	010011	1/64
11	$F(4)+F(6)$	001011	1/64
12	$F(2)+F(4)+F(6)$	101011	1/64
13	$F(7)$	0000011	1/128
14	$F(2)+F(7)$	1000011	1/128

किसी पूर्णांक N को सांकेतिक शब्दों में एन्कोड किया जाता है,

1. N के समतुल्य या उससे कम की सबसे बड़ी फाइबोनैचि संख्या ज्ञात करते है और इस प्रकार शेषफल के N ट्रैक ध्यान रखते है और संख्या को घटाते है।
2. यदि घटाई गई संख्या 1वीं फाइबोनैचि संख्या F(i) के रूप में होती है, तो कोड शब्द में i−2 के स्थान पर 1 रखते है और सबसे बाएं अंक को 0 के रूप में गिनें जाते है।
3. N के लिए शेषफल प्रतिस्थापित करते हुए पिछले चरणों को दोहराते है, जब तक कि शेषफल 0 के रूप में नहीं पहुंच जाता है।
4. कोड शब्द में सबसे दाहिने अंक के बाद एक अतिरिक्त 1 लगाते है।

किसी कोड शब्द को डिकोड करने के लिए अंतिम 1 को लगाते है और शेष मानों 1,2,3,5,8,13... को कोड शब्द में बिट्स के रूप में निर्दिष्ट करते है और फाइबोनैचि संख्या 1 के मानों का योग करते है.

अन्य यूनिवर्सल कोड के साथ तुलना

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

यह दृष्टिकोण प्रतीकों के अनुक्रम का उपयोग करके एन्कोडिंग के रूप में कुछ पैटर्न होते है, जैसे 11 निषिद्ध को स्वतंत्र रूप से सामान्यीकृत किया जा सकता है।

उदाहरण

निम्न तालिका से पता चलता है कि संख्या 65 को फाइबोनैचि कोडिंग में 0100100011 के रूप में दर्शाया गया है, क्योंकि 65 = 2 + 8 + 55. पहले दो फाइबोनैचि संख्याओं 0 और 1 का उपयोग नहीं किया जाता है और एक अतिरिक्त 1 निरंतर जोड़ा जाता है।

${\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}$

सामान्यीकरण

धनात्मक पूर्णांकों के लिए फाइबोनैचि एन्कोडिंग बाइनरी स्ट्रिंग के रूप में हैं, जो 11 के साथ समाप्त होती हैं और जिसमें "11" का कोई अन्य उदाहरण नहीं होता है। इसे बाइनरी स्ट्रिंग्स के लिए सामान्यीकृत किया जा सकता है, जो N क्रमागत 1 के साथ समाप्त होता हैं और इसमें क्रमागत N 1 का कोई अन्य उदाहरण नहीं होता है। उदाहरण के लिए, N = 3 के लिए धनात्मक पूर्णांकों को 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, .. के रूप में एन्कोड किया गया है। इस मामले में, स्ट्रिंग की लंबाई के एक फलन के रूप में एन्कोडिंग की संख्या ट्राइबोनैचि संख्याओं के अनुक्रम द्वारा दी गई है।

किसी दिए गए प्रतीक के बाद कौन से प्रतीकों की अनुमति है, इसे परिभाषित करने वाली सामान्य बाधाओं के लिए अधिकतम एन्ट्रॉपी यादृच्छिक प्रक्रिया का उपयोग करके पहले इष्टतम ट्रांजीशन संभावनाओं को ढूंढकर अधिकतम सूचना दर प्राप्त की जा सकती है, फिर एक संदेश को एनकोड करने के लिए एन्ट्रापी कोडर डिकोडर के साथ स्विच किए गए एनकोडर के साथ का उपयोग कर सकते है और इष्टतम ट्रांजीशन संभावनाओं को पूरा करने वाले प्रतीकों का अनुक्रम किया जा सकता है.

यह भी देखें

• स्वर्णिम अनुपात आधार
• नेगाफाइबोनैचि कोडिंग
• ओस्ट्रोवस्की संकेत पद्धति
• यूनिवर्सल कोड (डेटा संपीड़न)
• वेरीकोड , एक प्रायोगिक अनुप्रयोग
• ज़ेकेंडोर्फ का प्रमेय
• अधिकतम एन्ट्रापी यादृच्छिक प्रक्रिया

संदर्भ

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 105. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Robust universal complete codes for transmission and compression". Discrete Applied Mathematics. 64 (1): 31–55. CiteSeerX 10.1.1.37.3064. doi:10.1016/0166-218X(93)00116-H. ISSN 0166-218X. Zbl 0874.94026.

अग्रिम पठन

• Stakhov, A. P. (2009). The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science. Singapore: World Scientific Publishing.