Rate adaptive huffman coding

• US 5,420,639 A
• Filed: 04/01/1993
• Issued: 05/30/1995
• Est. Priority Date: 04/01/1993
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: Perkins, Michael G.
• Primary Examiner(s): Britton, Howard W.
• Assistant Examiner(s): LEE, RICHARD J
• Application Number:
  US08/041,670
• Time in Patent Office: 789 Days
• Field of Search: 348/414, 348/417, 348/418, 348/422, 358/427, 341/65
• US Class Current: 375/240.12
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

Methods for compressing data in a system employing vector quantization (VQ) and Huffman coding comprise: First, quantizing an input vector by representing the input vector with a VQ codevector selected from a VQ codebook partitioned into subsets, wherein each subset comprises codevectors and each codevector is stored at a corresponding address in the VQ codebook. Next, generating a rate dependent Huffman codeword for the selected codevector, wherein the rate dependent Huffman codeword identifies the subset of the VQ codebook in which the selected codevector is stored. And finally, generating a substantially rate independent Huffman codeword for the selected codevector, wherein the substantially rate independent Huffman codeword identifies a particular VQ codevector within the subset identified by the rate dependent Huffman codeword.

Claims

1. A method for compressing data, comprising the steps of:

(a) quantizing an input vector by representing said input vector with a vector quantization (VQ) codevector selected from a VQ codebook partitioned into subsets, wherein each subset comprises codevectors and each one of said codevectors is stored at a corresponding address in said VQ codebook;

(b) generating a rate dependent Huffman codeword for the selected codevector, wherein said rate dependent Huffman codeword identifies the subset of said VQ codebook in which the selected codevector is stored; and

(c) generating a substantially rate independent Huffman codeword for the selected codevector, wherein said substantially rate independent Huffman codeword identifies a particular VQ codevector within the subset identified by said rate dependent Huffman codeword.

2. The method recited in claim 1, wherein the VQ codebook is a tree structured codebook (TSCB) and the subsets correspond to levels of the TSCB.

3. The method recited in claim 1, wherein the steps of generating a rate dependent Huffman codeword and generating a substantially rate independent Huffman codeword comprise reading codewords from a Huffman codebook.

4. The method recited in claim 3, wherein said Huffman codebook is characterized in that the length of each said rate dependent Huffman codeword is generally inversely related to the probability that the selected VQ codevector will be within the subset identified by that codeword;

and the length of each said substantially rate independent Huffman codeword is generally inversely related to the probability that the particular VQ codevector identified by that codeword will be selected.

5. The method recited in claim 1, wherein the subsets correspond to different VQ codebooks.

6. The method recited in claim 1, wherein:

(1) the VQ codebook is a tree structured codebook (TSCB) and the subsets correspond to levels of the TSCB;

(2) the steps of generating a rate dependent Huffman codeword and generating a substantially rate independent Huffman codeword comprise reading codewords from a Huffman codebook; and

(3) said Huffman codebook is characterized in that the length of each said rate dependent Huffman codeword is generally inversely related to the probability that the selected VQ codevector will be within the subset identified by that codeword; and

the length of each said substantially rate independent Huffman codeword is generally inversely related to the probability that the particular VQ codevector identified by that codeword will be selected.

7. A system for compressing data, comprising:

(a) a vector quantization (V Q) codebook partitioned into subsets, wherein each subset comprises codevectors and each one of said codevectors is stored at a corresponding address in said VQ codebook;

(b) means for quantizing an input vector by representing said input vector with a VQ codeword determined on the basis of a VQ codevector selected from said VQ codebook;

(c) means for generating a rate dependent Huffman codeword for the selected VQ codevector, wherein said rate dependent Huffman codeword identifies the subset of said VQ codebook in which the selected codevector is stored; and

(d) means for generating a substantially rate independent Huffman codeword for the selected codevector, wherein said substantially rate independent Huffman codeword identifies a particular VQ codevector within the subset identified by said rate dependent Huffman codeword.

8. The system recited in claim 7, wherein said VQ codebook is a tree structured codebook (TSCB) and the subsets correspond to levels of the TSCB.

9. The system recited in claim 7, wherein the means for generating a rate dependent Huffman codeword and generating a substantially rate independent Huffman codeword comprise a Huffman codebook embodied in a memory and means for reading codewords from said Huffman codebook.

10. The system recited in claim 9, wherein said Huffman codebook is characterized in that the length of each said rate dependent Huffman codeword is generally inversely related to the probability that the selected VQ codevector will be within the subset identified by that codeword;

and the length of each said substantially rate independent Huffman codeword is generally inversely related to the probability that the particular VQ codevector identified by that codeword will be selected.

11. The system recited in claim 7, wherein the subsets correspond to different VQ codebooks.

12. The system recited in claim 7, wherein:

(1) the VQ codebook is a tree structured codebook (TSCB) and the subsets correspond to levels of the TSCB;

(2) the means for generating a rate dependent Huffman codeword and generating a substantially rate independent Huffman codeword comprise a Huffman codebook embodied in a memory and means for reading codewords from said Huffman codebook; and

(3) said Huffman codebook is characterized in that the length of each said rate dependent Huffman codeword is generally inversely related to the probability that the selected VQ codevector will be within the subset identified by that codeword; and

the length of each said substantially rate independent Huffman codeword is generally inversely related to the probability that the particular VQ codevector identified by that codeword will be selected.