US5615020A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for fast huffman decoding
Assignee: Intel Corp
•
Filing: 1993-05-13
•
Granted: 1997-03-25
•
Expires: 2013-05-13
Abstract
Abstract A method is provided for performing statistical decoding if a symbol in a data stream having byte boundaries wherein the symbol may have varying alignments with respect to the byte boundaries. The next byte of data is fetched from the data stream wherein the fetched byte contains at least a portion of the symbol. Based on this byte and on the current bit position, which is maintained by a state machine, either (a) a decoded value is obtained from a lookup table, or (b) further bytes are fetched and used to determine the decoded value. Each symbol has a prefix and free bits wherein the entire symbol may be included in the next byte, a boundary of the next byte may fall within a prefix, or a boundary of the next byte may fall within the free bits depending on the alignment of the symbol. Differing action routines, corresponding to differing symbols, may be selected for execution according to the decoded values determined in the symbols.
Inventors
- 👤 Michael Keith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:29
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
146 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, comprising the steps of: (a) fetching a first byte of data from said data stream, said first byte of data containing at least a portion of said symbol; (b) determining said alignment of said at least a portion within said first byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) extracting a determined number of bits from said second byte of data, wherein said determined number of bits is determined in accordance with said first byte of data; and (e) determining said decoded value in accordance with said fetched data.
Claim 2
Independent Claim
146 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, comprising the steps of: (a) fetching a first byte of data from said data stream, said first byte of data containing at least a portion of said symbol; (b) determining said alignment of said at least a portion within said first byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) extracting a determined number of bits from said second byte of data, wherein said determined number of bits is determined in accordance with said first byte of data; and (e) determining said decoded value in accordance with said fetched data.
Claim 3
Dependent Claim
20 words
The method for the statistical decoding of a symbol of claim 1, wherein step (e) comprises performing a table lookup.
Claim 4
Dependent Claim
30 words
The method for the statistical decoding of a symbol of claim 1, comprising the step of forming an index according to said first byte of data and said extracted bits.
Claim 5
Dependent Claim
24 words
The method for the statistical decoding of a symbol of claim 3, wherein step (e) comprises determining said decoded value according to said index.
Claim 6
Independent Claim
155 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, wherein there is provided a plurality of symbols and a plurality of action routines corresponding to said plurality of symbols, comprising the steps of: (a) fetching a first byte of data from said data stream, said first byte of data containing at least a portion of said symbol; (b) determining said alignment of said at least a portion within said first byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) determining said decoded value in accordance with said fetched data; and (e) executing a selected action routine of said plurality of action routines in accordance with said decoded value.
Claim 7
Independent Claim
155 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, wherein there is provided a plurality of symbols and a plurality of action routines corresponding to said plurality of symbols, comprising the steps of: (a) fetching a first byte of data from said data stream, said first byte of data containing at least a portion of said symbol; (b) determining said alignment of said at least a portion within said first byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) determining said decoded value in accordance with said fetched data; and (e) executing a selected action routine of said plurality of action routines in accordance with said decoded value.
Claim 8
Independent Claim
181 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, wherein there is provided a plurality of variable length symbols including a prefix and free bits, comprising the steps of: (a) fetch a first byte of data from said stream, said first byte of data containing at least a portion of said; (b) determining said alignment of said at least a potion within said byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) determining said decoded value in accordance with said fetched data, wherein step (b) comprises the steps of: (e) determining whether both said prefix and said free bits fall within said first byte; (f) determining whether a byte boundary of said first byte falls within said free bits; and (g) determining whether a byte boundary of said first byte fall within said prefix.
Claim 9
Independent Claim
181 words
A method for statistical decoding of a variable bit length symbol in a data stream divided into a plurality of bytes having byte boundaries to provide an output value, said symbol having an alignment with respect to said byte boundaries, wherein there is provided a plurality of variable length symbols including a prefix and free bits, comprising the steps of: (a) fetch a first byte of data from said stream, said first byte of data containing at least a portion of said; (b) determining said alignment of said at least a potion within said byte with respect to a byte boundary of said first byte; (c) fetching a second byte of data in accordance with said determined alignment; (d) determining said decoded value in accordance with said fetched data, wherein step (b) comprises the steps of: (e) determining whether both said prefix and said free bits fall within said first byte; (f) determining whether a byte boundary of said first byte falls within said free bits; and (g) determining whether a byte boundary of said first byte fall within said prefix.
Claim 10
Dependent Claim
37 words
The method for statistical decoding of a symbol of claim 6, wherein both prefix and free bits fall within said first byte and the decoded value is determined only in accordance with said first byte of data.
Claim 11
Dependent Claim
60 words
The method for the statistical decoding of a symbol of claim 6, wherein a byte boundary of said first byte falls within said free bits, further comprising the step of extracting a number of free bits from said second byte of data, the number of free bits being determined in accordance with the data of said first byte of data.
Claim 12
Dependent Claim
45 words
The method for the statistical decoding of a symbol of claim 6, wherein a byte boundary of said first byte falls within said prefix, further comprising the step of determining whether to fetch a third byte of data in accordance said first byte of data.
References Cited (Backward Citations)
US3883847A
Cited
US4386416A
Cited
US4396906A
Cited
US4369463A
Cited
US4593267A
Cited
US4580162A
Cited
JPS59152780A
Cited
US4563671A
Cited
US4574382A
Cited
EP0145396A2
Cited
US4706265A
Cited
US4700175A
Cited
US4899149A
Cited
US5045853A
Cited
US4926266A
Cited
US4813056A
Cited
WO1989005556A1
Cited
US4967196A
Cited
US5057917A
Cited
US5304995A
Cited
US5268769A
Cited
US5253053A
Cited
US5220325A
Cited
US5329313A
Cited
EP0577330A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-24 | 2000-09-23 | 2001-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-24 | 2004-09-23 | 2005-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-24 | 2008-09-23 | 2009-03-25 | $7700.00 | Window Closed / Lapsed |