LDPC碼之信息傳遞解碼演算法—調適性選擇位元節點之分析

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：50

、訪客IP：3.145.102.187

姓名

林仕元(Shih-yuan Lin) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

LDPC碼之信息傳遞解碼演算法—調適性選擇位元節點之分析
(Message Passing Decoding Algorithm of LDPC Codes—Analysis of Adaptively Selecting Bit Nodes)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

LDPC(Low-Density Parity-Check)碼為下個世代的先進通訊標準所採用的錯誤更正碼，其優異的錯誤更正能力可以逼近Shannon的理論值，配合訊息傳遞(Message Passing , MP)演算法，可以快速得到傳送端所發出的訊息，雖然該演算法在解碼方面有很好的效能，但因為其複雜度偏高，所以，很多研究都在探討如何改善複雜度，又不會使其效能嚴重的衰減。在本論文中，基於和積演算法(Sum-Product algorithm , SPA)為軟式解碼法中最佳的解碼演算法，而針對此解碼法提出三種不同疊代分配的方式來做分析，調適的選擇出部份位元節點來替代所有的位元節點，減少其運算量，在疊代解碼失敗時，依所分配的疊代次數，增加位元節點的運算來更新檢查節點，其在最後幾次疊代時將回歸至Sum-Product演算法，有效的降低運算複雜度，在效能上也沒有嚴重的衰減。

摘要(英)

LDPC code is an error-correcting code which is adopted for the next generation’’s advanced communication standard. Its error-correcting ability may approach the Shannon’s theoretical value. With the MP algorithm, it can decode received samples in high speed from transmitter. This algorithm has a good performance in the decoding aspect, but its complexity is higher. Thus, many researchers discuss how to improve complexity without making the performance reduced seriously. In this thesis, the SPA(Sum-Product algorithm) is the best decoding algorithm in soft-decoding to aim at this decoding method which proposes three different ways in the distribution of iteration to do analysis. The method adjusts bit nodes to substitute all bit nodes, and reduces the quantity of operations. When the iteration decoding fails, we increase number of bit nodes and update the message of the check nodes according to the result of the iteration. Finally, its several iterations will return to Sum-Product algorithm. Therefore, it effectively reduces the complexity and without seriously weaken its performance.

關鍵字(中)

★ 錯誤更正碼
★ 和積演算法
★ 調適性

關鍵字(英)

★ Sum-Product algorithm
★ LDPC
★ Adaptive

論文目次

中文摘要 I
Abstract II
目錄 IV
圖目錄 VI
表目錄 VIII
第一章前言 1
1.1 研究內容與論文動機 1
1.2 論文組織 1
第二章 LDPC Code 2
2.1 線性區塊碼 2
2.1.1 線性區塊碼定義 2
2.1.2 生成矩陣與同位元檢查矩陣 3
2.1.3 漢明權重與漢明距離 6
2.2 LDPC Codes之介紹 8
2.2.1 LDPC Code定義 10
2.2.2 Tanner Graph 12
2.3 LDPC Codes之設計架構類型 13
2.3.1 隨機構造方法 13
2.3.1.1 規則性(Regular) LDPC Codes 14
2.3.1.2 不規則性(Irregular) LDPC Codes 14
2.3.2 代數構造方法 15
2.4 LDPC Codes之編碼法 17
第三章解碼演算法 20
3.1 Message Passing演算法 21
3.1.1 Sum-Product algorithm 22
3.1.2 Min-Sum algorithm 29
3.1.3 Normalized BP-Based algorithm 30
3.1.4 Offset BP-Based algorithm 32
3.2 低複雜度解碼演算法 32
3.2.1 Algorithm 1 32
3.2.2 Algorithm 2 35
3.3 解碼演算法 37
3.3.1 動機 37
3.3.2 提出減少運算量的機制 37
第四章模擬結果與分析 43
第五章結論 54
參考文獻 55
附錄 57

參考文獻

[1] C. E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., pp. 379-423(Part 1); pp. 623-56(Part 2), July 1948.
[2] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, pp. 21-28, vol. 8, no. 1, 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. 74, no. 2, pp. 533-547, Sept. 1981.
[5] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” IEE 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. COMM-5, no. 2, pp. 58-60, Feb. 2001.
[7] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Trans. Inf. Theory, 45, pp. 399–432, March 1999
[8] Y. Kou, S. Lin, and M. P. Fossorier, “Low-density parity-check codes based on finite geometries: a rediscovery and new results,” IEEE Trans. Inform. Theory, Vol. 47, no. 7, pp. 2711–2736, Nov. 2001.
[9] John L. Fan ,“Constrained coding and soft iterative decoding” Kluwer Academic Publishers, 2001.
[10] Kwangho Shin, Jungwoo Lee, “Low Complexity LDPC Decoding Techniques with Adaptive Selection of Edges,” in VTC2007, Apr. 2007, pp. 2205-2209.
[11] M. Miladinovic, M. P. C. Fossorier and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE Trans. Commun., Vol. 47, pp. 673-680, May 1999.
[12] J. Chen and M. P. C. Fossorier, “Near optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Comm. Lett., Vol. 50, pp. 406-414, March 2002.
[13] Cavus. E, Daneshrad, B,“A Computationally efficient selective node updating scheme for decoding of LDPC codes,” in MILCOM 2005, Oct.2005, pp1375-1379.
[14] Eun-A Choi, Dae-IK Chang, Deock-Gil Oh, Electronics and Telecommunications Research Institute, Ji-Won Jung, Korea Maritime University, “Low Computational Complexity Algorithm of LDPC Decoder for DVB-S2 Systems,” in VTC05, Sep. 2005.
[15] 林銀議, “數位通訊原理編碼與消息理論,” 五南, 2005.
[16] David J.C MacKay:Cavendish Laboratory, Cambridge. Get from http://www.inference.phy.cam.ac.uk/mackay/codes/data.html

指導教授

賀嘉律(Chia-Lu Ho)

審核日期

2008-7-16

推文