In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, negaFibonacci coding is a universal code

Universal code (data compression)

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...

 which encodes integers into binary code word

Code word

In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning...

s. It is similar to Fibonacci coding

Fibonacci coding

In mathematics, Fibonacci coding is a universal code which encodes positive integers into binary code words. Each code word ends with "11" and contains no other instances of "11" before the end.-Definition:...

, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end. The code for the integers from -11 to 11 is given below.

xx 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 01
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

The Fibonacci code is closely related to negaFibonacci representation, a positional numeral system

Numeral system

A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....

 sometimes used by mathematicians. The negaFibonacci code for a particular 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.

To encode an integer X:

1. Calculate the largest (or smallest) encodeable number with N bits by summing the odd (or even) negafibonacci numbers from 1 to N.
2. 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.
3. 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.
4. Put a one in the N+1th bit to finish.

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.

See also

• Golden ratio base
  Golden ratio base
  Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary...
  
  
• Zeckendorf's theorem
  Zeckendorf's theorem
  Zeckendorf's theorem, named after Belgian mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers....