Method and apparatus for parallel encoding and decoding of data

• US 5,583,500 A
• Filed: 12/23/1993
• Issued: 12/10/1996
• 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: Allen, James D., Gormish, Michael, Schwartz, Edward L., Boliek, Martin
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/172,646
• Time in Patent Office: 1,083 Days
• Field of Search: 341/51, 341/60, 341/63, 341/65, 341/67, 341/107
• 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 method for decoding a data stream of a plurality of codewords comprising the steps of:

assigning portions of the data stream to a plurality of decoding resources;

entropy decoding the portions of the data stream in parallel using the plurality of decoding resources and a decoding scheme employing contexts and probabilities, wherein the step of entropy decoding comprises the steps of

at least one of the plurality of decoding resources determining a context in one stage of a decoding pipeline,

said at least one of the plurality of decoding resources reading a decoder state from memory in a first next stage of the decoding pipeline immediately following said one stage of the decoding pipeline, and

said at least one of the plurality of decoding resources generating at least one decoded bit in a second next stage of the decoding pipeline immediately following said first next stage, such that said at least one of the plurality of decoding resources decodes its corresponding portion of the data stream during successive cycles in a pipelined manner.

2. The method defined in claim 1 wherein said decoder state comprises a probability state and a bit generation state.

3. The method defined in claim 1 further comprising the step of ordering the data stream into an ordered data stream.

4. The method defined in claim 3 wherein said step of assigning includes assigning the portions according to the order of the data stream.

5. The method defined in claim 1 wherein the plurality of decoding resources includes a plurality of QM-coders.

6. The method defined in claim 1 wherein the plurality of decoding resources includes a plurality of lossy decoders.

7. A method for decoding a data stream of a plurality of codewords comprising the steps of:

assigning portions of the data stream to a plurality of decoding resources;

entropy decoding the portions of the data stream in parallel using the plurality of decoding resources and a decoding scheme employing contexts and probabilities, wherein at least one of the plurality of decoding resources decodes its corresponding portion of the data stream during successive cycles in a pipelined manner and includes a first type of decoder and a second type of decoder, wherein the first type of decoder is different that the second type of decoder.

8. The method defined in claim 7 wherein the first type of decoder comprises a run-length coder and the second type of decoder comprises a Q-coder.

9. The method defined in claim 7 wherein the first type of decoder comprises a binary coder and the second type of coder comprises a non-binary decoder.

10. The method defined in claim 7 wherein the first type of decoder comprises a lossless decoder and the second type of decoder comprises a lossy decoder.

11. A method for decoding a data stream of a plurality of codewords comprising the steps of:

determining a current context bin in one pipestage in a decoding pipeline;

fetching a decoder state for the context bin from memory in a first next pipestage immediately after the one pipestage in the decoding pipeline; and

processing one of the codewords beginning in a second next pipestage immediately after the first next pipestage in the decoding pipeline, including the step of decoding said one of the codewords, wherein the steps of determining, fetching and processing occur in successive cycles in a pipelined manner.

12. The method defined in claim 11 further comprising the step of shifting the data stream to a codeword following said one of the codewords.

13. The method defined in claim 11 wherein the step of fetching the decoder state includes the steps of:

fetching a PEM state; and

fetching a bit generation state.

14. The method defined in claim 11 wherein the step of processing includes the steps of:

generating a decoded bit; and

decoding said one of the codewords, such that the decoded bit is generated prior to the decoding of said one of the codewords.

15. The method defined in claim 14 wherein the steps of generating and decoding occur in successive cycles.

16. The method defined in claim 11 further comprising the step of decoding a PEM state to determine a code for decoding said one of the plurality of codewords.

17. The method defined in claim 11 further comprising the step of updating a PEM state to produce an updated PEM state after said one of the plurality of codewords has been decoded.

18. The method defined in claim 17 wherein the step of updating and the step of decoding occur in the same cycle.

19. The method defined in claim 17 further comprising the step of writing the updated PEM state to memory.

20. A method for decoding a data stream of a plurality of codewords comprising the steps of:

determining a current context bin for one of said plurality of codewords in a first stage of a decoding pipeline;

fetching a probability estimate machine (PEM) state for the current context bin in a second stage of a decoding pipeline immediately following the first stage;

fetching a bit generator state for the current context bin in a second stage of a decoding pipeline immediately following the first stage;

generating a decoded bit representing a first bit of said one of the plurality of codewords being decoded in a third stage of a decoding pipeline immediately following the second stage;

decoding the PEM state to determine a code for decoding said one of the plurality of codewords; and

decoding said one of the plurality of codewords using the code.

