Method and apparatus for encoding and decoding data

• US 5,717,394 A
• Filed: 12/17/1996
• Issued: 02/10/1998
• Est. Priority Date: 02/10/1993
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Gormish, Michael J., Allen, James D., Schwartz, Edward L., Boliek, Martin
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/768,237
• Time in Patent Office: 420 Days
• Field of Search: 341/51, 341/63, 341/65, 341/67, 341/60, 341/107
• US Class Current: 341/51
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A method and apparatus for decompressing and compressing data is described. The present invention provides an encoder for use in a compression system having a decoder for decoding information generated by the encoder. The encoder of the present invention includes a coder for producing codeword information in response to data. The encoder also includes a reorder unit that generates a coded data stream in response to the codeword information from the coder. The reorder unit comprises a run count reorder unit for arranging codewords into a decoding order and a bit pack unit to combine variable length codewords into fixed length interleaved words and to output the fixed length interleaved words in an order required by the decoder.

Claims

1. A method for encoding a data stream comprising the steps of:

generating codeword information representative of the data stream in response to the data stream, wherein the codeword information comprises a plurality of codewords, and further wherein multiple codewords are generated from data of the data stream being processed in parallel;

generating coded data in response to the codeword information, wherein the step of generating coded data comprises outputting each of said plurality of codewords in the codeword information as fixed length data structures ordered in an order based on data at the beginning of each if the fixed length data structures.

2. The method defined in claim 1 wherein each of the plurality of codewords are output at the beginning of each run.

3. The method defined in claim 1 wherein the step of generating coded data further comprises combining variable length codewords into fixed length data structures.

4. The method defined in claim 3 wherein each of the fixed length data structures comprises an interleaved word.

5. The method defined in claim 1 further comprising outputting coded data such that codewords are ordered in a decoding order.

6. The method defined in claim 1 further comprising the step of ordering codewords.

7. The method defined in claim 1 wherein the step of generating codeword information comprises the steps of:

generating a probability state of a codeword;

selecting a bit generation code based on the probability state; and

accessing memory to obtain a run count associated with the bit generation code.

8. The encoding system defined in claim 7 wherein the reorder unit stores the codewords in such a manner as to indicate codeword size.

9. The encoding system defined in claim 8 wherein 1N codewords are reordered such that the the most significant "1" bit indicates the length of each codeword.

10. An encoding system for encoding a data stream, said encoding system comprising:

an encoder coupled to receive the data stream for generating codeword information including codewords, and further wherein multiple codewords are generated by the encoder from data being processed in parallel; and

a reorder unit coupled to the encoder to generate coded data as a code stream in response to the codeword information, wherein the reorder unit reorders codewords generated by the encoder in a decoder order based on data at the beginning of a portion of the data stream represented by each codeword.

11. The encoding system defined in claim 10 wherein the reorder unit comprises:

at least one run count reorder unit to generate each of said plurality of codewords in the codeword information at the beginning of each run; and

at least one bit pack unit to combine variable length codewords into fixed length data structures.

12. The encoding system defined in claim 11 wherein each of the fixed length data structures comprises an interleaved word.

13. The encoding system defined in claim 11 wherein said at least one bit pack unit orders interleaved words to generate the coded data stream as interleaved streams ordered according to a Nth previous codeword in each interleaved word of each stream.

14. The encoding system defined in claim 11 wherein the reorder unit comprises a snooper decoder for selecting interleaved words output into the code stream.

15. The encoding system defined in claim 14 wherein the reorder unit comprises a plurality of run count reorder units coupled to a plurality of bit pack units, wherein each of the plurality of bit pack units generates interleaved words and the snooper decoder selects an interleaved word from the plurality of interleaved words as an output into the code stream.

16. The encoding system defined in claim 11 wherein a single queue supplies codewords to a plurality of bit pack units, and wherein the plurality of bit pack units generate interleaved words for output as part of the code stream.

17. The encoding system defined in claim 16 wherein the single queue includes a single run count reorder unit, and wherein logic determines the next interleaved word for output as part of the code stream.

18. The encoding system defined in claim 11 wherein a single queue supplies codewords to a single bit pack unit.

19. The encoding system defined in claim 10 further comprising a memory coupled to the reorder unit to store codewords in an order.

20. The encoding system defined in claim 10 wherein the encoder comprises:

a context model;

a probability estimation machine coupled to the context model; and

a bit generator structure coupled to the probability estimation machine to generate codewords in response to the data stream.

21. The encoding system defined in claim 20 wherein the encoder further comprises a memory storing a plurality of run counts, and wherein the memory is accessed using a probability class from the probability estimation machine to provide one of the plurality of run counts to the bit generator for output as part of the codeword information.

22. The encoding system defined in claim 20 wherein the bit generator structure comprises:

a bit generator to provide codeword information in response to an index and an MPS/LPS indication; and

a memory coupled to the bit generator for providing a run count to the bit generator, wherein the bit generator reads the memory based on the index and performs bit generation based on data obtained from reading the memory.

23. The encoding system defined in claim 22 wherein the codeword information comprises a first signal indicating whether the MPS/LPS indication comprises the start of a run, a second signal indicating whether the MPS/LPS indication comprises the end of a run, and a codeword output.

24. The encoding system defined in claim 22 wherein a bit generator state of the bit generator is updated after performing bit generation, and further wherein the bit generator is reused prior to completion of updating the bit generation state being written to the memory.

25. The encoding system defined in claim 24 wherein the bit generator is reused during the modify stage of a read-modify-write cycle.

26. The encoding system defined in claim 22 wherein the bit generator generates a non-minimal length run count when reused prior to writing an updated state to the memory.

27. The system defined in claim 26 wherein at least one of the plurality of decoders performs variable length shifting based on decoded data that is available after a delay.

28. The encoding system defined in claim 22 wherein the bit generator codes data using R-codes defined such that each run length is followed by at least one uncoded bit, thereby preventing two codewords of the same run length from being decoded in a row.

29. The encoding system defined in claim 10 wherein the codeword information includes a time stamp and wherein the reorder unit further comprises logic to output interleaved words based on associated time stamps.

30. The encoding system defined in claim 29 wherein the reorder unit comprises a plurality of run count reorder units coupled to a plurality of bit pack units, and further wherein the logic causes interleaved words to be output based on the associated time stamps.

31. The encoding system defined in claim 30 wherein interleaved words are output based on the oldest time stamp.

32. An encoding system for use in a compression system, said encoding comprising:

an encoder for producing codeword information in response to data;

a reorder unit coupled to the coder, wherein the reorder unit generates a coded data stream in response to the codeword information, wherein the reorder unit comprises a run count reorder unit for reordering run counts by placing each codeword at the beginning of a run and a bit pack unit coupled to receive codewords from the run count reorder unit to combine variable length codewords into a plurality of fixed length interleaved words and to output the plurality of fixed length interleaved words in an order required by a decoder.

33. The encoding system defined in claim 32 wherein the reorder unit further comprises a memory to store codewords during reordering.

34. The encoding system defined in claim 32 wherein the encoder further comprises a context model, a probability estimation mechanism coupled to the context model and a bit stream generator coupled to the probability estimation mechanism.

35. The encoding system defined in claim 34 wherein the run count reorder unit further comprises:

a first memory to store codewords;

a first indicator and a second indicator for addressing the first memory as a queue, wherein the first indicator points to a first entry designated as an output of the first memory and the second indicator points to a second entry designated as a next available and unassigned storage location in the first memory.

36. The encoding system defined in claim 35 further comprising a pointer memory for storing address information corresponding to locations in the first memory currently designated for storage of codewords for each index.

37. The encoding system defined in claim 36 wherein each index indicates a probability class.

38. The encoding system defined in claim 36 wherein each index indicates at least one context.

39. The encoding system defined in claim 32 wherein the reorder unit further comprises a codeword memory queue for storing codewords, a head pointer coupled to the codeword memory queue to indicate at least one memory location of at least one codeword for output from the codeword memory queue, and a tail pointer to indicate at least memory location for inserting codewords into the codeword memory queue.

