EP0577330A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Improved variable length decoder
Assignee: AT&T Inc
•
Filing: 1993-06-24
•
Granted: —
•
Expires: 2013-06-24
Abstract
Abstract Apparatus for decoding a stream containing codes of a variable length code (VLC) takes advantage of the fact that a trie representation of the VLC can be pruned to leaves that each represent a complete binary trie. Combinational circuits or ROMs are then employed to decode the pruned trie, thereby substantially reducing the complexity of decoding a VLC. In one embodiment the decoding problem is partitioned into segments by considering a few bits at a time, starting with the most significant bits. Each segment either outputs a valid code or informs the next segment that the decoding process is incomplete and provides information to assist the next segment in its decoding effort. In applications where the VL code can be selected for greater efficiency of the decoder, the offered VL code can be restructured to minimize the number of k-nodes, to thereby minimize the pruned trie, and to concomitantly minimize the sizes of the ROMs in the decoder.
Inventors
- 👤 George J. Kustka
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-06 09:29
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425; H04; H04L; H04L9/00; H04L9/06; H04L9/065; H04N; H04N19/00; H04N19/44; H04L2209/00; H04L2209/12; H04L2209/125; H04L2209/34; H04N19/10; H04N19/102; H04N19/13; H04N19/60; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
130 words
Apparatus for decoding a stream of signals encoded with given a variable-length code (VLC) comprising: first means (10) for presenting a number of bits of said stream of signals, which number is at least equal to the number of bits in the longest code of said VLC; a plurality of processing blocks (100,120,110,130), interconnected in a chain such that each processing block in the chain, other than the last processing block in the chain, feeds information to a next processing block in the chain, and further interconnected so that each processing block is responsive to responsive to a different group of adjacent bits presented by the first means and, in response to received information from the previous block and the group of adjacent bits, identifies a subset of said VLC.
Claim 2
Dependent Claim
130 words
Apparatus for decoding a stream of signals encoded with given a variable-length code (VLC) comprising: first means (10) for presenting a number of bits of said stream of signals, which number is at least equal to the number of bits in the longest code of said VLC; a plurality of processing blocks (100,120,110,130), interconnected in a chain such that each processing block in the chain, other than the last processing block in the chain, feeds information to a next processing block in the chain, and further interconnected so that each processing block is responsive to responsive to a different group of adjacent bits presented by the first means and, in response to received information from the previous block and the group of adjacent bits, identifies a subset of said VLC.
Claim 3
Dependent Claim
25 words
The apparatus of claim 1 wherein each processing block comprises a read-only memory responsive to at least a subset of the group of adjacent bits.
Claim 4
Dependent Claim
57 words
The apparatus of claim 1 wherein each of the processing blocks decodes a portion of a trie that is pruned down to its k-nodes, where a k-node is a node of the trie which supports a binary number of leaves of any particular number code length and which has no k-nodes in its path toward the root.
Claim 5
Dependent Claim
52 words
The apparatus of claim 1 wherein the information communicated from each processing block in the chain to the next processing block in the chain is an indication as to whether a VLC code has been identified. comprises a read-only memory responsive to at least a subset of the group of adjacent bits.
Claim 6
Dependent Claim
29 words
The apparatus of claim 4 wherein the information communicated from at least one processing block in the chain to the next processing block in the chain includes state information.
Claim 7
Dependent Claim
31 words
The apparatus of claim 4 wherein the information communicated from each of the processing blocks in the chain to the next processing block in the chain includes a VLC identifier signal.
Claim 8
Dependent Claim
40 words
The apparatus of claim 1 wherein said plurality of processing blocks develops a unique address for each decoded VLC and further comprises a storage means (400), responsive to the developed unique address, for converting the address into a fixed-length code.
Claim 9
Dependent Claim
38 words
The apparatus of claim 1 further comprising: combinatorial means (410) responsive to the first means for determining the length of a currently to be decoded code of the VLC; and clocked storage means interposed between selected processing blocks.
Claim 10
Dependent Claim
21 words
The apparatus of claim 8 wherein the combinational means take advantage of k-nodes found in a trie representation of the VLC.
Claim 11
Dependent Claim
93 words
A VLC decoder having an input register (10) for storing a portion of a stream of input signals and a decoder block (400, 500, 510, 520, 530, 540, 550) responsive to the register output signals, which decoder block includes a ROM (500), characterized in that: The ROM contains information that decodes a trie that is pruned down to its k-nodes, where a k-node is a node of the trie which supports a binary number of leaves of any particular number code length and which has no k-nodes in its path toward the root.
Claim 12
Dependent Claim
93 words
A VLC decoder having an input register (10) for storing a portion of a stream of input signals and a decoder block (400, 500, 510, 520, 530, 540, 550) responsive to the register output signals, which decoder block includes a ROM (500), characterized in that: The ROM contains information that decodes a trie that is pruned down to its k-nodes, where a k-node is a node of the trie which supports a binary number of leaves of any particular number code length and which has no k-nodes in its path toward the root.
Claim 13
Dependent Claim
81 words
The decoder of claim 10 wherein the decoder block includes: a state register (510) responsive to a first portion of the output of the ROM, which register is clocked with a clock signal and delivered its clocked output to address inputs of the ROM, thereby making the decoder block a finite state machine; and means for concatenating (530) second portion of the output of the ROM with output signals of the input register to form an output signal of the decoder.
Claim 14
Dependent Claim
40 words
The decoder of claim 11 further comprising means (540) for selecting the number of output signals of the input register that are concatenated in the means for concatenating under control of a fourth portion of the output of the ROM.
Claim 15
Dependent Claim
31 words
The decoder of claim 11 furt her comprising a h it flag at t he output of t he ROM t hat captures the information concatenated in the means for concatenating.
Claim 16
Dependent Claim
16 words
The decoder of claim 13 further comprising a ROM (400) responsive to the means for concatenating.
Claim 17
Dependent Claim
28 words
The decoder of claim 11 further comprising a control circuit (550) that shifts data in the input register in responsive to a fifth portion of the ROM output.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.