No Access

A Codec Architecture for the Compression of Short Data Blocks

Jürgen Freudenberger

Institute for System Dynamics, HTWG Konstanz, University of Applied Sciences, Germany

E-mail Address: jfreuden@htwg-konstanz.de

Corresponding author.

Search for more papers by this author

Mohammed Rajab

Institute for System Dynamics, HTWG Konstanz, University of Applied Sciences, Germany

E-mail Address: mrajab@htwg-konstanz.de

Search for more papers by this author

Daniel Rohweder

Institute for System Dynamics, HTWG Konstanz, University of Applied Sciences, Germany

E-mail Address: drohwede@htwg-konstanz.de

Search for more papers by this author

, and

Malek Safieh

Institute for System Dynamics, HTWG Konstanz, University of Applied Sciences, Germany

E-mail Address: msafieh@htwg-konstanz.de

Search for more papers by this author

https://doi.org/10.1142/S0218126618500196Cited by:7 (Source: Crossref)

Abstract

This work proposes a lossless data compression algorithm for short data blocks. The proposed compression scheme combines a modified move-to-front algorithm with Huffman coding. This algorithm is applicable in storage systems where the data compression is performed on block level with short block sizes, in particular, in non-volatile memories. For block sizes in the range of 1kB, it provides a compression gain comparable to the Lempel–Ziv–Welch algorithm. Moreover, encoder and decoder architectures are proposed that have low memory requirements and provide fast data encoding and decoding.

This paper was recommended by Regional Editor Zoran Stamenkovic.

Keywords:

References