21. The method defined in claim 20 wherein the steps of generating a decoded bit and decoding said one of the plurality of codewords occur in two consecutive cycles in a pipelined manner.

22. The method defined in claim 20 wherein the steps of generating a bit and decoding the PEM state occur in successive cycles in a pipelined manner.

23. The method defined in claim 20 further comprising the step of reusing said current context bin for the codeword immediately following said one of the plurality of codewords, wherein requirements to access external memory to obtain the context information is obviated.

24. A system for decompressing a data stream having a plurality of codewords, said system comprising:

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

decoder means coupled to said channel means, for entropy decoding codewords in parallel based on contexts and probabilities, wherein the plurality of codewords are decoded in a decoding pipeline in a pipelined manner, wherein the decoding pipeline comprises

a first stage to determine a context,

a second stage immediately following the first stage to read a decoder state from memory, and

a third stage immediately following the second stage to generate at least one decoded bit, such that decoding pipeline decodes its corresponding portion of the data stream during successive cycles in a pipelined manner.

25. The system defined in claim 24 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.

26. The system defined in claim 24 wherein said decoder means includes a plurality of decoders.

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

channel control means for receiving the plurality of codewords of the data stream and partitioning the plurality of codewords into a plurality of data streams based on contexts and probabilities;

a plurality of bit stream generators, each coupled to receive a distinct one of the plurality of data streams from the channel control means, wherein each of the plurality of bit stream generators decodes each of the codewords using at least one non-binary code, and further wherein at least two of the plurality of bit stream generators decodes codewords at the same time, such that the data stream is decoded in parallel to produce decoded data; and

modeling means coupled to the plurality of bit stream generators for selecting the decoded data from the plurality of bit stream generators to output the decoded data.

28. The system defined in claim 27 wherein the said at least one non-binary code comprises a Tunstall code.

29. The system defined in claim 27 wherein the plurality of bit stream generators uses a plurality of non-binary codes.

30. A system for decompressing a data stream having a plurality of codewords, said system comprising:

channel means for receiving the plurality of codewords;

a plurality of bit generators coupled to the channel means, wherein the plurality of generators comprises a plurality of Huffman decoders and receives the plurality of codewords from the channel means as a continuous stream and entropy decodes the plurality of codewords into a decoded data stream in parallel using contexts and probabilities, wherein at least two of the plurality of bit generators decode codewords in parallel; and

control means coupled to the plurality of bit generators for controlling the plurality of bit generators to receive individual and successive codewords from the channel means for decoding in parallel.

31. The system defined in claim 30 wherein each of the plurality of bit generators decodes every n^th codeword in the data stream, where n comprises the number of the plurality of bit stream generators.

32. The system defined in claim 30 wherein the control means includes a state machine.

33. The system defined in claim 30 wherein the channel means includes a buffer, wherein the control means provides data to each of the plurality of Huffman decoders in order, such that each Huffman decoder receives every nth token where n is the number of Huffman decoders.

34. The system defined in claim 33 wherein the codewords are delivered to the plurality of Huffman decoders and the tokens are decoded in the same sequential order used during encoding.

35. The system defined in claim 33 wherein the plurality of Huffman decoders perform decoding according to the JPEG standard, except for the interleaved order of the codewords.

36. The system defined in claim 33 wherein the plurality of Huffman decoders perform decoding according to the MPEG standard, except for the interleaved order of the codewords.

37. The system defined in claim 33 wherein at least one of the plurality of Huffman decoders decodes data using one of plurality of available Huffman codes, wherein each of the plurality of available Huffman codes is selected based on the probability of the current values.

38. The system defined in claim 33 wherein the control means includes a state machine.

39. The system defined in claim 33 further comprising a QM-coder for determining binary decision outcomes, wherein the plurality of Huffman decoders specify coefficient values in response to the outcomes.

40. The system defined in claim 30 wherein at least one of the plurality of Huffman decoders switches the corresponding codeword for a particular symbol based on the adaptive probability of the symbol.

41. The system defined in claim 30 wherein the control means includes a context model.

42. The system defined in claim 30 further comprising at least one JPEG QM-coder.

43. A method for forming a composite code stream from a plurality of code streams, wherein each of the plurality of code streams includes a plurality of codewords, said method comprising the steps of:

packing codewords in each of the plurality of code streams into fixed-length segments;

interleaving the codewords from the plurality of code streams according to an assigned sequence of the codewords in the fixed-length segments, such that the composite code stream includes the plurality of codewords in the plurality of code streams.

44. The method defined in claim 43 wherein the step of interleaving includes interleaving by adding a fixed-length segment to the composite code stream having the codeword nearest to the beginning of the composite code stream.

