Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have read this wiki article but it seems not very clear to me. Why should we ever use fibonacci coding in data compression if even regular binary coding always gives better results? I mean, it seems that for any given number fibonacci codeword is actually longer than binary codeword. So what are the properties of fibonacci coding that make it useful?

P.S. Sorry if it's a dumb question.

UPD. I have an assumption that binary coding does not have a separator, so the code must be splited in some fixed-length blocks, while fibonacci coding does have a separator which makes it a variable-length coding. Please correct me if I'm wrong.

share|cite|improve this question
The article mentions a possible advantage, that an isolated error does not mess up much. But then again, that's what error-correcting codes are for. – André Nicolas May 4 '12 at 22:51
up vote 5 down vote accepted

Fibonacci codes are used as alternatives to dense codes for large textual word based data. They are in particular good choice for compressing a set of small integers, and fast decoding as well as compressed searches may be important tools for such applications.

Fibonacci codes are robust even against insertions and deletions. which means they are robust in terms of correcting errors. If the codes are to be used over a noisy communication channel, their resilience to bit insertions, deletions and to bit-flips is of high importance.

You may have to read this paper and some of its references

share|cite|improve this answer
Thanks, I have those paper and I'm going to read it ASAP. – ikostia May 4 '12 at 23:08

Fibonacci code is optimal for the distribution for which it is optimal!

That prefix code can be defined as the set of all bit-strings which terminate in '11' and contain no other '11' substring.

If '11' is replaced with '111' a different prefix-code is defined. More complicated termination conditions are possible, e.g. '1011' OR '1111'. In each case a prefix code is defined which will be, like a Huffman code, optimal for some distribution.

A main difference between these codes and Huffman codes is that the latter are finite, while Fibonacci or related codes can be used for arbitrarily large integers.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.