Variable length decoding system and method
A method of decoding variable length codes converts a variable length code table into standard format decomposition tables from which a universal variable length decoder can decode. This allows the same universal variable length decoder to decode any variable length code. The memory required to store the standard format decomposition tables is minimized by the conversion process.
1. A method of decoding variable length codes, comprising:
(a) providing a translation of a variable length code table into a variable length decode control table and a variable length decode code table;
(b) applying a universal decode function to an input bitstream, said input bitstream including sequences of codewords from said variable length code table, and said universal decode function interpreting said bitstream using said variable length decode control table to access said variable length decode code table to decode said codewords.
2. The method of claim 1 , wherein said universal decode function:
(a) interprets a first set of bits from said bitstream as a codeword prefix;
(b) uses said prefix and a provided variable length decoding prefix table to determine (i) a maximum length for codewords with said prefix after removal of said prefix and (ii) a mask for bit complementation by XOR; and
(c) uses said prefix and said mask applied to a second set of bits from said bitstream to access said variable length decode control table and then to find an index to access said variable length decode code table and decode one of said codewords.
3. The method of claim 1 , wherein said universal decode function:
(a) interprets a first set of bits from said bitstream as a codeword prefix to determine a first location within said variable length control table;
(b) uses a first entry at said first location to interpret a second set of bits from said bitstream to determine a second location in said variable length control table;
(c) uses a second entry at said second location in said variable length decode control table to find an index to access said variable length decode code table and decode one of said codewords.
4. The method of claim 3 , wherein:
(a) said first entry includes (i) a maximum length for codewords with said prefix after removal of said prefix and (ii) a mask for bit complementation by XOR of said second set of bits;
(b) said second entry includes (i) a shift and (ii) an offset; and
(c) said index is computed as the XOR of said second set of bits followed by said shift and then by said offset.