Y.S.Han Cyclic codes Consider the polynomial xg(x),22g(x),...,xm--1g(x). Clearly,they are cyclic shifts of g(x)and hence code polynomials in C.Since C is linear,a linear combination of g(x),xg(x),...,xn-r-1g(x), v(x）=uog(r)+u1xg(）+…+n-r-1an-r-1g(x) =(o+w1x+·+n-r-1xn-T-1)g(x), is also a code polynomial where ui∈{0，l}. Let g(z)=1+gx+...+gr-1x"-1+x"be the nonzero code polynomial of minimum degree in an (n,k)cyclic code C.A binary polynomial of degree n-1 or less is a code polynomial if and only if it is a multiple of g(x). Proof:Let v(x)be a binary polynomial of degree n-1 or less. Suppose that v(x)is a multiple of g(x).Then v(x)=(ao+az+...+an-r-1x"-r-1)g(x) School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 5 • Consider the polynomial xg(x), x2 g(x), . . . , xn−r−1 g(x). Clearly, they are cyclic shifts of g(x) and hence code polynomials in C. Since C is linear, a linear combination of g(x), xg(x), . . . , xn−r−1 g(x), v(x) = u0 g(x) + u1 xg(x) + · · · + un−r−1 x n−r−1 g(x) = (u0 + u1 x + · · · + un−r−1 x n−r−1 )g(x), is also a code polynomial where ui ∈ {0, 1}. • Let g(x) = 1 + g1 x + · · · + gr−1 x r−1 + x r be the nonzero code polynomial of minimum degree in an (n, k) cyclic code C. A binary polynomial of degree n − 1 or less is a code polynomial if and only if it is a multiple of g(x). Proof: Let v(x) be a binary polynomial of degree n − 1 or less. Suppose that v(x) is a multiple of g(x). Then v(x) = (a0 + a1 x + · · · + an−r−1 x n−r−1 )g(x) School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes 6 aog(x)+axg(x)+...+an-r-1x"-r-1g(x). Since v(x)is a linear combination of the code polynomials, g(x),xg(x),...,"--1g(x),it is a code polynomial in C. Now let v(x)be a code polynomial in C.Dividing v(x)by g(x),we obtain v(x)=a(x)g(z)+b(x), where the degree of b(x)is less than the degree of g(z).Since v(x)and a(x)g(x)are code polynomials,b(x)is also a code polynomial.Suppose b(x)0.Then b(x)is a code polynomial with less degree than that of g(x).Contradiction. The number of binary polynomials of degree n-1 or less that are multiples of g(x)is 2m-r. There are total of 2 code polynomials in C,2"-=2%,i.e., r=n-k. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 6 = a0 g(x) + a1 xg(x) + · · · + an−r−1 x n−r−1 g(x). Since v(x) is a linear combination of the code polynomials, g(x), xg(x), . . . , xn−r−1 g(x), it is a code polynomial in C. Now let v(x) be a code polynomial in C. Dividing v(x) by g(x), we obtain v(x) = a(x)g(x) + b(x), where the degree of b(x) is less than the degree of g(x). Since v(x) and a(x)g(x) are code polynomials, b(x) is also a code polynomial. Suppose b(x) ̸= 0. Then b(x) is a code polynomial with less degree than that of g(x). Contradiction. • The number of binary polynomials of degree n − 1 or less that are multiples of g(x) is 2 n−r . • There are total of 2 k code polynomials in C, 2 n−r = 2k , i.e., r = n − k. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes The polynomial g(x)is called the generator polynomial of the code. The degree of g(x)is equal to the number of parity-check digits of the code. The generator polynomial g(x)of an (n,k)cyclic code is a factor of x"+1. Proof:We have xg(x)=(n+1)+g(c). Since g(k)()is the code polynomial obtained by shifting g(x) to the right cyclically k times,g()is a multiple of g(). Hence, 2n+1={xk+a(x)}g(z). If g(x)is a polynomial of degree n-k and is a factor of x"+1, then g(x)generates an (n,k)cyclic code. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 7 • The polynomial g(x) is called the generator polynomial of the code. • The degree of g(x) is equal to the number of parity-check digits of the code. • The generator polynomial g(x) of an (n, k) cyclic code is a factor of x n + 1. Proof: We have x k g(x) = (x n + 1) + g (k) (x). Since g (k) (x) is the code polynomial obtained by shifting g(x) to the right cyclically k times, g (k) (x) is a multiple of g(x). Hence, x n + 1 = {x k + a(x)}g(x). • If g(x) is a polynomial of degree n − k and is a factor of x n + 1, then g(x) generates an (n, k) cyclic code. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes 8 Proof:A linear combination of g(),xg(a),...g(), v(x)=aog(x)+alzg(x)+...+ak-1xk-1g(z) =(a0+a1x+·+ak-1x-1)g(x), is a polynomial of degree n-1 or less and is a multiple of g(x). There are a total of 2%such polynomial and they form an (n,k) linear code. Let v(x)=vo +v12+...+Un-1x"-1 be a code polynomial in this code.We have xv(c)=0x+u1x2+…+n-1x” =vn-1(x”+1)+(n-1+0x+…+vn-2xn-1) =vn-1(xn+1)+v1(c). Since both xu(x)and x"+1 are divisible by g(a),v(1)must be divisible by g().Hence,v(1)(x)is a code polynomial and the code generated by g()is a cyclic code. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 8 Proof: A linear combination of g(x), xg(x), . . . , xk−1 g(x), v(x) = a0 g(x) + a1 xg(x) + · · · + ak−1 x k−1 g(x) = (a0 + a1 x + · · · + ak−1 x k−1 )g(x), is a polynomial of degree n − 1 or less and is a multiple of g(x). There are a total of 2 k such polynomial and they form an (n, k) linear code. Let v(x) = v0 + v1 x + · · · + vn−1 x n−1 be a code polynomial in this code. We have xv(x) = v0 x + v1 x 2 + · · · + vn−1 x n = vn−1(x n + 1) + (vn−1 + v0 x + · · · + vn−2 x n−1 ) = vn−1 (x n + 1) + v (1)(x). Since both xv(x) and x n + 1 are divisible by g(x), v (1) must be divisible by g(x). Hence, v (1)(x) is a code polynomial and the code generated by g(x) is a cyclic code. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes Suppose that the message to be encoded is u=(uo,u1,...,uk-1).Then xn-ku(c)=uoxn-k+u1xn-k+1+…十uk-1xn-1. Dividing z-ku(x)by g(x),we have x"-ku(x)=a(x)g(z)+b(x). Since the degree of g(x)is n-k,the degree of b(x)must be n-k-1 or less.Then b(x)+x"-ku(x)=a(x)g(x) is a multiple of g(x)and therefore it is a code polynomial. b(c）+xn-u(c）=b0+b1x+…+bn-k-1xn-k-1 +uoxn-k+u1x”-k+1+…+-1xn-1 School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 9 • Suppose that the message to be encoded is u = (u0, u1, . . . , uk−1). Then x n−k u(x) = u0 x n−k + u1 x n−k+1 + · · · + uk−1 x n−1 . Dividing x n−k u(x) by g(x), we have x n−k u(x) = a(x)g(x) + b(x). Since the degree of g(x) is n − k, the degree of b(x) must be n − k − 1 or less. Then b(x) + x n−k u(x) = a(x)g(x) is a multiple of g(x) and therefore it is a code polynomial. b(x) + x n−k u(x) = b0 + b1 x + · · · + bn−k−1 x n−k−1 +u0 x n−k + u1 x n−k+1 + · · · + uk−1 x n−1 School of Electrical Engineering & Intelligentization, Dongguan University of Technology