Uniform decoding of minimum-redundancy codes

• US 3,883,847 A
• Filed: 03/28/1974
• Issued: 05/13/1975
• Est. Priority Date: 03/28/1974
• Status: Expired due to Term

• Current Assignee: Amalie Julianna Frank
• Original Assignee: Amalie Julianna Frank
• Inventors: Frank, Amalie Julianna
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/455,668
• Time in Patent Office: 411 Days
• Field of Search: 340/146.1R,347DD,172.5,147T
• US Class Current: 711/206
• CPC Class Codes: H03M 7/425 for the decoding process only

Abstract

A high-speed decoding system and method for decoding minimumredundancy Huffman codes, which features translation using stored tables rather than a tracing through tree structures. When speed is of utmost importance only a single table access is required; when required storage is to be minimized, one or two accesses are required.

Claims

1. Apparatus for decoding an ordered sequence of variable-length input binary codewords each associated with a symbol in an Nsymbol output alphabet comprising A. a memory storing a first plurality of words each storing information relating to an output symbol, B. means for selecting a fixed-length K-bit sample, K >

OR = 2, from said input sequence, C. means for deriving address signals based on said sample of bits, and D. means for reading information from the location in said memory specified by said address.

2. Apparatus according to claim 1 wherein said memory also contains in each of said words information relating to the length of the input codeword corresponding to each of said output symbols, said apparatus further comprising means responsive to said information related to said codeword length for identifying the first bit in the following codeword in said input sequence.

3. Apparatus according to claim 2 wherein said memory is a memory storing in said first plurality of words information explicity identifying a symbol in said output alphabet.

4. Apparatus according to claim 1 wherein said memory is a memory also storing a plurality of secondary tables, each secondary table comprising words explicitly identifying a symbol in said output alphabet, said memory also storing, in a first subset of said first plurality of words, information identifying one of said plurality of second tables.

5. Apparatus according to claim 4 wherein said memory also stores in each of said words in said secondary tables information identifying Li-K, where Li, i 1,2, . . . , M, is the length of the codeword associated with the ith of said output symbols.

6. Apparatus according to claim 5 further comprising means responsive to said information identifying Li-K for identifying the first bit in the immediately following codeword in said input sequence.

7. Apparatus according to claim 4 wherein said memory is a memory also storing in each of said first plurality of words signals indicating an additional number, A, of bits in said input stream, means responsive to said signals for accessing the immediately succeeding A bits in said input stream, means responsive to said A bits and to said information identifying said one of said tables for accessing one of said words in said one of said tables.

8. Apparatus according to claim 4 wherein said memory is a memory storing in a second subset of said first plurality of words information explicity identifying a symbol in said output alphabet.

9. Apparatus according to claim 8 wherein said memory stores, for each output symbol explicity identified, an indication of the length of the associated input codeword.