FAST DECODE CHARACTER ERROR DETECTION AND CORRECTION SYSTEM

• US 3,668,632 A
• Filed: 02/13/1969
• Issued: 06/06/1972
• Est. Priority Date: 02/13/1969
• Status: Expired due to Term

• Current Assignee: Ira B. Oldham III
• Original Assignee: Ira B. Oldham III
• Inventors: Oldham, Ira B. III
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Dildine, Jr., R. Stephen
• Application Number:
  US04/798,976
• Time in Patent Office: 1,209 Days
• Field of Search: 340/146.1
• US Class Current: 714/775
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

Apparatus for detecting and correcting errors in a digital computer storage system is disclosed. Data is encoded using a generalized Reed-Solomon encoder. Error detection circuitry including power sum calculating devices are used for detection of data in error. The error correction portion of the invention includes an improved decoding scheme for determining the location and magnitudes of errors within the data and has a very low average correction time. Means are provided for determining the starting area of a data block in the presence of errors in the starting area. Further means are provided for detecting a cyclic shift in a data character which, under normal conditions, would appear as an acceptable code word even though in error.

Claims

1. In an error detection and correction system, the combination of:

means for encoding data blocks by adding redundancy according to a non-random code, each said data block having an identifier near the end thereof;

means for decoding said encoded data blocks and providing an indication of any error detected therein;

.

2. actuating control connections in a decoder to segregate Nu sets of first signals from combinations of components of said error syndrome, said Nu sets of first signals representative of elementary symmetric functions sigma i, and Nu being a selected integral value less than or equal to the maximum number of errors correctable by said code;

3. In an error detection and correction system, the combination of:

means for encoding characters with a non-random code to form an encoded data block comprising characters having a number of bits, said encoding means including means for inverting at least one bit of said encoded data block;

means for checking errors in said encoded data block; and

, means for re-inverting said at least one inverted bit prior to the operation of said error checking means on said at least one inverted bit.

4. actuating control connections in a decoder to segregate Nu sets of second signals from a combination of components of said error syndrome and said non-zero elements of step (3), said Nu sets of second signals indicative of error magnitudes.

5. The combination of claim 3 wherein said inverted bits are in the redundancy added according to said code.

6. The method of providing error correction of data comprising the steps of:

a. encoding characters of information to form an encoded information block having redundancy, by using a generator polynomial having Alpha 0 as a factor thereof, where Alpha 0 is the identity element of the Galois Field of qM elements; and

b. decoding said encoded information block by forming check sums such that the magnitude of the error for single error correction is obtained directly as one of said check sums.

7. In a data error detection and correction system, a data encoder comprising shift register means having as components thereof symmetrical multiplication means, each of which is connected to modulo-two adders in said shift register, for encoding information blocks in a generalized Reed-Solomon code having Alpha 0 as a factor of its generator polynomial.

8. The method of recording a pattern XnXX(n-1)X-XX2XX1X where X is the logical complement of X, and n is the number of times X is repeated, including the steps of:

decoding n sequences of clock pulses, each of said sequences being of length j, where j successively varies from n to ((n+

     1)-(n-

     1)) ; and

recording for each sequence decoded, a number of bits of a first logical state followed by a single bit of the complement logical state to said first logical state, said number of bits of said first logical state being of length equal to one less than the length of said decoded sequence.

9. In a data error detection and correction system, wherein data is encoded in a non-random code, the combInation of:

a plurality of power sum calculating means for computing a residue from encoded data;

means for determining the error magnitude and error location for single error correction, said last-named means including apparatus for performing Galois Field arithmetic to obtain the error location, and means for obtaining the error magnitude as the direct output of one of said power sum calculators.

10. The combination of claim 9 wherein said apparatus for performing Galois Field arithmetic includes:

means for determining the logarithm to the base Alpha of specified power sums;

means for providing an output indicative of the difference modulo qM between said logarithms where qM is the number of elements in said Galois Field and Alpha is the primitive element of said field; and

means for translating said output to a physical storage address which contains said single error.

11. In a data error detection and correction system wherein data is encoded according to a non-random code and decoded to obtain a residue from said encoded data, the combination of:

decoding means for obtaining elementary symmetric functions from particular components of said residue;

detection means for determining the elements of the Galois Field of qM elements which force to zero the function where Nu is the number of elementary symmetric functions, sigma i are the elementary symmetric functions, X are elements of the Galois Field qM, and Nu -i is greater than 2 polynomial divider means for reducing the polynomial by each of said elements of said Galois Field;

means for detecting that said polynomial has been reduced to a quadratic function;

means for solving said quadratic function and providing an indication that solutions have been reached or that no solutions are possible;

means for storing said solutions and said elements.

12. The combination of claim 11 further including decoding means for accepting said solutions and said elements and providing error magnitudes;

and means for providing error location numbers from said solutions and said elements.

13. The combination of claim 12 further including detection means for providing an indication that there are insufficient elements in said Galois Field to reduce said polynomial to a quadratic;

and gating means for supplying said last-named indication or said indication of no solution as a signal indicative of the fact that error correction is not possible.

14. In a data error detection and correction system wherein data is encoded in a non-random code, the process of determining error magnitudes and error locations including the steps of: