臺灣博碩士論文加值系統

這篇論文主要工作是使用了由R.He等人在文章[1]中提到的新代數解碼方法，來得出一個針對二元平方剩餘碼QR(89,45,17)五個錯以內的解碼運算法。之前的代數解碼方式是應用了Sylvester豫解式的技巧來消解由牛頓等式得出的非線性多變數方程式組中變元的數量，因而解出那些變元的值。新方法乃是使用了矩陣-行列式的技巧來產生變數間的新關係式做為輔助式以增加方程式的數量，這是解出錯位多項式所需要的。
當錯誤的字元數在三以內的，還不需要這種新的方式，在這兒，新的解碼方式是用來解四個錯或五個錯的情形，在解碼的過程中我們是透過能執行符號運算的數學軟件Mathematica和Maple V 來解那些複雜的非線性多變數方程式組。
我們也將所得到的結果，以C++程式語言寫出一個能在個人電腦上執行的程式來進行編解碼的模擬及實現，也成功的測試了將一張圖像的傳送過程以二元平方剩餘碼來進行編碼，而當錯誤數量是在五個以內時，我們得到的方法能夠正確無誤地解碼。

The main purpose of this thesis is, by applying a new algebraic decoding method used by R. He et al [1] to develop an algorithm for decoding the binary (89, 45, 17) code up to five errors. The original algebraic decoding method is applying Sylvester resultant to reduce the unknowns and to solve the nonlinear multivariate equations in the Newton identities. The new method is to use a matrix-determinant technique to produce phantom-relations of unknowns as auxiliary equations. This will add the number of equations that are needed to solve the error-locator polynomial.
It is not necessary to use the new method for the first three errors. We apply the new method to treat the cases of four and five errors. With the help of the software Maple V and Mathematica we can solve complicated equations of multivariate.
Based on the result obtained above, a C++ program was developed and was run in an Intel’s P-III personal computer to implement the decoding algorithm. An image was checked successively through our decoding algorithm for the binary (89, 45, 17) QR code up to five errors.

CONTENTS
ACKNOWLEDGEMENTS………………………………...…………………I
ABSTRACT………………………………………………………………II
CONTENTS………………………………………………………………IV
LIST OF FIGURES………………………………………………………VI
LIST OF TABLES………………………………………………………VII
CHAPTER 1 INTRODUCTION
1.1 The Motivation………………………………………………1
1.2 The Proposed Methods and Contributions………………2
1.3 Organization of the Dissertation………………………3
CHAPTER 2 MATHEMATICAL BACKGROUND
2.1 Basic of Algebra……………………………………………4
2.2 Polynomials Preliminaries………………………………7
2.3 Cyclic Codes………………………………………………10
CHAPTER 3 THE QUADRATIC RESIDUE CODE
3.1 Encoder………………………………………………………12
3.1.1 Quadratic Residue and Cyclotomic Coset…………12
3.1.2 the Generator Polynomial……………………………14
3.1.3 Process of the Encoder………………………………14
3.2 Decoder……………………………………………………16
3.2.1 Syndrome Evaluation…………………………………17
3.2.2 the Error-Locator Polynomial……………………18
3.2.3 the Newton Identities………………………………19
3.2.4 Chien Search…………………………………………20
3.2.5 Decode Algorithm……………………………………20
3.3 Known Result……………………………………………21
CHAPTER 4 DECODING METHODS
4.1 The Sylvester Resultant……………………………25
4.2 Nonrecurrent Syndrome Dependence Relations……29
CHAPTER 5 DECODING THE (89, 45, 17) QR CODE UP TO FIVE ERRORS
5.1 Decoding up to Three Errors………………………32
5.2 Decoding 4 Errors……………………………………36
5.3 Decoding 5 Errors……………………………………41
CHAPTER 6 CONCLUSIONS
6.1 Conclusions……………………………………………46
6.2Recommendations for Further Research……………47
APPENDIX A
The flowcharts of the algorithm for decoding the (89, 45, 17) QR code………………………………………………………49
APPENDIX B
The equations of necessary condition of decoding 4 and 5 errors for the (89, 45, 17) QR code…………………………52
BIBLIOGRAPHY………………………………………………55

