Universal code: Difference between revisions

Revision as of 03:54, 23 January 2005

Revision as of 11:03, 23 January 2005

Line 5:

(Self-delimiting codes are also called [[prefix-free]] codes or "instantaneously decodable" codes).

Unlike other compression codes such as [[Huffman coding]] or [[fixed-length codes]], universal codes do not require the recieverreceiver or the transmitter to know the maximum integer (number of potential messages) ahead of time.

Universal codes include:

Line 22:

However, universal codes are useful when Huffman coding cannot be used -- for example, when one does not know the exact probability of each message, but only knows their ranking (this message is more probable than that message).

Universal codes are also useful when Huffman codes are inconvenient. For example, when the transmitter but not the recieverreceiver knows the probabilities of the messages, Huffman coding requires an overhead of transmitting those probabilities to the recieverreceiver. Using a universal code does not have that overhead.

Each universal code, like each other self-delimiting (prefix-free) binary code, has its own "implied probability distribution". If a set of messages happens to have a probability distribution similar enough to that implied by some universal code, then the Huffman code for that set of messages will be equivalent to that universal code. Since universal codes are simpler and faster to encode and decode than Huffman codes (which is, in turn, simpler and faster than [[range encoding]] and [[arithmetic encoding]]), the universal code would be preferable in cases where the codes are equivalent.