Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

24.7 Cyclic Codes

Cyclic codes are a very important class of codes. In the next two sections, we’ll meet two of the most useful examples of these codes. In this section, we describe the general framework.

A code C $C$ is called cyclic if

(c 1, c 2, \dots, c n) \in C implies (c n, c 1, c 2, \dots, c n - 1) \in C .

$(c_{1}, c_{2}, \dots, c_{n}) \in C implies (c_{n}, c_{1}, c_{2}, \dots, c_{n - 1}) \in C .$

For example, if (1, 1, 0, 1) $(1, 1, 0, 1)$ is in a cyclic code, then so is (1, 1, 1, 0) $(1, 1, 1, 0)$ . Applying the definition two more times, we see that (0, 1, 1, 1) $(0, 1, 1, 1)$ and (1, 0, 1, 1) $(1, 0, 1, 1)$ are also codewords, so all cyclic permutations of the codeword are codewords. This might seem to be a strange condition for a code to satisfy. After all, it would seem to be rather irrelevant that, for a given codeword, all of its cyclic shifts are still codewords. The point is that cyclic codes have a lot of structure, which makes them easier to study. In the case of BCH codes (see Section 24.8), this structure yields an efficient decoding algorithm.

Let’s start with an example. Consider the binary matrix

G = ⎛ ⎝ ⎜ 100010101110111011001 ⎞ ⎠ ⎟ .

$G = (\begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{array}) .$

The rows of G $G$ generate a three-dimensional subspace of seven-dimensional binary space. In fact, in this case, the cyclic shifts of the first row give all the nonzero codewords:

G = {(0, 0, 0, 0, 0, 0, 0), (1, 0, 1, 1, 1, 0, 0), (0, 1, 0, 1, 1, 1, 0), (0, 0, 1, 0, 1, 1, 1), (1, 0, 0, 1, 0, 1, 1), (1, 1, 0, 0, 1, 0, 1), (1, 1, 1, 0, 0, 1, 0), (0, 1, 1, 1, 0, 0, 1)} .

$\begin{array}{rcl} G = {(0, 0, 0, 0, 0, 0, 0), (1, 0, 1, 1, 1, 0, 0), (0, 1, 0, 1, 1, 1, 0), (0, 0, 1, 0, 1, 1, 1), \\ (1, 0, 0, 1, 0, 1, 1), (1, 1, 0, 0, 1, 0, 1), (1, 1, 1, 0, 0, 1, 0), (0, 1, 1, 1, 0, 0, 1)} . \end{array}$

Clearly the minimum weight is 4, so we have a cyclic [7, 3, 4] code.

We now show an algebraic way to obtain this code. Let Z2[X] $Z_{2} [X]$ denote polynomials in X $X$ with coefficients mod 2, and let Z2[X]/(X7−1) $Z_{2} [X] / (X^{7} - 1)$ denote these polynomials mod (X7−1) $(X^{7} - 1)$ . For a detailed description of what this means, see Section 3.11. For the present, it suffices to say that working mod X7−1 $X^{7} - 1$ means we are working with polynomials of degree less than 7. Whenever we have a polynomial of degree 7 or higher, we divide by X7−1 $X^{7} - 1$ and take the remainder.

Let g(X)=1+X2+X3+X4 $g (X) = 1 + X^{2} + X^{3} + X^{4}$ . Consider all products

g (X) f (X) = a 0 + a 1 X + \dots + a 6 X 6

$g (X) f (X) = a_{0} + a_{1} X + \dots + a_{6} X^{6}$

with f(X) $f (X)$ of degree ≤2 $\leq 2$ . Write the coefficients of the product as a vector (a0, …, a6) $(a_{0}, \dots, a_{6})$ . For example, g(X)⋅1 $g (X) \cdot 1$ yields (1, 0, 1, 1, 1, 0, 0) $(1, 0, 1, 1, 1, 0, 0)$ , which is the top row of G $G$ . Similarly, g(X)X $g (X) X$ yields the second row of G $G$ and g(X)X2 $g (X) X^{2}$ yields the third row of G $G$ . Also, g(X)(1+X2) $g (X) (1 + X^{2})$ yields (1, 0, 0, 1, 0, 1, 1) $(1, 0, 0, 1, 0, 1, 1)$ , which is the sum of the first and third rows of G $G$ . In this way, we obtain all the codewords of our code.