45. The method defined in claim 43 further comprising the step of assigning an order to codewords in the plurality of code streams according to the modeling order.

46. The method defined in claim 43 wherein one of the plurality of code streams includes audio data and another of the plurality of code streams includes video data, such that the composite code stream includes audio data and video data interleaved.

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

a buffer to supply codewords from the code stream;

a context model to provide contexts;

a memory located on an integrated circuit and coupled to the context model to store state information, wherein the memory provides state information in response to each context provided by the context model;

a plurality of decoders located on the integrated circuit and coupled to the buffer and the memory to decode codewords supplied by the buffer using state information from the memory, wherein two of the plurality of decoders decode codewords in parallel, such that the plurality of decoders decodes the code stream,

wherein the buffer, context model, memory and plurality of decoders operate to determine contexts, estimate probabilities, decode codewords and generate bits from run counts in a pipelined manner.

48. The system defined in claim 47 wherein the memory stores information for commonly used contexts.

49. The system defined in claim 47 wherein the memory stores the least significant portion of larger run counts and accesses external memory at the end of the run.

50. The system defined in claim 47 wherein the memory stores state information for a portion of bit generators and uses external memory for the remaining state information.

51. The system defined in claim 47 wherein said memory includes at least two banks of memory, wherein each of said two banks of memory stores state information for separate sets of context bins, and further wherein said at least two banks of memory are accessed in alternate cycles.

52. A method for performing JPEG decompression on an image data stream of a plurality of codewords comprising the steps of:

assigning portions of the data stream to a plurality of decoding resources;

entropy decoding the portions of the data stream using the plurality of decoding resources operating in parallel on separate codewords, wherein at least two of the plurality of decoding resources comprise R-coders and portions of the data stream are decoded using a lossless binary entropy coder.

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

encoding with a finite amount of buffer memory; and

signaling between an encoder and a decoder to indicate that a memory limit has been reached.

54. The method defined in claim 53 wherein the encoder generates an output in response to said signalling indicating that the memory limit has been reached.

55. The method defined in claim 53 wherein the step of signaling includes adding non-maximum length runs of most probable symbols that are not followed by a least probable symbol.

56. The method defined in claim 53 wherein the step of signaling comprises the steps of:

timestamping the codewords in the data stream;

buffering the codewords after timestamping; and

completing the codeword with the lowest time stamp until the memory limit is no longer reached.

57. The method defined in claim 53 wherein the step of signaling includes the step of providing status of the memory to the decoder using a separate context bin, and wherein the context bin is decoded for every codeword to indicate whether or not the codeword was due to a buffer overflow.

58. An encoder comprising:

a sequencer for receiving a data stream of a plurality of codewords;

a plurality of coders coupled to the sequencer for entropy encoding the plurality of codewords using contexts and probabilities;

buffer means coupled to the plurality of coders or buffering the encoded codewords;

interleaving mechanism for requesting the encoded data from the buffer means to produce an output stream of interleaved encoded data;

decoder coupled to the interleaving mechanism for modeling the order for encoding the data, wherein the decoder operates in a pipelined manner using contexts and probabilities.

59. The encoder defined in claim 58 further comprising means for indicating when the buffer means overflows.

60. The encoder defined in claim 59 wherein the means for indicating includes at least one predetermined codeword.

61. An encoder comprising:

a sequencer for receiving a data stream of a plurality of codewords;

a plurality of coders coupled to the sequencer for encoding the plurality of codewords;

buffer means coupled to the plurality of coders for buffering the encoded codewords;

interleaving mechanism for requesting the encoded data from the buffer means to produce an output stream of interleaved encoded data, wherein interleaving mechanism includes means for outputting data that is not fully encoded when the memory limit for the buffer means has been reached.

62. The encoder defined in claim 61 further comprising means for adding non-maximum length runs of most probable symbols that are not followed by a least probable symbol.

63. The encoder defined in claim 61 further comprising:

means for timestamping the codewords in the data stream;

means coupled to the timestamping means for buffering the codewords after timestamping; and

means for completing the codeword with the lowest time stamp until the memory limit is no longer reached.

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

first plurality of entropy decoding resources coupled to receive the data stream for decoding each codeword in the data stream, wherein at least two of the first plurality of decoding resources operate to decode separate codewords at the same time such that the data stream is decoded in parallel;

formatting means for formatting the decoded data stream to prepare the decoded data stream for display; and

display means for displaying the decoded data.

65. The system as defined in claim 64 wherein the display means comprises a television monitor.

66. The system as defined in claim 64 wherein the display means comprises a video monitor.

67. The system as defined in claim 64 wherein one of the first plurality of decoding resources comprises second decoder means for lossy decoding codewords in the data stream.

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

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

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