Cyclic Codes Yunghsiang S.Han（韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com
Cyclic Codes Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com
Y.S.Han Cyclic codes Description of Cyclic Codes If the components of an n-tuple v=(vo,v1,...,Un-1)are cyclically shifted i places to the right,the resultant n-tuple would be v）=(n-i,vn-i+1,,vn-l,0,U1,,n-i-1). Cyclically shifting v i places to the right is equivalent to cyclically shifting v n-i places to the left. An (n,k)linear code C is called a cyclic code if every cyclic shift of a code vector in C is also a code vector in C. Code polynomial v(x)of the code vector v is defined as u(x)=0+U1x+…+n-1xn-1. ·v((c)=xv(x)）mod zm+1. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 1 Description of Cyclic Codes • If the components of an n-tuple v = (v0, v1, . . . , vn−1) are cyclically shifted i places to the right, the resultant n-tuple would be v (i) = (vn−i , vn−i+1, . . . , vn−1, v0, v1, . . . , vn−i−1). • Cyclically shifting v i places to the right is equivalent to cyclically shifting v n − i places to the left. • An (n, k) linear code C is called a cyclic code if every cyclic shift of a code vector in C is also a code vector in C. • Code polynomial v(x) of the code vector v is defined as v(x) = v0 + v1 x + · · · + vn−1 x n−1 . • v (i) (x) = x i v(x) mod x n + 1. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes 2 Proof:Multiplying v(x)by x,we obtain x2v()=0x2+v1x+1+…+n--1xn-1++un-1an+i-1. Then we manipulate the equation into the following form: x2v(x)=n-i+n-i+1x+…+n-1xi-1+0x2+. +n-i-1xn-1+vn-i(xn+1)+wn-i+1x(x”+1) +…+vn-1x2-1(xn+1) =q(x)(xn+1)+v@(c), Where q(x)=Un-i+Un-i+1x+...+Un-1xi-1, The nonzero code polynomial of minimum degree in a cyclic code C is unique. Let g(x)=go+gx+...+gr-1x"-1+z"be the nonzero code polynomial of minimum degree in an (n,k)cyclic code C. Then the constant term go must be equal to 1. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 2 Proof: Multiplying v(x) by x i , we obtain x i v(x) = v0 x i + v1 x i+1 + · · · + vn−i−1 x n−1 + · · · + vn−1 x n+i−1 . Then we manipulate the equation into the following form: x i v(x) = vn−i + vn−i+1x + · · · + vn−1 x i−1 + v0 x i + · · · +vn−i−1 x n−1 + vn−i (x n + 1) + vn−i+1x(x n + 1) + · · · + vn−1 x i−1 (x n + 1) = q(x)(x n + 1) + v (i) (x), where q(x) = vn−i + vn−i+1x + · · · + vn−1 x i−1 . • The nonzero code polynomial of minimum degree in a cyclic code C is unique. • Let g(x) = g0 + g1 x + · · · + gr−1 x r−1 + x r be the nonzero code polynomial of minimum degree in an (n, k) cyclic code C. Then the constant term g0 must be equal to 1. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes Proof:Suppose that go =0.Then 9(x)=91x+92x2+·+9,-1x-1+x =x(g1+92x+…+9-1x-2+x-1). If we shift g(x)cyclically n-1 places to the right (or one place to the left),we obtain a nonzero code polynomial, g1+g2+...+gr-x"-2+x"-1,which has a degree less than r.Contradiction. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 3 Proof: Suppose that g0 = 0. Then g(x) = g1 x + g2 x 2 + · · · + gr−1 x r−1 + x r = x(g1 + g2 x + · · · + gr−1 x r−2 + x r−1 ). If we shift g(x) cyclically n − 1 places to the right (or one place to the left), we obtain a nonzero code polynomial, g1 + g2 x + · · · + gr−1 x r−2 + x r−1 , which has a degree less than r. Contradiction. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Cyclic codes A (7,4)Cyclic Code Generated by g(x)=1+x+23 Messages Code Vectors Code Polynomials (0000) 00000000=0·g(x) (1000) 11010001+x+x3=1·g(x) (0100) 0110100x+x2+x4=x·g(x) (1100) 1011100 1+x2+x3+x4=(1+x)·g(x) (0010) 0011010 x2+x3+x5=x2·g(c) (1010) 1110010 1+x+x2+x5=(1+x2)·9(x) (0110) 0101110 x+x3+x4+x5=(x+x2)·g(x) (1110) 1000110 1+x4+x5=(1+x+x2)·g(x) (0001) 0001101 x3+x4+x6=x3·g(c) (1001) 11001011+x+x4+x6=(1+x3)·g(x) (0101) 0111001 x+x2+x3+x6=(x+x3)·g(x) (1101) 1010001 1+x2+x6=(1+x+x3)·g(x) (0011) 0010111x2+x4+x5+x6=(x2+x3)·g(x) (1011) 1111111 1+x+x2+x3+x4+x5+x6=(1+x2+x3)·g(x) (1111) 1001011 1+x3+x5+x6=(1+x+x2+x3)·g(c) School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Cyclic codes 4 A (7, 4) Cyclic Code Generated by g(x) = 1 + x + x 3 Messages Code Vectors Code Polynomials (0 0 0 0) 0 0 0 0 0 0 0 0 = 0 · g(x) (1 0 0 0) 1 1 0 1 0 0 0 1 + x + x 3 = 1 · g(x) (0 1 0 0) 0 1 1 0 1 0 0 x + x 2 + x 4 = x · g(x) (1 1 0 0) 1 0 1 1 1 0 0 1 + x 2 + x 3 + x 4 = (1 + x) · g(x) (0 0 1 0) 0 0 1 1 0 1 0 x 2 + x 3 + x 5 = x 2 · g(x) (1 0 1 0) 1 1 1 0 0 1 0 1 + x + x 2 + x 5 = (1 + x 2 ) · g(x) (0 1 1 0) 0 1 0 1 1 1 0 x + x 3 + x 4 + x 5 = (x + x 2 ) · g(x) (1 1 1 0) 1 0 0 0 1 1 0 1 + x 4 + x 5 = (1 + x + x 2 ) · g(x) (0 0 0 1) 0 0 0 1 1 0 1 x 3 + x 4 + x 6 = x 3 · g(x) (1 0 0 1) 1 1 0 0 1 0 1 1 + x + x 4 + x 6 = (1 + x 3 ) · g(x) (0 1 0 1) 0 1 1 1 0 0 1 x + x 2 + x 3 + x 6 = (x + x 3 ) · g(x) (1 1 0 1) 1 0 1 0 0 0 1 1 + x 2 + x 6 = (1 + x + x 3 ) · g(x) (0 0 1 1) 0 0 1 0 1 1 1 x 2 + x 4 + x 5 + x 6 = (x 2 + x 3 ) · g(x) (1 0 1 1) 1 1 1 1 1 1 1 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 = (1 + x 2 + x 3 ) · g(x) (1 1 1 1) 1 0 0 1 0 1 1 1 + x 3 + x 5 + x 6 = (1 + x + x 2 + x 3 ) · g(x) School of Electrical Engineering & Intelligentization, Dongguan University of Technology