Error Correction Coding Receiver - Part 4

Back to the problem of decoding a linear block code with multiple correctable bits.

From page 15 of this [pdf] description mentioned in Part 3, there is a set of minimal polynomials for any particular system. These can be looked up in a table. This example shows three unique equations for the system of six syndrome equations for a triple error correcting code:

m1(x) = m2(x) = m4(x) = x^5 + x^2 + 1

m3(x) = m6(x) = x^5 + x^4 + x^3 + x^2 + 1

m5(x) = x^5 + x^4 + x^2 + x + 1

The syndrome vector can be obtained by taking the received codeword v(x) modulo with each of the minimal polynomials.

With the LFSR, it is a simple matter of setting the reduction polynomial to each of the minimal polynomials, shifting in the codeword, and saving the result as S1(x), S2(x), and so on.

Next, a system of equations in α is needed. This is achieved by taking S1(α), S2(α^2), S3(α^3) ... S6(α^6). Replacing x with α^i is the same as spreading out the "bits" in the polynomial in x with (i - 1) zeroes in between, and taking the result modulo the reduction polynomial for this field.

In this example, that means S1 just replaces x with α. S2 through S6 can each be fed into an LFSR with the spacing mentioned above, and with the reduction polynomial set appropriately. In this case that is x^5 + x^2 + 1.

Example: If S3(x) = x^3 + x^2 + 1, then feed in x^9 + x^6 + 1. Binary 01101 becomes 1001000001. The bolded zeroes show which ones were inserted to get the equation in α. This is fed into the LFSR to reduce it to fit in the field.

Now there is a set of six equations in α. We are ready for the Berlekamp-Massey algorithm.