近年來，多層式儲存 (Multi-Level Cell) 技術有效地增加了先進快閃記憶體的儲存空間。但是MLC技術同時伴隨了較窄的操作邊際，增加位元錯誤率 (Bit Error Rate)。
當MLC快閃記憶體的未更正位元錯誤更正率 (raw-BER) 急據增加，運用在MLC快閃記憶體上的傳統錯誤更正碼 (Error Correcting Code) 面臨嚴重的挑戰。也就是說，為了提供更高的錯誤更正能力，以保持MLC快閃記憶體的可靠性，需要更多的同位元 (Parity Bit)。這大大增加了MLC快閃記憶體的成本以存儲大量增加的Parity Bit。因此，很多研究文章著眼於新的ECC方法，以增加MLC快閃記憶體的可靠性。
低密度奇偶校驗（LDPC）碼，已被廣泛運用在通訊上，尤於其優越的錯誤更正能力，近年正贏得越來越多的注意。為了提高先進的MLC快閃記憶體的可靠性，本論文提出一個方法來構造LDPC ECC scheme以應用在先進快閃記憶體上。該貢獻包括：（1）不同raw-BERs MLC快閃記憶體的模擬模型;（2）用來取得軟訊息 (Soft Information) 的非均勻的讀取電壓方案;（3）奇偶校驗矩陣的建構和其錯誤更正能力的評估，及（4）硬體架構設計上，考量了面積和時間的權衡。
實驗結果顯示，本論文提出的 (9180, 8364, 816) LDPC ECC scheme 的codeword error rate (CER) 在raw-BER為6.0E-03的2-bit/cell MLC快閃記憶體上比使用了826個Parity Bit的 (9178, 8352, 59) BCH ECC scheme好了10^6倍。本論文提出的LDPC CODEC的編碼器/解碼器的面積為42.89k/313.48K gate，而編碼/解碼所需的時間為10.66/16.32微秒。本論文提出的LDPC CODEC的面積和使用相同Parity Bit數量的BCH CODEC是相差不大的。而且，編碼和解碼延遲時間可以滿足Open NAND Flash Interface (ONFI) 規範的吞吐量要求。
這表明了，由本論文提出來的流程所建構的LDPC編解碼器是一個有效的錯誤更正替代策略以應付面臨嚴重可靠性問題的先進快閃記憶體。只要給於快閃記憶體的設計規範和錯誤分佈狀況，本論文提出的方法可適用於任一快閃記憶體。
未來我們的工作包括，評估新的校驗矩陣以增進錯誤更正性能，為了能更進一步分析，需要建立硬體的仿真環境 (如，Error Floor和新奇偶校驗矩陣的錯誤更正性能測試)。

In recent years, the technology of multi-level cell (MLC) shows the effectiveness for increasing
storage capacity in advanced flash memories. However, using more levels in a cell also reduces
the operation margin and increases the bit error rate (BER). Traditional error correction
codes (ECC) used for advanced MLC memories face a serious problem caused by high raw-
BER. That is, in order to provide higher error-correction performance to keep the reliability
of the memory system, more number of parity bits are required. It greatly increases the
cost of flash memories to store the large number of parity bits. Hence, a lot of research
articles focus on new ECC schemes for improving the reliability of next generation of MLC
memories.
Low-density parity-check (LDPC) codes, which have been widely adopted in communication
applications, are gaining more and more attention as the superior error correction
ability. To improve the reliability for advanced multilevel flash memories, this thesis proposes
a methodology to construct an LDPC ECC scheme for advanced flash memories. The
contribution includes (1) the simulation model of MLC flash for different raw-BERs; (2)
the novel non-uniformly read voltages scheme to estimate the soft information; (3) paritycheck
and generator matrix construction and error correction performance evaluation, and
(4) hardware architecture design for the trade-off between area and latency.
The experiment results show that the codeword error rate (CER) of the proposed (9180,
8364, 816) LDPC ECC scheme is 10^6 times smaller than that of the (9178, 8352, 59) BCH
code using 826 parity bits when the raw-BER is 6.0E-03 in a 2-bit/cell MLC memory. The
encoder/decoder area of the proposed LDPC CODEC is 42.89K/313.48K gate, and the
encoding/decoding latency is 10.66/16.32 μs, respectively. The area cost of the proposed
LDPC CODEC is comparable with that of BCH CODEC with the same number of parity
bits. Moveover, the encoding and decoding latency meets the throughput requirement of the
Open NAND Flash Interface (ONFI) specification.
It shows that the proposed LDPC CODEC constructed by our flow is an effective error
correction alternative for coping with the urgent reliability issue of advanced flash memories.
Our methodology can be applied once given the target flash model of design specification
and error distribution.
Our future work includes, the evaluation of the new parity-check matrix for improving
the error correction performance, the construction of the hardware emulation environment
for further analysis (e.g., error floor and error correction performance of new parity-check
matrix).

