Apparatus for variable-length coding and variable-length-decoding using a plurality of Huffman coding tables

• US 5,528,628 A
• Filed: 01/31/1995
• Issued: 06/18/1996
• Est. Priority Date: 11/26/1994
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jeong, Jechang, Jeon, Byeung-woo, Park, Ju-ha
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): GLUCK, JEFFREY WILLIAM
• Application Number:
  US08/381,494
• Time in Patent Office: 504 Days
• Field of Search: 375/240, 375/253, 348/390, 348/420, 358/427, 358/430, 370/118
• US Class Current: 375/240
• 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/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An apparatus for variable-length-coding input symbols using a plurality of variable-length-code tables includes N variable-length-code tables each having a symbol-codeword association different from the others according to statistics regarding the symbols and a variable-length-coding device for coding the input symbols according to each of the variable-length-code tables for every block in a predetermined block data unit, for generating codewords, and for providing both table information representing each of the variable-length-code tables utilized in generating the respective codewords and a control signal indicating that variable-length-coding to a predetermined block data unit has been completed. The apparatus also includes buffers which store the codewords generated by the variable-length-coding device, an optimum table determining device receiving the output codewords for controlling the buffer so as to output codewords with a minimum amount of data for the block data unit, for supplying the table information from the variable-length-coding device and for providing table selection information representing a variable-length-code table producing the minimum amount of data for an input block data unit. The apparatus further includes a first switching circuit which receives table selection information and codewords and respectively outputs data in response to the output control signal. The apparatus advantageously can improve data compression efficiency. A complementary decoder, which can be used in building a communication system, is also described.

Claims

1. An apparatus for variable-length-coding input symbols representing a data block using a plurality of variable-length-code tables, the apparatus comprising:

N variable-length-code tables each having a respective symbol-codeword association different from one another according to associated statistics of said symbols;

N variable-length coders, respectively connected to one of said N variable-length-code tables, for variable-length-coding said symbols having a predetermined block data unit using a corresponding one of said N variable-length-code tables, thereby generating a plurality of codewords;

N buffers, respectively connected to an output terminal of one of said N variable-length coders, for storing corresponding said codewords generated by said one of said N variable-length coders;

optimum table determining means for outputting table information representing the respective one of said N variable-length code tables producing a minimum amount of data for said block data unit on the basis of an amount of respective data of the codewords generated by each of said N variable-length coders; and

means for outputting respective said codewords stored in a respective one of said buffers, in response to the table information generated by said optimum table determining means.

2. The variable-length-coding apparatus as claimed in claim 1, wherein said optimum table determining means comprises:

a plurality of counters, each of said counters connected to a respective output terminal of one of said N variable-length coders, for counting a number of bits of all respective codewords obtained by variable-length-coding said symbols of said data block, and for outputting a respective counted value, corresponding to one of said N variable-length coders; and

a comparator for comparing the generated counted values output by said counters and for outputting table selection information corresponding to a minimum counted value.

3. The variable-length coding apparatus as claimed in claim 1, wherein said N variable-length code tables include Huffman codes.

4. An apparatus for variable-length-coding input symbols representing a data block using a plurality of variable-length-code tables, the apparatus comprising:

N variable-length-code tables each having a respective symbol-codeword association different from one another according to associated statistics of said symbols, wherein each of said N variable-length code tables includes Huffman codes;

variable-length-coding means for variable-length-coding said symbols according to respective ones of said N variable-length-code tables for every data block having a predetermined block data unit, for generating codewords, and for producing both table information representing each of said N variable-length-code tables utilized in generating respective codewords and a control signal indicating that variable-length-coding of said block data unit has been completed;

buffers for storing respective codewords generated by said variable-length-coding means;

optimum table determining means receiving respective codewords from said variable-length-coding means for controlling said buffers so as to output respective said codewords with a minimum amount of data representing said block data unit, and for supplying table information from said variable-length-coding means and outputting table selection information representing a selected one of said N variable-length-code tables with a minimum amount of data for said block data unit; and

first switching means for receiving and outputting said table selection information from said optimum table determining means and respective codewords output from said buffers in response to said control signal.

5. The variable-length-coding apparatus as claimed in claim 4, wherein said variable-length-coding means generates a plurality of codeword sets with respect to the data block, using a respective plurality of variable-length-code tables.

6. The variable-length-coding apparatus as claimed in claim 4, wherein said variable-length-coding means comprises:

second switching means for selecting said N of variable-length-code tables seriatim and for outputting a table switching signal in accordance with the selected variable-length-code table;

a switching controller, receiving said table switching signal, for generating an output control signal when variable-length-coding is completed with respect to all of said N variable-length-code tables utilized in variable-length-coding said block data unit; and

a variable-length coder storing said symbols in predetermined block data unit, for variable-length coding said symbols with the respective one of said N variable-length-code tables selected through said second switching means, and for generating respective said codewords.

7. The variable-length-coding apparatus as claimed in claim 4, wherein said buffers comprise:

a first buffer for storing respective first codewords output from said variable-length-coding means;

