Entropy encoding with a reduced memory size of code table

• US 5,673,043 A
• Filed: 12/27/1995
• Issued: 09/30/1997
• Est. Priority Date: 12/28/1994
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Sato, Yutaka, Hayashi, Nobutake, Ryu, Tadanori
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/579,296
• Time in Patent Office: 643 Days
• Field of Search: 341/106, 341/51, 341/107, 348/403, 348/404, 375/246
• US Class Current: 341/106
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• 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

Abstract

An entropy encoder includes: a memory for storing a code table in a compressed data format in which continuing digits "1" that continue successively from the most significant bit of a code word for a predetermined number of bits are removed, together with a control code indicative of the type of the original code word, and a code word restoring unit for restoring the original code word from the compressed code word by supplementing a predetermined number of digits "1" to the compressed code word according to the type of the original code word.

Claims

1. An entropy data encoding method, comprising the steps of:

compressing a code table containing original code words in terms of bits having first and second logic values, to produce a compressed code table, said step of compressing the code table comprising the substeps of;

detecting the number of continuing bits having said first logic value and continuing from the most significant bit for each of said original code words;

classifying said original code words into at least three types, according to the number of said continuing bits of said first logic value, including a type in which there is no such continuing bits of the first logic value from the most significant bit; and

compressing said original code words to create a compressed code table, by representing each of said original code words by a combination of;

a control code indicative of said type of said original code word;

code length data indicative of the length of said original code word; and

a partial code indicative of the content of said original code word from which said continuing bits of the first logic value are removed; and

restoring said original code word from said compressed code word by adding a predetermined number of continuing bits of said first logic value to said partial code word as higher order bits thereof, according to the type of said original code word as indicated by said control code.

2. An entropy encoding method as claimed in claim 1, wherein said code length data indicates a code length of said partial code, said code length data thereby representing the code length of said original code word in terms of the code length of said partial code and the type of said original code word as represented by said control code.

3. An entropy encoding method as claimed in claim 2, wherein said method further includes a step of restoring a code length of said original code word from said code length data that indicates the code length of said partial code, said step of restoring the code length data including the steps of:

identifying the type of said original code word based upon said control code; and

increasing said code length data according to the type of said original code word, such that said code length data is increased by a value corresponding to the number of the bits having said first logic value and continuing from the most significant bit in said original code word.

4. An entropy encoding method, comprising the steps of:

restoring original code words from a compressed code table containing therein compressed code words, each of said original code words containing bits of first and second logic values, each of said compressed code words containing said compressed code words as a combination of;

a control code indicative of a type of said original code word, said type being determined according to the number of bits having said first logic value and continuing from the most significant bit of said original code word;

code length data indicative of the length of said original code word; and

a partial code indicative of the content of said original code word from which said continuing bits of said first logic value are removed;

said step of restoring said original code words comprising the steps of;

adding a predetermined number of continuing bits of said first logic value to said partial code word as higher order bits thereof according to the type of said original code word as indicated by said control code.

5. An entropy encoding method as claimed in claim 4, wherein said code length data indicates a code length of said partial code, said code length data thereby representing the code length of said original code word in terms of the code length of said partial code and the type of said original code word as represented by said control code.

6. An entropy encoding method as claimed in claim 5, wherein said method further includes a step of restoring a code length of said original code word from said code length data that indicates the code length of said partial code, said step of restoring the code length data including the steps of:

identifying the type of said original code word based upon said control code; and

increasing said code length data according to the type of said original code word, such that said code length data is increased by a value corresponding to the number of the bits having said first logic value and continuing from the most significant bit in said original code word.

7. An encoder for encoding data according to an entropy encoding process, comprising:

a memory for storing original code words used for an entropy encoding process in a compressed form as compressed code words, each of said original code words including bits of first and second logic values, each of said compressed code words including;

a control code indicative of one of at least three types of said original code word corresponding to said compressed code word, according to the number of bits having said first logic value and continuing from the most significant bit of said original code word, said three types including a type in which there is no such continuing bits of said first logic value from the most significant bit;

a data length code indicating the length of said original code word; and

a partial code representing a remaining part of said original code word;

an address circuit supplied with input data for selecting a corresponding compressed code word in said memory;

a data length extraction unit for extracting said data length code from said selected compressed code word;

a control code extraction unit for extracting said control code from said selected compressed code word, said control code extraction unit outputting said control code as a part of said compressed data; and

a partial code extraction unit supplied for extracting said partial code from said selected code word; and

a code word restoring unit supplied with said control code and said partial code for restoring said original code word therefrom, said code word restoring unit restoring said original code word by adding a predetermined number of bits having said first logic value to said partial code according to the type of said original code word indicated by said control code, said predetermined number being determined by said control code.

8. An encoder as claimed in claim 7, wherein said code word restoring unit comprises:

a register supplied with said partial code from said partial code extraction unit for holding said partial code therein;

a controller supplied with said control code from said control code extraction unit for producing a control signal in response to said control code;

a selection circuit supplied with said partial code from said register for selectively outputting either one of said partial code and a digit having said first logic value for each of bits of said original code word.

9. An encoder as claimed in claim 8, wherein said register includes a first register section for storing a first part of said partial code and a second register section for storing a second part of said partial code, said selection circuit including first through fourth selection circuit elements respectively producing first through fourth bits, fifth through eighth bits, ninth through twelfth bits, and thirteenth through sixteenth bits of said original code word as measured from the most significant bit of said original code word, under control of said controller, said first register section supplying said first part of said partial code to said first through third selection circuit elements simultaneously, said second register section supplying said second part of said partial code to said second through fourth selection circuit elements simultaneously.

10. An encoder as claimed in claim 9, wherein said first through fourth selection circuit elements comprise first through fourth OR circuit respectively, said first and third OR circuits being supplied with said first part of said partial code from said first register section, said second and fourth OR circuits being supplied with said second part of said partial code from said second register section, said controller supplying one of logic data "0" and "1" to two of said first through fourth OR circuits as an input signal depending upon the content of said control code and the other of logic data "0" and "1" to the other two of said fist through fourth OR circuits as an input signal depending upon the content of said control code.

11. An encoder as claimed in claim 8, wherein said memory stores said data length code as a code indicating the data length of said partial code, and wherein said code word restoring unit further includes a logic circuit for discriminating the content of said control code and for producing numeric data to be added to said data length code arithmetically, and an adder circuit supplied with said data length code from said data length extraction unit, for adding said numeric data to said data length code arithmetically.