臺灣博碩士論文加值系統

近年來在通訊領域裡，由於不同體制的存在，使得越來越多的新系統不斷出現，這讓傳統上的硬體設計漸漸失去其優勢，而為了因應此種問題，一種稱為「軟體無線電」的新概念應運而生；在傳統上，我們以硬體解決了「準確」、「快速」和「大量」這三大問題，然而為了因應最新的通訊發展趨勢，我們重新使用軟體來替換掉硬體，這使得舊有的軟體問題「快速」和「大量」浮現了出來。
本論文將實現一種通訊上的編解碼架構LDPC（Low density parity check，低密度奇偶校驗碼）的解碼部分，並將之應用在軟體無線電（Software Defined Radio）上，由於LDPC架構極為適合平行，所以本文利用新的平行技術CUDA（Compute Unified Device Architecture，統一計算架構）進行加速以解決軟體效能低落的問題；在一般上，軟體無線電是以多個CPU來平行加速，但是CP值較低，所以本文提出利用GPU來取代CPU以改善此現象；本研究會對兩種解碼演算法SPA（Sum-Product Algorithm，和積演算法）與MS（Min-Sum Algorithm，最小和演算法）進行測試，並分析在不同GPGPU和不同平行架構下的異同。

Recently, in communication field, because of the existence of different systems, more and newer systems appear constantly, which makes traditional design lost their advantages gradually. To solve these questions, a new concept "Software Defined Radio" is proposed. Traditionally, we use hardware to solve these issues such as "accuracy", "fast" and "volume". However, for the newest trend of communication development, we reuse the software to replace the hardware, which makes some old software questions appear such as "fast" and "volume".

Our thesis will realize structural LDPC (Low density parity check, low density odd-even check-up yard) on a kind of communication decoding, which will been applied to SDR (Software Defined Radio). Because LDPC structure is extremely suitable for paralleling, we will use a new parallel technology "CUDA" (Compute Unified Device Architecture, calculate the structure in unison) to speed up the process of solving low efficiency. Generally, SDR speed up the work by numerous CPUs, but CPI (Cost Performance Index) is low relatively. Our thesis makes use of GPU to replace CPU to improve this phenomenon. We perform and measure for both SPA (Sum-Product Algorithm) and MS(Min-Sum Algorithm), and analyze the similarities and differences under different GPGPUs and parallel structures.

摘要 i
ABSTRACT ii
誌　謝 iii
目　錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景介紹 1
1.2 研究方法簡介 2
1.3 論文架構 2
第二章　相關背景探討 3
2.1 低密度奇偶校驗碼 3
2.1.1 線性區塊碼 3
2.1.2 低密度奇偶校驗矩陣 4
2.1.3 Tanner Graph 5
2.1.4 LDPC解碼演算法 7
2.2 平行架構CUDA 15
2.2.1 GPGPU 15
2.2.2 CUDA 17
第三章 研究方法 18
3.1 事前準備 18
3.2 LDPC平行架構 19
3.3 Log SPA平行方法 20
3.4 Pipeline 23
3.5 LDPC平行Pipeline 24
第四章 實驗結果 27
4.1 實驗設備 27
4.2 實驗數據 28
4.3 序向架構與平行架構之比較 29
4.3.1 平行架構對正確率之影響 29
4.3.2 疊代次數對效能之影響 29
4.4平行架構中區塊切割之影響 31
4.5同步與非同步應用在平行架構之比較 32
第五章 結論與未來研究方向 34
5.1 結論 34
5.2 未來研究方向 35
參考文獻 36

書籍：
[1]Moon, Todd K., “Error Correction Coding Mathematical Methods”, John Wiley & Sons, 634-379
期刊論文：
[2]Falcao G, Yamagiwa S, Silva V et al., “Parallel LDPC decoding on GPUs using a stream-based computing approach,” JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 24(5): 913-924 Sept. 2009
[3]R. G. Gallager, “Low Density Parity Check Codes,”. IRE. Trans. Inf. Theory. IT:8:21-28, Jan. 1962
[4]D. J. C. MACKAY, “Near Shannon limit performance of Low Density Parity Check Codes,” Electron. Lett., vol. 33 , pp. 457-458, Mar. 1997
[5]Bormin H, Jarno M, Hyunjong O, H-L A.H., “Development of a GPU-based High-Performance Radiative Transfer Model for the Infrated Atmospheric Sounding Interferometer (IASI)”, Journal of Computational Physics
學位論文：
[6]詹慶達，低成本及閘架構之最小和演算法低密度奇偶校驗碼解碼器，碩士論文，國立雲林科技大學，雲林，民國97年。
[7]蕭志豪，適用於IEEE802.16e標準之多碼率LDPC解碼設計，碩士論文，國立中山大學，高雄，民國96年。
[8]賴碧蓮，以低密度同位檢查碼解碼機制運用於長迴旋之解碼，碩士論文，私立逢甲大學，台中，民國93年。
其他：
[9]NVIDIA(2008). “CUDA Programming Guide v2.0”, NVIDIA.
[10]張舒、褚艷利、趙開勇、張鈺勃，「GPU高性能運算之CUDA」，書籍，中國水利水電出版社，2009。
[11]MACKAY,“H-matrix”.http://www.inference.phy.cam.ac.uk/mackay/codes/data.html
[12]Igor V. Kozintsev,”H-to-G software”, http://www.kozintsev.net/soft.html