臺灣博碩士論文加值系統

習知利用代數解碼法及步階式解碼法所設計之解碼器，因分別具有硬體複雜度高及解碼耗時之缺點，故無法對循環碼進行高效率解碼，而為了改善習知缺失，本論文係提出一種改良型步階式解碼演算法，其主要是針對BCH碼的改錯電路及其演算法進行改良設計；在功效上改良式步階解碼法在錯誤量較少 的情形下，其解碼過程中所耗費的時間，較代數解碼法與傳統步階式解碼法為少。
本論文係改良傳統步階式解碼演算法，利用組合電路設計並進行餘式、徵狀、徵狀矩陣及行列式值之計算。而驗證上，係將設計完成之BCH解碼器的VHDL程式碼下載至FPGA實驗板，並自電腦端以RS232介面傳送訊息資料至FPGA端進行計算，待FPGA端計算完成後，回傳計算結果至電腦端，再以超級終端機檢視其更正結果。
本論文所得之結果，在解碼速度上，比傳統步階式解碼法快，且硬體複雜度近似傳統步階式解碼法，本論文所改良的步階式解碼演算法係可有效改善代數解碼法之硬體複雜度過高及傳統步階式解碼法解碼耗費之問題。

In general, an algebraic decoder is with high hardware complexity or a conventional step-by-step decoder is with long decoding delay, and both of them are not efficient for a cyclic code in terms of decoding complexity. In order to overcome this difficulty, a modified step-by-step decoding is proposed in this thesis, which increases the decoding speed of conventional step-by-step decoding. Comparing to algebraic decoding, it reduces hardware complexity. Especially, as the error correcting capability is no more than 3, modified step-by-step decoding needs less decoding delay than algebraic decoding and conventional step-by-step decoding do.
In this thesis, a design of remainder circuits, syndromes, the syndrome-matrix determinant is implemented to detect and correct errors. In verification of the designed implementation, the VHDL code of the proposed decoding algorithm for a BCH code are first downloaded to a FPGA board, and data are transmitted from a computer via an RS232 interface. After a solution is ready on the FPGA board, and then transmitted back to the computer and check whether it is correct.
In the results, the modified step-by-step algorithm holds better decoding speed and little more hardware complexity in comparison with the conventional step-by-step algorithm and can improve the drawbacks of the algebraic algorithm for BCH codes.

第一章　緒論
1.1資料傳輸與儲存系統．．．．．．．．．．．．．．1
1.2 錯誤更正．．．．．．．．．．．．．．．．．．2
1.3 研究動機．．．．．．．．．．．．．．．．．．3
1.4 論文組織．．．．．．．．．．．．．．．．．．4
第二章　線性區塊碼
2.1線性區塊碼．．．．．．．．．．．．．．．．．．5
2.1.1生成矩陣．．．．．．．．．．．．．．．．6
2.1.2 線性系統區塊碼．．．．．．．．．．．．．7
2.1.3 同位檢測矩陣．．．．．．．．．．．．．．9
2.2 徵狀與錯誤檢測．．．．．．．．．．．．．．11
2.2.1 徵狀．．．．．．．．．．．．．．．．．．12
2.2.2 錯誤檢測．．．．．．．．．．．．．．．．13
2.3 漢明碼．．．．．．．．．．．．．．．．．．．14
2.4 循環碼．．．．．．．．．．．．．．．．．．．14
2.4.1 循環碼之編碼．．．．．．．．．．．．．．16
2.4.2 徵狀值計算．．．．．．．．．．．．．．18
第三章　二位元BCH碼之編解碼
3.1 BCH碼簡介．．．．．．．．．．．．．．．．20
3.2 BCH碼解碼．．．．．．．．．．．．．．．．22
3.2.1 徵狀值計算．．．．．．．．．．．．．．．22
3.2.2 錯誤樣本的定義．．．．．．．．．．．．．23
3.2.3 錯誤位置多項式．．．．．．．．．．．．．25
3.3 BCH碼之解碼方式．．．．．．．．．．．．．26
3.3.1 Peterson-Gorenstein-Zierler Algorithm．．．．27
3.3.2 Berlekamp-Massey Algorithm．．．．．．．．32
3.3.3 Euclidean Algorithm．．．．．．．．．．．．37
3.4 Galois Field的硬體實現．．．．．．．．．．44
第四章　改良式步階解碼法
4.1 步階式解碼法．．．．．．．．．．．．．．．．51
4.2 改良式步階解碼法．．．．．．．．．．．．．．52
4.2.1 餘式電路．．．．．．．．．．．．．．．．55
4.2.2 徵狀值計算．．．．．．．．．．．．．．．58
4.2.3 徵狀矩陣計算與比較．．．．．．．．．．．60
4.2.4 步階式解碼法演算流程．．．．．．．．．．65
4.3 權重檢測．．．．．．．．．．．．．．．．．．66
4.4 演算法比較．．．．．．．．．．．．．．．．．69
第五章　硬體電路之模擬結果與硬體驗證
5.1設計流程．．．．．．．．．．．．．．．．．．78
5.2模擬測試．．．．．．．．．．．．．．．．．．80
5.3硬體驗證．．．．．．．．．．．．．．．．．．86
第六章　結論與討論．．．．．．．．．．．．．．．．．．．91
參考文獻．．．．．．．．．．．．．．．．．．．．．．．．93

