NegaFibonacci coding

From Wikipedia, the free encyclopedia

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic Eastern Arabic Khmer	Indian family Brahmi Thai
East Asian numerals
Chinese Japanese	Korean
Alphabetic numerals
Abjad Armenian Cyrillic Ge'ez	Hebrew Ionian/Greek Sanskrit
Other systems
Attic Etruscan Urnfield Roman	Babylonian Egyptian Mayan
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64
3, 9, 12, 24, 30, 36, 60, more…
v • d • e

In mathematics, negaFibonacci coding is a universal code which encodes integers into binary code words. 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. 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 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:

Find the largest negafibonacci number with a value equal to or less than X; subtract this number from X, keeping track of the remainder.
If the number we subtracted was the Nth unique negaFibonacci number, put a one in the Nth digit of our output.
Repeat the previous steps, substituting our remainder for X, until we reach a remainder of 0.
Place a one after the last naturally-occurring one in our output.

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