臺灣博碩士論文加值系統

本論文主要提出代數解碼方法可用於二元平方剩餘碼，利用柏利根 (Berlekamp Massey) 演算法，再根據Ruhua等人所提出方法改良，可透過已知症狀值經由函數計算得到未知症狀值，論文當中也針對這些未知症狀值提出了一個快速有效率的演算法進行尋找。然而，柏利根演算法需要連續症狀值才能使用，由於二元平方剩餘碼在計算出症狀值當中會有一些未知症狀值的出現。所以需要補足計算出這些未知症狀值，才能使用這新的解碼法進行解碼。

目前發展此新的解碼法，比先前解碼法，更適合用在格雷碼 (23, 12, 7) 與 (47, 24, 11) 二元平方剩餘碼上，而且更容易實現。此方法原本是針對生成多項式為不可分解的二元平方剩餘碼進行解碼，也可以擴展成為可通用於二元平方剩餘碼之解碼法。前述演算法已經使用C++程式語言撰寫，並且對於 (23, 12, 7) 、 (47, 24, 11) 、 (103, 51, 19) 與 (113, 57, 15) 的二元平方剩餘碼，進行所有錯誤位址的組合的測試。

In this dissertation, an algebraic decoding method is proposed for the quadratic residue codes that utilize the Berlekamp-Massey algorithm. By a modification of the technique mentioned by Ruhua et al, one can express the unknown syndromes as functions of the known syndromes. The unknown syndromes are determined by an efficient algorithm also developed in this dissertation. With the appearance of unknown syndromes, one obtains the consecutive syndromes needed for the application of the Berlekamp-Massey algorithm.

The new decoding scheme, developed here, is easier to implement than the previous decoding algorithm developed for the Golay (23, 12, 7) code and the (47, 24, 11) QR code. Moreover, it can be extended to decode all codes of the family of binary quadratic residue codes with irreducible generating polynomials and can serve as a universal decoding scheme for these binary quadratic residue codes. This new algorithm is verified by a computer program that uses C++ language. This program is used to check every possible error pattern of the (23, 12, 7), (47, 24, 11) (103, 51, 19), and (113, 57, 15) QR codes.

摘 要 I
ABSTRACT II
CONTENTS III
LIST OF TABLES VI
CHAPTER 1 INTRODUCTION 1
1.1 THE MOTIVATION 2
1.2 THE PROPOSED METHODS AND CONTRIBUTIONS 3
1.3 ORGANIZATION OF THIS DISSERTATION 3
CHAPTER 2 TERMINOLOGY AND MATHEMATICS BACKGROUND 5
2.1 ALGEBRAIC STRUCTURE 5
2.2 GALOIS FILED 6
2.3 THE POLYNOMIAL ALGEBRA STRUCTURE 8
2.4 LINEAR BLOCK CODES 9
2.5 CYCLIC CODES 10
2.6 BINARY QR CODES 12
CHAPTER 3 THE (23, 12, 7) AND (47, 24, 11) QR CODES 15
3.1 EFFICIENT ALGORITHM TO DETERMINE THE UNKNOWN SYNDROMES 15
3.2 ALGEBRAIC DECODER FOR (47, 24, 11) QR CODE USING THE BM ALGORITHM 21
3.2.1 Determination of the Unknown Syndrome S5 23
3.2.2 The Inverse-Free Berlekamp-Massey Algorithm 28
CHAPTER 4 THE (103, 52, 19) AND (113, 57, 15) QR CODES 37
4.1 POWER OF S1 37
4.2 DETERMINATION OF THE UNKNOWN SYNDROMES 40
4.3 DECODE THE (103, 52, 19) AND (113, 57, 15) QR CODES 49
CHAPTER 5 BINARY QR CODES PERFORMANCE ANALYSIS 52
5.1 NOISE MODELS 52
5.2 THE GRAPHS OF RESULTS 56
CHAPTER 6 THE RESULT AND CONCLUSIONS 58
REFERENCE 60
APPENDIX 62

