AN UNRESTRICTEDLY PARALLEL SCHEME FOR ULTRA-HIGH-RATE REPROGRAMMABLEHUFFMAN CODING

This paper proposes a comprehensivemethod for overcoming the inherently serial nature of variable-length near-entropy coding to obtain unrestrictedly parallel realizations of Huffman compression. A codestream rearrangement technique together with a symbol-stream order-recoveryprocedure form a concurrent approach capable of exceeding all previously attainablecoderate figures. Furthermore, the method is noteworthy for achieving 100% hardwareutilization with no coderate overhead while maintaining data output in a traditional streamed format. To further this endeavor, bit-serial encoder and decoder designs that possess compelling speed and area advantages are developed for service as parallel processing elements. However, both are suitable in more general contexts as well. The decoder, in particular, is optimally fast. The encoder and decoder designs are programmable, thus suggesting the appropriateness of the composite approach for a general-purpose ultra-high-speed codec. Benefits for low-power and variable-rateapplications are briefly discussed.