A Huffman-type code generator with order-N complexity

A new method with order-N complexity is presented to construct Huffman-type minimum-redundancy codes for N distinguished symbols in the source alphabets. This method includes a contraction process as well as an expansion process. The contraction process has (N-3) contraction stages. To reduce the data-transfer operations, (N-5) vacancies are reserved beforehand in the array which is used to store the probabilities of symbols. At each contraction stage, the number of the symbols whose probabilities are equal to or less than the sum of the two least probabilities is stored and named as the expansion index. Under the contraction process, the code lengths of the original symbols and those at each contraction stage increase monotonically. Since the proposed method gives a monotonically increasing code both in code length and in code value, its implementation becomes easy in VLSI technology, in microprocessor-based systems, or in software programming