BCH code

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In coding theory the BCH codes form a class of parameterised error-correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose and Ray-Chaudhuri ¹. The acronym BCH comprises the initials of these inventors' names.

The principal advantage of BCH codes is the ease with which they can be decoded, via an elegant algebraic method known as syndrome decoding. This allows very simple electronic hardware to perform the task, obviating the need for a computer, and meaning that a decoding device may be made small and low-powered. As a class of codes, they are also highly flexible, allowing control over block length and acceptable error thresholds, meaning that a custom code can be designed to a given specification (subject to mathematical constraints).

Reed–Solomon codes, which are BCH codes, are used in applications such as satellite communications, compact disc players, DVDs, disk drives, and two-dimensional bar codes.

In technical terms a BCH code is a multilevel cyclic variable-length digital error-correcting code used to correct multiple random error patterns. BCH codes may also be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign digit.²

BCH codes are also useful in theoretical computer science, for instance in the MAXEkSAT problem.

Construction

A BCH code is a polynomial code over a finite field with a particularly chosen generator polynomial. It is also a cyclic code.

Simplified BCH codes

For ease of exposition, we first describe a special class of BCH codes. General BCH codes are described in the next section.

Definition. Fix a finite field $G F (q m)$ , where $q$ is a prime. Also fix positive integers $n$ , and $d$ such that $n = q m - 1$ and $2 \leq d \leq n$ . We will construct a polynomial code over $G F (q)$ with code length $n$ , whose minimum Hamming distance is at least $d$ . What remains to be specified is the generator polynomial of this code.

Let $α$ be a primitive $n$ th root of unity in $G F (q m)$ . For all $i$ , let $m i (x)$ be the minimal polynomial of $α i$ with coefficients in $G F (q)$ . The generator polynomial of the BCH code is defined as the least common multiple $g(x) = {\rm lcm}(m_1(x),\ldots,m_{d-1}(x))$ .

Example

Let $q = 2$ and $m = 4$ (therefore $n = 15$ ). We will consider different values of $d$ . There is a primitive root $\alpha\in GF(16)$ satisfying

α 4 + α + 1 = 0

(1)

its minimal polynomial over $G F (2)$ is : $m 1 (x) = x 4 + x + 1$ . Note that in $G F (2 4)$ , the equation $(a + b) 2 = a 2 + 2 a b + b 2 = a 2 + b 2$ holds, and therefore $m 1 (α 2) = m 1 (α) 2 = 0$ . Thus $α 2$ is a root of $m 1 (x)$ , and therefore

m 2 (x) = m 1 (x) = x 4 + x + 1

.

To compute $m 3 (x)$ , notice that, by repeated application of (1), we have the following linear relations:

$1 = 0α 3 + 0α 2 + 0α + 1$
$α 3 = 1α 3 + 0α 2 + 0α + 0$
$α 6 = 1α 3 + 1α 2 + 0α + 0$
$α 9 = 1α 3 + 0α 2 + 1α + 0$
$α 12 = 1α 3 + 1α 2 + 1α + 1$

Five right-hand-sides of length four must be linearly dependent, and indeed we find a linear dependency $α 12 + α 9 + α 6 + α 3 + 1 = 0$ . Since there is no smaller degree dependency, the minimal polynomial of $α 3$ is : $m 3 (x) = x 4 + x 3 + x 2 + x + 1$ . Continuing in a similar manner, we find

$m_4(x) = m_2(x) = m_1(x) = x^4+x+1,\,$

$m_5(x) = x^2+x+1,\,$

$m_6(x) = m_3(x) = x^4+x^3+x^2+x+1,\,$

$m_7(x) = x^4+x^3+1.\,$

The BCH code with $d = 1,2,3$ has generator polynomial

$g(x) = m_1(x) = x^4+x+1.\,$

It has minimal Hamming distance at least 3 and corrects up to 1 error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.

The BCH code with $d = 4,5$ has generator polynomial

$g(x) = {\rm lcm}(m_1(x),m_3(x)) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1.\,$

It has minimal Hamming distance at least 5 and corrects up to 2 errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.

