US5226043A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for data error detection and correction and address error detection in a memory system
Assignee: Raytheon Co
•
Filing: 1990-12-27
•
Granted: 1993-07-06
•
Expires: 2010-12-27
Abstract
Abstract An error detection and correction apparatus and method in a memory system for performing single symbol error correction and at least double symbol error detection of data errors and single symbol error detection and at least double symbol error detection of addressing errors using a modified Reed Solomon code. A first of three parity symbols in a codeword is used to determine the value of a single symbol error, if any, over a memory word comprising data symbols and its corresponding address comprising address symbols. A second parity symbol is used to locate a single symbol error, and a third parity symbol is used to detect at least two errors in the data and address symbols. The three parity symbols are used to generate syndromes which determine if there is an error and what corrective action to take. In calculating product terms for the modified Reed Solomon code, a technique of bit padding that requires no additional memory is used to match the number of bits needed in the Reed Solomon code data symbols to the bit width of a memory chip of a memory array in the memory system.
Inventors
- 👤 Earle W. Pughe, Jr.
- 👤 Robert P. Landstrom
- 👤 H. Frank Howes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 13:27
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1012; G06F11/1016; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; G06F11/1028
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
175 words
A combination for detecting errors and providing correction information comprising: memory means for storing a codeword, including data symbols and parity symbols each of said symbols having multiple bits, into a location of said memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; means for generating said parity symbols of each codeword based on said data symbols and corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code, a first of said parity symbols determines an error value in said data symbols and corresponding address symbols, a second of said parity symbols provides for locating said error value in one of said data symbols and said corresponding address symbols, and a third of said parity symbols provides for detecting at least two symbol errors; and means coupled to said parity symbol generating means and said parity symbol outputs of said memory means for generating syndromes, said syndromes providing information to perform error detection and correction of said codeword.
Claim 2
Dependent Claim
175 words
A combination for detecting errors and providing correction information comprising: memory means for storing a codeword, including data symbols and parity symbols each of said symbols having multiple bits, into a location of said memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; means for generating said parity symbols of each codeword based on said data symbols and corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code, a first of said parity symbols determines an error value in said data symbols and corresponding address symbols, a second of said parity symbols provides for locating said error value in one of said data symbols and said corresponding address symbols, and a third of said parity symbols provides for detecting at least two symbol errors; and means coupled to said parity symbol generating means and said parity symbol outputs of said memory means for generating syndromes, said syndromes providing information to perform error detection and correction of said codeword.
Claim 3
Dependent Claim
32 words
The combination as recited in claim 1 wherein: said control signal causes said memory means to perform a write mode for storing said codeword or a read mode for reading said codeword.
Claim 4
Dependent Claim
44 words
The combination as recited in claim 2 wherein: said parity symbols generating means generates said parity symbols for said data symbols and corresponding address symbols when said memory means is performing said write mode and when said memory means is performing said read mode.
Claim 5
Dependent Claim
67 words
The combination as recited in claim 1 wherein: said parity symbol outputs from said memory means to said syndrome generating means when reading said codeword are compared to a second set of parity symbols, generated by said parity symbol generator means based on said data symbols being read and said corresponding address symbols, for determining a difference pattern for said error detection and correction of said codeword.
Claim 6
Dependent Claim
47 words
The combination as recited in claim 1 wherein: said syndrome generating means comprises means for generating a plurality of syndrome signals; and means coupled to said syndrome signals for interpreting said syndrome signals to identify a data symbol error and whether said data symbol error is correctable.
Claim 7
Dependent Claim
26 words
The combination as recited in claim 5 wherein: said interpreting means further comprises means for generating select signals to enable correction of said data symbol error.
Claim 8
Dependent Claim
42 words
The combination as recited in claim 5 wherein: said combination comprises means coupled to data symbols read from said memory means and one of said syndrome signals for performing symbol error correction in accordance with a select signal from said interpreting means.
Claim 9
Dependent Claim
41 words
The combination as recited in claim 1 wherein: said combination performs single data symbol error correction, double data symbol error detection, single address symbol error detection, double address symbol error detection, and single and double error detection in said parity symbols.
Claim 10
Dependent Claim
28 words
The combination as recited in claim 8 wherein: said apparatus further performs detection of any combination of two errors from said data symbols, address symbols and parity symbols.
Claim 11
Dependent Claim
276 words
An error detection and correction apparatus comprising: memory means for storing a codeword including data symbols and parity symbols into a location of said memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location, said address includes a plurality of symbols; means for generating a first (P A ) of said parity symbols based on said data symbols and said corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code for determining an error value in said data symbols and corresponding address symbols, where ##EQU7## N i being said data symbols and corresponding address symbols; means for generating a second (P B ) of said parity symbols, where ##EQU8## α being a primitive element in a Galois Field (2 m ) where m is the number of bits in said symbols, said P B providing for locating a single symbol error of said data symbols and symbols of said address; means for generating a third (P C ) of said parity symbols, where ##EQU9## for detecting at least two symbol errors of said data symbols and corresponding address symbols; means coupled to said data symbols and address symbols for generating said N i , α i N i and α 2i N i product terms to produce said P A , P B and P C parity symbols in accordance with said Galois Field of 2 m elements; means coupled to said parity symbol generating means and said parity symbol outputs of said memory means for generating syndromes; and means coupled to said syndromes generating means for performing error correction.
Claim 12
Dependent Claim
276 words
An error detection and correction apparatus comprising: memory means for storing a codeword including data symbols and parity symbols into a location of said memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location, said address includes a plurality of symbols; means for generating a first (P A ) of said parity symbols based on said data symbols and said corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code for determining an error value in said data symbols and corresponding address symbols, where ##EQU7## N i being said data symbols and corresponding address symbols; means for generating a second (P B ) of said parity symbols, where ##EQU8## α being a primitive element in a Galois Field (2 m ) where m is the number of bits in said symbols, said P B providing for locating a single symbol error of said data symbols and symbols of said address; means for generating a third (P C ) of said parity symbols, where ##EQU9## for detecting at least two symbol errors of said data symbols and corresponding address symbols; means coupled to said data symbols and address symbols for generating said N i , α i N i and α 2i N i product terms to produce said P A , P B and P C parity symbols in accordance with said Galois Field of 2 m elements; means coupled to said parity symbol generating means and said parity symbol outputs of said memory means for generating syndromes; and means coupled to said syndromes generating means for performing error correction.
Claim 13
Dependent Claim
36 words
The error detection and correction apparatus as recited in claim 10 wherein: said control signal causes said memory means to perform a write mode for storing said codeword or a read mode for reading said codeword.
Claim 14
Dependent Claim
69 words
The error detection and correction apparatus as recited in claim 11 wherein: said parity symbols generating means generates said P A , P B and P C parity symbols for said data symbols and corresponding address symbols when said memory means is performing said write mode and when said memory means is performing said read mode generates P A ', P B ' and P C ' parity symbols.
Claim 15
Dependent Claim
83 words
The error detection and correction apparatus as recited in claim 12 wherein: said parity symbol outputs P A , P B and P C from said memory means to said syndrome generating means when reading said codeword are compared to said parity symbols P A ', P B ' and P C ', generated by said parity symbol generator means based on said data symbols being read and said corresponding address symbols, for determining a difference pattern for said error detection and correction.
Claim 16
Dependent Claim
53 words
The error detection and correction apparatus as recited in claim 10 wherein: said product terms generating means comprises means for adding a padded bit to a data symbol input and an address symbol input for matching the number of symbol bits to the bit width of a memory ship in said memory means.
Claim 17
Dependent Claim
56 words
The error detection and correction apparatus as recited in claim 10 wherein: said syndrome generating means comprises means for generating a plurality of syndrome signals; and said error correction means comprises means coupled to said syndrome signals for interpreting said syndrome signals to identify a data symbol error and whether said data symbol error is correctable.
Claim 18
Dependent Claim
30 words
The error detection and correction apparatus as recited in claim 15 wherein: said interpreting means further comprises means for generating select signals to enable correction of said data symbol error.
Claim 19
Dependent Claim
46 words
The error detection and correction apparatus as recited in claim 15 wherein: said apparatus comprises means coupled to data symbols read from said memory means and one of said syndrome signals for performing symbol error correction in accordance with a select signal from said interpreting means.
Claim 20
Dependent Claim
49 words
The error detection and correction apparatus as recited in claim 10 wherein: said error detection and correction apparatus performs single data symbol error correction, double data symbol error detection, single address symbol error detection, double address symbol error detection, and single and double error detection in said parity symbols.
Claim 21
Dependent Claim
32 words
The error detection and correction apparatus as recited in claim 18 wherein: said apparatus further performs detection of any combination of two errors from said data symbols, address symbols and parity symbols.
Claim 22
Independent Claim
172 words
A method of detecting errors and providing correcting information comprising the steps of: storing a codeword, including data symbols and parity symbols each of said symbols having multiple bits, into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; generating said parity symbols of each codeword based on said data symbols and corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code, a first of said parity symbols provides for determining an error in said data symbols and corresponding address symbols, a second of said parity symbols provides for locating said error in one of said data symbols or corresponding address symbols, and a third of said parity symbols provides for detecting at least two symbol errors; and generating syndromes with means coupled to said parity symbol generating means and said parity symbol outputs of said memory means, said syndromes providing information to perform error detection and correction of said codeword.
Claim 23
Independent Claim
172 words
A method of detecting errors and providing correcting information comprising the steps of: storing a codeword, including data symbols and parity symbols each of said symbols having multiple bits, into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; generating said parity symbols of each codeword based on said data symbols and corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code, a first of said parity symbols provides for determining an error in said data symbols and corresponding address symbols, a second of said parity symbols provides for locating said error in one of said data symbols or corresponding address symbols, and a third of said parity symbols provides for detecting at least two symbol errors; and generating syndromes with means coupled to said parity symbol generating means and said parity symbol outputs of said memory means, said syndromes providing information to perform error detection and correction of said codeword.
Claim 24
Dependent Claim
44 words
The method as recited in claim 20 wherein: said step of generating syndromes to perform error detection and correction of said codeword includes single data symbol error correction, double data symbol error detection, single address symbol error detection and double address symbol error detection.
Claim 25
Independent Claim
284 words
A method of error detection and correction comprising the steps of: storing a codeword including data symbols and parity symbols into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location, said address includes a plurality of symbols; generating a first (P A ) of said parity symbols based on said data symbols and said corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code for determining an error value in said data symbols and corresponding address symbols, where ##EQU10## N i being said data symbols and corresponding address symbols; generating a second (P B ) of said parity symbols, where ##EQU11## α being a primitive element in a Galois Field (2 m ) where m is the number of bits in said symbols, said P B providing for locating a single symbol error of said data symbols and symbols of said address; generating a third (P C ) of said parity symbols where ##EQU12## for detecting at least two symbol errors of said data symbols and corresponding address symbols; generating said N i , α i N i and α 2i N i product terms which produce said P A , P B and P C parity symbols in accordance with said Galois Field of 2 m elements with means coupled to said data symbols and address symbols; generating syndromes with means coupled to said parity symbol generator means and said parity symbol outputs of said memory means, said syndromes providing information to perform error detection and correction of said codeword; and performing error correction with means coupled to said syndromes generating means.
Claim 26
Independent Claim
284 words
A method of error detection and correction comprising the steps of: storing a codeword including data symbols and parity symbols into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location, said address includes a plurality of symbols; generating a first (P A ) of said parity symbols based on said data symbols and said corresponding address symbols of said codeword in accordance with a modified Reed-Solomon code for determining an error value in said data symbols and corresponding address symbols, where ##EQU10## N i being said data symbols and corresponding address symbols; generating a second (P B ) of said parity symbols, where ##EQU11## α being a primitive element in a Galois Field (2 m ) where m is the number of bits in said symbols, said P B providing for locating a single symbol error of said data symbols and symbols of said address; generating a third (P C ) of said parity symbols where ##EQU12## for detecting at least two symbol errors of said data symbols and corresponding address symbols; generating said N i , α i N i and α 2i N i product terms which produce said P A , P B and P C parity symbols in accordance with said Galois Field of 2 m elements with means coupled to said data symbols and address symbols; generating syndromes with means coupled to said parity symbol generator means and said parity symbol outputs of said memory means, said syndromes providing information to perform error detection and correction of said codeword; and performing error correction with means coupled to said syndromes generating means.
Claim 27
Dependent Claim
51 words
The method as recited in claim 22 wherein: said step of generating syndromes to perform error detection and correction of said codeword includes single data symbol error correction, double data symbol error detection, single address symbol error detection, double address symbol error detection and single and double parity symbol error detection.
Claim 28
Dependent Claim
38 words
The method as recited in claim 23 wherein said error detection and correction of said codeword further includes the step of performing detection of any combination of two errors from said data symbols, address symbols and parity symbols.
Claim 29
Dependent Claim
53 words
The method as recited in claim 22 wherein: said step of generating said product terms further comprises the step of adding a padded bit to a data symbol input and an address symbol input for matching the number of symbol bits to the bit width of a memory chip in said memory means.
Claim 30
Dependent Claim
121 words
A memory system comprising: memory means for storing a codeword including data symbols and parity symbols into a location of said memory means and reading said codeword from said emory means in accordance with a control signal and an address of said codeword location; means for generating said parity symbols m bits wide for each codeword in accordance with a Reed-Solomon code using q bit symbols for said data symbols and address symbols when m bit symbols are required for said Reed-Solomon code where m is equal to q +1; and means for padding said data symbols and address symbols with a logic zero in said parity symbol generating means to obtain said q +1 bits of said m bit symbols.
Claim 31
Dependent Claim
121 words
A memory system comprising: memory means for storing a codeword including data symbols and parity symbols into a location of said memory means and reading said codeword from said emory means in accordance with a control signal and an address of said codeword location; means for generating said parity symbols m bits wide for each codeword in accordance with a Reed-Solomon code using q bit symbols for said data symbols and address symbols when m bit symbols are required for said Reed-Solomon code where m is equal to q +1; and means for padding said data symbols and address symbols with a logic zero in said parity symbol generating means to obtain said q +1 bits of said m bit symbols.
Claim 32
Independent Claim
124 words
A method of detecting errors in a memory system comprising the steps of: storing a codeword including data symbols and parity symbols into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; generating said parity symbols of m bits wide for each codeword in accordance with a Reed-Solomon code using q bit symbols for said data symbols and address symbols when m bit symbols are required for said Reed-Solomon code where m is equal to x +1; and padding said data symbols and address symbols with a logic zero in said parity symbol generating means to obtain said q +1 bits of said m bit symbols.
Claim 33
Independent Claim
124 words
A method of detecting errors in a memory system comprising the steps of: storing a codeword including data symbols and parity symbols into a location of a memory means and reading said codeword from said memory means in accordance with a control signal and an address of said codeword location; generating said parity symbols of m bits wide for each codeword in accordance with a Reed-Solomon code using q bit symbols for said data symbols and address symbols when m bit symbols are required for said Reed-Solomon code where m is equal to x +1; and padding said data symbols and address symbols with a logic zero in said parity symbol generating means to obtain said q +1 bits of said m bit symbols.
References Cited (Backward Citations)
US3914741A
Cited
US3963908A
Cited
US4035766A
Cited
US4142174A
Cited
US4271521A
Cited
US4464753A
Cited
US4661955A
Cited
US4763332A
Cited
US4862463A
Cited
US4928280A
Cited
US4961193A
Cited
US4926426A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-05 | 1997-01-04 | 1997-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-05 | 2001-01-04 | 2001-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-05 | 2005-01-04 | 2005-07-06 | $7700.00 | Window Closed / Lapsed |