Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Pipelined decoder for the limited context order Burrows–Wheeler transformation

© The Institution of Engineering and Technology
Received 17/11/2017, Accepted 18/04/2018, Revised 14/03/2018, Published 20/04/2018

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.

Inspec keywords: inverse transforms; data compression; sorting; decoding

Other keywords: fast encoding; memory-efficient pipelined decoder; pipelined decoder; reversible block sorting transform; limited context order BWT decoding; fast inverse BWT; limited context order Burrows–Wheeler transformation; data compression algorithms

Subjects: Codes; Integral transforms; Combinatorial mathematics

References

    1. 1)
      • 22. Schindler, M.: ‘A fast block-sorting algorithm for lossless data compression’. Data Compression Conf., Snowbird, UT, USA, March 1997, p. 469.
    2. 2)
      • 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. 139–142.
    3. 3)
      • 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. 43–50.
    4. 4)
      • 31. Culpepper, J.S., Petri, M., Puglisi, S.J.: ‘Revisiting bounded context block-sorting transformations’, Softw. Pract. Exper., 2012, 42, (8), pp. 1037–1054. doi: 10.1002/spe.1112.
    5. 5)
      • 10. Burrows, M., Wheeler, D.: ‘A block-sorting lossless data compression algorithm’. SRC Research Report 124, Digital Systems Research Center, Palo Alto, CA, 1994.
    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. 1–4.
    7. 7)
      • 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. 60–65.
    8. 8)
      • 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. 335–345.
    9. 9)
      • 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. 77–80.
    10. 10)
      • 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. 1–7.
    11. 11)
      • 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. 337–340.
    12. 12)
      • 18. Huffman, D.A.: ‘A method for the construction of minimum-redundancy codes’, Proc. IRE, 1952, 40, (9), pp. 1098–1101.
    13. 13)
      • 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. 1–10.
    14. 14)
      • 16. Elias, P.: ‘Interval and recency rank source coding: two on-line adaptive variable-length schemes’, IEEE Trans. Inf. Theory, 1987, 33, (1), pp. 3–10.
    15. 15)
      • 17. Willems, F.: ‘Universal data compression and repetition times’, IEEE Trans. Inf. Theory, 1989, 35, (1), pp. 54–58.
    16. 16)
      • 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. 1–4.
    17. 17)
      • 21. Sayir, J., Spieler, I., Portmann, P.: ‘Conditional recency-ranking for source coding’. Proc. IEEE Information Theory Workshop, June 1996, pp. 61.
    18. 18)
      • 35. Powell, M.: ‘Evaluating lossless compression methods’. New Zealand Computer Science Research Students’ Conf., Canterbury, 2001, pp. 35–41.
    19. 19)
      • 11. Kruse, H., Mukherjee, A.: ‘Improving text compression ratios with the Burrows-Wheeler transform’. Data Compression Conf., Los Alamitos, March 1999, p. 536.
    20. 20)
      • 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. 1–4.
    21. 21)
      • 8. Dolecek, L., Cassuto, Y.: ‘Channel coding for nonvolatile memory technologies: theoretical advances and practical considerations’, Proc. IEEE, 2017, 105, (9), pp. 1705–1724.
    22. 22)
      • 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. 1–17.
    23. 23)
      • 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. 1148–1156.
    24. 24)
      • 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. 227–240.
    25. 25)
      • 30. Nong, G., Zhang, S., Chan, W.H.: ‘Computing the inverse sort transform in linear time’, ACM Trans. Algorithms, 2011, 7, (2), pp. 27:1–27:16. doi: 10.1145/1921659.1921673.
    26. 26)
      • 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. 592–598.
    27. 27)
      • 29. Nong, G., Zhang, S.: ‘Efficient algorithms for the inverse sort transform’, IEEE Trans. Comput., 2007, 56, (11), pp. 1564–1574.
    28. 28)
      • 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. 1061–1081.
    29. 29)
      • 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. 1–6.
    30. 30)
      • 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. 209–212.
    31. 31)
      • 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. 369–381.
    32. 32)
      • 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. 188–197.
    33. 33)
      • 34. Bell, T., Cleary, J., Witten, I.: ‘Text compression’ (Prentice Hall, Englewood Cliffs, NJ, 1990).
    34. 34)
      • 19. Bentley, J.L., Sleator, D.D., Tarjan, R.E., et al: ‘A locally adaptive data compression scheme’, Commun. ACM, 1986, 29, (4), pp. 320–330. doi: 10.1145/5684.5688.
    35. 35)
      • 20. Gutman, M.: ‘Fixed-prefix encoding of the integers can be Huffman-optimal’, IEEE Trans. Inf. Theory, 1990, 36, (4), pp. 936–938.
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
Print this page
This is a required field
Please enter a valid email address