Method and structure for decoding Huffman codes using leading ones detection
First Claim
1. A method for decoding a variable length codeword embedded in a bit stream, comprising the steps of:
- detecting the number of leading 1'"'"'s in said variable length codeword;
looking up from a first storage means (i) a "tail length" corresponding to the maximum number of bits following said number of leading 1'"'"'s in said variable length codeword; and
(ii) a first memory address;
separating from said bit stream in accordance with said tail length a bit string including the bits of said codeword following said leading 1'"'"'s;
combining said first memory address and said bit string to form a second memory address; and
using said second address to access a second storage means to obtain a decoded value of said codeword.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and a structure are provided for decoding Huffman codes using a random access memory having a size less than twice the total number of codewords decodable. Under this method, the number of leading 1'"'"'s in a Huffman codeword and the bits of the Huftman code word other than the leading 1'"'"'s ("remainder") are combined to form an address into the random access memory. Using the fact that, for a given number of leading 1'"'"'s in a Huffman code, the possible remainder of the Huffman code is no longer than a predetermined number of bits, the size of the random access memory necessary for decoding such Huffman codes can be made optimally small.
-
Citations
12 Claims
-
1. A method for decoding a variable length codeword embedded in a bit stream, comprising the steps of:
-
detecting the number of leading 1'"'"'s in said variable length codeword; looking up from a first storage means (i) a "tail length" corresponding to the maximum number of bits following said number of leading 1'"'"'s in said variable length codeword; and
(ii) a first memory address;separating from said bit stream in accordance with said tail length a bit string including the bits of said codeword following said leading 1'"'"'s; combining said first memory address and said bit string to form a second memory address; and using said second address to access a second storage means to obtain a decoded value of said codeword. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A structure for decoding a variable length codeword embedded in a bit stream, comprising:
-
means for detecting the number of leading 1'"'"'s in said variable length codeword; means for looking up from a first storage means (i) a "tail length" corresponding to the maximum number of bits following said number of leading 1'"'"'s in said variable length codeword; and
(ii) a first memory address;means for separating from said bit stream in accordance with said tail length a bit string including the bits of said codeword following said leading 1'"'"'s; means for combining said first memory address and said bit string to form a second memory address; and means, using said second address, for accessing a second storage means to obtain a decoded value of said codeword. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification