Fast minimum-redundancy prefix coding for real-time space data compression

Bormin Huang

doi:10.1117/12.738370

1 October 2007 Fast minimum-redundancy prefix coding for real-time space data compression

Bormin Huang

Proceedings Volume 6683, Satellite Data Compression, Communications, and Archiving III; 66830H (2007) https://doi.org/10.1117/12.738370
Event: Optical Engineering + Applications, 2007, San Diego, California, United States

Abstract

The minimum-redundancy prefix-free code problem is to determine an array l = {l₁ ,..., f_n} of n integer codeword lengths, given an array f = {f₁ ,..., f_n} 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.

Citation Download Citation

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); https://doi.org/10.1117/12.738370

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available