Method and apparatus for parallel decoding and encoding of data

• US 5,381,145 A
• Filed: 02/10/1993
• Issued: 01/10/1995
• 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: Boliek, Matin, Allen, James D., Schwartz, Edward L.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/016,035
• Time in Patent Office: 699 Days
• Field of Search: 341/51, 341/63, 341/65, 341/67, 341/107, 358/426, 358/500, 358/261.1, 358/261.2, 358/261.3, 348/397
• US Class Current: 341/107
• 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

The present invention provides a method and apparatus for encoding and decoding data in parallel. The present invention provides a system for decompressing a data stream having multiple codewords. The system includes an input channel that receives the data stream. The system also includes a decoder which decodes each bit of the data stream, wherein at least two of the codewords in the data stream are decoded at the same time, such that the data stream is decoded in parallel.

Claims

1. A system for decompressing a data stream of a plurality of codewords comprising:

channel means for receiving the plurality of codeword of the data stream; and

decoding means coupled to said channel means for decoding each codeword in the data stream according to its context and a probability estimate, wherein codewords of different contexts in the data stream are decoded at the same time, such that the data stream is decoded in parallel.

2. The system as defined in claim 1 wherein the channel means comprises a plurality of channels of data.

5. The system as defined in claim 1 or 3 wherein the channel means provides at least two data streams in parallel.

6. The system as defined in claim 5 wherein the channel means comprises a single non-interleaved channel.

7. The system as defined in claim 5 wherein the channel means comprises a single interleaved channel.

8. The system as defined in claim 1 wherein the codewords in the data stream comprise image data, such that the decoding means decodes image data in parallel.

9. The system as defined in claim 1 further comprising encoding means for receiving a data stream and encoding the data stream into a plurality of codewords.

10. The system defined in claim 1 wherein the channel means and the decoding means operate in a pipelined manner.

3. A system for decompressing a data stream of a plurality of codewords comprising:

channel means for receiving the plurality of codewords of the data stream; and

decoding means coupled to said channel means or decoding each codeword in the data stream according to its context and a probability estimate, wherein codewords of different probability estimates in the data stream are decoded at the same time, such that the data stream is decoded in parallel.

4. The system defined in claim 3 wherein the channel means and the decoding means operate in a pipelined manner.

11. A system or decompressing a data stream of a plurality of codewords comprising:

a channel control mechanism coupled to receive the plurality of codewords of the data stream;

a plurality of decoders coupled to said channel control mechanism to receive and decode each codeword in the data stream according to its context, wherein codewords in the data stream of different contexts are decoded at the same time, such that decoded data bits from codewords of different contexts are output in parallel;

data storage coupled to the plurality of decoders to store the decoded data; and

modeling mechanism coupled to the data storage to select the decoded data from the data storage, such that the decoded data is output in its original order.

12. The system as defined in claim 11 wherein at least one of the plurality of decoders decodes data corresponding to a class of context bins.

13. A system for decompressing a data stream of a plurality of codewords comprising:

a channel control mechanism coupled to receive the plurality of codewords of the data stream;

a plurality of decoders coupled to said channel control mechanism to receive and decode each codeword in the data stream according to its probability class, wherein codewords in the data stream of different probability classed are decoded at the same time, such that decoded data bits from codewords of different probability classes are output in parallel;

data storage coupled to the plurality of decoders to store the decoded data; and

modeling mechanism coupled to the data storage to select the decoded data from the data storage, such that the decoded data is output in its original order.

14. A system for decompressing a data stream of a plurality of codewords coded according to a coding scheme, said system comprising:

channel control means for receiving the plurality of codewords of the data stream, wherein the channel control means includes means for partitioning the plurality of codewords into a plurality of parallel data streams based on one of a set of attributes of the coding scheme and means for supplying the plurality of parallel data streams;

plurality of bit-stream generators, each coupled to a distinct one of the plurality of parallel data streams, wherein each of the plurality of bit-stream generators decodes codewords of the plurality of parallel data streams and further wherein at least two of the plurality of bit-stream generators decode codewords at the same time, such that codewords in the data stream partitioned into different parallel data streams based on the coding scheme are decoded in parallel to produce decoded data;

modeling means coupled to the plurality of bit-stream generators for selecting the decoded data from the bit-stream generators to output the decoded data in a deterministic order.

15. The system defined in claim 14 wherein the channel control means, plurality of bit stream generators and the modeling means operate in a pipelined manner.

