Negafibonacci coding explained

In mathematics, negafibonacci coding is a universal code which encodes nonzero 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.

Encoding method

The following steps describe how to encode a nonzero integer

. Note that

denotes the Negafibonacci sequence.

is positive, compute the greatest odd negative integer

such that the sum of the odd negative terms of the Negafibonacci sequence from -1 to

with a step of -2, is greater than or equal to

n\in\{-\left(2k+1\right),k\in[0,infty[\},

	n-2
\sum
	i=-1, i odd

f(i)<x\leq

	n
\sum
	i=-1, i odd

f(i).

is negative, compute the greatest even negative integer

such that the sum of the even negative terms of the Negafibonacci sequence from 0 to

with a step of -2, is less than or equal to

n\in\{-2k,k\in[2,infty[\},

	n-2
\sum
	i=-2, i even

f(i)>x\geq

	n
\sum
	i=-2, i even

f(i)

Add a 1 at the

|n|^th

bit of the binary word. Subtract

f(n)

from

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.

Negafibonacci representation

Negafibonacci coding 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.

Table

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

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

References

Works cited

Knuth . Donald . 2008 . Negafibonacci Numbers and the Hyperbolic Plane . Annual meeting of the Mathematical Association of America . San Jose, California.
Book: Knuth, Donald . The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams . 2009 . Addison-Wesley . 978-0-321-58050-4. In the pre-publication draft of section 7.1.3 see in particular pp. 36–39.
Book: Margenstern, Maurice . Cellular Automata in Hyperbolic Spaces . Archives contemporaines . 2008 . 9782914610834 . Advances in unconventional computing and cellular automata . 2 . 79.