Take the 2-minute tour ×
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.

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|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
add comment

2 Answers 2

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|improve this answer
    
Thanks, I have those paper and I'm going to read it ASAP. –  ikostia May 4 '12 at 23:08
add comment

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|improve this answer
add comment

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.