LDPC碼的位元翻轉解碼的改進

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：66

、訪客IP：18.227.46.43

姓名

張書瑋(Shu-wei Zhang) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

LDPC碼的位元翻轉解碼的改進
(Improved Bit-Flipping Decoding of Low-Density Parity-Check Codes)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

利用訊息傳遞解碼演算法，我們發現在解碼方面有很好的效能，但因為其複雜度偏高，所以，很多研究都在討論如何改善複雜度，又不會使效能嚴重的衰減。相對於硬式解碼演算法在效能方面不像軟式解碼演算法這麼出色，因此，較少的研究提出來改善硬式解碼演算法。不過，硬式解碼演算法也有優點，像是複雜度低、易於硬體實現。在這篇論文，主要是要討論低複雜度的解碼演算法，因為每次疊代只更正ㄧ個位元節點，所以，需要多次疊代才能完成解碼動作。因此，在這裡提出ㄧ個方法，就是利用位元節點間的不相關性，判斷哪些位元節點是要翻轉，並且隨著疊代越多次，表示位元節點越來越可靠，不可任意翻轉，有一機制來判定是否要翻轉多位元節點。在每次疊代翻轉多個位元節點，可以發現疊代次數在較少的情況下，每次疊代翻轉多個位元節點的效能比每次疊代翻轉一個位元節點好很多。當要達到相同的效能時，每次疊代翻轉多個位元節點，可使用較少的疊代數目即可達到，因此，可以有效的節省解碼時間，提高解碼速度。

摘要(英)

Utilize the message-passing decoding algorithm , we find that there is very good performance in decoding. But, because its complexity is on the high side, a lot are studying and discussing how to improve complexity , and it will not make the performance decay seriously. Decode algorithm of performing in efficiency as to hard type as soft to is it perform algorithm so outstanding to decode. So, less research puts forward and improves the performance of hard-decision decoding algorithms. However, the hard-decision decoding algorithms have some advantages. as if low complexity, and realizing of hardware easily. In this thesis , I will mainly discuss decoding algorithms of low- complexity, because it corrects one bit-node per iteration. so, it needs many iterations to finish decoding movements . Hence, I propose a method here. Utilizing the non-correlation of bits nodes and than judging what bit nodes to be flipped. As increasing the frequency of iterations, it represents the bit nodes are more reliable and can not be flipped arbitrarily. It should have a mechanism to judge if flipping multi-bits. When flipping multi-bits per iteration, we can find the performance of flipping multi-bits per iteration better than flipping one bit per iteration in the condition of less iterations. Flipping multi-bits per iteration can use less iterations to achieve the same performance. Therefore , it can save decoding time effectively and improve the speed of decoding.

關鍵字(中)

★ 錯誤更正碼

關鍵字(英)

★ LDPC
★ bit-flipping

論文目次

中文摘要.………………………………………………………………………..Ⅳ
Abstract…………………………………………………………………………..Ⅴ
目錄….…………………………………………………………………………..Ⅶ
圖目錄.......................................................................................................Ⅸ
表目錄.......................................................................................................XI
第一章前言............................................................................................ 1
1.1 研究內容與論文動機.................................................................. 1
1.2 論文組織.................................................................................... 1
第二章 LDPC Code .................................................................................. 2
2.1 LDPC 起源.................................................................................. 2
2.2 LDPC Code 之介紹...................................................................... 2
2.2.1 LDPC Code 之矩陣表示方法與定義................................... 2
2.2.2 Tanner graph....................................................................... 4
2.3 LDPC Code 之設計架構類型........................................................ 6
2.3.1 隨機構造方法................................................................... 6
2.3.1.1 規則性(Regular) LDPC Codes .................................. 6
Gallager 方法..................................................................... 6
Mackay-1A 方法................................................................. 7
2.3.1.2 不規則性(Irregular) LDPC Codes ............................. 7
Mackay-2A 方法................................................................. 7
2.3.2 代數構造方法................................................................... 8
2.4 LDPC Code 之編碼法................................................................. 11
第三章解碼演算法................................................................................ 13
3.1 Message Passing 演算法............................................................. 14
3.1.1 Sum-Product algorithm ..................................................... 15
3.1.2 Min-Sum algorithm........................................................... 22
3.1.3 Normalized BP-Based algorithm........................................ 23
3.1.4 Offset BP-Based algorithm................................................ 25
3.2 低複雜度解碼演算法................................................................ 25
3.2.1 Bit-Flipping(BF) algorithm................................................ 25
3.2.2 Weighted Bit-Flipping(WBF) algorithm.............................. 26
3.2.3 Modified Weighted Bit-Flipping(MWBF) algorithm............ 28
3.2.4 Improved Modified Weighted bit-Flipping algorithm........... 29
3.2.5 Liu-Pados (LP) Weighted Bit-Flipping algorithm ................ 29
3.2.6 Weighted-Sum Bit-Flipping algorithm................................ 32
3.2.7 Reliability Ratio(RR) Weighted Bit-Flipping algorithm....... 33
3.3 解碼演算法............................................................................... 35
3.3.1 動機................................................................................ 35
3.3.2 翻多個位元遭遇的問題................................................... 35
3.3.3 提出翻多個位元節點的機制........................................... 37
第四章模擬結果與分析........................................................................ 44
第五章結論…………………………………………………………………….56
參考文獻............................................................................................... .57

