臺灣博碩士論文加值系統

里德-索羅門碼至少有兩種編碼的方法。我們選用的方法可以用長除法作, 但是它所需要的複雜度(有限體
元素間的加法與乘法個數) 太大。因此我們把編碼方成兩部分來完成。我們的目標是加速它的第一部分, 而第
二部分的加快留待未來展望。
在整個里德-索羅門碼的編碼與解碼中, 有兩個部分用到了多項式的求值。一個在編碼的第一部分; 另一個
在解碼部分syndrome 的計算上。我們用C++ 程式測量知道, 多項式求值在整個里德-索羅門碼的編碼與解
碼過程中的確是一個瓶頸。
在這篇論文中, 我們提供兩個多項式求值的方法, C.E.O. (參考[12] 並修改之) 和M.C.E.O.。(參考
[13] 並修改之) 並與直接求值D.E. (Horn’s rule) 與M.F.F.T. (Cooley-Tukey FFT (1965) [10]) 作
了比較。
在每個方法中, 我們都混合了一些技巧。在3.2.1 這一節中我們展示了C.E.O. 與M.F.F.T. 如何被
合併使用於多項式的求值。但它的performance 不太好。感謝神, 讓我想到M.C.E.O. 的方法; 它同時包
含了C.E.O. 與M.F.F.T. 兩種方法的優點。
以上所有程式都有辦法用程式自動產生C++ code 出來。

There are at least two encoding methods for Reed-Solomon codes. The one we choose can be
achieved by long division method, but its complexity in terms of the number of operations is a
little too large. Our approach is to divide it into two steps. Our goal is to make the computing of
the first step more efficient, and we leave the second step to the future work.
In the whole encoding and decoding schemes of Reed-Solomon codes, there are two parts where
evaluations for polynomials are computed: one is in the first step of the encoding scheme, and
the other in the syndrome computing of the decoding scheme. We have run our C++ programming
codes to measure the ratio of time-complexity occupied by the part of evaluations for
polynomials over that by the remaining part. By running our C++ programming codes, we
are told that the evaluation for polynomials is really a bottleneck for the whole encoding and
decoding complexity of Reed-Solomon codes.
In this paper, a number of complexity reduction tricks on the evaluation for polynomials,
with a little or much modification are suggested. They are D.E., C.E.O., M.F.F.T., and
M.C.E.O.. D.E. is a direct evaluation method using Horn’s rule. M.F.F.T. is a method by
applying Cooley-Tukey FFT (1965) [10]. C.E.O. is a method by modifying the algorithm of Sergei
V. Fedorenko and Peter V. Trifonov [12]. M.C.E.O. is a method by following the idea of Peter
V. Trifonov and Sergei V. Fedorenko [13], but with much modification. C.E.O and M.C.E.O.
are the two methods we give in this thesis.
In each methods, some important properties are used and combined together. In section 3.2.1,
we show how C.E.O. and M.F.F.T. can be used together in the polynomial evaluation. But
its performance is not that good. I give thanks to God, since I came up with the modified idea
of M.C.E.O.. To our thinking, M.C.E.O. takes both advantages of C.E.O. and M.F.F.T..
Moreover, for all of the methods suggested, automatic generations of the programming codes implementing
the described algorithms are possible.