16. The system as defined in claim 14 further comprising a plurality of probability estimation mechanisms, each coupled to the modeling means and one of the plurality of bit-stream generators to provide probability estimates to the plurality of bit-stream generators, wherein each one of the plurality of bit stream generators is associated with at least one context bin distinct from context bins of bit stream generators other than said each one of the plurality of bit stream generators, such that codewords of different context bins are decoded in parallel according to the probability estimates received from the plurality of probability estimation mechanisms, wherein the modeling means selects each of the plurality of probability estimation mechanisms in the deterministic order to output the decoded data from the plurality of bit stream generators.

17. The system as defined in claim 14 further comprising a probability estimation mechanisms coupled to the modeling means and each of the plurality of bit-stream generators to provide probability estimates to the plurality of bit-stream generators, wherein each one of the plurality of bit stream generators is associated with at least one probability class distinct from probability classes of bit stream generators other than said each one of the plurality of bit stream generators, such that codewords of different probability classes are decoded in parallel according to the probability estimates received from the probability estimation mechanisms, wherein the modeling means selects the decoded data from the plurality of bit-stream generators by providing contexts in the deterministic order to the probability estimation mechanisms, such that the probability estimation mechanisms selects decoded data from the plurality of bit stream generators.

18. The system as defined in claim 14 wherein the channel control means comprises:

a memory means for storing the data stream; and

at least one channel coupled to the memory means and the plurality of bit-stream generators for providing a data streams corresponding to at least one distinct context bin to each of the plurality of bit stream generators.

19. The system as defined in claim 14 wherein the channel control means comprises:

a memory means for storing the data stream; and

at least one channel coupled to the memory means and the plurality of bit-stream generators for providing a data streams corresponding to at least one probability class to each of the plurality of bit stream generators.

20. The system as defined in claim 14 wherein the channel control means comprises:

a memory means for receiving the data stream;

a plurality of channels, each coupled to one of the plurality of bit stream generators, each for carrying data to said one of the plurality of bit stream generatom; and

means for directing data in the data stream from the memory means to the plurality of channels.

21. The system as defined in claim 14 wherein the data stream comprises a plurality of code streams concatenated into a concatenated code stream and the channel control means includes means to direct the proper portion of the concatenated code stream to the proper one of the plurality of bit-stream generators.

22. The system as defined in claim 21 wherein the concatenated code stream includes the data for each context bin and a plurality of pointers to indicate the location of the data for each context bin in the concatenated code stream.

23. The system as defined in claim 21 wherein the concatenated code stream includes the data for each probability class and a plurality of pointers to indicate the location of the data for each probability class in the concatenated code stream.

24. The system as defined in claim 14 wherein the channel control means includes means for directing the codewords in the data stream to the proper bit stream generation means.

25. The system as defined in claim 14 wherein the channel control means includes a FIFO.

26. The system as defined in claim 14 wherein the channel control means comprises:

a memory means for receiving the data stream and outputting the data stream in a predetermined order;

a plurality of register means coupled serially to the data stream from the memory means and each coupled to one of the plurality of bit-stream generators for supplying at least one codeword of the data stream to its associated one of the plurality of bit-stream generators, wherein the data stream is ordered, such that as codewords are used by at least two bit-stream generators, multiple request for data can be made and data is shifted between the plurality of registers, wherein after each access all of the registers contain data.

27. The system as defined in claim 26 wherein the memory means comprises a FIFO.

28. The system as defined in claim 26 wherein each of the register means comprises a FIFO.

29. The system as defined in claim 14 further comprising an arbitration means coupled to the plurality of bit stream generators for arbitrating access to the memory means when at least two of the plurality of bit stream generators request data from memory at the same time.

30. The system as defined in claim 14 wherein the plurality of bit stream generators use at least one Rx(k) code, where x and k are integers.

31. The system as defined in claim 14 wherein the plurality of bit stream generators use R2(k) and Rn(k) codes, where n is an integer other than the integer 2.

32. The system as defined in claim 31 wherein n is 3, such that the plurality of bit-stream generators use R2(k) and R3(k) codes.

33. The system as defined in claim 14 wherein the plurality of bit stream generators use variable length to variable length codes.

34. The system as defined in claim 14 wherein the plurality of bit stream generators decoded probability classes in parallel using cascaded codes.

35. The system as defined in claim 14 wherein at least one of the codes comprises the code wherein data input is decoded (→

) according to

space="preserve" listing-type="tabular">______________________________________ 0000 →

0 0001 →

1000 0010 →

1001 0011 →

11111 010 →

101 011 →

11101 100 →

110 101 →

11110 11 →

11100 ______________________________________ for one of the probability classes.

