臺灣博碩士論文加值系統

單一症狀值可解碼的二元循環碼中包含了許多好的糾錯碼，本論文提出一種通用的新型解碼法能適用於所有此類的糾錯碼。文中提出三種預先被計算出的多項式，在解碼時用來計算錯誤位置，它被稱為”錯誤位置核對多項式”，此多項式的根包含了與某一個指定錯誤位置相關的所有症狀值，所以當解碼時只要將計算出的症狀值帶入此多項式中，即可判斷此症狀值是否與指定的錯誤位置相關，從而判斷此位置是否發生錯誤。
然而，本論文應用於糾錯能力較高之碼類時，使用原本錯誤位置核對多項式的定義方式將涉及大量的計算，為了解決此問題，本論文提出了一種遞迴關係式，可利用已知的錯誤位置核對多項式來求出所需之錯誤位置核對多項式，如此提供了一種快速的計算方式讓本方法能適用於糾錯能力較高之情況。此外，針對糾錯能力為二的情形下，本論文證明了其錯誤位置核對多項式可以直接被碼長決定，如此對於碼長很大的碼類而言，能提供一種準確評估其電路實現複雜度的方法。
對於單一症狀值可解碼的二元循環碼，目前存在有三種通用的解碼法，它們的精神與本論文相似，在解碼前，必須要預先計算出一個多項式，隨後再利用此多項式進行解碼，與這三種方法比較下，本論文方法無論在多項式計算的複雜度及解碼器電路的複雜度上均為最低，故本論文的解碼法較能被實務所應用。

There are many good even best codes belong to the single-syndrome correctable codes. In this dissertation, a new general decoding algorithm is proposed for these codes. We define three pre-calculated polynomials which are used to determine the error positions and called the "error-location-checking polynomials". The roots of such polynomial are all the syndromes of those correctable error patterns with an error occurred at a fixed position. In the decoding scheme, the error locations can be determined by the output of plugging the syndrome into the error-location-checking polynomials.
However, applying this method to the single-syndrome correctable codes, we encounter a huge computing complexity for the cases with big error-capabilities. For solving this problem, a recursive relation is proposed to generate an error-location-checking polynomial by two pre-calculated error-location-checking polynomials, which provides a faster computation of error-location-checking polynomials for the codes with big error-capabilities. Moreover, especially for the codes with error-capabilities 2, we prove that their error-location-checking polynomials can be determined only by the code length. This provides a precise method to estimate the hardware complexity of circuit implementation for the codes with big error-capabilities.
There are three general decoding algorithms for the single-syndrome correctable codes. The mutual decoding procedure is using a pre-calculated polynomial to decode. The comparison with those algorithms, our complexities of computing the needed pre-calculated polynomial and circuit implementation are the lowest. That is, the decoding algorithm can be used in practical applications.

Dedication i
Acknowledgement ii
中文摘要iii
Abstract v
List of Tables and Figure vii
List of Theorems viii
List of Properties and Corollary ix
List of Algorithms x
List of Contents xii
Chapter 1 Introduction 1
1.1 Preliminary of Cyclic Codes 1
1.2 Motivation 3
1.3 Framework 4
Chapter 2 Mathematical Background 5
2.1 Finite Fields 5
2.1.1 Addition and Subtraction 6
2.1.2 Multiplication and Multiplicative Inversion 7
2.1.3 Exponentiation 8
2.2 Minimal Polynomials and Conjugacy Classes 9
2.3 Cyclic Codes 10
2.3.1 Encoding Scheme 11
2.3.2 Decoding Scheme 12
Chapter 3 Error-Location-Checking Polynomial for Two-Error Case 16
3.1 Notations 16
3.2 Polynomial Definitions 17
3.3 General Error-Location-Checking Polynomial for 21
3.4 Decoding Algorithm 24
3.5 Compare to General 2-Error Algebraic Decoding Methods 26
3.6 The Low-Complexity Decoder for 30
Chapter 4 General Error-Location-Checking Polynomial for Decoding Up to the True Minimum Distance 32
4.1 The Main Theorem 32
4.2 Generalized n-conjugate Class and n-minimal Polynomial 34
4.3 Proposed Method to Calculate Mr(x) and Hi(x) 36
4.4 Fast Method to Calculate H2(x) 38
Chapter 5 Simulation Result and Limitation 41
5.1 The On-Line and Off-Line Parts for the Proposed Decoding Algorithm 41
5.2 The Limitation for the Proposed Decoding Algorithm 46
Chapter 6 Conclusion 47
Reference 48
List of Tables and Figure
Figure I The BCH (left) and the proposed (right) decoding schemes 3
Figure II The low-complexity serial-typed decoder for wt(e(x))<=2 31
Table I The elements belong to the set T1 14
Table II The elements belong to the set T2 14
Table III All illustrations of the 2-error correctable code C with n<512 27
Table IV Comparisons of decoding procedures of three decoding methods 28
Table V The elements belong to the set A1 42
Table VI The elements belong to the set A2 42
Table VII Comparisons of decoding procedures of three decoding methods 43
Table VIII The complexity of operations of algorithms listed in Table VII 44
Table IX The complexity of various decoders for (23, 12) Golay code 45