1 Introduction 3
1.1 Error Correcting Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 An example – Reed-Solomon code and its minimum distance . . . . . . . . 4
1.2 Reed-Solomon codes (RS codes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Outlines about the encoding and decoding of RS(255,223) . . . . . . . . . . . . . 5
1.4 Outline of the following chapters . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Toward the encoding of RS(255,223) 7
2.1 Generating the Galois field GF(28) . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Encoding RS(255,223) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The first part of the encoding scheme–Evaluating using C.E.O. . . . . . . . . . . . 14
2.4 The second part of the encoding scheme - Linear equation . . . . . . . . . . . . . 16
2.5 Pseucode of Inversion of Vandermode Matrix . . . . . . . . . . . . . . . . . . . . . 18
2.6 The complexity of the whole encoding scheme using C.E.O. . . . . . . . . . . . . . 19
2.7 Compare C.E.O. with the D.E. method . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Another evaluating method: M.F.F.T. 21
3.1 Theoretical discussion: C.E.O., D.E. vs M.F.F.T. . . . . . . . . . . . . . . . . . . 21
3.2 Analysis of two cases of M.F.F.T. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Case 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 A modified version of C.E.O. (M.C.E.O) 26
4.1 Relations between the elements in a Galois field . . . . . . . . . . . . . . . . . . . 27
4.2 Evaluating polynomial in cyclotomic-form: First attempt. . . . . . . . . . . . . . . 30
4.3 Evaluating polynomial in cyclotomic-form: Improvement. . . . . . . . . . . . . . . 33
4.4 Evaluating polynomial in cyclotomic-form: The core part. . . . . . . . . . . . . . 34
4.5 Evaluating polynomial in cyclotomic-form: The remaining part. . . . . . . . . . . 34
4.6 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.6.1 Further reducing the number of additions . . . . . . . . . . . . . . . . . . . 36
4.7 Review for the complexity of evaluating . . . . . . . . . . . . . . . . . . . . . . . . 36
5 The decoding of RS(255,223) 37
5.1 Calculate the syndromes Si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 The Berlekamp-Massey algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.3 Find the roots of the error-locator polynomial . . . . . . . . . . . . . . . . . . . . 42
5.4 Forney’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 The efficiency of Forney’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.5.1 The linear convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.5.2 The computing of the error magnitudes . . . . . . . . . . . . . . . . . . . . 44
Conclusion and Future work 45
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.2.1 Interesting relations between the Forney’s algorithm, Vandermonde matrix
and the Berlekamp-Massey algorithm . . . . . . . . . . . . . . . . . . . . . 46
6.2.2 The speedup of the Berlekamp-Massey algorithm . . . . . . . . . . . . . . 47
6.2.3 More regularity for M.C.E.O. (section 4.6.1) . . . . . . . . . . . . . . . . . 47
6.2.4 The regularity for V¡1 ¢ a (section 2.4) . . . . . . . . . . . . . . . . . . . . 47
Thanks to . . . i
誌謝. ii
Abstract 1
論文摘要2
Bibliography 48

[1] Joachm von zur Gathen and J¨urgen Gerhard, Modern Computer Algebra, Cambridge University
Press, 2003.
[2] S. Gao, ”A new algorithm for decoding Reed-Solomon codes,” in Communications, Information
and Network Security, V. Bhargave, H. V. Poor, V. Tarokh, and S. Toon, Eds. Norwell,
MA: Kluwer, 2003, vol. 712, pp.55-68.
[3] Sergei V. Fedorenko, Member, IEEE, ”A simple algorithm for decoding Reed-Solomon codes
and its relation to the Welch-Berlekamp algorithm”, IEEE Transactions on information theory,
vol. 51, no. 3, pp.1196-1198, March 2005.
[4] Victor Y. Pan and Xinmao Want, ”Acceleration of Euclidean Algorithm and Extensions”,
SIAM Journal on Computing, vol. 32, no. 2, pp. 548-556, 2002.
[5] Alban Goupil and Jacques Palicot, ”Variation on Variation on Euclid’s Algorithm”, IEEE
Signal Letters, vol. 11, no. 5, pp.457-458, May 2004.
[6] L.C. Calvez, S. Azou, and P. Vilb´e, ”Variation on Euclid’s algorithm for polynomials,” IEEE
Electronics Letters, vol. 33, no. 11, pp.939-940, May 1997.
[7] B. Sunar and C.K. Koc, Member, IEEE, ”Mastrovito Multiplier for All Trinomials”, IEEE
Transactions on Computers, vol. 48, no. 5, pp.522-527, May 1999.
[8] Irving S. Reed and Xuemin Chen, Error-Control Coding For Data Networks, Kluwer Academic
Publishers, 1999.
[9] Richard E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing
Company, 1983.
[10] Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley Publishing
Company, 1985.
[11] Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edition, Society for
Industrial and Applied Mathematics, 2002.
[12] Sergei V. Fedorenko, Member, IEEE, and Peter V. Trifonov, Student Member, IEEE, ”Finding
Roots of Polynomials Over Finite Fields,” IEEE Transactions on Communications, vol.50,
no.11, Nov. 2002
[13] Sergei V. Fedorenko and P.V. Trifonov, ”On computing the Fast Fourier Transform over finite
fields,” Proceedings of ACCT’02 (Proceedings of Eighth International Workshop on Algebraic
and Combinatorial Coding Theory at Tsarskoe Selo, Russia), pages 108-111, 2002.
[14] P.V. Trifonov and Sergei V. Fedorenko, ”A method for fast computation of the Fourier
transform over a finite field,” Problems of Information Transmission, 39(3):231-238, July-
September 2003.
[15] Christofides’s Algorithm : http://www.cs.gsu.edu/ cscazz/CS4520/ps15.ppt.
[16] Naofumi Takagi, Member, IEEE, Jun-ichi Yoshiki, and Kazuyoshi Takagi, Member, IEEE
Computer Society, ”A Fast Algorithm for Multiplicative Inversion in GF(2m) Using Normal
Basis,” IEEE Transactions On Computers, vol.50, no.5, May 2001.
[17] Some papers about linear equations : http://www.math.uconn.edu/»olshevsk/papers.html.
[18] I. Gohberg and V. Olshevsky, ”The fast generalized Parker-Traub algorithm for inversion of
Vandermonde and related matrices”, Journal of Complexity, vol. 13 , issue 2, June 1997.
[19] Gray Code : http://mathworld.wolfram.com/GrayCode.html.
[20] C. K. Yuen, ”The Separability of Gray Code”, IEEE Transactions on Information Theory,
vol.20, p.668, September 1974.
[21] J. Guajardo and C. Paar, ”Efficient Algorithms for Elliptic Curve Cryptosystems,” Advances
in Cryptology–CRYPTO 97, B.S. Kaliski, ed., pp.342-356, 1997.
[22] A.J. Menezes, Elliptic Curve Public Key Cryptosystems. Boston: Kluwer Academic, 1993.
[23] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, New Tork:
Cambridge Univ. Press, 1994.
[24] A.J. Menezes, Applications of Finite Fields, ed. Boston: Kluwer Academic, 1993.