An FPGA Architecture to Accelerate the Burrows Wheeler Transform by Using a Linear Sorter
Juan Andres Perez-Celis, José Martínez-Carranza, Alicia Morales-Reyes, Claudia Feregrino-Uribe, René Cumplido · 2016
The Burrows-Wheeler Transform (BWT) has been used in several applications demanding high volume of data and real-time capabilities. Current research focuses on reducing the time to compute the BWT by software or hardware means. This paper presents a novel FPGA architecture based on a Linear Sorter (LS) to efficiently calculate the BWT. The architecture is composed of a control logic and several identical Comparison Units (CU), in order to provide scaling flexibility. The proposed hardware implementation sorts the string as itis fed, substitutes only the required characters and efficiently computes the BWT without knowing the Longest Common Prefix(LCP). The architecture is implemented in an FPGA showing a significant reduction in the cycles required to compute the BWT. The results show that the cycles involved to calculate the BWT are reduced for any given string in comparison to those reported in previous works where the LCP is not known in advance.