臺灣博碩士論文加值系統

本篇論文主要闡述低密度同位元檢查碼(Low-density parity-check codes)以及密度演化(Density evolution)。低密度同位元檢查碼是一線性區段碼，以置信傳播的疊代解碼演算法(Belief propagation algorithm)，在大量資料傳輸時提供逼近通道容量的效能。在良好的設計下，碼率為0.5的低密度檢查碼在二進位輸入可加性白高斯雜訊(binary-input AWGN)通道，與Shannon limit只差0.0045 dB。
密度演化是一種用來分析低密度同位元檢查碼非常直接有效的方式。在三種假設之下，利用電腦模擬找出二進位無記憶(Binary-input memoryless)通道在不同碼率的近似閾值(Threshold)。利用密度進化，可以得知所設計之低密度同位元檢查碼的好壞，並且進一步藉由密度進化我們可以去設計出更好的低密度同位檢測碼，當它的碼的長度為無窮大時，效能可達到Shannon limit。

In this paper, we demonstrate the Low-density parity-check (LDPC) codes and density evolution (DE). LDPC codes are a class of linear block codes which provide near-capacity performance on large data transmission by using belief propagation (BP) iterative decoding algorithm. In well design degree distribution, the rate 1/2 LDPC code can approach Shannon limit within 0.0045 dB for binary-input AWGN channels.
Density evolution is a very useful and straightforward method to analyze the LDPC codes. In three assuming conditions, we can simulation and find the threshold for different rates binary-input memoryless channel. By using density evolution, we could know the LDPC code that we designed performs well or not, and then find the good degree distribution for LDPC code via density evolution to achieve the Shannon limit asymptotically as the block length tends to infinity become possible.

目錄
頁碼
誌謝辭 II
中文摘要 III
ABSTRACT VI
目錄 V
圖目錄 VII
表目錄 VIII
第一章 簡介 1
1.1 簡介 1
1.2 論文架構 3
第二章 低密度同位檢查碼(LDPC Codes) 4
2.1 LDPC碼的表示法 5
2.1.1 矩陣表示法 5
2.1.2 圖形表示法(Tanner Graph) 5
2.1.3 Tanner圖的循環與周長(Cycle and Girth) 7
2.1.4 度分佈多項式(Degree Distribution Polynomials) 7
2.2 規則與不規則LDPC碼 9
2.2.1 規則LDPC碼(Regular LDPC Codes) 9
2.2.2 不規則LDPC碼(Irregular LDPC Codes) 10
2.3 LDPC碼的設計方式 11
2.3.1 規則LDPC碼 11
2.3.2 不規則LDPC碼 12
第三章 疊代解碼演算法 14
3.1 硬式解碼(Hard decoding) 14
3.1.1 Gallager第一解碼演算法(Gallager’s First Decoding
Algorithm) 15
3.1.2 Gallager第二解碼演算法(Gallager’s Second Decoding
Algorithm) 15
3.2 軟式解碼(Soft decoding) 16
3.2.1 訊息傳遞演算法MPA(Message Passing Algorithm) 17
3.2.2 機率領域和積演算法(Probability-Domain Sum-Product
Algorithm) 19
3.2.3對數領域和積演算法(Log-Domain Sum-Product Algorithm)
22
3.2.4 最小和演算法(Min-Sum Algorithm) 24
第四章 密度演化(Density Evolution) 25
4.1 對稱性假設(Symmetric Assumption) 26
4.2 通道模型、容量和穩態條件 28
4.3 BP演算法的密度演化描述 31
4.4 離散密度演化(Discrete Density Evolution) 36
4.5 錯誤率和閾值 39
第五章 數值分析結果及結論 41
5.1 數值分析結果 41
5.2 結論 46
參考文獻 47
附錄一 50
附錄二 52
作者簡介 53

