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