36. The system as defined in claim 14 wherein each of the plurality of bit stream generation means use a binary arithmetic coder.

37. A method for decompressing a data stream of a plurality of codewords comprising the steps of:

producing decoded results using a plurality of bit stream generators in response to data in a plurality of data streams supplied from the data stream, wherein each of the plurality of data streams corresponds to a particular context bin, and further wherein at least two of the decoded results are produced as the same time, such that decoded results are generated in parallel; and

selecting the decoded results singularly to output the decompressed data according to the deterministic order of the data, such that the data stream is decoded in parallel.

38. The method as defined in claim 37 wherein the step of selecting includes the step of outputting the decoded data in parallel.

39. A method for decompressing a data stream of a plurality of codewords comprising the steps of:

producing decoded results using a plurality of bit stream generators in response to data in a plurality of data streams supplied from the data stream, wherein each of the plurality of data streams corresponds to a particular probability class and further wherein at least two of the decoded results are produced as the same time, such that decoded results are generated in parallel; and

selecting the decoded results singularly to output the decompressed data according to the deterministic order of the data, such that the data stream is decoded in parallel.

40. A system for decoding a coded data stream of a plurality of bits comprising:

a memory coupled to receive and store the coded data stream;

a decoder coupled to the memory, wherein the decoder receives coded data from the memory and decodes the coded data;

a plurality of counters coupled to receive the decoded data from the decoder, wherein the plurality of counters generate decoded results, such that at least two of the plurality of counters have decoded results available at the same time;

a modeling mechanism coupled to receive the decoded results produced by the plurality of counters, wherein the modeling mechanism selects the plurality of counters singularly to obtain its decoded result to produce decompressed data.

41. A method for decompressing a data stream of a plurality of codewords comprising the steps of:

providing a plurality of data streams, wherein each of the plurality of channels supplies data corresponding to a particular context bin;

producing a decoded result in response to the data in the plurality of data streams using a plurality of bit-stream generators, wherein each one of the plurality of bit stream generators provides decoded results for a distinct context bin and wherein at least two of the plurality of bit-stream generators produce decoded results at the same time;

indicating the code to the plurality of bit stream generation means for decoding their individual data streams; and

selecting the plurality of probability estimation means singularly to receive the decoded results produced by its associated bit stream generator to produce decompressed data, such that the data stream is decoded in parallel.

42. A method for decompressing a data stream of a plurality of codewords comprising the steps of:

providing a plurality of data streams, wherein each of the plurality of channels supplies data corresponding to a particular probability class;

producing a decoded result in response to the data in the plurality of data streams using a plurality of bit-stream generators, wherein each one of the plurality of bit stream generators provides decoded results for a distinct probability class and wherein at least two of the plurality of bit-stream generators produce decoded results at the same time;

indicating the code to the plurality of bit stream generation means for decoding their individual data streams; and

selecting the plurality of probability estimation means singularly to receive the decoded results produced by its associated bit stream generator to produce decompressed data, such that the data stream is decoded in parallel.

43. A system for decoding a data stream of a plurality of bits coded according to a coding scheme employing contexts and probability estimates, said system comprising:

channel means for receiving the plurality of bits of the data stream;

decoding means coupled to the channel means for decoding portions of the plurality of bits in parallel, such that bits are decoded according to a coding-based partitioning, such that at least two streams of decoded data bits are generated; and

modeling means coupled to receive the decoded data bits from the decoding means, wherein the modeling means selects decoded data bits from the decoding means singularly, such that the modeling means selects its output from a plurality of decoded data bit streams.

44. The system as defined in claim 43 wherein each of said at least two streams corresponds to at least one context bin different from context bins of other streams of decoded data bits, such that bits corresponding to different context bins are decoded in parallel.

45. The system as defined in claim 44 wherein each of said at least two streams corresponds to at least one probability class different from probability classes of other streams of decoded data bits, such that bits corresponding to different probability classes are decoded in parallel.

46. A system for decoding a coded data stream of a plurality of bits comprising:

a memory coupled to receive and store the coded data stream;

a decoder coupled to the memory, wherein the decoder receives the coded data from the memory and decodes the coded data, such that the run length is determined and whether a least probable symbol is at the end of the run is determined;

a plurality of counters coupled to receive the run length and least probable symbol determination from the decoder, wherein the plurality of counters generates decoded results, such that at least two of the plurality of counters have decoded results available at the same time;

a modeling mechanism coupled to receive the decoded results produced by the plurality of counters, wherein the modeling mechanism selects the plurality of counters singularly to obtain its decoded result to produce decompressed data.

