Share Email Print

Proceedings Paper

Fast minimum-redundancy prefix coding for real-time space data compression
Author(s): Bormin Huang
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 1 October 2007
PDF: 11 pages
Proc. SPIE 6683, Satellite Data Compression, Communications, and Archiving III, 66830H (1 October 2007); doi: 10.1117/12.738370
Show Author Affiliations
Bormin Huang, Univ. of Wisconsin, Madison (United States)

Published in SPIE Proceedings Vol. 6683:
Satellite Data Compression, Communications, and Archiving III
Roger W. Heymann; Bormin Huang; Irina Gladkova, Editor(s)

© SPIE. Terms of Use
Back to Top