[1]C. D. Lee, Y. Chang, H. H. Chang, and J. H. Chen, “Unusual General Error Locator Polynomial for the (23, 12, 7) Golay Code,” IEEE Commun. Lett., vol. 14, no. 4, pp. 339-341, Apr. 2010.
[2]C. D. Lee, Y. Chang, M. H. Jing, and J. H. Chen, “Decoding binary cyclic codes with irreducible generator polynomials up to actual minimum distance,” IEEE Commun. Lett., vol. 14, no. 11, pp. 1050-1052, Nov. 2010.
[3]C. Ding, T. Helleseth, H. Niederreiter, and C. Xing, “The minimum distance of the duals of binary irreducible cyclic codes, ” IEEE Trans. Inform. Theory, vol. 48, no. 10, pp. 2679-2689, 2002.
[4]C. Marcolla, E. Orsini, and M. Sala, “Improved decoding of affine-variety codes,” Mar. 2011. [Online]. Available: http://arxiv.org/abs/1102.4186.
[5]D. Augot, M. Bardet, and J.-C. Faugère, “On the decoding of binary cyclic codes with the Newton identities,” J. Symboc. Comput., vol. 44, no. 12, pp. 1608-1625, Dec. 2009.
[6]Dmitri Strukov, “The area and latency tradeoffs of binary bit-parallel BCH decoders for prospective nano electronic memories,” ACSSC Papers, pp. 1183-1187, May, 2007.
[7]E. Orsini and M. Sala, “Correcting errors and erasures via the syndrome variety,” J. Pure Appl. Algebra, vol. 200, pp. 191-226, 2005.
[8]E. Orsini and M. Sala, “General error locator polynomials for binary cyclic codes with and ,” IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1095-1107, Mar. 2007.
[9]E. Prange, “Cyclic error-correcting codes in two symbols,” Air Force Cambridge Research Center-TN-57-103, Cambridge, MA, 1957.
[10]E. R. Berlekamp, Algebraic Decoding Theory. New York: McGrawHill, 1968.
[11]E. V. York, “Algebraic description and construction of error correcting codes, a systems theory point of view,” Ph.D. dissertation, Univ. Notre Dame, 1997.
[12]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, Sept. 1994.
[13]I. E. Sutherland, R. F. Sproull, and D. Harris, Logical effort designing fast CMOS circuits, San Francisco, CA; London: Morgan Kaufmann Publishers, 1999.
[14]J. E. Meggitt, “Error Correcting Codes and Their Implementation,” IRE Trans. Inf. Theory, IT-7, pp. 232-244, Oct. 1961.
[15]K. K. Shen, C. Wang, K. K. Tzeng, and B.-Z. Shen, “Generation of matrix for determining minimum distance and decoding of cyclic codes,” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 653-657, Mar. 1996.
[16]L. Rudolph, “Easily Implemented Error-Correction Encoding-Decoding,” G. E. Report No. 62MCD2, General Electric Corporation, Oklahoma City, Okla., Dec. 1962.
[17]M. A. Armand and S. H. Ong, “Linear dependence relations of nonrecurrent syndromes in decoding cyclic codes beyond their design distance,” in Proc. International Conference on Commun. Systems, vol. 1, pp. 317-321, Singapore, Nov. 2002.
[18]M. A. Neifeld and J. D. Hayes, “Error-correction schemes for volume optical memories,” Applied Optics, vol. 34, no. 35, pp. 8183-8191, 1995.
[19]M. E. Mitchell et al., “Coding and Decoding Operation Research,” G. E. Advanced Chap. 5 References 139 Electronics Final Report on Contract AF 19 (604)-6183, Air Force Cambridge Research Labs., Cambridge, Mass., 1961.
[20]M. Elia, “Algebraic decoding of the (23, 12, 7) Golay code,” IEEE Trans. Inf. Theory, vol. IT-33, pp. 150-151, Jan. 1987.
[21]Ming-Haw Jing, Yaotsu Chang, Chong-Dao Lee, Jian-Hong Chen, and Zih-Heng Chen, “A Result on Zetterberg Codes, ” IEEE Commun. Lett., vol. 14, no. 7, pp. 662-663, July, 2010.
[22]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.
[23]S. Lin and D. J. Costello, Error-Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall, 1983.
[24]S. Reed, “A Class of Multiple-Error-Correcting Codes and the Decoding Scheme,” IRE Trans., IT-4. pp. 38-49, Sept. 1954.
[25]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.
[26]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, July 1990.
[27]T. K. Truong, P. Y. Shih, W. K. Su, C. D. Lee, and Y. Chang, “Algebraic decoding of (89, 45, 17) quadratic residue code, ” IEEE Trans. Inform. Theory, vol. 54, no. 11, pp. 5005-5011, Nov. 2008.
[28]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.
[29]T. Kasami, “A Decoding Method for Multiple-Error-Correcting Cyclic Codes by Using Threshold Logics,” Conv. Rec. Inf. Process. Soc. Jap. (in Japanese), Tokyo, Nov. 1961.
[30]X. Chen, I. S. Reed, and T. K. Truong, “Decoding the (73, 37, 13) quadratic residue code,” Proc. IEE, vol. 141, pp. 253-258, Sept. 1994.
[31]X. Chen, I. S. Reed, T. Hellessth, 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, Sept. 1994.
[32]Y. Chang and C. D. Lee, “Algebraic decoding of a class of binary cyclic codes via Lagrange interpolation formula,” IEEE Trans. Inform. Theory, vol. 56, no. 1, pp. 130-139, Jan. 2010.
[33]Y. Chang, C. D. Lee, Z. H. Chen, J. H. Chen, “(23, 12, 7) quadratic residue decoder based on syndrome-weight determination,” Electronics Letters, vol. 44, no. 19, pp. 1147-1149, 2008.09.
[34]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, Sept. 2003.