Miscellaneous active electrical nonlinear devices – circuits – and – Specific signal discriminating without subsequent control – By amplitude
Reexamination Certificate
2000-03-16
2001-08-07
Lam, Tuan T. (Department: 2816)
Miscellaneous active electrical nonlinear devices, circuits, and
Specific signal discriminating without subsequent control
By amplitude
C327S065000
Reexamination Certificate
active
06271689
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the processing of digital data to effect variable-length encoding.
2. Description of Related Art
Variable-length coding (VLC) commands a dominant role in data compression as a result of its speed and simplicity. However, the very trends that commend its employ—the growth in data volume and increasing transmission rates—have preponderated to threaten its ability to palliate them. The art of VLC encoding has therefore focused on speed, yet with deference to circuit size.
A mapping between fixed-length input data, termed symbols, and variable-length output data, termed codewords, constitutes a codetable. The codetable singularly determines most of the structure, and consequently most of the performance characteristics, of an encoder. This codetable usually takes one of two forms: a compact tree-based arrangement or a larger direct tabulation. The tree-based arrangement was originally a decoding device, but has recently been transferred to the encoding domain. In support of decoding, its attributes are highly desirable. By contrast, the arrangement proves awkward with encoding. Much of the art has therefore attempted to reconcile it with encoding. This endeavor has met with only limited success. Some art mitigates the size advantage the arrangement suggests over direct tabulation. Other art requires post-encoding reversal operations that introduce undesirable variable latency between the output of the primary encoder and output of post-encoding hardware.
Direct tabulation, by virtue of its directness, should be fast. It is often not as compact as desired, though. Because codewords are variable in length, indication of the length of each codeword is required. This may be accomplished in a number of ways, all of which necessitate some concessions. For example, length may be stored explicitly alongside codewords, as an associated value of each symbol. This obviously consumes precious memory space. Alternatively, codewords of equal length may be grouped, with length and associated memory ranges specified separately. This approach restricts the type of code to which the encoder applies, e.g., the Huffinan-Shannon-Fano code would be supported, but general Huffinan codes would not. It also results in complex—and hence slow—processing.
Note that any scheme that explicitly stores a length value in any manner must employ arithmetic operations in releasing the recalled codeword to the output. Most often a unit decrement operation is utilized, reducing the length by one each time a bit of the codeword is output. Such an operation, while intrinsically simple, is often responsible for over half of the delay in a processing cycle.
SUMMARY OF THE INVENTION
The present invention describes a processing means for the variable-length encoding of digital signals. The resultant serial encoder admits symbols at data-dependent intervals and progressively releases one bit of encoded output each cycle. The encoder comprises storage, a shifter and a simple pattern tester. Excepting the pattern tester, no arithmetic operations are involved. These three parts are arranged such that processing speed is limited by the greater of the retrieval delay from storage and the delay of the pattern tester. This arrangement is made feasible by an implicit means of codeword length storage. Optimal encoding rates for a serial encoder may hereby be obtained.
OBJECTS AND ADVANTAGES OF THE INVENTION
It is a primary object and advantage of the present invention that optimal rates of operation may be obtained.
It is a significant object and advantage of this invention that memory requirements are low as a result of the avoidance of storage of explicit length information.
It is a clear advantage of this invention that composing parts are few and simple, and connections among parts are likewise trivial.
It is a strong advantage of this invention that formatting of variable-length codewords in larger fixed-length memory cells is trivially accomplished.
It is a noteworthy advantage of the present invention that the codes are online or offline reprogrammable since simple direct storage is employed. Because codes are not hardwired, as is sometimes done in the art, the invention has utility spanning both general and specific regimes. It is a definite advantage of this invention that output is delivered without post-encoding hardware, hence avoiding the imposition of additional latency in variable quantities.
REFERENCES:
patent: 5309156 (1994-05-01), Fujiyama
patent: 5404138 (1995-04-01), Kim et al.
patent: 5929793 (1999-07-01), Choi
Freking Robert Allen
Parhi Keshab K.
LandOfFree
Fast and small serial variable length encoder with 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 variable length encoder with an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and small serial variable length encoder with an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539997