臺灣博碩士論文加值系統

本論文研究主題是二元平方剩餘碼的代數解碼，本論文提出二種新式代數解碼方法，分別是使用無反根Berlekamp-Massey演算法和症狀子多項式(Syndrome polynomial)來完成二元平方剩餘碼之解碼。
基於被張肇健院長等人提出適用於部分具有不可分解的生成多項式之二元平方剩餘碼的解碼法，本研究發展出ㄧ個(89, 45, 17)二元平方剩餘碼的解碼器。此碼具有可分解的生成多項式，同時也是長度100以內最後一個未被解碼成功的碼。本論文提出一個理論用以驗證解碼結果是否正確，其可被廣泛應用於檢測解碼器的正確性，尤其隨著碼的長度越長與解碼能力越大相對須要檢測可能錯誤情況的數量越來越龐大，此時更顯現以理論方式檢測解碼正確性的重要性。此解碼法已經由理論方式驗證其在解碼能力範圍內之所有錯誤情況皆可以被解碼成功。

Binary quadratic residue codes are among the most powerful known block codes. This dissertation is focused on the topics of algebraic decoding of binary quadratic residue codes. Two new algebraic decoding schemes for the binary quadratic residue codes are proposed. The key ideals behind these two decoding techniques are the utilization of the inverse-free Berlekamp-Massey algorithm and syndrome polynomial, respectively. In this research, based on ideas of the decoding algorithm suggested by Truong et al. for some quadratic residue codes with irreducible generating polynomials, an algebraic decoder for the (89, 45, 17) binary quadratic residue code with a reducible generating polynomial, the last one not decoded yet of length less than 100, is proposed. It was also verified theoretically for all error patterns within the error-correcting capacity of the code. Moreover, the verification method developed in this research can be extended for all cyclic codes without checking all error patterns by computer simulations.

Acknowledgments…………………………………………… ii
Abstract (Chinese)……………………………………………………………… iii
Abstract (English)……………………………………………………………… iv
List of Figures………………………………………………… vii
List of Tables…………………………………………… viii

1Introduction…………………………………………………… 1
1.1 Historical Background and Motivation………… 1
1.2 Framework……………………………… 2

2 Mathematical Background…………………………… 4
2.1 Galois Fields…………………………… 4
2.2 Polynomials Over Galois Fields….… 6
2.3 Cyclic Codes and Quadratic Residue Codes…… 9

3 Algebraic Decoding Methods……………………… 12
3.1 Preliminaries……………………………………… 12
3.1.1 Syndromes and Error-Locator Polynomials……… 12
3.1.2 Inverse-Free Berlekamp-Massey Algorithm…… 17
3.1.3 Syndrome Polynomials……………………………… 18
3.2 Unknown Syndromes………………………………… 19
3.2.1 Determination of Unknown Syndromes…………… 20
3.2.2 Mapping Relationship of the (89, 45, 17) Quadratic Residue Code Between Error Patterns and Primary Known Syndromes………………………………………………… 23
3.2.3 Primary Unknown Syndromes S3 and S13 of the (89, 45, 17) Quadratic Residue Code………………………………27
3.3 Decoding Method Using Inverse-Free Berlekamp-Massey Algorithm……………………………………… 32
3.3.1 The (89, 45, 17) Quadratic Residue Decoder……34
3.3.2 Simulation Result ………………………… 37
3.4 Decoding Binary Quadratic Residue Codes Using the Euclidean Algorithm…………………………………… 38
3.4.1 Decoding Algorithm………………………………… 40
3.4.2 An Example of Decoding (41, 21, 9) Quadratic Residue Code………………………………………………………45
3.4.3 Simulation Results…………………………………49

4 Conclusions
4.1Contributions…………………………………………………51
4.2 Future Work……………………………………………52

Bibliography………………………………………………………53

[1]M. J. E. Golay, “Notes on digital coding,” Proc. IRE, vol. 37, p. 67, 1949.
[2]E. Prange, “Some cyclic error-correcting codes with simple decoding algorithms,” Air Force Cambridge Research Center-TN-58-156, Cambridge, MA: April 1958.
[3]S. B. Wicker, Error Control Systems for Digital Communication and Storage. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1995.
[4]R. He, I. S. Reed, T. K. Truong, and X. Chen, “Decoding of the (47, 24, 11) quadratic residue code,” IEEE Trans. Inform. Theory, vol. 47, pp. 1181-1186, Mar. 2001.
[5]R. W. Hamming, “Error detecting and error correcting codes,” Bell Syst. Tech. J., vol. 29, pp. 147-160, 1950.
[6]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.
[7]M. Elia, “Algebraic decoding of the (23, 12, 7) Golay code,” IEEE Trans. Inform. Theory, vol. IT-33, pp. 150-151, Jan. 1987.
[8]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.
[9]I. S. Reed and X. Chen, Error-Control Coding for Data Networks. Boston, MA: Kluwer, 1999.
[10]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.
[11]Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S. H. Chen, “Algebraic decoding of quadratic residue codes using inverse-free Berlekamp-Massey algorithm,” Journal of Information Science and Engineering, vol. 23, pp. 127-145, Jan. 2007.
[12]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.
[13]Yaotsu Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic decoding of (71, 36, 11), (79, 36, 11), and (97, 49, 15) quadratic residue codes,” IEEE Trans. Commun., vol. 51, pp. 1463-1473, Sep. 2003.
[14]T. K. Truong, Yaotsu Chang, Yan-Haw Chen, and C. D. Lee, “Algebraic decoding of (103, 52, 19) and (113, 57, 15) quadratic residue codes,” IEEE Trans. Commun., vol. 53, pp. 749-754, May 2005.
[15]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, pp. 1654-1661, Sep. 1994.
[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, pp. 138-140, 1991.
[18]R. E. Blahut, Theory and Practice of Error Control Code. Reading, MA: Addison-Wesley, 1983.
[19]E. Prange, “Cyclic error-correcting codes in two symbols,” AFCRC-TN-57-103, Air Force Cambridge Research Center, Cambridge, Mass., Sep. 1957.
[20]E. Prange, “Cyclic error-correcting codes in two symbols,” AFCRC-TN-57-103, Air Force Cambridge Research Center, Cambridge, Mass., Sep. 1957.
[21]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.
[22]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, April 2003.
[23]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, March 2003.
[24]T. K. Truong, P. Y. Shih, W. K. Su, C. D. Lee, and Yaotsu Chang, “ Algebratic Decoding of the (89, 45, 17) Quadratic Residue code,” IEEE Trans. Inform. Theory, vol.54, no.11, pp. 5005-5011, Nov. 2008.
[25]P. Y. Shih, W. K. Su, T. K. Truong, and Y. Chang, “ Decoding Binary Quadratic Residue Codes Using the Euclidean Algorithm ,” accepted to publish in Journal of Information Science and Engineering. Mar. 2008.
[26]D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inform. Theory, vol. IT-18, no. 1, pp. 170–182, Jan. 1972.
[27]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.