Error correction circuit utilizing multiple parity bits

Abstract

An arrangement for correcting errors in words read from a memory due to a bit in a word location of the memory being stuck in one of the two binary states, 0 or 1. The arrangement is used in cooperation with parity error detection arrangements which utilize more than one parity bit per word. Upon detection of a single parity failure in a word read from a selected word location in memory the complement of the data word which is indicated to contain a parity failure is placed in the selected word location; the memory is read at the selected word location and the data so obtained is placed back into the selected word location of the memory. After this step the data in the selected word location of memory comprises the complement of the correct data word and the parity bits are all the complement of the correct parity for that data word. The correct data word for use by the processor is thus generated by complementing this later received data. On subsequent reading of the memory at a previously failed location the corrected word in the location is recognized as such by a failure of all of the parity bits. A word in which all of the parity bits fail is automatically complemented and the result is utilized in the data processor.

What is claimed is: 
     
       1. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit where each data word in said memory comprises: a plurality of data bits and a plurality of parity bits; and   said method is practiced in an error correcting circuit comprising: read and write circuitry for said memory;   parity check means;   complementing means; and   output circuitry for transmitting corrected words to a destination circuit;     said method comprising the following steps: a reading the contents of a selected word location from said memory and applying said contents to said parity check means,   (b) complementing said contents of said memory, applying said complemented contents to said destination circuit and stopping if the output of said parity check means indicates that all of said plurality of parity bits are bad,   (c) performing the following steps if the output of said parity check means indicates that at least one but not all of said plurality of parity bits are bad: (1) complementing said contents,   (2) writing said complemented contents into said selected word location of said memory,   (3) repeating steps a) through b).       
     
     
       2. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit where each data word in said memory comprises: a plurality of data bits and a plurality of parity bits; and   said method is practiced in an error correcting circuit comprising: read and write circuitry for said memory;   parity check means;   complementing means; and   output circuitry for transmitting corrected words to a destination circuit;     (a) method comprising the following steps: a. reading the contents of a selected word location from said memory a first time and applying said contents to said parity check means,   (b) complementing said first read contents of said memory, applying said complemented first read contents to said destination circuit and stopping if the output of said parity check means indicates that all of said plurality of parity bits are bad,   (c) performing the following steps if the output of said parity check means indicates that at least one but not all of said plurality of parity bits are bad: (1) complementing said first read 1)   (2) writing said complemented first read contents into said selected word location of said memory,   (3) reading the contents of said selected word location of said memory a second time and applying said second read contents to said parity check means,   (4) complementing said second read contents and applying said complemented second read contents to said destination circuit if the output of said parity check means indicates that all of said plurality of parity bits are bad.       
     
     
       3. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit according to claim 2 wherein the method is practiced in an error correcting circuit further comprising an error signal means for transmitting an error signal to said destination circuit and said method further comprises the following step performed following step 3 and before step 4: (3a) causing said error signal means to generate an error signal if the output of said parity check circuit indicates that one or more of said parity bits are good.   
     
     
       4. The method for correcting errors in a memory and applying the corrected words to a destination circuit according to claim 2 further comprising the following step performed following step 3 and before step 4: (3a) writing said second read contents into said selected word location if the output of said parity check means indicates that all of said plurality of parity check bits are bad.   
     
     
       5. The method of correcting data words obtained from a memory where each data word comprises a plurality of data bits and a plurality of parity bits; the method practiced in an error correction circuit arrangement which comprises: means for writing information into the memory, means for reading information from the memory, means for evaluating the plausibility of the data words obtained from memory and for generating signals indicating failure of at least one parity bit and for indicating failure of all parity bits, means for complementing data words, means for transmitting corrected data words to a destination circuit and means for controlling the operation of said error correction circuit arrangement in response to output signals of said evaluating means; the method comprising the steps of: 1. reading a data word from a location in said memory;   2. checking plausibility of the data word obtained from memory; and   3. controlling the error correction circuit arrangement as follows: a. if at least one but not all parity bits fail, complementing the data word and writing the resulting complemented data word back into said location in memory, and repeating steps 1-3; and   b. if all parity bits fail, complementing the data word and transmitting the resulting data word to said destination circuit.     
     
     
       6. In a memory having a plurality of word locations for storing words therein having a plurality of parity bits, read and write circuitry for said memory, output circuitry for words read from said memory, a parity check circuit, complementing circuitry, and an error signal circuit, a method for correcting failures in said memory and applying corrected words to said output circuitry comprising the steps of: a. applying the contents of a selected word location in said memory to said parity check circuit,   b. applying the contents of said selected word location to said complementing circuitry,   c. applying the complemented word from said complementing circuitry to said output circuitry and stopping if all of said plurality of parity bits from step (a) are not correct,   d. causing said writing means to write said complemented word into said selected word location if at least one but not all of said plurality of parity bits from step (a) are not correct,   e. applying the contents of said selected word location to said parity checking circuit,   f. applying the contents of said selected word location to said complementing circuitry, and   g. applying said complemented word to said output circuitry if all of said plurality of parity bits from step (e) are not correct.   
     
     
       7. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit where each data word in said memory comprises: a plurality of data bits and a plurality of parity bits, each parity bit associated with certain ones of said plurality of data bits; and   said method is practiced in an error correcting circuit comprising: read and write circuitry for said memory;   parity check means;   complementing means; and   output circuitry for transmitting corrected words to a destination circuit;     said method comprising the following steps: (a) reading the contents of a selected word location from said memory a first time and applying said contents to said parity check means,   (b) performing the following steps if the output of said parity check means indicates that at least one but not all of said plurality of parity bits are bad: (1) complementing said first read contents,   (2) writing said complemented first read contents into said selected word location of said memory,   (3) reading the contents of said selected word location from said memory a second time and applying said second read contents to said parity check means,   (4) combining the complement of the data bits from said first read contents associated with each bad parity bit of said second read contents with the data bits of said second read contents associated with the good parity bits of said second read contents and stopping if at least one but not all of said plurality of parity bits of said second read contents are bad,   (5) complementing said second read contents, applying said complemented second read contents to said destination circuit and stopping if all of said parity bits of said second read contents are bad,     (c) performing the following steps if the output of said parity check means indicates that all of said plurality of parity bits are bad: (1) complementing said first read contents,   (2) writing said complemented first read contents into said selected word location of said memory,   (3) reading the contents of said selected word location from said memory a second time and applying said second read contents to said parity check means,   (4) writing said first read contents into said selected word location, applying said complemented first read contents to said destination circuit and stopping if one or more of said plurality of parity bits are good,   (5) complementing said second read contents, writing said complemented second read contents into said selected word location and applying said complemented second read contents to said destination circuit if all of said plurality of parity bits are bad.       
     
     
       8. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit according to claim 7 wherein the method is practiced in an error correcting circuit further comprising an error signal means for transmitting an error signal to said destination circuit and said method further comprises the following step performed following step (c3) and before step (c4): (c3a) causing said error signal means to generate an error signal and stopping if the output of said parity check circuit indicates that all of said parity bits are good.   
     
     
       9. A method for correcting errors in a memory comprising one or more words and applying the corrected words to a destination circuit according to claim 7 further comprising the following step performed following step (c4) and before step (c5): (c4a) writing said second read contents into said selected word location if the output of said parity check means indicates that all of said plurality of parity check bits are bad.   
     
     
       10. An error correcting circuit having a plurality of operating states for checking and for correcting errors in information read from a memory and for gating the correct information to a destination circuit arranged to provide start memory signals for initiating a memory read or a memory write operation, the error correcting circuit comprising: a state counter for generating signals defining the current operating state of said error correcting circuit;   a data register comprising means for storing a plurality of data bits and a plurality of parity bits;   parity check circuitry connected to said data register for generating signals indicative of parity errors in the contents of said data register;   input gating means connected to said memory, said destination circuit, and said data register for gating information into said data register selectively from said destination circuit and said memory; and   output gating means connected to said memory, said destination circuit, and said data register for gating information from said data register selectively to said memory and to said destination circuit, said output gating means including means for selectively complementing the contents of said data register;   controlling means connected to said counter, said parity check circuitry, said input gating means, said output gating means, said memory, and said destination circuit and responsive to the outputs of said counter, said parity error signals, and said start memory signals for generating signals for controlling said input gating means, said output gating means, said counter, and said memory such that: a memory location is read and the information contained therein is gated to said data register; if said parity error signals indicate that at least one but one all of said parity bits contained in said data register is bad, the contents of said data register are complemented and written into said memory location, said memory location is again read and the information contained therein is gated to said data register; if said parity error signals indicate that all of said parity bits contained in said data register are then bad the contents of said data register are complemented and gated to said destination circuit; and that if said parity error signals indicate that all of said parity bits contained in said data register after the initial read of a location of said memory are bad, the contents of said data register are complemented and gated to said destination circuit.     
     
     
       11. An error correcting circuit in accordance with claim 10 wherein said controlling means further comprises: an error signal output connected to said destination circuit; and   means responsive to output signals of said counter and said parity error signals for generating an error signal on said error signal output if one or more of said plurality of parity bits are good after said memory location is again read.   
     
     
       12. An error correcting circuit having a plurality of operating states for checking and for correcting errors in information read from a memory and for gating the correct information to a destination circuit arranged to provide start memory signals for initiating a memory read or memory write operation, the error correcting circuit comprising: a state counter for generating signals defining the current operating state of said error correcting circuit;   a first data register and a second data register each comprising means for storing a plurality of data bits and a plurality of parity bits;   parity check circuitry connected to said first data register for generating signals indicative of parity errors in the contents of said first data register;   input gating means connected to said memory, said destination circuit, said first data register and said second data register for gating information into said first and second data registers selectively from said destination circuit and said memory;   output gating means connected to said memory, said destination circuit, said first data register and said second data register for gating information from said first and second data registers selectively to said memory and to said destination circuit, said output gating means including means for selectively complementing the contents of said first and second data registers; and   controlling means connected to said counter, said parity check circuitry, said input gating means, said output gating means, said memory, and said destination circuit and responsive to the outputs of said counter, said parity error signals, and said start memory signals for generating signals for controlling said input gating means, said output gating means, said counter, and said memory such that: a memory location is read and the information contained therein is gated into said first data register and said second data register; if said parity error signals indicate that at least one but not all of said parity bits contained in said first data register is bad, the contents of said first data register are complemented and written into said memory location, said memory location is again read and the information therein is gated to said first data register; if said parity error signals indicate that all of said parity bits contained in said first data register are then bad, the contents of said first data register are written into said memory location and complemented and gated to said destination circuit; if less than all of said parity bits contained in said first data register are then bad, the contents of said first data register which corresponds to bad parity bits for information in said first data register are complemented and gated to said destination circuit and written into said memory location and the contents of said second data register which correspond to good parity bits for information in said second data register due to the initial read are gated to said destination circuit and written into said memory; and that if said parity error signals indicate that all of said data bits contained in said first data register after the initial read of a location of said memory are bad, the contents of said first data register are complemented and written into said memory location, said memory location is again read and the information therein is gated to said first data register; if said parity error signals indicate that all of said parity bits contained in said first data register are then bad, the contents of said first data register are written into said memory location and complemented and gated to said destination circuit; if said parity error signals indicate that less than all of said parity bits contained in said first data register are then bad, the contents of said second data register are written into said memory location and the contents of said second data register are complemented and gated to said destination circuit.   
     
     
       13. An error correcting circuit in accordance with claim 12 wherein said controlling means further comprises: an error signal output connected to said destination circuit; and   means responsive to output signals of said counter and said parity error signals for generating an error signal on said error signal output if at least one but not all of said parity bits in said first data register after said initial read is bad and all of said parity bits are good after said memory location is again read.