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
Y.S.Han RS Codes 5 Encoding Reed-Solomon Codes RS codes can be encoded just as any other cyclic code. The systematic encoding process is v()=u(t)a"-k-u(t)z"-k mod g(x) Typically,the code is over GF(2m)for some m.The information symbols ui can be formed by grabbing m bits of data,then interpreting these as the vector representation of the GF(2m)elements. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 5 Encoding Reed-Solomon Codes • RS codes can be encoded just as any other cyclic code. • The systematic encoding process is v(x) = u(x)x n−k − [ u(x)x n−k mod g(x) ] . • Typically, the code is over GF(2m) for some m. The information symbols ui can be formed by grabbing m bits of data, then interpreting these as the vector representation of the GF(2m) elements. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 6 Weight Distributions for RS Codes A code is called maximum distance separable (MDS)code when its dmin is equal to n-k+1.A family of well-known MDS nonbinary codes is Reed-Solomon codes. The dual code of any (n,k)MDS code C is also an (n,n-k)MDS code with dmin =k +1. It can be proved as follows:We need to prove that the (n,n-k)dual code C,which is generated by the parity-check matrix H of C,has dmin =k+1.Let c∈C-have weight w,0<w≤k.Since w≤k,there are at least n-k coordinates of c are zero.Let HIs be an (n-k)x(n-k)submatrix formed by any collection of n-k columns of II in the above coordinates.Since the School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 6 Weight Distributions for RS Codes • A code is called maximum distance separable (MDS) code when its dmin is equal to n − k + 1. A family of well-known MDS nonbinary codes is Reed-Solomon codes. • The dual code of any (n, k) MDS code C is also an (n, n − k) MDS code with dmin = k + 1. • It can be proved as follows: We need to prove that the (n, n − k) dual code C⊥ , which is generated by the parity-check matrix H of C, has dmin = k + 1. Let c ∈ C⊥ have weight w, 0 < w ≤ k. Since w ≤ k, there are at least n − k coordinates of c are zero. Let Hs be an (n − k) × (n − k) submatrix formed by any collection of n − k columns of H in the above coordinates. Since the School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes row rank of IIs is less than n-k and consequently the column rank is also less than n-k.Therefore,we have found n-k columns of II are linear dependent which contradicts to the facts that dmin of C is n-k+1 and then any combination of n-k columns of II is linear independent. Any combination of k symbols of codewords in an MDS code may be used as information symbols in a systematic representation. It can be proved as follows:Let G be the k x n generator matrix of an MDS code C.Then G is the parity check matrix for C.Since C has minimum distance k+1, any combination of k columns of G must be linearly independent.Thus any k x k submatrix of G must be School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 7 row rank of Hs is less than n − k and consequently the column rank is also less than n − k. Therefore, we have found n − k columns of H are linear dependent which contradicts to the facts that dmin of C is n − k + 1 and then any combination of n − k columns of H is linear independent. • Any combination of k symbols of codewords in an MDS code may be used as information symbols in a systematic representation. • It can be proved as follows: Let G be the k × n generator matrix of an MDS code C. Then G is the parity check matrix for C⊥. Since C⊥ has minimum distance k + 1, any combination of k columns of G must be linearly independent . Thus any k × k submatrix of G must be School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 8 nonsingular.So,by row reduction on G,any k xk submatrix can be reduced to the k x k identity matrix. The number of codewords in a q-ary (n,k)MDS code C of weight dmin =n-k+1 is 4=g-(n-+) It can be proved as follows:Select an arbitrary set of k coordinates as information positions for an information u of weight 1.The systemic encoding for these coordinates thus has k-1 zeros in it.Since the minimum distance of the code is n-k+1,all the n-k parity check symbols must be nonzero.Since there are(k”）=(n-k+i) School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 8 nonsingular. So, by row reduction on G, any k × k submatrix can be reduced to the k × k identity matrix. • The number of codewords in a q-ary (n, k) MDS code C of weight dmin = n − k + 1 is An−k+1 = (q−1)( n n − k + 1) . • It can be proved as follows: Select an arbitrary set of k coordinates as information positions for an information u of weight 1. The systemic encoding for these coordinates thus has k − 1 zeros in it. Since the minimum distance of the code is n − k + 1, all the n − k parity check symbols must be nonzero. Since there are ( n k−1 ) = ( n n−k+1) School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han RS Codes 9 different ways of selecting the k-1 zero coordinates and q-1 ways of selecting the nonzero information symbols, A--g-(n-g+) The number of codewords of weight j in a q-qry (n,k) MDS code is j-dmin 4=(C)o-∑-r(: School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han RS Codes 9 different ways of selecting the k − 1 zero coordinates and q − 1 ways of selecting the nonzero information symbols, An−k+1 = (q − 1)( n n − k + 1) . • The number of codewords of weight j in a q-qry (n, k) MDS code is Aj = ( n j ) (q − 1) j−∑ dmin i=0 (−1)i ( j − 1 i ) q j−dmin−i . School of Electrical Engineering & Intelligentization, Dongguan University of Technology