參考文獻
[1] C.E. Shannon,　“A Mathematical Theory of Communication,”　Bell System Technical Journal, vol. 27,
pp. 379-423, 623-656, July, October, 1948.
[2] Richard E. Blahut,　“Principles and Practice of Information Theory,”　MA:Addison-Wesley, 1987.
[3] R. G. Gallager,　“Low-Density Parity-Check Codes,”　IRE Trans. Inform. Theroy, pp. 21-28, Jan.
1962.
[4] D. MacKay, R. Neal,　“Good codes based on very sparse matrices,”　in Proc. 5th IMA Conf.
Cryptography and Coding, C. Boyd, Ed., Lecture Notes in Computer Science, pp. 100-111, Berlin,
Germany: Springer, 1995.
[5] Presentation by Hughes Systems.(http://ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf)
[6] HomePNA Blog: G.hn, a PHY For All Seasons.
(http://homepnablog.typepad.com/my_weblog/2008/12/index.html)
[7] J. Pearl,　“Probabilistic Reasoning in Intelligent Systems: Networks of PlausibleInference,”　San
Mateo, CA: Morgan Kaufmann, 1988.
[8] D. MacKay,　“Good error correcting codes based on very sparse matrices,” IEEE Trans. on Inform.
Theory, vol. 45, pp. 399–431, Mar. 1999.
[9] T. Richardson and R. Urbanke,　”The capacity of low-density parity-check codes under message-
passing decoding,”　IEEE Trans. Inform. Theory, vol. 47, pp. 599-618, Feb. 2001.
[10] Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spiel-man.　“Analysis of low-
density parity-check codes and improved designs using irreg-ular graphs.”　30th ACM STOC, May 23-
26 1998.
[11] R. G. Gallager,　“Low-Density Parity-Check Codes,”　Cambridge, MA: MIT Press, 1963.
[12] R. M. Tanner,　“A recursive approach to low complexity codes,”　IEEE Trans. on Inform. Theory,
vol. 27, pp. 533–547, Sept. 1981.
[13] T. J. Richardson, M. Shokrollahi, and R. Urbanke,　“Design of capacity-approaching irregular low-
density parity-check codes,”　IEEE Trans. on Inform. Theory, vol. 47, pp. 619-637, Feb. 2001.
[14] M. Luby, M.Mitzenmacher, M. Shokrollahi, and D. Spielman,　“Improved low-density parity-check
codes using irregular graphs,”　IEEE Trans. on Inform. Theory, vol. 47, pp. 585-598, Feb. 2001.
[15] S. Y. Chung, G. D. Forney, T. J. Richardson, and R. Urbanke,　“On the design of low-density parity-
check codes within 0.0045 dB of the Shannon limit,”　IEEE Commun. Letters, vol. 5, pp. 58–60, Feb.
2001.
[16] M. Yang, Y. Li, and W. E. Ryan,　“Design of efficiently encodable moderate-length high-rate
irregular LDPC codes,”　Proc. 40th Annual Allerton Conf. on Commun., Control, and Computing,
Champaign, IL., pp. 1415-1424, Oct. 2002.
[17] T. J. Richardson, R. Urbanke,　“Efficient encoding of low-density parity-check codes,”　IEEE
Trans. on Inform. Theory, vol. 47, pp. 638-656, Feb. 2001.
[18] J. Hagenauer, E. Offer, and L. Papke,　“Iterative decoding of binary block and convolutional
codes,”　IEEE Trans. on Inform. Theory, vol. 42, pp. 429-445, Mar. 1996.
[19] H. Tang, J. Xu, S. Lin, and K. A. S. Abdel-Ghaffar,　“Codes on finite geometries,”　IEEE Trans.
Inform. Theory, vol. 51, no. 2, pp. 572-596, Feb. 2005.
[20] H. Xiao and A. H. Banihashemi,　“Graph-based message-passing schedules fordecoding LDPC codes,”　
IEEE Trans. Commun., vol. 52, no. 12, pp. 2098-2105, Dec. 2004.
[21] X. Y. Hu, E. Eleftherious, D. M. Arnold, and A. Dholakia, “Efficient implementation of the sum-
product algorithm for decoding LDPC codes,” Proc. 2001 IEEE GlobeCom Conf., pp.1036-1036E, Nov.
2001.