Correction: Fibonacci Coding can (NOT!) maximize compression

Jpeg’s, MP3’s and digital video, together with encrypted data, all create data dense encoding. As a result they are hard to compress further. In encryption, this hurdle is overcome by compressing first, before we encrypt, enhancing the effect of encryption as a side effect.

An exception might be Fibonacci Coding. If a message was a number, Fibonacci Coding would represent that number as a summation of Fibonacci numbers, using a creative notation scheme that results in only 1’s and 0’s. It further eliminates double one (11,) entries, using double one as termination indicator.

The resulting list is usually longer than the message number, but has a vocabulary that lends itself to dictionary compression. Huffman encoding is a good example of a dictionary coder. These are all examples of lossless compression.

Since Fibonacci Coding uses such a simple vocabulary, it might be easier to reverse even against encrypted data.

Fibonacci Coding theoretically yields the best lossless compression short of a Universal Code. Depending on what compromises you are prepared to make, lossy compression might result in a smaller compressed message, but the compression-decompression cycle would result in lost information.

Updated entry “Chalk One Up to Academia,” clarifies why Fibonacci Coding does not compress data.


About James Johnson

I am an amateur mathematician & political theorist who enjoys (occasionally cerebral) humor.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s