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) 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 =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<=i1 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