47. A system for decoding a coded data stream of a plurality of bits comprising:

memory means for receiving and storing the coded data stream;

decoding means coupled to the memory means for receiving coded data from the memory means and decoding the coded data;

a plurality of counter means coupled to receive the decoded data from the decoding means and for generating decoded results, such that at least two of the plurality of counter means have decoded results available at the same time;

modeling means coupled to receive the decoded results produced by the plurality of counter means, wherein the modeling means selects the plurality of counter means singularly to obtain its decoded result to produce decompressed data.

48. The system as defined in claim 47 wherein the coded data is received by the decoding means as the decoding means outputs decoded data to the plurality of counter means, such that the system operates in a pipelined manner.

49. A system for decoding a coded data stream of a plurality of bits comprising:

memory means for receiving and storing the coded data stream;

decoding means coupled to the memory means for receiving coded data from the memory means and decoding the coded data, such that the run length is determined and whether a least probable symbol is at the end of the run is determined;

a plurality of counters coupled to receive the run length and least probable symbol determination from the decoding means and for generating decoded results, such that at least two of the plurality of counters have decoded results available at the same time;

modeling means coupled to receive the decoded results produced by the plurality of counters, wherein the modeling means selects the plurality of counters singularly to obtain its decoded result to produce decompressed data.

50. A real-time video system for decompressing a data stream of a plurality of codewords comprising:

first decoding means coupled to receive the data stream for decoding each codeword in the data stream, wherein at least two of the codewords in the data stream are decoded at the same time according to a coding-based partitioning of the data stream, such that the data stream is decoded in parallel;

second decoder means or further decoding the decoded data stream to prepare the decoded data stream for display; and

display means for displaying the decoded data.

51. The system as defined in claim 50 wherein the display means comprises a television monitor.

52. The system as defined in claim 50 wherein the display means comprises a video monitor.

53. The system as defined in claim 50 wherein the second decoder means is a lossy decoder.

54. The system as defined in claim 53 wherein the lossy decoder comprises the transform portion of a decoder.

55. The system as defined in claim 53 wherein the lossy decoder comprises the color conversion portion of a decoder.

56. The system as defined in claim 53 wherein the lossy decoder comprises the subsampling portion of a decoder.

57. A system for encoding a data stream having a plurality of bits comprising:

a memory means for storing the data stream;

means coupled to the memory means for providing a plurality of data streams from the data stream, wherein each of the plurality of data streams includes data from the data stream corresponding to a particular context bin;

plurality of encoding means coupled to the means for providing a plurality of data streams, said plurality of encoding means for encoding the data, such that the data is encoded in parallel, wherein one of the plurality of encoding means is coupled to one of the plurality of data streams;

storage means coupled to received the encoded data from the plurality of encoding means; and

ordering means coupled to the storage means for accessing the storage means to produce an ordered coded stream.

58. The system as defined in claim 57 wherein the ordering means includes a decoder means for requesting the coded data, such that the order for the compressed data is ascertained.

59. The system as defined in claim 58 wherein the decoder means comprises:

a plurality of decoders coupled to the storage means for decoding data from the storage means;

modeling means for providing a context to the plurality of decoders, such that the plurality of decoders decode data in the order given by the modeling means.

60. The system as defined in claim 59 further comprising arbitration means for arbitrating the data requests from the plurality of decoders, such that each of the plurality of decoders receives data of the proper context bin.

61. The system as defined in claim 57 wherein the storage means comprises a plurality of bit pack buffers.

62. The system as defined in claim 57 wherein the ordering means includes means for appending the encoded data from the storage means into a sequence of data.

63. A system for encoding a data stream having a plurality of bits comprising:

a memory means for storing the data stream;

means coupled to the memory means for providing a plurality of data streams from the data stream, wherein each of the plurality of data streams includes data from the data stream corresponding to a particular probability class;

plurality of encoding means coupled to the means for providing a plurality of data streams, said plurality of encoding means for encoding the data, such that the data is encoded in parallel, wherein one of the plurality of encoding means is coupled to one of the plurality of data streams;

storage means coupled to received the encoded data from the plurality of encoding means; and

ordering means coupled to the storage means for accessing the storage means to produce an ordered coded stream.

64. The system as defined in claim 63 wherein the ordering means includes a decoder means for requesting the coded data, such that the order for the compressed data is ascertained.

65. The system as defined in claim 64 wherein the decoder means comprises:

a plurality of decoders coupled to the storage means for decoding data from the storage means;

modeling means for providing a context to the plurality of decoders, such that the plurality of decoders decode data in the order given by the modeling means.

