US4168486A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Segmented error-correction system
Assignee: Unisys Corp
•
Filing: 1978-06-30
•
Granted: 1979-09-18
•
Expires: 1998-06-30
Abstract
Abstract In a data processing error control system for named data, a parity check matrix and apparatus for using same provides for single error correcting of the data word and for multiple error detecting in both the data word and data name. The parity check matrix and apparatus utilize two additional parity check bits (over that required by a system using a prior art SEC/DED Hamming code) to provide protection against single bit errors, eight contiguous bit errors (i.e., hardware stuck at logical one or logical zero for the whole eight contiguous bits), similar four contiguous bit errors, and faults covering the entire data name field (which could occur, for example, if a wrong data word was fetched from memory). The parity check matrix is segmented and mated to the error correctional requirements and prevalent error modes of each field being protected. In encoding, parity check bits are generated for the combined data word and associated data name field. In decoding, an overall parity check of the check bits, data word and data name is performed for distinguishing between odd and even errors. Further, the parity check matrix is invoked to generate a parity checking number for addressing a decoding table circuit (realizable as a ROM) which in turn provides the error bit location for single bit correctable errors. Given the error bit location a correction circuit corrects (i.e., complements) the detected single erroneous bit in the data word or in the generated parity check bits.
Inventors
- 👤 John E. Legory
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:13
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1064; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19; G06F11/1012; G06F11/1016
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
182 words
A method of detecting and correcting errors in a binary named-data code word comprising a data word field, a data name field and a field of check bits covering both the data word and the data name field, said method comprising the steps of: performing a parity check on said binary named-data code word to generate an overall parity indicator and a checking number; generating an even error indicator if said overall parity indicator indicates good parity and said checking number equals any number other than zero; generating a zero error indicator if said overall parity indicator indicates good parity and said checking number equals zero; decoding said checking number if said overall parity indicator indicates bad parity to generate from said checking number an error bit address; generating an odd error indicator if said error bit address lies outside the fields of said data word and said check bits; and complementing the bit in said binary named-data word at said error bit address if said error bit address lies within either said data word field or said field of check bits.
Claim 2
Independent Claim
182 words
A method of detecting and correcting errors in a binary named-data code word comprising a data word field, a data name field and a field of check bits covering both the data word and the data name field, said method comprising the steps of: performing a parity check on said binary named-data code word to generate an overall parity indicator and a checking number; generating an even error indicator if said overall parity indicator indicates good parity and said checking number equals any number other than zero; generating a zero error indicator if said overall parity indicator indicates good parity and said checking number equals zero; decoding said checking number if said overall parity indicator indicates bad parity to generate from said checking number an error bit address; generating an odd error indicator if said error bit address lies outside the fields of said data word and said check bits; and complementing the bit in said binary named-data word at said error bit address if said error bit address lies within either said data word field or said field of check bits.
Claim 3
Dependent Claim
24 words
The method of claim 1 wherein said step of performing a parity check generates a single-bit overall parity indicator and a nine-bit checking number.
Claim 4
Dependent Claim
38 words
The method of claim 1 wherein said step of performing a parity check generates said overall parity indicator and said checking number by the step of multiplying said binary named-data code word times a two-dimensional parity check matrix.
Claim 5
Dependent Claim
49 words
The method of claim 3 wherein said two-dimensional parity check matrix includes a data word segment for error checking of said data word field in said binary named-data code word and a data name segment for error checking of said data name field in said binary named-data code word.
Claim 6
Dependent Claim
93 words
The method of claim 4 wherein said data word segment includes a plurality of eight-column groups, each column therein including a plurality of column bits to differentiate one eight-column group from another within said plurality thereof, a plurality of column bits to differentiate one column from another within the same eight-column group in said plurality thereof, and a plurality of column bits to map multi-bit odd errors occuring in said data word field of said binary named-data code word into addresses lying outside said fields of said data word and said check bits.
Claim 7
Dependent Claim
57 words
The method of claim 4 wherein said data name segment includes a plurality of eight-column groups, each column therein including a plurality of column bits to map most multi-bit odd errors occurring in said data name field of said binary named-data code word into addresses lying outside said fields of said data word and said check bits.
Claim 8
Independent Claim
212 words
An apparatus for detecting and correcting errors in a binary named-data code word comprising a data word field, a data name field and a field of check bits covering both the data word and the data name field, said apparatus comprising: means for performing a parity check on said binary named-data code word to generate an overall parity indicator and a checking number; means connected to said parity check performing means for generating an even error indicator if said overall parity indicator indicates good parity and said checking number equals any number other than zero and also for generating a zero error indicator if said overall parity indicator indicates good parity and said checking number equals zero; means connected to said parity check performing means for decoding said checking number if said overall parity indicator indicates bad parity to generate from said checking number an error bit address; means connected to said decoding means for generating a detected odd error indication if said error bit address lies outside the fields of said data word and said check bits; and means for complementing the bit in said binary named-data word at said error bit address if said error bit address lies within either said data word field or said field of check bits.
Claim 9
Independent Claim
212 words
An apparatus for detecting and correcting errors in a binary named-data code word comprising a data word field, a data name field and a field of check bits covering both the data word and the data name field, said apparatus comprising: means for performing a parity check on said binary named-data code word to generate an overall parity indicator and a checking number; means connected to said parity check performing means for generating an even error indicator if said overall parity indicator indicates good parity and said checking number equals any number other than zero and also for generating a zero error indicator if said overall parity indicator indicates good parity and said checking number equals zero; means connected to said parity check performing means for decoding said checking number if said overall parity indicator indicates bad parity to generate from said checking number an error bit address; means connected to said decoding means for generating a detected odd error indication if said error bit address lies outside the fields of said data word and said check bits; and means for complementing the bit in said binary named-data word at said error bit address if said error bit address lies within either said data word field or said field of check bits.
Claim 10
Dependent Claim
25 words
The apparatus according to claim 7 wherein said means for decoding includes a memory addressable by said checking number for outputting said error bit address.
Claim 11
Dependent Claim
13 words
The apparatus according to claim 8 wherein said memory is a read-only memory.
Claim 12
Dependent Claim
26 words
The apparatus according to claim 7 wherein said overall parity indicator is a single-bit overall parity indicator and said checking number is a nine-bit checking number.
Claim 13
Dependent Claim
39 words
The apparatus according to claim 7 wherein said means for performing a parity check includes means for multiplying said binary named-data code word times a two-dimensional parity check matrix to generate said overall parity indicator and said checking number.
Claim 14
Dependent Claim
54 words
The apparatus of claim 11 wherein said two-dimensional parity check matrix in said step of performing includes a data word segment for error checking of said data word field in said binary named-data code word and a data name segment for error checking of said data name field in said binary named-data code word.
Claim 15
Dependent Claim
93 words
The apparatus of claim 12 wherein said data word segment includes a plurality of eight-column groups, each column therein including a plurality of column bits to differentiate one eight-column group from another within said plurality thereof, a plurality of column bits to differentiate one column from another within the same eight-column group in said plurality thereof, and a plurality of column bits to map multi-bit odd errors occuring in said data word field of said binary named-data code word into addresses lying outside said fields of said data word and said check bits.
Claim 16
Dependent Claim
57 words
The method of claim 13 wherein said data name segment includes a plurality of eight-column groups, each column therein including a plurality of column bits to map most multi-bit odd errors occurring in said data name field of said binary named-data code word into addresses lying outside said fields of said data word and said check bits.
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) | 1982-09-17 | 1983-03-19 | 1983-09-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1986-09-17 | 1987-03-19 | 1987-09-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1990-09-17 | 1991-03-19 | 1991-09-18 | $7700.00 | Window Closed / Lapsed |