Method and apparatus for decoding huffman codes by detecting a special class
AssigneeLSI Logic Corporation
InventorsPo Tong, Peter Ruetz
Life of this patent
Estimating the term…
Abstract
A structure and a method are provided for fast-decoding a Huffman code using a leading 1's detector for recognizing the number of leading 1's in the Huffman codeword up to a predetermined maximum, so as to provide a class number in accordance with the number of leading 1's recognized, a first logic circuit for providing a "remainder" by removing from the Huffman codeword a number of bits in accordance with the class number, and a second logic circuit for recognizing a special class. In one embodiment, decoding is accomplished by accessing a storage device using an address formed by a table number, a subclass number derived from the class number and all of the bits in the remainder except the least significant bit.
Claims12
A structure for decoding a Huffman codeword, said Huffman codeword having a length no longer than w bits, said structure comprising:
- a leading 1's detector for detecting a number c of leading 1's in said Huffman codeword up to a predetermined maximum no more than w and for providing a class number equal to said number c;
- a first logic circuit receiving said number c and said Huffman code word for providing a remainder word of up to m bits, said remainder word being said Huffman codeword remaining after removing, for said class number less than said pre-determined maximum, c+1 bits, and for said class number equal to said predetermined maximum, c bits;
- means for dividing said remainder word into a special bit and a sub-remainder word portions;
- a second logic circuit receiving said special bit and said sub-remainder portions for providing a subclass number, such that when said class number does not equal a special class number said subclass number is assigned said class number, and when said class number equals said special class number, said subclass number is assigned said special class number or a predetermined value, in accordance with the value of said special bit;
- means for storing decoded values of Huffman codewords;
- and
- address decoder for mapping an address comprising first and second fields, being respectively said sub-class number and said sub-remainder word, to a location in said storage means.
A method for decoding a Huffman codeword, said Huffman codeword having a length no longer than w bits, said method comprising the steps of:
- using a leading 1's detector to detect a number c of leading 1's in said Huffman codeword up to a predetermined maximum no more than w and for providing a class number equal to said number c;
- using a first logic circuit to provide a remainder word, said remainder word being said Huffman codeword remaining after removing, for said class number less than said pre-determined maximum, c+1 bits, and for said class number equal to said predetermined maximum, c bits;
- dividing said remainder word into a special bit and a sub-remainder word portions;
- using a second logic circuit to provide a subclass number, such that when said class number does not equal a special class number said subclass number is assigned said class number, and when said class number equals said special class number, said subclass number is assigned said special class number or a predetermined value, in accordance with the value of said special bit;
- providing means for storing decoded values of Huffman codewords;
- and
- providing an address decoder for mapping an address having first and second fields, being respectively said sub-class number and said sub-remainder word, to a location in said storage means.
Dependencies are inferred from the claim text.