Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Cyclic codes


Inhaltsbereich

Cyclic codes

Plain Text icon 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


Funktionsleiste