Z-coder: a fast adaptive binary arithmetic coder

Details Z-coder: a fast adaptive binary arithmetic coder Z-coder: a fast adaptive binary arithmetic coder

2001-12-14

2002-11-05

Wamsley, Patrick (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C341S051000

Reexamination Certificate

active

06476740

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a improved adaptive binary arithmetic coder that provides improved processing speed and accuracy over conventional arithmetic coders.
2. Related Art
Arithmetic coders provide well-known algorithms for encoding data. Compression ratios of the arithmetic coders can reach the information theory limit. The arithmetic coder and decoder must possess good estimates of the probability distribution of each symbol to code. For each symbol to be coded in a string element, the encoder and decoder must possess a table containing estimated probabilities for the occurrence of each possible symbol at each point in the symbol string. The coders themselves must perform a table search and at least one multiplication. For this reason, arithmetic coders incur high computational expense. Binary adaptive arithmetic coders, such as the “Q-Coder,” by Pennebaker, et al. (1998) and the “QM-Coder,” by Ono (1993), have been developed to overcome this drawback.
A high-level system diagram of a prior art binary arithmetic coder is shown in FIG.
1
. Data to be coded is input to an encoder
100
. The encoder
100
encodes the data and outputs a string of coded data to a channel
200
. A decoder
300
retrieves the code string from the channel
200
and replicates the original data by decoding the coded data.
The coding process often is described by the operation of the decoder
300
. In the decoder, the code string is interpreted as a binary representation of a real number contained in the unit interval [0,1[. The binary arithmetic coder divides the unit interval into two sub-intervals having lengths that are proportional to the estimated probabilities of each value of the first bit in the symbol string. Any code string located in a first, lower sub-interval represents a symbol string starting with a zero (0). Conversely, any code string located in the upper sub-interval represents a symbol string starting with a one (1).
Each of the sub-intervals can be divided into two smaller sub-intervals having lengths that are proportional to the estimated conditional probabilities of the second symbol bit given the previously encoded symbol bit. Any code string located in one of these sub-intervals represents a symbol string starting with the corresponding two bit prefix.
The decoding process is repeated. Sub-intervals are themselves divided into smaller sub-intervals representing probabilities of the value of the next bit in the symbol string. The process produces a partition of the unit interval having sub-intervals that correspond to each possible value of the symbol string. Any code string in the interval can be chosen corresponding to the encoded symbol string.
According to theory, when an interval is divided into sub-intervals, the length of each sub-interval should be proportional to the probability of the value of the next data symbol to be decoded given the previous symbol bits. The probability distribution of the code string therefore would be uniform in the interval. Since each code bit is equally likely to be a 0 or a 1, it would carry as much information as information theory allows. In other words, the coder would achieve entropic compression.
The known Q-Coder and QM-Coder, while they represent advances over traditional arithmetic coders, do not provide performance that approaches entropic compression. Thus, there is a need in the art for a binary arithmetic coder that provides improved compression ratios than the Q-Code and the QM-Coder.
Decoding speed is an important performance characteristic of data coding systems. Decoding latency, the time that is required to generate decoded data once the coded data is received should be minimized wherever possible. Thus, decoders that introduce lengthy or complex computational processes to the decoding operation are disfavored. Accordingly, there is a need in the art for a data decoding scheme that is computationally simple and provides improved throughput of decoded data.
SUMMARY OF THE INVENTION
The present invention provides a binary arithmetic coder and decoder having important advantages over the prior art. The coding scheme provides improved coding accuracy over the prior art due to improved probability estimation and adaptation. It provides improved decoding speed through a “fast path” design wherein decoding of a most probable symbol requires few computational steps.
According to the present invention, coded data represents data that is populated by more probable symbols (“MPS”) and less probable symbols (“LPS”). In an embodiment, the decoder receives a segment of the coded data as a binary fraction C. It defines a coding interval of possible values of C, the interval extending from a variable lower bound A to a constant upper bound 1. For each position in the decoded symbol string, the decoder computes a test value Z that subdivides the coding interval into sub-intervals according to the relative probabilities that an MPS or an LPS occurs in the position. A first sub-interval extends from the lower bound A to the test value Z; the second sub-interval extending from the test value Z to 1. If C is greater than Z, the decoder emits an MPS for the current position in the decoded symbol string and sets the lower bound A to the test variable Z for use during decoding of the next position in the decoded symbol string. If C is less than Z, the decoder emits an LPS and computes a new lower bound A and a new binary fraction C for use during decoding of the next position in the decoded symbol string. The encoder operates according to analogous techniques to compose coded data from original data.


REFERENCES:
patent: 4933883 (1990-06-01), Pennebaker et al.
patent: 4935882 (1990-06-01), Pennebaker et al.
patent: 5059976 (1991-10-01), Ono et al.
patent: 5307062 (1994-04-01), Ono et al.
patent: RE35781 (1998-05-01), Ono et al.
patent: 6144320 (2000-11-01), Van Der Leuten
patent: 6188334 (2001-02-01), Bengio et al.
patent: 6225925 (2001-05-01), Bengio et al.
patent: 6281817 (2001-08-01), Bengio et al.
patent: 1291820 (1991-11-01), None
patent: 1291821 (1991-11-01), None
patent: 1292070 (1991-11-01), None
patent: 2008943 (1995-04-01), None
Ono et al, “Bi-Level Image Coding with Melcode—Comparison of Block Type Code and Arithmetic Type Code—”, Communication Systems Development Lab., Mitsubishi Electric Corp., CH2682-3/89/0000-0255 1989 IEEE.
Paul G. Howard, Jeffrey Scott Vitter,Arithmetic Coding for Data Compression, Proceedings of the IEEE, vol. 82, No. 6, Jun. 1994.
Langdon, Jr. “An Introduction to Arithmetic Coding”, IBM Journal of Research and Development, U.S., IBM Corp., Armonk, vol. 28, No. 2, pp. 135-149.
Mitchell et al, “Software Implementations of the Q-Coder”, IBM Journal of Research and Development, U.S., IBM Corp., Armonk, vol. 32, No. 6, pp. 753-774.
“Speed-Up Mode” for Q-Coder Software Implementation, IBM Technical Bulletin, U.S. IBM Corp., New York, vol. 32, No. 8B, pp. 17-20.

Affiliated with

Also associated with

Rating

Z-coder: a fast adaptive binary arithmetic coder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Z-coder: a fast adaptive binary arithmetic coder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Z-coder: a fast adaptive binary arithmetic coder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2972455