[1] Amrani, Y. Be’ery, A. Vardy, F.-W. Sun, and H. C. A. van Tilborg “The Leech lattice and the Golay code: Bounded-distance decoding and multilevel constructions,” IEEE Trans. Inform. Theory, vol. 40, pp.1030-1043, July 1994.
[2] E. F. Assmus, Jr., and H. F. Mattson, Jr., “New 5-designs,” J. Comb. Theory, vol. 6, pp. 22-151, 1969.
[3] 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. on Inform. Theory, vol. 40, pp. 126–136, 1994.
[4] F. J. MacWilliams and N. J. A. Sloan, The theory of error-correcting codes. Amsterdam, The Netherlands: North-Holland, 1977.
[5] J. Wolfmann, “A permutation decoding of the (24, 12, 8) Golay code,” IEEE Trans.Inform. Theory, vol. IT-29, no. 5, pp. 748–750, Sept. 1983.
[6] T. Kasami, “A decoding procedure for multiple-error-correcting cyclic codes,” IEEE Trans. Inform. Theory, vol. IT-10, pp. 134–138, April 1964.
[7] M. Blaum and J. Bruck, “Decoding the Golay code with Venn diagrams,” IEEE Trans. Inform. Theory, vol. 36, no. 4, pp. 906–910, July 1990.
[8] V. Pless, “Decoding the Golay codes,” IEEE Trans. Inform. Theory, vol. IT-32, no. 4, pp.561–567, July 1986.
[9] J. Yuan, C. S. Chen, and S. Ma, “Two-level decoding of (32, 16, 8) quadratic residue Code,” Proc. IEE Commun. Speech Vis., vol. 140, no. 6, pp. 409–414, Dec. 1993.
[10]M. Elia, “Algebraic decoding of the (23, 12, 7) Golay code,” IEEE Trans. Inform. Theory, vol. 33, no. 1, pp. 150–151, Jan. 1987.
[11] I. S. Reed, X. Yin, T. K. Truong, and J. K. Holmes, “Decoding the (24, 12, 8) Golay code, ” Proc. IEE Inst. Elec. Eng., vol. 137, no. 3, pp. 202–206, May 1990.
[12]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, no. 4, pp. 876–880, July 1990.
[13] 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, no. 3, pp. 974–985, May 1992.
[14] X. Chen, I. S. Reed, and T. K. Truong, “Decoding the (73, 37, 13) quadratic residue code,” Proc. IEE Comput. Digit. Tech., vol. 141, no. 5, pp. 253–258, Sept. 1994.
[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, no. 5, pp. 1654–1661, Sept. 1994.
[16] Y. Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic decoding of the (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes,”IEEE Trans. Commun., vol. 51, no. 9, pp. 1463–1473, Sept. 2003 .
[17] 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, no. 3, pp. 1181–1186, March 2001.
[18] E. R. Berlekamp, Algebraic Decoding Theory. New York: McGraw-Hill, 1968.
[19] J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. On Inform. Theory, vol. IT-15, no. 1, pp. 122–127, Jan. 1969.
[20] I. S. Reed, M. T. Shih, and T. K. Truong, “VLSI design of inverse-free Berlekamp-Massey algorithm,” Proc. IEE, vol. 138, no. 5, pp. 295–298, Sept. 1991.
[21] X. Youzhi, “Implementation of Berlekamp-Massey algorithm without inversion,” Proc. IEE Commun. Speech Vis., vol. 138, no. 3, pp. 138–140, June 1991.
[22] M. Karlin, “New binary coding results by circulants,” IEEE Trans. Inform. Theory, vol. 15, no. 1, pp. 81–92, Jan. 1969.
[23] D. Coppersmith and G. Seroussi, “On the minimum distance of some quadratic residue codes,” IEEE Trans. Inform. Theory, vol. 30, no. 2, pp. 407–411, March 1984.
[24] I. S. Reed and X. Chen, Error-Control Coding for Data Networks, Massachusetts: KAP, 1999
[25]S. B. Wicker, Error Control Sytems for Digital Comunication and Storage, Canada: PHI. 1985
[26] T. K. Truong, J. H. Jeng, and I. S. Reed, “Fast algorithm for computing the roots of the error locator polynomials up to degree 11 in Reed-Solomon decoders, “ IEEE Trans. on Commun., vol. 49, no. 5, pp. 779–783, May 2001.
[27] S. V. Fedorenko and P. V. Trifonov, “Finding roots of polynomials over finite fields,”IEEE Trans. on Commun., vol. 50, no. 11, pp. 1709–1711, Nov. 2002.