臺灣博碩士論文加值系統

本論文提出降低Chase-2 decoding演算法複雜度之Low-Complexity Chase-2 decoding (LCC)方法。Chase提出了Chase-2 decoding的演算法以降低軟式解碼 (soft-decision) 在線性區塊碼 (linear block codes) 上的複雜度，Chase-2 decoding是在硬式解碼 (hard-decision decoding) 的基礎上，利用不可靠的位置 (Least Reliable Positions, LRPs) 增加解碼候選碼以提升改錯效能，但是相對當不可靠的位置取的數量增加時，複雜度則會隨著不可靠的位置的數量呈指數成長。因此本論文提出了利用線性區塊碼中，每個codeword之間最小漢明距離(Minimum Hamming Distance) 的特性來有效減少Chase-2 decoding的解碼複雜度，並且效能與原始的 Chase-2 decoding完全相同。

This paper proposes a Low-Complexity Chase-2 (LCC) decoding for linear block codes. Chase proposed Chase-2 decoding algorithm to reduced decoding complexity of soft-decision decoding for linear block codes. Base on hard-decision decoding, Chase-2 decoding can provide a candidate list by performing bit-flipping on the bits of Least Reliable Positions (LRPs). However, the numbers of LRPs increase and the complexity is in an exponential growth. For the reason that this paper proposed a Low-Complexity Chase-2 decoding which can be apply in linear block codes and it use the feature that there is a minimum hamming distance between each codeword. At last, the Low-Complexity Chase-2 decoding we proposed can reduce the decoding complexity of Chase-2 decoding significantly and the decoding performance is exactly the same as Chase-2 decoding.

指導教授推薦書
口試委員會審定書
誌謝...iii
摘要...iv
Abstract...v
第一章 緒論...1
1. 1 研究背景...1
1. 2 研究目的...1
1. 3 結果概述...2
1. 4 論文架構...2
第二章 理論基礎...3
2. 1 BCH Codes...3
2. 1. 1 BCH Codes編碼...3
2. 1. 2 BCH Codes解碼...6
2. 2 RS Codes...12
2. 2. 1 RS Codes編碼...12
2. 2. 2 RS Codes解碼...15
2. 2. 3 錯誤的位置error location...15
2. 2. 4 錯誤的值error value...19
2. 3 Chase Decoding...20
2. 3. 1 不可靠的位置...21
2. 3. 2 Chase-2 Decoding解碼方式...22
2. 4 Block Code Modulation with Chase-2 Decoding...24
2. 4. 1 Block Code Modulation距離概念...24
2. 4. 2 Multilevel Block Modulation Codes...26
2. 4. 3 Multilevel Block Modulation Codes解碼...29
2. 4. 4 3-Level BCH Codes with Chase-2 Decoding...32
第三章 提出方法...37
3.1 Codewords之間的距離概念...37
3.2 Low Complexity Chase-2 Decoding...38
第四章 模擬結果...45
4. 1 BCH Codes with Low-Complexity Chase-2 decoding...45
4. 2 RS Codes with Low-Complexity Chase-2 decoding...54
4. 3 與Fast Chase2比較...59
第五章 結論...63
參考文獻...64

圖目錄
圖2-1 (n, k) systematic form BCH Codes編碼器...5
圖2-2 (n, k) systematic form RS Codes編碼器...14
圖2-3 Multilevel Block Modulation Codes星座點分層圖...27
圖2-4 3-level BCM code編碼器...28
圖2-5 Multilevel第一層解碼...30
圖2-6 Multilevel第二層解碼...31
圖2-7 Multilevel第三層解碼...31
圖2-8 3-level BCM code 編碼器(2)...32
圖2-9 3-level BCH Code解碼效能...35
圖2-10 3-level BCH Code搭配Chase-2 decoding解碼效能...36
圖3-1 BCH及RS Codes最小漢明距離 dmin 示意圖...38
圖3-2 Chase-2 decoding幾何示意圖...39
圖3-3 Chase-2 decoding解碼流程圖...40
圖3-4 低複雜度Chase-2 decoding解碼流程圖...41
圖3-5 低複雜度Chase-2 decoding幾何示意圖-1...42
圖3-6 低複雜度Chase-2 decoding幾何示意圖-2...43
圖3-7 低複雜度Chase-2 decoding幾何示意圖-3...44
圖4-1 BCH (15, 7) 低複雜度Chase-2 decoding解碼效能...47
圖4-2 BCH (31, 21) 低複雜度Chase-2 decoding解碼效能...48
圖4-3 BCH (31, 16) 低複雜度Chase-2 decoding解碼效能...49
圖4-4 BCH (63, 39) 低複雜度Chase-2 decoding解碼效能...50
圖4-5 BCH (63, 36) 低複雜度Chase-2 decoding解碼效能...51
圖4-6 BCH (63, 24) 低複雜度Chase-2 decoding解碼效能...52
圖4-7 BCH Codes之 p 與解碼次數比較圖...53
圖4-8 RS (15, 11) 低複雜度Chase-2 decoding解碼效能...56
圖4-9 RS (31, 27) 低複雜度Chase-2 decoding解碼效能...57
圖4-10 RS Codes之 p 與解碼次數比較圖...58
圖4-11 RS(15, 9) 低複雜度Chase-2與Fast Chase-2效能比較...60
圖4-12 RS (15, 9) Fast Chase-2搭配低複雜度Chase-2解碼效能...61
圖4-13 RS (31, 25) Fast Chase-2搭配低複雜度Chase-2解碼效能...62

