Negafibonacci coding: Difference between revisions

Revision as of 14:34, 21 February 2020

Latest revision as of 16:25, 12 July 2025

(14 intermediate revisions by 6 users not shown)

Line 1:

In [[mathematics]], '''negaFibonaccinegafibonacci coding''' is a [[universal code (data compression)|universal code]] which encodes nonzero integers into binary [[Code word (communication)|code word]]s. It is similar to [[Fibonacci coding]], except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.

{{Refimprove|date=January 2018}}

{{numeral systems}}

In [[mathematics]], '''negaFibonacci coding''' is a [[universal code (data compression)|universal code]] which encodes nonzero integers into binary [[code word]]s. It is similar to [[Fibonacci coding]], except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.

== Encoding method ==

The Fibonacci code is closely related to ''negaFibonacci representation'', a positional [[numeral system]] sometimes used by mathematicians. The negaFibonacci code for a particular nonzero integer is exactly that of the integer's negaFibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end. The negaFibonacci code for all negative numbers has an odd

number of digits, while those of all positive numbers have an even number of digits.

The following steps describe how to encode a nonzero integer <math> x </math>. Note that <math> f </math> denotes the Negafibonacci sequence.

==Encoding method==

To encode a nonzero integer ''X'':

# Calculate the largest (or smallest) encodeable number with ''N'' bits by summing the odd (or even) [[negafibonacci]] numbers from 1 to ''N''.

# When it is determined that ''N'' bits is just enough to contain ''X'', subtract the ''Nth'' negaFibonacci number from ''X'', keeping track of the remainder, and put a one in the ''Nth'' bit of the output.

# Working downward from the ''Nth'' bit to the first one, compare each of the corresponding negaFibonacci numbers to the remainder. Subtract it from the remainder if the absolute value of the difference is less, AND if the next higher bit does not already have a one in it. A one is placed in the appropriate bit if the subtraction is made, or a zero if not.

# Put a one in the ''N+1th'' bit to finish.

# If <math> x </math> is positive, compute the greatest odd negative integer <math> n </math> such that the sum of the odd negative terms of the Negafibonacci sequence from −1 to <math> n </math> with a step of −2, is greater than or equal to <math> x </math>: <br /> <math> n \in \{ - \left( 2k + 1 \right) , k \in [0, \infty [ \} , \quad \sum_{i=-1, \; i \; odd}^{n-2} f(i) < x \leq \sum_{i=-1, \; i \; odd}^{n} f(i). </math> <br /> If <math> x </math> is negative, compute the greatest even negative integer <math> n </math> such that the sum of the even negative terms of the Negafibonacci sequence from 0 to <math> n </math> with a step of −2, is less than or equal to <math> x </math>: <br /> <math> n \in \{ - 2k , k \in [2, \infty [ \} , \quad \sum_{i=-2, \; i \; even}^{n-2} f(i) > x \geq \sum_{i=-2, \; i \; even}^{n} f(i) </math>

To decode a token in the code, remove the last "1", assign the remaining bits the values 1, −1, 2, −3, 5, −8, 13… (the [[negafibonacci]] numbers), and add the "1" bits.

# Add a 1 at the <math> |n|^{\text{th}} </math> bit of the binary word. Subtract <math> f(n) </math> from <math> x </math>.

# Repeat the process from step 1 with the new value of ''x'', until it reaches 0.

# Add a 1 on the left of the resulting binary word to finish the encoding.

To decode an encoded binary word, remove the leftmost 1 from the binary word, since it is used only to denote the end of the encoded number. Then assign the remaining bits the values of the Negafibonacci sequence from −1 (1, −1, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

==Table==

== Negafibonacci representation ==

<!--[[Negafibonacci representation redirects here; please update the redirect if this section is retitled, split, or moved.-->

{{numeral systems}}

TheNegafibonacci Fibonacci codecoding is closely related to ''negaFibonacci'negafibonacci representation''', a positional [[numeral system]] sometimes used by mathematicians. The negaFibonaccinegafibonacci code for a particular nonzero integer is exactly that of the integer's negaFibonaccinegafibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end. The negaFibonaccinegafibonacci code for all negative numbers has an odd number of digits, while those of all positive numbers have an even number of digits.

== Table ==

The code for the integers from −11 to 11 is given below.

{| class="wikitable"

|-

!numberNumber

!negaFibonacciNegafibonacci representation

!negaFibonacciNegafibonacci code

|-

| −11 ||101000 ||0001011

Line 71 ⟶ 74:

|}

== See also ==

* [[Fibonacci numbers]]

* [[Golden ratio base]]

* [[Zeckendorf's theorem]]

== References ==

{{No footnotes|date=September 2022}}

*{{citation|last=Knuth|first=Donald|title=Negafibonacci Numbers and the Hyperbolic Plane|publisher=Paper presented at the annual meeting of the Mathematical Association of America, San Jose, California|year=2008}}.

{{Reflist}}

*{{citation|last=Knuth|first=Donald|title=[[The Art of Computer Programming]], Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams|year=2009|isbn=0-321-58050-8}}. In the [https://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz pre-publication draft of section 7.1.3] see in particular pp. 36–39.

*{{citation|title=Cellular Automata in Hyperbolic Spaces|volume=2|series=Advances in unconventional computing and cellular automata|first=Maurice|last=Margenstern|publisher=Archives contemporaines|year=2008|isbn=9782914610834|page=79|url=https://books.google.com/books?id=eEgvfic3A4kC&pg=PA79}}.

=== Works cited ===

{{Refbegin}}

* {{citationCite conference |last=Knuth |first=Donald |year=2008 |title=Negafibonacci Numbers and the Hyperbolic Plane |publisherconference=Paper presented at the annualAnnual meeting of the Mathematical Association of America, |___location=San Jose, California|year=2008}}.

* {{citationCite book |last=Knuth |first=Donald |title=[[The Art of Computer Programming]], Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams |year=2009 |publisher=Addison-Wesley |isbn=978-0-321-58050-84}}. In the [https://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz pre-publication draft of section 7.1.3] see in particular pp. &nbsp;36–39.

* {{Cite book |last=Margenstern |first=Maurice |url=https://books.google.com/books?id=eEgvfic3A4kC&pg=PA79 |title=Cellular Automata in Hyperbolic Spaces |publisher=Archives contemporaines |year=2008 |isbn=9782914610834 |series=Advances in unconventional computing and cellular automata |volume=2 |page=79}}

{{Refend}}

{{Compression Methods}}

Line 86 ⟶ 96:

[[Category:Lossless compression algorithms]]

[[Category:Fibonacci numbers]]

[[Category:Data compression]]

[[fr:Codage de Fibonacci]]