Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2003-09-18
2004-11-30
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
C702S181000
Reexamination Certificate
active
06825782
ABSTRACT:
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The present invention relates generally to information theory, video compression and arithmetic coding. More particularly, the present invention relates to method and apparatus for termination of arithmetic coding and byte stuffing, as well as the creation and use of a state machine during arithmetic coding
BACKGROUND
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a network transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner that allows for perfect reconstruction.
Arithmetic coding is a well-known compression technique that is used in some data coding and compression systems to reduce the number of bits or symbols required for transmission. An arithmetic encoder receives an input, which includes a sequence of events (e.g., binary events), or symbols. The encoder encodes the input sequence into a corresponding sequence of bits or bytes. In some cases, fewer data bits are produced at the encoder output than are received at the encoder input, resulting in data compression. An arithmetic decoder may receive or access the encoded data. The arithmetic decoder reads the sequence of encoded data and produces decoded data, which should match the input symbols received at the decoder. Compression is achieved by generating less bits in the information sequences for the events being encoded, where ratios of events to information bits being encoded may reach 64:1 or even 128:1, depending on the probability distribution of the events.
Preferably, decoder operation is symmetric with encoder operation. If the encoder and decoder are symmetric in operation, the number of encoded data bits read at the decoder should match the number of encoded bits produced by the encoder.
In some arithmetic decoders, upon initiating the decoder operation, the decoder reads ahead a group of bits. However, since the decoder reads ahead a group of bits, a mismatch or asymmetry can occur.
One conventional solution to compensate for this asymmetry has been to add extra bits to the encoded data at the encoder. In another convention solution, no additional encoded bits are generated but the decoder is allowed to read ahead in the bitstream of encoded data, then back track.
Both of these conventional solutions introduce inefficiencies. A more efficient solution is desired to reduce the complexity of the coding and decoding algorithms, reduce data for encoding, transmission and decoding and to reduce storage requirements.
SUMMARY OF THE INVENTION
Methods and apparatus for performing a arithmetic encoding and/or decoding are disclosed. In one embodiment, an arithmetic decoder comprises a sequencer to generate a context identifier for an event of an event sequence, a probability estimator to determine a value for a least probable symbol (LPS) and a probability estimate for the LPS, and a decoding engine that includes a range register to assign a value to a range for the LPS. The value is based on the probability estimate, a value stored in the range register and the context identifier to a range for the LPS if the context identifier is not equal to an index and the value is not based on the value stored in range register if the context identifier is equal to the index. The decoding engine further determines a value of a binary event based on the value of the range for the LPS and bits from an information sequence.
REFERENCES:
patent: 5099440 (1992-03-01), Pennebaker et al.
patent: 5583500 (1996-12-01), Allen et al.
patent: 5751859 (1998-05-01), Howard
patent: 6236759 (2001-05-01), Horie et al.
patent: 6411231 (2002-06-01), Yanagiya et al.
patent: 6476740 (2002-11-01), Bengio et al.
patent: 6677869 (2004-01-01), Horie
Yip,US application No. 09/927,316, “Entropy Encoding and decoding” filed on Aug. 13, 2001.*
Horie (US application No. 10/680,152) “an arithmetic decoding method and an arithmetic decoding apparatus”, filed on Oct. 8, 2003.
Jeanglaude Jean Bruner
NTT Docomo Inc.
LandOfFree
Method and apparatus for arithmetic coding and termination does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for arithmetic coding and termination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for arithmetic coding and termination will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274885