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 6 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

With regular binary coding, you need to know in advance the maximum possible number. For example, if you choose 16 bits, you're limited to 0-65535, and if you happen to need a larger number you're in trouble - which, depending on the application, can mess things up completely.

You can "upgrade" binary coding to allow arbitrarily large numbers. But this requires additional bits.

Fibonacci coding natively supports arbitrarily large numbers. When compared with the upgraded binary coding, some codewords will be shorter, some longer. Which is better depends entirely on the distribution - Fibonacci will fare better when the probability decreases faster as the values increase.

In addition, Fibonacci coding is more elegant and regular.

Of course, if you do know in advance the possible range, and the values are distributed uniformly over this range, then of course there's no contest - that's the situation binary coding was made for, and it will beat any other coding (assuming the number of possible values is a power of 2).

share|cite|improve this answer

Your Answer

 
discard

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.