[1] S. Lin and D. J. Costello, Jr, Error Control Codin, Prentice Hall, 2004.
[2] J. Massey, “Step-by-step decoding of the Bose-Chaudhuri- Hocquenghem codes,” IEEE Transactions on Information Theory, Vol. 11, No. 4, pp. 580-585, Oct 1965.
[3] Z. Szwaja “On step-by-step decoding of the BCH binary codes,” IEEE Transactions on Information Theory, Vol.13, No.2, pp.350-351, Apr. 1967.
[4] S.W. Wei, and C.-H.Wei, “A high-speed real-time binary BCH decoder,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 3, No. 2 , pp.138-147,April 1993.
[5] C. L. Chr , Szu-Lin. Su and Shao-Wei. Wu, “New step-by-step decoding for binary BCH codes,” The Ninth International Conference on Communications Systems, 2004. ICCS 2004. pp. 456-460, Sept. 2004.
[6] S. W. Wei, and C.H. U’ei , “High speed hardware decoder for double-error correcting binary BCH codes”. IEE Proceedings, vol. 136. Pt. I, no. 3, June 1989.
[7] S. A. Abbasi, “FPGA based realization of a reduced complexity high speed decoder for error correction,” ICECS 2003. Proceedings of the 2003 10th IEEE International Conference on Electronics, Circuits and Systems, 2003,Vol. 3, pp.1002-1005, Dec. 2003.
[8] E. -H. Lu and T. Chang,” New decoder for double-error-correcting binary BCH codes,” IEE Proceedings Communications,Vol. 143, Issue 3, pp.129-132, June 1996.
[9] Kraft. C,” Closed solution of Berlekamp's algorithm for fast decoding of BCH codes,” IEEE Transactions on Communications,
Vol. 39, Issue 12, pp.1721-1725, Dec. 1991.
[10] G. -L. Feng and K. K. Tzeng,” A generalized Euclidean algorithm for multisequence shift-register synthesis,” IEEE Transactions on Information Theory,Vol. 35, Issue 3, pp.584-594, May 1989.
[11] M. -H. Cheng,” Generalised Berlekamp-Massey algorithm,” IEE Proceedings Communications,Vol. 149, Issue 4, pp.207-210,Aug. 2002.
[12] M. Srinivasan and D. V. Sarwate,” Malfunction in the Peterson-Gorenstein-Zierler decoder,” IEEE Transactions on Information Theory, Vol. 40, Issue 5, pp.1649-1653, Sept. 1994.
[13] W.M.EI-Medany , C.G.Warrison , P. G. Farrell.and C. J. Mardf,” VHDL implmentation of a BCH minimum weight decoder for double error,” Radio Science Conference, 2001. NRSC 2001. Proceedings of the Eighteenth National,Vol. 2, pp.27-29, March 2001.
[14] Lijun Zhang , Victor O. K. Li and Zhigang Cao” Short BCH codes for wireless multimedia data,” Wireless Communications and Networking Conference, 2002. WCNC2002. 2002 IEEE,Vol. 1, pp.220-222,March 2002.
[15] W. W. Peterson,” Encoding and error-correction procedures for the Bose-Chaudhuri codes,” IEEE Transactions on Information Theory,Vol. 6, Issue 4, pp.459-470,Sep 1960.
[16] R. T. Chien,” Cyclic decoding procedures for Bose- Chaudhuri-Hocquenghem codes,” IEEE Transactions on Information Theory,Vol. 10, Issue 4, pp.357-363,Oct 1964.
[17] D. J. Jr. Costello , J. Hagenauer , H. Imai and S. B. Wicker, “Applications of error-control coding,” IEEE Transactions on Information Theory, Vol. 44 , No. 6, pp.2531-2560, Oct. 1998.
[18] G. JR. Forney, “Generalized Minimum Distance Decoding,” IEEE Trans. Inform. Theory, Vol .IT-12, No 2. pp.125-131, Sept. 1966.
[19] H. Helgert , R. Stinaff, “Shortened BCH codes,” IEEE Transactions on Information Theory, Vol. 19, No.6, pp. 818-820, Nov 1973.