隨著製程的進步以及成本降低，使得記憶體儲存容量大幅上升，但是也造成資料的可靠度降低，因此使用錯誤更正碼來提升可靠度。傳統上運用在NAND型快閃記憶體的錯誤控制碼為使用BCH，然而面對不斷提升的記憶體容量所造成的可靠性降低的問題，BCH碼只能不斷地增加校驗碼的數量來增加資料的可靠性，此法間接降低記憶體所能儲存資料的空間，因此有必要尋找更正能力更強並且更有效率的錯誤更正碼來更正錯誤。而低密度奇偶檢查碼(Low-Density Parity-Check Codes，簡稱LDPC Codes)就是很好的選擇，尤其當使用軟性資訊來解碼時，可得到比BCH碼更佳的效能。
本論文主要是實現一個以拉丁方陣(Latin Square)所建構成編碼率(Code Rate)為0.89的(9241,8240) LDPC Codes，並採用位元節點為中心之循序排程演算法(Variable-node-centric Sequential Scheduling，簡稱VSS)來降低演算法的硬體複雜度。相較於傳統二階層的Min-Sum硬體架構，使用VSS可以降低線路的連線複雜度，在解碼器中的檢查節點單元與位元節點單元也可以有效的被簡化，並降低硬體成本。最後本論文使用TSMC 180nm製程，並於工作頻率100MHz與10次解碼次數來合成我們所實現的電路，而此電路最高吞吐量為2.02Gbps。

With the advance of new IC technology, more bits of data can be stored in each flash memory cell to increase capacity of storage; however, it reduces the reliability of flash memory cell. In tradition, BCH code is commonly used in NAND flash memory. BCH can only increase parity bits to correct large number of errors such that storage capacity is reduced. Hence, it is necessary to find a new error correcting code with higher rate and error correcting capability. To solve this problem, LDPC code is a good candidate. When soft information is used to decode stored data, LDPC codes with high code rate even perform better than BCH codes.
This thesis evaluates the frame error rate and bit error rate of (9241,8240) LDPC code with code rate 0.89. The hardware architecture of decoder of this code is also presented. This LDPC code is constructed based on Latin square. In order to reduce hardware complexity, we adopt variable-node-centric sequential scheduling (VSS) technology. Compared to the conventional Min-Sum decoder, using VSS not only reduces complexity of routing network, but also reduces hardware implementation cost. In the end, we use 180nm CMOS technology to implementation decoder under operating frequency of 100 Mhz. The number of iterations of the decoder is 10 and the maximum throughput can reach 2.02Gbps.

[1] S. Lin and D. J. Costello, Error Control Coding, Prentice-Hall, Second Edition
(2004)
[2] Ting-Yuan Kung,”LDPC Decoder Architecture Using Variable-node-centric
Sequential Scheduling Algorithm,” Master thesis, National Taiwan University of
Science and Technology, Taipei, Taiwan(2012)
[3] R. Micheloni, A. Marelli and R. Ravasio, Error Correction Codes for
Non-Volatile Memories, Springer, Italy (2008)
[4] Jiadong Wang, Courtade T., Shankar H., and Wesel R.D., “Soft Information for
LDPC Decoding in Flash: Mutual-Information Optimized Quantization ,” IEEE
Global Telecommunications Conference (GLOBECOM 2011)
[5] John P. Uyemura, and John Paul Uyemura, Introduction to VLSI Circuits and
Systems, Wiley(2001)
[6] Kin-Chu Ho, “Design and Implementation of a (9153,8256) LDPC Decoder with
2-bit Soft Input for NAND Flash Memory,” Master thesis, National Chiao Tung
University, Hsinchu, Taiwan (2010)
[7] Seongcheol Hong, and Dongkun Shin, “NAND Flash-Based Disk Cache Using
SLC/MLC Combined Flash Memory,” International Workshop on Storage
Network Architecture and Parallel I/Os (SNAPI)(2010)
[8] “Flash 與SSD 產業的挑戰─可靠度與總成本,” DTF 2012 Taiwan 前瞻儲存技
術與應用論壇, 2012/08/30-DIGITIMES 企劃
[9] Kai Zhang, Xinming Huang, and Zhongfeng Wang, “High-throughput layered
decoder implementation for quasi-cyclic LDPC codes,” IEEE Journal on
Selected Areas in Communications, Volume: 27, Issue: 6(2009)
[10] Li Zhang, Qin Huang, Shu Lin, Abdel-Ghaffar, K., and Blake, I.F.,” Quasi-Cyclic
LDPC Codes:An Algebraic Construction, Rank Analysis, and Codes on Latin
Squares,” IEEE Transactions on Communications, Volume:58, Issue: 11(2010)
[11] Heller J., and Jacobs I.,” Viterbi Decoding for Satellite and Space
Communication,” IEEE Transactions on Communication Technology, Volume:
19, Issue: 5, Part: 1(1971)
[12] Lan Lan, Lingqi Zeng, Tai Y.Y., Lei Chen, Shu Lin, and Abdel-Ghaffar K.,”
Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure
Channels: A Finite Field Approach,” IEEE Transactions on Information Theory,
Volume:53 , Issue: 7 (2007)
[13] Xiaofei Huang, “Single-Scan Min-Sum Algorithms for Fast Decoding of LDPC
Codes,” IEEE Information Theory Workshop(2006)
[14] Zion Kwok, and Scott Nelson, “LDPC Test Methodology,” Intel (2011)