臺灣博碩士論文加值系統

低密度同位元檢查碼（Low Density Parity-check Code, LDPC）最初在西元1962年由趕瘜掑h（Dr. Gallger）發表。此編碼可說是被遺忘了將近四十年，近幾年才發掘到它良好的效能，而對它的研究才開始熱門了起來。
LDPC的解碼是在譚能圖（Tanner graph)上進行，而最近的研究指出，譚能圖就是影響解碼效能的關鍵。但是譚能圖為甚麼會影響效能的問題並沒有很明確的答案。而偽編碼字（pseudo-codeword）以及偽權重（pseudo-weight）則被視為最有可能的解答之一。
前人研究顯示，由收斂到何編碼字的角度來看LDPC碼的解碼效能，不再是由最小漢明距離（minimum Hamming distance）決定，取而代之的則是最小偽權重。尋找偽編碼字以及偽權重的方法有兩派，一是由原本譚能圖所展開的運算樹（computation tree），另一則是延展成覆遜洁]graph-cover）來計算。兩種方法的偽編碼字的定義也不盡相同。運算樹本身有嚴謹的理論支持，而覆遜洏豪郃繭L明確的理論證明他與解碼器的收斂有直接關係。
事實上，無論使用運算樹或是覆遜洁A想要用偽權重來分析已知的編碼幾乎是不可能的。由最簡單的例子我們可以發現，尋找最小偽權重的計算量遠遠超過找出其最小漢明距離上兆倍不只，而我們早已知道，尋找最小漢明距離本身已經是個NP complte的問題。
本論文將介紹這兩種方法，並且提供尋找偽編碼字以及偽權重的演算法。最後，雖然找出最小偽權重本身如此困難，我們仍然採用最簡單的漢明碼（Hamming code），盡量演練此兩種方法的實用性以及正確性。

Earlier work of LDPC codes showed that Tanner graph mainly affects the decoding
performance of iterative decoding. Pseudo-codewords and pseudo-weights on
Tanner graph are found playing an important rule in determining the performance.
Computation tree and graph covers are proposed by different researchers to find
the pseudo-codewords and pseudo-weights. Definitions of pseudo-codeword using
computation tree and graph-cover are somewhat different. Actually, neither
computation tree or graph-covers is a good tool to analysis any known codes. In
this thesis we will introduce both approachers and the corresponding algorithms.
Also, the simulation result will be shown.

1 Introduction 3
2 Background 6
2.1 Linear block codes . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Tanner graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Decoding algorithms based on Tanner graphs . . . . . . . . . . . 9
3 Computation Tree of A Tanner Graph 15
3.1 Introduction to computation tree . . . . . . . . . . . . . . . . . . 15
3.2 Basics of computation tree . . . . . . . . . . . . . . . . . . . . . 16
3.3 Pseudo-codewords and Pseudo-weights on Computation Tree . . . 18
3.4 Parity check matrix of computation tree . . . . . . . . . . . . . . 22
4 Graph Covers of A Tanner Graph 26
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Basices of Graph Covers . . . . . . . . . . . . . . . . . . . . . . 27
4.3 Parity-Check Matrix of Graph Covers . . . . . . . . . . . . . . . 29
5 Simulation 33
5.1 Computation tree of (7, 4, 3) Hamming code . . . . . . . . . . . . 34
5.2 Graph-covers of (7, 4, 3) Hamming code . . . . . . . . . . . . . . 39
6 Conclusion 42

[1] R. Gallager, Low-density parity-check codes, in IRE Trans. Information Theory, pp. 21-28, Jan, 1962.
[2] R. M. Tanner,, A recursive approach to low complexity codes, in IEEE Trans,
Information Theory, pp. 533-547, Sept, 1981.
[3] N.Wiberg, Codes and Decoding on General Graphs. PhD thesis, University
of Linkoping, Sweeden, 1996.
[4] D. Mackay and R. Neal, Good codes based on very sparse matrices, in Cryptography and Coding, 5th IMA Conf., C. Boyd, Ed., Lecture Notes in Computer Science,pp. 100-111, Berlin, Germany, Spring, 1995.
[5] W. E. Ryan, An Introduction to LDPC Codes, The University of Arizona, Box 210104, Tucson, AZ 85721, Aug. 19,2003.
[6] R. Koetter and P.O. Vontobel, Graph-covers and iterative decoding of finite
length codes, in Proceeding of the IEEE International Symposium on Turbo Codes and Applications. , (brest, France), Sept, 2003.
[7] C. Kelley, D. Sridhara, Pseudocodeword of Tanner Graphs, Apr 5, 2005, submitted to IEEE Trans on Information Theory.