US3622982A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for triple error correction
Assignee: International Business Machines Corp
•
Filing: 1969-02-28
•
Granted: 1971-11-23
•
Expires: 1989-02-28
Abstract
Abstract The invention relates to a simplified method for extracting triple error correction information from a (23, 12) BoseChaudhuri code which is the Golay code. In a 23-bit word having three or less errors, the method provides correction on a bit-bybit basis. Each bit is assumed to be in error and corrected, the remaining 22 bits are then interrogated for two or less errors. Also disclosed is the apparatus for extracting the error correction information from the Golay code in a Bose-Chaudhuri code is comprised of a check word generator and shifting means, decoder circuitry, false error indication inhibit circuitry, control circuitry and error action circuitry.
Inventors
- 👤 Bradford S Clark Jr
- 👤 Alexander H Frey Jr
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 09:37
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
260 words
An apparatus for detecting and correcting less than four errors in a 23-bit coded word, said coded word being encoded in a cyclic (23, 12) Golay code, said apparatus determining whether each bit of said 23 bits is in error alone or in combination with less than three other bits of said 23 comprising: a storage means for storing said coded word; an 11 stage check word generator for generating a check word from said coded word; a control means for cycling an interrogation cycle for said check word by shifting said check word one bit after each of said interrogation cycles, for causing the first stage of said check word generator to be complemented at the beginning of each of said interrogation cycles, for shifting said check word 23 times during each of said interrogation cycles, the cycle number ''''n'''' being indicative of the bit of said 23 bits being interrogated for error; a detecting means for detecting and storing the oCcurrence of less than three valid errors in said check word generator during any one of said 23 shifts of said check word generator caused by said control means; an error action means for generating a first and second output after the 23rd shift of said control means, said first output being generated if said detecting means detected less than three valid errors and correcting bit ''''n'''' in said storage means, said second output being generated if said detecting means detected more than two valid errors, said second output complementing the first stage of said check word generator.
Claim 2
Independent Claim
260 words
An apparatus for detecting and correcting less than four errors in a 23-bit coded word, said coded word being encoded in a cyclic (23, 12) Golay code, said apparatus determining whether each bit of said 23 bits is in error alone or in combination with less than three other bits of said 23 comprising: a storage means for storing said coded word; an 11 stage check word generator for generating a check word from said coded word; a control means for cycling an interrogation cycle for said check word by shifting said check word one bit after each of said interrogation cycles, for causing the first stage of said check word generator to be complemented at the beginning of each of said interrogation cycles, for shifting said check word 23 times during each of said interrogation cycles, the cycle number ''''n'''' being indicative of the bit of said 23 bits being interrogated for error; a detecting means for detecting and storing the oCcurrence of less than three valid errors in said check word generator during any one of said 23 shifts of said check word generator caused by said control means; an error action means for generating a first and second output after the 23rd shift of said control means, said first output being generated if said detecting means detected less than three valid errors and correcting bit ''''n'''' in said storage means, said second output being generated if said detecting means detected more than two valid errors, said second output complementing the first stage of said check word generator.
Claim 3
Dependent Claim
54 words
An apparatus as set forth in claim 1 wherein said detecting means comprises: a first means for generating a third output when there is all zeros in said check word generator upon the completion of the 23 cycles of said control means, said third output indicating that said coded word has been successfully corrected.
Claim 4
Dependent Claim
190 words
An apparatus as set forth in claim 1 wherein said detecting means comprises: a second means for generating a fourth output when the contents of said check word generator is the unique double-error pattern; a third means for generating a fifth output when the contents of said check word generator contains a one in said first stage of said check word generator and less than two ones present in the remaining 10 stages of said check word generator; a fourth means for generating a sixth output when the contents of said check word generator is all zeros; a fifth means for inhibiting said fourth output of said second means at times when said fourth output would be erroneous due to the operation of said control means having complemented said first stage of said check word generator; a sixth means for inhibiting said fifth output of said third means at times when said fifth output would be erroneous due to the operation of said control means having complemented said first stage of said check word generator; a memory means responsive to the first occurrence of said fourth, fifth or sixth outputs.
Claim 5
Dependent Claim
192 words
An apparatus as set forth in claim 3 wherein said third means comprises: a greater than one detector for generating a seventh output when there is more than one one in the last 10 stages of said check word generator: a first inverter for inverting said seventh output of said greater than one detector; a first AND circuit having a first input from said first stage of said check word generator and a second input from said first inverter, the output of said first AND circuit being said fifth output; and said fourth means comprises: an odd number detector for generating an eighth output when there is an odd number of ones in the last 10 stages of said check word generator; a second inverter for inverting the output of said odd number detector; a third inverter for inverting the output of said first stage of said check word generator; a second AND circuit having a third input from said second inverter, a fourth input from said third inverter and a fifth input from said first inverter of said third means, the output of said second AND circuit being said sixth output.
Claim 6
Dependent Claim
69 words
An apparatus as set forth in claim 1 wherein: said control means controls only 12 of said 23 cycles, and a seventh means for generating a ninth output when the contents of said check word generator has less than four ones upon the completion of said 12th cycle of said control means, said ninth output indicating that the first 12 bits of said 23 bits have been successfully corrected.
Claim 7
Independent Claim
200 words
A method for detecting and correcting less than four errors in a 23-bit coded word in a bit stream, said coded word being encoded in a cyclic (23, 12) Golay code, said method determining whether each bit of said 23 bits is in error alone or in combination with less than three other bits of said 23 bits, comprising the steps of: storing Said coded word; generating a check word from said coded word; sequentially determining whether each bit of said coded word is in error alone or in combination with less than three other errors in the remaining 22 bits of said check word by performing an interrogation cycle for each of said bits, said interrogation cycle comprising the steps of: complementing the first bit of said check word under the assumption that the bit under interrogation is in error, detecting the presence of less than three valid errors in the modified check word, correcting the bit under interrogation in said stored coded word if less than three valid errors were detected in said modified check word, recomplementing the first bit of said check word if less than three valid errors were not detected in said modified check word.
Claim 8
Independent Claim
200 words
A method for detecting and correcting less than four errors in a 23-bit coded word in a bit stream, said coded word being encoded in a cyclic (23, 12) Golay code, said method determining whether each bit of said 23 bits is in error alone or in combination with less than three other bits of said 23 bits, comprising the steps of: storing Said coded word; generating a check word from said coded word; sequentially determining whether each bit of said coded word is in error alone or in combination with less than three other errors in the remaining 22 bits of said check word by performing an interrogation cycle for each of said bits, said interrogation cycle comprising the steps of: complementing the first bit of said check word under the assumption that the bit under interrogation is in error, detecting the presence of less than three valid errors in the modified check word, correcting the bit under interrogation in said stored coded word if less than three valid errors were detected in said modified check word, recomplementing the first bit of said check word if less than three valid errors were not detected in said modified check word.
Claim 9
Dependent Claim
55 words
A method as set forth in claim 6 comprising the further step of: detecting if the check word has a value of all zeros after the last bit of said coded word has been interrogated for errors by said interrogation cycle, and generating an output signal that will indicate successful correction of said coded word.
Claim 10
Dependent Claim
104 words
A method as set forth in claim 6 wherein the step of sequentially determining the status of each bit of said coded word by an interrogation cycle is only performed for the first 12 bits of said coded word, and further comprises the step of detecting if the check word has less than four errors in the remaining 11 bits of said check word that have not been interrogated, and generating the output signal that will indicate successful correction of said first 12 bits of said coded word if less than four errors was detected in the remaining 11 bits of said coded word.
References Cited (Backward Citations)
US3209327A
Cited
US3437995A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-11-22 | 1975-05-24 | 1975-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-11-22 | 1979-05-24 | 1979-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-11-22 | 1983-05-24 | 1983-11-23 | $7700.00 | Window Closed / Lapsed |