簡易檢索 / 詳目顯示

研究生: 費冠華
Fei, Guan-Hua
論文名稱: 使用同位元檢查錯誤偵測之低密度同位元檢查碼解碼器之低計算複雜度停止準則設計
Low-Complexity Stopping Criterion for LDPC Decoding using Parity-Check Errors Detection
指導教授: 謝明得
Shieh, M.D.
學位類別: 碩士
Master
系所名稱: 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年: 2006
畢業學年度: 94
語文別: 英文
論文頁數: 72
中文關鍵詞: 低密度同位元檢查碼停止準則變數節點可靠度分析
外文關鍵詞: VNR, stopping criterion, LDPC
相關次數: 點閱:47下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 低密度奇偶檢查碼(Low-Density Parity-Check)解碼
    時,是利用疊代來提高解碼的正確性,但是過多不必要之
    疊代次數會造成多餘的功率消耗以及時間浪費。解決這兩
    個問題大略有兩個方向: 快速收斂架構和停止準則。快速
    收斂架構是一種使解碼器能在較少的疊代次數下達成收斂
    之設計方法,現有的方法包含:循環冗餘查核(Cyclic Red
    undancy Check)和高斯-賽德演算法(Gauss-Seidel Algor
    ithm)等。停止準則是利用已知的資訊,決定何時要停止疊
    代的機制,現有的方法包含: 硬性判決法(Hard-Decision
    Aided)、變數節點可靠度分析(Variable Node Reliability)
    和循環冗餘查核。
    雖然利用變數節點可靠度分析來判斷解碼中的碼字是
    否無法解碼成功,可以明顯的降低平均疊代次數,但是因
    為其要將所有變數節點的可靠性全部加起來判斷,因此需
    要相當大的運算量;於本論文中,我們提出藉由同位元檢
    查錯誤偵測(Parity-Check Errors Detection)之方法來尋
    找無法解碼成功的碼字,此方法只需要將查核節點所作的
    結果總和起來判斷,因此其所需求的計算量就較變數節點
    少,實驗結果亦顯示其錯誤率仍然很接近未加停止準則前
    的解碼器。

    Iterative decoding has been used in low-density parity-check (LDPC) codes to improve 
    its performance; however, unnecessary iterations will cause a waste of power consumption and 
    time. To overcome this problem, two types of techniques have been proposed in the literature: 
    Fast Convergence Scheme and Stopping Criterion. Fast convergence schemes make decoding algorithm 
    converge with fewer iterations such as Cyclic Redundancy Check (CRC), and Gauss-Seidel Algorithm. 
    On the other side, stopping criterion extracts some information at each iteration step to determine 
    when to stop decoding. The existing methods include Hard-Decision Aided (HDA), Variable Node 
    Reliability (VNR), and CRC, etc.
    By way of detecting the un-decodable words, the VNR method can obviously reduce the average 
    number of iterations. The price paid is the relatively complicated process to sum up the reliabilities 
    of all variable nodes for the stopping criterion. Since it leads to quite huge computation complexity, 
    we proposed another method called Parity-Check Errors Detection (PCED) to find out the un-decodable 
    words. The proposed method just makes the judgment through the result of all check equations, so 
    its computation complexity is much lower than VNR. Experimental results also reveal that the bit 
    error rate (BER) of PCED is close to that of the original decoding without introducing stopping 
    criteria.

    TABLE OF CONTENTS                                 vi LIST OF TABLES                                  ix LIST OF FIGURES                                  x Chapter 1 Introduction                               1 1.1 Overview of Channel Coding in Digital Communication Systems       1 1.2 Motivation                                   3 1.3 Organization of This Thesis                         4 Chapter 2 Low-Density Parity-Check Codes                     5 2.1 Parity-Check Matrix H                             5 2.2 Encoding of LDPC Codes                             7 2.3 Decoding of LDPC Codes                             8 2.3.1 Gallager's LDPC Decoding                          9 2.3.2 Message-Passing Algorithm                          11 2.3.3 Log-Domain Decoding                             15 2.3.4 Check Node                                 18 2.3.5 Variable Node                                19 2.4 Girth of Parity-Check Matrix H                       20 2.5 Issues of LDPC Codes                             20 Chapter 3 Stopping Criterion and Fast Convergence Scheme for LDPC Codes  22 3.1 Parity-Check                                  22 3.2 Hard Decision Aided (HDA)                          22 3.3 Variable Node Reliability (VNR)                       23 3.4 Cyclic Redundancy Check (CRC)                         25 3.5 Gauss-Seidel Iteration Algorithm (GS)                    26 3.6 Discussion                                   27 Chapter 4 Experiments on Reliability Trend of Message            29 4.1 Reliability Trend of Message                        29 4.2 Experiment of Reliability Trend                       30 4.2.1 Fixed Addition Method (FAM)                        31 4.2.2 Dynamic Addition Method (DAM)                       32 4.2.3 Results for Four Successive Iterations                  37 4.3 Discussion                                   39 Chapter 5 Parity-Check Error Detection (PCED) Stopping Criterion       40 5.1 Relation between the Number of Parity-Check Errors and Erroneous Bits 41 5.2 Variation of the Total Number of Parity-Check Errors (TPCE)      46 5.3 Detection of the Total Number of Parity-Check Errors (TPCE)      48 5.3.1 Veer of TPCE                                49 5.3.2 Fixed Model of TPCE                            52 5.3.3 Ripple Model of TPCE                           53 5.3.4 Flow Chart of PCED Stopping Criterion                  54 5.4 Gauss-Seidel Iteration for Irregular LDPC with PCED Stop Rule     56 5.5 Discussion                                   59 Chapter 6 Conclusion and Future Work                      63 6.1 Conclusion                                   63 6.2 Future Work                                  64 Appendix A                                     65 A.1 Proof of Initial Value of LDPC Decoding                 65 A.2 Proof of Passing Reliability from Check Node to Variable Node     66 A.3 Proof of Lemma 2.3.3                            68 A.4 Proof of Phi-Function                            69 References                                     71

    [1] Simon Haykin, Communication Systems 4th Edition, 2001.
    [2] S. Lin and D. J. Costello, Error Control Coding Fundamentals and Applications Second Edition, 2004.
    [3] R.G. Gallager, “Low-Density Parity Check Codes,” IRE Transactions on Information Theory, Volume IT-8, pp.21-28, 1962.
    [4] T. Richardson and R. Urbanke, “The Renaissance of Gallager’s Low-Density Parity-Check Codes,” IEEE Communications Magazine, Volume 41, Issue 8, pp.126-131, Aug. 2003.
    [5] R. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Transactions on Information Theory, Volume 27, Issue 5, pp.533-547, Sep. 1981.
    [6] Z.W. Li, L. Chen, L. Zeng, S. Lin and W. Fong, “Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes,” in Proc. IEEE Globecom, Volume 3, pp.6, 28, Nov.-2 Dec. 2005.
    [7] Z.W. Li, L. Chen, L. Zeng, S. Lin and W.H. Fong, “Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes,” IEEE Transactions on Communications, Volume 54, Issue 1, pp.71-81, Jan. 2006.
    [8] D.E. Hocevar, “Efficient Encoding for a Family of Quasi-Cyclic LDPC Codes,” in Proc. IEEE Globecom, Volume 7, 1-5, pp.3996-4000, Dec. 2003.
    [9] M.P.C. Fossorier, “Quasi-Cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices,” IEEE Transaction on Information Theory, Volume 50, No.8, Aug. 2004.
    [10] H. Zhang and J.M.F. Moura, “Large-Girth LDPC Codes based on Graphical Models,” IEEE Workshop on Signal Processing Advances in Wireless Communications, pp.100-104, June 2003.
    [11] H. Zhang and J.M.F. Moura, “The Design of Structured Regular LDPC Codes with Large Girth,” in Proc. IEEE Globecom, Volume 7, pp.4022-4027, Dec. 2003.
    [12] M. Fujisawa and S. Sakata, “A Class of Quasi-Cyclic Regular LDPC Codes from Cyclic Difference Families with Girth 8,” in Proc. International Symposium on Information Theory, pp.2290-2294, Sept. 2005.
    [13] J. Lu and J.M.F. Moura, “Partition-and-Shift LDPC Codes,” IEEE Transactions on Magnetics, Volume 41, Issue 10, pp.2977-2979, Oct. 2005.
    [14] M.M. Mansour and N.R. Shanbhag, “High-Throughput LDPC Decoders,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 11, Issue 6, pp.976-996, Dec. 2003.
    [15] F. Kienle and N. Wehn, “Low Complexity Stopping Criterion for LDPC Codes Decoders.” in Proc. IEEE on Vehicular Technology Conference, Volume 1, 30 May-1, pp.606-609, June 2005.
    [16] Y.H. Kwon, M.K. Oh and D.J. Park, “A New LDPC Decoding Algorithm Aided by Segmented CRCs for Erasure Channels,” in Proc. IEEE on Vehicular Technology Conference, Volume 1, pp.705-708, 30 May-1 June 2005.
    [17] Y.H. Kwon, M.K. Oh and D.J. Park, “A New LDPC Decoding Algorithm Aided by Segmented CRCs for Magnetic Recording Channels,” IEEE Transactions on Magnetic, Volume 41, Issue 7, pp.2318-2320, July 2005.
    [18] J. Kim, N. Kim and H. Park, “Fast Convergence Decoding Scheme for Regular LDPC Codes,” in Proc. International Symposium on Intelligent Signal Processing and Communication Systems, pp.454-458, Nov. 2004.
    [19] O.S. Chauhan, T.K. Moon and J.H. Gunther, “Accelerating the Convergence of Message Passing on Loopy Graphs Using Eigenmessages,” IEEE on Signals, Systems and Computers, Volume 1, 9-12, pp.79-83, Nov. 2003.
    [20] J. Heo, K. Chung and K.M. Chugg, “Simple Stopping Criterion for Min-Sum Iterative Decoding Algorithm,” IEE Electronics Letters, Volume 37, Issue 25, pp.1530-1531, 6 Dec. 2001.

    下載圖示 校內:2009-08-31公開
    校外:2009-08-31公開
    QR CODE