|
== Encoding method ==
The following steps describe how to encode a nonzero integer ''<math> x'' </math>. Note that ''<math> f'' </math> denotes the Negafibonacci sequence.
# 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−1 to ''<math> n'' </math> with a step of -2−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−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>
# 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 aton the beginningleft of the resulting binary word to finish the encoding.
To decode aan tokenencoded in thebinary codeword, remove the lastleftmost "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... (the negafibonacci numbers), and addsum the "1"all bitsthe values associated with a 1.
== Negafibonacci representation ==
[[Category:Lossless compression algorithms]]
[[Category:Fibonacci numbers]]
[[Category:Data compression]]
[[fr:Codage de Fibonacci]]
| 