We obtained this code by considering products g(X)f(X) $g (X) f (X)$ with deg(f)≤2 $deg (f) \leq 2$ . We could also work with f(X) $f (X)$ of arbitrary degree and obtain the same code, as long as we work mod (X7−1) $(X^{7} - 1)$ . Note that g(X)(X3+X2+1)=X7−1 (mod 2) $g (X) (X^{3} + X^{2} + 1) = X^{7} - 1 (m o d 2)$ . Divide X3+X2+1 $X^{3} + X^{2} + 1$ into f(X) $f (X)$ :

f (X) = (X 3 + X 2 + 1) q (X) + f 1 (X),

$f (X) = (X^{3} + X^{2} + 1) q (X) + f_{1} (X),$

with deg(f1)≤2 $deg (f_{1}) \leq 2$ . Then

g (X) f (X) = g (X) (X 3 + X 2 + 1) q (X) + g (X) f 1 (X) = (X 7 - 1) q (X) + g (X) f 1 (X) \equiv g (X) f 1 (X) mod (X 7 - 1) .

$\begin{matrix} g (X) f (X) = g (X) (X^{3} + X^{2} + 1) q (X) + g (X) f_{1} (X) \\ = (X^{7} - 1) q (X) + g (X) f_{1} (X) \equiv g (X) f_{1} (X) mod (X^{7} - 1) . \end{matrix}$

Therefore, g(X)f1(X) $g (X) f_{1} (X)$ gives the same codeword as g(X)f(X) $g (X) f (X)$ , so we may restrict to working with polynomials of degree at most two, as claimed.

Why is the code cyclic? Start with the vector for g(X) $g (X)$ . The vectors for g(X)X $g (X) X$ and g(X)X2 $g (X) X^{2}$ are cyclic shifts of the one for g(X) $g (X)$ by one place and by two places, respectively. What happens if we multiply by X3 $X^{3}$ ? We obtain a polynomial of degree 7, so we divide by X7−1 $X^{7} - 1$ and take the remainder:

g (X) X 3 = X 3 + X 5 + X 6 + X 7 = (X 7 - 1) (1) + (1 + X 3 + X 5 + X 6) .

$g (X) X^{3} = X^{3} + X^{5} + X^{6} + X^{7} = (X^{7} - 1) (1) + (1 + X^{3} + X^{5} + X^{6}) .$

The remainder yields the vector (1, 0, 0, 1, 0, 1, 1) $(1, 0, 0, 1, 0, 1, 1)$ . This is the cyclic shift by three places of the vector for g(X) $g (X)$ .

A similar calculation for j=4, 5, 6 $j = 4, 5, 6$ shows that the vector for g(X)Xj $g (X) X^{j}$ yields the shift by j $j$ places of the vector for g(X) $g (X)$ . In fact, this is a general phenomenon. If q(X)=a0+a1X+⋯+a6X6 $q (X) = a_{0} + a_{1} X + \dots + a_{6} X^{6}$ is a polynomial, then

q (X) X = = a 0 X + a 1 X 2 + \dots + a 6 X 7 a 6 (X 7 - 1) + a 6 + a 0 X + a 1 X 2 + \dots + a 5 X 6 .

$\begin{array}{rcl} q (X) X & = & a_{0} X + a_{1} X^{2} + \dots + a_{6} X^{7} \\ = & a_{6} (X^{7} - 1) + a_{6} + a_{0} X + a_{1} X^{2} + \dots + a_{5} X^{6} . \end{array}$

