Low-complexity two instructions set computer for suffix sort in burrow wheeler transform

J H Kong; Li-Minn Ang; K P Seng

doi:10.1109/ACSAT.2012.61

Back

Low-complexity two instructions set computer for suffix sort in burrow wheeler transform

Conference paper

Peer reviewed

Low-complexity two instructions set computer for suffix sort in burrow wheeler transform

J H Kong, Li-Minn Ang and K P Seng

Proceedings of the 2012 International Conference on Advanced Computer Science Applications and Technologies, ACSAT 2012, Vol.1, pp.181-186

International Conference on Advanced Computer Science Applications and Technologies (ACSAT), 2012 (Kuala Lumpur, Malaysia, 26-Nov-2012–28-Nov-2012)

Institute of Electrical and Electronics Engineers

2012

DOI: https://doi.org/10.1109/ACSAT.2012.61

Files and links (1)

url

https://doi.org/10.1109/ACSAT.2012.61View

Published Version

Abstract

Burrow-Wheeler transform

BWT

BWCA

URISC

computer architecture

FPGA

suffix sort

hardware decryption languages

TISC

block sorting compression

The Burrow Wheelers Transform (also called the block sorting compression) was referred to as the jewel loss less compression due its effectiveness and is used as the core algorithm in bzip2 compressor. With much attention given, hardware realization of the BWT algorithm has been limited due to the complexity of suffix sorting computation. Given the small hardware-footprint design trend, we propose the use of a reconfigurable FPGA platform and unified computer architecture with minimal hardware components. In this paper, we are presenting a low-complexity two instructions set computer architecture (TISC) for the lexicographical sorting in Burrow Wheelers Transform. The proposed architecture has been implemented and tested using the DK Design Suite software environment, which provides a Handel-C Hardware Descriptive language to ease the design process. A Celoxica RC10 board which houses the Spartan 3 XCS1500L-4 FPGA is used.

Details

Title: Low-complexity two instructions set computer for suffix sort in burrow wheeler transform
Authors: J H Kong (Author) - University of Nottingham Malaysia Campus
Li-Minn Ang (Author) - Edith Cowan University
K P Seng (Author) - Sunway University
Publication details: Proceedings of the 2012 International Conference on Advanced Computer Science Applications and Technologies, ACSAT 2012, Vol.1, pp.181-186
Conference details: International Conference on Advanced Computer Science Applications and Technologies (ACSAT), 2012 (Kuala Lumpur, Malaysia, 26-Nov-2012–28-Nov-2012)
Publisher: Institute of Electrical and Electronics Engineers
Date published: 2012
DOI: 10.1109/ACSAT.2012.61; 10.1109/ACSAT31133.2012
ISBN: 9780769549590
Organisation Unit: University of the Sunshine Coast, Queensland; School of Science, Technology and Engineering; Engage Research Lab
Language: English
Record Identifier: 99513801902621
Output Type: Conference paper

Metrics

12 Record Views