Log encoder/decorder system
AssigneeInternational Business Machines Corporation
InventorsJoan L. Mitchell, William B. Pennebaker, Gerald Goertzel
Life of this patent
Estimating the term…
Abstract
A high speed form of finite precision binary arithmetic coding comprises encoding/decoding performed in the logarithm domain, resulting in facilitated computation based on additions and subtractions rather than multiplications and divisions. In encoding and decoding, antilogs are used which are retrieved from an antilog table. The antilog table is characterized by the following constraints to assure decodability wherein for any two mantissas .alpha. and .beta. representing respective inputs to the antilog table: (a) antilog (.alpha.+.beta.).ltoreq.antilog (.alpha.) * antilog (.beta.); at least when (.alpha.+.beta.) is less than one; and (b) each antilog table output value is to be unique.
Claims17
A machine-implemented method of compressing data where successive binary decisions are normally encoded to a point in a range R along a number line, wherein one decision outcome has a probability Q and the other decision outcome has a probability P and wherein the range R normally shrinks in magnitude with each successive encoded decision to a new range product of either R multiplied by Q (R*Q) or R multiplied by P (R*P), the method comprising the steps of:
- producing, in a state generator, a string of decisions and a respective context state corresponding to each produced decision;
- and
- logarithmically encoding the string of decisions and context states into a compressed form including the steps of:
- representing the range and probability values of the new range product in the logarithmic domain, wherein each such logarithmic value has a finite precision mantissa;
- and
- re-computing a next range R in the logarithmic domain as the sum of the logarithm of the current R (log R) plus the logarithm of either P or Q (log P or log Q) depending on the decision outcome being encoded.
A computerized apparatus for compressing data where successive binary decisions are normally encoded to a point in a range R along a number line, wherein one decision outcome has a probability Q and the other decision outcome has a probability P and wherein the range R normally shrinks in magnitude with each successive encoded decision to a new range product of either R multiplied by Q (R*Q) or R multiplied by P (R*P), the apparatus comprising:
- state generator means for producing a string of decisions and a respective context state corresponding to each produced decision;
- and
- means for logarithmically encoding the string of decisions and context states into a compressed form including:
- means for representing the range and probability values of the new range product in the logarithmic domain, wherein each such logarithmic value has a finite precision mantissa;
- and
- means for recomputing a next range R in the logarithmic domain as the sum of the logarithm of the current R (log R) plus the logarithm of either P or Q (log P or log Q) depending on the decision outcome being encoded.
In data compression/decompression where successive binary decisions are normally encoded to one code stream value X after another each of which corresponds to one point in a range R along a number line after another, wherein one decision outcome has a probability Q and the other decision outcome has a probability P and wherein a next range R is normally determined for each successive encoded decision outcome as either a current range R multiplied by Q or the current range R multiplied by P, a logarithmic arithmetic coding data compression/decompression computerized apparatus comprising:
- encoder state generator means for producing, in response to input data, a string of decision outcomes and a respective context state which indicates (i) the respective probability values of P and Q and (ii) which decision outcome is more probable for each produced decision;
- and
- log encoder means for logarithmically encoding the string of decision outcomes and context states into a compressed form including:
- first memory table means for storing logarithmic mantissa values associated with real domain values, each mantissa value having a finite bit length;
- means for converting the range-determining values into the logarithmic domain as a mantissa value from said first table means;
- and adder means for re-computing, for a given decision outcome and context state, the next range in the logarithmic domain as LR, where LR is the sum of the logarithm of the current range R (log R) plus the logarithm of either P (log P) or Q (log Q) depending on the decision outcome being encoded.
Dependencies are inferred from the claim text.