西安电子科技大学：《纠错码》课程教学资源（课件讲义）Decoding BCH/RS Codes

Decoding BCH/RS Codes Yunghsiang S.Han（韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com

Decoding BCH/RS Codes Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com

Y.S.Han Decoding BCH/RS Codes 1 Decoding Procedure The BCH/RS codes decoding has four steps: 1.Syndrome computation 2.Solving the key equation for the error-locator polynomial A(x) 3.Searching error locations given the A(x)polynomial by simply finding the inverse roots 4.(Only nonbinary codes need this step)Determine the error magnitude at each error location by error-evaluator polynomial (x) The decoding procedure can be performed in time or frequency domains. This lecture only considers the decoding procedure in School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 1 Decoding Procedure • The BCH/RS codes decoding has four steps: 1. Syndrome computation 2. Solving the key equation for the error-locator polynomial Λ(x) 3. Searching error locations given the Λ(x) polynomial by simply finding the inverse roots 4. (Only nonbinary codes need this step) Determine the error magnitude at each error location by error-evaluator polynomial Ω(x) • The decoding procedure can be performed in time or frequency domains. • This lecture only considers the decoding procedure in School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 2 time domain.The frequency domain decoding can be found in [1,2]. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 2 time domain. The frequency domain decoding can be found in [1, 2]. School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 3 Syndrome Computation .Let a,a2,.2 be the 2t consecutive roots of the generator polynomial for the BCH/RS code,where a is an element in finite field GF(g")with order n. Let y(z)be the received vector.Then define the syndrome Si,1≤j≤2t,as follows: Sj y(ai)=c(a)+e(ai)=e(ai) n-1 oy (1) U k=1 School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 3 Syndrome Computation • Let α, α2 , . . . , α2t be the 2t consecutive roots of the generator polynomial for the BCH/RS code, where α is an element in finite field GF(q m) with order n. • Let y(x) be the received vector. Then define the syndrome Sj , 1 ≤ j ≤ 2t, as follows: Sj = y(α j ) = c(α j ) + e(α j ) = e(α j ) = n ∑−1 i=0 ei (α j ) i = ∑ v k=1 eik α ikj , (1) School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes where n is the code length and it is assumed that v errors occurred in locations corresponding to time indexes i1,i2,…,iu When n is large one can calculate syndromes by the minimum polynomial for a. Let i(x)be the minimum polynomial for a.That is, j(a)=0.Let y(x)=q(x)oj(x)+rj(x),where ri(x)is the remainder and the degree of ri(z)is less than the degree of ()which is at most m. Sj=y(ai)=q(ai)oj(a)+rj(ai)=rj(aj). For ease of notation we reformulate the syndromes as ∑kX,ior1≤j≤2t, k- School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 4 where n is the code length and it is assumed that v errors occurred in locations corresponding to time indexes i 1, i2, . . . , iv. • When n is large one can calculate syndromes by the minimum polynomial for α j . • Let ϕj (x) be the minimum polynomial for α j . That is, ϕj (α j ) = 0. Let y(x) = q(x)ϕj (x) + rj (x), where rj (x) is the remainder and the degree of rj (x) is less than the degree of ϕj (x), which is at most m. • Sj = y(α j ) = q(α j )ϕj (α j ) + rj (α j ) = rj (α j ). • For ease of notation we reformulate the syndromes as Sj = ∑ v k=1 YkX j k , for 1 ≤ j ≤ 2t, School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 5 where Y eig and Xk=aik. The system of equations for syndromes is S1=YX1+Y2X2+…+Y,X S2=X子+Y2X号+…+YX S3=YiX+Y2X+…+Y,X3 S2t=Yixi+Y2x2+..+Yox2t School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 5 where Yk = eik and Xk = α ik . • The system of equations for syndromes is S1 = Y1X1 + Y2X2 + · · · + YvXv S2 = Y1X2 1 + Y2X2 2 + · · · + YvX2 v S3 = Y1X3 1 + Y2X3 2 + · · · + YvX3 v . . . S2t = Y1X2t 1 + Y2X2t 2 + · · · + YvX2t v . School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 6 Key Equation Recall that the error-locator polynomial is A()=(1-X1-xX2)…1-xX)=A0+∑Aa, where Ao=1. Define the infinite degree syndrome polynomial (though we only know the first 2t coefficients)as 0 S(x)= ∑S+1 j= j=0 k-1 School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 6 Key Equation • Recall that the error-locator polynomial is Λ(x) = (1 − xX1 )(1 − xX2 )· · ·(1 − xXv ) = Λ0 + ∑ v i=1 Λi x i , where Λ0 = 1. • Define the infinite degree syndrome polynomial (though we only know the first 2t coefficients) as S(x) = ∑ ∞ j=0 Sj+1x j = ∑ ∞ j=0 x j ( ∑ v k=1 YkX j+1 k ) School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes YhXk 1-xXk k=1 Define the error-evaluator polynomial as 2(x）)AA()S() ∑KXkΠ1-xX) k= The degree of the error-evaluator polynomial is less than U. Actually we only know the first 2t terms of S(x)such that we have School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 7 = ∑ v k=1 YkXk 1 − xXk . • Define the error-evaluator polynomial as Ω(x) △ = Λ(x)S(x) = ∑ v k=1 YkXk ∏ v j=1 j̸=k (1 − xXj ). • The degree of the error-evaluator polynomial is less than v. • Actually we only know the first 2t terms of S(x) such that we have School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 8 A(x)S(x)=2(x)mod x24. (2) Since the degree of (x)is at most v-1 the terms of A()S(a)from through a2-1 are all zeros. 。Then ∑AkS)-k=0,foru+1≤j≤2t. (3) k=0 The above system of equations is the same as the key equation given previously if we only consider those equations up to j=2v(remember that v<t). Thus,(2)is also known as key equation. Solving key equation to determine the coefficients of the School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 8 Λ(x)S(x) ≡ Ω(x) mod x 2t . (2) • Since the degree of Ω(x) is at most v − 1 the terms of Λ(x)S(x) from x v through x 2t−1 are all zeros. • Then ∑ v k=0 Λk Sj−k = 0, for v + 1 ≤ j ≤ 2t. (3) • The above system of equations is the same as the key equation given previously if we only consider those equations up to j = 2v (remember that v ≤ t). • Thus, (2) is also known as key equation. • Solving key equation to determine the coefficients of the School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han Decoding BCH/RS Codes 9 error-locator polynomial is a hard problem and it will be mentioned later. The key equation becomes A()(1+S(2))=2(2)mod 224+1 (4) if we define the infinite degree syndrome equation as (5) j=1 School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han Decoding BCH/RS Codes 9 error-locator polynomial is a hard problem and it will be mentioned later. • The key equation becomes Λ(x)(1 + S(x)) ≡ Ω(x) mod x 2t+1 (4) if we define the infinite degree syndrome equation as S(x) = ∑ ∞ j=1 Sj x j . (5) School of Electrical Engineering & Intelligentization, Dongguan University of Technology