Parallel Algorithms for Entropy-Coding Techniques

Published

December 1, 1998

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(log² 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(log² N + n log n), where n is the alphabet size, n

Citation

- 6113

Report Number

6113

Pub Type

NIST Pubs

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 November 8, 2024)