論文實現一個以拉丁方陣(Latin Square)所建構而成且編碼率(Code Rate)為0.89的(9242,8240)低密度奇偶檢查碼的解碼器硬體電路，並於數種已知的低密度奇偶檢查碼的演算碼中選用位元節點為中心之循序排程演算法(Variable-node-centric Sequential Scheduling，VSS)來降低演算法的硬體複雜度。此演算法屬於一種分組曳步解碼的演算法，也就是結合並行與串列的解碼方式，相較於傳統二階層的Min-Sum演算法硬體架構，可以有效的減少解碼的疊代次數並降低線路的複雜度，並且在解碼器中的檢查節點單元與位元節點單元也可以被有效的簡化以降低硬體成本。本論文於工作頻率100MHz與20次解碼疊代次數下使用TSMC180nm製程來進行合成，而此電路的最高吞吐量為1.03Gbps。

This thesis realizes the hardware architecture of the LDPC decoder, where the (9241,8240) LDPC code is constructed based on the Latin Square with code rate 0.89. The variable-node-centric sequential scheduling (VSS) technology is adopted to reduce hardware complexity and utilization efficiently. In contrast to the traditional Min-Sum decoder, the proposed VSS technology not only reduces the iteration times, but also hardware implementation cost and complexity of routing network. By using TSMC180nm CMOS technology to implement decoder, the maximum throughput can achieve 1.03 Gbps under operating frequency of 100 MHz with 20 iterations.

[1] S. Lin and D. J. Costello, Error Control Coding, Prentice-Hall, Second Edition (2004)
[2] R. G. Gallager , Low-Density Parity-Check Codes, Cambridge, MA, MIT Press (1963)
[3] Heller J., and Jacobs I., Viterbi Decoding for Satellite and Space Communication, IEEE Transactions on Communication Technology, Volume: 19, Issue: 5, Part: 1(1971)
[4] 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)
[5] 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)
[6] 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)
[7] 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)
[8] J.W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, A digital fountain
approach to reliable distribution of bulk data, Proceedings of the
ACMSIGCOMM conference on Applications, technologies, architectures, and protocols for Computer Communication, pp. 56-57, (1998)
[9] W.E. Ryan and S. Lin, Channel Codes: Classical and Modern, Cambridge University Press, New York (2009)
[10] R. Micheloni, A. Marelli and R. Ravasio, Error Correction Codes for Non-Volatile Memories, Springer, (2008)
[11] 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)
[12] John P. Uyemura , and John Paul Uyemura, Introduction to VLSI Circuits and
Systems, Wiley(2001)
[13] Zion Kwok, and Scott Nelson, LDPC Test Methodology ,Intel (2011)
[14] 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)
[15] 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)
[16] Heller J., and Jacobs I., Viterbi Decoding for Satellite and Space
Communication, IEEE Transactions on Communication Technology, Volume:
19, Issue: 5, Part: 1(1971)
[17] 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)
[18] Chun-Jen Yu, Decoder Implementation of Latin Squares LDPC Codes , Master thesis, National Taiwan University of Science and Technology, Taipei, Taiwan(2013)
[19] Chung-Chieh Lin, Decoder Implementation of SFT LDPC Codes, Master
thesis, National Taiwan University of Science and Technology, Taipei,
Taiwan(2013)
[20] Yeh-Hsiang Chen, Encoder Implementation of SFT LDPC Codes , Master
thesis, National Taiwan University of Science and Technology, Taipei,
Taiwan(2013)
[21] 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)

[22] 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)