For coding schemes that can correct more than one error, things get more complicated. Instead of one syndrome vector, there will be 2t equations, where t is the number of correctable errors. A method called the Berlekamp-Massey algorithm is used to solve this system of equations to create an error locator polynomial.
Next, the roots of this polynomial must be found to indicate the location of up to t errors. Once these locations are known, the corrupted bits can be fixed.
A good description and example can be found here: [pdf]
I will attempt to write some code to implement the 31,16 BCH code that can correct up to 3 errors. There are 16 message bits and 15 parity bits which together make up a 31-bit codeword. It uses a polynomial x^5 + x^2 + 1 which generates a field of 32 elements. See the table starting on page 12 of the above link.
To implement this in hardware, a couple of math functions are needed. One is the mutiplying of primitive coefficients. This can be done by representing the coefficients as exponents, and they are multiplied by adding the exponents. For example, to multiply alpha^5 times alpha^11, add 5 and 11. This must be done mod 31 for this code, since any higher exponents are equivalent to the (mod 31) of that exponent. It is not very efficient to do a (mod 31) function in logic, and in any case, it is often not synthesizable with the mod operator (% symbol in Verilog.) A lookup table that handles adding and subtracting (mod 31) is fairly efficient and can be done in 22 slices on a Xilinx Virtex4 device. A result can be returned in one clock cycle.
Another operation is addition, which is done bitwise modulo 2. This is a simple XOR operation, but must be done on the tuple form of the coefficients. Therefore it is useful to have another lookup table that converts between the exponent and tuple forms. This can be realized in 11 slices of a Virtex4 device. For example, alpha^7 is equivalent to alpha^4 + alpha^2 and can be represented as binary 10100.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment