Method and system for high order conditional entropy coding

• US 5,298,896 A
• Filed: 03/15/1993
• Issued: 03/29/1994
• Est. Priority Date: 03/15/1993
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Lei, Shaw-Min, Sun, Ming-Ting, Tzou, Kou-Hu
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/031,421
• Time in Patent Office: 379 Days
• Field of Search: 341/51, 341/79, 341/106, 341/107, 358/133
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

Method and system for high order conditional entropy coding utilizing an incremental-tree-extension technique to design a conditional tree for the coding. For complexity reduction, code table reduction and non-uniform quantization of conditioning symbols or pixels is provided. A pattern matching technique is provided for fast conditioning state extraction, and a multistage pipelined structure is provided to handle the case of a large number of conditioning pixels. Using the complexity reduction techniques and the hardware structures, it is possible to implement practical high order conditional entropy codecs using current low-cost VLSI (Very Large Scale Integration) technology.

Claims

1. A method for compressing data in a data transmission system, the method comprising the steps of:

generating a reduced number of code tables containing statistical information for translating between first and second sets of data, the first set of data representing source symbols and the second set of data representing corresponding coded bit streams;

temporarily storing the source symbols to obtain a current symbol and its conditional symbols;

generating a reduced number of conditioning states for the source symbols;

non-uniformly quantizing the conditioning symbols to obtain quantized conditioning symbols;

extracting a conditioning state from the reduced number of conditioning states based on the quantized conditioning symbols;

selecting a code table from the reduced number of code tables based on the extracted conditioning state;

determining a code from the selected code table for the current symbol; and

encoding the current symbol based on the determined code to obtain a coded bit stream.

2. The method of claim 1 wherein the step of extracting includes the step of performing a multistage, parallel pattern matching algorithm to extract the conditioning state.

3. The method as claimed in claim 1 wherein the step of generating a reduced number of conditioning states includes the steps of generating a plurality of conditioning states by an incremental tree extension algorithm and reducing the number of conditioning states to obtain the reduced number of conditioning states.

4. The method of claim 1 wherein the symbols are pixels.

5. A system for compressing data in a data transmission system, the system comprising:

means for storing a reduced number of code tables containing statistical information for translating between first and second sets of data, the first set of data representing source symbols and the second set of data representing corresponding coded bit streams;

means for temporarily storing the source symbols to obtain a current symbol and its conditional symbols;

means for storing a reduced number of conditioning states for the source symbols;

means for non-uniformly quantizing the conditioning symbols to obtain quantized conditioning symbols;

means for extracting a conditioning state from the reduced number of conditioning states based on the quantized conditioning symbols;

means for selecting a code table from the reduced number of code tables based on the extracted conditioning state;

means for determining a code from the selected code table for the current symbol; and

means for encoding the current symbol based on the determined code to obtain a coded bit stream.

6. The system of claim 5 wherein the means for extracting includes a multistage pipelined PLA for performing a multistage, parallel pattern matching algorithm to extract the conditioning state.

7. The system as claimed in claim 5 further comprising means for performing an incremental tree extension algorithm to obtain a plurality of conditioning states and means for reducing the number of conditioning states to obtain the reduced number of conditioning states.

8. The method of claim 5 wherein the symbols are pixels.

9. A method for decompressing data in a data transmission system, the method comprising the steps of:

generating a reduced number of code tables containing statistical information for translating between first and second sets of data, the first set of data representing source symbols and the second set of data representing corresponding coded bit streams;

temporarily storing the source symbols to obtain a current symbol and its conditional symbols;

generating a reduced number of conditioning states for the source symbols;

non-uniformly quantizing the conditioning symbols to obtain quantized conditioning symbols;

extracting a conditioning state from the reduced number of conditioning states based on the quantized conditioning symbols;

selecting a code table from the reduced number of code tables based on the extracted conditioning state;

determining a code from the selected code table for the current coded bit stream; and

decoding the current coded bit stream based on the determined code to obtain a decoded symbol.

10. The method of claim 9 wherein the step of extracting includes the step of performing a multistage, parallel pattern matching algorithm to extract the conditioning state.

11. The method as claimed in claim 9 wherein the step of generating a reduced number of conditioning states includes the steps of generating a plurality of conditioning states by an incremental tree extension algorithm and reducing the number of conditioning states to obtain the reduced number of conditioning states.

12. The method of claim 9 wherein the symbols are pixels.

13. A system for decompressing data in a data transmission system, the system comprising:

means for storing a reduced number of code tables containing statistical information for translating between first and second sets of data, the first set of data representing source symbols and the second set of data representing corresponding coded bit streams;

means for temporarily storing the source symbols to obtain a current symbol and its conditional symbols;

means for storing a reduced number of conditioning states for the source symbols;

means for non-uniformly quantizing the conditioning symbols to obtain quantized conditioning symbols;

means for extracting a conditioning state from the reduced number of conditioning states based on the quantized conditioning symbols;

means for selecting a code table from the reduced number of code tables based on the extracted conditioning state;

means for determining a code from the selected code table for the current coded bit stream; and

means for decoding the current coded bit stream based on the determined code to obtain a decoded symbol.

14. The system of claim 13 wherein the means for extracting includes a multistage pipelined PLA for performing a multistage, parallel pattern matching algorithm to extract the conditioning state.

15. The system as claimed in claim 13 further comprising means for performing an incremental tree extension algorithm to obtain a plurality of conditioning states and means for reducing the number of conditioning states to obtain the reduced number of conditioning states.

16. The system as claimed in claim 13 wherein the symbols are pixels.