Title page for 93523025


[Back to Results | New Search]

Student Number 93523025
Author Hsu-Hung Yang(楊旭弘)
Author's Email Address No Public.
Statistics This thesis had been viewed 1224 times. Download 5 times.
Department Communication Engineering
Year 2005
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title On the Hybrid Decoding Method for LDPC Code by Using the Message Passing and the A* Algorithms
Date of Defense 2006-06-30
Page Count 50
Keyword
  • A* algorithm
  • LDPC Code
  • message passing algorithm
  • Abstract 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.
    Table of Content 中文摘要IV
    AbstractV
    目錄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
    Reference [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.
    Advisor
  • Chia-Lu Ho(賀嘉律)
  • Files
  • 93523025.pdf
  • disapprove authorization
    Date of Submission 2006-07-12

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.