System and method for arithmetic encoding and decoding

Patent metadata

Field	Value
Publication number	US-9577667-B2
Application number	US-57038309-A
Country	US
Kind code	B2
Filing date	Sep 30, 2009
Priority date	Apr 23, 2002
Publication date	Feb 21, 2017
Grant date	Feb 21, 2017

Abstract

An arithmetic encoder is provided for converting an event sequence comprised of a plurality of events to an information sequence comprised of at least one information piece, and includes a core engine for receiving an event of the event sequence, and a probability estimate from a probability estimator, and generating zero or more pieces of the information sequence responsive to the received event and the probability estimate by bounding the ratio of events to information pieces. An arithmetic encoder is provided that is capable of constraining a number of events in at least one event sequence as a function of the number of generated information pieces in at least one information sequence. An arithmetic decoder is provided for converting an information sequence comprised of at least one information piece to an event sequence comprised of a plurality of events, and includes a core engine for processing at least one information piece of the information sequence from the sequencer responsive to a probability estimate received from a probability estimator to generate at least one event by accounting for a bounded ratio of events to information pieces in the information sequence.

First claim

I claim:

1. An entropy coder for converting at least one event sequence, each event sequence including a plurality of events, to at least one information sequence, each information sequence including at least one information piece, wherein the at least one event sequence represents input data partitioned into a number of segments, comprising:
an arithmetic encoder configured to generate zero or more information pieces of at least one information sequence by encoding at least one event of at least one event sequence; and
a controller coupled with the arithmetic encoder configured to maintain a constraint of the number of events of the sequence of events with respect to a number of information pieces generated wherein the constraint includes the number of events in the at least one event sequence to be equal to or less than a number determined by a function of a linear combination including the number of generated information pieces in at least one information sequence and the number of segments.

2. The entropy coder of claim 1 , wherein the controller is further configured to constrain the number of events of at least one event sequence to the number of information pieces of at least one information sequence by generating zero or more stuffing pieces in at least one information sequence.

3. The entropy coder of claim 1 , wherein the input data is video data.

4. The entropy coder of claim 3 , wherein each segment comprises a block of 16 by 16 samples of the input data.

5. An encoding apparatus comprising the entropy encoder of claim 1 , further comprising a processor configured to convert the input data into the at least one event sequence.

6. The encoding apparatus of claim 5 wherein the controller is further configured to constrain the number of events of the at least one event sequence to the number of information pieces of the at least one information sequence by generating zero or more stuffing pieces in the at least one information sequence.

7. The encoding apparatus of claim 5 wherein the processor is further configured to partition the input data into the number of segments.

8. The encoding apparatus of claim 7 , wherein the input data is video data.

9. The encoding apparatus of claim 8 , wherein each segment comprises a block of 16 by 16 samples.

10. The encoding apparatus of claim 7 , wherein the controller is further configured to constrain the maximum number of events by generating zero or more stuffing pieces in the at least one information sequence.

11. An entropy encoding method of converting at least one event sequence, each event sequence including a plurality of events, to at least one information sequence, each information sequence including at least one information piece, wherein the at least one event sequence represents input data partitioned into a number of segments, comprising:
computer implemented steps performed by a processor of a computer system to implement:
generating zero or more information pieces of at least one information sequence by encoding at least one event of at least one event sequence according to an arithmetic encoding; and
maintaining a constraint of the number of events of the sequence of events with respect to a number of information pieces generated wherein the constraint includes the number of events in at least one event sequence to be equal to or less than a number determined by a function of a linear combination including the number of generated information pieces in at least one information sequence and the number of segments.

Assignees

• Bossen Frank Jan
• Ntt Docomo Inc

Inventors

• Bossen Frank Jan

Classifications

• H03M7/4006 Primary

  Conversion to or from arithmetic code · CPC title

• G06T9/00

  Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00) · CPC title

• H03M7/4018

  Context adapative binary arithmetic codes [CABAC] · CPC title

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• G06T9/005

  Statistical coding, e.g. Huffman, run length coding · CPC title