Hubbry Logo
search
logo
Fibonacci coding avatar
Fibonacci coding
Fibonacci coding
current hub
F

Fibonacci coding

logo
Community Hub0 Subscribers
Read side by side
Fibonacci coding
View on Wikipedia
from Wikipedia
Part of a series on
Numeral systems
Place-value notation
Hindu–Arabic numerals
East Asian systems
Contemporary
Historic
Other systems
Ancient
Post-classical
Contemporary
By radix/base
Common radices/bases
Non-standard radices/bases
Sign-value notation
Non-alphabetic
Alphabetic
List of numeral systems

In mathematics and computing, Fibonacci coding is a universal code[1] which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

Definition

[edit]

For a number , if represent the digits of the code word representing then we have:

where F(i) is the ith Fibonacci number, and so F(i+2) is the ith distinct Fibonacci number starting with . The last bit is always an appended bit of 1 and does not carry place value.

It can be shown that such a coding is unique, and the only occurrence of "11" in any code word is at the end (that is, d(k−1) and d(k)). The penultimate bit is the most significant bit and the first bit is the least significant bit. Also, leading zeros cannot be omitted as they can be in, for example, decimal numbers.

The first few Fibonacci codes are shown below, and also their so-called implied probability, the value for each number that has a minimum-size code in Fibonacci coding.

Symbol Fibonacci representation Fibonacci code word Implied probability
1 11 1/4
2 011 1/8
3 0011 1/16
4 1011 1/16
5 00011 1/32
6 10011 1/32
7 01011 1/32
8 000011 1/64
9 100011 1/64
10 010011 1/64
11 001011 1/64
12 101011 1/64
13 0000011 1/128
14 1000011 1/128

To encode an integer N:

  1. Find the largest Fibonacci number equal to or less than N; subtract this number from N, keeping track of the remainder.
  2. If the number subtracted was the ith Fibonacci number F(i), put a 1 in place i − 2 in the code word (counting the left most digit as place 0).
  3. Repeat the previous steps, substituting the remainder for N, until a remainder of 0 is reached.
  4. Place an additional 1 after the rightmost digit in the code word.

To decode a code word, remove the final "1", assign the remaining the values 1,2,3,5,8,13... (the Fibonacci numbers) to the bits in the code word, and sum the values of the "1" bits.

Comparison with other universal codes

[edit]

Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a self-synchronizing code, making it easier to recover data from a damaged stream. With most other universal codes, if a single bit is altered, then none of the data that comes after it will be correctly read. With Fibonacci coding, on the other hand, a changed bit may cause one token to be read as two, or cause two tokens to be read incorrectly as one, but reading a "0" from the stream will stop the errors from propagating further. Since the only stream that has no "0" in it is a stream of "11" tokens, the total edit distance between a stream damaged by a single bit error and the original stream is at most three.

This approach, encoding using sequence of symbols, in which some patterns (like "11") are forbidden, can be freely generalized.[2]

Example

[edit]

The following table shows that the number 65 is represented in Fibonacci coding as 0100100011, since 65 = 2 + 8 + 55. The first two Fibonacci numbers (0 and 1) are not used, and an additional 1 is always appended.

Generalizations

[edit]

The Fibonacci encodings for the positive integers are binary strings that end with "11" and contain no other instances of "11". This can be generalized to binary strings that end with N consecutive 1s and contain no other instances of N consecutive 1s. For instance, for N = 3 the positive integers are encoded as 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. In this case, the number of encodings as a function of string length is given by the sequence of tribonacci numbers.

For general constraints defining which symbols are allowed after a given symbol, the maximal information rate can be obtained by first finding the optimal transition probabilities using a maximal entropy random walk, then using an entropy coder (with switched encoder and decoder) to encode a message as a sequence of symbols fulfilling the found optimal transition probabilities.

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Fibonacci coding

