在本論文中, 我們呈現了適用於IEEE 802.15.3c規格中四種碼率的低密度同位元檢查(LDPC)編解碼器。為了達到高解碼速度，我們使用了常態化最小和(normalized min-sum)演算法搭配排層流程(row-based layered scheduling)來降低迴圈數。此外，利用可重構8/16/32個輸入的排序器來處理四種碼率的解碼，並擁有幾乎可忽略的硬體代價。我們也提出排序器輸入的重置與繞線事先編排的網路來簡化繞線的複雜度。
編碼器方面，我們針對類循環(QC)-LDPC碼提出了一個更有效率的硬體電路來編碼。而我們實做了一個LDPC的編解碼器，其中也包括一個相加白高斯雜訊(AWGN)的通道。以65-nm CMOS製程實作，在1.1V供應電壓下，此晶片可達到最高5.69Gbps的解碼速度與有436.7mW的功率消耗。所提出的解碼器，在硬體與功率的效率都勝過其它解碼器。最後，我們也將提出的解碼器用在ADRES CGRA處理器來評估其效能。實驗結果指出這個具有16個功能運算單位(FU)的ADRES架構，可比傳統VLIW處理器有12.98倍的效能改善。

In this thesis, LDPC encoder and decoder designs supporting four code rates of IEEE 802.15.3c applications are presented. In order to achieve the throughput target, normalized min-sum algorithm with row-based layered scheduling is employed to reduce the iteration number. In addition, reconfigurable 8/16/32-input sorter is designed to deal with four code rates decoding with negligible hardware overhead. Both of the reallocation of sorter inputs and pre-coding routing switch are proposed to simplify the routing complexity.
For the LDPC encoder, an AASR circuit is proposed for QC-LDPC codes to encode codewords with efficient hardware. A LDPC codec including AWGN channel has been implemented. Fabricated in the 65 nm CMOS process, the chip can achieve maximum 5.69Gbps throughput with power of 436.7mW under 1.1V. The proposed LDPC decoder outperforms the others in the aspects of hardware efficiency and power efficiency. Finally, the proposed LDPC decoder is evaluated on the ADRES CGRA processor. Experiment results show that the ADRES architecture based on 16 FUs could outperform conventional VLIW processor by a factor of 12.98.

Chapter 1 Introduction 1
1.1 Overview of Forward Error Correction for High Data Rate Wireless Personal Area Network 1
1.2 Motivation 2
1.3 Thesis Organization 3
Chapter 2 LDPC Codes 4
2.1 Concept of LDPC 4
2.2 LDPC Codes for IEEE 802.15.3c Standard 6
Chapter 3 Algorithm Optimization for Implementation 8
3.1 LDPC Decoding Algorithm 8
3.1.1 Belief Propagation Algorithm 8
3.1.2 Normalized Min-sum Algorithm 11
3.1.3 Normalized Min-sum Algorithm with Row-based Layered Scheduling 13
3.1.4 Architecture Exploration 16
3.1.5 Performance Comparison 19
3.2 LDPC Encoding Scheme 25
Chapter 4 Architecture Design and Circuit Implementation 31
4.1 Decoder Design 31
4.1.1 Architecture Overview 31
4.1.2 Check Node Unit: Reconfigurable 8/16/32-input Sorter 33
4.1.3 Sorter Inputs Reallocation Switch 35
4.1.4 Pre-coding Routing Switch 38
4.1.5 Variable Node Group 41
4.1.6 Early Termination Block 43
4.2 Chip Implementation and Measurement Results 45
4.2.1 Chip Implementation 45
4.2.2 Measurement Setup and Results 47
Chapter 5 LDPC Decoder on the ADRES Coarse-Grained Reconfigurable Array Processor 53
5.1 Introduction to ADRES Processor 53
5.2 Architecture Description of ADRES Processor 54
5.3 Mapping Result of IEEE 802.15.3c LDPC Decoder 57
5.4 Conclusion 62
Chapter 6 Conclusion and Future Work 63
6.1 Conclusion 63
6.2 Future Work 64
Reference 65

