臺灣博碩士論文加值系統

本篇論文提出用於二進位線性區塊碼上的一種快速軟式決策解碼法。有別於其他以基於訊號雜訊比以及導出的式子當做解碼停止的標準，此篇論文所提出來的演算法乃基於錯誤權重，利用將最不可靠的位元做一個高低準位的轉相，來造成解碼改錯能力的提升，改善了Chase演算法必須要測試大量的可能組合。本文所提出的演算法只要做一些運算量較低的處理程序，使得解碼複雜度明顯地減少，並且在區塊錯誤率為10-5時與最大可能解碼法相比只犧牲大約0.1到0.5個分貝的編碼增益，些許的犧牲掉編碼增益，進而達到大幅降低演算法的解碼複雜度為此論文提出的最主要的目的。
根據測試樣本，相較於Chase演算法所要測試dmin-1個位置的大量可能組合造成解碼複雜度的增加，此篇論文所提出的演算法相較於Chase演算法能達到平均解碼複雜度被減少為 20%的能力。

A new fast soft-decision decoding algorithm for binary linear block codes is proposed in this thesis. Different than other algorithms using the threshold base on the signal-to-noise ratio to stop the decoding process, the proposed algorithm utilizes the flip of the least reliable bit according to the error weights to reduce the computational complexity. This reduces the computational complexity compared to the Chase algorithm which needs to test large amount of error patterns.
The purpose of the thesis is to present a new approach to reduce a significant amount of decoding complexity by sacrificing less coding gain.
Furthermore, in terms of test patterns, decoding complexity is reduced to 20% on average, compared to that of Chase algorithm with dmin-1 tested positions. At the block-error rate=10-5, the coding gain just reduced at the expense of about 0.1dB to 0.5dB.

指導教授推薦書...........................................I
口試委員會審定書.........................................II
授權書...................................................III
誌謝.....................................................IV
中文摘要.................................................V
英文摘要.................................................VI
第一章 簡介...............................................1
1.1 研究背景.........................................4
1.2 研究目的.........................................5
1.3 論文架構.........................................6
第二章 Chase演算法........................................7
2.1 代數解碼法簡介...................................7
2.2 Chase 演算法簡介.................................9
2.3 延伸式Chase演算法..............................12
2.3.1 Chase-1演算法..............................12
2.3.2 Chase-2演算法..............................12

第三章 基於錯誤權重之快速軟式決策解碼法..................13
3.1 Tanaka 基於訊雜比之演算法.......................14
3.2 Kaneko 基於停止準則之演算法.....................16
3.3 Hackett 基於錯誤權重奇偶之演算法................19
3.4 基於錯誤權重之演算法............................21
3.5 基於錯誤權重之快速軟式決策解碼法................24
第四章 模擬結果..........................................36
4.1 (23,12,7) Golay碼模擬結果.......................36
4.2 (15,7,5) BCH碼模擬結果..........................38
第五章 結論與未來展望....................................40
5.1 結論............................................40
5.2 未來展望........................................41
參考文獻...............................................42

[1] D. Chase, “A Class of Algorithms for Decoding Block Codes With Channel Measurement Information”, IEEE Trans. Inf. Theory, Vol. IT-18, No. 1, pp. 170-182, January 1972.
[2] S.A. Hirst, B. Honary, and G. Markarian, “Fast Chase algorithm with an application in turbo decoding,” IEEE transactions on Communication, Vol. 49, pp.1639-1699, October 2001.
[3] Martin Bossert, “Channel Coding for Telecommunications,” pp.117-199, JOHN WILLEY & SONS, LTD, 1999.
[4] C.M. Hackett, “An Efficient Algorithm for Soft –Decision Decoding of the (24, 12) Extended Golay Code “, IEEE Trans. Communications, Vol. COM-29, No. 6, pp. 909-911, June 1981.
[5] E.H. Lu, H.P. Wu, Y.C. Cheng, and P.C. Lu, “Fast algorithms for decoding the (23, 12) binary Golay code with four-error-correcting capability”, International Journal of Systems Science, Vol. 26, No. 4, pp. 937-945, 1995.
[6] H. Tanaka and K. Kakigahara, “Simplified correlation decoding by selecting possible codewords using erasure information”, IEEE Trans. Inf. Theory, Vol. IT-29, No. 5, pp. 743-748, September 1983.
[7] T. Kaneko, T. Nishijima, H. Inazumi, and S. Hirasawa, “An Efficient Maximum Likelihood-Decoding Algorithm for Linear Block Codes with Algebraic Decoder”, IEEE Trans. Inf. Theory, Vol. 40, No. 2, pp. 320-327, March 1994.
[8] A. Mahran and M. Benaissa, “Adaptive Chase algorithm for block turbo codes”, Electronics Letters, Vol. 39, No. 7, pp. 617-619, April 2003.
[9] S. Dave, J. Kim and S.C. Kwatra, “Turbo Block Codes using Modified Kaneko’s Algorithm.” MILCOM 2000. 21st Century Military Communications Conference Proceedings , Volume: 1 , pp.22-25 October 2000.
[10] D.J. Taipale and M.B. Pursley, “An Improvement to Generalized Minimum Distance Decoding,” IEEE Transactions on Information Theory, Vol. 37, No.1, pp. 167-172, January 1991.
[11] G. Einarsson and C.E. Sundberg, “A Note on Soft Decision Decoding with Successive Erasures”, IEEE Transactions on Information Theory, pp. 88-96, January 1976.
[12] G.D. Forney and Jr., “Generalized Minimum Distance Decoding”, IEEE Transactions on Information Theory, Vol. IT-12, No.2, pp. 125-131, April 1996.
[13] D.J. Taipale and M.B. Pursley, “New Results on Soft-Decision Decoding of Block Codes”, MILCOM.1989. IEEE Military Communications Conference, Vol. 2, pp. 546-550, October 1989.
[14] S.W. Wei and C.H. Wei, “On High-Speed Decoding of the (23, 12, 7) Golay Code”, IEEE Transactions on Information Theory, Vol. 36, No.3, pp. 692-695, May 1990.
[15] M. Elia, “Algebraic Decoding of (23, 12, 7) Golay Code”, IEEE Transactions on Information Theory, Vol. IT-33, No.1, pp. 150-151, January 1987.
[16] George C. Clark, Jr. and J. Bibb Chen, “Error-Correction Coding for Digital Communications,” pp141-180, Plenum Press, New York, 1981.

[17] Simon Haykin, “Communication System”, 4th edition, JOHN WILEY & SONS, LTD, 2000.
[18] John G. Proakis, “Digital Communications”, fourth edition, McGraw-Hill Higher Education, 2000.