{ "id": "epd9yxxdyn", "slug": "fibonacci-coding", "title": "Fibonacci coding", "updated": "2026-10-15", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.number", "label": "Numbers and algebra", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.number" }, { "id": "physical.math.number.number-theory", "label": "Number theory", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.number.number-theory" }, { "id": "physical.math.number.computational-number-theory", "label": "Computational and probabilistic number theory", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.number.computational-number-theory" } ], "geo": [ { "id": "geo.weu.t1000.physical.math.number.number-theory", "label": "Western Europe · 1000 to 1799: Number theory", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000.physical.math.number.number-theory", "path": [ { "id": "geo.weu", "label": "Western Europe", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu" }, { "id": "geo.weu.t1000", "label": "Western Europe · 1000 to 1799", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000" }, { "id": "geo.weu.t1000.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000.physical" }, { "id": "geo.weu.t1000.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000.physical.math" }, { "id": "geo.weu.t1000.physical.math.number", "label": "Numbers and algebra", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000.physical.math.number" }, { "id": "geo.weu.t1000.physical.math.number.number-theory", "label": "Number theory", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.weu.t1000.physical.math.number.number-theory" } ] } ], "excerpt": "Fibonacci coding, also called the Gopala-Hemachandra code, is a universal, prefix-free code for positive integers that uses the Zeckendorf representation and ends each codeword with the pair 11.", "snippet": "Fibonacci coding, also called the Gopala-Hemachandra code, is a universal, prefix-free code for positive integers that uses the Zeckendorf representation and ends each codeword with the pair 11.", "node": "physical.math.number.computational-number-theory", "markdown": "# Fibonacci coding\n\n**Fibonacci coding** is a universal, prefix-free code for positive integers in which each number is written as its Zeckendorf representation, the unique decomposition of the integer into a sum of non-consecutive [Fibonacci](https://www.edgepedia.org/fibonacci) numbers, with the digits reversed and an extra 1 appended as a terminator[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf) • [2](https://arxiv.org/abs/1008.3202). Because no valid representation contains two consecutive 1s, the terminating pair \"11\" marks the end of every codeword, making the code self-delimiting without any length field[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf).\n\n| Key fact | Detail |\n|---|---|\n| Construction | Codeword for an integer is its Zeckendorf representation with digit order reversed and an additional \"1\" appended[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf) |\n| Self-delimiting | No codeword contains \"11\" except the final pair, so codewords can be concatenated and decoded without separators[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf) |\n| Length growth | The Zeckendorf representation uses roughly \\( \\log_{\\phi} n \\) Fibonacci numbers, so codeword length grows approximately logarithmically in the value encoded[3](https://metafunctor.com/post/2023-04-fibonacci-wire-formats/) |\n| Mean lengths | Average codeword length is 2.0 bits for the integer 1, 3.5 for 2–3, 4.8 for 4–7, 6.4 for 8–15, 7.9 for 16–31, 9.2 for 32–63, and 10.6 for 64–127[4](https://paperzz.com/doc/9057061/11_chapter-3) |\n| Robustness | An error is localized and contained within a codeword rather than corrupting the whole stream[4](https://paperzz.com/doc/9057061/11_chapter-3) • [5](https://www.sciencedirect.com/science/article/pii/0166218X9300116H) |\n| Distribution-free | The code is fixed and universal; it need not be regenerated for each probability distribution, unlike Huffman codes[5](https://www.sciencedirect.com/science/article/pii/0166218X9300116H) |\n| Alternate name | The Fibonacci universal code is also called the Gopala-Hemachandra code[6](https://arxiv.org/abs/cs/0701085) |\n\n## How the code works\n\n[Zeckendorf's theorem](https://www.edgepedia.org/zeckendorfs-theorem) states that every positive integer can be written uniquely as a sum of non-consecutive Fibonacci numbers[2](https://arxiv.org/abs/1008.3202). For example, 10 = 8 + 2, which selects the Fibonacci numbers F(6) and F(3) and gives the representation 100010 (reading positions from the largest Fibonacci number down). Reversing the digits of the Zeckendorf representation 10010 and appending a final 1 yields the Fibonacci codeword 010011[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf) • [13](https://pmc.ncbi.nlm.nih.gov/articles/PMC4707848/).\n\nDecoding reads bits until two consecutive 1s appear. The final 1 of that pair is the appended terminator, and the preceding bits, read in reverse, are the Zeckendorf digits; summing the Fibonacci numbers at the marked positions recovers the integer. This is why the code is prefix-free: no codeword's interior can contain \"11\", so the first occurrence of \"11\" always ends the current codeword[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf).\n\nThe smallest Fibonacci numbers used in the representation are 1, 2, 3, 5, 8, and so on; the code represents the positive integers, and the codeword for 1 is the shortest, at 2 bits[4](https://paperzz.com/doc/9057061/11_chapter-3).\n\n## Universal codes and where Fibonacci fits\n\nA universal code for the positive integers can store or compress a sequence of integers without prior knowledge of their distribution; every universal code implies a probability distribution over the integers, which is a reasonable default when the true distribution is unknown[7](https://arxiv.org/abs/1906.05004). Within this family, codeword length grows roughly as \\( \\log n \\) for the n-th symbol under the code's implied prior. Elias gamma minimizes expected length for power-law distributions, while delta and omega extend the recursion for heavier tails[3](https://metafunctor.com/post/2023-04-fibonacci-wire-formats/).\n\nMeasured against the Elias codes, Fibonacci coding trades some compression at the low end for robustness and simplicity. A comparison of mean codeword lengths shows Elias gamma ahead for small values: gamma uses 1 bit for the integer 1 and 3 bits for 2–3, against 2.0 and 3.5 for Fibonacci, and if even half of the values fall in the range 1 to 7 the gamma code wins by a wide margin[4](https://paperzz.com/doc/9057061/11_chapter-3). On an English-language text source, however, the Fibonacci code achieved a mean codeword length of 4.928 bits per word, an efficiency of \\( \\eta = H/L = 4.184/4.928 = 84.90\\% \\), an improvement over the Elias-gamma and delta codes at 79.83%[8](https://ndl.ethernet.edu.et/bitstream/123456789/48236/1/10.pdf).\n\n## Robustness against errors\n\nThe property that distinguishes Fibonacci codes in practice is error containment. Because each codeword ends at the first \"11\", a corrupted bit tends to damage only the codeword it falls in, localizing and containing the error, whereas in codes without this structure errors can propagate[4](https://paperzz.com/doc/9057061/11_chapter-3). A systematic study of robustness measures for variable-length codes led Dov Apostolico, professor of computer science, and [Abraham Lempel](https://www.edgepedia.org/abraham-lempel) to propose new universal and complete sequences of variable-length codewords based on representing integers in a binary Fibonacci numeration system[5](https://www.sciencedirect.com/science/article/pii/0166218X9300116H). Their paper frames these codes as alternatives to Huffman codes when optimal compression is not required and simplicity, faster processing, and robustness are preferred; each sequence is constant and need not be generated for every probability distribution[5](https://www.sciencedirect.com/science/article/pii/0166218X9300116H).\n\nThis robustness has limits in larger systems. If a Fibonacci-coded stream sits inside a larger container, the upper level loses synchronization anyway, and most adaptive methods cannot recover from errors whether or not they are detected; even in LZ77 errors can propagate far into the decoded output[4](https://paperzz.com/doc/9057061/11_chapter-3).\n\n## Faster decoding and variants\n\nEarly Fibonacci decoding was bit-by-bit, which kept variable-length codes out of data-processing applications where decompression speed matters. Fast decoding algorithms for Elias-delta and for Fibonacci codes of order 2 and order 3 were later introduced, all based on a finite automaton with precomputed mapping tables, with automaton-reduction techniques to keep the tables small[9](https://www.sciencedirect.com/science/article/abs/pii/S0020025511003033). The same work introduced the Elias–Fibonacci code, which has a lower compression ratio than the Fibonacci of order 3 code for lower numbers but decodes faster than the other codes tested; Elias–Fibonacci codewords are shorter than the compared codes for numbers longer than 26 bits[9](https://www.sciencedirect.com/science/article/abs/pii/S0020025511003033).\n\nHigher-order Fibonacci codes generalize the construction by using numeration systems built on other recurrences, and variations on the Fibonacci universal code, also called the Gopala-[Hemachandra](https://www.edgepedia.org/hemachandra) code, have been proposed for applications in source coding as well as cryptography[6](https://arxiv.org/abs/cs/0701085). The Fibonacci family is described as probably the most famous flag-pattern strategy for universal coding of integers[1](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf).\n\n## Applications\n\nFibonacci coding suits data dominated by small integers, since its shortest codewords cover the smallest values[10](https://arxiv.org/abs/0712.0811). In seismic instrumentation, analysis of recorded geophysical data showed a large spread in the probability of instrument readings during seismic activity; applying Fibonacci codes to this information produced a gain in compression ratio of 10–30% relative to other coding methods, while the coding algorithms were chosen for minimal demands on the processor and, consequently, on power consumption in autonomous computer-based systems[11](https://www.researchgate.net/publication/226637397_Comparison_of_variable-length_codes_Elias_and_Fibonacci_codes_as_applied_to_problems_of_data_compression).\n\n## References\n\n1. [Raso, Tesi di dottorato, Università di Roma (Fibonacci family of codes and Zeckendorf construction)](https://iris.uniroma1.it/retrieve/0b2e5a82-d995-46aa-b20a-defe01f13654/Tesi_dottorato_Raso.pdf)\n2. [From Fibonacci Numbers to Central Limit Type Theorems, arXiv:1008.3202](https://arxiv.org/abs/1008.3202)\n3. [Fibonacci Coding, metafunctor (2023)](https://metafunctor.com/post/2023-04-fibonacci-wire-formats/)\n4. [Data compression thesis chapter 3, comparison of delta, gamma and Fibonacci codes](https://paperzz.com/doc/9057061/11_chapter-3)\n5. [Apostolico & Lempel, Robust universal complete codes for transmission and compression, Discrete Applied Mathematics 64(1):31–55, 1996](https://www.sciencedirect.com/science/article/pii/0166218X9300116H)\n6. [Variations on the Fibonacci Universal Code, arXiv:cs/0701085](https://arxiv.org/abs/cs/0701085)\n7. [Allison, Konagurthu & Schmidt, On Universal Codes for Integers: Wallace Tree, Elias Omega and Variations, arXiv:1906.05004](https://arxiv.org/abs/1906.05004)\n8. [Classical and Quantum Information Theory (text, Table 8.3)](https://ndl.ethernet.edu.et/bitstream/123456789/48236/1/10.pdf)\n9. [Fast decoding algorithms for variable-length codes, Information Processing Letters / ScienceDirect](https://www.sciencedirect.com/science/article/abs/pii/S0020025511003033)\n10. [The Fast Fibonacci Decompression Algorithm, arXiv:0712.0811](https://arxiv.org/abs/0712.0811)\n11. [Kaloshin, Bashkirev & Burmin, Comparison of variable-length codes: Elias and Fibonacci codes as applied to problems of data compression, Seismic Instruments 45(1):86–89, 2009](https://www.researchgate.net/publication/226637397_Comparison_of_variable-length_codes_Elias_and_Fibonacci_codes_as_applied_to_problems_of_data_compression)\n12. [Penerapan Algoritma Fibonacci Code Pada File Transfer Berbasis Android, JIMAT](https://www.hostjournals.com/jimat/article/view/109)\n13. [pmc.ncbi.nlm.nih.gov](https://pmc.ncbi.nlm.nih.gov/articles/PMC4707848/)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Computational and probabilistic number theory*\n\n*Initially written Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/fibonacci-coding", "markdown_url": "https://www.edgepedia.org/fibonacci-coding.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Fibonacci coding\", Edgepedia (EdgeChat), https://www.edgepedia.org/fibonacci-coding. Edgepedia Community License 1.0.", "credit_md": "\"[Fibonacci coding](https://www.edgepedia.org/fibonacci-coding)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/fibonacci-coding](https://www.edgepedia.org/fibonacci-coding). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Fibonacci coding\", Edgepedia (EdgeChat), https://www.edgepedia.org/fibonacci-coding. Edgepedia Community License 1.0.", "speakable": "Fibonacci coding, also called the Gopala-Hemachandra code, is a universal, prefix-free code for positive integers that uses the Zeckendorf representation and ends each codeword with the pair 11." }