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

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

एन्कोडिंग विधि

एक गैर-शून्य पूर्णांक X को एन्कोड करने के लिए:

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

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

नेगाफाइबोनैचि प्रतिनिधित्व

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

तालिका

-11 से 11 तक के पूर्णांकों का कोड नीचे दिया गया है।

Number	Negafibonacci representation	Negafibonacci code
−11	101000	0001011
−10	101001	1001011
−9	100010	0100011
−8	100000	0000011
−7	100001	1000011
−6	100100	0010011
−5	100101	1010011
−4	1010	01011
−3	1000	00011
−2	1001	10011
−1	10	011
0	0	(cannot be encoded)
1	1	11
2	100	0011
3	101	1011
4	10010	010011
5	10000	000011
6	10001	100011
7	10100	001011
8	10101	101011
9	1001010	01010011
10	1001000	00010011
11	1001001	10010011

यह भी देखें

• फाइबोनैचि संख्याएँ
• स्वर्णिम अनुपात आधार
• ज़ेकेंडोर्फ का प्रमेय

संदर्भ

उद्धृत कार्य

• Knuth, Donald (2008). नेगाफाइबोनैचि संख्याएँ और हाइपरबोलिक तल. Annual meeting of the Mathematical Association of America. San Jose, California.
• Knuth, Donald (2009). कंप्यूटर प्रोग्रामिंग की कला, खंड 4, फ़ासिकल 1: बिटवाइज़ ट्रिक्स और तकनीकें; द्विआधारी निर्णय आरेख. ISBN 978-0-321-58050-4. अनुभाग 7.1.3 के पूर्व-प्रकाशन ड्राफ्ट में विशेष पृष्ठ 36-39 देखें।
• Margenstern, Maurice (2008). हाइपरबोलिक स्पेस में सेलुलर ऑटोमेटा. Advances in unconventional computing and cellular automata. Vol. 2. Archives contemporaines. p. 79. ISBN 9782914610834.

श्रेणी:गैर-मानक स्थितीय अंक प्रणाली श्रेणी:दोषरहित संपीड़न एल्गोरिदम श्रेणी:फाइबोनैचि संख्याएँ

fr:कोडेज डी फाइबोनैचि