[1]R. He, I. S. Reed, T. K. Truong and X. Chen, “Decoding the (47,24,11) Quadratic Residue Code”, NSF Grant NCR-9314347, 2000.
[2]M. Elia, “Algebraic Decoding of the (23,12,7) Golay Code”, IEEE Trans. on Inform. Theory, IT-33, No.1, pp.150-151, Jan. 1987.
[3]I. S. Reed, X. Yin, T. K. Truong, “Algebraic Decoding of the (32,16,8) Quadratic Residue Code”, IEEE Trans. on Inform. Theory, IT-36, No.3, July 1990.
[4]I. S. Reed, T. K. Truong, X. Chen and X. Yin, “Algebraic Decoding of the (41,21,9) Quadratic Residue Code”, IEEE Trans. on Inform. Theory, IT-38, No.3, May 1992.
[5]X. Chen, I. S. Reed, and T. K. Truong, “Decoding the (73,37,13) QR codes of Length n = 8m + 1”, Submitted to IEEE Trans. on Inform. Theory, 1992.
[6]E. R. Berlekamp, H. Rumsey, and G. Solomon, “On the Solution of Algebraic Equation over Finite Fields”, Information and Control 10, pp.553-564, 1967.
[7]E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, Inc., 1968.
[8]F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North Holland, 1977.
[9]K. O. Geddes, S. R. Czapor and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992.
[10]X. Chen, Binary Quadratic Residue Codes For Random Error Correction, University of Southern California Ph.D. Thesis, May 1993.
[11]X. Yin, Decoding The Binary Quadratic Residue Codes, University of Southern California Ph.D. Thesis, November 1993.
[12]P. Bours, J. C. M. Janssen, M. van Asperdt and H. C. A. van Tilborg, “Algebraic Decoding Beyond eBCH of Some Binary Cyclic Codes, When e > eBCH”, IEEE Trans. on Inform. Theory, vol. IT-36, No.1, pp214-222, Jan. 1990.
[13]X. Chen, I. S. Reed, and T. K. Truong, “A Performance Comparison of the Binary QR codes with the -Rate Convolutional Codes”, Submitted to IEEE Trans. on Inform. Theory, 1992.
[14]X. Chen, I. S. Reed, and T. K. Truong, “No Binary Quadratic Residue Code of Length 8m-1 is quasi-perfect”, Accepted for publishing in IEEE Trans. on Inform. Theory. No.2 March 1994.
[15]X. Chen, I. S. Reed, and T. K. Truong, “On Certain Subcodes of the Binary Self-Daul Codes”, Submitted to IEEE Trans. on Inform. Theory. 1992.
[16]X. Chen, I. S. Reed, and T. K. Truong, “On of a Grobner Basis to Algebraically Decode a Binary Cyclic Codes”, Submitted to IEEE Trans. on Inform. Theory, 1992.
[17]K. Imamura, “A Method for Computing Addition Tables on GF( )”, IEEE Trans. on Inform. Theory, IT-26, No.3, pp.367-369, May 1980.
[18]W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes. 2nd ed., The MIT Press, Cambridge, 1972.
[19]L. R. Vermani, Elements of Algebraic Coding Theory, Kurukshetra University, India., 1996.
[20]J. Z. Lin, A Study on the Quadratic Residue Code (89,45,17), Thesis, May 1999.
[21]G. L. Feng, K. K. Tzeng, “A new procedure for decoding Cyclic and BCH Codes up to Actual Minimum Distance”, IEEE Trans., 1994, IT-40(5), pp. 1364-1374.
[22]Iwan M. Duursma, Ralf Kotter, “Error-Locating Pairs for Cyclic Codes”, IEEE Trans., 1994, IT-40, pp. 1108-1121.