I'm researching into Fibonacci coding and up until this point I have surprised myself and understood the majority of what I have been reading.
I'm now looking into the usefulness of Fibonacci coding, however dont quite understand exactly what is meant by the following sentence. (This reference is wikipedia, however it was the most easy to understand version, even though I still don't understand it!)
"With most other universal codes, if a single bit is altered, 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."
I understand that this is trying to say that Fibonacci coding is very good at error detecting, however I don't quite understand why!?
If anyone could explain, that would be wonderful! An example or two and I'd be forever in your debt.
The point is that every number ends with $11$, but the string $11$ appears nowhere else in the data stream. If you change a bit it corrupts the symbol you change it in, but within a couple symbols you will find the pattern $11$ which indicates the end of a symbol. You can then start decoding again correctly with only those symbols incorrect. The first claim is that changing one bit can corrupt at most three symbols. You should be able to verify that by thinking about the possibilities: a 0 gets changed to a 1 that is next to a correct 1, a 1 that is part of the data gets changed to a 0, a 1 that is part of the ending 11 gets changed to a 0, and so on. The second claim is that other codes do not share this property, that the decoding never gets resynchronized, so once you make an error the stream is wrong forever.