Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2000-03-15
2001-10-23
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
C341S079000
Reexamination Certificate
active
06307489
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the processing of digital signals to render Huffman coding with minimal of hardware.
2. Description of Related Art
The digital-signal processing technique of Huffman coding is one of the most pervasive compression means in use today. It has earned a principle position as an enabling component in more sophisticated and specialized compression standards, such as CCITT (facsimile), JPEG (image) and MPEG (video) coding. The art bears this popularity out. Unparalleled speed and simplicity are at the core of its appeal. Yet, known implementations are neither adequately fast nor sufficiently uncomplicated to match the performance demands exacted by modern applications. Most of the art focuses on either reducing memory consumption or raising performance, but few attempt both simultaneous.
A Huffman decoder receives as input a variable-length encoded codeword and generates as output a fixed-length decoded symbol. If the Huffman codetable—the mapping between input codewords and output symbols—is stored directly, the resultant decoder would be fast, but exorbitantly large. This is never done in practice.
The mapping can be decomposed into smaller codetables, where data is processed over each simultaneously with only one responding with a decoding. This approach is fast for large codewords, but the resultant circuits are needlessly complex and consumptive of space.
It is known that the codetable can be stored as a set of pointers implementing a binary tree, with branches associated with codeword bits and leaves associated with symbols. This arrangement is reasonably compact, but requires a unit increment operation. A modification of this arrangement requires less memory at the expense of a variable increment operation. Due to the nature of tree-based storage, such decoders are serial devices, receiving one bit of the codeword per cycle and producing one symbol after all bits of the codeword have been admitted.
Many decoding styles have the potential to process one symbol every cycle. Nevertheless, representatives of this class of coder, such as the mapping decomposition methods mentioned above, have much slower cycle periods than serial-decoder cycle periods as a result of their complexity. Therefore, though for large codewords the effective throughput engendered by releasing a symbol in one cycle is great, for small codewords the effective throughput is obviously worse. Since Huffman coding compresses by assigning small codewords to the most frequently occurring symbols, the ostensibly dramatic throughput of such devices does not, on average, occur. Serial decoders thus prove faster than these in many circumstances.
SUMMARY OF THE INVENTION
The present invention describes a serial Huffman decoder that is concise and capable of extremely high rates of operation. Optimal speed is attained with this invention because the critical-path of an embodying circuit has only a memory in the critical path, thereby minimizing the iteration period. 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.
OBJECTS AND ADVANTAGES OF THE INVENTION
The primary object of this invention is the optimally fast serial processing of Huffman decoding.
It is an advantage of this invention that the critical path of a circuit embodying it is optimally short, consisting only of a memory. No arithmetic operations are entailed. Because Huffman coding involves a mapping of data, a memory is obligatory. Therefore, it is clear that the critical path is optimal.
It is the overriding advantage of this invention that operating speed is optimal for a given implementation of memory. This is a direct consequence of critical path optimality.
It is a clear advantage of this invention that the codetable remains programmable. Codetable programmability is a critical capability for optimizing compression ratios, but much of the art derives performance by forgoing this feature, hardwiring a specific code.
It is a noteworthy advantage of this invention that the modified tree arrangement constituting the codetable of the present invention is stored in roughly half the space of a conventional tree-based codetable.
It is a definite object and advantage of this invention that it is, as a whole, very compact. This follows from the previous advantage together with the fact that the entire invention comprises just a memory and a delay.
REFERENCES:
patent: 5153591 (1992-10-01), Clark
patent: 5583500 (1996-12-01), Allen et al.
patent: 5602550 (1997-02-01), Stein
patent: 5923785 (1999-07-01), Dube
Freking Robert Allen
Parhi Keshab K.
Jean-Pierre Peguy
Jeanglaude Jean Bruner
LandOfFree
Fast and small serial huffman decoder for decoding at an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast and small serial huffman decoder for decoding at an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and small serial huffman decoder for decoding at an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2601269