I'm studying compression and coding, and we learnt about $n$-Fibonacci codes. I understand how to construct $n$-Fibonacci code, but I can't figure out which code is better (e.g $2$-Fibonacci vs $3$-Fibonacci).
Intuitively I think that $2$-Fibonacci is better because it uses fewer bits. Is it correct? Are there any other advantages for $3$-Fibonacci?
Thanks,
The most efficient Fibonacci coding depends on the text you want to encode. Assuming you want to send $m$ binary strings with $n$ bits, the standard Finacci coding produces an output of approximately $(1.44042 n+4)m $ bits, while the Fibonacci $3$-coding produces an output of approximately $(1.13747n+5)m$ bits, so the most efficient coding depends on $n$ being $\geq 3.3$ on average or not.
The Fibonacci $2$-coding uses more bits than the Fibonacci $3$-coding, but it has a shorter separator ($0110$ versus $01110$). Namely the additive base for the Fibonacci $2$-coding is $1,2,3,5,8,13,21,34,55,89,\ldots$ while the additive base for the Fibonacci $3$-coding is $1,2,3,6,11,20,37,68,\ldots$, so if we want to send $100;101$ through the Fibonacci $2$-coding we send $1000010100\color{blue}{0110}1000010101$, if we want to send $100;101$ through the Fibonacci $3$-coding we send $10110001\color{blue}{01110}10110010$, which is shorter.