View on Grokipedia
from Grokipedia
Fibonacci coding is a universal binary coding scheme designed to encode positive integers using the Fibonacci number system, where each integer is represented as a unique sum of non-consecutive Fibonacci numbers according to Zeckendorf's theorem, resulting in a binary string with no adjacent 1s except for the terminating "11" pattern that ensures prefix-freeness.[1][2] The encoding process begins by finding the Zeckendorf representation of the integer n, which involves greedily selecting the largest Fibonacci number less than or equal to the remaining value without using consecutive terms, producing a bit string where 1s indicate used Fibonacci positions (starting from F_2 = 1). An additional 1 is appended to the end to form the terminating "11", making the code self-delimiting and allowing instantaneous decoding by scanning from the end until the first "11" is found, then summing the corresponding Fibonacci numbers for the preceding 1s.[1] For example, the number 3 (F_4 = 3) encodes as "0011", while 6 (F_5 + F_2 = 5 + 1) encodes as "10011".[3] This structure leverages the growth rate of Fibonacci numbers, providing code lengths that are asymptotically optimal for uniform distributions, with the length of the code for n being approximately the index of the largest Fibonacci number in its representation plus two bits.[1] Fibonacci coding finds primary applications in lossless data compression, particularly for encoding sequences of integers or symbols with varying frequencies, as it offers variable-length codes that reduce redundancy compared to fixed-length binary representations.[4] In compression scenarios, it achieves space savings of up to 56.5% for text data by assigning shorter codes to more frequent symbols based on their Fibonacci representations, outperforming simpler methods in certain noisy channel environments due to its error-detecting properties from the no-adjacent-1s rule.[4] Additionally, extensions like multidimensional or polynomial-based variants have been explored for advanced error correction in information theory.[5]

Fundamentals

Definition

Fibonacci coding is a universal binary encoding scheme for positive integers that leverages the Fibonacci number system to produce prefix-free codewords. Each positive integer NN is represented uniquely as a binary string corresponding to a sum of distinct non-consecutive Fibonacci numbers, where the codeword terminates with two consecutive 1s ("11") and contains no other adjacent 1s. This ensures the code is instantaneous, meaning no codeword is a prefix of another, facilitating efficient decoding without delimiters. The Fibonacci sequence employed in this coding starts with F2=1F_2 = 1, F3=2F_3 = 2, F4=3F_4 = 3, F5=5F_5 = 5, and generally Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n>3n > 3. This indexing shifts the conventional sequence (F1=1F_1 = 1, F2=1F_2 = 1) to align with the coding requirements, beginning the summation from F2F_2. Mathematically, a codeword of length k+1k+1 with bits d0,d1,…,dk−1,1d_0, d_1, \dots, d_{k-1}, 1—where each di∈{0,1}d_i \in \{0, 1\}, dk−1=1d_{k-1} = 1, and the final 1 is appended for termination—encodes N=∑i=0k−1diFi+2N = \sum_{i=0}^{k-1} d_i F_{i+2}. The appended 1 distinguishes the codeword while preserving the underlying representation. This scheme originates from Zeckendorf's theorem, which establishes the unique representation of any positive integer as a sum of non-consecutive Fibonacci numbers greater than or equal to F2F_2, and was adapted into a prefix-free universal code by Apostolico and Fraenkel in 1987.[6][7]

Relation to Zeckendorf Representation

Zeckendorf's theorem asserts that every positive integer can be uniquely expressed as a sum of distinct non-consecutive Fibonacci numbers, where "non-consecutive" means no two selected Fibonacci numbers have indices differing by 1.[7] This representation, known as the Zeckendorf representation, forms the foundation of Fibonacci coding by providing a binary-like encoding without adjacent 1s in the bit string corresponding to the coefficients of the Fibonacci basis.[6] The Fibonacci sequence used in this context is typically indexed as F1=1F_1 = 1, F2=1F_2 = 1, F3=2F_3 = 2, F4=3F_4 = 3, F5=5F_5 = 5, and so on, with Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n≥3n \geq 3.[7] The Zeckendorf representation of a positive integer NN employs Fibonacci numbers starting from F2=1F_2 = 1 (skipping F1=1F_1 = 1 to avoid redundancy), ensuring the sum uses non-adjacent terms such as FkF_k where the indices kk satisfy k≥2k \geq 2 and no two are consecutive.[7] The uniqueness of this representation follows from a key property of the Fibonacci sequence: for any n≥2n \geq 2, Fn+1>∑i=1n−1FiF_{n+1} > \sum_{i=1}^{n-1} F_i.[7] This inequality implies that the largest possible sum of non-consecutive Fibonacci numbers up to FnF_n is strictly less than Fn+1F_{n+1}, preventing ambiguities or "carry-over" issues similar to those in binary addition. To sketch the proof, suppose two different Zeckendorf representations sum to the same NN; let SS and TT be the sets of indices in each, and assume without loss of generality that the maximum index in SS exceeds that in TT. The difference in sums would then contradict the inequality, as the excess in SS cannot be compensated by smaller terms in TT without violating the non-consecutivity. Thus, the representations must coincide.[7] Fibonacci coding adapts the Zeckendorf representation to form a prefix-free code suitable for variable-length encoding of positive integers. Specifically, the bit string of the Zeckendorf representation (with 1s indicating selected Fibonacci numbers and 0s elsewhere, ordered from lowest to highest index) is modified by appending an extra 1 at the end.[6] This appendage creates a terminating sequence of "11" (since the original Zeckendorf string ends with a 1 followed by no adjacent 1, ensuring the prior bit is 0), which enforces the prefix property without introducing adjacent 1s elsewhere in the codeword. The resulting code is instantaneous and uniquely decodable, leveraging the inherent uniqueness of Zeckendorf while bounding error propagation in transmission.[6]