[1] Part 15.3: wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs), IEEE Std. P802.15.3c, 2009.
[2] R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT Press, 1963.
[3] A. J. Blanksby and C. J. Howland, “A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder,” IEEE J. Solid-State Circuits, vol. 37, pp. 404–412, Mar. 2002.
[4] C. C. Lin, K. L. Lin, H. C. Chang and C.Y. Lee, “A 3.33Gb/s (1200,720) Low-Density Parity Check Code Decoder,” IEEE ESSCIRC, pp. 211-214, Sep. 2005.
[5] C. L. Chen, K. S. Lin, H. C. Chang, W.C. Fang, and C. Y. Lee, "A 11.5-Gbps LDPC decoder based on CP-PEG code construction,” IEEE ESSCIRC, pp. 412-415, Sep. 2009.
[6] C. H. Liu, S. W. Yen, C. L. Chen, H. C. Chang, C. Y. Lee, Y. S. Hsu, and S. J. Jou, “An LDPC Decoder Chip Based on Self-Routing Network for IEEE 802.16e Applications,” IEEE Jour. Solid-State Circuits, vol. 43, no. 3, pp. 684-694, Mar. 2008.
[7] X. Y. Shih, C. Z. Zhan, C. H. Lin, and A. Y. Wu, “An 8.29 mm2 52 mW Multi-Mode LDPC Decoder Design for Mobile WiMAX System in 0.13 μm CMOS Process” IEEE Jour. Solid-State Circuits, vol. 43, no. 3, pp. 672-683, Mar. 2008.
[8] B. Mei, S. Vernalde, D. Verkest, H. D. Man, and R. Lauwereins, “ADRES: An architecture with tightly coupled VLIW processor and coarse-grained reconfigurable matrix,” IEEE Proc. Of Field-Programmable Logic and Applications, 2003.
[9] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol.33, no.6, pp.457–458, Mar. 1997.
[10] M. Mansour and N. Shanbhag, “High-throughput LDPC decoders,” IEEE Trans. on VLSI Systems, vol. 11, no. 6, pp. 976–996, Dec. 2003.
[11] J. Zhang and M. Fossorier, “Shuffled iterative decoding,” IEEE Transactions on Communications, vol. 53, no. 2, pp. 209–213, Feb. 2005.
[12] M. Fossorier et al., “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE Transactions on Communications, vol. 47, pp. 673–680, May 1999.
[13] J. Chen and M. Fossorier, “Near optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Transactions on Communications, vol. 50,pp. 406–414, May. 2002.
[14] J. Zhao, F. Zarkeshvari, and A. Banihashemi, ” On Implementation of Min-Sum Algorithm and Its Modifications for Decoding Low-Density Parity-Check (LDPC) Codes,” IEEE Trans. Communications, vol. 53, no. 4, pp. 549-554, April. 2005.
[15] Y. Kou, S. Lin, and M. Fossorier, “Low density parity check codes based on finite geometries: A rediscovery and more,” IEEE Trans. Inform. Theory, vol. 47, pp. 2711–2736, Nov. 2001.
[16] W. J. Gross, V. C. Gaudet, and A. Milner, “Stochastic Implementation of LDPC Decoders,” Proceedings of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers, pp. 713-717, Oct. 2005.
[17] C, Jones, E, Valles, M, Smith, and J, Villasenor, “Approximate-MIN constraint node updating for LDPC code decoding,” IEEE Military Communications Conf., pp. 157-162, Oct. 2003.
[18] R. M. Tanner, D. Sridhara, and T. Fuja, “A class of group-structured LDPC codes,” Proc. ICSTA, Jul. 2001.
[19] M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, vol. 50, no. 8, pp. 1788–1793, Aug. 2004.
[20] Z. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, “Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes,” IEEE Trans. Comm., vol. 54, pp. 71-81, Jan. 2006.
[21] A. Darabiha, A. C. Carusone, and F. R. Kschischang, “Power Reduction Techniques for LDPC Decoders,” IEEE Jour. Solid-State Circuits, vol. 43, no. 8, pp. 1835-1845, Aug. 2008.
[22] Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolic, “An Efficient 10GBASE-T Ethernet LDPC Decoder Design with Low Error Floors,” IEEE Jour. Solid-State Circuits, vol. 45, no. 4, pp. 843-855, April. 2010.
[23] R. Hartenstein, “A decade of reconfigurable computing: a visionary retrospective,” IEEE Proceedings of Design, Automation and Test in Europe (DATE), pp. 642–649, 2001.
[24] B. Mei, S. Vernalde, D. Verkest, H. D. Man, and R. Lauwereins, “DRESC: A retargetable compiler for coarse-grained reconfigurable architectures,” IEEE Proc. of International Conference on Field Programmable Technology, pages 166–173, 2002.