Method and circuitry for correcting errors in recirculating memories

• US 4,365,332 A
• Filed: 11/03/1980
• Issued: 12/21/1982
• Est. Priority Date: 11/03/1980
• Status: Expired due to Term

• Current Assignee: National Semiconductor Corporation (Texas Instruments, Inc.)
• Original Assignee: Fairchild Camera and Instrument Corporation (ON Semiconductor Corporation)
• Inventors: Rice, Rex
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US06/203,774
• Time in Patent Office: 778 Days
• Field of Search: 371/49, 371/50, 371/51, 371/13, 371/71, 365/200
• US Class Current: 714/746
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G11C 19/00 Digital stores in which the information is moved stepwise, e.g. shift registers

Abstract

A method and circuitry are disclosed for correcting bit errors introduced by random events in a data recirculating memory, such as a charge coupled memory device or a bubble memory. The bit errors, caused by random events such as by alpha particle bombardment or other causes, are corrected in circuitry that generates row and column parity bits corresponding to various segments of the information stored in the memory. Changes in the row and column parity bits uniquely define the location of failed bits circulating through the memory even though each failed bit has no fixed address, so that error detection circuitry thereafter may correct the error during the next or a subsequent bit recirculating cycle. The invention facilitates the use of very large memories, for example, on the order of one billion bits or more.

Claims

1. A method for detecting and correcting bit errors in binary data circulating from the output terminal into the input terminal of a first recirculating memory, said method including the steps of:

sampling the data bits circulating from the first memory and storing said bits in a second recirculating memory operating in synchronization with the first memory;

comparing the state of each stored bit circulating from the second memory with the next bit occupying the corresponding location in the first memory as the next corresponding bit circulates from said first memory;

generating an error detection signal whenever the state of said stored bit differs from that of the next corresponding bit;

reversing the state of the next corresponding bit in response to said error detection signal; and

inserting said reversed state next corresponding bit into the data circulating from the first memory at the next recirculating bit location of the next corresponding bit.

2. 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.

3. The method claimed in claim 2 wherein:

the step of generating new parity bits further includes the step of computing a row parity bit for data bits in odd and even membered locations in data bit groups circulating from each of the recirculating memory registers; and

each of the row parity bit loop and the column parity bit loop have the same storage capacity as one of the plurality of recirculating memory registers.

4. 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.

7. The correction system claimed in claim 4, 5 or 6 wherein each of the plurality of data recirculating registers in said recirculating memory has an interlaced serial-parallel-serial organization, and wherein the data bits in the serial output register are sequentially reorganized.

8. The error correction system claimed in claim 7 wherein said correction generating system includes means for locating the column having a faulty column parity bit and for generating a correct column parity bit signal to the proper bit location in said column parity bit storage circuitry.

9. The error correction system claimed in claim 7 wherein said correction generating system includes circuitry means for locating a serial bit group having a faulty row parity bit and for generating a correct row parity bit signal to the proper location in said row parity bit storage circuitry.

10. The error correction system claimed in claim 7 wherein said correction generating system includes circuitry means for locating the column location having a faulty column parity bit and the bit group having a faulty row parity bit, and further includes timing and loop selection circuitry for transferring said changed bit output signal, at the appropriate instant, to the loop data tap associated with the data memory loop containing the faulty data bit.

11. The correction system claimed in claim 7 wherein the correction generating circuitry includes addressing circuitry for sequentially addressing each of the plurality of data memory loops in said recirculating memory, the addressing circuitry being enabled by the occurrences of an error output signal from the row error detection circuitry.

12. The correction system claimed in claim 11 wherein the correction generating circuitry further includes counting circuitry, the counting of which is initiated by the occurrence of an error output signal from said column error detection circuitry, the counting circuitry generating a change bit enabling signal to said addressing circuitry at the moment for next arrival at the respective loop tap of the faulty bit that produced the row and column parity bit error output signals.

13. The correction system claimed in claim 7 wherein the row parity bit generating circuitry includes first and second input flip-flops enabled by the state of the data bit at each of the plurality of loop data taps, the first and second flip-flops being activated by alternate common cycles, the row parity bit generating circuitry further including a parallel-input serial-output shift register, first and second parallel input terminal pairs of which are coupled to each of the first and second input flip-flops, respectively.

14. The correction system claimed in claim 13 wherein the first and second input flip-flops in the row parity bit generating circuitry are enabled by data bits in odd and even bit locations emanating from the recirculating register serial output register.

15. The correction system claimed in claim 7 wherein the recirculating memory is dynamic and includes a plurality of sixteen data recirculating registers, wherein the row parity bit generator includes sixteen pairs of odd-even input flip-flops, each cleared every 32 counts of a common clock, and a 32-bit parallel input serial output shift register having its output clocked every 32 clock counts.

16. The correction system claimed in claim 12 wherein each of the memory loops has 4096 circulating data storage locations and wherein the correction generating circuitry clock counting circuitry generates the change bit enabling signal 4095 clock counts after being enabled by the occurrence of a column error output signal.

5. 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.

6. 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.