研究生: |
費冠華 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.
[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.