Translator Disclaimer
1 October 2007 Fast minimum-redundancy prefix coding for real-time space data compression
Author Affiliations +
The minimum-redundancy prefix-free code problem is to determine an array l = {l1 ,..., fn} of n integer codeword lengths, given an array f = {f1 ,..., fn} of n symbol occurrence frequencies, such that the Kraft-McMillan inequality [equation] holds and the number of the total coded bits [equation] is minimized. Previous minimum-redundancy prefix-free code based on Huffman's greedy algorithm solves this problem in O (n) time if the input array f is sorted; but in O (n log n) time if f is unsorted. In this paper a fast algorithm is proposed to solve this problem in linear time if f is unsorted. It is suitable for real-time applications in satellite communication and consumer electronics. We also develop its VLSI architecture that consists of four modules, namely, the frequency table builder, the codeword length table builder, the codeword table builder, and the input-to-codeword mapper.
© (2007) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Bormin Huang "Fast minimum-redundancy prefix coding for real-time space data compression", Proc. SPIE 6683, Satellite Data Compression, Communications, and Archiving III, 66830H (1 October 2007);

Back to Top