Encoding and Decoding

Encoding Algorithm

The encoding algorithm for Fibonacci coding generates a binary codeword for a given positive integer NN by leveraging the Zeckendorf representation, which uniquely expresses NN as a sum of non-consecutive Fibonacci numbers starting from F2=1F_2 = 1, F3=2F_3 = 2, F4=3F_4 = 3, and so on, where the sequence is defined by F1=1F_1 = 1, F2=1F_2 = 1, and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n>2n > 2. This greedy approach ensures the representation uses the largest possible Fibonacci number at each step without adjacent selections, as guaranteed by Zeckendorf's theorem.[8] The procedure begins by identifying the largest Fibonacci number Fk≤NF_k \leq N. The bit corresponding to position k−2k-2 (indexing bits from the lowest position 0 for F2F_2) is set to 1, and FkF_k is subtracted from NN to obtain the remainder. This process repeats on the remainder until it reaches 0, producing a bit string with no two consecutive 1s. To form the complete codeword, an extra 1 is appended to the end, ensuring the code ends with "11" for prefix-free decoding. The bit string is constructed with the lowest position (F_2) as the leftmost bit.[8] For edge cases, if N=1N = 1, the Zeckendorf representation uses F2=1F_2 = 1, yielding the bit string "1" followed by the appended 1, resulting in "11". For N=2N = 2, it uses F3=2F_3 = 2, with bits "01" (0 for F2F_2, 1 for F3F_3) followed by 1, giving "011".[8] The following pseudocode outlines the algorithm, assuming a precomputed list of Fibonacci numbers up to exceeding NN: 
function fibonacci_encode(N):
    if N == 0:
        return ""  // Not typically encoded, as coding starts from 1
    fibs = generate_fibonacci_up_to(N)  // List [F_2=1, F_3=2, F_4=3, ..., F_k] where F_k > N
    code = []
    i = len(fibs) - 1
    while i >= 0:
        if fibs[i] <= N:
            code.append(1)
            N -= fibs[i]
        else:
            code.append(0)
        i -= 1
    // code now has bits from high (F_k) to low (F_2)
    // Reverse to have low (F_2) first to high last
    code = code[::-1]
    // No lstrip, as leading 0s (low bits) are needed
    return ''.join(map(str, code)) + '1'
This greedy nature directly mirrors the Zeckendorf algorithm, producing the unique representation required for the code's completeness.[8]

Decoding Algorithm

The decoding of a Fibonacci codeword involves identifying the terminating "11" sequence, which delimits the end of the codeword due to the appended 1 during encoding.[9][10] The final 1 in this sequence is then discarded, as it functions solely as a delimiter to ensure prefix-free decoding.[9][10] In the remaining bit string, each 1 corresponds to a Fibonacci number, with positions interpreted from the least significant bit (leftmost) onward: the leftmost bit aligns with F2=1F_2 = 1, the next (to the right) with F3=2F_3 = 2, the following with F4=3F_4 = 3, and so on up to FkF_k for higher positions to the right.[9][10] The original integer NN is recovered by summing the Fibonacci numbers at these 1 positions.[9][10] This procedure exhibits a self-synchronizing property, allowing decoding to resume from any point in the bitstream by searching for the next "11" sequence, which confines desynchronization errors to at most one affected codeword.[10][9] For edge cases, the codeword "11" decodes to 1, as discarding the final 1 leaves a single bit "1" at the F2F_2 position.[10][9] Likewise, "011" decodes to 2, with the remaining "01" having its 1 at the F3F_3 position.[10][9] The algorithm's reliability stems from the prefix-free property enforced by the termination rule, which introduces the only instance of consecutive 1s in the codeword, preventing ambiguity since internal representations adhere to the no-adjacent-1s constraint of Zeckendorf's theorem.[9][10]

Properties and Analysis

Uniqueness and Completeness

