Method and apparatus for encoding and decoding data

A coding system for processing data comprising:

• an index generator for generating indices based on the data;
• and
• a state table coupled to provide a probability estimate based on the indices, wherein the state table includes a plurality of states, wherein each of the states corresponds to a code, and every code in the state table is repeated a predetermined number of times;
• wherein transitioning between states of the state table occurs based on an acceleration term that is modifiable, such that transitioning between states occurs at a first rate during a first time period is different than a second rate of transitioning during a second time period.

An entropy decoder for decoding a data stream of a plurality of codewords comprising:

• a plurality of bit stream generators for receiving data from the data stream;
• and
• a state table coupled to provide probability estimates based on the indices, wherein the state table includes a plurality of states, wherein each of the states corresponds to a code, and every code in the state table is repeated a predetermined number of times;
• wherein transitioning between states of the state table occurs based on an acceleration term that is modifiable, such that a first rate of transitioning between states during a first time period is different than a second rate of transitioning during a second time period.

A decoding system comprising:

• a FIFO structure coupled to receive data;
• a context model for providing contexts;
• a memory coupled to the context model for storing state information and providing state information in response to each context provided by the context model;
• a plurality of decoders coupled to receive coded data from the FIFO structure and coupled to the memory for decoding codewords supplied by the FIFO structure using state information from the memory, wherein the plurality of decoders provide run counts may be generated for a plurality of codes.

A method for initializing a plurality of contexts in a system while coding data, said method comprising:

• specifying an initial PEM state;
• obtaining a PEM state of a current context, wherein the step of obtaining comprises the steps of
• accessing a memory location for the current context to obtain a currently assigned PEM state;
• determining whether the memory location is valid by comparing a current context number for the current context to a counter value incremented as each context is accessed, wherein the currently assigned PEM state is determined valid is if the counter value indicates that the memory location has already been initialized;
• using the initial PEM state for the current context and ignoring currently assigned PEM state for the current context when PEM data of the accessed memory location is not valid;
• and
• using the currently assigned PEM state for the current context if the PEM data is valid.

A decoder comprising:

• a context model to provide context bins;
• a memory coupled to the context model to provide probability states based on the context bins;
• a logic coupled to the memory to generate probability classes based on the probability states;
• a decoder coupled the logic to generate a plurality of enable signals based on the probability classes;
• a plurality of bit generators coupled to the decoder and coupled to receive the coded data, wherein each of the plurality of bit generators is dedicated to at least one distinct code and operates in response to a distinct one of the plurality of enable signals, wherein the decoder enables one of the plurality of bit generators based on a current probability class to cause one of the plurality of bit stream generators to decode coded data associated with the current probability class.

A method for decoding comprising the steps of:

• providing a context bin;
• accessing a memory using the context bin to obtain a probability state;
• generating a probability class based on the probability state;
• enabling one of a plurality of bit generators, wherein each of the plurality of bit generators is dedicated to at least one distinct code, such that only said at least one distinct code is used for decoding;
• and
• said one of the plurality of bit stream generators decoding coded data.

An encoder system comprising:

• a context model to provide context bins
• a memory coupled to the context model to provide probability states based on the context bins;
• a logic coupled to the memory to generate probability classes based on the probability states;
• an encoder coupled the logic to generate a plurality of enable signals based on the probability class;
• a plurality of bit generators coupled to the encoder and coupled to receive the input data, wherein each of the plurality of bit generators is dedicated to at least one distinct code, wherein the encoder enables one of the plurality of bit generators based on a current probability class, such that said one of the plurality of bit stream generators encodes input data associated with the current probability class.

A method for encoding comprising the steps of:

• providing a context bin;
• accessing a memory using the context bin to obtain a probability state;
• generating a probability class based on the probability state;
• enabling one of a plurality of bit generators that are dedicated to at least one distinct code, such that only said one distinct code is used for encoding;
• and
• said one of the plurality of bit stream generators encoding the input data.

A method for decoding coded data comprising a plurality of codewords, said method comprising the steps of:

• loading a count value into a counter associated with each run counter, wherein the count value corresponds to the size of a codeword memory used during encoding when a new run is started, said count value being loaded when a new codeword for said each run counter is fetched;
• decrementing the count value each time any codeword is fetched;
• and
• clearing a bit generator state associated with said new codeword when the counter decrements to zero.

A method for decoding coded data comprising a plurality of codewords, said method comprising the steps of:

• incrementing a counter value each time a codeword is requested, wherein the counter value comprises a current time indication;
• storing the counter value as a stored time indication when a codeword is started;
• comparing the stored time indication plus the size of an encoder memory to the current time indication;
• and
• clearing a bit generator state for the first codeword and requesting a new codeword when the current time indication is greater than the stored time indication plus the size of an encoder memory.

A method for decoding coded data comprising a plurality of codewords, said method comprising the steps of:

• storing an index corresponding to a codeword, wherein the index is stored in a queue when the codeword is requested;
• marking an entry of the index in the queue as invalid;
• storing the codeword in the entry and marking the entry as valid if the codeword completes;
• and
• outputting data from the queue comprising the steps of outputting data from the queue entry and indicating the data is invalid to the decoder if the queue entry is marked invalid and the codeword prematurely completes and the decoder clearing bit generator state information in response to receiving data from the queue marked invalid.

A decoder for decoding coded data, said decoder comprising:

• a context modelling mechanism for providing contexts, wherein the context modelling mechanism comprises a plurality of integrated circuits;
• a memory coupled to the context modeling mechanism for storing state information, wherein the memory provides state information in response to each context provided by the context modeling mechanism;
• and
• a plurality of decoders coupled the memory for decoding codewords using the state information from the memory, wherein the plurality of decoders decode codewords using a plurality of R-codes, wherein the plurality of R-codes are operable to code at least one non-maximum length run of most probable symbols that is not followed by a least probable symbol.

A system for decoding a code stream having a plurality of codewords, said system comprising:

• a context modelling mechanism for providing contexts, wherein the context modelling mechanism comprises a plurality of integrated circuits;
• a memory coupled to the context modeling mechanism for storing state information, wherein the memory provides state information in response to each context provided by the context modeling mechanism;
• and
• a plurality of decoders coupled the memory for decoding codewords using the state information from the memory.

A system for decoding a code stream having a plurality of codewords, said system comprising:

• a context modelling mechanism for providing contexts;
• a memory coupled to the context modeling mechanism for storing state information, wherein the memory provides state information in response to each context provided by the context modeling mechanism;
• and
• a plurality of decoders coupled to the memory for decoding codewords using the state information from the memory, wherein at least one of the plurality of decoders comprises a delay tolerant decoder.