LDPC碼之混和解碼法-MP法與A*演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：114

、訪客IP：18.191.5.239

姓名

楊旭弘(Hsu-Hung Yang) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

LDPC碼之混和解碼法-MP法與A*演算法
(On the Hybrid Decoding Method for LDPC Code by Using the Message Passing and the A* Algorithms)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

LDPC(Low-Density Parity-Check)碼為下個世代的先進通訊標準所採用的錯誤更正碼，其優異的錯誤更正能力可以逼近Shannon的理論值，配合訊息傳遞(message passing, MP)演算法，可以快速得到傳送端所發出之訊息。但是MP法不保證得到為最佳的解碼結果，故在本論文裡，將把它和A*法結合作混和解碼，但同時也把它們的優缺點作比較，由結果發現，A*法的編碼增益較MP法高，但是解碼的複雜度隨碼長度呈指數性增加，而非如MP法的線性增加。
若採用混和式架構，則可以得到與A*相同的編碼增益，同時解碼複雜度只略大於MP法。當使用碼長96 bits、碼率為1/2的LDPC碼，並在BER = 10E-5時，本論文所提出之混和式架構比MP法提高1.4 dB的編碼增益，經實驗統計結果得知約只有1%的接收序列在第一階段MP法不成功時，要轉入第二階段的A*法，因為A*法保證得到最佳解。故混和式架構的解碼方式，可以在編碼增益(由A*法所提供)與解碼複雜度(只有約1%的序列要作A*法，剩餘的約99%序列由快速的MP法解出)之間取得一個平衡。

摘要(英)

LDPC code used by the advanced communication standard of the next generation is an error control code. Its error correction ability may approach the Shannon’s theoretical value. With the MP algorithm, it can decode received samples in high speed from transmitter. However, the MP method is suboptimum and optimum solution is not guaranteed. In this thesis, a hybrid decoding method is formed by combing the MP and the A* methods. We first make comparison between the MP and A* method and then show their combined performance. From the results, the coding gain of A* model is higher than that of MP model. The decoding complexity increases exponentially with the codeword length for A* method, but the MP method assumes linear increase.
Using the hybrid structure, its coding gain is the same as that of A* method. Moreover, decoding complexity is slightly greater than that of MP one. For codeword length 96 bits and coding rate 1/2 and BER = 10E-5, the hybrid structure outperforms 1.4 dB coding gain than the MP method. This improvement only required 1% received sequences to be sent to A* decoding block. Our newly designed hybrid structure can solve both of the high coding gain and low decoding complexity while it has the ability to yield the optimum solution.

關鍵字(中)

★ A*演算法
★ 訊息流通演算法
★ 低密度奇偶檢查碼

關鍵字(英)

★ A* algorithm
★ message passing algorithm
★ LDPC Code

論文目次

中文摘要 IV
Abstract V
目錄 VII
圖目錄 IX
表目錄 X
第一章緒論 1
1.1 LDPC碼簡介 1
1.2 研究內容與論文設計動機 2
第二章 LDPC碼之簡介 4
2.1 線性區塊碼(Linear Block Code) 4
2.1.1 線性區塊碼定義 4
2.1.2 生成矩陣與奇偶檢驗矩陣 4
2.1.3 漢明權數與漢明距離 7
2.2 LDPC碼 9
2.2.1 LDPC碼之Tanner圖 9
2.2.2 LDPC的屬性 10
2.3 LDPC碼之碼字距離分析 11
2.3.1 Gallager碼之距離函數 11
2.3.2 自由位元列舉序列集合之平均碼字個數上界 15
第三章解碼演算法 20
3.1 Message Passing演算法 20
3.1.1 事後機率域 20
3.1.2 LLR域 22
3.2 A*演算法 25
3.2.1 簡介 25
3.2.2 路徑成本函數 27
3.2.3 解碼原理 28
3.2.4 接收訊號之排序 30
3.2.5 生成矩陣排序之問題 33
第四章電腦模擬 34
4.1 系統模型 34
4.2 模擬結果與分析 40
第五章總結 48
參考文獻 49

參考文獻

[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] T. J. Richardson, M. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” IEEE Trans. Inform. Theory, pp. 619-637, Feb. 2001.
[8] L. Ekroot and S. Dolinar, “A* Decoding of Block Codes,” IEEE Trans. Commun., vol. 44, pp. 1052-1056, Sept. 1996.
[9] John L. Fan ,“Constrained coding and soft iterative decoding” Kluwer Academic Publishers, 2001.
[10] O. Collins, “Coding beyond the computational cutoff rate,” Ph.D. dissertation, California Institute of Technology, Pasadena, CA, 1989.
[11] 林銀議, “數位通訊原理編碼與消息理論,” 五南, 2005.

指導教授

賀嘉律(Chia-Lu Ho)

審核日期

2006-7-12

推文