An error correcting system transforms a degree-five error locator polynomial sigma (x) into the polynomial w(y)=y5=b2y2+b1y+b0, where b1=0 or 1, and y= sigma (x), and determines the roots of sigma (x) based on the roots of w(y). The polynomial w(y) has (2M)2 solutions over GF(2M), rather than (2M)5 solutions, since for any solution with b2=h2, b0=h0 and b1=1, there is no such solution with b2=h2, b0=h0 and b1=0. Conversely, if there is such a solution with b1=0 there are no such solutions with b1=1. The system can thus use a table that has 22M entries and is addressed by {b2, b0}. The table produces roots y=ri, i=0, 1, 2, 3, 4, and the system then transforms the roots y=ri to the roots of sigma (x) by calculating x= sigma -1(y). To further reduce the overall table storage needs, the table may include in each entry four roots ri, i=0, 1, 2, 3, and the system then calculates the associated fifth root r4 by adding the stored roots. The size of the look-up table can be even further reduced by (i) segmenting the Galois Field (2M) into conjugate classes; (ii) determining which of the classes contain values of b0 that correspond to solutions of w(y) with five distinct roots; (iii) representing each of these classes, respectively, by a single value of b0'=(b0)2k; and (iv) including in the table for each class only those solutions that correspond to representative values of b0'. The table then contains a relatively small number of sets of roots of each of the classes, with each set associated with a particular value of b2'=b22k. The roots of w(y) are determined by finding the value of k that produces b0' and b2', entering the look-up table using {b0', b2'}, raising the roots ri' produced by the table to the power -2k to produce y=ri, and then transforming the result into the roots of sigma (x) by x= sigma -1(y).
展开▼
