Y.S.Han Decoding BCH/RS Codes 10 Chien Search The next important decoding step is to find the actual error locations X1=ai,X2 ai2,...,Xv=ai. Note that A(x)has roots X11=a-1,X21=a-2,,X1=a-i0. Observe that an error occurs in position i if and only if A(a-i)=0 or 。Then Aat-y=∑Aaa=∑(aa）a k0 School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 10 Chien Search • The next important decoding step is to find the actual error locations X1 = α i1 , X2 = α i2 , . . . , Xv = α iv . • Note that Λ(x) has roots X −1 1 = α −i1 , X−1 2 = α −i2 , . . . , X−1 v = α −iv . • Observe that an error occurs in position i if and only if Λ(α −i ) = 0 or ∑ v k=0 Λk α −ik = 0. • Then Λ(α −(i−1)) = ∑ v k=0 Λk α −ik+k = ∑ v k=0 ( Λk α −ik) α k . School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 11 This suggests that the potential error locations are tested in succession starting with time index n-1. Summing all terms of A(ai)at index i tests to see if A(a-i)= 0. Then to test at index i-1 only requires multiplying the kth term of A(a)by a for all k and summing all terms again. This procedure is repeated until index 0 is reached. The initial value for kth term is Akank This procedure is known as Chien Search. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 11 • This suggests that the potential error locations are tested in succession starting with time index n − 1. Summing all terms of Λ(α −i ) at index i tests to see if Λ(α −i ) = 0. Then to test at index i − 1 only requires multiplying the kth term of Λ(α −i ) by α k for all k and summing all terms again. This procedure is repeated until index 0 is reached. The initial value for kth term is Λk α −nk . This procedure is known as Chien Search. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 12 Forney's Formula For nonbinary BCH or RS codes one still needs to determine the error magnitude for each error location. These values,Y1,Y2,...,Y,can be obtained by utilizing the error-evaluator polynomial.This step is known as Forney's formula. By substituting Xaik into the error-evaluator polynomial we have 2(X1)=YXI1-XX): By taking the formal derivative of A(x)and also School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 12 Forney’s Formula • For nonbinary BCH or RS codes one still needs to determine the error magnitude for each error location. • These values, Y1, Y2, . . . , Yv, can be obtained by utilizing the error-evaluator polynomial. This step is known as Forney’s formula. • By substituting X −1 k = α −ik into the error-evaluator polynomial we have Ω(X −1 k ) = YkXk ∏ v j=1 j̸=k (1 − X −1 k Xj ). • By taking the formal derivative of Λ(x) and also School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 13 evaluating it at x-Xl we have '(X1)=-XΠ1-X%1X) j=1 ≠k Thus the error magnitude Yk is given by 2(xz1) 2(aik)》 (6) '(X) A'(a-ik） Clearly,the above formula can be determined by a search procedure similar to Chien Search. Usually,(x)can be obtained by solving the key School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 13 evaluating it at x = X −1 k we have Λ ′ (X −1 k ) = −Xk ∏ v j=1 j̸=k (1 − X −1 k Xj ) = −1 Yk Ω(X −1 k ). • Thus the error magnitude Yk is given by Yk = − Ω(X −1 k ) Λ′ (X −1 k ) = − Ω(α −ik ) Λ′ (α−ik ) . (6) • Clearly, the above formula can be determined by a search procedure similar to Chien Search. • Usually, Ω(x) can be obtained by solving the key School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Decoding BCH/RS Codes 14 equation. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Decoding BCH/RS Codes 14 equation. School of Electrical Engineering & Intelligentization, Dongguan University of Technology