An FPGA Parallel Sorting Architecture for the Burrows Wheeler Transform

Abstract

Burrows-Wheeler transform (BWT) has received special attention due to its effectiveness in lossless data compression algorithms. However, implementations of BWT-based algorithms have been limited due to the complexity of the suffix sorting process applied to the input string. Proposed solutions involve data structures combined with hardware architectures aimed at reducing computational complexity. However, advanced data structures are difficult to be implemented directly into hardware architectures as they require sophisticated control units. In this paper we present a novel architecture based on a parallel sorting block to implement the BWT transform. The proposed architecture has been implemented on a field programmable gate array (FPGA) device providing good performance improvements compared with other reported implementations on FPGAs. Results obtained show a reduction in the number of cycles and an increase in the maximum frequency compared with other works. FPGA implementation results are presented and discussed.