Fibonacci coding - Definition and Overview

The Fibonacci code is a universal code which encodes positive integers into binary code words. All tokens end with "11" and have no "11" before the end. The code begins as follows:

1  11
2  011
3  0011
4  1011
5  00011
6  10011
7  01011
8  000011
9  100011
10 010011
11 001011
12 101011

Fibonacci Representation

To convert an integer x to its Fibonacci representation:

1. Replace x with the difference between x and the largest Fibonacci number less than or equal to x and let the output be 1
2. If the previous (next smaller) Fibonacci number is less than or equal to x, replace x with the difference, and append 1 to the output. Else, append 0 to the output. Repeat this step until the Fibonacci number 1 is encountered.

This method guarantees that there are no consecutive 1's in the Fibonacci representation of any number.

Encoding

To encode an integer x as little-endian:

1. Convert x to its Fibonacci representation
2. Change the representation to little endian and append a 1 after the last 1

Example: 46 -> 10010101 -> 10101001 -> 101010011 To encode an integer x as big-endian:

1. Convert x to its Fibonacci representation
2. Remove the leading 10 and appending a trailing 011

Example: 46 -> 10010101 -> 010101 -> 010101011