View Source: ArithmeticEncoding - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages

An encoding of all binary strings in the range to all [Binary] strings in the domain, based on an expected probability distribution of bitstings. The encoder starts with the range [0,1) and to encode reach bit the encoder takes the expected distribution of the bit (maybe 20/80) and divides the range in those proportions and throws away the portion the bit didn't fall into (in this case either [[0,0.2) or [[0.8,1) ). When all bits have been seen the range is sent as the encoding.

ArithmeticDecoding is the reverse process.

ArithmeticEncoding has been shown to be the asymototical optimal way to encode such a string (only  asymototical optimal because of the need to round up the range to the nearest bit).

ArithmeticEncoding and ArithmeticDecoding are used in bzip2(1) and but zip(1).


AddToMe.

2 pages link to ArithmeticEncoding:

HuffmanCoding
ArithmeticDecoding

Last edited on Friday, October 10, 2003 12:35:03 am by StuartYeates

Edit PageHistory Diff Info LikePages