The uniqueness of Fibonacci coding stems directly from Zeckendorf's theorem, which guarantees that every positive integer has a unique representation as a sum of distinct non-consecutive Fibonacci numbers, where the Fibonacci sequence is defined with F1=1F_1 = 1, F2=2F_2 = 2, and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n≥3n \geq 3.[11] In Fibonacci coding, this representation is converted to a binary string by placing 1s at positions corresponding to the selected Fibonacci numbers (starting from the least significant bit) and appending an extra 1 to terminate the codeword, preserving the uniqueness since no two different integers share the same Zeckendorf representation.[12] The appended 1 ensures the prefix-free property, meaning no valid codeword is a prefix of another, as every codeword ends with "11" while the no-adjacent-1s rule (inherited from the Zeckendorf representation) prevents any internal "11" sequence that could cause ambiguity during prefix detection.[11] This termination rule eliminates the possibility of one codeword being misinterpreted as the beginning of a longer one, guaranteeing instantaneous decodability without lookahead beyond the termination bits.[12] Completeness follows from the fact that Zeckendorf's theorem covers all positive integers exactly once, establishing a bijection between the positive integers and the set of valid Fibonacci codewords, with the appended 1 making the mapping prefix-free and thus suitable for concatenation in streams.[11] Fibonacci coding satisfies the Kraft inequality for uniquely decodable codes, where the sum over all codewords cic_i of 2−li≤12^{-l_i} \leq 1 (with lil_i the length of codeword cic_i) holds with equality, confirming that the code is complete and no additional codewords can be added without violating unique decodability.[6] Violations of the no-adjacent-1s rule, such as allowing consecutive 1s in the representation before termination, would introduce multiple possible Zeckendorf-like decompositions for the same integer, thereby breaking the uniqueness of the mapping and potentially leading to decoding ambiguities.[11]

Efficiency and Code Length

Fibonacci coding achieves codeword lengths that scale logarithmically with the value being encoded. The length of the codeword for a positive integer NN is O(log⁡ϕN)O(\log_\phi N), where ϕ=(1+5)/2≈1.618\phi = (1 + \sqrt{5})/2 \approx 1.618 is the golden ratio. Specifically, the codeword length is k+1k + 1, where kk is the index of the largest Fibonacci number Fk≤NF_k \leq N, and Fk+1≈NϕF_{k+1} \approx N \phi. This follows from the growth rate of the Fibonacci sequence, Fk≈ϕk/5F_k \approx \phi^k / \sqrt{5}, ensuring that the representation remains compact for large NN.[13] The average codeword length for uniformly distributed integers from 1 to NN is approximately log⁡ϕN+O(1)\log_\phi N + O(1) bits. This asymptotic expression accounts for the varying lengths across the range, with shorter codewords for smaller integers pulling the average below the maximum length. Additionally, the exact asymptotic density of ones in the codewords is 1/(ϕ2+1)≈0.2761/(\phi^2 + 1) \approx 0.276 per bit, reflecting the sparse nature of the Zeckendorf representation where no two consecutive ones appear in the coefficient bits (excluding the terminating one).[14] These properties contribute to the code's efficiency in representing sequences of integers without prior knowledge of their distribution.[13] Relative to information-theoretic bounds, for a uniform distribution over 1 to NN, the average codeword length is asymptotically (1/log⁡2ϕ)log⁡2N≈1.44log⁡2N(1 / \log_2 \phi) \log_2 N \approx 1.44 \log_2 N bits, compared to the entropy log⁡2N\log_2 N bits, resulting in redundancy of approximately 0.44log⁡2N0.44 \log_2 N bits per symbol. This factor arises because each codeword requires about log⁡ϕN\log_\phi N bits while the entropy is log⁡2N\log_2 N, yielding log⁡ϕN/log⁡2N=1/log⁡2ϕ\log_\phi N / \log_2 N = 1 / \log_2 \phi. The code's completeness and uniqueness ensure full coverage without gaps or overlaps.[13] Encoding and decoding in Fibonacci coding exhibit O(log⁡N)O(\log N) time complexity, achieved through precomputation of a table of Fibonacci numbers up to the required index, which takes O(log⁡N)O(\log N) space and time to build. The encoding process involves greedy selection of the largest possible Fibonacci number, while decoding scans the bitstream until the terminating "11" pattern, leveraging the no-adjacent-ones property for rapid synchronization. This linearithmic performance makes it practical for applications requiring variable-length integer encoding.[13]

Comparisons

With Unary and Binary Codes