The remainder is a6+a0X+a1X2+⋯+a5X6 $a_{6} + a_{0} X + a_{1} X^{2} + \dots + a_{5} X^{6}$ , which corresponds to the vector (a6, a0, …, a5) $(a_{6}, a_{0}, \dots, a_{5})$ . Therefore, multiplying by X $X$ and reducing mod X7−1 $X^{7} - 1$ corresponds to a cyclic shift by one place of the corresponding vector. Repeating this j $j$ times shows that multiplying by Xj $X^{j}$ corresponds to shifting by j $j$ places.

We now describe the general situation. Let F $F$ be a finite field. For a treatment of finite fields, see Section 3.11. For the present purposes, you may think of F $F$ as being the integers mod p $p$ , where p $p$ is a prime number, since this is an example of a finite field. For example, you could take F=Z2={0, 1} $F = Z_{2} = {0, 1}$ , the integers mod 2. Let F[X] $F [X]$ denote polynomials in X $X$ with coefficients in F $F$ . Choose a positive integer n $n$ . We’ll work in F[X]/(Xn−1) $F [X] / (X^{n} - 1)$ , which denotes the elements of F[X] $F [X]$ mod (Xn−1) $(X^{n} - 1)$ . This means we’re working with polynomials of degree less than n $n$ . Whenever we encounter a polynomial of degree ≥n $\geq n$ , we divide by Xn−1 $X^{n} - 1$ and take the remainder. Let g(X) $g (X)$ be a polynomial in F[X] $F [X]$ . Consider the set of polynomials

m (X) = g (X) f (X) mod (X n - 1),

$m (X) = g (X) f (X) mod (X^{n} - 1),$

where f(X) $f (X)$ runs through all polynomials in F[X] $F [X]$ (we only need to consider f(X) $f (X)$ with degree less than n $n$ , since higher-degree polynomials can be reduced mod Xn−1 $X^{n} - 1$ ). Write

m (X) = a 0 + a 1 X + \dots + a n - 1 X n - 1 .

$m (X) = a_{0} + a_{1} X + \dots + a_{n - 1} X^{n - 1} .$

The coefficients give us the n $n$ -dimensional vector (a0, …, an−1) $(a_{0}, \dots, a_{n - 1})$ . The set of all such coefficients forms a subspace C $C$ of n $n$ -dimensional space Fn $F^{n}$ . Then C $C$ is a code.

If m(X)=g(X)f(X) mod (Xn−1) $m (X) = g (X) f (X) mod (X^{n} - 1)$ is any such polynomial, and s(X) $s (X)$ is another polynomial, then m(X)s(X)=g(X)f(X)s(X) mod (Xn−1) $m (X) s (X) = g (X) f (X) s (X) mod (X^{n} - 1)$ is the multiple of g(X) $g (X)$ by the polynomial f(X)s(X) $f (X) s (X)$ . Therefore, it yields an element of the code C $C$ . In particular, multiplication by X $X$ and reducing mod Xn−1 $X^{n} - 1$ corresponds to a codeword that is a cyclic shift of the original codeword, as above. Therefore, C $C$ is cyclic.

The following theorem gives the general description of cyclic codes.

Theorem

Let C $C$ be a cyclic code of length n $n$ over a finite field F $F$ . To each codeword (a0, …, an−1)∈C $(a_{0}, \dots, a_{n - 1}) \in C$ , associate the polynomial a0+a1X+⋯+an−1Xn−1 $a_{0} + a_{1} X + \dots + a_{n - 1} X^{n - 1}$ in F[X] $F [X]$ . Among all the nonzero polynomials obtained from C $C$ in this way, let g(X) $g (X)$ have the smallest degree. By dividing by its highest coefficient, we may assume that the highest nonzero coefficient of g(X) $g (X)$ is 1. The polynomial g(X) $g (X)$ is called the generating polynomial for C $C$ . Then

