Improved Decoding Algorithm for BCH Code

INTRODUCTION

The BCH codes are a class of error-correcting codes possessing strict algebraic architecture and are easy to construct (Peterson, 1960). The BCH codes are widely used in data transmission due to its powerful correction abilities especially the performance of short codes closing to theory values (Seddiki et al., 2008).

In all the iterative decoding algorithms for binary BCH code, the Berlekamp-Masssey iterative algorithm and Chien’s search algorithm are the most efficient (Blake et al., 1998; Penzhorn, 1993). However, both of them need complex algebraic operation and iterative operation. Another algebraic decoding method, known as the step-by-step decoding method was presented and improved for the general cases of BCH codes (Chr et al., 2004; Xiaobei et al., 2007). The method is less complex since it avoids calculating the coefficients of error location polynomial and searching the roots. However the decoding speed is not fast enough. Then the arithmetic algorithm based on look-up table (Hung et al., 1999) was proposed, which has fast decoding speed and is simple in structure and easy in implementation. The drawback of this algorithm is that it requires a great deal of EMS memory.

To avoid this problem, A weight method (Ozkan and Ozkan, 2002) using a reduced look-up table to decode the three possible errors in (15,5,7) BCH code is proposed by Lee et al. (2008) and Chang et al. (2008). The data in his reduced look-up table consists of syndrome patterns and corresponding error patterns which only have one and two errors occurred in the message block of the received codeword. It can greatly reduce the memory size, but it is restricted to the situation that one error occurred in the message block and two errors occurred in the parity check block. The algorithm proposed in this study needs so many circulations that the computing time is increasing enormously. To resolve the issue a modified decoding algorithm also based on look-up table and hamming weight is developed in this study. In the algorithm the look-up table consists of syndrome patterns and corresponding error patterns of the codeword which has one to three errors occurred in the message block. Compared with Lee’s table, our method increases only a few memory cells but the decoding speed can be significantly improved. The decoding algorithm just needs some addition (modulo 2) with the look-up table and computation of the weight of the word. Therefore, the decoder based on this algorithm is simpler, taking fewer memory cells and suitable for hardware implementation.

BACKGROUND OF ENCODING AND DECODING FOR BINARY BCH CODE

Coding theory of binary BCH code: For any integer m≥3 and t<2^m-1 it exists a primitive BCH code with the parameters: n = 2^m-1, n-k≤2t+1, d_min≥2t+1. This code can correct t or fewer errors over a span of 2^m-1 bit positions.

Supposing the generator polynomial is g(x), each of the code polynomial c(x) is a multiple of g(x) and can be expressed as c(x) = m(x) g(x), where, m(x) is the message polynomial whose coefficients form the message vector m. If the generator matrix is G, the codeword can also be achieved by c = mxG.

Suppose a codeword c is transmitted over a noise channel, the received codeword is then r = c+e, where, e is the error pattern induced by the noisy channel. The decoding procedure mainly includes three parts: (1) Syndrome computation, (2) detemination of error pattern and (3) error correction.

Decoding algorithm with traditional look-up table: Take binary (15,5,7) BCH code as the example, the system generator matrix of (15,5,7) BCH code is:

And the parity check matrix is:

From the matrix above, we can see the generator matrix version is G = [I_k P], so the first five bits of the generated codeword is the message block and the remaining is the parity check block. If the codeword c = (c₁ c₂ .... c₁₅) is transmitted, then the received codeword is r = c+e, where, is the error pattern.

The calculating formula of the syndrome is S = rxH^T = exH^T. From the calculating formula, we can see that if S = 0, then e₁ e₂ .... e₁₅ are all equal to zero, it means there is no error happened in the received codeword. And if S ≠ 0, then e₁ e₂ .... e₁₅ are not all equal to zero, it means there is at least one error happened in the received codeword. The relationship between the syndrome and the parity check matrix is that if there is one error in the location i of the codeword, the S will be the same as the i'th column in H and if there are two errors in the location i and j of the codeword, the S will be the summation (modulo 2) of the i'th and j'th column in H and similar rules apply to the situation when there are three errors. Then all the syndrome patterns and corresponding error patterns are stored in the look-up table. The decoding process is to compute S first and look for the same data in the look-up table one by one, finally use the selected error pattern to correct errors. For (15,5,7) BCH code, there are all 575 syndrome patterns and corresponding error patterns stored in the traditional look-up table.

IMPROVED DECODING ALGORITHM

The look-up table used in this improved algorithm consists of syndrome patterns and corresponding error patterns which have one to three errors occurred in the message block of the codeword. Then the look-up table contains only 25 syndrome patterns and corresponding error patterns. Suppose that there are only three or less errors occurred in (15,5,7) BCH codeword. Due to the latter part of H is a 10x10 identity matrix and S = eH^T, if the weight of S w(S)≤3, it means at most three errors only occurred in the parity check block and the location of 1 in S is just the error location in the parity check block. Then shift the syndrome right 5 bits to form a 15-bit length word and minus (modulo 2) the received codeword to decode. If w(S)≥4, it means at least one error occurred in the message block. First, the syndrome minus (modulo 2) all syndrome patterns in the table to obtain the difference and compute the weight of these difference, respectively. Then we will discuss the errors location in three possible conditions: (1) One error in the message block and two or less errors in the check block, the weight of the corresponding difference will be the number of errors occurred in the parity check block. (2) Two errors in the message block and one or no error in the check block, the weight of the corresponding difference will be one or zero. (3) Three errors in the message block and no error in the check block, the weight of the corresponding difference will be zero. Also, the location of 1 in the difference is just the error location in the parity check block. At last shift the certain difference right 5 bit to form a 15-bit length word, then minus (modulo 2) the received codeword and minus (modulo 2) the corresponding error pattern to decode.

The proposed decoding algorithm for (15,5,7) BCH code is presented as follows:

Fig. 1:	The flowchart of the algorithm

The flowchart of this algorithm is shown in Fig. 1.

Give an example: There is a simple example to expatiate the whole decoding process.

A message m = (0 0 0 0 1) is encoded into a codeword c = (0 0 0 0 1 1 1 0 1 1 0 0 1 0 1) by an encoder. If the received codeword is r = (1 0 0 0 1 0 1 0 1 1 1 0 1 0 1), then the decoding procedure is:

Step 1:	Receive the codeword r = (1 0 0 0 1 0 1 0 1 1 1 0 1 0 1)
Step 2:	Compute S = (0 1 1 0 1 0 0 0 1 0) and w(S) = 4
Step 3:	w(S)≠0, go to step 4
Step 4:	w(S)>3, go to step 5
Step 5:	Compute all Sd and their weight w(Sd)
Step 6:	w(Sd1) = 2=3, Choose the certain Sd' = Sd1 =(1 0 0 0 0 1 0 0 0 0) and the corresponding e' = (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
Step 7:	Compute c = (1 0 0 0 1 0 1 0 1 1 1 0 1 0 1) - ((1 0 0 0 0 1 0 0 0 0)>>5) - (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0) = (0 0 0 0 1 1 1 0 1 1 0 0 1 0 1) then go to end