由於快閃記憶體製程的快速演進，使得每個快閃記憶體元件可以儲存更多的資料內容，卻也將導致資料的完整性與可靠性下降。傳統的快閃記憶體控制器主要是以BCH碼作為錯誤更正碼，而BCH碼有限的錯誤更正能力，僅能透過不斷增加冗餘位元來提升錯誤更正能力，如此一來也間接縮短資料的儲存空間。因此，本論文提出適用於快閃記憶體之低密度奇偶檢查碼(Low-Density Parity-Check Codes, LDPC Codes)及其解碼器，並以軟性資訊作為解碼器輸入，能提供同碼率下比BCH優異的錯誤更正能力。
本論文使用SFT碼架構創建碼率為0.9之(9153,8240)低密度奇偶檢查碼，並使用重疊訊息傳遞排程演算法(Overlapped Message Passing Scheduling Algorithm)來提高硬體使用效率與縮短疊代時間。相較於傳統的部分並行架構，使用重疊訊息傳遞排程演算法可以提高吞吐量為原來1.4倍並減少29.25%的解碼時間。最後使用TSMC 0.18um製程，所實現之解碼器電路可在工作頻率65MHz與20次的疊代次數情況下，最高吞吐量可達到每秒1.941Gbits。

Conventionally, BCH code is used for Flash memory controller as error correction code due to its simple hardware architecture. Recently, flash memory manufacturing technology scales down such that more data bits can be stored into a single flash memory cell. However, it also degrades reliability of flash memory. Hence, more parity bits are required to improve the error correcting capability of BCH code. In practice, to increase parity bits reduces storage capacity, and it is impractical for commercial products. In this thesis, we propose an LDPC decoder that can provide better performance when soft information is used as input under the same code rate.
The (9153,8240) LDPC code is constructed based on SFT code structure with code rate 0.9. To improve hardware utilization efficiency and reduce iteration time, the overlapped message passing scheduling algorithm is adopted. In contrast to the traditional partly parallel architecture, the proposed architecture can reduce approximately 29.25% decoding time, and can raise throughput gain up to 1.4. By using TSMC 0.18um technology, the maximum throughput can achieve 1.941Gbps under operating frequency of 65MHz with 20 iterations.

[1]Todd K. Moon, Error Correction Coding Mathematical Methods and Algorithms, Wiley, (2005)
[2]R. Micheloni, A. Marelli and R. Ravasio, Error Correction Codes for Non-Volatile Memories, Springer, (2008)
[3]Jim Cooke, “NAND Flash101: An introduction to NAND flash and how to design It in to your next product,” Micron Technology Inc, (2006)
[4]Yu Cai, Erich F. Haratsch, Onur Mutlu and Ken Mai, “Threshold voltage distribution in MLC NAND flash memory: Characterization, Analysis, and Modeling,” Proceedings of the Conference on Design, Automation and Test in Europe, pp. 1285-1290 (2013)
[5]Robert Gallager, “Low density parity-check codes,” IRE Transactions on Information Theory, Vol. 8, Issue. 1, pp. 21-28 (1962)
[6]Robert Gallager, Low density parity-check codes, in MA: MIT Press, 1963.
[7]R. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, Vol. 27, Issue. 5, pp. 533-547, (1981)
[8]D. J. MacKay and R.M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters, Vol. 33, Issue. 6, pp. 457-458, (1997)
[9]M. C. Davey and D. J. MacKay, “Low density parity check codes over GF(q),” IEEE Communications Latters, Vol. 2, Issue. 6, pp. 165-167, (1998)
[10]D. J. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory, Vol. 45, Issue. 2, pp.399-431 (1999)
[11]N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery,” IEEE Transactions on Information Theory, Vol. 42, Issue. 6, pp. 1732-1736 (1996)
[12]J.W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A digital fountain approach to reliable distribution of bulk data,” Proceedings of the ACM SIGCOMM conference on Applications, technologies, architectures, and protocols for Computer Communication, pp. 56-57, (1998)
[13]W. E. Ryan and S. Lin, Channel Codes: Classical and Modern, NY: Cambridge University Press, (2009)
[14]Z Li, L. Chen, L. Zeng, S. Lin, and W.H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Transactions on Communication, Vol. 54, Issue. 1, pp. 71-81, (2006)
[15]R. M. Tanner, D. Sridhara, and T. Fuja, “A class of group structured LDPC codes,” Proceeding of International Symposium on Communication Theory and Applications, (2001)
[16]R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello,Jr., "LDPC block and convolutional codes based on circulant matrices," IEEE Transactions on Information Theory, Vol. 50, Issue. 12, pp. 2966-2984, (2004)
[17]H. Zhong and T. Zhang, “High-rate quasi-cyclic LDPC codes for magnetic recording channel with low error floor,” Proceedings of IEEE International Symposium on Circuits and Systems, (2006)
[18]X. Huang, “Single-scan min-sum algorithms for fast decoding of LDPC codes,” IEEE Information Theory Workshop, (2006)
[19]L. Sun, H. Song, and B.V.K.V. Kumar, “Error floor investigation and girth optimization for certain types of low-density parity check codes,” Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, pp. 1101-1104, (2005)
[20]Y. Chen, and K. K. Parhi, “Overlapped message passing for quasi-cyclic low-density parity check codes,” IEEE Transactions on Circuits and Systems, Vol. 51, Issue. 6, pp. 1106-1113, (2004)
[21]Y. Dai, Z. Yan, and N.Chen, “Optimal overlapped message passng decoding of quasi-cyclic LDPC codes,” IEEE Transactions on VLSI Systems, Vol.16, Issue. 5, pp. 656-578, (2008)