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.8 BCH Codes

BCH codes are a class of cyclic codes. They were discovered around 1959 by R. C. Bose and D. K. Ray-Chaudhuri and independently by A. Hocquenghem. One reason they are important is that there exist good decoding algorithms that correct multiple errors (see, for example, [Gallager] or [Wicker]). BCH codes are used in satellites. The special BCH codes called Reed-Solomon codes (see Section 24.9) have numerous applications.

Before describing BCH codes, we need a fact about finite fields. Let F $F$ be a finite field with q $q$ elements. From Section 3.11, we know that q=pm $q = p^{m}$ is a power of a prime number p $p$ . Let n $n$ be a positive integer not divisible by p $p$ . Then it can be proved that there exists a finite field F′ $F^{'}$ containing F $F$ such that F′ $F^{'}$ contains a primitive n $n$ th root of unity α $α$ . This means that αn=1 $α^{n} = 1$ , but αk≠1 $α^{k} \neq 1$ for 1≤k<n $1 \leq k < n$ .

For example, if F=Z2 $F = Z_{2}$ , the integers mod 2, and n=3 $n = 3$ , we may take F′=GF(4) $F^{'} = G F (4)$ . The element ω $ω$ in the description of GF(4) $G F (4)$ in Section 3.11 is a primitive third root of unity. More generally, a primitive n $n$ th root of unity exists in a finite field F′ $F^{'}$ with q′ $q^{'}$ elements if and only if n|q′−1 $n | q^{'} - 1$ .

The reason we need the auxiliary field F′ $F^{'}$ is that several of the calculations we perform need to be carried out in this larger field. In the following, when we use an n $n$ th root of unity α $α$ , we’ll implicitly assume that we’re calculating in some field F′ $F^{'}$ that contains α $α$ . The results of the calculations, however, will give results about codes over the smaller field F $F$ .

The following result, often called the BCH bound, gives an estimate for the minimum weight of a cyclic code.

Theorem 24.8

Let C $C$ be a cyclic [n, k, d] $[n, k, d]$ code over a finite field F $F$ , where F $F$ has q=pm $q = p^{m}$ elements. Assume p|n. $p | n .$ Let g(X) $g (X)$ be the generating polynomial for C $C$ . Let α $α$ be a primitive n $n$ th root of unity and suppose that for some integers ℓ $ℓ$ and δ $δ$ ,

g (α ℓ) = g (α ℓ + 1) = \dots = g (α ℓ + δ) = 0.

$g (α^{ℓ}) = g (α^{ℓ + 1}) = \dots = g (α^{ℓ + δ}) = 0.$

Then d≥δ+2 $d \geq δ + 2$ .

Proof. Suppose (c0, c1, …, cn−1)∈C $(c_{0}, c_{1}, \dots, c_{n - 1}) \in C$ has weight w $w$ with 1≤w<δ+2 $1 \leq w < δ + 2$ . We want to obtain a contradiction. Let m(X)=c0+c1X+⋯+cn−1Xn−1 $m (X) = c_{0} + c_{1} X + \dots + c_{n - 1} X^{n - 1}$ . We know that m(X) $m (X)$ is a multiple of g(X) $g (X)$ , so

m (α ℓ) = m (α ℓ + 1) = \dots = m (α ℓ + δ) = 0.

$m (α^{ℓ}) = m (α^{ℓ + 1}) = \dots = m (α^{ℓ + δ}) = 0.$

Let ci1, ci2, …, ciw $c_{i_{1}}, c_{i_{2}}, \dots, c_{i_{w}}$ be the nonzero coefficients of m(X) $m (X)$ , so

m (X) = c i 1 X i 1 + c i 2 X i 2 + \dots + c i w X i w .

$m (X) = c_{i_{1}} X^{i_{1}} + c_{i_{2}} X^{i_{2}} + \dots + c_{i_{w}} X^{i_{w}} .$

The fact that m(αj)=0 $m (α^{j}) = 0$ for l≤j≤ℓ+w−1 $l \leq j \leq ℓ + w - 1$ (note that w−1≤δ $w - 1 \leq δ$ ) can be rewritten as

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ α ℓ i 1 α (ℓ + 1) i 1 ⋮ α (ℓ + w - 1) i 1 \dots \dots ⋱ \dots α ℓ i w α (ℓ + 1) i w ⋮ α (ℓ + w - 1) i w ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ c i 1 c i 2 ⋮ c i w ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ 00 ⋮ 0 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ .

$(\begin{matrix} α^{ℓ i_{1}} & \dots & α^{ℓ i_{w}} \\ α^{(ℓ + 1) i_{1}} & \dots & α^{(ℓ + 1) i_{w}} \\ ⋮ & ⋱ & ⋮ \\ α^{(ℓ + w - 1) i_{1}} & \dots & α^{(ℓ + w - 1) i_{w}} \end{matrix}) (\begin{matrix} c_{i_{1}} \\ c_{i_{2}} \\ ⋮ \\ c_{i_{w}} \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}) .$

We claim that the determinant of the matrix is nonzero. We need the following evaluation of the Vandermonde determinant. The proof can be found in most books on linear algebra.

Proposition

det ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 1 x 1 x 21 ⋮ x n - 1 1 1 x 2 x 22 ⋮ x n - 1 2 \dots \dots \dots ⋱ \dots 1 x n x 2 n ⋮ x n - 1 n ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = \prod 1 \leq i t j \leq n (x j - x i) .

$det (\begin{array}{cccc} 1 & 1 & \dots & 1 \\ x_{1} & x_{2} & \dots & x_{n} \\ x_{1}^{2} & x_{2}^{2} & \dots & x_{n}^{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{1}^{n - 1} & x_{2}^{n - 1} & \dots & x_{n}^{n - 1} \end{array}) = \prod_{1 \leq i t j \leq n} (x_{j} - x_{i}) .$

(The product is over all pairs of integers (i, j) $(i, j)$ with 1≤i<j≤n $1 \leq i < j \leq n$ .) In particular, if x1, …, xn $x_{1}, \dots, x_{n}$ are pairwise distinct, the determinant is nonzero.

In our matrix, we can factor αℓi1 $α^{ℓ i_{1}}$ from the first column, αℓi2 $α^{ℓ i_{2}}$ from the second column, etc., to obtain

det ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ α ℓ i 1 α (ℓ + 1) i 1 ⋮ α (ℓ + w - 1) i 1 \dots \dots ⋱ \dots α ℓ i w α (ℓ + 1) i w ⋮ α (ℓ + w - 1) i w ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ = α ℓ i 1 + \dots + ℓ i w det ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ 1 α i 1 ⋮ α (w - 1) i 1 \dots \dots ⋱ \dots 1 α i w ⋮ α (w - 1) i w ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ .

$\begin{matrix} \det (\begin{matrix} α^{ℓ i_{1}} & \dots & α^{ℓ i_{w}} \\ α^{(ℓ + 1) i_{1}} & \dots & α^{(ℓ + 1) i_{w}} \\ ⋮ & ⋱ & ⋮ \\ α^{(ℓ + w - 1) i_{1}} & \dots & α^{(ℓ + w - 1) i_{w}} \end{matrix}) \\ = α^{ℓ i_{1} + \dots + ℓ i_{w}} \det (\begin{matrix} 1 & \dots & 1 \\ α^{i_{1}} & \dots & α^{i_{w}} \\ ⋮ & ⋱ & ⋮ \\ α^{(w - 1) i_{1}} & \dots & α^{(w - 1) i_{w}} \end{matrix}) . \end{matrix}$

Since αi1, ⋯, αiw $α^{i_{1}}, \dots, α^{i_{w}}$ are pairwise distinct, the determinant is nonzero. Why are these numbers distinct? Suppose αij=αik $α^{i_{j}} = α^{i_{k}}$ . We may assume ij≤ik $i_{j} \leq i_{k}$ . We have 0≤ij≤ik<n $0 \leq i_{j} \leq i_{k} < n$ . Therefore, 0≤ik−ij<n $0 \leq i_{k} - i_{j} < n$ . Note that αik−ij=1 $α^{i_{k} - i_{j}} = 1$ . Since α $α$ is a primitive n $n$ th root of unity, αi≠1 $α^{i} \neq 1$ for 1≤i<n $1 \leq i < n$ . Therefore, ik−ij=0 $i_{k} - i_{j} = 0$ , so ij=ik $i_{j} = i_{k}$ . This means that the numbers αi1, ⋯, αiw $α^{i_{1}}, \dots, α^{i_{w}}$ are pairwise distinct, as claimed.

Since the determinant is nonzero, the matrix is nonsingular. This implies that (ci1, …, ciw)=0 $(c_{i_{1}}, \dots, c_{i_{w}}) = 0$ , contradicting the fact that these were the nonzero ci $c_{i}$ ’s. Therefore, all nonzero codewords have weight at least δ+2 $δ + 2$ . This completes the proof of the theorem.

Example

Let F=Z2 $F = Z_{2}$ = the integers mod 2, and let n=3 $n = 3$ . Let g(X)=X2+X+1 $g (X) = X^{2} + X + 1$ . Then

C = {(0, 0, 0), (1, 1, 1)},

$C = {(0, 0, 0), (1, 1, 1)},$

which is a binary repetition code. Let ω $ω$ be a primitive third root of unity, as in the description of GF(4) $G F (4)$ in Section 3.11. Then g(ω)=g(ω2)=0 $g (ω) = g (ω^{2}) = 0$ . In the theorem, we can therefore take ℓ=1 $ℓ = 1$ and δ=1 $δ = 1$ . We find that the minimal weight of C $C$ is at least 3. In this case, the bound is sharp, since the minimal weight of C $C$ is exactly 3.

Example

Let F $F$ be any finite field and let n $n$ be any positive integer. Let g(X)=X−1 $g (X) = X - 1$ . Then g(1)=0 $g (1) = 0$ , so we may take ℓ=0 $ℓ = 0$ and δ=0 $δ = 0$ . We conclude that the minimum weight of the code generated by g(X) $g (X)$ is at least 2 (actually, the theorem assumes that p|n, $p | n,$ but this assumption is not needed for this special case where ℓ=δ=0 $ℓ = δ = 0$ ). We have seen this code before. If (c0, …, cn−1) $(c_{0}, \dots, c_{n - 1})$ is a vector, and m(X)=c0+⋯+cn−1Xn−1 $m (X) = c_{0} + \dots + c_{n - 1} X^{n - 1}$ is the associated polynomial, then m(X) $m (X)$ is a multiple of X−1 $X - 1$ exactly when m(1)=0 $m (1) = 0$ . This means that c0+⋯+cn−1=0 $c_{0} + \dots + c_{n - 1} = 0$ . So a vector is a codeword if and only if the sum of its entries is 0. When F=Z2 $F = Z_{2}$ , this is the parity check code, and for other finite fields it is a generalization of the parity check code. The fact that its minimal weight is 2 is easy to see directly: If a codeword has a nonzero entry, then it must contain another nonzero entry to cancel it and make the sum of the entries be 0. Therefore, each nonzero codeword has at least two nonzero entries, and hence has weight at least 2. The vector (1, −1, 0, …) $(1, - 1, 0, \dots)$ is a codeword and has weight 2, so the minimal weight is exactly 2.

Example

Let’s return to the example of a binary cyclic code of length 7 from Section 24.7. We have F=Z2 $F = Z_{2}$ , and g(X)=1+X2+X3+X4 $g (X) = 1 + X^{2} + X^{3} + X^{4}$ . We can factor g(X)=(X−1)(X3+X+1) $g (X) = (X - 1) (X^{3} + X + 1)$ . Let α $α$ be a root of X3+X+1 $X^{3} + X + 1$ . Then α $α$ is a primitive seventh root of unity (see Exercise 18), and we are working in GF(8) $G F (8)$ . Since Z2⊂GF(8) $Z_{2} \subset G F (8)$ , we have 2=1+1=0 $2 = 1 + 1 = 0$ and −1=1 $- 1 = 1$ . Therefore, α3=α+1 $α^{3} = α + 1$ . Squaring yields α6=α2+2α+1=α2+1 $α^{6} = α^{2} + 2 α + 1 = α^{2} + 1$ . Therefore, (α2)3+(α2)+1=0 $(α^{2})^{3} + (α^{2}) + 1 = 0$ . This means that g(α2)=0 $g (α^{2}) = 0$ , so

g (1) = g (α) = g (α 2) = 0.

$g (1) = g (α) = g (α^{2}) = 0.$

In the theorem, we can take ℓ=0 $ℓ = 0$ and δ=2 $δ = 2$ . Therefore, the minimal weight in the code is at least 4 (in fact, it is exactly 4).

To define the BCH codes, we need some more notation. We are going to construct codes of length n $n$ over a finite field F $F$ . Factor Xn−1 $X^{n} - 1$ into irreducible factors over F $F$ :

X n - 1 = f 1 (X) f 2 (X) \dots f r (X),

$X^{n} - 1 = f_{1} (X) f_{2} (X) \dots f_{r} (X),$

where each fi(X) $f_{i} (X)$ is a polynomial with coefficients in F $F$ , and each fi(X) $f_{i} (X)$ cannot be factored into lower-degree polynomials with coefficients in F $F$ . We may assume that the highest nonzero coefficient of each fi(X) $f_{i} (X)$ is 1. Let α $α$ be a primitive n $n$ th root of unity. Then α0, α1, α2, …, αn−1 $α^{0}, α^{1}, α^{2}, \dots, α^{n - 1}$ are roots of Xn−1 $X^{n} - 1$ . This means that

X n - 1 = (X - 1) (X - α) (X - α 2) \dots (X - α n - 1) .

$X^{n} - 1 = (X - 1) (X - α) (X - α^{2}) \dots (X - α^{n - 1}) .$

Therefore, each fi(X) $f_{i} (X)$ is a product of some of these factors (X−αj) $(X - α^{j})$ , and each αj $α^{j}$ is a root of exactly one of the polynomials fi(X) $f_{i} (X)$ . For each j $j$ , let qj(X) $q_{j} (X)$ be the polynomial fi(X) $f_{i} (X)$ such that fi(αj)=0 $f_{i} (α^{j}) = 0$ . This gives us polynomials q0(X), q1(X), …qn−1(X) $q_{0} (X), q_{1} (X), \dots q_{n - 1} (X)$ . Of course, usually these polynomials are not all distinct, since a polynomial fi(X) $f_{i} (X)$ that has two different powers αj, αk $α^{j}, α^{k}$ as roots will serve as both qj(X) $q_{j} (X)$ and qk(X) $q_{k} (X)$ (see the examples given later in this section).

A BCH code of designed distance d $d$ is a code with generating polynomial

g (X) = least common multiple of q k + 1 (X), q k + 2 (X), \dots, q k + d - 1 (X)

$g (X) = least common multiple of q_{k + 1} (X), q_{k + 2} (X), \dots, q_{k + d - 1} (X)$

for some integer k $k$ .

Theorem

A BCH code of designed distance d $d$ has minimum weight greater than or equal to d $d$ .

Proof. Since qj(X) $q_{j} (X)$ divides g(X) $g (X)$ for k+1≤j≤k+d−1 $k + 1 \leq j \leq k + d - 1$ , and qj(αj)=0 $q_{j} (α^{j}) = 0$ , we have

g (α k + 1) = g (α k + 2) = \dots = g (α k + d - 1) = 0.

$g (α^{k + 1}) = g (α^{k + 2}) = \dots = g (α^{k + d - 1}) = 0.$

The BCH bound (with ℓ=k+1 $ℓ = k + 1$ and δ=d−2 $δ = d - 2$ ) implies that the code has minimum weight at least d=δ+2 $d = δ + 2$ .

Example

Let F=Z2 $F = Z_{2}$ , and let n=7 $n = 7$ . Then

X 7 - 1 = (X - 1) (X 3 + X 2 + 1) (X 3 + X + 1) .

$X^{7} - 1 = (X - 1) (X^{3} + X^{2} + 1) (X^{3} + X + 1) .$

Let α $α$ be a root of X3+X+1 $X^{3} + X + 1$ . Then α $α$ is a primitive 7th root of unity, as in the previous example. Moreover, in that example, we showed that α2 $α^{2}$ is also a root of X3+X+1 $X^{3} + X + 1$ . In fact, we actually showed that the square of a root of X3+X+1 $X^{3} + X + 1$ is also a root, so we have that α4=(α2)2 $α^{4} = (α^{2})^{2}$ is also a root of X3+X+1 $X^{3} + X + 1$ . (We could square this again, but α8=α $α^{8} = α$ , so we are back to where we started.) Therefore, α, α2, α4 $α, α^{2}, α^{4}$ are the roots of X3+X+1 $X^{3} + X + 1$ , so

X 3 + X + 1 = (X - α) (X - α 2) (X - α 4) .

$X^{3} + X + 1 = (X - α) (X - α^{2}) (X - α^{4}) .$

The remaining powers of α $α$ must be roots of X3+X2+1 $X^{3} + X^{2} + 1$ , so

X 3 + X 2 + 1 = (X - α 3) (X - α 5) (X - α 6) .

$X^{3} + X^{2} + 1 = (X - α^{3}) (X - α^{5}) (X - α^{6}) .$

Therefore,

q 0 (X) = X - 1, q 1 (X) = q 2 (X) = q 4 (X) = X 3 + X + 1, q 3 (X) = q 5 (X) = q 6 (X) = X 3 + X 2 + 1.

$\begin{matrix} q_{0} (X) = X - 1, q_{1} (X) = q_{2} (X) = q_{4} (X) = X^{3} + X + 1, \\ q_{3} (X) = q_{5} (X) = q_{6} (X) = X^{3} + X^{2} + 1. \end{matrix}$

If we take k=−1 $k = - 1$ and d=3 $d = 3$ , then

g (X) = lcm (q 0 (X), q 1 (X)) = (X - 1) (X 3 + X + 1) = X 4 + X 3 + X 2 + 1.

$\begin{matrix} g (X) = lcm (q_{0} (X), q_{1} (X)) \\ = (X - 1) (X^{3} + X + 1) = X^{4} + X^{3} + X^{2} + 1. \end{matrix}$

We obtain the cyclic [7, 3, 4] $[7, 3, 4]$ code discussed in Section 24.7. The theorem says that the minimum weight is at least 3. In this case, we can do a little better. If we take k=−1 $k = - 1$ and d=4 $d = 4$ , then we have a generating polynomial g1(X) $g_{1} (X)$ with

g 1 (X) = lcm (q 0 (X), q 1 (X), q 2 (X)) = g (X) .

$g_{1} (X) = lcm (q_{0} (X), q_{1} (X), q_{2} (X)) = g (X) .$

This is because q2(X)=q1(X) $q_{2} (X) = q_{1} (X)$ , so the least common multiple doesn’t change when q2(X) $q_{2} (X)$ is included. The theorem now tells us that the minimum weight of the code is at least 4. As we have seen before, the minimum weight is exactly 4.

Example (continued)

Let’s continue with the previous example, but take k=0 $k = 0$ and d=7 $d = 7$ . Then

g (X) = lcm (q 1 (X), \dots, q 6 (X)) = (X 3 + X + 1) (X 3 + X 2 + 1) = X 6 + X 5 + X 4 + X 3 + X 2 + X + 1.

$\begin{matrix} g (X) = lcm (q_{1} (X), \dots, q_{6} (X)) = (X^{3} + X + 1) (X^{3} + X^{2} + 1) \\ = X^{6} + X^{5} + X^{4} + X^{3} + X^{2} + X + 1. \end{matrix}$

We obtain the repetition code with only two codewords:

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

${(0, 0, 0, 0, 0, 0, 0), (1, 1, 1, 1, 1, 1, 1)} .$

The theorem says that the minimum distance is at least 7. In fact it is exactly 7.

Example

Let F=Z5={0, 1, 2, 3, 4} $F = Z_{5} = {0, 1, 2, 3, 4}$ = the integers mod 5. Let n=4 $n = 4$ . Then

X 4 - 1 = (X - 1) (X - 2) (X - 3) (X - 4)

$X^{4} - 1 = (X - 1) (X - 2) (X - 3) (X - 4)$

(this is an equality, or congruence if you prefer, in Z5 $Z_{5}$ ). Let α=2 $α = 2$ . We have 24=1 $2^{4} = 1$ , but 2j≠1 $2^{j} \neq 1$ for 1≤j<4 $1 \leq j < 4$ . Therefore, 2 is a primitive 4th root of unity in Z5 $Z_{5}$ . We have 20=1, 22=4, 23=3 $2^{0} = 1, 2^{2} = 4, 2^{3} = 3$ (these are just congruences mod 5). Therefore,

q 0 (X) = X - 1, q 1 (X) = X - 2, q 2 (X) = X - 4, q 3 (X) = X - 3.

$q_{0} (X) = X - 1, q_{1} (X) = X - 2, q_{2} (X) = X - 4, q_{3} (X) = X - 3.$

In the theorem, let k=0, d=3 $k = 0, d = 3$ . Then

g (X) = lcm (q 1 (X), q 2 (X)) = (X - 2) (X - 4) = X 2 - 6 X + 8 = X 2 + 4 X + 3.

$\begin{matrix} g (X) = lcm (q_{1} (X), q_{2} (X)) = (X - 2) (X - 4) \\ = X^{2} - 6 X + 8 = X^{2} + 4 X + 3. \end{matrix}$

We obtain a cyclic [4, 2] $[4, 2]$ code over Z5 $Z_{5}$ with generating matrix

(30431401) .

$(\begin{array}{cccc} 3 & 4 & 1 & 0 \\ 0 & 3 & 4 & 1 \end{array}) .$

The theorem says that the minimum weight is at least 3. Since the first row of the matrix is a codeword of weight 3, the minimum weight is exactly 3. This code is an example of a Reed-Solomon code, which will be discussed in the next section.

24.8.1 Decoding BCH Codes

One of the reason BCH codes are useful is that there are good decoding algorithms. One of the best known is due to Berlekamp and Massey (see [Gallager] or [Wicker]). In the following, we won’t give the algorithm, but, in order to give the spirit of some of the ideas that are involved, we show a way to correct one error in a BCH code with designed distance d≥3 $d \geq 3$ .

Let C $C$ be a BCH code of designed distance d≥3 $d \geq 3$ . Then C $C$ is a cyclic code, say of length n $n$ , with generating polynomial g(X) $g (X)$ . There is a primitive n $n$ th root of unity α $α$ such that

g (α k + 1) = g (α k + 2) = 0

$g (α^{k + 1}) = g (α^{k + 2}) = 0$

for some integer k $k$ .

Let

H = (11 α k + 1 α k + 2 α 2 (k + 1) α 2 (k + 2) \dots \dots α (n - 1) (k + 1) α (n - 1) (k + 2)) .

$H = (\begin{array}{ccccc} 1 & α^{k + 1} & α^{2 (k + 1)} & \dots & α^{(n - 1) (k + 1)} \\ 1 & α^{k + 2} & α^{2 (k + 2)} & \dots & α^{(n - 1) (k + 2)} \end{array}) .$

If c=(c0, …, cn−1) $c = (c_{0}, \dots, c_{n - 1})$ is a codeword, then the polynomial m(X)=c0+c1X+⋯+cn−1Xn−1 $m (X) = c_{0} + c_{1} X + \dots + c_{n - 1} X^{n - 1}$ is a multiple of g(X) $g (X)$ , so

m (α k + 1) = m (α k + 2) = 0.

$m (α^{k + 1}) = m (α^{k + 2}) = 0.$

This may be rewritten in terms of H $H$ :

c H T = (c 0, c 1, \dots, c n - 1) ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 1 α k + 1 α 2 (k + 1) ⋮ α (n - 1) (k + 1) 1 α k + 2 α 2 (k + 2) ⋮ α (n - 1) (k + 2) ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = 0.

$c H^{T} = (c_{0}, c_{1}, \dots, c_{n - 1}) (\begin{array}{cc} 1 & 1 \\ α^{k + 1} & α^{k + 2} \\ α^{2 (k + 1)} & α^{2 (k + 2)} \\ ⋮ & ⋮ \\ α^{(n - 1) (k + 1)} & α^{(n - 1) (k + 2)} \end{array}) = 0.$

H $H$ is not necessarily a parity check matrix for C $C$ , since there might be noncodewords that are also in the null space of H $H$ . However, as we shall see, H $H$ can correct an error.

Suppose the vector r=c+e $r = c + e$ is received, where c $c$ is a codeword and e=(e0, …, en−1) $e = (e_{0}, \dots, e_{n - 1})$ is an error vector. We assume that at most one entry of e $e$ is nonzero.

Here is the algorithm for correcting one error.

Write rHT=(s1, s2) $r H^{T} = (s_{1}, s_{2})$ .
If s1=0 $s_{1} = 0$ , there is no error (or there is more than one error), so we’re done.
If s1≠0 $s_{1} \neq 0$ , compute s2/s1 $s_{2} / s_{1}$ . This will be a power αj−1 $α^{j - 1}$ of α $α$ . The error is in the j $j$ th position. If we are working over the finite field Z2 $Z_{2}$ , we are done, since then ej=1 $e_{j} = 1$ . But for other finite fields, there are several choices for the value of ej $e_{j}$ .
Compute ej=s1/α(j−1)(k+1) $e_{j} = s_{1} / α^{(j - 1) (k + 1)}$ . This is the j $j$ th entry of the error vector e $e$ . The other entries of e $e$ are 0.
Subtract the error vector e $e$ from the received vector r $r$ to obtain the correct codeword c $c$ .

Example

Let’s look at the BCH code over Z2 $Z_{2}$ of length 7 and designed distance 7 considered previously. It is the binary repetition code of length 7 and has two codewords: (0, 0, 0, 0, 0, 0, 0), (1, 1, 1, 1, 1, 1, 1) $(0, 0, 0, 0, 0, 0, 0), (1, 1, 1, 1, 1, 1, 1)$ . The algorithm corrects one error. Suppose the received vector is r=(1, 1, 1, 1, 0, 1, 1) $r = (1, 1, 1, 1, 0, 1, 1)$ . As before, let α $α$ be a root of X3+X+1 $X^{3} + X + 1$ . Then α $α$ is a primitive 7th root of unity.

Before proceeding, we need to deduce a few facts about computing with powers of α $α$ . We have α3=α+1 $α^{3} = α + 1$ . Multiplying this relation by powers of α $α$ yields

α 4 = α 2 + α, α 5 = α 3 + α 2 = α 2 + α + 1, α 6 = α 3 + α 2 + α = (α + 1) + α 2 + α = α 2 + 1.

$\begin{matrix} α^{4} = α^{2} + α, \\ α^{5} = α^{3} + α^{2} = α^{2} + α + 1, \\ α^{6} = α^{3} + α^{2} + α = (α + 1) + α^{2} + α = α^{2} + 1. \end{matrix}$

Also, the fact that αj=αj (mod 7) $α^{j} = α^{j (m o d 7)}$ is useful.

We now can compute

r H T = (1, 1, 1, 1, 0, 1, 1) ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 1 α α 2 ⋮ α 6 1 α 2 α 4 ⋮ α 12 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = (1 + α + α 2 + α 3 + α 5 + α 6, 1 + α 2 + α 4 + α 6 + α 10 + α 12) = (α + α 2, α) ​ .

$\begin{matrix} r H^{T} = (1, 1, 1, 1, 0, 1, 1) (\begin{matrix} 1 & 1 \\ α & α^{2} \\ α^{2} & α^{4} \\ ⋮ & ⋮ \\ α^{6} & α^{12} \end{matrix}) \\ = (\begin{matrix} 1 + α + α^{2} + α^{3} + α^{5} + α^{6}, & 1 + α^{2} + α^{4} + α^{6} + α^{10} + α^{12} \end{matrix}) \\ = (\begin{matrix} α + α^{2}, & α \end{matrix}) . \end{matrix}$

The sum in the first entry, for example, can be evaluated as follows:

1 + α + α 2 + α 3 + α 5 + α 6 = 1 + α + α 2 + (1 + α) + (α 2 + α + 1) + (α 2 + 1) = α + α 2 .

$1 + α + α^{2} + α^{3} + α^{5} + α^{6} = 1 + α + α^{2} + (1 + α) + (α^{2} + α + 1) + (α^{2} + 1) = α + α^{2} .$

Therefore, s1=α+α2 $s_{1} = α + α^{2}$ and s2=α $s_{2} = α$ . We need to calculate s2/s1 $s_{2} / s_{1}$ . Since s1=α+α2=α4 $s_{1} = α + α^{2} = α^{4}$ , we have

$s_{2} / s_{1} = α / α^{4} = α^{- 3} = α^{4} .$

Therefore, $j - 1 = 4$ , so the error is in position $j = 5$ . The fifth entry of the error vector is $s_{1} / α^{4} = 1$ , so the error vector is $(0, 0, 0, 0, 1, 0, 0)$ . The corrected message is

$r - e = (1, 1, 1, 1, 1, 1, 1) .$

Here is why the algorithm works. Since $c H^{T} = 0$ , we have

$r H^{T} = c H^{T} = e H^{T} = e H^{T} = (s_{1}, s_{2}) .$

If $e = (0, 0, \dots, e_{j}, 0, \dots)$ with $e_{j} \neq 0$ , then the definition of $H$ gives

$s_{1} = e_{j} α^{(j - 1) (k + 1)}, s_{2} = e_{j} α^{(j - 1) (k + 2)} .$

Therefore, $s_{2} / s_{1} = α^{j - 1}$ . Also, $s_{1} / α^{(j - 1) (k + 1)} = e_{j}$ , as claimed.

..................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.8 BCH Codes

Create new playlist

Sign In

Sign Up

Table of Contents for
24.8 BCH Codes