Fibonacci coding offers significant advantages over unary coding for representing positive integers, particularly as values grow larger. Unary coding encodes the integer nn as a sequence of nn ones followed by a zero, yielding a codeword length of n+1n + 1 bits, which scales linearly and becomes impractical for even moderately large nn. In contrast, Fibonacci coding employs a variable-length, prefix-free scheme based on the Zeckendorf representation, achieving code lengths that grow logarithmically, approximately 1.44log⁡2(n+1)1.44 \log_2 (n + 1) bits on average. For instance, encoding 65 requires 66 bits in unary but only 10 bits in Fibonacci coding. Compared to standard binary coding, Fibonacci coding provides prefix-free encoding without needing additional delimiters or fixed block sizes, but at the cost of greater length. Binary representation of nn uses ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 bits in fixed-length form, which is optimal for known ranges but lacks the prefix property, necessitating extra bits for separation in variable-length contexts. Fibonacci codes, while inherently instantaneous and suitable for concatenation, incur about 44% more bits on average due to the inefficiency of the Fibonacci base ϕ≈1.618\phi \approx 1.618 versus base 2; for example, numbers up to 825 require 15 bits in Fibonacci versus 10 in binary. However, for small integers in fixed-width binary (e.g., 1 to 31), Fibonacci's variable lengths average 4.6 bits per number, outperforming 5-bit binary blocks. Key trade-offs highlight Fibonacci coding's niche: it eliminates the need for predefined block sizes or length prefixes, making it ideal for streaming unbounded integers, though the base-ϕ\phi overhead increases redundancy relative to binary's efficiency. Unary suits minimal values where linear growth is tolerable and decoding is trivial, binary excels with bounded ranges for minimal bits, and Fibonacci is preferred for prefix-free encoding of arbitrary positive integers without length metadata.

With Other Universal Codes

Fibonacci coding is often compared to other universal codes such as Elias gamma and exponential Golomb codes, highlighting differences in efficiency, implementation, and error handling. The Elias gamma code encodes a positive integer NN using a unary prefix of length ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1 followed by the binary representation of NN (omitting the leading 1), yielding an average code length of approximately 2log⁡2N+12 \log_2 N + 1 bits.[15] In contrast, Fibonacci coding leverages the Zeckendorf representation terminated by "11", resulting in code lengths of roughly log⁡ϕN+2\log_\phi N + 2 bits, where ϕ≈1.618\phi \approx 1.618 is the golden ratio; this makes Fibonacci codes shorter than Elias gamma for many values of NN, such as 11 bits for N=100N=100 versus 13 bits for Elias gamma.[16] However, Elias gamma benefits from simpler implementation relying on standard binary shifts and unary counting, whereas Fibonacci encoding requires Fibonacci number computations or tables.[17] Against exponential Golomb codes, which are parameterized (e.g., via parameter MM) for geometric distributions and encode NN as a quotient in unary followed by a binary remainder, Fibonacci coding offers parameter-free universality suitable for unknown distributions.[17] Benchmarks show Fibonacci codes achieving comparable or better compression for uniform integer data, such as disk access costs of 7,175 MB versus Golomb's 8,477 MB on random 6D datasets, though Golomb excels when the distribution matches its parameter.[17] A key strength of Fibonacci coding is its self-synchronization: the "11" terminator acts as a marker, confining bit errors or insertions/deletions to a single symbol and enabling quick resynchronization, unlike Elias gamma where misalignment can propagate errors across multiple codewords.[18] This prefix-free property allows instantaneous decoding without lookahead, a shared trait with other universal codes, but Fibonacci's no-adjacent-1s constraint (except at termination) reduces flexibility for highly non-uniform sources.[18] Overall, while optimal for representations in the Fibonacci number system, Fibonacci coding trades some efficiency for robustness, typically yielding 20-50% longer codewords than entropy-approaching adaptive methods like Huffman coding under uniform distributions (e.g., 10.6 bits versus 7 bits for integers up to 128).[18]

Examples and Illustrations

Basic Numerical Examples