1. Y. Park and J.-S. Kim, zFTL: Power-efficient data compression support for NAND flash-based consumer electronics devices, IEEE Trans. Consum. Electron. 57 (2011) 1148–1156. Crossref, Web of Science, Google Scholar
2. N. Xie, G. Dong and T. Zhang, Using lossless data compression in data storage systems: Not for saving space, IEEE Trans. Comput. 60 (2011) 335–345. Crossref, Web of Science, Google Scholar
3. M. Martina, C. Condo, G. Masera and M. Zamboni, A joint source/channel approach to strengthen embedded programmable devices against flash memory errors, IEEE Embed. Syst. Lett. 6 (2014) 77–80. Crossref, Google Scholar
4. J. Li, K. Zhao, X. Zhang, J. Ma, M. Zhao and T. Zhang, How much can data compressibility help to improve NAND flash memory lifetime? Proc. 13th USENIX Conf. File and Storage Technologies (FAST15), Feb. 2015, pp. 227–240. Google Scholar
5. J. Freudenberger, A. Beck and M. Rajab, A data compression scheme for reliable data storage in non-volatile memories, IEEE 5th Int. Conf. Consumer Electronics (ICCE), Sept 2015, pp. 139–142. Google Scholar
6. T. Ahrens, M. Rajab and J. Freudenberger, Compression of short data blocks to improve the reliability of non-volatile flash memories, Int. Conf. Information and Digital Technologies (IDT), July 2016, pp. 1–4. Google Scholar
7. F. Sun, S. Devarajan, K. Rose and T. Zhang, Design of on-chip error correction systems for multilevel NOR and NAND flash memories, IET Circuit Devices Syst. 1 (2007) 241–249. Crossref, Web of Science, Google Scholar
8. R. Micheloni, A. Marelli and R. Ravasio, Error Correction Codes for Non-Volatile Memories (Springer, 2008). Google Scholar
9. G. Dong, N. Xie and T. Zhang, On the use of soft-decision error-correction codes in NAND Flash memory, IEEE Trans. Circuits Syst. I: Regular Papers 58 (2011) 429–439. Google Scholar
10. J. Freudenberger and J. Spinner, A configurable Bose–Chaudhuri–Hocquenghem codec architecture for flash controller applications, J. Circuits Syst. Comput. 23 (2014) 1–15. Link, Web of Science, Google Scholar
11. K. Zhao, W. Zhao, H. Sun, X. Zhang, N. Zheng and T. Zhang, LDPC-in-SSD: Making advanced error correction codes work effectively in solid state drives, 11th USENIX Conf. File and Storage Technologies (FAST 13). San Jose, CA, pp. 243–256. Google Scholar
12. J. Wang, K. Vakilinia, T.-Y. Chen, T. Courtade, G. Dong, T. Zhang, H. Shankar and R. Wesel, Enhanced precision through multiple reads for LDPC decoding in flash memories, IEEE J. Sel. Areas Commun. 32 (2014) 880–891. Crossref, Web of Science, Google Scholar
13. K. Haymaker and C. A. Kelley, Structured bit-interleaved LDPC codes for MLC flash memory, IEEE J. Sel. Areas Commun. 32 (2014) 870–879. Crossref, Web of Science, Google Scholar
14. S. Cho, D. Kim, J. Choi and J. Ha, Block-wise concatenated BCH codes for NAND flash memories, IEEE Trans. Commun. 62 (2014) 1164–1177. Crossref, Web of Science, Google Scholar
15. J. Spinner and J. Freudenberger, Decoder architecture for generalized concatenated codes, IET Circuits Devices Syst. 9 (2015) 328–335. Crossref, Web of Science, Google Scholar
16. B. Balkenhol, S. Kurtz and Y. Shtarkov, Modifications of the Burrows and Wheeler data compression algorithm, Proc. Data Compression Conference (DCC99), Mar 1999, pp. 188–197. Google Scholar
17. T. Welch, A technique for high-performance data compression, Computer 17 (1984) 8–19. Crossref, Web of Science, Google Scholar
18. M.-B. Lin, J.-F. Lee and G. E. Jan, A lossless data compression and decompression algorithm and its hardware architecture, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 14 (2006) 925–936. Crossref, Web of Science, Google Scholar
19. J. Sayir, I. Spieler and P. Portmann, Conditional recency-ranking for source coding, Proc. IEEE Information Theory Workshop, June 1996, p. 61. Google Scholar
20. T. Bell, J. Cleary and I. Witten, Text Compression (Prentice Hall, Englewood Cliffs, NJ, 1990). Google Scholar
21. M. Powell, Evaluating lossless compression methods, New Zealand Computer Science Research Students’ Conf. Canterbury, 2001, pp. 35–41. Google Scholar
22. P. Elias, Interval and recency rank source coding: Two on-line adaptive variable-length schemes, IEEE Trans. Inf. Theory 33 (1987) 3–10. Crossref, Web of Science, Google Scholar
23. F. Willems, Universal data compression and repetition times, IEEE Trans. Inf. Theory 35 (1989) 54–58. Crossref, Web of Science, Google Scholar
24. D. A. Huffman, A method for the construction of minimum-redundancy codes, Proc. IRE 40 (1952) 1098–1101. Crossref, Web of Science, Google Scholar
25. M. Gutman, Fixed-prefix encoding of the integers can be Huffman-optimal, IEEE Trans. Inf. Theory 36 (1990) 936–938. Crossref, Web of Science, Google Scholar
26. S. Kullback, Information Theory and Statistics (John Wiley & Sons, 1959). Google Scholar
27. R. Samanta and R. Mahapatra, An enhanced CAM architecture to accelerate LZW compression algorithm, 20th Int. Conf. VLSI Design, Jan 2007, pp. 824–829. Google Scholar
28. J. Jiang and S. Jones, Word-based dynamic algorithms for data compression, IEE Proc. I (Commun. Speech Vision) 139 (1992), 582–586. Crossref, Google Scholar
29. M.-B. Lin, A hardware architecture for the lzw compression and decompression algorithms based on parallel dictionaries, J. VLSI Signal Process. Syst. Signal Image Video Technol. 26 (2000) 369–381. Crossref, Web of Science, Google Scholar
30. T. Lee and J. Park, Design and implementation of static Huffman encoding hardware using a parallel shifting algorithm, IEEE Trans. Nucl. Sci. 51 (2004) 2073–2080. Crossref, Web of Science, Google Scholar
31. R. Hashemian, Design and hardware implementation of a memory efficient Huffman decoding, IEEE Trans. Consum. Electron. 40 (1994) 345–352. Crossref, Web of Science, Google Scholar