A Parallel Huffman Coder on the CUDA Architecture

Rahmani H., TOPAL C., Akinlar C.

IEEE Visual Communications and Image Processing Conference, Valletta, Malta, 7 - 10 December 2014, pp.311-314 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Valletta
  • Country: Malta
  • Page Numbers: pp.311-314
  • Keywords: Huffman coding, variable length coding, CUDA, GPGPU, parallel computing, JPEG
  • Anadolu University Affiliated: Yes


We present a parallel implementation of the widely-used entropy encoding algorithm, the Huffman coder, on the NVIDIA CUDA architecture. After constructing the Huffman codeword tree serially, we proceed in parallel by generating a byte stream where each byte represents a single bit of the compressed output stream. The final step is then to combine each consecutive 8 bytes into a single byte in parallel to generate the final compressed output bit stream. Experimental results show that we can achieve up to 22x speedups compared to the serial CPU implementation without any constraint on the maximum codeword length or data entropy.