To illustrate Fibonacci coding, consider the Zeckendorf representation, which expresses each positive integer as a unique sum of non-consecutive Fibonacci numbers starting from F2=1F_2 = 1, where the Fibonacci sequence is defined as F1=1F_1 = 1, F2=1F_2 = 1, and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n>2n > 2. The codeword is formed by writing the binary digits of this representation from lowest to highest Fibonacci index (left to right), ensuring no two consecutive 1s, and appending a final 1 to make the code prefix-free.[19] For N=1N = 1, the Zeckendorf representation is F2=1F_2 = 1. The binary bits are 1 (for F2F_2), and appending 1 yields the codeword "11". To decode, read until the ending "11", discard the last 1, and sum the remaining bits weighted by Fibonacci numbers starting from F2F_2 as the rightmost bit before the terminator: the bit for F2F_2 is 1, so 1⋅F2=11 \cdot F_2 = 1.[19] For N=2N = 2, the Zeckendorf representation is F3=2F_3 = 2. The binary bits are 01 (0 for F2F_2, 1 for F3F_3), and appending 1 yields "011". Decoding discards the last 1, leaving 01; the rightmost bit (before terminator) is for F3=1⋅2=2F_3 = 1 \cdot 2 = 2, and the next left is for F2=0F_2 = 0, summing to 2.[19] For N=3N = 3, the Zeckendorf representation is F4=3F_4 = 3. The binary bits are 001 (0 for F2F_2, 0 for F3F_3, 1 for F4F_4), and appending 1 yields "0011". Decoding leaves 001 after discarding the last 1; weights from right: F4=1⋅3=3F_4 = 1 \cdot 3 = 3, F3=0F_3 = 0, F2=0F_2 = 0, summing to 3.[19] A more involved example is N=65N = 65, with Zeckendorf representation F10+F6+F3=55+8+2F_{10} + F_6 + F_3 = 55 + 8 + 2. The binary bits from F2F_2 to F10F_{10} are 010010001 (0 for F2F_2, 1 for F3F_3, 0 for F4F_4, 0 for F5F_5, 1 for F6F_6, 0 for F7F_7, 0 for F8F_8, 0 for F9F_9, 1 for F10F_{10}), and appending 1 yields "0100100011". Decoding discards the last 1, leaving 010010001; weights from right: F10=1⋅55F_{10} = 1 \cdot 55, F9=0F_9 = 0, F8=0F_8 = 0, F7=0F_7 = 0, F6=1⋅8F_6 = 1 \cdot 8, F5=0F_5 = 0, F4=0F_4 = 0, F3=1⋅2F_3 = 1 \cdot 2, F2=0F_2 = 0, summing to 65.[19] For a step-by-step encoding of N=13N = 13 using the greedy algorithm from the encoding process: the largest Fibonacci number ≤13\leq 13 is F7=13F_7 = 13; subtract to get remainder 0, so the representation is F7=13F_7 = 13. The binary bits from F2F_2 to F7F_7 are 000001 (0 for F2F_2 to F6F_6, 1 for F7F_7), and appending 1 yields "0000011". Decoding leaves 000001, with weights from right: F7=1⋅13F_7 = 1 \cdot 13, others 0, summing to 13.[19]
Integer NNZeckendorf RepresentationCodewordDecoded Sum
1F2F_211F2=1F_2 = 1
2F3F_3011F3=2F_3 = 2
3F4F_40011F4=3F_4 = 3
13F7F_70000011F7=13F_7 = 13
65F3+F6+F10F_3 + F_6 + F_{10}01001000112+8+55=652 + 8 + 55 = 65

Visual Representation

Fibonacci coding can be visually represented through structured tables and diagrams that illustrate the mapping of positive integers to their binary codewords, highlighting the underlying Zeckendorf representations as sums of non-adjacent Fibonacci numbers. These visualizations emphasize the no-adjacent-1s property in the representation bits and the terminating "11" suffix, which ensures unique decodability.[7] The following table lists the codewords for the first 10 positive integers NN, along with their lengths and the corresponding Fibonacci components based on the Zeckendorf representation (using the Fibonacci sequence where F2=1F_2 = 1, F3=2F_3 = 2, F4=3F_4 = 3, F5=5F_5 = 5, F6=8F_6 = 8, etc.). The codeword bits (excluding the terminating 1) directly correspond to the coefficients for F2F_2 (leftmost) to higher terms (rightward before termination).[7]
NNCodewordLengthFibonacci Components
1112F2=1F_2 = 1
20113F3=2F_3 = 2
300114F4=3F_4 = 3
410114F4+F2=3+1F_4 + F_2 = 3 + 1
5000115F5=5F_5 = 5
6100115F5+F2=5+1F_5 + F_2 = 5 + 1
7010115F5+F3=5+2F_5 + F_3 = 5 + 2
80000116F6=8F_6 = 8
91000116F6+F2=8+1F_6 + F_2 = 8 + 1
100100116F6+F3=8+2F_6 + F_3 = 8 + 2
A diagram aligning bit positions with the Fibonacci sequence reveals the systematic placement of 1s in non-adjacent positions, corresponding to the selected Fibonacci numbers in the Zeckendorf sum. For instance, consider codewords up to N=7N=7, aligned by their terminating "11": 
N=1:  11                                    (F2:1 | term:1)
N=2: 011                                    (F2:0 F3:1 | term:1)
N=3: 0011                                   (F2:0 F3:0 F4:1 | term:1)
N=4: 1011                                   (F2:1 F3:0 F4:1 | term:1)
N=5: 00011                                  (F2:0 F3:0 F4:0 F5:1 | term:1)
N=6: 10011                                  (F2:1 F3:0 F4:0 F5:1 | term:1)
N=7: 01011                                  (F2:0 F3:1 F4:0 F5:1 | term:1)
       F2  F3  F4  F5
