Introduction to Reed-Solomon Codes[1] Yunghsiang S.Han（韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com
Introduction to Reed-Solomon Codes[1] Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com
Y.S.Han RS Codes 1 Reed-Solomon Codes Construction (1) The first construction of Reed-solomon (RS)codes is simply to evaluate the information polynomials at all the non-zero elements of finite field GF(gm). Let a be a primitive element in GF(gm)and let n=gm-1. .Let u(x)=uo+u+.+u-1 be the information polynomial,where u∈GF(qm)for all0≤i≤k-l. The encoding is defined by the mapping p:u(x)>by (0,v1,…,n-1）=(u(1,u(a,u(a2),,u(an-1). The RS code of length n and dimensional k over GF(gm) is the image under all polynomials in GF(g")[x]of School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 1 Reed-Solomon Codes Construction (1) • The first construction of Reed-solomon (RS) codes is simply to evaluate the information polynomials at all the non-zero elements of finite field GF(q m). • Let α be a primitive element in GF(q m) and let n = q m − 1. • Let u(x) = u0 + u1 x + · · · + uk−1 x k−1 be the information polynomial, where ui ∈ GF(q m) for all 0 ≤ i ≤ k − 1. • The encoding is defined by the mapping ρ : u(x) −→ v by (v0, v1, . . . , vn−1 ) = (u(1), u(α), u(α 2 ), . . . , u(α n−1 )). • The RS code of length n and dimensional k over GF(q m) is the image under all polynomials in GF(q m)[x] of School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 2 degree less than or equal to k-1. The minimum distance of an (n,k)RS code is dmin =n-k+1.It can be proved by follows. Since u(x)has at most k-1 roots,there are at most k-1 zero positions in each nonzero codeword.Hence, dmin >n-k+1.By the Singleton bound, dmin <n-k+1.So dmin =n-k+1. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 2 degree less than or equal to k − 1. • The minimum distance of an (n, k) RS code is dmin = n − k + 1. It can be proved by follows. • Since u(x) has at most k − 1 roots, there are at most k − 1 zero positions in each nonzero codeword. Hence, dmin ≥ n − k + 1. By the Singleton bound, dmin ≤ n − k + 1. So dmin = n − k + 1. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 3 Reed-Solomon Codes Construction(2) The RS codes can be constructed by finding their generator polynomials. In GF(gm),the minimum polynomial for any element ai is simply (x-a). ·Letg(c)=(x-a)(x-ab+1)…(c-ab+2t-l)be the generator polynomial for the RS code.Since the degree of g(x)is exactly equal to 2t,by the BCH bound, n =qm-1,n-k 2t,and dmin >n-k +1. Again,by the Singleton bound,dmin =n-k+1. Considering GF(8)with the primitive polynomial School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 3 Reed-Solomon Codes Construction (2) • The RS codes can be constructed by finding their generator polynomials. • In GF(q m), the minimum polynomial for any element α i is simply (x − α i ). • Let g(x) = (x − α b )(x − α b+1)· · ·(x − α b+2t−1 ) be the generator polynomial for the RS code. Since the degree of g(x) is exactly equal to 2t, by the BCH bound, n = q m − 1, n − k = 2t, and dmin ≥ n − k + 1. • Again, by the Singleton bound, dmin = n − k + 1. • Considering GF(8) with the primitive polynomial School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 23+x+1.Let a be a root of x3+x+1.Then g(z)=(x-a)(a-a2)(c-a3)(x-a4)=x4+a3x3+x2+ax+a3 will generate a(7,3)RS code with dmin =2 x 2+1=5. The number of codewords of this code is 83 =512. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 4 x 3 + x + 1. Let α be a root of x 3 + x + 1. Then g(x) = (x−α)(x−α 2 )(x−α 3 )(x−α 4 ) = x 4 +α 3 x 3 +x 2 +αx+α 3 will generate a (7, 3) RS code with dmin = 2 × 2 + 1 = 5. The number of codewords of this code is 8 3 = 512. School of Electrical Engineering & Intelligentization, Dongguan University of Technology