臺灣博碩士論文加值系統

本論文研究主題是二元平方剩餘碼的相關研究，有兩個主要方向，首先在代數解碼方面，本論文提出二種新式代數解碼方法，分別是使用無反根Berlekamp-Massey演算法和症狀子多項式(Syndrome polynomial)來完成二元平方剩餘碼之解碼。該解碼方法不但比已知的解碼方法更容易實現而且適用於許多二元平方剩餘碼解碼，特別是之前未被成功解碼的(71, 36, 11)，(79, 40, 15)和(97, 49, 15)三個二元平方剩餘碼，它們都可以由這個新式代數解碼方法成功解碼。

在權重分布方面，本論文發現二元平方剩餘碼之權重分布有規則性，進而得出兩個權重的數學公式，使得所有二元平方剩餘碼權重分布之計算量縮減為八分之一。並且利用一個有效率的權重演算法計算出至今尚未被發表的二元平方剩餘碼(73, 37, 13)，(89, 45, 17)和(97, 49, 15)的權重分布。

Binary quadratic residue codes are among the most powerful known block codes. This dissertation is focused on the topics of algebraic decoding and weight distributions of binary quadratic residue codes. Two new algebraic decoding schemes for binary quadratic residue codes are proposed. The key ideals behind the decoding techniques are the utilization of the inverse-free Berlekamp-Massey algorithm and syndrome polynomial. The new decoding schemes are not only easier to implement than the previous ones, but also able to serve as a useful decoding for many other binary quadratic residue codes. In particular, the decoders of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes, which have not been decoded before, are developed here.

On the other hand, the weight distributions of a binary quadratic residue code C can be computed from the weight distribution of a subset of C that contains one-eighth of the codewords in C. An algorithm to determine the weight distributions of binary cyclic codes is given. As a consequence, the unpublished weight distributions of (73, 37, 13), (89, 45, 17), and (97, 49, 15) quadratic residue codes are determined precisely.

Acknowledgments ii
Abstract (Chinese) iii
Abstract (English) iv
List of Figures vii
List of Tables x
1 Introduction 1
1.1 Historical Background and Motivation 1
1.2 Framework 3
2 Mathematical Background 4
2.1 Galois Fields 4
2.2 Polynomials Over Galois Fields 5
2.3 Cyclic Codes and Quadratic Residue Codes 7
3 Algebraic Decoding Methods 9
3.1 Preliminaries 9
3.1.1 Syndromes and Error-Locator Polynomials 9
3.1.2 Inverse-Free Berlekamp-Massey Algorithm 13
3.1.3 Syndrome Polynomials 14
3.2 Unknown Syndromes 14
3.2.1 Determination of Unknown Syndromes 15
3.2.2 Unknown Syndrome of (71, 36, 11) Quadratic Residue Code 17
3.2.3 Unknown Syndrome of (79, 40, 15) Quadratic Residue Code 20
3.2.4 Unknown Syndrome of (97, 49, 15) Quadratic Residue Code 25
3.3 Decoding Method Using Inverse-Free Berlekamp-Massey Algorithm 29
3.3.1 Algebraic Decoding Algorithm 29
3.3.2 (71, 36, 11), (79, 40, 15), and (97, 49, 15) Quadratic Residue Decoders 30
3.4 Decoding Method Using Syndrome Polynomials 33
3.4.1 Decoding Algorithm 34
3.4.2 An Example of Decoding (41, 21, 9) Quadratic Residue Code 37
4 Weight Distributions of Binary Quadratic Residue Codes 40
4.1 Preliminaries 40
4.1.1 Weight Distributions 40
4.1.2 t-Designs 40
4.1.3 Projective special linear group 42
4.1.4 Partition of Information Sets 43
4.2 Weight Counting Algorithms 46
4.3 Results of Weight Distributions 48
4.3.1 Divide Information Sets into Two Subsets 48
4.3.2 Divide Information Sets into Four Subsets 50
4.3.3 Divide Information Sets into Eight Subsets 52
4.4 Weight Distributions of (73, 37, 13), (89, 45, 17), and (97, 49, 15) Quadratic Residue Codes 56
5 Conclusions 59
5.1 Contributions 59
5.2 Future Work 60
Appendix A Binary Quadratic Residue Codes and t-Designs 61
Appendix B The Detailed Weight Distributions 77
Bibliography 105

