Five-error correction system

Details Five-error correction system Five-error correction system

1997-12-03

1999-11-02

Baker, Stephen M.

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

714759, 714782, H03M 1300

Patent

active

059789565

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).

REFERENCES:
patent: 5710782 (1998-01-01), Weng
patent: 5905740 (1999-05-01), Williamson

Affiliated with

Also associated with

Rating

Five-error correction system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Five-error correction system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Five-error correction system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2151426