40. The encoding system defined in claim 39 wherein each codeword entry in the codeword memory queue includes a validity indication, and further wherein a codeword is output from the codeword memory queue when the head pointer specifies the address of the codeword and the validity indication for the codeword indicates its validity.

41. The encoder defined in claim 32 wherein the bit pack unit comprises bit packing logic to receive codewords from the reorder unit and merge codewords into interleaved words for a plurality of streams.

42. The encoder defined in claim 41 wherein the bit packing logic further comprises a plurality of accumulators and a plurality of registers, wherein each of the plurality of registers is associated with one of the plurality of accumulators and one of the plurality of streams, each register for storing an interleaved word for its associated stream and each accumulator indicating the next location in the associated register for storing a current codeword for the stream, such that each codeword for one of the plurality of streams is appended to the contents of the register associated with said one of the plurality of streams based on the value in the associated accumulator.

43. The encoding system defined in claim 42 further comprising a shifter coupled to the plurality of accumulators for shifting codewords in response to at least one signal from the plurality of accumulators, wherein codewords are shifted for appending to contents in one of the plurality of registers based on an accumulator value to pack portions of at least two codewords into each interleaved word.

44. The encoding system defined in claim 41 further comprising a reorder memory for storing interleaved words in an order designated by the decoder.

45. The encoding system defined in claim 44 further comprising a plurality of pointers corresponding to a plurality of interleaved data streams, wherein each of the plurality of pointers designates a location in the reorder memory for the next interleaved word for each of the plurality of streams.

46. The encoding system defined in claim 32 further comprising:

a plurality of run count reorder units, wherein each of the run count reorder units is associated with one of the coded data streams,

a plurality of bit pack units, when each of plurality of bit pack units is coupled to an individual one of the plurality of run count reorder units and generates interleaved words for each coded data stream; and

a decoder for selecting the interleaved words from the plurality of bit pack units as encoded output.

47. The encoding system defined in claim 32 further comprising:

a plurality of run count reorder units, wherein each of the run count reorder units is associated with one of the coded data streams and generates a plurality of codewords and a timestamp associated with each of the plurality of codewords;

a plurality of bit pack units for generating interleaved words for each coded data stream; and

logic for selecting each of the interleaved words based on timestamps of codewords in each of the interleaved words.

48. The encoding system defined in claim 47 wherein the logic selects an interleaved word containing a codeword having the oldest timestamp from among a plurality of interleaved words for each output of the encoder.

49. The encoding system defined in claim 32 wherein the bit pack unit comprises a plurality of bit packing units coupled to receive codewords from one of a plurality of streams, and further comprising logic to select interleaved words for output from each of the plurality of bit packing units based on the next stream.

50. The encoding system defined in claim 32 wherein the reorder unit further comprises a finite memory.

51. 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 first plurality of states and a second plurality of states, wherein each of the states corresponds to a code, and further wherein transitions between different codes corresponding to the first plurality of states occurs faster when transitioning between states in the first plurality of states than transitions between different codes corresponding to the second plurality of states when transitioning in the second plurality of states.

52. The coding system defined in claim 51 wherein the first plurality of states are used only for a predetermined number of indices.

53. The coding system defined in claim 52 wherein the first plurality of states includes at least one transition to the second plurality of states, such that the state table transitions to the second plurality of states from the first plurality of states after the predetermined number of indices.

54. The coding system defined in claim 51 wherein the first plurality of states are used only for a predetermined number of indices that initially index the state table.

55. The coding system defined in claim 51 wherein each of the first plurality of states are associated with an R2 code.

56. The coding system defined in claim 51 wherein each of the first plurality of states is associated with a different code.

57. The coding system defined in claim 51 wherein the state table transitions from one of the first plurality of states to one of the second plurality of states in response to a least probable symbol.

58. The coding system defined in claim 51 wherein the state machine increases state in response to a most probable symbol.

59. 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.

60. The coding system defined in claim 59 wherein the state table is updated by modifying the PEM state by incrementing or decrementing the acceleration term.

61. The coding system defined in claim 60 wherein no adaptive acceleration occurs when the acceleration term comprises a predetermined number.

62. The coding system defined in claim 60 wherein the acceleration term is updated based on the number of consecutive codewords.

63. The coding system defined in claim 62 wherein consecutive codewords comprises consecutive codewords in a context.

64. The coding system defined in claim 62 wherein consecutive codewords comprises consecutive codewords in a probability class.

65. The coding system defined in claim 60 wherein the acceleration term is updated based on the number of alternating codewords.

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

a plurality of bit stream generators for receiving the data stream; and

a state table coupled to the plurality of bit stream generators to provide a probability estimate to the plurality of bit stream generators, wherein the plurality of bit stream generators generates a decoded result for each codeword in the data stream in response to the probability estimate using a Rn(k) code for multiple values of n, and further wherein the state table includes a first plurality of states and a second plurality of states, wherein transitions between different codes in the first plurality of states occurs faster than transitions between codes in the second plurality of states.

67. The entropy decoder defined in claim 66 wherein the first plurality of states each contain an R2(k) code.

68. The entropy decoder defined in claim 66 wherein the first plurality of states am only used during initialization.

69. The coding system defined in claim 66 wherein every code in the state table is repeated a constant number of times.

70. The coding system defined in claim 69 wherein the state table is updated by modifying the PEM state by an acceleration term.

71. The coding system defined in claim 70 wherein no adaptive acceleration occurs when the acceleration term comprises a predetermined number.

72. The coding system defined in claim 70 wherein the acceleration term is updated based on the number of consecutive codewords.

73. The coding system defined in claim 70 wherein the acceleration term is updated based on the number of alternating codewords.

74. 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.

75. A decoder for decoding a plurality of interleaved words, said decoder comprising:

a variable length shifter for receiving the data stream and for shifting codewords to output properly aligned coded data, wherein the variable length shifter comprises a plurality of registers;

a run length decoder coupled to the variable length shifter to receive the properly aligned coded data as codewords for determining the codeword type;

a probability estimation machine coupled to the run length decoder to determine the code for the run length decoder, such that the run length decoder generates a run length and an indication of whether the LPS occurred in response to each codeword.

76. The decoder defined in claim 75 wherein a portion of the plurality of registers are coupled to receive data from another of the plurality of registers or from the data stream.

77. The decoder defined in claim 75 wherein the variable length shifter includes a barrel shifter to shift data into the plurality of registers.

78. The decoder defined in claim 75 wherein the variable length shifter comprises a FIFO having a plurality of registers, wherein each of the registers receives data as an input from the interleaved coded data and at least one of the plurality of registers is coupled to receive codewords from another of said plurality of registers.

79. The decoder defined in claim 75 wherein the shifter comprises:

a first plurality of registers coupled to receive codeword data, wherein each of the first plurality of registers is coupled to a distinct one of the plurality of streams;

a multiplexer coupled to receive codeword data from each of the first plurality of registers as an input and output codewords from one of the plurality of streams at a time;

a barrel shifter coupled to the output of the multiplexer to shift codeword data from the multiplexer for output as aligned coded data;

logic coupled to the barrel shifter to indicate a number of bits to shift the codeword; and

a FIFO having a plurality of registers coupled to receive codewords from said multiplexer, wherein the FIFO includes a plurality of registers, wherein each of the plurality of registers receives data as an input from the interleaved coded data and at least one of the plurality of registers is coupled to receive codewords from another of said plurality of registers.

80. 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.

81. The decoding system defined in claim 80 wherein the FIFO structure supplies coded data to the plurality of decoders independent of context and probability class.

82. The decoding system defined in claim 80 wherein the decoder comprises a run count memory for storing run counts which are assessible based on probability class.

83. The decoding system defined in claim 80 wherein the FIFO structure provides data for two of the plurality of decoders.

