Open AccessPipelined decoder for the limited context order Burrows–Wheeler transformation
Author(s) -
Safieh Malek,
Freudenberger Jürgen
Publication year - 2019
Publication title -
iet circuits, devices and systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.251
H-Index - 49
eISSN - 1751-8598
pISSN - 1751-858X
DOI - 10.1049/iet-cds.2017.0496
Subject(s) - computer science , decoding methods , encoding (memory) , pipeline (software) , transformation (genetics) , parallel computing , context (archaeology) , sorting , block (permutation group theory) , soft decision decoder , data compression , algorithm , artificial intelligence , mathematics , programming language , biochemistry , biology , gene , paleontology , chemistry , geometry
The Burrows–Wheeler transformation (BWT) is a reversible block sorting transform that is an integral part of many data compression algorithms. This work proposes a memory‐efficient pipelined decoder for the BWT. In particular, the authors consider the limited context order BWT that has low memory requirements and enable fast encoding. However, the decoding of the limited context order BWT is typically much slower than the encoding. The proposed decoder pipeline provides a fast inverse BWT by splitting the decoding into several processing stages which are executed in parallel.