The BCH code with $d = 6,7$ has generator polynomial

$\begin{align} g(x) & {} = {\rm lcm}(m_1(x),m_3(x),m_5(x)) \\ & {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) \\ & {} = x^{10}+x^8+x^5+x^4+x^2+x+1. \end{align}$

It has minimal Hamming distance at least 7 and corrects up to 3 errors. This code has 5 data bits and 10 checksum bits.

The BCH code with $d = 8$ and higher have generator polynomial

$\begin{align} g(x) & {} = {\rm lcm}(m_1(x),m_3(x),m_5(x),m_7(x)) \\ & {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)(x^4+x^3+1) \\ & {} = x^{14}+x^{13}+x^{12}+\cdots+x^2+x+1. \end{align}$

This code has minimal Hamming distance 8 and corrects up to 3 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

General BCH codes

General BCH codes differ from the simplified case discussed above in two respects. First, one replaces the requirement $n = q m - 1$ by a more general condition. Second, the consecutive roots of the generator polynomial may run from $\alpha^c,\ldots,\alpha^{c+d-2}$ instead of $\alpha,\ldots,\alpha^{d-1}$ .

Definition. Fix a finite field $G F (q)$ , where $q$ is a prime power. Choose positive integers $m, n, d, c$ such that $2\leq d\leq n$ , $gcd(n, q) = 1$ , and $m$ is the multiplicative order of $q$ modulo $n$ .

As before, let $α$ be a primitive $n$ th root of unity in $G F (q m)$ , and let $m i (x)$ be the minimal polynomial over $G F (q)$ of $α i$ for all $i$ . The generator polynomial of the BCH code is defined as the least common multiple $g(x) = {\rm lcm}(m_c(x),\ldots,m_{c+d-2}(x))$ .

Note: if $n = q m - 1$ as in the simplified definition, then $gcd(n, q)$ is automatically 1, and the order of $q$ modulo $n$ is automatically $m$ . Therefore, the simplified definition is indeed a special case of the general one.

Properties

1. The generator polynomial of a BCH code has degree at most $(d - 1) m$ . Moreover, if $q = 2$ and $c = 1$ , the generator polynomial has degree at most $d m / 2$ .

Proof: each minimal polynomial

m i (x)

has degree at most

m

. Therefore, the least common multiple of

d - 1

of them has degree at most

(d - 1) m

. Moreover, if

q = 2

, then

m i (x) = m 2 i (x)

for all

i

. Therefore,

g (x)

is the least common multiple of at most

d / 2

minimal polynomials

m i (x)

for odd indices

i

, each of degree at most

m

.

2. A BCH code has minimal Hamming distance at least $d$ . Proof: We only give the proof in the simplified case; the general case is similar. Suppose that $p (x)$ is a code word with fewer than $d$ non-zero terms. Then

$p(x) = b_1x^{k_1} + \cdots + b_{d-1}x^{k_{d-1}},\text{ where }k_1<k_2<\cdots<k_{d-1}.$

Recall that $\alpha^1,\ldots,\alpha^{d-1}$ are roots of $g (x)$ , hence of $p (x)$ . This implies that $b_1,\ldots,b_{d-1}$ satisfy the following equations, for $i=1,\ldots,d-1$ :

$p(\alpha^i) = b_1\alpha^{ik_1} + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0$ .

In matrix form, we have

$\begin{bmatrix} \alpha^{k_1} & \alpha^{k_2} & \cdots & \alpha^{k_{d-1}} \\ \alpha^{2k_1} & \alpha^{2k_2} & \cdots & \alpha^{2k_{d-1}} \\ \vdots & \vdots && \vdots \\ \alpha^{(d-1)k_1} & \alpha^{(d-1)k_2} & \cdots & \alpha^{(d-1)k_{d-1}} \\ \end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_{d-1} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$

The determinant of this matrix equals

