Fibonacci Encoding

I recently learned this cool encoding in my info theory class and wanted to share.

As a forewarning, I am a student still learning and write this as a way of processing the information as I learn it. None of this is peer-reviewed. My writing here may (and likely will) have mistakes.

Lets dive in though! First let us consider representations for a number $n$. There is a greedy algorithm to produce a representation for any number given placeholders. Lets assume we have the placeholders

To represent $n$ we

1. Find the largest $P_i$ such that $P_i \leq n$
2. Find the largest $c_i \in \mathbb{N}$ such that $c_iP_i \leq n$
3. Put $c_i$ in position $i$
4. $n \leftarrow n - c_iP_i$ and repeat (i.e subtract $n$ by $c_iP_i$ and go back to step 1)

For example given $n = 60$ and typical binary placeholders $2^{i-1}$ for $P_i$, which are

We then step through the algorithm getting the highest placeholder $P_6 = 32$, which we can multiply by at most $1$. This gives us a $1$ in position 6. $n$ then becomes $n = 60 - 32 = 28$. We then get $P_5 = 16$, with $c_6 = 1$, and $n$ becomes $n = 28 - 16 = 12$. We then do this again with $P=4$ and $P=3$ to give us:

$P_6$	$P_5$	$P_4$	$P_3$	$P_2$	$P_1$
1	1	1	1	0	0

For the base representations we always have that $c_i < d$ for some $d$-ary base since the greedy algorithm would pick the larger placeholder. This is because for a $d$-ary base, $d \dot P_i = P_{i+1}$.

Now let us consider $\vec{P}$ placeholders to be fibonacci. That is we start at $P_1 = 1$, then $P_2 = 2$ (to make sure we have that subsequent $P$ are strictly greater then previous ones), $P_3 = 3$, $P_4 = 5$, and so on following that $P_{i+2} = P_{i+1} + P_i$

That same number $n = 60$ would be represented as

$55$	$34$	$21$	$13$	$8$	$5$	$3$	$2$	$1$
1	0	0	0	0	1	0	0	0

In fibonacci representation. This representation has two important properties

(1) Fibonacci representations only contains 0s and 1s. Why?

Thus, for all placeholders, since multiplying by two is always greater than the next placeholder, the greedy algorithm would have us pick that placeholder rather than multiply by 2.

(2) Fibonacci representations will never have consecutive $1$s. This is because the greedy algorithm will choose the biggest possible placeholder. Thus we would always have $100$ instead of $011$.

The second property is how we will leverage this to construct fibonacci encodings, allowing us to encode a stream of integers of unknown length. We do this by

1. Creating the fibonacci representation
2. Reversing the order (i.e. least significant bit to most)
3. Adding a trailing 1.

Going back to our $n = 60$ example, the representation of $10001000$ would then be reversed to $000100001$ and then a trailing $1$ is added to get us the encoding of $0001000011$.

We essentially encode in the base of the ratio between numbers, in this case we are encoding in the golden ratio $\phi \sim 1.618$. Thus to encode $n$ we need roughly $log_\phi n$ bits.

This is roughly $\frac{log_\phi n}{lg n} \sim 1.44$ times more bits than in binary. However this encoding allows us to send an arbitrary amount of $n$ at a time, with a way of punctuating between numbers (something called a universal code).

The robustness of fibonacci comes from the fact that by flipping a bit in the stream, we mess up at most 2 numbers. Contrary to other encoding schemes like Lempel-Ziv, Elias Gamma, Elias Delta, and Elias Omega, flipping one bit has some robustness, and is able to preserve the majority of the stream of integers.

Lastly, although not planned, is the ability to convert units rather easily in this representation. Specifically from kilometers to miles and centimeters to inches. The ratio of kilometers to miles is roughly $1.61$, in other words there are $1.61$ kilometers in a mile; Therefore, we can shift a bit to the left to convert from miles to kilometers.

$1 0 0$ ($3$) miles becomes $1 0 0 0$ ($5$) kilometers.

The ratio between centimeters to inches is roughly $2.54$, and since $1.61 \cdot 1.61$ is roughly $2.56$, we can a bit shift twice to convert between the two.

$1 0 0$ ($3$) inches becomes $1 0 0 0$ ($8$) centimeters.

This is purely a coincidence due to the fact that the ratios between these units are close to (or close to a power of) the golden ratio $1.61$.