g(X) $g (X)$ is uniquely determined by C $C$ .
g(X) $g (X)$ is a divisor of Xn−1 $X^{n} - 1$ .
C $C$ is exactly the set of coefficients of the polynomials of the form g(X)f(X) $g (X) f (X)$ with deg(f)≤n−1−deg(g) $deg (f) \leq n - 1 - deg (g)$ .
Write Xn−1=g(X)h(X) $X^{n} - 1 = g (X) h (X)$ . Then m(X)∈F[X]/(Xn−1) $m (X) \in F [X] / (X^{n} - 1)$ corresponds to an element of C $C$ if and only if h(X)m(X)≡0 mod (Xn−1) $h (X) m (X) \equiv 0 m o d (X^{n} - 1)$ .

Proof.

If g1(X) $g_{1} (X)$ is another such polynomial, then g(X) $g (X)$ and g1(X) $g_{1} (X)$ have the same degree and have highest nonzero coefficient equal to 1. Therefore, g(X)−g1(X) $g (X) - g_{1} (X)$ has lower degree and still corresponds to a codeword, since C $C$ is closed under subtraction. Since g(X) $g (X)$ had the smallest degree among nonzero polynomials corresponding to codewords, g(X)−g1(X) $g (X) - g_{1} (X)$ must be 0, which means that g1(X)=g(X) $g_{1} (X) = g (X)$ . Therefore, g(X) $g (X)$ is unique.
Divide g(X) $g (X)$ into Xn−1 $X^{n} - 1$ :

$X n - 1 = g (X) h (X) + r (X)$ $X^{n} - 1 = g (X) h (X) + r (X)$

for some polynomials h(X) $h (X)$ and r(X) $r (X)$ , with deg(r)tdeg(g) $deg (r) t deg (g)$ . This means that

$- r (X) \equiv g (X) h (X) m o d (X n - 1) .$ $- r (X) \equiv g (X) h (X) m o d (X^{n} - 1) .$

As explained previously, multiplying g(X) $g (X)$ by powers of X $X$ corresponds to cyclic shifts of the codeword associated to g(X) $g (X)$ . Since C $C$ is assumed to be cyclic, the polynomials g(X)Xj mod (Xn−1) $g (X) X^{j} m o d (X^{n} - 1)$ for j=0, 1, 2, … $j = 0, 1, 2, \dots$ therefore correspond to codewords; call them c0, c1, c2, … $c_{0}, c_{1}, c_{2}, \dots$ . Write h(X)=b0+b1X+⋯+bkXk $h (X) = b_{0} + b_{1} X + \dots + b_{k} X^{k}$ . Then g(X)h(X) $g (X) h (X)$ corresponds to the linear combination

$b 0 c 0 + b 1 c 1 + \dots + b k c k .$ $b_{0} c_{0} + b_{1} c_{1} + \dots + b_{k} c_{k} .$

Since each bi $b_{i}$ is in F $F$ and each ci $c_{i}$ is in C $C$ , we have a linear combination of elements of C $C$ . But C $C$ is a vector subspace of n $n$ -dimensional space Fn $F^{n}$ . Therefore, this linear combination is in C $C$ . This means that r(X) $r (X)$ , which is g(X)h(X) mod (Xn−1) $g (X) h (X) mod (X^{n} - 1)$ , corresponds to a codeword. But deg(r)tdeg(g) $deg (r) t deg (g)$ , which is the minimal degree of a polynomial corresponding to a nonzero codeword in C $C$ . Therefore, r(X)=0 $r (X) = 0$ . Consequently Xn−1=g(X)h(X) $X^{n} - 1 = g (X) h (X)$ , so g(X) $g (X)$ is a divisor of Xn−1 $X^{n} - 1$ .
Let m(X) $m (X)$ correspond to an element of C $C$ . Divide g(X) $g (X)$ into m(X) $m (X)$ :

$m (X) = g (X) f (X) + r 1 (X),$ $m (X) = g (X) f (X) + r_{1} (X),$

