BCH CODE

A BCH (Bose-Chaudhuri-Hochquenghem) code is a multilevel, cyclic, error-correcting, variable-length digital code used to correct errors up to approximately 25% of the total number of digits.

Note: BCH codes are not limited to binary codes, but may be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number, such as 2, 3, 4, 5, 7, 8, 11, and 13. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign digit.

BCH codes make use of field theory and polynomials over that field. The way the check polynomial is constructed provides the key to indicating that an error has occurred.

If we wish to construct a BCH code to detect and correct 2 errors we use the field GF(16) or Z₂[x]/<x⁴+x+1>

Now if we have α a root of x⁴+x+1, m₁(x)=x⁴+x+1. Now m₁ is minimal for α since

m₁(x)=(x-α)(x-α²)(x-α⁴)(x-α⁸)=x⁴+x+1.

If we wish to construct a code to correct 1 error we use m₁(x). Our codewords will be

C(x)≡0 (mod m₁(x))

which has roots α, α², α⁴, α⁸.

This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α³, and then the minimal polynomial for this is

m₃(x)=x⁴+x³+x²+x+1.

which has roots α, α⁶, α¹², α²⁴=&alpha⁹.

We take codewords having all of these as roots, so we form the polynomial

m_1,3(x)=m₁(x)m₃(x)=x⁸+x⁷+x⁶+x⁴+1

and take coodewords corresponding to polynomials of degree 14 such that

C(x)≡0 (mod m_1,3(x))

So now C(α)=C(α²)=...=C(α⁸)=0. (*)

Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*).

Encoding

Construct our information codeword as

(c₁₄, c₁₃, ..., c₈)

so our polynomial will be

c₁₄+c₁₃+...+c₈

Call this C_I.

We then want to find a C_R such that C_R=C_I (mod m_1,3(x))=c₇+c₆+...+c₀

So we have the following codeword to send C(x) = C_I+C_R (mod m_1,3(x)) = 0

For example, if we are to encode (1,1,0,0,1,1,0)

C_I=x¹⁴+x¹³+x¹⁰+x⁹

and using polynomial long division of m_1,3(x) and C_I to get C_R(x), in Z₂ we obtain C_R to be

x³+1

So then the codeword to send is

(1,1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1)

Decoding

Suppose we receive a codeword vector r (the polynomial R(x)).

If there is no error R(α)=R(α³)=0

If there is one error, ie r=c+e_i where e_i represents the ith basis vector for R¹⁴

So then

S₁=R(α)=C(α)+αⁱ=αⁱ

S₃=R(α³)=C(α³)+(α³)ⁱ

=(αⁱ)³=S₁³

so we can recognize one error. A change in the bit position shown by α's power will aid us correct that error.

If there are two errors

r=c+e_i+e_j

then

S₁=R(α)=C(α)+αⁱ+α^j

S₃=R(α³)=C(α³)+(α³)ⁱ+(α³)^j

= (α³)ⁱ+(α³)^j

which is not the same as S₁³ so we can recognize two errors. Further algebra can aid us in correcting these two errors.

Original source (first two paragraphs) from Federal Standard 1037C

Synonym: BCH CODE

Synonym by domain: bose (electrical engineering).