Fast Huffman Decoding by Exploiting Data Level Parallelism

Tim Drijvers1,  Carlos Alba Pinto2,  Henk Corporaal1,  Bart Mesman1
1Eindhoven University of Technology, 2Silicon Hive


Abstract

The frame rates and resolutions of digital videos are on the ricing edge. Thereby, pushing the compression ratios of video coding standards to their limits, resulting in more complex and computational power hungry algorithms. Programmable solutions are gaining interest to keep up the pace of the evolving video coding standards, by reducing the time-to-market of upcoming video products. However, to compete with hardwired solutions, parallelism needs to be exploited on as many levels as possible. In this paper the focus will be on data level parallelism. Huffman coding is proven to be very efficient and therefore commonly applied in many coding standards. However, due to the inherently sequential nature, parallelization of the Huffman decoding is considered hard. The proposed fully flexible and programable acceleration exploits available data level parallelism in Huffman decoding. Our implementation achieves a decoding speed of 106 MBit/s while running on a 250 MHz processor. This is a speed-up of 24x compared to our sequential reference implementation.