Data compression in hardware — The Burrows-Wheeler approach

Abstract

Nowadays, data compression is used in nearly every field of digital applications. Many efforts have been taken to improve the theory of compression algorithms, albeit these approaches are mostly suitable for software implementation. Hardware implementations are sometimes suggested, but in general rarely found. Many approaches rely on some kind of LZ-method, which are generally fast but lack compression rate. This paper focuses on the Burrows-Wheeler Transform (BWT) as it is becoming increasingly important through the many benefits it provides and potentially even more so, if implemented in hardware. Two methods of the forward transform are compared and tested at realistic block sizes. Furthermore a implementation of a bzip2 compression system for Field programmable gate arrays (FPGAs) is described.