LDPC codes have been discovered as a powerful class of error control codes in a variety of communication applications. However, for applications demanding different levels of code rates and code lengths, there is a challenge in realizing a low-complexity multi-mode LDPC decoder. In this thesis, we propose dividing the decoding operations of a variety of irregular quasi-cyclic (QC) low-density parity-check (LDPC) codes into several smaller tasks. An algorithm is devised in order to arrange these tasks in a similar form such that a highly reusable multi-mode architecture can be designed to process these tasks. For this task-based decoder, the associated memory access can be accomplished with the help of the proposed address generators and two routing networks. Using these approach, the difficulty in designing a low-complexity multi-mode decoder, which is capable of supporting a variety of irregular QC-LDPC codes, can be overcome. In addition, layered encoding that enables the routing networks and memory for decoding to be reused for the encoding, and an early termination circuit which shares the same hardware resources with encoder, are also proposed. The encoding functions can thus be included with very low additional increase in chip area. Using the above techniques, a multi-mode codec architecture which can support both encoding and decoding functions for all 114 WiMAX LDPC codes is designed and implemented in a 90-nm 1P9M process. The full-mode WiMAX codec architecture achieves a moderate encoding (decoding) throughput of 800 Mb/s (200 Mb/s) and occupies an area of only 0.679 mm^2 at operation frequency of 400 MHz.

