臺灣博碩士論文加值系統

第二代數位衛星廣播 (DVB-S2) 為新一代的數位衛星廣播標準以提升相較於 DVB-S之傳輸量，在通道編碼方面，使用 LDPC (low- density parity-check)碼作為內碼、BCH 碼作為外碼，用兩種錯誤更正碼組合，提供良好的錯誤更正能力，且 LDPC 碼提供兩種碼長，以及各種碼率，可應用於各種需求。

本論文研究內容為以FPGA硬體架構設計與實現完整DVB-S2規格(包含各種碼率與長度)之LDPC解碼器，由於DVB-S2 LDPC之校驗矩陣可經重新排列轉成特定QC(quasi-cyclic)-LDPC校驗矩陣形式，本論文使用適用於QC-LDPC之部分平行運算可程式掃描式硬體架構作為解碼器之硬體架構，此架構包含掃描參數儲存與控制模組、區塊資訊迴旋移動重排模組、軟式輸入輸出(Soft Input Soft Output: SISO)解碼計算模組及解碼資訊更新機制模組，其中多重碼率與長度DVB-S2 LDPC之相應QC-LDPC解碼參數皆經推導且以特殊資料結構儲存於記憶體，而SISO解碼演算法是使用 Min-Sun 演算法以降低硬體複雜度。本論文所整合實現之解碼器可藉由簡易參數輸入控制以實現高資料率之完整DVB-S2規格(包含各種碼率與長度)LDPC解碼器。

Second generation digital satellite broadcasting (DVB-S2) is a new generation of digital satellite broadcasting standard specified for enhancing the transmission capacity of the DVB-S. The main improvement of the DVB-S2 relies on the new channel coding scheme which uses LDPC (low-density parity-check) as an inner code and BCH as the outer code. The concatenation of these two kinds of error correction provides an error correction capability nearer to the theoretical limit. For satisfying varying demands of throughput versus sensitivity, DVB-S2 provides a variety of code-rates and the two kinds of code length in the LDPC codes.

The research topic of this thesis is on the hardware architecture design and realization of the decoder for the complete DVB-S2 LDPC specification with FPGA. Since all the parity check matrices specified in the multi-rate DVB-S2 LDPC codes can be transformed in QC(quasi-cyclic)-LDPC codes through particular reordering of data and parity-checks, we uses a partial parallel and programmable hardware architecture, which is specially designed for QC-LDPC codes and based on a raster-scanning scheme, as the hardware architecture of the decoder. This hardware architecture includes the raster-scanning parameter storing and controlling module, barrel-shift module, soft input soft output (SISO) decoder computer module, and the message-passing/updating module. All raster-scanning parameters for the corresponding DVB-S2 LDPC codes are derived and stored in memory with a special data structure. The SISO decoder is implemented based on the min-sum algorithm to reduce the hardware complexity. The decoder completed in this thesis can be configured by a simple parameter input to fulfill a LDPC decoder for all specifications in DVB-S2.

中文摘要.............................................................................................................. i
ABSTRACT......................................................................................................... ii
謝誌...................................................................................................................... iii
目錄...................................................................................................................... iv
圖目錄.................................................................................................................. vi
表目錄.................................................................................................................. ix
一、緒論.............................................................................................................. 1
1.1 研究動機與背景. . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 章節簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
二、LDPC碼...................................................................................................... 3
2.1 LDPC碼之介紹. . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 線性區塊碼. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Tanner Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 LDPC碼之解碼演算法. . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Sum-Product Algorithm . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Min-Sum Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 LDPC碼之DVB-S2編碼規格. . . . . . . . . . . . . . . . . . 12
2.3.1 Quasi-Cyclic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 校驗矩陣查找表(Lookup Table) . . . . . . . . . . . . . . . . . 15
三、軟體模擬LDPC碼效能............................................................................... 16
3.1 Sum-Product與Min-Sum演算法性能比較. . . . . . . . . . . 16
3.2 迭代次數與a 參數分析. . . . . . . . . . . . . . . . . . . . . 17
3.3 量化分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
四、FPGA實現LDPC解碼架構......................................................................... 21
4.1 FPGA開發環境. . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 LDPC解碼器架構. . . . . . . . . . . . . . . . . . . . . . . . 22
4.2.1 Modified Min-Sum Algorithm [1] [2] . . . . . . . . . . . . . . . 24
4.2.2 區塊式掃描動作流程. . . . . . . . . . . . . . . . . . . . . . . 25
4.2.3 Control Unit模組. . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.4 Barrel Shifter模組. . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.5 Check Node Process模組. . . . . . . . . . . . . . . . . . . . . 34
4.2.6 Decoder模組. . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.7 Parallel Adder和Subtractor、Accumulator模組. . . . . . . . 38
4.3 記憶體設定. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3.1 A ROM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.2 Intrinsic Information RAM . . . . . . . . . . . . . . . . . . . . 43
4.3.3 Rcv RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.4 S RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
五、FPGA硬體實現結果................................................................................... 46
5.1 硬體資源使用率. . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 硬體測試結果與效能分析. . . . . . . . . . . . . . . . . . . . 48
六、結論.............................................................................................................. 52
參考文獻.............................................................................................................. 53

[1] Z. Wang and Z. Cui, “A memory efficient partially parallel decoder architecture for quasi-cyclic ldpc codes,” Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 15, no. 4, pp. 483–488, 2007.
[2] J. Zhao, F. Zarkeshvari, and A. Banihashemi, “On implementation of min-sum algorithm and its modifications for decoding low-density parity-check (ldpc) codes,” Communications, IEEE Transactions on, vol. 53, pp. 549–554, April 2005.
[3] R. G. Gallager, “Low-density parity-check codes,” Information Theory, IRE Transactions on, vol. 8, no. 1, pp. 21–28, 1962.
[4] D. J. MacKay and R. M. Neal, “Near shannon limit performance of low density parity check codes,” Electronics letters, vol. 32, no. 18, pp. 1645–1646, 1996.
[5] E. ETSI, “302 307 v1. 2.1 (2009-08),” Digital Video Broadcasting (DVB), Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2), 2009.
[6] R. M. Tanner, “A recursive approach to low complexity codes,” Information Theory, IEEE Transactions on, vol. 27, no. 5, pp. 533–547, 1981.
[7] W. Zhou, J. Yang, and P.Wang, “Vlsi design for dvb-t2 ldpc decoder,” in Wireless Communications, Networking and Mobile Computing, 2009. WiCom’09. 5th International Conference on, pp. 1–4, IEEE, 2009.
[8] Y.-M. Chen and P.-H.Wen, “Design and fpga implementation of a configurable multi-rate qc-ldpc decoder with raster scanning architecture,” APWCS-2010.
[9] L. MING-HSIEN, “Design and implementation of dvb-t2 ldpc decoder with fpga,” 2011.