$\left(\prod_{i=1}^{d-1}\alpha^{k_i}\right)\det\begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha^{k_1} & \alpha^{k_2} & \cdots & \alpha^{k_{d-1}} \\ \vdots & \vdots && \vdots \\ \alpha^{(d-2)k_1} & \alpha^{(d-2)k_2} & \cdots & \alpha^{(d-2)k_{d-1}} \\ \end{pmatrix} = \left(\prod_{i=1}^{d-1}\alpha^{k_i}\right) \det(V)$

The matrix $V$ is seen to be a Vandermonde matrix, and its determinant is

$\det(V) = \prod_{1\le i<j\le d-1} (\alpha^{k_j}-\alpha^{k_i})$ ,

which is non-zero. It therefore follows that $b_1,\ldots,b_{d-1}=0$ , hence $p (x) = 0$ .

3. A BCH code is cyclic.

Proof: A polynomial code of length $n$ is cyclic if and only if its generator polynomial divides $x n - 1$ . Since $g (x)$ is the minimal polynomial with roots $\alpha^c,\ldots,\alpha^{c+d-2}$ , it suffices to check that each of $\alpha^c,\ldots,\alpha^{c+d-2}$ is a root of $x n - 1$ . This follows immediately from the fact that $α$ is, by definition, an $n$ th root of unity.

Special cases

A BCH code with $c = 1$ is called a narrow-sense BCH code.
A BCH code with $n = q m - 1$ is called primitive.

Therefore, the "simplified" BCH codes we considered above were just the primitive narrow-sense codes.

A narrow-sense BCH code with $n = q - 1$ is called a Reed-Solomon code.

Decoding

There are many algorithms for decoding BCH codes. The most common ones follow this general outline:

Calculate the syndrome values for the received vector
Calculate the error locator polynomials
Calculate the roots of this polynomial to get error location positions.
Calculate the error values at these error locations.

The received vector $R$ is the sum of the correct codeword $C$ and an unknown error vector $E$ . The syndrome values are formed by considering $R$ as a polynomial and evaluating it at $\alpha^c,\ldots,\alpha^{c+d-2}$ . Thus the syndromes are³

s j = R (α c + j - 1) = C (α c + j - 1) + E (α c + j - 1)

for $j = 1$ to $d - 1$ . Since $α c + j - 1$ are the zeros of $g (x)$ , of which $C (x)$ is a multiple, $C (α c + j - 1) = 0$ . Examining the syndrome values thus isolates the error vector so we can begin to solve for it.

If there is no error, $s j = 0$ for all $j$ . If there is a single error, write this as $E(x) = e\,x^i$ , where $i$ is the location of the error and $e$ is its magnitude. Then the first two syndromes are

$s_1 = e\,\alpha^{c\,i}$

$s_2 = e\,\alpha^{(c+1)\,i} = \alpha^i s_1$

so together they allow us to calculate $e$ and provide some information about $i$ (completely determining it in the case of Reed-Solomon codes).

If there are two or more errors,

$E(x) = e_1 x^{i_1} + e_2 x^{i_2} + \ldots$

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns $e k$ and $i k$ . Two popular algorithms for this task are:

Peterson Gorenstein Zierler algorithm

Peterson's algorithm is the step 2 of the generalized BCH decoding procedure. We use Peterson's algorithm to calculate the error locator polynomial coefficients $\lambda_1 , \lambda_2, \dots, \lambda_{t}$ of a polynomial $\Lambda(x) = 1 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_{t}x^{t}$

Now the procedure of the Peterson Gorenstein Zierler algorithm for a given $(n, k, d m i n)$ BCH code designed to correct $[t=\frac{d_{min}-1}{2}]$ errors is

First generate the Matrix of $2 t$ syndromes
Next generate the $S_{t\times t}$ matrix with elements that are syndrome values

$S_{t \times t}=\begin{bmatrix}s_1&s_2&s_3&\dots&s_t\\ s_2&s_3&s_4&\dots&s_{t+1}\\ s_3&s_4&s_5&\dots&s_{t+2}\\ \dots&\dots&\dots&\dots&\dots\\ s_t&s_{t+1}&s_{t+2}&\dots&s_{2t-1}\end{bmatrix}$

Generate a $c t x 1$ matrix with elements

