Hardware Acceleration of rANS Decoder

Abstract

The rANS algorithm, (range Asymmetric Numeral System), is a popular lossless data compression technique based on probability distributions of a symbol alphabet. Several ANS variants exist, but the rANS variant makes clever tradeoffs that support practical use cases. The simplicity of the decoding portion of this algorithm lends itself to efficient hardware acceleration. Building a dedicated logic circuit to implement the rANS decoding equations directly allows one to update the rANS state on every clock cycle. In a software solution, the rANS equations are calculated over many steps. Memory moves to store intermediate values take even more cycles. This research introduces a simple digital logic design using a finite state machine that will decode one symbol per clock with no other latencies and no circuit elements duplicated for parallel operations. It implements one decoder without pipelining or other methods to hide parallel operations. It assumes no specific hardware or CPU architecture and measure performance in clock cycles per decoding operation.