# Cyclic codes

Cyclic.txt — Plain Text, 10 KB (10394 bytes)

## File contents

Cyclic Codes ~~~~~~~~~~~~ A cyclic code is a linear code with the property that whenever c=(c0,...c_{n-1}) is a codeword so is (c1,c2,...,c_{n-1},c0) and as a consequence any other cyclic shift of c. A simple example of a cyclic codes is the parity check codes (sum mod2 of bits =0 or =1) for the parity does not change upon a cyclic shift or indeed any permutation of the bits. Another example is the Reed-Solomon code with the canonical choice of test positions alpha^i, i=0..q-2 with alpha a primitive element of GF(q). This is because if c=(c_0..c_{q-2}) is a codeword via polynomial f, i.e., c_i = f(alpha^i), then (c_1,...,c_{q-2},c_0) is also a codeword via g(X)=f(alpha*X). Notice that alpha^(q-1)=1. Just as in the case of the alternative presentation of the Reed-Solomon code we will consider codewords as polynomials, by using the symbols as coefficients: the codeword c=(c_0,...c_{n-1}) is regarded as the polynomial c(X) = c_0+c_1*X+...c_{n-1}*X^{n-1}. In conjunction with cyclic codes (of length n) we will need the ring F[X]/(X^n-1) whose elements can be seen as polynomials over the field F of degree at most n-1. Multiplication in this ring is defined by setting X^n equal to 1. Thus, for example, if n=3 then, in F[X]/(X^3-1), we have (X^2+X+1)(X^2-2X-1) = X^4-2X^3-X^2+X^3-2X^2-X+X^2-2X-1 = X^4-X^3-2X^2-1 = X-1-2X^2-1 = -2X^2+X-2 Notice that multiplication with X in F[X]/(X^n-1) is cyclic shift, albeit in reverse direction: X*(X^2+2X+3) = X^3+2X^2+3X = 2X^2+3X+1 X*(3,2,1) = (1,3,2) A subset I of F[X]/(X^n-1) is called an ideal if it is closed under addition and under multiplication with arbitrary polynomials: p,q:I => p+q:I and p:I and q:F[X]/(X^n-1) => pq:I. NB this definition is completely standard and good for any ring. E.g. ideals in Z are precisely the sets {0} and the multiples of numbers, e.g. the multiples of 7. Proposition: A subset I of F[X]/(X^n-1) is an ideal if and only if it is a cyclic code. Proof: Let I b e an ideal. It is thus a set of polynomials of degree at most n. It is closed under addition and (in particular) scalar multiplication thus a linear code. Moreover, it is (in particular) closed by multiplication with X which means that if (c0,...,c_n-1):I then also (c_(n-1),c0,c1,...,c_(n-2)):I because this is the coefficient list of X*c. Thus, I is a cyclic code. Conversely, if C is a cyclic code then C is closed under addition, multiplication with scalars (since it is a linear code) and under multiplication with X (by cyclicity). Thus, again by linearity, it is closed under multiplication with arbitrary polynomials. E.g. if c is in C then by cyclicity X*c and X^2*C are in C so by linearity (2+3X+4X^2)*c : C. Proposition: For each cyclic code C of length n there exists a polynomial g:F[X] such that c:C iff c=pg in F[X]/(X^n-1) for some polynomial p, ie C comprises the multiples of g. Conversely, any set of polynomials {pg | p:F[X]/(X^n-1)} forms a cyclic code. Furthermore, such polynomial g can be chosen as a divisor of X^n-1. Proof: Choose g a polynomial in C of minimal degree but different from 0. If h:C then we can write h=qg+r with deg(r)<g by polynomial division. Since the code is linear we must have r=qg-r : C so r=0 since g was chosen of minimal degree. The converse is obvious because the set of multiples of a polynomial g forms an ideal. Now write X^n-1 = qg+r with deg(r)<deg(g)<n in F[X]. In F[X]/(X^n-1) we thus have that r is a code word, hence a multiple of g, hence 0. So, in F[X] we have that X^n-1 = qg. QED The polynomial g (or any polynomial with its properties) is called *generator polynomial of C. We have seen that any cyclic code has a generator polynomial which is a divisor of X^n-1. Example: Let us find all cyclic codes of length 4 over F = GF(2). We have X^4-1 = (X+1)^4, so the divisors of X^4-1 are 1, X+1, (X+1)^2, (X+1)^3, (X+1)^4. The corresponding cyclic codes are GF(2)^4, the parity code (even parity), {0000,1010,0101,1111}, {0000,1111}, and {0000}. Notice that the odd-parity code is not linear. Proposition: Let C be a cyclic code of length n with generator polynomial g or degree r. Then dim(C) = n - r and (g Xg X^2g ... X^{n-r-1}g) is a generator matrix for C where X^ig stands for the column vector comprising the coefficients of X^ig). Proof: Code words are in 1-1 corresponds with polynomials of degree n-r-1 via p |-> pg. These polynomials form a vector space of dimension n-r and the above matrix describes the passage from p to pg. Proposition: Let C be a cyclic code of length n with generator polynomial g and h such that X^n-1 = hg (see above). Then c:C iff hc=0 in F[X]/(X^n-1). Proof: If hc=0 then hc is a multiple of X^n-1 in F[X] so hc=p(X^n-1)=phg so c=pg in F[X] and hence in F[X]/(X^n-1). Conversely, if c=pg then hc=hpg=0 in F[X]/(X^n-1). The polynomial h such that hg=X^n-1 is called *control polynomial* of C. For a polynomial p of degree <n let rev(p) stand for the polynomial given by the list of coefficients of p reversed, ie if p=p_0 + p_1X + ... p_{n-1}X^{n-1} then rev(p) = p_0 X^{n-1} + ... + p_{n-2} X + p_{n-1}. Lemma: Let p, q be polynomials of degree <n. If pq=0 in F[X]/(X^n-1) then rev(p)^T q = 0 when viewed as column vectors. Proof: Let (p_0..p_(n-1)) and (q_0..q_(n-1)) be the coefficients of p,q, resp. The coefficient of X^{n-1} in pq is p_0q_{n-1}+p_1q_{n-1}+...+p_{n-1}q_0. Notice that even though X^n = 1 no other products of monomials can contribute here because no product of monomials has order higher than 2n-2 which after reduction mod X^n-1 has degree < n-1. Thus, the coefficient of the X^{n-1} in pq is indeed p^T rev(q) and =0 if pq=0. Proposition: Let C be a cyclic code of length n with generator polynomial g and control polynomial h. Then a control matrix of C is given by H= ( rev(h)^T rev(X h)^T ... rev (X^{n-1-r}h)^T ) Proof: By the Lemma we have Hc = 0 for any codeword but H has dim(C)=n-r linearly independent rows thus is a control matrix. Example: The parity check code of length 4 over F=GF(2) has generator polynomial g=X+1 and control polynomial h=X^3+X^2+X+1. Notice that gh=X^4+1 (=X^4-1). Generator and control matrices are thus (100) G = (110) H = (1 1 1 1) (011) (001) Up to a permutation of the bits the [7,4,3] Hamming code happens to be a cyclic code over GF(2) with generator polynomial g=X^3+X+1. The control polynomial is h = X^4 + X^2 + X + 1. Note that gh=X^7+1. The ensuing matrices are (1000) (1100) (0110) (1011100) G = (1011) H = (0101110) (0101) (0010111) (0010) (0001) Notice how the columns of H are the binary numbers from 1 to 7. Proposition: The dual code of a cyclic code is again cyclic. If C has generator polynomial g and control polynomial h then rev(h) is a generator polynomial of the dual of C and rev(g) the corresponding control polynomial. Proof: This is direct from the above characterisation of generator and control matrices and the already established facts about generator and control matrices of dual codes. Theorem (BCH-bound): Let C be a cyclic code of length n over GF(q) with generator polynomial g. Suppose that gcd(n,q)=1 and let alpha be a primitive n-th root of unity over GF(q). That is to say alpha^n=1 and 1,alpha,alpha^2,...,alpha^{n-1} are pairwise distinct. If b b+1 b+d-2 g(a ) = g(a ) = ... = g(a ) = 0 for some b>=0 and 2<=d<=n then C has a minimal distance of at least d. Example: n=q-1 and alpha a primitive element of GF(q). Take b=1, d=q-m, g=(X-alpha)*...*(X-alpha^{q-1-m}). One then obtains the RS(q,m) code of minimal distance q-m. Proof of the BCH bound: If c:C then c=pg mod X^n-1 so c=pg+q(X^n-1). So, each of the elements alpha^{j} for j=b..b+d-2 is a zero of c as it is a zero of the right-hand side. Now, if c=(c_0 ... c_{n-1})^T then the fact that c(beta)=0 can be written as (1 beta beta^2 ... beta^{n-1}) c = 0 Thus, for each codeword c we have Hc=0 when H is the following matrix: ( 1 alpha^b alpha^2b ... alpha^{(n-1)b} ) | 1 alpha^{b+1} alpha^{2(b+1)} ... alpha^{(n-1)(b+1)} | | ... ... ... ... ... | ( 1 alpha^{b+d-2} alpha^(2(n+d-2)} ... alpha^{(n-1)(b+d-2)}) We show now that any d-1 columns of this matrix are linearly independent. This will yield the result via the Theorem on t-independence. So, let us pick any d-1 columns and let x_1^b .. x_{d-1}^b be the first entries of those columns (all the x_i are powers of alpha and pairwise different since alpha is a primitive root of unity). We consider the determinant made from those columns: | x_1^b ... x_{d-1}^b | |1 1 | | x_1^{b+1} ... x_{d-1}^{b+1} | = Gamma * |x_1 ... x_{d-1}| | ... ... ... | |.. .. | | x_1^{b+d-2} ... x_{d-1}^{b+d-2}| |x_1^{d-2}..x_{d-1}^{d-2}| where Gamma = x_1 * ... * x_{d-1} =/=0. The second determinant, however, is the well-known Vandermonde-determinant which is nonzero too. So the selected columns are linearly independent as required. Thus the code C'={c|Hc=0} has minimal distance at least d and C being a subset then shares this property. Codes as in the statement of the theorem are called BCH-codes (so named after their inventors Bose, Ray-Chaudhuri, and Hocquenghem). QED Supplement (Vandermonde determinant): For x_1..x_n in some field the Vandermonde determinant is given by V(x_1..x_n) = |1 .. 1 | |x_1 .. x_n| |.. .. ... | |x_1^n..x_n^n| One has V(x1..xn) = - prod_{1<=i<j<=n}(x_j-x_i). Proof: by induction on n. The base case is obvious. Otherwise, consider x_1 as an indeterminate and x_2..x_n as constants and expand the determinant as a polynomial P(x_1) of degree n in x_1. One has P(x_j)=0 for j>1 because the resulting determinant has two identical rows. Thus, P(x_1)=(x_1-x_2)*...*(x_1-x_n)*Q, where Q depends only on x_2..x_n and is the coefficient in V(x1..xn) of x_1^n. Expanding the determinant along the first column, we see that this coefficient is (-1)^(n+1) * V(x2..xn). Now, V(x1..xn) = (x1-x2)*...*(x1-xn)*(-1)^(n+1)*V(x2..xn) = (x2-x1)*...*(xn-x1)*prod(2<=i<j<=n)(x_j-x_i) = prod_{1<=i<j<=n}(x_j-x_i).

Document Actions