Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Parallel Algorithms for Entropy-Coding Techniques

Published

Author(s)

Abdou S. Youssef

Abstract

With the explosion of imaging applications, and due to the massive amounts of imagery data, data compression is essential. Lossless compression also called entropy coding, is of special importance because not only it serves as a stand-alone system for certain applications such as medical imaging, it also is an inherent part of lossy compression. Therefore, fast entropy coding/decoding algorithms are desirable. In this paper we will develop parallel algorithms for several widely used entropy coding techniques, namely, arithmetic coding, run-length encoding (RLE), and Huffman coding. Our parallel arithmetic coding algorithm takes O(log2 N) time on an N-processor hypercube, where N is the input size. For RLE, our parallel coding and decoding algorithms take O(log N) time on N processors. Finally, in the case of Huffman coding, the parallel coding algorithm takes O(log2 N + n log n), where n is the alphabet size, n
Citation
- 6113
Report Number
6113

Keywords

arithmetic coding, decoding, Huffman coding, hypercube, parallet algorithms, run-length encoding, statistics gathering

Citation

Youssef, A. (1998), Parallel Algorithms for Entropy-Coding Techniques, - 6113, National Institute of Standards and Technology, Gaithersburg, MD (Accessed February 25, 2024)
Created December 1, 1998, Updated October 16, 2008