$C_{t \times 1}=\begin{bmatrix}s_{t+1}\\ s_{t+2}\\ \vdots\\ \vdots\\ s_{2t}\end{bmatrix}$

Let $Λ$ denote the unknown polynomial coefficients, which are given by

$\Lambda_{t \times 1} = \begin{bmatrix}\lambda_{t}\\ \lambda_{t-1}\\ \vdots\\ \lambda_{2}\\ \lambda_{1}\end{bmatrix}$

Form the matrix equation

$S_{t \times t} \Lambda_{t \times 1} = C_{t \times 1\,}$

If the determinant of matrix $S_{t \times t}$ exists, then we can actually find an inverse of this matrix and solve for the values of unknown $Λ$ values.

If $\det(S_{t \times t}) = 0$ , then follow

       if  $t = 0$ 
       then
             declare an empty error locator polynomial
             stop Peterson procedure.
       end
       set 
       continue from the beginning of Peterson's decoding

After you have values of $Λ$ you have with you the error locator polynomial.
Stop Peterson procedure.

Factoring error locator polynomial

Now that you have the $Λ(x)$ polynomial, you can find its roots in the form $\Lambda(x)=(\alpha^i x + 1) (\alpha ^j x + 1) \cdots (\alpha^k x + 1)$ using the Chien search algorithm. The exponential powers of the primitive element $α$ will yield the positions where errors occur in the received word; hence the name 'error locator' polynomial.

Correcting errors

Once the error locations are known, the next step is to calculate the correct values. For the case of binary BCH, this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights $e j$ can be determined by solving the linear system

$s_1 = e_1 \alpha^{c\,i_1} + e_2 \alpha^{c\,i_2} + \ldots$

$s_2 = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \ldots$

. . .

However, there is a more efficient method known as the Forney Algorithm⁴, which is based on Lagrange interpolation. First calculate the error evaluator polynomial

$\omega(x) = S(x)\,\Lambda(x) \pmod{x^{d-1}}$

Then evaluate the error values.

$e_j = \frac{\omega(\alpha^{-c\,i_j})}{\prod_{k \ne j}(1 - \alpha^{c\,i_k} \alpha^{-c\,i_j})}$

Citations

^ Page 189, Reed, Irving, S.. Error-Control Coding for Data Networks. Kluwer Academic Publishers. ISBN 0-7923-8528-4.
^ Federal Standard 1037C, 1996.
^ Lidl, Rudolf; Pilz, Günter (1999). Applied Abstract Algebra (2nd ed.). Wiley. p. 229.
^ Hanzo, Lajos; Tong Hooi Liew, Bee Leong Yeap (2002). Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels. Wiley. p. 66.

References

Primary sources

A. Hocquenghem. Codes correcteurs d'erreurs. Chiffres (Paris), 2:147–156, September 1959
R. C. Bose, Dwijendra K. Ray-Chaudhuri: On A Class of Error Correcting Binary Group Codes Information and Control 3(1): 68-79, March 1960

Secondary sources

Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall
Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (2nd ed.), John Wiley
Lidl, R. (1999), Applied Abstract Algebra (2nd ed.)
MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers
Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, http://www.cse.buffalo.edu/~atri/courses/coding-theory/
Gill, John (unknown), EE387 Notes #7, Handout #28, Stanford University, pp. 42–45, http://www.stanford.edu/class/ee387/handouts/notes7.pdf, retrieved April 21, 2010

Return to Fuhz Home - This article covering BCH code is enhanced for the visually impaired.

Article from Wikipedia. All text is available under the terms of the GNU Free Documentation License - Our Privacy Policy - Thanks Auto Blog Commenter

[0] Page 189, Reed, Irving, S.. Error-Control Coding for Data Networks. Kluwer Academic Publishers. ISBN 0-7923-8528-4.

[1] Federal Standard 1037C, 1996.

[2] Lidl, Rudolf; Pilz, Günter (1999). Applied Abstract Algebra (2nd ed.). Wiley. p. 229.

[3] Hanzo, Lajos; Tong Hooi Liew, Bee Leong Yeap (2002). Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels. Wiley. p. 66.

1

2

3

4