This alignment shows how 1s map to non-adjacent FiF_i indices, with the left-to-right order starting from the lowest F2F_2, ensuring the representation avoids consecutive 1s except at the termination.[7] The self-synchronization property of Fibonacci codes is illustrated by their ability to recover from bit errors in a concatenated stream, as the "11" suffix uniquely demarcates codeword boundaries and does not appear internally. Consider the stream for N=1,2,3N=1, 2, 3: 110110011. If a bit error flips the third bit (yielding 111110011), the decoder correctly decodes the first codeword as "11" to 1, but misdecodes the second as "11" to 1 (instead of 2), and the third as "10011" to 6 (instead of 3). This robustness allows decoding to continue after the error, with typically only a few codewords affected. Observing patterns across codewords, lengths increase incrementally with NN (e.g., groups of 2, 3, 5, 8 codewords at lengths 2 through 6, mirroring Fibonacci growth), while the density of 0s rises as higher FiF_i dominate, reflecting the sparse, non-adjacent 1s in Zeckendorf sums.

Generalizations

Multi-Bit Termination Variants

Multi-bit termination variants extend the standard Fibonacci coding scheme by requiring codewords to terminate with n consecutive 1s (where n > 2), while prohibiting any instance of n-1 or more consecutive 1s elsewhere in the codeword. This generalization maintains the core idea of representing positive integers using sums of non-adjacent Fibonacci numbers but adjusts the bit pattern constraints to accommodate the longer termination sequence, ensuring prefix-free decoding and unique representability. For n=3, the body avoids two or more consecutive 1s, similar to the standard case but with a terminating "111".[20] The encoding process begins with the Zeckendorf representation of the integer, which is a binary string with no two adjacent 1s corresponding to non-consecutive Fibonacci positions (using the convention where bits are ordered from lowest to highest Fibonacci number, left to right). To form the codeword, the termination is adjusted to end with n 1s, often by appending sufficient 1s to the representation while ensuring no internal violations. For example, the number 3, whose Zeckendorf representation is 001 (F_2=0, F_3=0, F_4=1), becomes 0011 for n=2 in standard coding; for n=3, a variant might use 0111 or adjusted representation to end with 111 without internal consecutive 1s exceeding limits. Decoding reverses this by locating the terminating n 1s from the end, discarding the extra n-1, and summing the Fibonacci values at the positions of the remaining 1s. These variants introduce greater redundancy compared to the standard n=2 case, increasing the average code length by roughly n-2 bits per codeword due to the extra terminating bits. However, this comes with improved error detection: the longer termination sequence allows detection of up to n-2 bit errors in the suffix, with the n=3 variant particularly effective at catching double errors that might flip bits and mimic shorter terminations. Additionally, the design enhances synchronization in concatenated code streams, as the distinct n-1 bit pattern before the end aids in rapid recovery from desynchronization errors.

Higher-Order Fibonacci-Like Sequences

Higher-order Fibonacci-like sequences generalize the standard Fibonacci sequence used in coding by employing recurrences involving more than two prior terms, enabling representations in bases greater than the golden ratio. For tribonacci coding, the underlying sequence is defined by the recurrence $ T_n = T_{n-1} + T_{n-2} + T_{n-3} $ for $ n > 3 $, with initial terms $ T_1 = 1 $, $ T_2 = 1 $, $ T_3 = 2 $, yielding subsequent values such as $ T_4 = 4 $, $ T_5 = 7 $, $ T_6 = 13 $, and so on. This sequence supports a Zeckendorf-like theorem, where every positive integer has a unique binary representation as a sum of distinct tribonacci numbers with no three consecutive 1s in the bit string.[21] The encoding process for tribonacci coding follows a greedy algorithm analogous to the Fibonacci case: to encode a positive integer $ N $, select the largest tribonacci number $ T_k \leq N $, set the corresponding bit to 1, subtract $ T_k $ from $ N $, and repeat until $ N = 0 $, ensuring no three consecutive 1s. The resulting bit string, which may end with up to two consecutive 1s but never three, is then terminated by appending bits to form exactly three consecutive 1s at the end (adjusting for the ending pattern to avoid longer internal runs). This ensures the code is prefix-free and instantaneously decodable, as the pattern 111 signals the end of a codeword without appearing elsewhere. For example, the number 5 can be represented as $ T_4 + T_2 = 4 + 1 $, corresponding to the bit string 101 (T_4=1, T_3=0, T_2=1, higher to lower), appended with 11 to yield 10111, ending with 111 (incorporating the final body 1). In the general k-bonacci coding for $ k \geq 2 $, the sequence satisfies the k-term recurrence $ Z_n = Z_{n-1} + Z_{n-2} + \cdots + Z_{n-k} $ for $ n > k $, with $ Z_1 = 1 $ and $ Z_i = 0 $ for $ i \leq 0 $, producing sequences like the Fibonacci for $ k=2 $ and tribonacci for $ k=3 $. A generalized Zeckendorf theorem holds under these conditions, guaranteeing unique representations without k consecutive 1s. Encoding proceeds greedily, selecting terms with at most k-1 consecutive, and terminates by appending bits to create exactly k consecutive 1s at the end, with adjustments to prevent internal k-runs. This approach can be combined with multi-bit termination variants for adjusted ending patterns.[21] Higher k values yield an effective base approaching the real root of the characteristic equation $ x^k = x^{k-1} + \cdots + x + 1 $, approximately 1.839 for k=3 and 1.928 for k=4, allowing shorter code lengths for large integers compared to binary or standard Fibonacci coding. However, the increased complexity arises from enforcing no k consecutive 1s, which demands more stringent greedy selection and decoding logic, though it remains optimal for certain power-law distributions with exponents around the base value.

