適用於非揮發性記憶體系統的可重組化半循環低密度奇偶校驗編解碼器之演算法與硬體架構設計

Algorithms and Architectures of Reconfigurable QC-LDPC Codec for Non-Volatile Memory Systems

鍾明翰(Ming-Han Chung)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.10993

摘要

近年來包含多階儲存(MLC)快閃記憶體的非揮發性記憶體系統，因為具有高儲存密度、高效能與低功率消耗的優點，特別適用於消費型電子產品的應用。然而，多階儲存快閃記憶體的高錯誤率特性也嚴重影響了非揮發性記憶體系統的可靠度。對於此問題，低密度奇偶校驗碼(LDPC codes)因具有優越的錯誤更正能力，被認為是未來高容量非揮發性記憶體系統中錯誤更正碼(ECC)的優良候選人。
但在實際應用上，有如下問題仍待解決：(1) 低密度奇偶校驗碼解碼時須搭配軟性值(soft values)才能得到最佳的錯誤更正能力。然而現今快閃記憶體的輸出入介面僅提供硬性值(hard values)。使用硬性值對低密度奇偶校驗碼解碼會造成其錯誤更正能力大幅下降。(2) 低密度奇偶校驗碼的編解碼器需要大量的記憶體單元，而該記憶體的大小又與碼字(codeword)的長度成正比。因此非揮發性記憶體系統的長碼字特性將大幅增加低密度奇偶校驗碼編解碼器的記憶體成本。(3) 現今在非揮發性記憶體系統中對於低密度奇偶校驗碼仍無統一之規格與標準，為了降低硬體重新設計的成本與提供快速驗證的原型設計，可重組化的編解碼器設計也是被期望的。
本論文的主要貢獻包含下列兩個部分：(1) 我們提出基於狀態轉變的軟性值估計方法。使用估計的軟性值進行低密度奇偶校驗碼的解碼，不僅提供較硬性值解碼更佳的錯誤更正能力，也可趨近於使用完美軟硬值解碼的效能。(2) 我們針對非揮發性記憶體系統的錯誤更正碼應用，提出一具有成本效率與吞吐量(throughput)增強之可重組化半循環低密度奇偶校驗(QC-LDPC)編解碼器架構設計。相較於傳統架構，我們所提出的編解碼器架構大幅減少了記憶體成本並可增強吞吐量。而在預先定義好的參數空間中，可重組化的架構設計可支援任意的半循環低密度奇偶校驗碼。
最後，我們利用台積電 90奈米製程實作一個可重組化半循環低密度奇偶校驗編解碼器的原型設計。編碼器與解碼器晶片面積分別為0.32mm2與2.58mm2。在138.8MHz的操作頻率下與設定為最長的碼字長度時，編碼器可達到1110Mb/s的資料吞吐量，而解碼器在8次疊代時，可達到393Mb/s的資料吞吐量。

關鍵字

非揮發性記憶體系統 ； 低密度奇偶校驗碼

並列摘要

Recently, non-volatile memory systems (NVMS) with multi-level cell (MLC) NAND flash memories have greatly prevailed among consumer electronics products for their high storage density, high performance, and low power consumption. However, the high error-rate characteristic of MLC NAND flash memories also degrades the reliability of NVMS significantly. To overcome this problem, low-density parity-check (LDPC) codes are regarded as good candidates for the error correcting code (ECC) in future high-capacity NVMS due to their superior error-correcting performance.
In practice, there are some problems to be solved before adopting LDPC codes in NVMS. (1) The superior error-correcting capability of LDPC codes comes from decoding with soft values. However, the I/O interface of flash memories currently only provides hard values. The error correcting performance of decoding LDPC codes with hard values is much worse. (2) An LDPC codec is a memory-dominant design, and the memory size of codec is linearly proportional to the codeword size. The large codeword size in NVMS may greatly increase the memory cost of a LDPC codec. (3) There is still no standardized LDPC code for NVMS. To reduce the hardware redesign cost and provide a rapid prototyping for evaluation, a codec design with reconfigurability is desirable.
The contributions of this thesis consist following two parts: (1) We propose state-transition-based soft value estimation schemes to generate estimated soft values for decoding LDPC codes. With the estimated soft value, the error correcting performance not only is better than that with hard values, but also approaches that with perfect soft values. (2) Targeted for ECCs in NVMS, cost-effective we propose throughput-enhanced reconfigurable architecture designs for quasi-cyclic LDPC (QC-LDPC) codec. The proposed codec architectures significantly reduce the area cost of memories and has higher throughput compared to conventional QC-LDPC codec designs. Moreover, the proposed reconfigurable architectures support arbitrary QC-LDPC codes within a pre-defined parameter space.
A prototyping reconfigurable QC-LDPC codec is designed and implemented in TSMC 90nm process. The core area of encoder and decoder are 0.32mm2 and 2.58 mm2, respectively. Operating at a clock frequency of 138.8MHz and configured to the maximum codeword size, the encoder attains a throughput of 1110Mb/s, and the decoder attains a throughput of 393Mb/s at 8 iterations.

並列關鍵字

non-volatile memory systems ； low-density parity-check (LDPC) codes

參考文獻

[1] G. Wong, “NAND Flash Memory: Enabling Mobility,” Sep. 2009, [online]. Available: http://www.forward-insights.com/present/Wong-Diskcon_0909.pdf

[2] P. Pavan, R. Bez, P. Olivo, and E. Zanoni, “Flash memory cells-an overview,” Proc. IEEE, vol. 85, no. 8, pp. 1248-1271, Aug. 1997.

[3] N. Mielke et al, “Bit error rate in NAND flash memories,” in Proc. IEEE Int. Rel. Phys. Symp. (IRPS), pp. 9-19, April 2008.

[4] Solid-State Drive (SSD) Requirements and Endurance Test Method, JEDEC Standard JESD218A, Sep. 2010.

[5] R. Micheloni, A. Marelli, and R. Ravasio, Error Correction Codes for Non-Volatile Memories. Springer, 2008.