66. The coder as defined in claim 64 wherein the state table comprises a symmetrical state table, such that only the positive or negative states of the table are stored.

67. The system as defined in claim 63 wherein the ordering means includes means for appending the encoded data from the storage means into a sequence of data.

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

a bit stream generator coupled to receive the data stream; and

a probability estimation mechanism coupled to the bit stream generator, wherein the probability estimation mechanism provides probability estimates to the bit stream generator,

wherein the bit stream generator generates decoded results for each codeword in the data stream in response to probability estimates from the probability estimation mechanism, wherein the bit stream generator provides decoded results using at least a first Rn(k) code and a second Rn(k) code having a value of n different than the first Rn(k) code.

69. The coder as defined in claim 68 wherein the probability estimation mechanism a state machine having positive and negative states.

70. The coder as defined in claim 68 wherein the probability estimation mechanism comprises a state machine.

71. The coder as defined in claim 70 wherein the state machine includes at least two states having the same Rn(k) code.

72. The coder as defined in claim 70 wherein the state machine includes a plurality of states, and wherein each of the plurality of states is associated with an Rn(k) code, and further wherein at least two of the plurality of states in the state machine are adjacent and associated with the same Rn(k) code, such that bit-stream generator uses the same Rn(k) codes to provide decoded results when transitioning between each of said at least two of the plurality of states.

73. The coder as defined in claim 68 wherein the bit stream generator uses R2(k) and Rn(k) codes, where n is an integer other than 2.

74. The coder as defined in claim 73 wherein n is 3, such that bit-stream generator uses R2(k) and R3(k) codes.

75. An entropy decoder or decoding a data stream of a plurality of codewords comprising:

a bit stream generator coupled to receive the data stream; and

a state table coupled to the bit stream generator, wherein the state table provides a probability estimate to the bit stream generator, wherein the state table includes a plurality of states, each of which is associated with a code, and further wherein at least two of the plurality of states include the same code, such the bit stream generator generates a decoded result for each codeword in the data stream in response to the probability estimate from the state table using a Rn(k) codes, where n and k are integers.

76. A system for decoding a compressed data stream of a plurality of bits comprising:

decoder means for decoding the data stream, wherein a run length and an indication of whether the Least Probable Symbol (LPS) occurred in response to the plurality of bits is generated, wherein the decoder means includes a state table having a plurality of states, each of which is associated with a code, and further wherein at least two states associated with the same code, such upon transitioning between said at least two, the decoder means uses the same code; and

counter means coupled to decoder means for outputting decoded data in response to the LPs and run length.

77. The system as defined in claim 76 wherein the codes comprise R2(k) and Rn(k) codes, where n is an integer.

78. The system as defined in claim 77 wherein n is 3, such that the codes comprise R2(k) and R3(k) codes.

79. The system as defined in claim 76 wherein the decoder means comprises:

run length decoding means coupled to receive the data stream as codewords, wherein the run length decoding means determining the codeword type;

probability estimation means coupled to the run length decoding means, wherein the probability estimation means determines the code for the run length decoding means, such that the run length decoding means generates the run length and an indication of whether the LPS occurred in response to each codeword and the code.

80. The system as defined in claim 79 further comprising shifting means for receiving the data stream and outputting properly aligned coded data to the run-length decoding means.

81. The system as defined in claim 80 wherein the shifting means provides coded data to the run-length decoding means in response to a signal from the probability estimation means indicating the length of the previous codeword.

82. The system as defined in claim 76 wherein the counter means includes means to indicate to the decoding means when the next codeword is to be processed.

83. A system for decompressing a data stream of a plurality of codewords comprising:

channel means for supplying the plurality of codewords of the data stream; and

decoding means coupled to said channel means for decoding each codeword in the data stream, wherein the decoding means includes a plurality of decoders for decoding the data stream according to probability classes using codes, wherein the plurality of decoders are coupled in a cascaded manner, each having an input of the previous one of the cascaded coders and a data input corresponding to a probability class, and further wherein each of the plurality of coders outputs a code stream at a probability different than the probability of the data input, such that the data stream is decoded by receiving data at an input in the cascaded chain of coders and having the data propagate through the remainder of the cascaded chain to produce decoded data.

84. The system as defined in claim 83 wherein at least one of the codes comprises the code wherein data input is decoded (→

) according to

space="preserve" listing-type="tabular">______________________________________ 0000 →

0 0001 →

1000 0010 →

1001 0011 →

11111 010 →

101 011 →

11101 100 →

110 101 →

11110 11 →

11100 ______________________________________

for one of the probability classes.