LDPC碼之低複雜度解碼演算法—結合型解碼演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：95

、訪客IP：3.137.187.229

姓名

許恭睿(Kung-jui Hsu) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

LDPC碼之低複雜度解碼演算法—結合型解碼演算法
(Low Complexity Decoding Algorithm of LDPC Codes—The Combined Decoding Algorithm)

相關論文

★ Branch and Bound 演算法在全光網路包含串音局限的限制條件之最佳化規劃效能分析	★ 平行式最佳區塊碼解碼演算法
★ 數位廣播之視訊系統架構與信號估測	★ 粒子群優化演算法應用於電信業解決方案選商及專案排程之優化
★ 結合PSO及K-Means聚類分析演算法的圖像分割	★ 利用粒子群優化演算法改善分群演算法在訊號分群上之應用
★ 應用模糊聚類與粒子演算法之色彩分群研究	★ 粒子群優化演算法應用於企業更新數據網路採購之優化
★ 粒子群演算法應用於無線區域網路產品硬體開發成本優化	★ 粒子群演算法應用企業伺服器負載平衡之省電優化
★ 粒子群優化演算法應用於瓦斯業微電腦瓦斯表自動讀表之優化	★ 近場通訊之智慧倉儲管理
★ 在Android 平台上實現NFC 室內定位	★ 適用於訊號傳輸暨無線電力傳輸之設計
★ 結合PSO及圖像品質評估演算法識別頻譜訊號	★ 粒子群優化與二維Otsu演算法於影像二元化閥值選取研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

LDPC(Low-Density Parity-Check)碼為下個世代的先進通訊標準所採用的錯誤更正碼，其優異的錯誤更正能力可以逼近Shannon的理論值，配合Sum-Product演算法以訊息傳遞的方式來解碼，可以快速得到傳送端所發出的訊息。但Sum-Product演算法之解碼複雜度偏高為主要缺點，故本篇論文將結合低複雜度解碼演算法與改善迴圈效應演算法，在不犧牲解碼效能的條件下，降低Sum-Product演算法之解碼複雜度。
結合型解碼演算法利用設定門限值(Threshold)的方式，排除部分位元節點以減少參與解碼的位元節點個數，接著在每次疊代運算完成後，判斷位元節點之值是否異號而產生振盪(Oscillation)的現象，並將振盪之位元節點加以修正，改善迴圈效應，以補償因降低解碼複雜度而衰減的效能。
經由模擬與分析的結果可知，低複雜度解碼演算法所降低的複雜度遠大於改善迴圈效應演算法所增加的複雜度，故結合型解碼演算法之複雜度確實低於Sum-Product演算法，且若設定理想的門限值，即可達到與Sum-Product演算法相同之解碼效能。

摘要(英)

LDPC code is an error-correcting code used by the advanced communication standard of the next generation. Its error correction ability may approach the Shannon limit. Decoding by the Sum-Product algorithm with the method of message passing, we can decode the received samples at high speed. The decoding complexity of this algorithm, however, is its major disadvantage. In this thesis, we combine the low-complexity decoding algorithm and the improved cycle-effect algorithm to reduce the complexity of Sum-Product algorithm without degrading performance.
Our combined decoding algorithm ignores some bit nodes by setting a threshold to decrease the number of decoding bit nodes. At the start, we first find those nodes whose values are oscillating and then try to modify them so that the cycle effect is reduced and the performance is improved.
Our results show that the low-complexity decoding algorithm has much lower complexity than that of the cycle-effect one. So the complexity of the combined decoding method is lower than that of the Sum-Product one. If a threshold is properly set, the performance of the proposed algorithm will be close to that of the Sum-Product one.

關鍵字(中)

★ 位元節點
★ 低複雜度解碼
★ 低密度同位檢查碼

關鍵字(英)

★ Bit nodes
★ Low complexity decoding
★ LDPC codes

論文目次

摘要 i
Abstract ii
目錄 iv
圖目錄 vi
表目錄 viii
第一章緒論 1
1-1 LDPC碼簡介 1
1-2 研究動機與內容 3
1-3 本篇論文組織 3
第二章線性區塊碼與LDPC碼 4
2-1 線性區塊碼 4
2-1-1 線性區塊碼之定義 4
2-1-2 生成矩陣與同位檢查矩陣 5
2-1-3 漢明權重與漢明距離 7
2-2 LDPC碼 9
2-2-1 LDPC碼之定義 9
2-2-2 LDPC碼之Tanner Graph 11
2-2-3 LDPC碼之屬性 12
第三章解碼演算法 14
3-1 Message Passing演算法 14
3-1-1 Sum-Product演算法 15
3-1-2 Min-Sum演算法 20
3-2 低複雜度解碼演算法 21
3-3 改善迴圈效應演算法 23
3-4 結合型解碼演算法 25
第四章模擬與分析 27
4-1 系統模型 27
4-2 模擬結果與分析 28
第五章總結 41
參考文獻 42
附錄 44

參考文獻

[1] C. E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., vol. 27, pp. 379-423(Part 1); pp. 623-656(Part 2), July 1948.
[2] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1962.
[3] R. G. Gallager, “Low-Density Parity-Check Codes,” MIT Press, Cambridge, MA, 1963.
[4] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 533-547, Sept. 1981.
[5] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, no. 18, pp. 1645-1646, Aug. 1996.
[6] 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 Comm. Lett., vol. 5, no. 2, pp. 58-60, Feb. 2001.
[7] Kwangho Shin and Jungwoo Lee, “Low Complexity LDPC Decoding Techniques with Adaptive Selection of Edges,” Vehicular Technology Conference, pp. 2205-2209, Spring 2007.
[8] Satoshi Gounai, Tomoaki Ohtsuki, Toshinobu Kaneko, “Modified Belief Propagation Decoding Algorithm for Low-Density Parity Check Code Based on Oscillation,” Vehicular Technology Conference, pp. 1467-1471, Spring 2006.
[9] John L. Fan, “Constrained coding and soft iterative decoding,” Kluwer Academic Publishers, 2001.
[10] Marc P. C. Fossorier, Miodrag Mihaljevic, and Hideki Imai, “Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation,” IEEE Trans. Comm., vol. 47, no. 5, May. 1999.
[11] G. Lechner, and J. Sayir, “On the convergence of log-likelihood values in iterative decoding,” Mini-Workshop on Topics in Information Theory, Sept. 2002.
[12] G. Lechner, “Convergence of sum-product algorithm for finite length low-density parity-check codes,” Winter School on Coding and Information Theory, Feb. 2003.
[13] D. J. C. MacKay：劍橋大學Cavendish實驗室網站。2008年6月1日，取自http://www.inference.phy.cam.ac.uk/mackay/codes/data.html。
[14] 林銀議，數位通訊原理—編碼與消息理論，一版，五南出版社，2005。

指導教授

賀嘉律(Chia-lu Ho)

審核日期

2008-7-17

推文