Variable-length-code decoders storing decoding results and corresponding code-bit-length information in memory

• US 5,600,812 A
• Filed: 05/03/1995
• Issued: 02/04/1997
• Est. Priority Date: 06/30/1994
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Heon-chul
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US08/434,006
• Time in Patent Office: 643 Days
• Field of Search: 395/410, 395/416, 395/412, 341/65, 341/67
• US Class Current: 711/200
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/425 for the decoding process only

Abstract

A decoder uses look-up table memory for variable-length coding (such as Huffman coding) that comprises concatenated variable-length codes, most species of which codes can each be analyzed as being composed of a pointer subcode of variable bit-length and a target subcode of fixed bit-length, the target subcodes being relatively efficiently encoded and the pointer subcodes being relatively inefficiently encoded. The memory stores not only decoding results, but the bit-lengths of the codes generating those results. The bit-lengths of the concatenated codes are accumulated and the accumulation result in modular arithmetic is supplied to as shift control signal to a data shifter. The data shifter positions each successive one of the concatenated codes within a window so the leadmost bit of the code is positioned at the edge of the window. The pointer subcodes are decoded, applied to address lines of the memory, and used to select target subcodes to an address decoder. The target subcodes are decoded by the address decoder and applied to further address lines of the memory.

Claims

1. A decoder for variable-length coding composed of concatenated variable-length code words, at least some of which said code words are composed of pointer and target subcodes, said decoder comprising:

a controlled data shifter receptive of unshifted said variable-length coding and responsive to a shift indication supplied thereto for shifting a selected portion of said variable-length coding to be positioned within an output window as wide as the longest variable-length code word, said shift indication being a binary number indicative of a number of bit places of desired shift for the selected portion of said variable-length coding to be positioned within said output window of said controlled data shifter;

an accumulator for accumulating code-word bit-length indications to generate said shift indication;

a first memory having a plurality of addressable storage locations a selected one of which is accessed for reading during first times responsive to said selected portion of said variable-length coding as positioned within said output window of said controlled data shifter, storing at each of its addressable storage locations a decoding result for a first decoding table, also storing at each of its addressable storage locations a binary number descriptive of the code bit-length of a variable-length code word as would give rise to the decoding result stored at that addressable storage location, and supplying from each one of the addressable storage locations in said first memory successively addressed during said first times the decoding result and the binary number descriptive of the code-word bit-length which are stored at that addressable storage location, said first memory having address lines for accessing its addressable storage locations and having first memory addressing circuitry that responds to said selected portion of said variable-length coding as positioned within said output window of said controlled data shifter to drive said address lines of said first memory;

means for supplying the code-word bit-length read from said first memory during said first times to said accumulator for accumulation;

a bin comparator included within said first memory addressing circuitry and connected to respond to ones of the leadmost bits of the selected portion of said variable-length coding positioned within said output window of said controlled data shifter, which said leadmost bits can describe a pointer subcode of a code word, for supplying from respective output connections of said bin comparator a respective bin response to each pointer subcode and a further bin response to the lack of a pointer subcode, the respective output connections of said bin comparator connecting to respective ones of a first group of some but not all of said address lines of said first memory;

an address decoder for decoding said target subcode, said address decoder being included within said first memory addressing circuitry and having respective output connections to respective ones of a second group of said address lines of said first memory, said second group containing those of said address lines of said first memory not contained in said first group of them; and

a multiplexer included within said first memory addressing circuitry, said multiplexer being responsive to the bin responses of said bin comparator for selecting said target subcode for application to said address decoder, said multiplexer selecting said target subcode at least in part from the selected portion of said variable-length coding positioned within said output window of said controlled data shifter.

2. A decoder as set forth in claim 1 wherein the binary number descriptive of the code bit-length of a variable-length code word as would give rise to the decoding result stored at that addressable storage location has a value equal to the number of bits in said variable-length code word.

3. A decoder as set forth in claim 1 wherein the binary number descriptive of the code bit-length of a variable-length code word as would give rise to the decoding result stored at that addressable storage location has a value equal to one less than the number of bits in said variable-length code word.

4. A decoder as set forth in claim 1 further comprising:

a second memory having a plurality of addressable storage locations a selected one of which is accessed for reading during second times responsive to said selected portion of said variable-length coding as positioned within said output window of said controlled data shifter, storing at each of its addressable storage locations a decoding result for a second decoding table, also storing at each of its addressable storage locations a binary number descriptive of the bit-length of a variable-length code word as would give rise to the decoding result stored at that addressable storage location, and reading out from each one of the addressable storage locations in said second memory successively addressed during said second times the decoding result and the binary number descriptive of the bit-length of the variable-length code word as would give rise to the decoding result which are stored at that addressable storage location; and

means for supplying the code-word bit-length read from said second memory during said second times to said accumulator for accumulation.