Five-error correction system

Abstract

An error correcting system transforms a degree-five error locator polynomial .sigma.(x) into the polynomial w(y)=y.sup.5 =b.sub.2 y.sup.2 +b.sub.1 y+b.sub.0, where b.sub.1 =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 (2.sup.M).sup.2 solutions over GF(2.sup.M), rather than (2.sup.M).sup.5 solutions, since for any solution with b.sub.2 =h.sub.2, b.sub.0 =h.sub.0 and b.sub.1 =1, there is no such solution with b.sub.2 =h.sub.2, b.sub.0 =h.sub.0 and b.sub.1 =0. Conversely, if there is such a solution with b.sub.1 =0 there are no such solutions with b.sub.1 =1. The system can thus use a table that has 2.sup.2M entries and is addressed by {b.sub.2, b.sub.0 }. The table produces roots y=r.sub.i, i=0, 1, 2, 3, 4, and the system then transforms the roots y=r.sub.i to the roots of .sigma.(x) by calculating x=.sigma..sup.-1 (y). To further reduce the overall table storage needs, the table may include in each entry four roots r.sub.i, i=0, 1, 2, 3, and the system then calculates the associated fifth root r.sub.4 by adding the stored roots. The size of the look-up table can be even further reduced by (i) segmenting the Galois Field (2.sup.M) into conjugate classes; (ii) determining which of the classes contain values of b.sub.0 that correspond to solutions of w(y) with five distinct roots; (iii) representing each of these classes, respectively, by a single value of b.sub.0 '=(b.sub.0).sup.2.spsp.k ; and (iv) including in the table for each class only those solutions that correspond to representative values of b.sub.0 '. 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 b.sub.2 '=b.sub.2.sup.2.spsp.k. The roots of w(y) are determined by finding the value of k that produces b.sub.0 ' and b.sub.2 ', entering the look-up table using {b.sub.0 ', b.sub.2 '}, raising the roots r.sub.i ' produced by the table to the power -2.sup.k to produce y=r.sub.i, and then transforming the result into the roots of .sigma.(x) by x=.sigma..sup.-1 (y).