Y.S.Han Decoding BCH/RS Codes 15 The Euclidean Algorithm [1] Euclidean algorithm is a recursive technology to find the greatest common divisor (GCD)of two numbers or two polynomials. The Euclidean algorithm is as follows.Let a(x)and b(x) represent the two polynomials,which deg [a(x)]=deg [o(x)].Divide a(x)by b(x).If the remainder,r(x),is zero,then GCD d(x)=b(x).If the remainder is not zero,then replace a(x)with b(x), replace b(x)with r(x),and repeat. Considering a simple example,where a(x)=x5+1 and b(x)=z3+1.Then School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 15 The Euclidean Algorithm [1] • Euclidean algorithm is a recursive technology to find the greatest common divisor (GCD) of two numbers or two polynomials. • The Euclidean algorithm is as follows. Let a(x) and b(x) represent the two polynomials, which deg [a(x)] ≥ deg [b(x)]. Divide a(x) by b(x). If the remainder, r(x), is zero, then GCD d(x) = b(x). If the remainder is not zero, then replace a(x) with b(x), replace b(x) with r(x), and repeat. • Considering a simple example, where a(x) = x 5 + 1 and b(x) = x 3 + 1. Then School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 16 x5+1=x2(x3+1)+(x2+1) x3+1=x(ax2+1)+(c+1) x2+1=(x+1)(x+1)+0 Since d(z)divides x5+1 and 23+1 it must also divide x2+1.Since it divides 23+1 and 22+1 it must also divide x+1.Consequently,x+1 d(x). The useful aspect of this process is that,at each iteration,a set of polynomials fi(x),gi(x),and ri(x)are generated such that fi(x)a(x)+gi(x)b(x)=ri(x). (7) A way to obtain fi(x)and gi(x)is as follows. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 16 x 5 + 1 = x 2 (x 3 + 1) + (x 2 + 1) x 3 + 1 = x(x 2 + 1) + (x + 1) x 2 + 1 = (x + 1)(x + 1) + 0 • Since d(x) divides x 5 + 1 and x 3 + 1 it must also divide x 2 + 1. Since it divides x 3 + 1 and x 2 + 1 it must also divide x + 1. Consequently, x + 1 = d(x). • The useful aspect of this process is that, at each iteration, a set of polynomials fi (x), gi (x), and ri (x) are generated such that fi (x)a(x) + gi (x)b(x) = ri (x). (7) • A way to obtain fi (x) and gi (x) is as follows. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 17 Define qi(x)to be the quotient polynomial that is produced by dividing ri-2(x)by ri1(x).Then,for i>1, ri(x)=ri-2-qi(x)ri-1(x) f(x)=f-2-q(c)fi-1(x) 9(c）=9i-2-q(c)9i-1(x), where the initial values are f-1(x)= 90(x)=1 fo(x) =g-1(x)=0 (8) r-1(x) =a(x) ro(x）=b(x). There are two useful properties of the algorithm: School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 17 • Define qi (x) to be the quotient polynomial that is produced by dividing ri−2 (x) by ri−1 (x). Then, for i ≥ 1, ri (x) = ri−2 − qi (x)ri−1 (x) fi (x) = fi−2 − qi (x)fi−1 (x) gi (x) = gi−2 − qi (x)gi−1 (x), where the initial values are f−1 (x) = g0 (x) = 1 f0 (x) = g−1 (x) = 0 r−1 (x) = a(x) r0 (x) = b(x). (8) • There are two useful properties of the algorithm: School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 18 1.deg [ri(x)]deg [ri-1(x)]; 2.deg[gi(x】+deg[ri-i(x】=deg[a(r]. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 18 1. deg [ri (x)] < deg [ri−1 (x)]; 2. deg [gi (x)] + deg [ri−1 (x)] = deg [a(x)]. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 19 The Sugiyama Algorithm for Solving Key Equation [1] The Sugiyama algorithm utilizes Euclidean algorithm to solve the key equation.Hence,the Sugiyama algorithm is also called Euclidean algorithm. 。(7)can be written as gi(x)b(x)=ri(x)mod a(x). Comparing(2)with the above equation,they are equivalent when a(x)=22,b(x)=S(x) 9(c)=Ai(x),r(x)=2(c) The Euclidean algorithm produces a sequence of solutions to the key equation. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 19 The Sugiyama Algorithm for Solving Key Equation [1] • The Sugiyama algorithm utilizes Euclidean algorithm to solve the key equation. Hence, the Sugiyama algorithm is also called Euclidean algorithm. • (7) can be written as gi (x)b(x) ≡ ri (x) mod a(x). • Comparing (2) with the above equation, they are equivalent when a(x) = x 2t , b(x) = S(x) gi (x) = Λi (x), ri (x) = Ωi (x). • The Euclidean algorithm produces a sequence of solutions to the key equation. School of Electrical Engineering & Intelligentization, Dongguan University of Technology