表目錄
表4-1 BCH (15, 7) 低複雜度Chase-2 decoding解碼次數...47
表4-2 BCH (31, 21) 低複雜度Chase-2 decoding解碼次數...48
表4-3 BCH (31, 16) 低複雜度Chase-2 decoding解碼次數...49
表4-4 BCH (63, 39) 低複雜度Chase-2 decoding解碼次數...50
表4-5 BCH (63, 36) 低複雜度Chase-2 decoding解碼次數...51
表4-6 BCH (63, 24) 低複雜度Chase-2 decoding解碼次數...52
表4-7 RS (15, 11) 低複雜度Chase-2 decoding解碼次數...56
表4-8 RS (31, 27) 低複雜度Chase-2 decoding解碼次數...57
表4-9 RS (15, 9) 低複雜度Chase-2 decoding解碼次數...60
表4-10 RS (15, 9) Fast Chase-2搭配低複雜度Chase-2解碼次數...61
表4-11 RS (31, 25) Fast Chase-2搭配低複雜度Chase-2解碼次數...62

[1]R. C. Bose and D. K. Ray-Chaudhuri, “On a class of Error Correcting Binary Group Codes,” Inform. Control, 3: 68-79, March 1960.
[2]A. Hocquenghem, “Codes corecteurs d’erreurs,” Chiffres, 2:147-56, 1959.
[3]I. S. Reed and G. Solomon, “Polynomial Codes over Certain Fields,” J. Soc. Ind. Appl. Math., 8: 300-304, June 1960.
[4]D. Chase, “A Class of Algorithms for Decoding Block Codes with Channel Measurement Information,” IEEE Trans. Inform. Theory, IT-18: 170-82, January 1972.
[5]H. Imai and S. Hirakawa, “A New Multilevel Coding Method Using Error-Correcting Codes,” IEEE Trans. Inform. Theory, 23 (3): 371-76, May 1977.
[6]Blahut, R. E., Theory and Practice of Error Control Codes (Reading, MA: Addison-Wesley, 1983).
[7]D. Gorenstein and N. Zierler, “A class of Cyclic Linear Error-Correcting Codes in p^m Symbols,” J. Soc. Ind. Appl. Math., 9: 107-214, June 1961.
[8]G. D. Forney, Jr., “Generalized Minimum Distance Decoding,” IEEE Trans. Inform. Theory, IT-12: 125-31, April 1966.
[9]I. Land, P. A. Hoeher, and U. Sorger, “Log-likelihood values and Monte Carlo simulation: some fundamental results,” in Proc. Int. Symp. On Turbo Codes and Related Topics, Brest, France, September 2000.

[10]Jianing Su; Zhenghao Lu; Xiaopeng Yu; Changhui Hu, “A Novel Low Complexity Soft-decision Demapper for QPSK 8-PSK Demodulation of DVB-S2 system,” International Conference of Electron Devices and Solid-State Circuits (EDSSC’11), pp. 17-18 Tianjin (China, Nov. 2011.).
[11]T. Kasami, T. Takata, T. Fujiwara, and S. Lin, “On Linear Structure and Phase Rotation Invariant Properties of Block 2^l-PSK Modulation Codes,” IEEE Trans. Inform. Theory, 37(1): 164-67, January 1991.
[12]J. Wu and S. Lin. “Multilevel Trellis MPSK Modulation Codes for the Rayleigh Fading Channels,” IEEE Trans. Commun., 41 (9): 1311-18, September 1993.
[13]Xingru Peng, Wei Zhang, Wenjie Ji, Zhibin Liang, and Yanyan Liu, “Reduced-Complexity Multiplicity Assignment Algorithm and Architecture for Low-Complexity Chase Decoder of Reed-Solomon Codes,” IEEE Communications Letters, vol. 19, no. 11, November 2015.
[14]Heng Tang, Student Member, IEEE, Ye Liu, Member, IEEE, Marc Fossorier, Member, IEEE, and Shu Lin, Fellow, IEEE, “On Combining Chase-2 and GMD Decoding Algorithms for Nonbinary Block Codes,” IEEE Communications Letters, vol. 5, no. 5, May 2001.
[15]Yung-Kuei Lu, Shen-Ming Chung, and Ming-Der Shieh, “Low-complexity Architecture for Chase Soft-decision Reed-Solomon Decoding,” IEEE, 2014.
[16]G. T. Chen, L. Cao, L. Yu and C. W. Chen, “Test-Pattern-Reduced Decoding for Turbo Product Codes with Multi-Error-Correcting eBCH Codes,” IEEE Trans. Commun., vol. 57, no. 2, pp. 307-310, Feb. 2009.
[17]S. A. Hirst, B. Honary and G. Markarian, “Fast Chase algorithm with an application in turbo decoding,” IEEE Trans. Commun., vol. 49, no. 10, pp. 1693-1699, 2011.
[18]Shao-I Chu, Yan-Haw Chen, Yi-Chan Chiu and Ru-Sian Chang, “Fast Chase Algorithms for Decoding Reed-Solomon Codes,” IEEE Trans. Commun., 2014