1 Introduction 1
1.1 ECC on Non-Volatile Memories . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Motivation and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 ECC Requirements for Advanced Flash Memories 8
2.1 Flash Memory System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 BCH Correction Performance for the target memory . . . . . . . . . . . . . . 11
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 ECC Design for Flash Memory Systems 17
3.1 Soft Information and ARVs Selection . . . . . . . . . . . . . . . . . . . . . . 17
3.2 LDPC CODEC for Flash Memories . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Parity-Check Matrix Design . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1.1 Progressive Edge Growth Algorithm . . . . . . . . . . . . . 21
3.2.1.2 Quasi Cyclic Progressive Edge Growth Algorithm . . . . . . 24
3.2.2 Generating Matrix Design . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 The Proposed LDPC CODEC . . . . . . . . . . . . . . . . . . . . . . 26
3.2.4 Precision and Correction Factor . . . . . . . . . . . . . . . . . . . . . 30
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Architecture Design 34
4.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1.1 Encoding Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1.2 Encoder Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.2 Decoding Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.3 Column-Based and Row-Based Designs . . . . . . . . . . . . . . . . . 39
4.2.4 Column-Based Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.5 Row-Based Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.6 Overlapped Row-Based Decoder . . . . . . . . . . . . . . . . . . . . . 54
5 Experimental Results and Analysis 59
5.1 Performance Evaluation on Number of Read Voltages . . . . . . . . . . . . . 59
5.2 Latency for Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Encoder Area and Encoding Latency . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Decoder Area Cost and Decoding Latency . . . . . . . . . . . . . . . . . . . 64
5.4.1 Column-Based Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.4.2 Row-Based Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.5 Implementation Results and Comparisons . . . . . . . . . . . . . . . . . . . 74
6 Conclusions and future work 81
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

