Programmable variable-length decoder
AssigneeBroadcom Corporation
InventorVivian Hsiun
Life of this patent
Estimating the term…
Abstract
System and method for decoding variable-length codes. A variable-length decoder includes an address generator and a local memory unit. The local memory stores a variable-length code look-up table. The local memory can be programmed to include a look-up table supporting substantially any decoding algorithm. In one embodiment, a decoder memory unit and a system memory unit are employed together with the local memory to store a codeword look-up table. The shortest codes are stored in local memory, the next shortest in decoder memory, and the longest codes are stored in system memory. A multistage search algorithm is employed to search for the longest codes. The address generator generates the address of the code table to be searched by adding the value of the bits to be searched to a base address.
Claims23
A method of decoding a variable-length code data stream, comprising steps of:
- (a) setting a base memory address equal to a start address;
- (b) retrieving the next n bits in the data stream;
- (c) accessing a memory location having an address equal to the sum of the base address plus the value of the n retrieved bits, which memory location includes status data indicating whether a codeword is found, wherein, if a codeword is found, the memory location includes corresponding information, and wherein if a codeword is not found, the memory location includes an offset value;
- (d) if a codeword has been identified:
- (d)(i) outputting the decoded information corresponding to the codeword;
- (d)(ii) setting the base address equal to the start address;
- and
- (d)(iii) shifting the data in the data stream by a number of the retrieved bits that correspond to the decoded information;
- and
- (e) if a codeword has not been identified:
- (e)(i) setting the base address according to the offset value;
- and
- (e)(ii) shifting the data in the data stream n bits.
A method of decoding a variable-length code data stream, comprising steps of:
- (a) designating a first memory element as a memory element to be searched;
- (b) retrieving the next n bits in the data stream;
- (c) accessing a designated memory location in the memory element to be searched, which memory location includes status data indicating whether a codeword from the data stream has been identified, wherein if a codeword has been identified, the memory location includes decoded information corresponding to the identified codeword, and wherein if a codeword has not been identified, the memory location includes a next-search-location indicator indicating a memory element at which to perform the next search;
- (d) if a codeword has been identified:
- (d)(i) outputting the decoded information corresponding to the codeword;
- (d)(ii) designating the first memory element as the memory element to be searched;
- and
- (d)(iii) shifting the data in the data stream by a number of the retrieved bits that correspond to the decoded information;
- and
- (e) if a codeword has not been identified:
- (e)(i) designating the memory element indicated by the next-search indicator as the memory element to be searched;
- and
- (e)(ii) shifting the data in the data stream n bits.
Dependencies are inferred from the claim text.