http://iet.metastore.ingenta.com
1887

Pipelined decoder for the limited context order Burrows–Wheeler transformation

Pipelined decoder for the limited context order Burrows–Wheeler transformation

For access to this article, please select a purchase option:

Buy eFirst article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • 1. Park, Y., Kim, J.-S.: ‘zFTL: power-efficient data compression support for NAND flash-based consumer electronics devices’, IEEE Trans. Consum. Electron., 2011, 57, (3), pp. 11481156.
    2. 2)
      • 2. Xie, N., Dong, G., Zhang, T.: ‘Using lossless data compression in data storage systems: not for saving space’, IEEE Trans. Comput., 2011, 60, (3), pp. 335345.
    3. 3)
      • 3. Martina, M., Condo, C., Masera, G., et al: ‘A joint source/channel approach to strengthen embedded programmable devices against flash memory errors’, IEEE Embed. Syst. Lett., 2014, 6, (4), pp. 7780.
    4. 4)
      • 4. Li, J., Zhao, K., Zhang, X., et al: ‘How much can data compressibility help to improve NAND flash memory lifetime?’. Proc. 13th USENIX Conf. File and Storage Technologies (FAST15), Santa Clara, CA, February 2015, pp. 227240.
    5. 5)
      • 5. Freudenberger, J., Beck, A., Rajab, M.: ‘A data compression scheme for reliable data storage in non-volatile memories’. IEEE 5th Int. Conf. Consumer Electronics (ICCE), Berlin, September 2015, pp. 139142.
    6. 6)
      • 6. Ahrens, T., Rajab, M., Freudenberger, J.: ‘Compression of short data blocks to improve the reliability of non-volatile flash memories’. Int. Conf. Information and Digital Technologies (IDT), Rzeszow, Poland, July 2016, pp. 14.
    7. 7)
      • 7. Freudenberger, J., Rajab, M., Shavgulidze, S.: ‘A channel and source coding approach for the binary asymmetric channel with applications to MLC flash memories’. 11th Int. ITG Conf. Systems, Communications and Coding (SCC), Hamburg, February 2017, pp. 14.
    8. 8)
      • 8. Dolecek, L., Cassuto, Y.: ‘Channel coding for nonvolatile memory technologies: theoretical advances and practical considerations’, Proc. IEEE, 2017, 105, (9), pp. 17051724.
    9. 9)
      • 9. Freudenberger, J., Rajab, M., Shavgulidze, S.: ‘A source and channel coding approach for improving flash memory endurance’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2018, 26, pp. 110.
    10. 10)
      • 10. Burrows, M., Wheeler, D.: ‘A block-sorting lossless data compression algorithm’. SRC Research Report 124, Digital Systems Research Center, Palo Alto, CA, 1994.
    11. 11)
      • 11. Kruse, H., Mukherjee, A.: ‘Improving text compression ratios with the Burrows-Wheeler transform’. Data Compression Conf., Los Alamitos, March 1999, p. 536.
    12. 12)
      • 12. Effros, M., Visweswariah, K., Kulkarni, S.R., et al: ‘Universal lossless source coding with the Burrows Wheeler transform’, IEEE Trans. Inf. Theory, 2002, 48, (5), pp. 10611081.
    13. 13)
      • 13. Elsayed, H.A., Alghoniemy, M.: ‘Lossless audio coding using Burrows-Wheeler transform and move-to-front coding’. Int. Conf. Computer Engineering Systems, Cairo, Egypt, November 2007, pp. 209212.
    14. 14)
      • 14. Szecowka, P.M., Mandrysz, T.: ‘Towards hardware implementation of bzip2 data compression algorithm’. 16th Int. Conf. Mixed Design of Integrated Circuits Systems (MIXDES), Lodz, Poland, June 2009, pp. 337340.
    15. 15)
      • 15. Liu, Y., Hankeln, T., Schmidt, B.: ‘Parallel and space-efficient construction of Burrows-Wheeler transform and suffix array for big genome data’, IEEE/ACM Trans. Comput. Biol. Bioinf., 2016, 13, (3), pp. 592598.
    16. 16)
      • 16. Elias, P.: ‘Interval and recency rank source coding: two on-line adaptive variable-length schemes’, IEEE Trans. Inf. Theory, 1987, 33, (1), pp. 310.
    17. 17)
      • 17. Willems, F.: ‘Universal data compression and repetition times’, IEEE Trans. Inf. Theory, 1989, 35, (1), pp. 5458.
    18. 18)
      • 18. Huffman, D.A.: ‘A method for the construction of minimum-redundancy codes’, Proc. IRE, 1952, 40, (9), pp. 10981101.
    19. 19)
      • 19. Bentley, J.L., Sleator, D.D., Tarjan, R.E., et al: ‘A locally adaptive data compression scheme’, Commun. ACM, 1986, 29, (4), pp. 320330. doi: 10.1145/5684.5688.
    20. 20)
      • 20. Gutman, M.: ‘Fixed-prefix encoding of the integers can be Huffman-optimal’, IEEE Trans. Inf. Theory, 1990, 36, (4), pp. 936938.
    21. 21)
      • 21. Sayir, J., Spieler, I., Portmann, P.: ‘Conditional recency-ranking for source coding’. Proc. IEEE Information Theory Workshop, June 1996, pp. 61.
    22. 22)
      • 22. Schindler, M.: ‘A fast block-sorting algorithm for lossless data compression’. Data Compression Conf., Snowbird, UT, USA, March 1997, p. 469.
    23. 23)
      • 23. Balkenhol, B., Kurtz, S., Shtarkov, Y.: ‘Modifications of the Burrows and Wheeler data compression algorithm’. Proc. Data Compression Conf. (DCC99), Snowbird, UT, USA, March 1999, pp. 188197.
    24. 24)
      • 24. Martinez, J., Cumplido, R., Feregrino, C.: ‘An FPGA-based parallel sorting architecture for the Burrows Wheeler transform’. Int. Conf. Reconfigurable Computing and FPGAs, Puebla City, Mexico, September 2005, pp. 17.
    25. 25)
      • 25. Arming, S., Fenkhuber, R., Handl, T.: ‘Data compression in hardware – the Burrows-Wheeler approach’. 13th IEEE Symp. Design and Diagnostics of Electronic Circuits and Systems, Vienna, Austria, April 2010, pp. 6065.
    26. 26)
      • 26. Cheema, U.I., Khokhar, A.A.: ‘A high performance architecture for computing Burrows-Wheeler transform on FPGAs’. Int. Conf. Reconfigurable Computing and FPGAs, Cancun, Mexico, December 2013, pp. 16.
    27. 27)
      • 27. Hayashi, S., Taura, K.: ‘Parallel and memory-efficient Burrows-Wheeler transform’. 2013 IEEE Int. Conf. Big Data, Silicon Valley, CA, USA, October 2013, pp. 4350.
    28. 28)
      • 28. Dong, S., Wang, X., Wang, X.: ‘A novel high-speed parallel scheme for data sorting algorithm based on FPGA’. 2009 2nd Int. Congress on Image and Signal Processing, Tianjin, China, October 2009, pp. 14.
    29. 29)
      • 29. Nong, G., Zhang, S.: ‘Efficient algorithms for the inverse sort transform’, IEEE Trans. Comput., 2007, 56, (11), pp. 15641574.
    30. 30)
      • 30. Nong, G., Zhang, S., Chan, W.H.: ‘Computing the inverse sort transform in linear time’, ACM Trans. Algorithms, 2011, 7, (2), pp. 27:127:16. doi: 10.1145/1921659.1921673.
    31. 31)
      • 31. Culpepper, J.S., Petri, M., Puglisi, S.J.: ‘Revisiting bounded context block-sorting transformations’, Softw. Pract. Exper., 2012, 42, (8), pp. 10371054. doi: 10.1002/spe.1112.
    32. 32)
      • 32. Lin, M.-B.: ‘A hardware architecture for the LZW compression and decompression algorithms based on parallel dictionaries’, J. VLSI Signal Process. Syst. Signal Image Video Technol., 2000, 26, (3), pp. 369381.
    33. 33)
      • 33. Freudenberger, J., Rajab, M., Rohweder, D., et al: ‘A codec architecture for the compression of short data blocks’, J. Circuits Syst. Comput., 2018, 27, (2), pp. 117.
    34. 34)
      • 34. Bell, T., Cleary, J., Witten, I.: ‘Text compression’ (Prentice Hall, Englewood Cliffs, NJ, 1990).
    35. 35)
      • 35. Powell, M.: ‘Evaluating lossless compression methods’. New Zealand Computer Science Research Students’ Conf., Canterbury, 2001, pp. 3541.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2017.0496
Loading

Related content

content/journals/10.1049/iet-cds.2017.0496
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address