Youssef, A.
(1998),
Parallel Algorithms for Entropy-Coding Techniques, - 6113, National Institute of Standards and Technology, Gaithersburg, MD
(Accessed May 5, 2024)
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)
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, nCitation
- 6113
Report Number
6113
Pub Type
NIST Pubs
Keywords
arithmetic coding, decoding, Huffman coding, hypercube, parallet algorithms, run-length encoding, statistics gathering
Citation
Created December 1, 1998, Updated October 16, 2008