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