[1] T.-H. Chen, Y.-Y. Hsiao, Y.-T. Hsing, and C.-W. Wu, “An adaptive-rate error correction
scheme for NAND flash memory”, in Proc. IEEE VLSI Test Symp. (VTS), May
2009, pp. 53–58.
[2] N. Mielke, T. Marquart, N.Wu, J. Kessenich, H. Belgal, E. Schares, F. Trivedi, E. Goodness,
and L.R. Nevill, “Bit error rate in NAND flash memories”, in IEEE Int. Reliability
Physics Symp. (IRPS), Apr. 2008, pp. 9–19.
[3] A. Hocquenghem, “Codes correcteurs d’erreurs”, Chiffres (Paris), vol. 2, pp. 147–156,
Sept. 1959.
[4] R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group
codes”, Information and Control, vol. 3, pp. 68–79, Mar. 1960.
[5] H. Choi, W. Liu, and W. Sung, “VLSI implementation of BCH error correction for
multilevel cell NAND flash memory”, IEEE Trans. on VLSI Systems, 2009 (to appear).
[6] E. Deal, “Trends in NAND flash memory error correction”, White paper, Cyclic Design,
June 2009, http://www.cyclicdesign.com/whitepapers /Cyclic Design NAND ECC.pdf.
[7] Nelson Duann, “Error correcting techniques for future NAND flash memory in SSD
applications”, in Flash Memory Summit, Aug. 2009.
[8] R. G. Gallager, “Low density parity check codes”, IEEE Trans. on Information Theory,
vol. 8, no. 1, pp. 21–28, Jan. 1962.
[9] R. M. Tanner, “A recursive approach to low complexity codes”, IEEE Trans. on Information
Theory, vol. 27, no. 5, pp. 533–547, Sept. 1981.
[10] A. Ramamoorthy, “Multi-level signal memory with LDPC and interleaving”, U.S.
Patent Application No. 20070245214, Oct. 2007.
[11] T. Ishikawa, M. Honma, and H. Uchikawa, “Non-volatile semiconductor storage device
and non-volatile storage system”, U.S. Patent Application No. 20080055990, Mar. 2008.
[12] E. Sharon, S. Litsyn, and I. Alrod, “Memory-efficient LDPC decoding”, U.S. Patent
Application No. 20080294960, May 2008.
[13] Y. Maeda and H. Kaneko, “Error control coding for multilevel cell flash memories using
nonbinary low-density parity-check codes”, in Proc. IEEE Int. Symp. Defect and Fault
Tolerance in VLSI Systems (DFT), Chicago, Oct. 2009, pp. 367–375.
[14] Z. Li and B. V. K. V. Kumar, “A class of good quasi-cyclic low-density parity check
codes based on progressive edge growth graph”, in Thirty-Eighth Asilomar Conference
on Signals Systems and Computers, Nov. 2004, pp. 1990–1994.
[15] M. M. Mansour, “A turbo-decoding message-passing algorithm for sparse parity-check
matrix codes”, IEEE Trans. on Signal Processing, vol. 54, no. 11, pp. 4376–4392, Oct.
2006.
[16] G. Atwood, A. Fazio, D. Mills, and B. Reaves, “Intel StrataFlashTM memory technology
overview”, Intel Technology Journal 4th Quarter, pp. 1–8, 1997.
[17] F. Sun, S. Devarajan, K. Rose, and T. Zhang, “Design of on-chip error correctin systems
for multilevel nor and nand flash memories”, Institution of Engineering and Technology
(IET), vol. 1, no. 3, pp. 241–249, 2007.
[18] Guiqiang Dong, Shu Li, and Tong Zhang, “Using data postcompensation and predistortion
to tolerate cell-to-cell interference in mlc nand flash memory”, IEEE Trans. on
Circuits and Systems I: Regular Paper, pp. to–appear, 2010.
[19] X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, “Progressive edge-growth tanner graphs”,
in IEEE Global Telecommunications Conf. (GLOBECOM), Nov. 2001, pp. 995–1001.
[20] Z. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, “Efficient encoding of quasi-cyclic lowdensity
parity-check codes”, IEEE Trans. on Communication, vol. 54, no. 1, pp. 71–81,
Jan. 2006.
[21] J. Heo, “Optimization of scaling soft information in iterative decoding via density evolution
methods”, IEEE Trans. on Communications, vol. 53, no. 6, pp. 957–961, 2005.
[22] J. Heo and K.M. Chugg, “Analysis of scaling soft information on low density parity
check code”, Institution of Engineering and Technology (IET), vol. 39, no. 2, pp. 219–
221, 2003.
[23] X.-Y. Hu, E. Eleftheriou, D.-M. Arnold, and A. Dholakia, “Efficient implementation of
the sum-product algorithm for decoding LDPC codes”, in IEEE Global Telecommunications
Conf. (GLOBECOM), Nov. 2001, pp. 1036–1036E.
[24] IEEE-802.11n., “Wireless LAN medium access control and physical layer specifications:
Enhancements for higher throughput”, Mar. 2008, http://ieeexplore.ieee.org/.
[25] IEEE-802.16e., “Air interface for fixed and mobile broadband wireless access systems
specifications: Physical and medium access control layers for combined fixed and mobile
operation in licensed bands and corrigendum 1”, Feb. 2006, http://ieeexplore.ieee.org/.
[26] ETSI-DVBS2, “Digital video broadcasting (dvb) specifications: Second generation
framing structure, channel coding and modulation systems for broadcasting, interac-
tive services, news gathering and other broadband satellite applications (dvb-s2)”, Aug.
2009, http://www.dvb.org/.
[27] J. Jin and C.-Y. Tsui, “An energy efficient layered decoding architecture for ldpc decoder”,
IEEE Trans. on VLSI Systems, pp. to–appear, 2009.
[28] Y. Ying, D. Bo, S. Huang, B. Xiang, Y. Chen, and X. Zeng, “A cost efficient ldpc
decoder for dvb-s2”, in Porc. IEEE Int. Conf. on ASIC (ASICON), Oct. 2009, pp.
1007–1010.
[29] K. K. Gunnam, G. S. Choi, and M.B. Yeary, “A parallel vlsi architecture for layered
decoding for array ldpc codes”, in IEEE 20th VLSI Design International Conference(
VLSID’07), Jan. 2007, pp. 738–743.
[30] VLSI and ASIC Technology Standard Cell Library Design, “Open source standard cell
library”, http://www.vlsitechnology.org/.
[31] Chin-Long Wey, Ming-Der Shieh, and Shin-Yo Lin, “Algorithms of finding the first two
minimum values and their hardware implementation”, IEEE Trans. on Circuits and
Systems I: Regular Paper, pp. 3430–3437, Dec. 2008.
[32] O. N. F. I.Workgroup, “Open nand flash interface (onfi) specification rev2.2”, 2010,
http://www.onfi.org/.
[33] Chang-Wei Chen, “Feasibility analysis of low-density parity-check code applied to flash
memory”, Nov. 2008, Master Thesis, Dept. Electrical Engineering, National Tsing Hua
University, Hsinchu, Taiwan.