Back to results
US 6,307,489 B1Granted
Fast and small serial huffman decoder for decoding at an optimally high rate
OwnerRobert Allen Freking, Keshab K. Parhiinventors
Life of this patent
Estimating the term…
Abstract
A serial Huffman decoder that is concise and capable of extremely high rates of operation is described. Optimal speed is attained because the critical-path of an embodying circuit has only a memory in the critical path. No other functions or operations are entailed. This being the only unequivocally essential device in the implementation of a mapping such as Huffman, the critical path is blatantly optimal. The codetable, composed of a specially modified Huffman binary tree, is much more compact than the typical Huffman binary tree.
Claims10
A machine for processing Huffman-coded digital signals into decoded signals, comprising:
- (a) storage, which stores a tree arrangement comprising a plurality of entries selected from the group consisting of:
- (1) a regularly disposed symbol, with indicium,
- (2) a regularly disposed index, with indicium, referencing an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) a different entity of regularly disposed index, thereof,
- (3) an oppositely disposed symbol, with indicium, associated with an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- (4) an oppositely disposed index, with indicium, referencing an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- and associated with an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- such that a hierarchy is developed comprising:
- (1) only one unreferenced regularly disposed entry, chosen from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- (2) only one unreferenced oppositely disposed entry, chosen from the group consisting of:
- (I) said oppositely disposed symbol, and
- (II) said oppositely disposed index
- (3) a plurality of referenced entries, such that:
- (1) a sequence of dispositions is formed, by:
- (I) initially focusing concern on an entry from the group consisting of:
- (i) said unreferenced regularly disposed entry, and
- (ii) said unreferenced oppositely disposed entry.
- (II) recursively:
- (i) recording the disposition of a concerned entry
- (ii) changing the focus of concern to an entry selected from the group consisting of:
- (A) said concerned entry's referenced entry, and
- (B) said associated entry of said concerned entry's said referenced entry,
- until said concerned entry is a symbol.
- (2) said sequnce of dispositions is in direct correspondence with a sequence of bit values associated by Huffman coding with said symbol terminating sequence of dispositions thereof,
- (b) a delay connected between the output of said storage and the input of storage thereof, detaining a recalled result from said storage comprising a plurality of bits corresponding to said stored index, controlled by a portion of said recalled result corresponding to said stored indicium,
- (c) an input line delivering Huffman-coded codewords to said storage a bit per cycle, wherein Huffman decoded signal are emitted at said output.
32 more elements
A method for processing Huffman-coded digital signals into decoded signals, comprising:
- (a) storing a tree arrangement comprising a plurality of entries selected from the group consisting of:
- (1) a regularly disposed symbol, with indicium,
- (2) a regularly disposed index, with indicium, referencing an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) a different entity of regularly disposed index, thereof,
- (3) an oppositely disposed symbol, with indicium, associated with an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- (4) an oppositely disposed index, with indicium, referencing an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- and associated with an entry selected from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- such that a hierarchy is developed comprising:
- (1) only one unreferenced regularly disposed entry, chosen from the group consisting of:
- (I) said regularly disposed symbol, and
- (II) said regularly disposed index,
- (2) only one unreferenced oppositely disposed entry, chosen from the group consisting of:
- (I) said oppositely disposed symbol, and
- (II) said oppositely disposed index
- (3) a plurality of referenced entries, such that:
- (1) a sequence of dispositions is formed, by:
- (I) initially focusing concern on an entry from the group consisting of:
- (i) said unreferenced regularly disposed entry, and
- (ii) said unreferenced oppositely disposed entry.
- (II) recursively:
- (i) recording the disposition of a concerned entry
- (ii) changing the focus of concern to an entry selected from the group consisting of:
- (A) said concerned entry's referenced entry, and
- (B) said associated entry of said concerned entry's said referenced entry,
- until said concerned entry is a symbol.
- (2) said sequnce of dispositions is in direct correspondence with a sequence of bit values associated by Huffman coding with said symbol terminating sequence of dispositions thereof,
- (b) recalling an entry according to Huffman-coded codewords presented one bit per step,
- (c) delaying a portion of said recalled entry comprising said stored index by one step according to a portion of said recalled entry comprising said indicium, Huffman decoded symbols are produced.
32 more elements
A machine for processing Huffman-coded digital signals into decoded signals, comprising:
- (a) storage, which stores a pointer-based representation of a Huffman binary tree modified such that:
- (1) the root node is not stored,
- (2) pointers to regularly disposed children are stored, with indicium
- (3) pointers to oppositely disposed children are not stored,
- (4) symbols are stored with indicium, inline in normal child positions of said storage,
- (b) a delay connected between the output of said storage and the input of storage thereof, detaining a recalled result from said storage comprising a plurality of bits corresponding to said stored pointer, controlled by a portion of said recalled result corresponding to said stored indicium,
- (c) an input line delivering Huffman-coded codewords to said storage a bit per cycle, Huffman decoded signal are emitted at said output.
4 more elements
Dependencies are inferred from the claim text.