US6445314B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for the decoding of variable length codes
Assignee: Cisco Technology Inc
•
Filing: 2000-03-01
•
Granted: 2002-09-03
•
Expires: 2020-03-01
Abstract
Abstract A system for decoding variable length codes comprises a window buffer, a unique variable length code look-up table and a decoder. The window buffer is coupled to receive a bit stream and provides a window output having the same number of bits in the longest variable length code. The output of the window buffer is coupled to address the variable length code look-up table. The look-up table has entries pre-calculated based on the variable length code book and is pre-stored in the system. The window buffer can have a size of any number of bits from X to Y where X is the number of bits in the longest variable length code and Y is a number greater than X. The output of the variable length code look-up table is provided to the decoder. The output of the variable length code look-up table includes the code specified by the bits, and a number of bits that the window buffer should be incremented. This number is in turn used by the decoder to increment the window buffer. The present invention is particularly advantageous because with a modest increase in the size and format of the variable length code look-up table, the decoder in a single computation can determine the code.
Inventors
- 👤 Ji Zhang
- 👤 Fang Wu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:06
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
141 words
A device for decoding variable length codes, the device comprising: window buffer having first input, a second input and an output, the window buffer storing a plurality of bits for use in addressing in response to a control signal on the second input, the first input of the window buffer coupled to receive a first bit stream; a look-up table having an input and an output for generating at least one code and a signal indicating a number of codes being output, the input of the look-up table coupled to the output of the window buffer; and a decoder having an input, a control output and a data output for providing codes, the input of the decoder coupled to the output of the look-up table and the control output of the decoder coupled to the second input of the window buffer.
Claim 2
Independent Claim
141 words
A device for decoding variable length codes, the device comprising: window buffer having first input, a second input and an output, the window buffer storing a plurality of bits for use in addressing in response to a control signal on the second input, the first input of the window buffer coupled to receive a first bit stream; a look-up table having an input and an output for generating at least one code and a signal indicating a number of codes being output, the input of the look-up table coupled to the output of the window buffer; and a decoder having an input, a control output and a data output for providing codes, the input of the decoder coupled to the output of the look-up table and the control output of the decoder coupled to the second input of the window buffer.
Claim 3
Dependent Claim
27 words
The device of claim 1 , wherein the window buffer stores at least as many bits as a number of bits of a longest variable length codeword.
Claim 4
Dependent Claim
29 words
The device of claim 1 , wherein the window buffer stores at least as many bits as two times the number of bits of a longest variable length codeword.
Claim 5
Dependent Claim
42 words
The device of claim 1 , wherein the window buffer can be incremented any number of bits from X to Y where X is a number of bits in a longest variable length code and Y is a number greater than X.
Claim 6
Dependent Claim
28 words
The device of claim 1 , wherein entries of the look-up table are pre-calculated based on a variable length code book and are pre-stored in the look-up table.
Claim 7
Dependent Claim
40 words
The device of claim 1 , wherein each entry of the look-up table includes a symbol value specified by bits of the address applied to the look-up table, and a number of bits that the window buffer should be incremented.
Claim 8
Dependent Claim
55 words
The device of claim 1 , wherein each entry of the look-up table includes a first code, a first number of bits in the first code, a second code, a second number of bits in the second code, and so on (not limited to only two code per LUT access) and a number of codes.
Claim 9
Independent Claim
119 words
A system for decoding variable length codes, the system comprising: a buffer having an first input, a second input and an output, the buffer storing a plurality of bits for use in addressing in response to a control signal on the second input, the first input of the buffer coupled to receive a first bit stream; a processor for performing operations on data in response to memory instruction, the processor coupled to the buffer by a bus; and a a memory coupled to the processor by a bus, the memory storing a VLD look-up table, and decoding routines used to control the processor for generating at least one code and a signal indicating a number of codes being output.
Claim 10
Independent Claim
119 words
A system for decoding variable length codes, the system comprising: a buffer having an first input, a second input and an output, the buffer storing a plurality of bits for use in addressing in response to a control signal on the second input, the first input of the buffer coupled to receive a first bit stream; a processor for performing operations on data in response to memory instruction, the processor coupled to the buffer by a bus; and a a memory coupled to the processor by a bus, the memory storing a VLD look-up table, and decoding routines used to control the processor for generating at least one code and a signal indicating a number of codes being output.
Claim 11
Dependent Claim
26 words
The device of claim 8 , wherein the buffer stores at least as many bits as a number of bits of a longest variable length codeword.
Claim 12
Dependent Claim
42 words
The device of claim 9 , wherein the window buffer can be incremented any number of bits from X to Y where X is a number of bits in a longest variable length code and Y is a number greater than X.
Claim 13
Dependent Claim
31 words
The device of claim 9 , wherein entries of the look-up table are pre-calculated based on a variable length code book and are pre-stored in the memory as the look-up table.
Claim 14
Dependent Claim
39 words
The device of claim 9 , wherein each entry of the look-up table includes a code specified by bits of the address applied to the look-up table, and a number of bits that the window buffer should be incremented.
Claim 15
Independent Claim
69 words
A method for decoding variable length codes, the method comprising the steps of: receiving an input bit stream; defining a window of W bits of the input bit stream; reading data from memory using W bits in the window; generating a code using data read from memory; and moving the window by t bits where t is a value read from memory, wherein the value for t is variable.
Claim 16
Independent Claim
69 words
A method for decoding variable length codes, the method comprising the steps of: receiving an input bit stream; defining a window of W bits of the input bit stream; reading data from memory using W bits in the window; generating a code using data read from memory; and moving the window by t bits where t is a value read from memory, wherein the value for t is variable.
Claim 17
Dependent Claim
29 words
The method of claim 13 , wherein the method further comprises the step of repeating the steps of defining, reading, generating and moving for the bits in the bitstream.
Claim 18
Dependent Claim
29 words
The method of claim 13 , wherein the step of reading the data from memory includes applying the bits from the window as address inputs to a look-up table.
Claim 19
Dependent Claim
46 words
The method of claim 13 , wherein the step of generating a code includes the step of determining a first portion of data read from memory that is code, and second portion of data read from memory that is the number of bits in the code.
Claim 20
Dependent Claim
29 words
The method of claim 13 , wherein the step of defining a window includes the step of providing an input buffer, and loading the input buffer with W bits.
Claim 21
Dependent Claim
40 words
The method of claim 13 , further comprising the step of wherein the step of defining a window includes the step of receiving t more bits from the bit stream and shifting the bits in the buffer by t bits.
Claim 22
Dependent Claim
34 words
The method of claim 13 , wherein the value for t is set to a number equal to or greater than a sum of the number of bits used for each variable length code.
References Cited (Backward Citations)
US5736945A
Cited
US5901177A
Cited
US5668548A
Cited
US5710561A
Cited
US6011498A
Cited
US6215424B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-09-02 | 2006-03-04 | 2006-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-02 | 2010-03-04 | 2010-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-02 | 2014-03-04 | 2014-09-03 | $7700.00 | Window Closed / Lapsed |