84. The decoding system defined in claim 80 wherein the FIFO structure comprises a plurality of outputs, one for each of the plurality of decoders.

85. The decoding system defined in claim 84 wherein the FIFO structure comprises a pair of multiplexers and control logic for selecting the pair of multiplexers to ensure that a codeword is provided to each decoder.

86. The decoding system defined in claim 85 wherein the pair of multiplexers are selected by the control logic based on requests received from one of the plurality of decoders.

87. An encoding system for encoding input data comprising:

an encoding unit coupled to receive the input data to generate coded data in the form of a plurality of streams, wherein coded data is assigned to one of the plurality of streams based on a set of criteria;

a fixed size memory coupled to the encoding unit for storing the plurality of streams of coded data, wherein coded data of greater importance is stored and coded data of less importance is discarded if the fixed size memory is full.

88. The encoding system defined in claim 87 wherein the memory comprises a plurality of storage areas, and coded data stored in each of the plurality of storage areas comprises coded data of a distinct importance level.

89. The encoding system defined in claim 87 wherein the memory comprises a plurality of storage areas, and further wherein coded data of one importance level is stored in at least one of the plurality of storage areas storing coded data of another importance level.

90. The encoding system defined in claim 89 wherein the coded data of said one importance level overwrites coded data of said another importance level in said at least one of the plurality of storage areas.

91. 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.

92. The method defined in claim 91 further comprising the step of writing a new PEM state if the PEM state has changed.

93. 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.

94. The decoder defined in claim 93 wherein at least one of the plurality of bit generators decodes data using an R-code and at least one of the plurality of bit generators decodes data using a non-R-code.

95. The decoder defined in claim 93 wherein at least one of the plurality of bit generators handles short run lengths and operates as an R-code decoder.

96. The decoder defined in claim 93 wherein at least one of the plurality of bit generators handles long run lengths and comprises a short run unit and a long run unit, wherein the short run unit handles codes of a first predetermined length and the long run unit handles any remaining bits and determines which, if any, of the remaining bits are to be output.

97. 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.

98. 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.

99. The encoder defined in claim 98 wherein at least one of the plurality of bit generators encodes data using an R-code and at least one of the plurality of bit generators encodes data using a non-R-code.

100. The encoder defined in claim 98 wherein at least one of the plurality of bit generators handles short run lengths and operates as an R-code encoder.

101. The decoder defined in claim 98 wherein at least one of the plurality of bit generators handles long run lengths and comprises a short run unit and a long run unit, wherein the short run unit handles codes of a first predetermined length and the long run unit handles any remaining bits and determines which, if any, of the remaining bits are to be output.

102. 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.

103. 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.

104. The method defined in claim 103 wherein each run counter is associated with a PEM state.

105. The method defined in claim 103 wherein each run counter is associated with a context bin.

106. 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.

107. The method defined in claim 106 wherein the stored time indication comprises a time stamp.

108. The method defined in claim 106 further comprising the step of reusing the stored time indication for a subsequent codeword.

109. 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.

110. 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.

111. The decoder defined in claim 110 wherein said at least one non-maximum length run counts have a uniquely decodeable prefix.

112. 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.

113. The system defined in claim 112 wherein the context modeling mechanism comprises at least one context model providing contexts from one of the plurality of integrated circuits and at least one context model providing contexts from a second of the plurality of integrated circuits.

114. The system defined in claim 113 wherein said at least one context model on said one of the plurality of integrated circuits comprises a zero order context model.

115. The system defined in claim 112 wherein the contexts from the plurality of integrated circuits are provided directly to the memory.

116. The system defined in claim 112 wherein a first portion of a first context is provided by one of the plurality of integrated circuits and a second portion of the first context is provided by a second of the plurality of integrated circuits.

117. 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.

118. The system defined in claim 117 wherein each of the plurality of decoders receive variable length data.

119. The system defined in claim 118 wherein the plurality of decoders decode variable length input data in parallel.

120. The system defined in claim 117 wherein output of the plurality of decoders is divided into fixed length interleaved words.