參考文獻

[1] Gallager, R.G.: “Low density parity check codes”, IRE Trans. Inf. Theory, pp. 21–28. 1962, 8
[2] R. M. Tanner, “A recursive approach to low complexity codes,”IEEE Trans. Inform. Theory, Vol. 27, pp. 533-547, Sept. 1981.
[3] 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.
[4] N. Wiberg, “Codes and Decoding on General Graphs,” Ph.D. thesis, Linkoping University, Sweden, 1996.
[5] D. J. C. MacKay, “Gallager codes that are better than turbo codes,” in Proc. 36th Allerton Conf . Comm., Control, and Computing, Sept. 1998.
[6] T. Richardson, A. Shokrollahi and R. Urbanke, “Design of capacityapproaching irregular codes,” IEEE Trans. Inform. Theory, Vol. 47, pp. 619-637, Feb. 2001.
[7] T. Richardson and R. Urbanke, “The capacity of low density parity check codes under message-passing decoding,” IEEE Trans. Inform.Theory, Vol. 47, pp. 599-618, Feb. 2001.
[8] S.-Y. Chung, G. D. Forney, T. 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, pp. 58-60, Feb. 2001.
[9] MacKay, D.J.C.: “Good error-correcting codes based on very sparse matrices”, IEEE Trans. Inf. Theory, 45, pp. 399–432, March 1999
[10] 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.
[11] John L. Fan ,“Constrained coding and soft iterative decoding” Kluwer Academic Publishers, 2001.
[12] 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. Comm., Vol. 47, pp. 673-680, May 1999.
[13] 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.
[14] 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.
[15] J. Zhang and M. P. C. Fossorier, “A Modified Weighted Bit-Flipping Decoding of Low-Density Parity-Check Codes,” IEEE Comm. Lett., Vol. 8, pp. 165-167, March 2004.
[16] M. Jiang, C. Zhao, Z.Shi, and Y. Chen, “An Improvement on theModified Weighted Bit Flipping Decoding algorithm for LDPC Codes,” IEEE Commun. , Vol. 9, No.9, pp.814-816, Sept. 2005.
[17] Liu, Z., and Pados, D.A.: ‘Low complexity decoding of finite geometry LDPC codes’, Communications, Vol.4,pp. 2713–2717,May 2003
[18] M. Shan, C.M. Zhao and M. Jiang ,” Improved weighted bit-flipping algorithm for decoding LDPC codes,” IEE Pro.- Commun. , Vol. 152, No. 6, pp. 919-922, December 2005
[19] F. Guo and L. Hanzo, “Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes,” IEEE Electron. Lett., Vol. 40, pp. 1356-1358, Oct. 2004.
[20] http://www.inference.phy.cam.ac.uk/mackay/codes/data.html

指導教授

賀嘉律(Chia-Lu Ho)

審核日期

2007-7-4

推文