[1] F. J. MacWilliams and N. J. A. Sloan, The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1977.
[2] V. Pless, Introduction to the theory of error-correcting codes. 3rd ed. New York: Wiley, 1998.
[3] W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes. 2nd ed., MIT Press, 1972.
[4] E. Prange, “Some cyclic error-correcting codes with simple decoding algorithms,” Air Force Cambridge Research Center-TN-58-156, Cambridge, MA: 1958.
[5] R. W. Hamming, “Error detecting and error correcting codes,” Bell System Technical Journal, vol. 29, pp. 147-160, 1950.
[6] M. J. E. Golay, “ Notes on digital coding,” Proc. IRE, vol. 37, p.67, 1949.
[7] I. S. Reed, X. Yin, T. K. Truong, and J. K. Holmes, “Decoding the (24, 12, 8) Golay code,” Proc. IEE, vol. 137, pp. 202-206, May 1990.
[8] M. Elia, “Algebraic decoding of the (23, 12, 7) Golay code,” IEEE Trans. Inform. Theory, vol. 33, pp. 150-151, Jan. 1987.
[9] I. S. Reed, X. Yin, and T. K. Truong, “Algebraic decoding of the (32, 16, 8) quadratic residue code,” IEEE Trans. Inform. Theory, vol. 36, pp. 876-880, Jul. 1990.
[10] I. S. Reed and X. Chen, Error-control coding for data networks. Kluwer Academic publishers, Boston, 1999.
[11] I. S. Reed, T. K. Truong, X. Chen, and X. Yin, “The algebraic decoding of the (41, 21, 9) quadratic residue code,” IEEE Trans. Inform. Theory, vol. 38, pp. 974-985, May 1992.
[12] R. He, I. S. Reed, T. K. Truong, and X. Chen, “Decoding the (47, 24, 11) quadratic residue code,” IEEE Trans. Inform. Theory, vol. 47, pp. 1181–1186, Mar. 2001.
[13] X. Chen, I. S. Reed, and T. K. Truong, “Decoding the (73, 37, 13) quadratic residue code,” Proc. IEE, vol. 141, pp. 253-258, Sep. 1994.
[14] X. Chen, I. S. Reed, T. Helleseth, and T. K. Truong, “Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance,” IEEE Trans. Inform. Theory, vol. 40, no. 5, pp. 1654-1661, Sep. 1994.
[15] P. Loustaunau, E. V. York, “On the decoding of cyclic codes using Gröbner bases,” Appl. Alg. Eng. Commun. Comput., vol. 8, pp. 469-483, 1997.
[16] I. S. Reed, M. T. Shih, and T. K. Truong, “VLSI design of inverse-free Berlekamp-Massey algorithm,” Proc. IEE, vol. 138, pp. 295-298, Sep. 1991.
[17] X. Youzhi, “Implementation of Berlekamp-Massey algorithm without inversion,” Proc. IEE, vol. 138, no. 3, 1991.
[18] R. E. Blahut, Theory and practice of error control code. Reading, Mass.: Addison-Wesley, 1983.
[19] S. B. Wicker and V. K. Bhargava, Reed-Solomon codes and their applications. The Institute of Electrical and Electronics Engineers, Inc., New York, 1994.
[20] S. B. Wicker, Error control systems for digital communication and storage. Prentice Hall, Englewood Cliffs, New Jersey, 1995.
[21] T. K. Truong, J. H. Jeng, and I. S. Reed, “Fast algorithm for computing the roots of error locator polynomials up to degree 11 in Reed-Solomon decoders,” IEEE Trans. Commun., vol. 49, pp. 779-783, May 2001.
[22] F. J. MacWilliams, “A theorem on the distribution of weights in a systematic code,” Bell System Technical Journal, vol. 42, pp. 79-94, Jan. 1962.
[23] V. Pless, J. M. Masley, and J. S. Leon, “On weights in duadic codes,” J. Combin. Theory, Series A, vol. 44, no. 1, pp. 6-21, Jan. 1987.
[24] R. J. McEliece, “Weight congruences for p-ary cyclic codes,” Discrete Math., vol. 3, pp. 177-192, 1972.
[25] V. Pless, “Power moment identities on weight distributions in error correcting codes,” Inform. and Control, vol. 6, pp. 147-152, Jun. 1963.
[26] R. J. McEliece, “Weights modulo 8 in binary cyclic codes,” JPL Tech. Rep. 32-1526, vol. 11, pp. 86-88, Oct. 1972.
[27] J. M. Goethals, “Analysis of weight distribution in binary cyclic codes,” IEEE Trans. Inform. Theory, vol. 12, pp. 401-402, Jul. 1966.
[28] X. Chen, I. S. Reed, and T. K. Truong, “A performance comparison of the binary quadratic residue codes with the 1/2-rate convolutional codes,” IEEE Trans. Inform. Theory, vol. 40, pp. 126-136, Jan. 1994.
[29] S. T. Dougherty, T. A. Gulliver, and M. Harada, “Extremal binary self-dual codes,” IEEE Trans. Inform. Theory, vol. 43, no. 6, pp. 2036-2047, Nov. 1997.
[30] J. Mykkeltveit, C. Lam, and R. McEliece, “On the weight enumerators of quadratic residue codes,” JPL Tech. Rep. 32-1526, vol. 12, pp. 161-166, Dec. 1972.
[31] V. Pless et al., Handbook of Coding Theory. Amsterdam, The Netherlands: North Holland, 1998.
[32] E. Prange, “Cyclic error-correcting codes in two symbols,” AFCRC-TN-57-103, Air Force Cambridge Research Center, Cambridge, Mass., Sep. 1957.
[33] G. L. Feng and K. K. Tzeng, “A new procedure for decoding cyclic and BCH codes up to actual minimum distance,” IEEE Trans. Inform. Theory, vol. 40, no. 5, pp. 1364-1374, Sep. 1994.
[34] K. K. Shen, C. Wang, K. K. Tzeng, and B. Z. Shen, “Generation of matrices for determining minimum distance and decoding of cyclic codes,” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 653-657, Mar. 1996.
[35] M. A. Armand and S. H. Ong, “Linear dependence relations of nonrecurrent syndromes in decoding cyclic codes beyond their design distance,” in Proc. 8th International conference on Communication systems, Singapore, Nov. 2002, pp. 317-321.
[36] Y. Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes,” IEEE Trans. Commun., vol. 51, no. 9, pp. 1463-1473, Sep. 2003.
[37] T. K. Truong, Y. Chang, Y. H. Chen, and C. D. Lee, “Algebraic decoding of (103, 52, 19) and (113, 57, 15) quadratic residue codes,” IEEE Trans. Commun., vol. 53, no. 5, pp. 749-754, May 2005.
[38] T. K. Truong, Y. Chang, I. S. Reed, R. He, C. D. Lee, and Y. H. Chen, “Algebraic decoding of (79, 40, 15) quadratic residue code using inverse-free Berlekamp-Massey algorithm,” in Proc. IEEE Inform. Theory Workshop 2003, Paris, France, pp. 238-224, Mar. 2003.
[39] Y. Chang, T. K. Truong, I. S. Reed, R. He, Y. H. Chen, and C.D. Lee, “Algebraic decoding of (71, 36, 11) quadratic residue code using inverse-free Berlekamp-Massey algorithm,” in Proc. International Conference on Communication Technology 2003, Beijing, China, vol. 2, pp. 1540-1546, Apr. 2003.
[40] E. F. Assmus, Jr. and H. F. Mattson, Jr., “New 5-designs,” J. Combin. Theory, vol. 6, pp. 122-151, 1969.
[41] C. D. Lee, Y. Chang, and T. K. Truong, “Decoding binary quadratic residue codes using syndrome polynomial,” Accepted for publication in Proc. International Conference on Communications, Circuits, and Systems 2006, Guilin, China, Jun. 2006.
[42] T. K. Truong, Y. Chang, and C. D. Lee, “The weight distributions of some binary quadratic residue codes,” IEEE Trans. Inform. Theory, vol. 51, no. 5, pp. 1776-1782, May 2005.
[43] C. D. Lee, Y. Chang, and T. K. Truong, “A result on the weight distributions of binary quadratic residue codes,” Des. Codes Crypt. (revised)
[44] R. Koetter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes,” IEEE Trans. Inform. Theory, vol. 49, no. 11, pp. 2809-2025, Nov. 2003.