US3668632A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast decode character error detection and correction system
Assignee: International Business Machines Corp
•
Filing: 1969-02-13
•
Granted: 1972-06-06
•
Expires: 1989-02-13
Abstract
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.
Inventors
- 👤 Ira B Oldham
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 02:32
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/1008
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
50 words
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;.
Claim 2
Dependent Claim
50 words
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;.
Claim 3
Dependent Claim
30 words
The combination of claim 1 wherein said indication comprises a component contributed by an error in said identifier and a component contributed by an error syndrome generated by said code.
Claim 4
Dependent Claim
55 words
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;
Claim 5
Dependent Claim
55 words
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;
Claim 6
Dependent Claim
24 words
actuating apparatus for determining each of the non-zero elements of the Galois Field of qM elements which force the polynomial to be zero; and
Claim 7
Dependent Claim
24 words
actuating apparatus for determining each of the non-zero elements of the Galois Field of qM elements which force the polynomial to be zero; and
Claim 8
Dependent Claim
82 words
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.
Claim 9
Dependent Claim
82 words
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.
Claim 10
Dependent Claim
33 words
The combination of claim 3 wherein the number of bits inverted encoder is equal to at least N/2 where N is a number greater than the maximum error correction capability of said code.
Claim 11
Dependent Claim
39 words
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.
Claim 12
Dependent Claim
39 words
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.
Claim 13
Dependent Claim
18 words
The combination of claim 3 wherein said inverted bits are in the redundancy added according to said code.
Claim 14
Independent Claim
82 words
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.
Claim 15
Independent Claim
82 words
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.
Claim 16
Dependent Claim
53 words
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.
Claim 17
Dependent Claim
53 words
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.
Claim 18
Independent Claim
107 words
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.
Claim 19
Independent Claim
107 words
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.
Claim 20
Dependent Claim
79 words
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.
Claim 21
Dependent Claim
79 words
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.
Claim 22
Dependent Claim
77 words
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.
Claim 23
Dependent Claim
151 words
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.
Claim 24
Dependent Claim
151 words
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.
Claim 25
Dependent Claim
33 words
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.
Claim 26
Dependent Claim
56 words
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.
Claim 27
Dependent Claim
29 words
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:
Claim 28
Dependent Claim
29 words
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:
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-06-06 | 1975-12-06 | 1976-06-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-06-06 | 1979-12-06 | 1980-06-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-06-06 | 1983-12-06 | 1984-06-06 | $7700.00 | Window Closed / Lapsed |