Universal and Non-universal Codes
These are some universal codes for integers; an asterisk (*) indicates a code that can be trivially restated in lexicographical order, while a double dagger (‡) indicates a code that is asymptotically optimal:
- Elias gamma coding *
- Elias delta coding * ‡
- Elias omega coding * ‡
- Exp-Golomb coding *, which has Elias gamma coding as a special case. (Used in H.264/MPEG-4 AVC)
- Fibonacci coding
- Levenstein coding * ‡, the original universal coding technique
- Byte coding, also known as comma coding, where a special bit pattern (with at least two bits) is used to mark the end of the code — for example, if an integer is encoded as a sequence of nibbles representing digits in base 15 instead of the more natural base 16, then the highest nibble value (i.e., a sequence of four ones in binary) can be used to indicate the end of the integer.
These are non-universal ones:
- unary coding, which is used in Elias codes
- Rice coding, which is used in the FLAC audio codec and which has unary coding as a special case
- Golomb coding, which has Rice coding and unary coding as special cases.
Their nonuniversality can be observed by noticing that, if any of these are used to code the Gauss–Kuzmin distribution or the Zeta distribution with parameter s=2, expected codeword length is infinite. For example, using unary coding on the Zeta distribution yields an expected length of
On the other hand, using the universal Elias gamma coding for the Gauss–Kuzmin distribution results in an expected codeword length (about 3.51 bits) near entropy (about 3.43 bits).
Read more about this topic: Universal Code (data Compression)
Famous quotes containing the words universal and, universal and/or codes:
“The earliest instinct of the child, and the ripest experience of age, unite in affirming simplicity to be the truest and profoundest part for man. Likewise this simplicity is so universal and all-containing as a rule for human life, that the subtlest bad man, and the purest good man, as well as the profoundest wise man, do all alike present it on that side which they socially turn to the inquisitive and unscrupulous world.”
—Herman Melville (1819–1891)
“Vanity, or to call it by a gentler name, the desire of admiration and applause, is, perhaps, the most universal principle of human actions.... Where that desire is wanting, we are apt to be indifferent, listless, indolent, and inert.... I will own to you, under the secrecy of confession, that my vanity has very often made me take great pains to make many a woman in love with me, if I could, for whose person I would not have given a pinch of snuff.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Thou hast a voice, great Mountain, to repeal
Large codes of fraud and woe; not understood
By all, but which the wise, and great, and good
Interpret, or make felt, or deeply feel.”
—Percy Bysshe Shelley (1792–1822)