VLSI VLSI EFFICIENT HUFFMAN ENCODING APPARATUS AND METHOD

摘要

A compression algorithm based on Huffman coding that is adapted to be easily implemented using a VLSI design is disclosed. The data file may be processed to replace duplicate data, such as in accordance with the LV algorithm, with copy instructions, including offset and length. The Huffman code can then be generated for portions of the file. The Huffman code can be generated according to a novel method of generating Huffman code lengths for literals in a data file without first sorting the literal statistics. The Huffman code lengths may be constrained not to be longer than the maximum length, and the Huffman codes may be modified to provide an acceptable overflow probability and be in standard order. The literals, offsets, and lengths can be separately encoded. Different values for these data sets may be allocated for a limited number of intervals for purposes of generating usage statistics used to generate Huffman codes.