US6771196B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Programmable variable-length decoder
Assignee: Avago Technologies International Sales Pte Ltd
•
Filing: 2002-11-12
•
Granted: 2004-08-03
•
Expires: 2022-11-12
Abstract
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.
Inventors
- 👤 Vivian Hsiun
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 05:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3885; G06F9/3861; G09; G09G; G09G5/00; G09G5/14; G09G5/36; H; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/103; H04N19/105; H04N19/12; H04N19/122; H04N19/124; H04N19/126; H04N19/127; H04N19/129; H04N19/134; H04N19/136; H04N19/157; H04N19/162; H04N19/169; H04N19/17; H04N19/176; H04N19/186; H04N19/42; H04N19/423; H04N19/44; H04N19/60; H04N19/61; H04N19/70; H04N19/80; H04N19/82; H04N19/90; H04N19/91; H04N19/93; H04N9/00; H04N9/64; H04N9/641; G09G2310/00; G09G2310/02; G09G2310/0224; G09G2340/00; G09G2340/04; G09G2340/0407; G09G2340/10; G09G2340/12; G09G2340/125; G09G2360/00; G09G2360/12; G09G2360/125; G09G5/02; G09G5/06; G09G5/12; G09G5/22; G09G5/24; G09G5/28; G09G5/34; G09G5/346; H04N5/00; H04N5/44; H04N5/46
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
182 words
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 identified, wherein, if a codeword is identified, the memory location includes decoded information corresponding to the identified codeword, and wherein if a codeword is not identified, the memory location includes an offset value; (d) if a codeword is 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; (e) if a codeword is not identified: (e)(i) setting the base address according to the offset value; and (e)(ii) shifting the data in the data stream n bits; and (f) iteratively repeating steps (b)-(e).
Claim 2
Independent Claim
182 words
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 identified, wherein, if a codeword is identified, the memory location includes decoded information corresponding to the identified codeword, and wherein if a codeword is not identified, the memory location includes an offset value; (d) if a codeword is 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; (e) if a codeword is not identified: (e)(i) setting the base address according to the offset value; and (e)(ii) shifting the data in the data stream n bits; and (f) iteratively repeating steps (b)-(e).
Claim 3
Dependent Claim
34 words
The method of claim 1 wherein the memory location includes current code-length data indicating the number of bits by which to shift the data in the data stream in shifting steps (d)(iii) and (e)(ii).
Claim 4
Dependent Claim
28 words
The method of claim 2 wherein, if a codeword is identified, the current code-length data indicates the number of the retrieved bits that correspond to the decoded information.
Claim 5
Dependent Claim
26 words
The method of claim 2 wherein, if a codeword is not identified, the current code-length data indicates the number, n, of bits retrieved in step (b).
Claim 6
Dependent Claim
19 words
The method of claim 1 wherein shifting steps (d)(iii) and (e)(ii) comprise left-shifting the data in the data stream.
Claim 7
Dependent Claim
62 words
The method of claim 1 wherein, if a codeword is not identified, the memory location includes next-search-length data indicating a number, n, of bits to be retrieved in the next stage and wherein step (e) further comprises a sub-step (e)(iii) of setting the number of bits, n, to be retrieved in the next stage equal to the value of the next-search-length data.
Claim 8
Dependent Claim
25 words
The method of claim 1 wherein step (f) comprises iteratively repeating steps (b)-(e) as long as there is data in the data stream to decode.
Claim 9
Dependent Claim
16 words
The method of claim 1 wherein the variable-length code data stream is a media data stream.
Claim 10
Dependent Claim
16 words
The method of claim 8 wherein the variable-length code data stream is a video data stream.
Claim 11
Dependent Claim
25 words
The method of claim 9 wherein if a codeword is identified, the memory location includes a discrete cosine transform coefficient corresponding to the found codeword.
Claim 12
Dependent Claim
18 words
The method of claim 1 wherein step (e)(i) comprises setting the base address equal to the offset value.
Claim 13
Dependent Claim
25 words
The method of claim 1 wherein step (e)(i) comprises setting the base address equal to the sum of the offset value plus the start address.
Claim 14
Independent Claim
198 words
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 is identified, wherein if a codeword is identified, the memory location includes decoded information corresponding to the identified codeword, and wherein if a codeword is not 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 is 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; (e) if a codeword is not 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; and (f) iteratively repeating steps (b)-(e).
Claim 15
Independent Claim
198 words
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 is identified, wherein if a codeword is identified, the memory location includes decoded information corresponding to the identified codeword, and wherein if a codeword is not 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 is 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; (e) if a codeword is not 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; and (f) iteratively repeating steps (b)-(e).
Claim 16
Dependent Claim
95 words
The method of claim 13 wherein step (a) further comprises setting a base memory address equal to a start address, wherein the designated memory location of step (c) has an address equal to the sum of the base address plus the value of the n retrieved bits, wherein the memory location of step (c) includes an offset value, wherein step (d) further comprises a sub-step (d)(iv) of setting the base address equal to the start address, and wherein step (e) further comprises a sub-step (e)(iii) of setting the base address according to the offset value.
Claim 17
Dependent Claim
18 words
The method of claim 14 wherein step (e)(iii) comprises setting the base address equal to the offset value.
Claim 18
Dependent Claim
34 words
The method of claim 14 wherein step (e)(iii) comprises setting the base address equal to the sum of the offset value plus a starting address of the memory element indicated by the next-search-location indicator.
Claim 19
Dependent Claim
34 words
The method of claim 13 wherein the memory location includes current code-length data indicating the number of bits by which to shift the data in the data stream in shifting steps (d)(iii) and (e)(ii).
Claim 20
Dependent Claim
28 words
The method of claim 17 wherein, if a codeword is identified, the current code-length data indicates the number of the retrieved bits that correspond to the decoded information.
Claim 21
Dependent Claim
26 words
The method of claim 17 wherein, if a codeword is not identified, the current code-length data indicates the number, n, of bits retrieved in step (b).
Claim 22
Dependent Claim
19 words
The method of claim 13 wherein shifting steps (d)(iii) and (e)(ii) comprise left-shifting the data in the data stream.
Claim 23
Dependent Claim
62 words
The method of claim 13 wherein if a codeword is not identified, the memory location includes next-search-length data indicating a number, n, of bits to be retrieved in the next stage and wherein step (e) further comprises a sub-step (e)(iii) of setting the number of bits, n, to be retrieved in the next stage equal to the value of the next-search-length data.
Claim 24
Dependent Claim
25 words
The method of claim 13 wherein step (f) comprises iteratively repeating steps (b)-(e) as long as there is data in the data stream to decode.
Claim 25
Dependent Claim
16 words
The method of claim 13 wherein the variable-length code data stream is a media data stream.
Claim 26
Dependent Claim
16 words
The method of claim 23 wherein the variable-length code data stream is a video data stream.
Claim 27
Dependent Claim
25 words
The method of claim 24 wherein if a codeword is identified, the memory location includes a discrete cosine transform coefficient corresponding to the identified codeword.
Claim 28
Dependent Claim
102 words
A data decoding system comprising: a variable-length decoder (VLD) comprising: an address generator adapted to receive data from the data stream and to generate a memory address at which to search for a codeword match in a VLD look-up table; and a local memory unit adapted to store at least a portion of the VLD look-up table; and a first external memory unit external to the variable-length decoder and adapted to store a portion of the VLD look-up table if the VLD look-up table is larger than an amount of memory allotted for the VLD look-up table in the local memory unit.
Claim 29
Dependent Claim
102 words
A data decoding system comprising: a variable-length decoder (VLD) comprising: an address generator adapted to receive data from the data stream and to generate a memory address at which to search for a codeword match in a VLD look-up table; and a local memory unit adapted to store at least a portion of the VLD look-up table; and a first external memory unit external to the variable-length decoder and adapted to store a portion of the VLD look-up table if the VLD look-up table is larger than an amount of memory allotted for the VLD look-up table in the local memory unit.
Claim 30
Dependent Claim
18 words
The system of claim 26 wherein the first external memory unit is internal to the data decoding system.
Claim 31
Dependent Claim
19 words
The system of claim 27 wherein the first external memory unit is a static random access memory (SRAM) unit.
Claim 32
Dependent Claim
57 words
The system of claim 26 further comprising a second external memory unit external to the variable-length decoder and adapted to store a portion of the VLD look-up table if the VLD look-up table is larger than a combined amount of memory allotted for the VLD table in the local memory unit and the first external memory unit.
Claim 33
Dependent Claim
18 words
The system of claim 29 wherein the second external memory unit is external to the data decoding system.
Claim 34
Dependent Claim
29 words
The system of claim 30 wherein the second external memory unit is a main memory unit for a communications system of which the data decoding system is a component.
Claim 35
Dependent Claim
19 words
The system of claim 31 wherein the second external memory unit is a dynamic random access memory (DRAM) unit.
Claim 36
Dependent Claim
60 words
The system of claim 26 wherein the variable-length decoder further comprises: a shift register adapted to store data from the data stream and to shift the data an indicated number of bits after a codeword search is completed and to provide an indicated number of the most significant bits in the shift register after a shift to the address generator.
Claim 37
Dependent Claim
61 words
The system of claim 33 wherein the VLD look-up table includes a plurality of entries, each entry comprising a status indicator indicating whether the entry contains the information corresponding to a block of data stream data for which a match is sought and a current-code-length indicator indicating the number of bits by which to shift the data in the shift register.
Claim 38
Dependent Claim
42 words
The system of claim 34 wherein each entry in the VLD look-up table that does not contain a code match further comprises a next-search-length indicator indicating the number of most significant bits the shift register is to provide to the address generator.
Claim 39
Dependent Claim
40 words
The system of claim 35 wherein each entry in the VLD look-up table that does not contain a code match further comprises a next-search-location indicator indicating the memory unit at which to next search the VLD table for a match.
Claim 40
Dependent Claim
56 words
The system of claim 36 wherein the address generator generates the memory address at which to search for a codeword match in a VLD look-up table by adding a starting address of the VLD look-up table in the memory unit indicated by the next-search-location indicator plus the value of the bits provided by the shift register.
Claim 41
Dependent Claim
45 words
The system of claim 37 wherein each entry in the VLD look-up table that does not contain a code match further comprises an offset value indicating an address at which to next search the VLD table in one of the memory units for a match.
Claim 42
Dependent Claim
64 words
The system of claim 38 wherein the address generator generates the memory address at which to search for a codeword match in a VLD look-up table by further adding the offset value to the sum of the starting address of the VLD look-up table in the memory unit indicated by the next-search-location indicator and the value of the bits provided by the shift register.
References Cited (Backward Citations)
US3883847A
Cited
US5857088A
Cited
US5675331A
Cited
US5703579A
Cited
US5694125A
Cited
US5675332A
Cited
US5696507A
Cited
US6546053B1
Cited
US6069575A
Cited
US6313767B1
Cited
US6538656B1
Cited
US6445314B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-08-03 | 2008-02-02 | 2008-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-08-03 | 2012-02-02 | 2012-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-08-03 | 2016-02-02 | 2016-08-03 | $7700.00 | Window Closed / Lapsed |