Patent ID: 6259388
Filing Date: 2001-07-10
Classification: H03M

Abstract:
A method of multiplication-free arithmetic coding to produce an encoded bit stream, comprising the steps of:initializing a first register to one and allowing a second register to be an arbitrary number;for each symbol in an input string, iteratively performing the following steps a-e:a. receiving a first frequency count representing a fractional value of the probability of 0, a second frequency count representing a fractional value of the probability of 1, and the symbol;b. if the first frequency count is greater than the second frequency count, then exchanging the values of the first frequency count and the second frequency count and setting a value of the encoded symbol to its logic complement;c. while a value of the first register is less than or equal to the first frequency count, iteratively performing the following steps c1-c3:c1. outputting a most significant bit of the second register,c2. left-shifting a value of the first register and a value of the second register, andc3. if the value of the first register is greater than the binary complement of the value of the second register, then setting the value of the first register to the binary complement of the value of the second register plus one;d. if the symbol equals zero, setting a value of the first register to the first frequency count, else subtracting the first frequency count from the value of the first register and adding the first frequency count to the value of the second register; ande. selecting the next symbol in the input string; andoutputting the value of the second register as the encoded bit stream.