BCH code
In coding theory, the BCH codes or Bose–Chaudhuri–Hocquenghem codes form a class of cyclic errorcorrecting codes that are constructed using polynomials over a finite field (also called Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Bose and D. K. RayChaudhuri.^{[1]}^{[2]}^{[3]} The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors' surnames (mistakenly, in the case of RayChaudhuri).
One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding; this simplifies the design of the decoder for these codes, using small lowpower electronic hardware.
BCH codes are used in applications such as satellite communications,^{[4]} compact disc players, DVDs, disk drives, solidstate drives^{[5]} and twodimensional bar codes.
Contents
 1 Definition and illustration
 2 Properties
 3 Encoding
 4 Decoding
 5 Citations
 6 References
 7 Further reading
Definition and illustration[edit]
Primitive narrowsense BCH codes[edit]
Given a prime number q and prime power q^{m} with positive integers m and d such that d ≤ q^{m} − 1, a primitive narrowsense BCH code over the finite field (or Galois field) GF(q) with code length n = q^{m} − 1 and distance at least d is constructed by the following method.
Let α be a primitive element of GF(q^{m}). For any positive integer i, let m_{i}(x) be the minimal polynomial with coefficients in GF(q) of α^{i}. The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m_{1}(x),…,m_{d − 1}(x)). It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides x^{n} − 1. Therefore, the polynomial code defined by g(x) is a cyclic code.
Example[edit]
Let q=2 and m=4 (therefore n=15). We will consider different values of d. For GF(16) = GF(2^{4}) based on the polynomial x^{4}+x+1 with primitive root α=x+0 there are minimum polynomials m_{i}(x) with coefficients in GF(2) satisfying
The minimal polynomials of the fourteen powers of α are
The BCH code with has generator polynomial
It has minimal Hamming distance at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.
The BCH code with has generator polynomial
It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.
The BCH code with has generator polynomial
It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. (This particular generator polynomial has a realworld application, in the format patterns of the QR code.)
The BCH code with and higher has generator polynomial
This code has minimal Hamming distance 15 and corrects 7 errors, it has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.
General BCH codes[edit]
General BCH codes differ from primitive narrowsense BCH codes in two respects.
First, the requirement that be a primitive element of can be relaxed. By relaxing this requirement, the code length changes from to the order of the element
Second, the consecutive roots of the generator polynomial may run from instead of
Definition. Fix a finite field where is a prime power. Choose positive integers such that and is the multiplicative order of modulo
As before, let be a primitive th root of unity in and let be the minimal polynomial over of for all The generator polynomial of the BCH code is defined as the least common multiple
Note: if as in the simplified definition, then is 1, and the order of modulo is Therefore, the simplified definition is indeed a special case of the general one.
Special cases[edit]
 A BCH code with is called a narrowsense BCH code.
 A BCH code with is called primitive.
The generator polynomial of a BCH code has coefficients from In general, a cyclic code over with as the generator polynomial is called a BCH code over The BCH code over and generator polynomial with successive powers of as roots is one type of Reed–Solomon code where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of .^{[6]} The other type of Reed Solomon code is an original view Reed Solomon code which is not a BCH code.
Properties[edit]
The generator polynomial of a BCH code has degree at most . Moreover, if and , the generator polynomial has degree at most .
Proof


Each minimal polynomial has degree at most . Therefore, the least common multiple of of them has degree at most . Moreover, if then for all . Therefore, is the least common multiple of at most minimal polynomials for odd indices each of degree at most . 
A BCH code has minimal Hamming distance at least .
Proof


Suppose that is a code word with fewer than nonzero terms. Then Recall that are roots of hence of . This implies that satisfy the following equations, for each : In matrix form, we have The determinant of this matrix equals The matrix is seen to be a Vandermonde matrix, and its determinant is which is nonzero. It therefore follows that hence 
A BCH code is cyclic.
Proof


A polynomial code of length is cyclic if and only if its generator polynomial divides Since is the minimal polynomial with roots it suffices to check that each of is a root of This follows immediately from the fact that is, by definition, an th root of unity. 
Encoding[edit]
This section is empty. You can help by adding to it. (March 2013) 
Decoding[edit]
There are many algorithms for decoding BCH codes; the most common ones follow this general outline:
 Calculate the syndromes s_{j} for the received vector
 Determine the number of errors t and the error locator polynomial Λ(x) from the syndromes
 Calculate the roots of the error location polynomial to find the error locations X_{i}
 Calculate the error values Y_{i} at those error locations
 Correct the errors
