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.

Error Correction Coding Receiver - Part 2

The first thing needed to decode a linear block code in hardware is a Linear Feedback Shift Register (LFSR). To implement this in programmable logic, a generic block such as that shown below can be written. It is easily customizable for different generator polynomials by adding registers as needed, and by changing the generic parameter that describes the p0lynomial g, with the most-significant degree on the left. This example shows the polynomial

x^5 + x^4 + x^3 + 1.

The term x^5 is implied in the generic parameter since the length of the register is 5. Messages are shifted in and out most-significant-bit first (where the highest bit is the coefficient of the highest degree term in the polynomial.)

This code block has a mode with feedback enabled, and a shift-only mode for shifting out the result.

module lfsr(
   input    rst_n,
   input    clk,
   input   d,
   input    en,
   input   calc_shft_n,
   output    q
);

reg [4:0] shift;

parameter g = 5'b11001;


assign q = shift[4];

always @(posedge clk or negedge rst_n)
    if (!rst_n)
        shift <= 5'b00000;
    else
        if (en)
            if (calc_shft_n) begin
                shift[0] <= d ^ shift[4];
                shift[1] <= shift[0] ^ (shift[4] & g[1]);
                shift[2] <= shift[1] ^ (shift[4] & g[2]);
                shift[3] <= shift[2] ^ (shift[4] & g[3]);
                shift[4] <= shift[3] ^ (shift[4] & g[4]);
            end
            else begin
                shift[0] <= d;
                shift[1] <= shift[0];
                shift[2] <= shift[1];
                shift[3] <= shift[2];
                shift[4] <= shift[3];
            end
endmodule