US4030067A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Table lookup direct decoder for double-error correcting (DEC) BCH codes using a pair of syndromes
Assignee: Bull HN Information Systems Inc
•
Filing: 1975-12-29
•
Granted: 1977-06-14
•
Expires: 1995-12-29
Abstract
Abstract Apparatus for directly decoding and correcting double-bit random errors per word and for detecting triple-bit errors per word is disclosed. Said apparatus comprises a syndrome calculator which operates upon codewords received from memory and generates syndromes. The syndromes are operated upon and translated by a mapping device which generates pointers identifying the bits which are in error. The pointers are then passed through decoding means to generate error words which are summed with the received word from memory to provide a corrected codeword. The syndrome calculator may further provide a parity check signal to determine if a three-bit error is present, in which case the decoding means are not enabled and a signal is generated indicating that a triple-bit error has been detected which is not correctable.
Inventors
- 👤 Thomas H. Howell
- 👤 Gordon E. Gregg
- 👤 Leonard Rabins
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 18:22
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1012; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; H03M13/152; H03M13/1575
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
243 words
An apparatus for detecting and correcting double-bit errors in n-bit codewords, where said codewords include k information bits, 2m check bits and one parity bit (n=k+2m+1), said apparatus comprising: means responsive to said codeword for calculating a first and a second syndrome, said syndromes identifying the existence and position of errors in said codeword according to an error-locator equation; translation means responsive to said syndromes for generating root signals corresponding to one of the roots of said error-locator equation; first multiplier means coupled to said translation means and to said calculation means for receiving said first syndrome and said root signals, said first multiplier means producing first signals for identifying a first error-location; first summing means coupled to said first multiplying means and to said calculation means for receiving said first signals and said first syndrome, said summing means producing second signals corresponding to a second error-location; first decoding means responsive to said first multiplying means for decoding said first signals and for producing an error word containing a 1 corresponding to said first error-location; second decoding means responsive to said first summing means for decoding said second signals and for producing a second error word containing a 1 corresponding to said second error-locaton; and second summing means adapted to receive said codeword and responsive to said first and said second decoding means, said second summing means adding said first and said second error words to said codeword for generating a corrected codeword.
Claim 2
Independent Claim
243 words
An apparatus for detecting and correcting double-bit errors in n-bit codewords, where said codewords include k information bits, 2m check bits and one parity bit (n=k+2m+1), said apparatus comprising: means responsive to said codeword for calculating a first and a second syndrome, said syndromes identifying the existence and position of errors in said codeword according to an error-locator equation; translation means responsive to said syndromes for generating root signals corresponding to one of the roots of said error-locator equation; first multiplier means coupled to said translation means and to said calculation means for receiving said first syndrome and said root signals, said first multiplier means producing first signals for identifying a first error-location; first summing means coupled to said first multiplying means and to said calculation means for receiving said first signals and said first syndrome, said summing means producing second signals corresponding to a second error-location; first decoding means responsive to said first multiplying means for decoding said first signals and for producing an error word containing a 1 corresponding to said first error-location; second decoding means responsive to said first summing means for decoding said second signals and for producing a second error word containing a 1 corresponding to said second error-locaton; and second summing means adapted to receive said codeword and responsive to said first and said second decoding means, said second summing means adding said first and said second error words to said codeword for generating a corrected codeword.
Claim 3
Dependent Claim
110 words
The apparatus as defined in claim 1 further comprising: first non-zero detect logic responsive to said first syndrome for producing a signal when said first syndrome is equal to zero; second non-zero detect logic responsive to said second syndrome for generating a signal when said second syndrome is equal to zero; first gating means responsive to said first and said second non-zero detect logic for generating an error detect signal when either of said syndromes is not equal to zero; and second gating means responsive to said first and said second non-zero detect logic for generating a decoding failure signal when only one of said syndromes is equal to zero.
Claim 4
Dependent Claim
56 words
The apparatus as defined in claim 1 wherein said translation means comprises: first means responsive to said first and said second syndromes for generating third signals corresponding to said second syndrome divided by the cube of said first syndrome; and second means responsive to said first means for translating said third signals into said root signals.
Claim 5
Dependent Claim
28 words
The apparatus as defined in claim 3 wherein said second means further comprises means for generating a multiple error signal indicating the occurrence of more than one error.
Claim 6
Dependent Claim
73 words
The apparatus as defined in claim 4 wherein said calculation means also generates a parity checking signal indicating the occurrence of a parity error in said codeword and further comprising third gating means responsive to said multiple error signal and said parity checking signal for generating a triple error detect signal, said third gating means connected to said first and said second decoding means for disabling said first and said second decoding means.
Claim 7
Dependent Claim
42 words
The apparatus as defined in claim 3 wherein said second means comprises a table look-up mechanism, said third signals acting as an address to said table look-up mechanism, said root signals corresponding to the contents of the location indicated by said address.
Claim 8
Dependent Claim
18 words
The apparatus as claimed in claim 6 wherein said table look-up mechanism is a read only memory (ROM).
Claim 9
Dependent Claim
66 words
The apparatus as defined in claim 3 wherein said first means comprises: translator means responsive to said first syndrome for generating fourth signals corresponding to said cubed inverse of said first syndrome; and second multiplying means coupled to said translator means and to said calculation means for multiplying said second syndrome and said fourth signals as elements in a Galois field over a generator polynomial g(x).
Claim 10
Dependent Claim
16 words
The apparatus as defined in claim 8 wherein said translator means comprises a table look-up mechanism.
Claim 11
Dependent Claim
18 words
The apparatus as defined in claim 9 wherein the table look-up mechanism is a read only memory (ROM).
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) | 1980-06-13 | 1980-12-13 | 1981-06-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1984-06-13 | 1984-12-13 | 1985-06-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1988-06-13 | 1988-12-13 | 1989-06-14 | $7700.00 | Window Closed / Lapsed |