During some of these steps, the decoding algorithm may determine that the received vector has too many errors and cannot be corrected. For example, if an appropriate value of t is not found, then the correction would fail. In a truncated (not primitive) code, an error location may be out of range. If the received vector has more errors than the code can correct, the decoder may unknowingly produce an apparently valid message that is not the one that was sent.
Calculate the syndromes[edit]
The received vector is the sum of the correct codeword and an unknown error vector The syndrome values are formed by considering as a polynomial and evaluating it at Thus the syndromes are^{[7]}
for to Since are the zeros of of which is a multiple, Examining the syndrome values thus isolates the error vector so one can begin to solve for it.
If there is no error, for all If the syndromes are all zero, then the decoding is done.
Calculate the error location polynomial[edit]
If there are nonzero syndromes, then there are errors; the decoder needs to figure out how many errors and the location of those errors.
If there is a single error, write this as where is the location of the error and is its magnitude. Then the first two syndromes are
so together they allow us to calculate and provide some information about (completely determining it in the case of Reed–Solomon codes).
If there are two or more errors,
It is not immediately obvious how to begin solving the resulting syndromes for the unknowns and First step is finding locator polynomial
 compatible with computed syndromes and with minimal possible
Two popular algorithms for this task are:
Peterson–Gorenstein–Zierler algorithm[edit]
Peterson's algorithm is the step 2 of the generalized BCH decoding procedure. Peterson's algorithm is used to calculate the error locator polynomial coefficients of a polynomial
Now the procedure of the Peterson–Gorenstein–Zierler algorithm.^{[8]} Expect we have at least 2t syndromes s_{c},...,s_{c+2t−1}. Let v = t.
 Start by generating the matrix with elements that are syndrome values
 Generate a vector with elements
 Let denote the unknown polynomial coefficients, which are given by
 Form the matrix equation
 If the determinant of matrix is nonzero, then we can actually find an inverse of this matrix and solve for the values of unknown values.
 If then follow
if then declare an empty error locator polynomial stop Peterson procedure. end set continue from the beginning of Peterson's decoding by making smaller
 After you have values of , you have with you the error locator polynomial.
 Stop Peterson procedure.
