隨著科技的發展，NAND Flash Memory已經逐漸取代傳統硬碟(Hard Disk Drive, HDD)，成為目前主流的儲存設備。NAND Flash Memory具有體積小、低功耗、讀寫速度快、高抗震性等優點，且隨著製程的進步，NAND Flash Memory也已經從容量較小的SLC(Single-Level Cell)、MLC(Multi-Level Cell)發展至容量較大的TLC(Triple-Level Cell)甚至是QLC(Quad-Level Cell)。儘管NAND Flash Memory有許多優勢，但它也存在著難以被克服的物理限制，比方說無法進行覆寫資料(Overwrite)的操作、擁有擦除次數(P/E Cycle)的限制等，而高容量的TLC NAND Flash Memory更存在著可靠度(Reliability)低落與壽命(Life Time)較短的問題。因此，本文將提出一種動態霍夫曼編碼的方法，使其應用在NAND Flash Memory的寫入(Write)操作上。動態霍夫曼編碼會為寫入資料選擇適合的儲存模式，並改變NAND Flash Memory中儲存狀態的分佈(VTH Distribution)，以降低儲存資料時的位元錯誤率，進而提升整體的可靠度。

Recently, NAND flash memory has gradually replaced the traditional Hard-Disk Drives and become the most mainstream storage device. NAND flash memory has many advantages such as non-volatile features, small size, low-power consumption, fast-access speed, and shock resistance, etc. With the advance of the process, NAND flash memory has evolved from single-level cell (SLC) and multi-level cell (MLC) into triple-level cell (TLC) or even quad-level cell (QLC). Although NAND flash memory has many advantages, it also has many physical problems such as the characteristic of erase-before-write, the limitation of P/E Cycles, etc. Moreover, TLC NAND flash memory has the problems of low reliability and short lifetime. Thus, we propose a dynamic Huffman coding method, which can apply to the write operation of NAND flash memory. Our method can select a suitable type of Huffman coding for different kinds of data dynamically and improve the VTH distribution of NAND flash memory to reduce the bit-error-rate and improve the reliability of NAND flash memory.

[1] R. Bez, E. Camerlenghi, A. Modelli, and A. Visconti, “Introduction to Flash Memory,” Proceedings of the IEEE, vol. 91, no. 4, pp. 489–502, Apr. 2003.
[2] “QLC NAND SSD.” [Online]. Available:
https://technews.tw/2018/05/22/qlc-nand-ssd-micron/
[3] P. Gutmann, “Data Remanence in Semiconductor Devices,” in Proceedings of the 10th conference on USENIX Security Symposium, vol. 10, pp. 39-54, Aug. 2001.
[4] A. Ben, “Flash file system,” US Patent Patent 5404485A, Apr. 1995.
[5] A. Ben, “Flash file system optimized for page-mode flash technologies,” US Patent Patent 5937425A, Aug. 1999.
[6] J. Kim, J. M. Kim, S. H. Noh, S. L. Min and Y. Cho, “A Space-Efficient Flash Translation Layer for CompactFlash Systems,” in IEEE Transactions on Consumer Electronics, vol. 48, no. 2, pp. 366-375, May. 2002.
[7] D. Park, B. Debnath, and D. Du, “CFTL: a convertible flash translation layer adaptive to data access patterns,” in ACM SIGMETRICS Perform Eval Rev. 38, pp. 365-366, Jun. 2010.
[8] J. Dawoon, J. Kang, H. Jo, J. Kim, and J. Lee, “Superblock FTL: A Superblock-Based Flash Translation Layer with a Hybrid Address Translation Scheme,” in ACM Transactions on Embedded Computing Systems (TECS), vol. 9, no. 4, pp. 40:1-40:41, Mar. 2010.
[9] S-W. Lee, D-J. Park, T-S. Chung, D-H. Lee, S. Park, and H-J. Song, “A Log Buffer-Based Flash Translation Layer using Fully-Associative Sector Translation,” in ACM Transactions on Embedded Computing Systems (TECS), vol. 6, no. 3, Article 18, Jul. 2007.
[10] H. Cho, D. Shin, and Y. I. Eom, “KAST: K-Associative Sector Translation for NAND Flash Memory in Real-Time Systems,” in Proceedings of the Conference on Design, Automation and Test in Europe, pp. 507-512, Apr. 2009.
[11] S. Lee, D. Shin, Y-J. Kim, and J. Kim, “LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems,” in ACM SIGOPS Operating Systems Review, vol. 42, no. 6, pp. 36-42, Oct. 2008.
[12] M. Wu and W. Zwaenepoel, “eNVy: A Non-volatile, Main Memory Storage System,” in ACM SIGPLAN Notices, vol. 29, no. 11, pp. 86-97, Nov. 1994.
[13] M. Rosenblum and J. K. Ousterhout, “The Design and Implementation of a Log-Structured File System,” in ACM Transactions on Computer Systems (TOCS), vol. 10, no. 1, pp. 26-52, Feb. 1992.
[14] O. Kwon, K. Koh, J. Lee, and H. Bahn, “FeGC: An Efficient Garbage Collection Scheme for Flash Memory Based Storage Systems,” in Journal of Systems and Software, vol. 84, no. 9, pp. 1507-1523, Sep. 2011.
[15] B. Kim, M. Park, C. Jeon, C. O. Sung, Y. Cho, and J. Hong, “AAGC: An Efficient Associativity-Aware Garbage Collection Scheme for Hybrid FTLs,” in Proceedings of the 27th Annual ACM Symposium on Applied Computing, pp. 1785-1790, Mar. 2012.
[16] D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” in Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, Sep. 1952.
[17] H. Watanabe, Y. Deguchi, and K. Takeuchi, “MLC/3LC NAND Flash SSD Cache with Asymmetric Error Reduction Huffman Coding for Tiered Hierarchical Storage,” 2017 IEEE Asian Solid-State Circuits Conference (A-SSCC), 2017, pp. 157-160.
[18] A. Gupta, Y. Kim, and B. Urgaonkar, “DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings,” SIGPLAN Not., vol. 44, no. 3, pp. 229-240, Mar. 2009.
[19] J. Lee, J. Choi, D. Park ,and K. Kim, “Degradation of Tunnel Oxide by FN Current Stress and its Effects on Data Retention Characteristics of 90 nm NAND Flash Memory Cells,” 2003 IEEE International Reliability Physics Symposium Proceedings, 41st Annual., Dallas, TX, USA, pp. 497-501, Mar. 2003.
[20] Y. Deguchi, A. Kobayashi and Ken Takeuchi, “Write/Erase Stress Relaxation Effect on Data-Retention and Read-Disturb Errors in Triple-Level Cell NAND Flash Memory with Round-Robin Wear-Leveling, ” in Japanese Journal of Applied Physics, vol. 56, no. 4S, pp. 04CE01, Feb. 2017.
[21] Y. Deguchi, A. Kobayashi, H. Watanabe and K. Takeuchi, “Flash Reliability Boost Huffman Coding (FRBH): Co-Optimization of Data Compression and Vth Distribution Modulation to Enhance Data-Retention Time by over 2900x,” 2017 Symposium on VLSI Technology, Kyoto, 2017, pp. T206-T207.
[22] “Silesia compression corpus.” [Online]. Available:
http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia/