Method and circuitry for correcting errors in recirculating memories

A method for detecting and correcting bit errors randomly introduced into a binary data loop circulating at a system clock frequency from the output terminals into the input terminals of a plurality of substantially identical recirculating memory registers in a memory system, the method comprising the steps of:

• sampling the binary data circulating in each of the plurality of data loops at a corresponding plurality of data loop taps;
• generating a separate column parity bit from the state of bits in corresponding bit locations in the plurality of data loops as the data bits are sampled at the data loop taps;
• sequentially storing the generated column parity bits in a recirculating column parity memory loop operating in synchronization with the plurality of recirculating memory registers;
• comparing the state of each of the generated column parity bits circulating through the column parity memory loop with the next corresponding generated parity bit;
• producing a column error detection signal whenever the state of the stored parity bit differs from that of the next corresponding generated parity bit, said error detection signal providing means for identifying one column in the plurality of recirculating data loops that contains a bit error;
• generating a separate row parity bit calculated from a predetermined group of sequential bits circulating from the output terminal of each of the plurality of recirculating memory registers;
• sequentially storing the row parity bits in a recirculating row parity memory loop operating in synchronization with the plurality of recirculating memory registers;
• comparing the state of each of the row parity bits circulating through the row parity memory loop with the next corresponding generated row parity bit;
• producing a row error detection signal whenever the state of the stored row parity bit differs from that of the next corresponding generated row parity bit, the row error detection signal providing means for identifying the predetermined group of sequential bits in each of the plurality of recirculating memory registers that contain a bit error;
• determining, from the occurrence of the row error detection signal and the column error detection signal, the data loop and bit location of the bit error;
• and
• correcting the bit error as its location circulates through its respective data loop tap.

An error correction system for correcting bit errors randomly introduced into a recirculating memory having a plurality of substantially identical data recirculating registers, each transferring data bits from its output terminal to its input terminal to form a plurality of data memory loops, said error correction system comprising:

• a loop data tap in each data memory loop of the plurality of data memory loops, the tap including gating circuitry for conducting data through its respective loop and for stopping the flow of said data to introduce into the loop an externally controlled data bit.
• column parity bit generating circuitry coupled to the output of the loop data tap in each of said plurality of data loops for computing parity bits from all data bits in said plurality of loops that are simultaneously moved through their respective data tap;
• row parity bit generating circuitry coupled to the output of the tap in each of said plurality of data loops for computing a parity bit from a group of data bits in each of the plurality of data loops as the bits in said group are serially moved through their respective data taps;
• parity bit storage circuitry coupled to the column and the row parity generator circuitry for separately storing the column parity bits and the row parity bits in a column parity bit memory and a row parity bit memory, respectively, each of the parity memories having a capacity for storing and recirculating, in synchronization, all of its respectively computed parity bits generated during a circulation of all data stored in the recirculating memory;
• P1 column error detection circuitry coupled to the column parity bit generating circuitry and to the column parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored and generated parity bits representing data bits occupying the same location in the recirculating memory, the column error detection circuitry producing an error output signal when the next generated parity bit has changed its state from that of its corresponding stored parity bit;
• row error detection circuitry coupled to the row parity bit generating circuitry and to the row parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored parity bit and corresponding generated parity bit representing data bits occupying the same data bit group and data loop in the recirculating memory, the row error detection circuitry producing an error output signal when said next generated parity bit has changed its state from that of its corresponding stored parity bit;
• and
• correction generating circuitry coupled synchronously to the column error detection circuitry and the row error detection circuitry and responsive to the signals therefrom for locating an error location of a faulty data bit producing the changed column and row parity bits, for generating a changed bit output signal to said loop data tap at the time said error location is next to be conducted through said tap, and for correcting the data bit in error.

An error correction system for correcting bit errors randomly introduced into a recirculating memory having a plurality of substantially identical data recirculating registers, each transferring data bits from its output terminal to its input terminal to form a plurality of data memory loops, said error correction system comprising:

• a loop data tap in each data memory loop of the plurality of data memory loops, the tap including gating circuitry for conducting data through its respective loop and for stopping the flow of said data to introduce into the loop an externally controlled data bit;
• column parity bit generating circuitry coupled to the output of the loop data tap in each of said plurality of data loops for computing parity bits from all data bits in said plurality of loops that are simultaneously moved through their respective data tap;
• row parity bit generating circuitry coupled to the output of the tap in each of said plurality of data loops for computing a parity bit from a group of data bits in each of the plurality of data loops as the bits in said group are serially moved through their respective data taps;
• parity bit storage circuitry coupled to the column and the row parity generator circuitry for separately storing the column parity bits and the row parity bits in a column parity bit memory and a row parity bit memory, respectively, each of the parity memories having a capacity for storing and recirculating, in synchronization, all of its respectively computed parity bits generated during a circulation of all data stored in the recirculating memory;
• column error detection circuitry coupled to the column parity bit generating circuitry and to the column parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored and generated parity bits representing data bits occupying the same location in the recirculating memory, the column error detection circuitry producing an error output signal when the next generated parity bit has changed its state from that of its corresponding stored parity bit;
• row error detection circuitry coupled to the row parity bit generating circuitry and to the row parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored parity bit and corresponding generated parity bit representing data bits occupying the same data bit group and data loop in the recirculating memory, the row error detection circuitry producing an error output signal when said next generated parity bit has changed its state from that of its corresponding stored parity bit;
• and
• correction generating circuitry coupled synchronously to the column error detection circuitry and the row error detection circuitry and responsive to the signals therefrom for locating an error location of a faulty column parity bit producing the changed column parity bit, for generating a changed bit output signal to said column parity bit memory at the time said error location is next to be conducted through said tap, and for correcting the column parity bit in error.

An error correction system for correcting bit errors randomly introduced into a recirculating memory having a plurality of substantially identical data recirculating registers, each transferring data bits from its output terminal to its input terminal to form a plurality of data memory loops, said error correction system comprising:

• a loop data tap in each data memory loop of the plurality of data memory loops, the tap including gating circuitry for conducting data through its respective loop and for stopping the flow of said data to introduce into the loop an externally controlled data bit;
• column parity bit generating circuitry coupled to the output of the loop data tap in each of said plurality of data loops for computing parity bits from all data bits in said plurality of loops that are simultaneously moved through their respective data tap;
• row parity bit generating circuitry coupled to the output of the tap in each of said plurality of data loops for computing a parity bit from a group of data bits in each of the plurality of data loops as the bits in said group are serially moved through their respective data taps;
• parity bit storage circuitry coupled to the column and the row parity generator circuitry for separately storing the column parity bits and the row parity bits in a column parity bit memory and a row parity bit memory, respectively, each of the parity memories having a capacity for storing and recirculating, in synchronization, all of its respectively computed parity bits generated during a circulation of all data stored in the recirculating memory;
• column error detection circuitry coupled to the column parity bit generating circuitry and to the column parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored and generated parity bits representing data bits occupying the same location in the recirculating memory, the column error detection circuitry producing an error output signal when the next generated parity bit has changed its state from that of its corresponding stored parity bit;
• row error detection circuitry coupled to the row parity bit generating circuitry and to the row parity bit storage circuitry for comparing each stored parity bit with the next corresponding generated parity bit, both stored parity bit and corresponding generated parity bit representing data bits occupying the same data bit group and data loop in the recirculating memory, the row error detection circuitry producing an error output signal when said next generated parity bit has changed its state from that of its corresponding stored parity bit;
• and
• correction generating circuitry coupled synchronously to the column error detection circuitry and the row error detection circuitry and responsive to the signals therefrom for locating an error location of a faulty row parity bit producing the changed row parity bit, for generating a changed bit output signal to said row parity bit memory at the time said error location is next to be conducted through said tap, and for correcting the row parity bit in error.