Factor error locator polynomial[edit]
Now that you have the polynomial, its roots can be found in the form by brute force for example 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.
The zeros of Λ(x) are α^{−i1}, ..., α^{−iv}.
Calculate error values[edit]
Once the error locations are known, the next step is to determine the error values at those locations; the error values are then used to correct the received values at those locations to recover the original codeword.
For the case of binary BCH, (with all characters readable) 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 can be determined by solving the linear system
Forney algorithm[edit]
However, there is a more efficient method known as the Forney algorithm.
Let
And the error evaluator polynomial^{[9]}
Finally:
where
Than if syndromes could be explained by an error word, which could be nonzero only on positions , then error values are
For narrowsense BCH codes, c = 1, so the expression simplifies to:
Explanation of Forney algorithm computation[edit]
It is based on Lagrange interpolation and techniques of generating functions.
Consider and for the sake of simplicity suppose for and for Then
We want to compute unknowns and we could simplify the context by removing the terms. This leads to the error evaluator polynomial
Thanks to we have
Thanks to (the Lagrange interpolation trick) the sum degenerates to only one summand for
To get we just should get rid of the product. We could compute the product directly from already computed roots of but we could use simpler form.
we get again only one summand in
So finally
This formula is advantageous when one computes the formal derivative of form
yielding:
where
Decoding based on extended Euclidean algorithm[edit]
An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama's adaptation of the Extended Euclidean algorithm.^{[10]} Correction of unreadable characters could be incorporated to the algorithm easily as well.
Let be positions of unreadable characters. One creates polynomial localising these positions Set values on unreadable positions to 0 and compute the syndromes.
As we have already defined for the Forney formula let
Let us run extended Euclidean algorithm for locating least common divisor of polynomials and The goal is not to find the least common divisor, but a polynomial of degree at most and polynomials such that Low degree of guarantees, that would satisfy extended (by ) defining conditions for
Defining and using on the place of in the Fourney formula will give us error values.
The main advantage of the algorithm is that it meanwhile computes required in the Forney formula.
Explanation of the decoding process[edit]
The goal is to find a codeword which differs from the received word minimally as possible on readable positions; when expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of nonzeros on readable positions. Syndrom restricts error word by condition
We could write these conditions separately or we could create polynomial
and compare coefficients near powers to
Suppose there is unreadable letter on position we could replace set of syndromes by set of syndromes defined by equation Suppose for an error word all restrictions by original set of syndromes hold, than
New set of syndromes restricts error vector
the same way the original set of syndromes restricted the error vector Note, that except the coordinate where we have an is zero, if For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by
In polynomial formulation, the replacement of syndromes set by syndromes set leads to
Therefore,
After replacement of by , one would require equation for coefficients near powers
One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates. If denotes the polynomial eliminating the influence of these coordinates, we obtain
In Euclidean algorithm, we try to correct at most errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for we are looking for, the equation must hold for coefficients near powers starting from
In Forney formula, could be multiplied by a scalar giving the same result.
It could happen that the Euclidean algorithm finds of degree higher than having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting of higher degree, we decide not to correct the errors. Correction could fail in the case has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.
Correct the errors[edit]
Using the error values and error location, correct the errors and form a corrected code vector by subtracting error values at error locations.
Decoding examples[edit]
Decoding of binary code without unreadable characters[edit]
Consider a BCH code in GF(2^{4}) with and . (This is used in QR codes.) Let the message to be transmitted be [1 1 0 1 1], or in polynomial notation, The "checksum" symbols are calculated by dividing by and taking the remainder, resulting in or [ 1 0 0 0 0 1 0 1 0 0 ]. These are appended to the message, so the transmitted codeword is [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].
Now, imagine that there are two biterrors in the transmission, so the received codeword is [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In polynomial notation:
In order to correct the errors, first calculate the syndromes. Taking we have and Next, apply the Peterson procedure by rowreducing the following augmented matrix.
Due to the zero row, S_{3×3} is singular, which is no surprise since only two errors were introduced into the codeword. However, the upperleft corner of the matrix is identical to [S_{2×2}  C_{2×1}], which gives rise to the solution The resulting error locator polynomial is which has zeros at and The exponents of correspond to the error locations. There is no need to calculate the error values in this example, as the only possible value is 1.
Decoding with unreadable characters[edit]
Suppose the same scenario, but the received word has two unreadable characters [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynom reflecting their positions We compute the syndromes and (Using log notation which is independent on GF(2^{4}) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. Hexadecimal description of the powers of are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)
Let us make syndrome polynomial
compute
Run the extended Euclidean algorithm:
We have reached polynomial of degree at most 3, and as
we get
Therefore,
Let Don't worry that Find by brute force a root of The roots are and (after finding for example we can divide by corresponding monom and the root of resulting monom could be found easily).
Let
Let us look for error values using formula
where are roots of We get
Fact, that should not be surprising.
Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].
Decoding with unreadable characters with a small number of errors[edit]
Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].
Again, replace the unreadable characters by zeros while creating the polynom reflecting their positions Compute the syndromes and Create syndrome polynomial
Let us run the extended Euclidean algorithm:
We have reached polynomial of degree at most 3, and as
we get
Therefore,
Let Don't worry that The root of is
Let
Let us look for error values using formula where are roots of polynomial We get
The fact that should not be surprising.
Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].
Citations[edit]
 ^ Reed & Chen 1999, p. 189
 ^ Hocquenghem 1959
 ^ Bose & RayChaudhuri 1960
 ^ "Phobos Lander Coding System: Software and Analysis" (PDF). Retrieved 25 February 2012.
 ^ "Sandforce SF2500/2600 Product Brief". Retrieved 25 February 2012.
 ^ Gill n.d., p. 3
 ^ Lidl & Pilz 1999, p. 229
 ^ Gorenstein, Peterson & Zierler 1960
 ^ Gill n.d., p. 47
 ^ Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975.
References[edit]
Primary sources[edit]
 Hocquenghem, A. (September 1959), "Codes correcteurs d'erreurs", Chiffres (in French), Paris, 2: 147–156
 Bose, R. C.; RayChaudhuri, D. K. (March 1960), "On A Class of Error Correcting Binary Group Codes", Information and Control, 3 (1): 68–79, doi:10.1016/s00199958(60)902874, ISSN 08905401
Secondary sources[edit]
 Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, retrieved April 21, 2010^{[dead link]} Course notes are apparently being redone for 2012: http://www.stanford.edu/class/ee387/
 Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal (1960), "TwoError Correcting BoseChaudhuri Codes are QuasiPerfect", Information and Control, 3 (3): 291–294, doi:10.1016/s00199958(60)908779
 Lidl, Rudolf; Pilz, Günter (1999), Applied Abstract Algebra (2nd ed.), John Wiley
 Reed, Irving S.; Chen, Xuemin (1999), ErrorControl Coding for Data Networks, Boston, MA: Kluwer Academic Publishers, ISBN 0792385284
Further reading[edit]
 Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0521553741
 Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (2nd ed.), John Wiley
 Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: PrenticeHall
 MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of ErrorCorrecting Codes, New York, NY: NorthHolland Publishing Company
 Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, archived from the original on 20100702, retrieved April 21, 2010