with deg(r1(X))<deg(g(X)) $deg (r_{1} (X)) < deg (g (X))$ . As before, g(X)f(X) mod (Xn−1) $g (X) f (X) mod (X^{n} - 1)$ corresponds to a codeword. Also, m(X) $m (X)$ corresponds to a codeword, by assumption. Therefore, m(X)−g(X)f(X) mod (Xn−1) $m (X) - g (X) f (X) m o d (X^{n} - 1)$ corresponds to the difference of these codewords, which is a codeword. But this polynomial is just r1(X)=r1(X) mod (Xn−1) $r_{1} (X) = r_{1} (X) mod (X^{n} - 1)$ . As before, this polynomial has degree less than deg(g(X)) $deg (g (X))$ , so r1(X)=0 $r_{1} (X) = 0$ . Therefore, m(X)=g(X)f(X) $m (X) = g (X) f (X)$ . Since deg(m)≤n−1 $deg (m) \leq n - 1$ , we must have deg((f)≤n−1−deg(g) $deg ((f) \leq n - 1 - deg (g)$ . Conversely, as explained in the proof of (2), since C $C$ is cyclic, any such polynomial of the form g(X)f(X) $g (X) f (X)$ yields a codeword. Therefore, these polynomials yield exactly the elements of C $C$ .
Write Xn−1=g(X)h(X) $X^{n} - 1 = g (X) h (X)$ , which can be done by (2). Suppose m(X) $m (X)$ corresponds to an element of C $C$ . Then m(X)=g(X)f(X) $m (X) = g (X) f (X)$ , by (3), so

$h (X) m (X) = h (X) g (X) f (X) = (X n - 1) f (X) \equiv 0 mod (X n - 1) .$ $h (X) m (X) = h (X) g (X) f (X) = (X^{n} - 1) f (X) \equiv 0 mod (X^{n} - 1) .$

Conversely, suppose m(X) $m (X)$ is a polynomial such that h(X)m(X)≡0 $h (X) m (X) \equiv 0$ mod (Xn−1) $m o d (X^{n} - 1)$ . Write h(X)m(X)=(Xn−1)q(X)=h(X)g(X)q(X) $h (X) m (X) = (X^{n} - 1) q (X) = h (X) g (X) q (X)$ , for some polynomial q(X) $q (X)$ . Dividing by h(X) $h (X)$ yields m(X)=g(X)q(X) $m (X) = g (X) q (X)$ , which is a multiple of g(X) $g (X)$ , and hence corresponds to a codeword. This completes the proof of the theorem.

Let g(X)=a0+a1X+⋯+ak−1Xk−1+Xk $g (X) = a_{0} + a_{1} X + \dots + a_{k - 1} X^{k - 1} + X^{k}$ be as in the theorem. By part (3) of the theorem, every element of C $C$ corresponds to a polynomial of the form g(X)f(X) $g (X) f (X)$ , with deg(f(X))≤n−1−k $deg (f (X)) \leq n - 1 - k$ . This means that each such f(X) $f (X)$ is a linear combination of the monomials 1, X, X2, …, Xn−1−k $1, X, X^{2}, \dots, X^{n - 1 - k}$ . It follows that the codewords of C $C$ are linear combinations of the codewords corresponding to the polynomials

g (X), g (X) X, g (X) X 2, \dots, g (X) X n - 1 - k .

$g (X), g (X) X, g (X) X^{2}, \dots, g (X) X^{n - 1 - k} .$

But these are the vectors

$a_{0}, \dots, a_{k}, 0, 0, \dots), (0, a_{0}, \dots, a_{k}, 0, \dots), \dots, (0, \dots, 0, a_{0}, \dots, a_{k}) .$

Therefore, a generating matrix for $C$ can be given by

$G = (\begin{array}{ccccccc} a_{0} & a_{1} & \dots & a_{k} & 0 & 0 & \dots \\ 0 & a_{0} & a_{1} & \dots & a_{k} & 0 & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & \dots & 0 & a_{0} & a_{1} & \dots & a_{k} \end{array}) .$

We can use part (4) of the theorem to obtain a parity check matrix for $C$ . Let $h (X) = b_{0} + b_{1} X + \dots + b_{l} X^{l}$ be as in the theorem (where $l = n - k$ ). We’ll prove that the $k \times n$ matrix

$H = (\begin{array}{ccccccc} b_{l} & b_{l - 1} & \dots & b_{0} & 0 & 0 & \dots \\ 0 & b_{l} & b_{l - 1} & \dots & b_{0} & 0 & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & \dots & 0 & b_{l} & b_{l - 1} & \dots & b_{0} \end{array})$

is a parity check matrix for $C$ . Note that the order of the coefficients of $h (X)$ is reversed. Recall that $H$ is a parity check matrix for $C$ means that $H c^{T} = 0$ if and only if $c \in C$ .

Proposition

$H$ is a parity check matrix for $C$ .

Proof. First observe that since $g (X)$ has 1 as its highest nonzero coefficient, and since $g (X) h (X) = X^{n} - 1$ , the highest nonzero coefficient $b_{l}$ of $h (X)$ must also be 1. Therefore, $H$ is in row echelon form and consequently its rows are linearly independent. Since $H$ has $k$ rows, it has rank $k$ . The right null space of $H$ therefore has dimension $n - k$ .

Let $m (X) = c_{0} + c_{1} X + \dots + c_{n - 1} X^{n - 1}$ . We know from part (4) that $(c_{0}, c_{1}, \dots, c_{n - 1}) \in C$ if and only if $h (X) m (X) \equiv 0 m o d (X^{n} - 1)$ .

Choose $j$ with $l \leq j \leq n - 1$ and look at the coefficient of $X^{j}$ in the product $h (X) m (X)$ . It equals

$b_{0} c_{j} + b_{1} c_{j - 1} + \dots + b_{l - 1} c_{j - l + 1} + b_{l} c_{j - l} .$

There is a technical point to mention: Since we are looking at $h (X) m (X) m o d (X^{n} - 1)$ , we need to worry about a contribution from the term $X^{n + j}$ (since $X^{n + j} \equiv X^{n} X^{j} \equiv 1 \cdot X^{j}$ , the monomial $X^{n + j}$ reduces to $X^{j}$ ). However, the highest-degree term in the product $h (X) m (X)$ before reducing mod $X^{n} - 1$ is $c_{n - 1} X^{l + n - 1}$ . Since $l \leq j$ , we have $l + n - 1 t j + n$ . Therefore, there is no term with $X^{n + j}$ to worry about.

When we multiply $H$ times $(c_{0}, c_{1}, \dots, c_{n - 1})^{T}$ , we obtain a vector whose first entry is

$b_{l} c_{0} + b_{l - 1} c_{1} + \dots + b_{0} c_{l} .$

More generally, the $i$ th entry (where $1 \leq i \leq k$ ) is

$b_{l} c_{i - 1} + b_{l - 1} c_{i} + \dots + b_{0} c_{l + i - 1} .$

This is the coefficient of $X^{l + i - 1}$ in the product $h (X) m (X) m o d (X^{n} - 1)$ .

If $(c_{0}, c_{1}, \dots, c_{n - 1})$ is in $C$ , then $h (X) m (X) \equiv 0 m o d (X^{n} - 1)$ , so all these coefficients are 0. Therefore, $H$ times $(c_{0}, c_{1}, \dots, c_{n - 1})^{T}$ is the 0 vector, so the transposes of the vectors of $C$ are contained in the right null space of $H$ . Since both $C$ and the null space have dimension $k$ , we must have equality. This proves that $c \in C$ if and only if $H c^{T} = 0$ , which means that $H$ is a parity check matrix for $C$ .

Example

In the example at the beginning of this section, we had $n = 7$ and $g (X) = X^{4} + X^{3} + X^{2} + 1$ . We have $g (X) (X^{3} + X^{2} + 1) = X^{7} - 1$ , so $h (X) = X^{3} + X^{2} + 1$ . The parity check matrix is

$H = (\begin{array}{ccccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{array}) .$

The parity check matrix gives a way of detecting errors, but correcting errors for general cyclic codes is generally quite difficult. In the next section, we describe a class of cyclic codes for which a good decoding algorithm exists.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 24.7 Cyclic Codes

Create new playlist

Sign In

Sign Up

Table of Contents for
24.7 Cyclic Codes