低密度奇偶檢查(Low-density parity-check, LDPC)碼為一類具有強大改錯能力的錯誤更正碼，且已被應用於多種通訊傳訊中。然而在需要多碼率及多碼長的應用中，實現一個低複雜度且能支援多種模式的低密度奇偶檢查碼解碼器仍然是一個困難的挑戰。在這篇論文中，我們提出了一種任務安排的方法，可將類循環低密度奇偶檢查(QC-LDPC)碼的解碼運算細切為數個較小的運算集合，稱為任務。任務安排演算法可將各種不同定義的類循環低密度奇偶檢查碼的解碼運算細切為較小且相似的任務，進而實現一可被高度重覆使用的任務運算器進行解碼運算。基於任務安排演算法所定義的任務以及任務運算器，我們也提出用於控制記憶體存取的位址產生器，以及運算單元中的二階搜尋器的實現方法。使用這些技術，我們完成一低複雜度且支援多種不同規範循環低密度奇偶檢查碼解碼運算的多模態解碼器。此外，我們也提出重覆使用解碼器的記憶體及繞線網路來達成階層編碼運算的方法，以及和編碼電路共用硬體資源的提前終止電路，於是編碼運算能夠在僅增加非常少量的複雜度後被支援。綜合以上的方法，我們設計了一個可支援WiMAX規範中共114種不同的類循環低密度奇偶檢查碼的編碼及解碼器電路。此電路晶片在90奈米製程實現下，核心面積僅有0.679 $mm^2$，且在操作頻率為400 MHz時最高可到達到800Mb/s的編碼吞吐量及200 Mb/s的解碼吞吐量。

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Implementation issues of LDPC decoders . . . . . . . . . . . . . 3
1.2.1 Decoding parallelism and flexibility for multi-mode decoding
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Layered message passing decoding . . . . . . . . . . . . . 4
1.2.3 Data dependency in LMPD . . . . . . . . . . . . . . . . 6
1.3 Goal and contribution . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Dissertation organization . . . . . . . . . . . . . . . . . . . . . . 7
2 LDPC codes 9
2.1 Definitions of LDPC codes . . . . . . . . . . . . . . . . . . . . . 9
2.2 QC-LDPC codes . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Decoding algorithms . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Sum-product algorithm (SPA) . . . . . . . . . . . . . . . 12
2.3.2 Min-sum algorithm (MSA), offset min-sum algorithm
(OMSA), and normalized min-sum algorithm (NMSA) . 14
2.4 Layered message passing decoding (LMPD) . . . . . . . . . . . 15
2.5 Layered message passing decoding using an identical core matrix
(LMPD-ICM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Proposed task arrangement algorithm for LMPD-ICM 21
3.1 Memory-based decoders using LMPD-ICM . . . . . . . . . . . . 21
3.2 Concept of task arrangement . . . . . . . . . . . . . . . . . . . . 24
3.3 Task arrangement algorithm . . . . . . . . . . . . . . . . . . . . 28
3.4 APP memory access and routing networks . . . . . . . . . . . . 32
4 Proposed layered encoding 37
4.1 First encoding step . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Second encoding step . . . . . . . . . . . . . . . . . . . . . . . . 38
5 A low-complexity full-mode codec with early termination for
WiMAX applications 40
5.1 Review of QC-LDPC codes in WiMAX . . . . . . . . . . . . . . 40
5.2 Parameters associated with task arrangement . . . . . . . . . . 41
5.3 An overview of the unified architecture (task processor) . . . . . 44
5.3.1 Check node units (CNUs) . . . . . . . . . . . . . . . . . 45
5.3.2 Variable node units (VNUs) . . . . . . . . . . . . . . . . 48
5.3.3 Write address generation . . . . . . . . . . . . . . . . . . 48
5.4 Extension for multi-rate functionality . . . . . . . . . . . . . . . 50
5.4.1 Multi-rate functionality in CNUs . . . . . . . . . . . . . 51
5.4.2 Multi-rate functionality in VNUs . . . . . . . . . . . . . 51
5.4.3 Multi-rate functionality in address generators . . . . . . 52
5.5 Early termination (ET) and encoder . . . . . . . . . . . . . . . 53
5.6 Data hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.6.1 Type-I hazards . . . . . . . . . . . . . . . . . . . . . . . 56
5.6.2 Type-II hazards . . . . . . . . . . . . . . . . . . . . . . . 57
5.6.3 Type-III hazards . . . . . . . . . . . . . . . . . . . . . . 58
5.6.4 Regularity of data hazards . . . . . . . . . . . . . . . . . 59
6 Implementation results 62
6.1 Chip characteristic . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2 Hardware utilization ratio in different modes . . . . . . . . . . . 64
6.3 Comparison with other related works . . . . . . . . . . . . . . . 65
6.4 Measurement results in a 0.18 μm process . . . . . . . . . . . . 69
7 Conclusion 77
A WiMAX LDPC Codes and the corresponding prototype tasks 78
A.1 Rate 1/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
A.2 Rate 2/3A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
A.3 Rate 2/3B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
A.4 Rate 3/4A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
A.5 Rate 3/4B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
A.6 Rate 5/6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

[1] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit errorcorrecting
coding and decoding: turbo-codes (1),” in Proc. IEEE Int.
Conf. on Communications pp. 1064-1070, May 1993.
[2] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory,
vol. 7, pp. 21-28, Jan. 1962.
[3] D.-J.-C. MacKay, “Good error-correcting codes based on very sparse matrices,”
IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399-431, March 1999.
[4] C.-H. Lin, C.-Y. Chen, and A.-Y. Wu, “High-throughput 12-mode CTC
decoder for WiMAX standard,” in Proc. IEEE Int. Symposium on VLSI
Design, Automation and Test, pp. 216-219, April 2008.
[5] I. Ahmed and T. Arslan, “VLSI design of multi standard turbo decoder
for 3G and beyond,” in Proc. Asia and South Pacific Design Automation
Conf., pp. 589-594, Jan. 2007.
[6] C.-C. Wong, Y.-Y. Lee, and H.-C. Chang, “A 188-size 2.1mm2 reconfigurable
turbo decoder chip with parallel architecture for 3GPP LTE
system,” in Proc. Symposium on VLSI Circuits, pp. 288-289, June 2009.
[7] IEEE 802.16e WiMAX standard, IEEE P802.16e-2005, Oct. 2005.
[8] IEEE 802.11 Wireless LANs WWiSE Proposal: High throughput extension
to the 802.11 standard. IEEE 11-04-0886-00-000n
[9] G. Gentile, M. Rovini, and L. Fanucci, “Low-complexity architectures of
a decoder for IEEE 802.16e LDPC codes,” in Proc. Euromicro Conf. on
Digital System Design Architectures, Methods and Tools (DSD), pp. 369-
375, Aug. 2007.
[10] T. Brack, M. Alles, T. Lehnigk-Emden, F. Kienle, N. Wehn, N.-E.
L’Insalata, F. Rossi, M. Rovini, and L. Fanucci, “Low complexity LDPC
code decoders for next generation standards,” in Proc. Design, Automation
and Test in Europe Conf. and Exhibition, pp. 16-20, April 2007.
[11] M. Alles, T. Vogt, and N. Wehn, “FlexiChaP: A reconfigurable ASIP for
convolutional, turbo, and LDPC code decoding,” in Proc. Turbo Codes
and Related Topics, pp. 84-89, Sept. 2008.
[12] 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 J. Solid-State Circuits, vol. 43, no. 3, pp. 672-683,
March 2008.
[13] 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 J. Solid-State Circuits, vol. 43, no. 3,
pp. 684-694, March 2008.
[14] C.-H. Liu, C.-C. Lin, S.-W. Yen, C.-L. Chen, H.-C. Chang, C.-Y. Lee, Y.-
S. Hsu, and S.-J. Jou, “Design of a multimode QC-LDPC decoder based
on shift-routing network,” IEEE Trans. Circuits Syst. II, Express Briefs,
vol. 56, no. 9, pp. 734-738, Sept. 2009.
[15] Y.-L. Ueng, C.-J. Yang, Z.-C. Wu, C.-E. Wu, and Y.-L. Wang, ”VLSI
decoding architecture with improved convergence speed and reduced decoding
latency for irregular LDPC codes in WiMAX,” in Proc. IEEE International Symposium on Circuits and Systems, Seattle, USA, 18-21,
May, 2008.
[16] T.-J. Richardson and R.-L. Urbanke, “Efficient encoding of low-density
parity-check codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 638-656,
Feb. 2001.
[17] H. Zhong and T. Zhang, “Block-LDPC: A practical LDPC coding system
design approach,” IEEE Trans. Circuits Syst. I, Reg. Papers, Vol. 52,
No. 4, pp. 766-775, April 2005.
[18] C. Yoon, E. Choi, M. Cheong, and S.-K. Lee, “Arbitrary bit generation
and correction technique for encoding QC-LDPC codes with dualdiagonal
parity structure,” in Proc. IEEE Wireless Commun. and Networking
Conf. (WCNC), pp. 662-666, March 2007.
[19] C.-Y. Lin, C.-C. Wei, and M.-K. Ku, “Efficient encoding for dual-diagonal
structured LDPC codes based on parity bit prediction and correction,”
in Proc. IEEE Asia Pacific Conf. on Circuits and System (APCCAS),
pp. 1648-1651, Nov. 2008.
[20] R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans.
Inform. Theory, vol. 27, no. 5, pp. 533-547, Sept. 1981.
[21] 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, no. 3, pp. 404-412, March 2002.
[22] E. Yeo, P. Pakzad, B. Nikoli´c, and V. Anantharam, “VLSI architectures
for iterative decoders in magnetic recording channels,” IEEE Trans.
Magn., vol. 37, no. 2, pp. 748-755, March 2001.
[23] S.-H. Kang and I.-C. Park, “Loosely coupled memory-based decoding architecture
for low density parity check codes,” IEEE Trans. Circuit Syst.
I, Reg. Papers, vol. 53, no. 5, pp. 1045-1056, May 2006.
[24] M. Karkooti, P. Radosavljevic, and J.-R. Cavllaro, “Configurable, high
throughput, irregular LDPC decoder architecture tradeoff analysis and
implementation,” in Proc. Int. Conf. on Application-specific Systems, Architectures
and Processors (ASAP), pp. 360-367, Sept. 2006.
[25] J. Lin, Z. Wang, L. Li, J. Sha, and M. Gao, “Efficient shuffle network
architecture and application for WiMAX LDPC decoders,” IEEE Trans.
Circuits Syst. II, Express Briefs, vol. 56, no. 3, pp. 215-219, March 2009.
[26] G. Masera, F. Quaglio, and F. Vacca, “Implementation of a flexible LDPC
decoder,” IEEE Trans. Circuits Syst. II, Express Briefs, vol. 54, no. 6,
pp. 542-546, June 2007.
[27] M.-M. Mansour and N.-R. Shanbhag, “High-throughput LDPC decoders,”
IEEE Trans. VLSI Systems, vol. 11, no. 6, pp. 976-996, Dec. 2003.
[28] D.-E. Hocevar, “A reduced complexity decoder architecture via layered
decoding of LDPC codes,” in Proc. IEEE Workshop on Signal Processing
Systems (SIPS), pp. 107-112, Oct. 2004.
[29] Y. Dai, N. Chen, and Z. Yan, “Memory efficient decoder architectures
for quasi-cyclic LDPC codes,” IEEE Trans. Circuit Syst. I, Reg. Papers,
vol. 55, no. 9, pp. 2898-2911, Oct. 2008.
[30] Y.-L. Ueng and C.-C. Cheng, “A fast-convergence decoding method and
memory-efficient VLSI decoder architecture for irregular LDPC codes in
the IEEE 802.16e standards,” in Proc. IEEE Semiann. Vehicular Technology
Conf., pp. 1255-1259, Oct. 2007.
[31] K. Zhang, X. Huang, and Z. Wang, “High-throughput layered decoder
implementation for quasi-cyclic LDPC codes,” IEEE Journal on Selected
Areas in Commun., vol. 27, no. 6, pp. 985-994, Aug. 2009.
[32] Y. Dai, Z. Yan, and N. Chen, “Optimal overlapped message passing decoding
of quasi-cyclic LDPC codes,” IEEE Trans. VLSI Systems, vol. 16,
no. 5, pp. 565-578, May 2008.
[33] J. Jin and C.-Y, Tsui, “Improving the hardware utilization efficiency of
partially parallel LDPC decoder with scheduling and sub-matrix decomposition,”
in Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS),
pp. 2233-2236, May 2009.
[34] M. Rovini, F. Rossi, P. Ciao, N. L’Insalata, and L. Fanucci, “Layered
decoding of non-layered LDPC codes,” in Proc. Euromicro Conf. on Digital
System Design Architectures, Methods and Tools (DSD), pp. 537-544,
Aug. 2006.
[35] T.-C. Kuo and A.-N. Willson, “Enhanced delta-based layered decoding of
WiMAX QC-LDPC codes,” in Proc. IEEE Int. Symposium on Circuits
and Systems (ISCAS), pp. 524-527, May 2008.
[36] M. Cocco, J. Dielissen, M. Heijligers, A. Hekstra, and J. Huisken, “A
scalable architecture for LDPC decoding,” in Proc. Design, Automation
and Test in Europe Conference and Exhibition vol. 3, pp. 88-93, Feb. 2004.
[37] G. Masera, F. Quaglio, and F. Vacca, “Implementation of a flexible LDPC
decoder,” IEEE Trans. Circuits. Syst. II, Exp. Briefs, vol. 54, no. 6, pp.
542-546, June 2007.
[38] L. Liu and C.-J. Richard Shi, “Sliced message passing: high throughput
overlapped decoding of high-rate low-density parity-check codes,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 55, no. 11, pp. 3697-3710, Dec.
2008.
[39] T. Mohsenin, D. Truong, and B. Baas, “Multi-split-row threshold decoding
implementations for LDPC codes,” in Proc. IEEE ISCAS 2009, pp.
2449-2452, May 2009.
[40] Y.-L. Ueng, C.-J. Yang, K.-C. Wang and C.-J. Chen, “A multi-mode
shuffled iterative decoder architecture for high-rate RS-LDPC codes,” to
apear in IEEE Trans. Circuits Syst. I, Reg. Papers,.