| BCH
Codes Overview of BCH codes The BCH family of codes is an Error Correcting Code that enables a limited number of errors to be detected and corrected. BCH codes were discovered independently by Bose and Ray Choudhury in 1960 and Hocquenghem in 1959. Basic Concepts The concepts and theories are very much involved with number theory and advanced linear algebra knowledge that are quite abstract. Some definitions: Galois Fields GF(q) is a field with q elements, also called a finite field because there are a finite number (q) of elements. A Primitive Element of GF(q) is an element asuch that every field element except zero can be expressed as a power of a . Each Galois Field has at least one primitive element. If q = 2m, where m is any integer, the elements of the field can be represented by polynomials whose co-efficients are elements of the field GF(2) i.e 0 and 1. The primitive element of such a field would itself be such a polynomial. The block length of the code is n = 2m-1 The error correcting capability of the code is bounded by t < (2m 1)/2 Encoding: The idea is to create a codeword which contains two parts : a remainder part for checking and the message part. To generate the complete codeword, the data part (the part that is to be encoded) is divided by a generator polynomial to get the remainder part, just as in ordinary polynomial division modulo 2. The number of bits assigned for the remainder is decided by first estimating the probability of error on the channel. The encoding scheme can be summarized in the following steps: Choose the degree m and the corresponding primitive polynomial p(x) and construct Galois Field GF(2m) Obtain a generator polynomial. Determine remainder Left shift data bits by number of bits assigned for remainder. Append remainder to data to get a complete code word. To encode a source message u(X) using a BCH code with generator polynomial g(X), the parity check symbols are found using the formula: b(X) = Xn-ku(X)( mod g(X) ) The encoded code word is : v(X) = Xn-k u(X) + b(X) BCH Decoder Suppose a valid codeword to be : v(X) = v0 + v1X + + vn-1 Xn-1 and the received codeword: r(X) = r0 + r1X + + rn-1 X n-1 The error pattern is : e(X) = r(X) vc(X) = e0 + e1X + + en-1 Xn-1. To determine the error vector, the received code word is passed through the decoding algorithm that is summarized below: First the syndrome set S ={S1, S2, , S2t} is computed. Each Syndrome is computed as : Si=r(ai) The error locator polynomial s(X) is found using the Berlekamp-Massey algorithm described in the next section. The error location numbers b1 through bnu are found by finding the inverses of the roots of s(X). Once the locations of the errors are known, the received code word can be corrected to obtain the correct code word. BCH codes for Data Synchronization The host that has the most up-to-date data set computes its characteristic vector and determines its syndrome by applying the BCH decoding algorithm. This syndrome is then broadcast to all other hosts on the network that need to be synchronized. Each host calculates their syndromes for their own characteristic vectors. Each host now adds (modulo 2 which is equivalent to XORing) its own syndrome and the syndrome it received The resultant syndrome when decoded determines the error locator polynomial, which indicates the location of errors in the characteristic vector formed by the addition (modulo 2) of the two characteristic vectors.. The error locator polynomial when added (modulo 2 ) to the characteristic vector determined by the target host results in a characteristic vector that exactly resembles the characteristic vector of the host with the most up-to-date data set. The extraction of the set elements from the characteristic vector is a trivial problem. It has to be borne in mind however that the maximum number of differences between the sets is bounded by the error correcting capability of the code |