a second buffer for storing respective second codewords output from said first buffer; and

a first switch for supplying said first codewords from said first buffer to said second buffer, thereby storing said second codewords.

8. The variable-length-coding apparatus as claimed in claim 7, wherein said first buffer has a data storage capacity for storing at most said first codewords and said second buffer has a data storage capacity for storing at most said second codewords, wherein each of said first and second codewords is generated by one of said N variable-length-code tables.

9. The variable-length-coding apparatus as claimed in claim 7, wherein said optimum table determining means comprises:

a counter for counting a number of bits of the respective codewords generated by each of said N variable-length-coding tables and for producing respective counted values;

a register for storing a previously counted one of said counted values output from said counter as a previous counted value;

a second switch, located between said counter and said register, for supplying a respective one of said counted values from said counter to said register;

a table information storing unit for storing table information output from said variable-length-coding means;

a third switch for supplying the table information from said variable-length-coding means to said table information storing unit; and

a comparator, receiving the respective one of said counted values output from said counter and said previous counted value from said register, for comparing the respective two counted values, and for controlling operation of said first, said second and said third switches,

wherein said register initially stores an initial count value generated by said counter, and

wherein said comparator switches said first, said second and said third switches "on" when the respective one of said counted values produced by said counter is less than said previous counted value of said register.

10. The variable-length-coding apparatus as claimed in claim 9, wherein said first switching means comprises:

a fourth switch for receiving the respective codewords output from said second buffer; and

a fifth switch for receiving table selection information output from said table information storing unit, and

wherein said first switching means outputs data supplied from said second buffer and said table information storing unit in response to said output control signal.

11. A communication system comprising:

means for generating a plurality of output codewords and corresponding table selection information from a plurality of input symbols representing a data block, said generating means further comprising;

N variable-length-code tables each having a symbol-codeword association different from all other of said tables according to statistics of said symbols;

N variable-length coders, respectively connected to one of said N variable-length-code tables, for variable-length-coding said symbols in a predetermined block data unit using a corresponding one of said N variable-length-code tables and for generating the respective codewords;

N buffers, respectively connected to output terminals of each of said variable-length coders, for storing said respective codewords generated by respective ones of said N variable-length coders;

optimum table determining means for generating said table selection information representing one of said N variable-length code tables producing a minimum amount of data corresponding to said block data unit based on an amount of each data of the respective codewords generated by each associated one of said variable-length coders; and

means for providing respective codewords stored in a selected one of said buffers as said output codewords in response to said table selection information generated by said optimum table determining means;

means serially connected to said generating means for transmitting said output codewords and said table selection information; and

means serially connected to said transmitting means for decoding said output codewords responsive to said table selection information, said decoding means further comprising;

variable-length decoding means for decoding said output codewords using a selected one of M variable-length-code tables;

means for storing said M variable-length-decode tables corresponding to said N variable-length-code tables; and

means receiving said table selection information for selecting and supplying said selected one of said M variable-length-decode tables to said variable-length-decoding means.

12. A communication system comprising:

means for generating a plurality of output codewords and corresponding table selection information from a plurality of input symbols representing a data block, said generating means further comprising;

N variable-length-code tables having symbol-codeword association different from each other according to statistics of the symbols;

variable-length-coding means for variable-length-coding said symbols according to all of said variable-length-code tables for every block in a predetermined block data unit, for generating codewords, and for producing both table information representing each of said variable-length-code tables utilized in generating respective said codewords and a control signal indicating that completion of variable-length-coding of said block data unit;

a plurality of buffers for storing selected codewords generated by said variable-length-coding means;

optimum table determining means for receiving said codewords from said variable-length-coding means and controlling said buffers so as to generate said output codewords having a minimum amount of data for said block data unit for supplying table information from said variable-length-coding means as table selection information representing a respective one of said variable-length-code tables producing said minimum amount of data for said block data unit; and

switching means for receiving said table selection information from said optimum table determining means and respective output codewords from a serially connected one of said buffers;

means serially connected to said generating means for transmitting said output codewords and said table selection information; and

means serially connected to said transmitting means for decoding said output codewords responsive to said table selection information, said decoding means further comprising;

variable-length decoding means for decoding said output codewords using a selected one of M variable-length-code tables;

means for storing said M variable-length-decode tables corresponding to said N variable-length-code tables; and

means receiving said table selection information for selecting and supplying said selected one of said M variable-length-decode tables to said variable-length-decoding means.

13. A decoder, comprising:

receiving means for receiving codewords generated by a variable-length coder using one of N variable-length-code tables and table selection information corresponding to said one of said N variable-length-code tables, said codewords each having a minimum amount of data among a plurality of codewords generated based on said N variable-length code tables; and

decoding means for decoding said codewords responsive to said table selection information, said decoding means further comprising;

variable-length decoding means for decoding said codewords using a selected one of M variable-length-decode tables;

means for storing said M variable-length-decode tables corresponding to said N variable-length-code tables; and

means for selecting and supplying said selected one of said M variable-length-decode tables to said variable-length-decoding means, based on said table selection information.