Fibonacci coding: compact by construction

Fibonacci coding represents positive integers as sums of non-consecutive Fibonacci numbers and uses a terminator to make the stream decodable. The mechanism is compact; the representation contract is the real subject.

The encoder derives the Zeckendorf representation: a unique sum of non-consecutive Fibonacci numbers. Bits mark the selected basis values, and an additional terminal one produces the only adjacent-one pair in a valid codeword. The decoder can therefore stream until it sees 11. That elegant delimiter still needs explicit bit order, integer domain, basis indexing, overflow behavior, and concatenation rules.

Small primitives deserve the same discipline as large systems: a precise problem statement, an implementation sketch, known test vectors, and failure cases that fit on one screen.

Property tests should round-trip a dense prefix of positive integers and a randomized high range. Boundary tests cover one, consecutive basis transitions, the largest representable value, truncated streams, an unterminated word, impossible internal 11 pairs, and arithmetic overflow while accumulating the result. A reference implementation can prioritize transparency while a production variant proves the same vectors under optimized bit I/O.

Compression details look minor until they become protocol. Then ambiguity, framing, and malformed input are architecture.

The universal code is prefix-free, not magically self-authenticating. A corrupted bit can change one integer and resynchronize later, or it can shift the semantic structure expected by the surrounding protocol. The container still needs length budgets, count limits, integrity protection where required, and a decoder that rejects resource-exhaustion inputs before allocation. Compactness never removes the need for an adversarial parser.