Why does every codeword end in 11?

The final data bit is one, and the appended one creates the delimiter; the valid data portion has no adjacent ones.

Can one integer have several valid nonconsecutive representations?

Under the stated Fibonacci weights and constraints, the representation is unique.

Does Fibonacci coding always compress better than binary?

No. Bare binary needs boundary information, but complete fixed-width or other variable-length formats can still be shorter for a particular workload.

AI Glossary / MLOps and deployment / Intermediate

Fibonacci coding

Definition

Fibonacci coding is a self-delimiting representation of positive integers based on Fibonacci numbers. It expresses an integer as a sum of nonconsecutive Fibonacci values, writes the corresponding selection bits, and appends a final one. The resulting codeword ends in 11, a pattern that does not occur earlier within that codeword.

What it means

The coding sequence uses weights 1, 2, 3, 5, 8, 13 and so on, avoiding the duplicated initial one sometimes used when listing Fibonacci numbers. Each weight is the sum of the two preceding weights. A positive integer has a unique representation as a sum of nonconsecutive weights in this sequence. That constraint supplies a useful delimiter: the data portion has no adjacent ones, so an extra one after its final selected weight creates an identifiable ending.

How it works

To encode, find the largest Fibonacci weight no greater than the integer, select it, subtract it and continue with the remainder while respecting the nonconsecutive representation. Write selection bits from the smallest weight up to the largest selected weight, then append a one. To decode, read until the first adjacent pair of ones. The second one terminates the code; the preceding bits specify which weights to add. The basic scheme represents positive integers, so zero or signed values require a separately defined mapping.

Three practical examples

A compression researcher compares Fibonacci and Elias codes for streams of positive counts.
An educational parser uses the distinctive 11 ending to demonstrate how variable-length integers can be separated without external commas.
A specialist format experiment examines how codeword boundaries behave after damaged bits, while still using separate integrity checks rather than treating the code as error correction.

Think of it this way

Think of making an amount using a special set of coin values while forbidding neighboring coin sizes from appearing together. A final marker then signals that the selection is complete. The analogy captures the sum representation but not ordinary currency behavior: real coins can usually repeat, whereas this coding representation uses each selected Fibonacci weight at most once.

Worked example

Encode 10 using weights 1, 2, 3, 5 and 8. The nonconsecutive sum is 8 + 2. In ascending weight order, the selection bits are 0, 1, 0, 0, 1, giving 01001. Append one to obtain 010011. The decoder stops at the final 11, discards its second one as the terminator, and sums the selected weights 2 + 8 = 10. For 1, the selection bit is 1 and the appended terminator produces 11. These bits are read in ascending weight order, unlike the usual left-to-right display of positional binary numbers.

Illustrative case study

Fictional case: Willow Storage builds a classroom binary format for positive event counts. The team initially writes the Fibonacci selection bits in descending weight order, which breaks the intended delimiter rule. It corrects the ordering and adds test vectors for 1, 2, 3, 4 and 10. It also specifies how many counts appear in each record and how padding is handled. The case illustrates specification and testing, not a production storage claim.

Common misconceptions and mistakes

Do not confuse Fibonacci coding with writing ordinary binary and adding 11. The constrained Fibonacci representation is what makes the ending meaningful. Do not use both initial ones from a conventional Fibonacci list as separate weights. The basic code does not directly encode zero. Also, a recognizable delimiter is not proof that damaged data can be restored: corruption can create or remove apparent boundaries. Error detection and recovery requirements should be evaluated separately from coding efficiency.

Business use

For businesses, this is mainly a specialist data-representation concept. It can be useful when comparing simple universal integer codes or reading an existing format. Evaluate actual code lengths on representative values, decoder speed and compatibility. A distribution dominated by one or two values may favor another representation, and large blocks may favor packing methods. Preserve bit ordering, integer mapping and framing rules so archived data can be decoded by another implementation.

Check your understanding

Decode 0011 using weights 1, 2, 3 and the standard stopping rule.

Answer: The final one is the terminator, leaving selection bits 001. Only the weight 3 is selected, so the decoded value is 3.

Related terms

Elias omega coding
Synchronization
Zeckendorf representation
universal integer code
prefix-free code
self-delimiting code

Learn next

Encode integers 1 through 12 and check that the first adjacent pair of ones always ends the codeword. Concatenate three examples and decode them without visual separators. Then compare total bit counts with gamma coding on an actual frequency table rather than judging from a single chosen value.

Sources

Primary research reference: Allison, Konagurthu and Schmidt, On Universal Codes for Integers: Wallace Tree, Elias Omega and Variations, https://arxiv.org/html/1906.05004v1 . Primary research full-text page opened and the Fibonacci discussion located; complete convention-specific and editorial review remain pending. Worked examples state the weight sequence and bit order explicitly.

Previous: FFT solver Next: Fibonacci search technique