US3918047A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Decoding circuit for variable length codes
Assignee: AT&T Inc
•
Filing: 1974-03-28
•
Granted: 1975-11-04
•
Expires: 1994-03-28
Abstract
Abstract A tree-structured network of substantially similar logic modules is used to decode butted variable-length code words. Bits of a fixed-length sample from a bit stream sample, which sample has length equal to the maximum allowed code word length, are applied in parallel to respective rows of the tree. When the codes have the prefix property, it is assured that only one row will generate an output at a terminal node. This output uniquely identifies the decoded symbol and, by virtue of its position in the tree, indicates the associated code word length and, therefore, the beginning point for the next code word.
Inventors
- 👤 Peter Bernard Denes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 20:42
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425; H03M7/4025
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
162 words
Apparatus for decoding an input sequence of butted, variablelength prefix code words having a maximum of M digits to derive the corresponding ones of symbols from an output alphabet comprising A. a tree decoding network in which each tree level corresponds uniquely to one of M digit positions, said tree comprising a terminal node for each symbol in said output alphabet, B. means for simultaneously applying M digits from said input sequence to said tree network, each digit being applied to a respective row of said tree, C. first means for detecting which terminal node of said tree has been selected by said M digits, (D) second means for determining the level of said tree at which said terminal node has been selected by said M digits, and (E) third means responsive to said second means for determining the beginning point in said input sequence of the code word immediately following the code word beginning with the first of said M digits.
Claim 2
Dependent Claim
162 words
Apparatus for decoding an input sequence of butted, variablelength prefix code words having a maximum of M digits to derive the corresponding ones of symbols from an output alphabet comprising A. a tree decoding network in which each tree level corresponds uniquely to one of M digit positions, said tree comprising a terminal node for each symbol in said output alphabet, B. means for simultaneously applying M digits from said input sequence to said tree network, each digit being applied to a respective row of said tree, C. first means for detecting which terminal node of said tree has been selected by said M digits, (D) second means for determining the level of said tree at which said terminal node has been selected by said M digits, and (E) third means responsive to said second means for determining the beginning point in said input sequence of the code word immediately following the code word beginning with the first of said M digits.
Claim 3
Dependent Claim
33 words
Apparatus according to claim 1 wherein said second means comprises a plurality of OR gates each arranged to OR output indications from all terminal nodes at a respective level of said tree network.
Claim 4
Dependent Claim
29 words
Apparatus according to claim 1 wherein said tree decoding network comprises means for connecting the input digit signal at any tree level to all nodes at that tree level.
Claim 5
Dependent Claim
48 words
Apparatus according to claim 1 wherein said tree network comprises at each level a plurality of bit detectors for detecting the presence in said input digit signal of either a 1 or a 0, and for controlling the branching to succeeding nodes, if any, based on said detection.
Claim 6
Dependent Claim
74 words
Apparatus according to claim 1 wherein said third means comprises means for storing a numerical count of said level determined by said second means, means for simultaneously decrementing said count and advancing said input data sequence, means for terminating said advancing when said count is decremented to a predetermined value, and means for applying an additional set of M digits from the input sequence to said decoding network when said predetermined value is reached.
References Cited (Backward Citations)
US3634855A
Cited
US3675211A
Cited
US3694813A
Cited
US3701108A
Cited
US3717851A
Cited
US3835467A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1978-11-03 | 1979-05-05 | 1979-11-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1982-11-03 | 1983-05-05 | 1983-11-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1986-11-03 | 1987-05-05 | 1987-11-04 | $7700.00 | Window Closed / Lapsed |