(3.230.76.48) 您好!臺灣時間:2021/04/11 09:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:徐偉峪
研究生(外文):Wei-yu Hsu
論文名稱:從運算樹及覆輒~中尋找偽編碼字之研究
論文名稱(外文):Finding Pseudo-codewords on Computation Tree and Graph-covers
指導教授:陸曉峰陸曉峰引用關係
指導教授(外文):Hsiao-feng Lu
學位類別:碩士
校院名稱:國立中正大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:46
中文關鍵詞:迭代演算法低密度同位元檢查碼偽編碼字偽權重運算樹覆遜
外文關鍵詞:graph-covercomputation treepseudo-weightpseudo-codeworditerative decodingLDPC code
相關次數:
  • 被引用被引用:0
  • 點閱點閱:159
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
低密度同位元檢查碼(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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