US4899149A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of and apparatus for decoding Huffman or variable-length coees
Assignee: Individual
•
Filing: 1986-02-28
•
Granted: 1990-02-06
•
Expires: 2006-02-28
Abstract
Abstract Novel decoding method and apparatus are disclosed for Huffman or variable-length codes. According to the invention, variable-length code-words are divided into two parts, a variable-length prefix part and the remainder of the code-word which is of fixed-length or approximately so. The variable-length part consists of a series of 1's terminated by a single 0 bit. The number of 1's preceeding the first 0 bit indicates the prefix of a particualr code-word. The code-words are arranged so that the ones with the same prefix have the same length, or as close as possible. With this novel codification, decoding the variable-length code-words is accomplished in two simple steps. In the first step the decoder determines the position of the first 0 bit in the present code-word, using this information to specify a section of the main memory. The second step is to index into that memory section using the remaining part of that code-word, and this retrieve the fixed length representation.
Inventors
- 👤 Gary Kahan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:42
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
141 words
A method for decoding input variable-length code-words wherein each code-word is divided into two parts, a prefix part consisting of the first 0 bit together with all the preceding 1 bits and a remainder part consisting of all the bits following the first 0 bit, whereby fixed-length binary data-symbols corresponding to said input code-words are stored in sections of a decoding table that correspond to the different code-word prefixes, said decoding method comprising the following two steps: first, determining the position of the first 0 bit in each input code-word and thus the code-word prefix, where said prefix specifies a section in the decoding table; and second, using the input bits following the first 0 bit which include the code-word remainder to specify an address in said decoding table section and thus retrieve the data-symbol corresponding to a given input code-word.
Claim 2
Independent Claim
141 words
A method for decoding input variable-length code-words wherein each code-word is divided into two parts, a prefix part consisting of the first 0 bit together with all the preceding 1 bits and a remainder part consisting of all the bits following the first 0 bit, whereby fixed-length binary data-symbols corresponding to said input code-words are stored in sections of a decoding table that correspond to the different code-word prefixes, said decoding method comprising the following two steps: first, determining the position of the first 0 bit in each input code-word and thus the code-word prefix, where said prefix specifies a section in the decoding table; and second, using the input bits following the first 0 bit which include the code-word remainder to specify an address in said decoding table section and thus retrieve the data-symbol corresponding to a given input code-word.
Claim 3
Dependent Claim
48 words
The decoding method set forth in claim 1, wherein an additional code-word prefix is designated, said prefix consisting of all 1 bits, and whereby the first step of said decoding method detects this prefix along with the other code-word prefixes when said prefix occurs in said input code-words.
Claim 4
Dependent Claim
29 words
The decoding method set forth in claim 1, wherein the number of bits used to specify the address in said decoding table section is the same for all prefixes.
Claim 5
Dependent Claim
120 words
The decoding method set forth in claim 1, wherein the number of bits used to specify the address in said decoding table section is not the same for all code-word prefixes, and where said decoding method includes an auxiliary decoding table to specify sections and address lengths of the main data-symbol decoding table, said auxiliary decoding table having entries corresponding to each of the prefixes, in which each auxiliary decoding table entry contains: (a) a base address field used to specify the position of a section in the main decoding table containing the data-symbols, and (b) a remaining length field used to indicate the number of bits needed to specify the addresses of the data-symbols in said decoding table section.
Claim 6
Dependent Claim
20 words
The decoding method set forth in claim 1, wherein the code-words associated with each prefix are of the same length.
Claim 7
Dependent Claim
49 words
The decoding method set forth in claim 1, wherein the code-words associated with each prefix are not of the same length, and where each entry in said decoding table contains a remaining length field together with a binary data-symbol to indicate the actual remaining length of the corresponding code-word.
Claim 8
Dependent Claim
149 words
Apparatus for decoding input variable-length code-words wherein each code-word has a prefix part consisting of the first 0 bit together with all the preceding 1 bits and a remainder part consisting of all the bits following the first 0 bit, said apparatus comprising: (a) a memory where fixed-length binary data-symbols corresponding to said input code-words are stored, having sections therein that correspond to the different code-word prefixes; (b) first means responsive to the input code-words for determining the position of the first 0 bit in each input code-word and thus the code-word prefix; (c) second means responsive to said position for specifying a section in the memory; (d) third means responsive to the input bits following a first 0 bit which include the code-word remainder for specifying an address in a memory section; and (e) fourth means for retrieving from the memory the data-symbol stored at the addressed location.
Claim 9
Dependent Claim
149 words
Apparatus for decoding input variable-length code-words wherein each code-word has a prefix part consisting of the first 0 bit together with all the preceding 1 bits and a remainder part consisting of all the bits following the first 0 bit, said apparatus comprising: (a) a memory where fixed-length binary data-symbols corresponding to said input code-words are stored, having sections therein that correspond to the different code-word prefixes; (b) first means responsive to the input code-words for determining the position of the first 0 bit in each input code-word and thus the code-word prefix; (c) second means responsive to said position for specifying a section in the memory; (d) third means responsive to the input bits following a first 0 bit which include the code-word remainder for specifying an address in a memory section; and (e) fourth means for retrieving from the memory the data-symbol stored at the addressed location.
Claim 10
Dependent Claim
48 words
Apparatus as set forth in claim 7, wherein an additional code-word prefix is designated, said prefix consisting of all 1 bits, and whereby means for detecting this prefix along with the other code-word prefixes when said prefix occurs in said input code-words, is included in said first means.
Claim 11
Dependent Claim
29 words
Apparatus as set forth in claim 7, wherein said first means comprises a counter which counts the number of 1 bits before the first 0 bit in each code-word.
Claim 12
Dependent Claim
40 words
Apparatus as set forth in claim 7, wherein said first means comprises bit logic which operates directly on a number of input bits, equal to the length of the longest prefix, to detect the first 0 bit in each code-word.
Claim 13
Dependent Claim
105 words
Apparatus as set forth in claim 7, wherein the number of bits used by said third means to specify an address in a memory section is not the same for all code-word prefixes, and where said apparatus further includes another memory, having entries corresponding to each of the prefixes, in which each entry contains: (a) a base address field used by said second means to specify the position of a section in the memory containing the data-symbols, and (b) a remaining length field used to indicate the number of bits needed by said third means to specify the addresses of the data-items in said section.
Claim 14
Dependent Claim
64 words
Apparatus as set forth in claim 7, wherein the code-words associated with each prefix are not of the same length, whereby each entry in said memory contains a remaining length field together with a binary data-symbol to indicate the actual remaining length of the corresponding code-word, and where said fourth means retrieves from said memory both said remaining length field together with said data-item.
Claim 15
Dependent Claim
135 words
A process for effecting conversions between variable-length and fixed-length codes comprising the following steps: (a) representing encodable items of information by variable-length code-words of such nature that the code-words can be divided into a variable-length prefix part consisting of a series of 1 bits terminated by a single 0 bit and a remainder part, whose lengths are equal or nearly equal to each other for the same prefix consisting of the remaining bits of the code-word; (c) ascertaining the prefix of the present code-word by detecting the position of the first 0 bit in the code-word; (c) registering the bits following the first 0 bit which include a code-word remainder; and (d) combining said bits with information denoting said prefix to address and retrieve the fixed-length representation of the present code-word from a decoding table.
Claim 16
Dependent Claim
135 words
A process for effecting conversions between variable-length and fixed-length codes comprising the following steps: (a) representing encodable items of information by variable-length code-words of such nature that the code-words can be divided into a variable-length prefix part consisting of a series of 1 bits terminated by a single 0 bit and a remainder part, whose lengths are equal or nearly equal to each other for the same prefix consisting of the remaining bits of the code-word; (c) ascertaining the prefix of the present code-word by detecting the position of the first 0 bit in the code-word; (c) registering the bits following the first 0 bit which include a code-word remainder; and (d) combining said bits with information denoting said prefix to address and retrieve the fixed-length representation of the present code-word from a decoding table.
References Cited (Backward Citations)
US3701111A
Cited
US3717851A
Cited
US3918047A
Cited
US4075622A
Cited
US4118773A
Cited
US4168513A
Cited
US4396906A
Cited
US4558302A
Cited
US4558302B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-02-05 | 1993-08-07 | 1994-02-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-02-05 | 1997-08-07 | 1998-02-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-02-05 | 2001-08-07 | 2002-02-06 | $7700.00 | Window Closed / Lapsed |