Applications

In Data Compression

Fibonacci coding serves as a universal prefix code for encoding positive integers in lossless data compression schemes, particularly effective for sequences of monotonically increasing values such as run-lengths in run-length encoding (RLE) or indices in metadata structures. By representing integers via the Zeckendorf theorem—expressing each number as a sum of non-consecutive Fibonacci numbers without adjacent 1s in the binary codeword—it enables self-delimiting variable-length codes that minimize redundancy for sparse or small-integer data. This makes it suitable as a building block in hybrid compressors, where it encodes lengths or positions efficiently before further processing.[8] In wavelet-based image compression, Fibonacci coding has been proposed as a static alternative to more complex entropy coders for algorithms like SPIHT (Set Partitioning in Hierarchical Trees) to compress quantized discrete wavelet transform (DWT) coefficients or refinement bits, particularly for significance maps and sparse coefficient trees.[22] Historical applications emerged in the 1980s, with Apostolico and Fraenkel introducing Fibonacci representations for variable-length integer coding in early compression contexts, influencing subsequent lossless schemes for unbounded integer streams.[8] Performance-wise, Fibonacci coding excels in reducing bit usage for sparse datasets following Zipf-like distributions, such as word frequencies in text or run lengths in images, yielding low redundancy close to the theoretical entropy limit and often outperforming some Elias codes in non-uniform sources, while supporting fast decoding via table-driven methods. It is frequently combined with Huffman coding in hybrid approaches to enhance adaptability, where Fibonacci handles integer components and Huffman addresses symbol probabilities, as seen in text and numerical metadata compression. Recent studies as of 2024 have explored multidimensional variants for improved compression in sequential data streams.[23] However, its static nature limits efficacy on highly non-uniform or evolving sources, necessitating pairing with adaptive estimators or dynamic codes to maintain optimal compression ratios across diverse inputs.

In Error-Resilient Coding

Fibonacci coding exhibits strong error-resilience properties due to its self-synchronizing nature, which enables rapid recovery from bit errors during data transmission. In the event of a bit flip, insertion, or deletion, the decoder can resynchronize by identifying the next occurrence of the "11" termination pattern, limiting the impact to at most one or two subsequent symbols rather than causing indefinite propagation across the stream, as seen in non-self-synchronizing variable-length codes like Huffman or Elias gamma.[24] This bounded error propagation ensures that a single corrupted codeword affects only the corresponding symbol, preserving the integrity of the remaining data sequence.[24] These synchronization features make Fibonacci coding particularly suitable for noisy communication channels, such as early digital radio systems where clock regeneration is essential without a dedicated clock signal, and in wireless sensor networks prone to intermittent interference.[25] It has been integrated into forward error correction (FEC) schemes, including block codes designed to correct double-burst errors by leveraging Fibonacci representations to detect and isolate error patterns within fixed-length channels.[26] For instance, in bursty error environments, the code's structure allows for straightforward error localization using the Fibonacci basis, enhancing overall transmission reliability without excessive redundancy.[26] In modern applications, Fibonacci-inspired coding extends to DNA storage systems, where ensembles of sequences restricted by Fibonacci-like rules improve minimum distance metrics, thereby boosting resilience against read errors like insertions or substitutions during sequencing.[27] Such restrictions yield critical distance fractions as high as 0.62 for certain ensembles, enabling higher fidelity in noisy biochemical channels compared to unconstrained random codes.[27]
User Avatar
No comments yet.