Real time fault tolerant error correction mechanism

• US 4,455,655 A
• Filed: 09/28/1981
• Issued: 06/19/1984
• Est. Priority Date: 09/28/1981
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Galen, Peter M., Wilken, Kent D.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US06/306,634
• Time in Patent Office: 995 Days
• Field of Search: 371/38, 371/37
• US Class Current: 714/758
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11B 2020/10916 Seeking data on the record carrier for preparing an access to a specific address
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes

Abstract

The present invention provides a real-time fault-tolerant hardware error correction device which is typically implemented as a data transfer circuit between a disc memory and a processing unit. It operates in two modes: as an encoding system and error detector on a disc write, and as a decoding system and error corrector on a disc read. In its first mode, each block of data from the processing unit is encoded with an error syndrome as it is transmitted to the disc memory. Two identical linear feedback shift registers (LFSR'"'"'s) are used for error detection purposes. In its second mode, the same two LFSR'"'"'s are implemented with a buffer memory to achieve real-time error correction. Data flow to the LFSR'"'"'s from the disc memory is alternated block-by-block, one block being received by one LFSR and the succeeding block being received by the other LFSR. At the same time that data is channeled to a particular LFSR, it is channeled synchronously to the buffer memory. While one LFSR is decoding the incoming block, the other LFSR is providing output signals to correct the previous data block which is leaving the buffer memory as new incoming data arrives.

Claims

1. An error-correcting code device for transmitting and correcting digital signals between a processing unit and a memory storage device comprising:

control means coupled with said memory storage device for providing first and second sets of control signals associated with successions of blocks of digital signals emanating from said memory storage device;

gating means having a plurality of channels and responsive to said first set of control signals for receiving a succession of blocks of digital signals from said memory storage device, for transmitting said succession of blocks of digital signals into a first channel, and for transmitting synchronously with transmissions into said first channel, block by block, said succession of blocks of digital signals into a second and third channel in an alternating manner;

a buffer memory, coupled to said gating means through said first channel, for receiving said succession of blocks of digital signals and for transmitting said succession of blocks of digital signals so received, one block after another;

first encoder/decoder means for receiving blocks of digital signals from said second channel, and in response to said first set of control signals for both performing error processing on each block and providing alternate blocks of output signals in synchronism in corresponding blocks of digital signals transmitted from said buffer memory, each alternate block of output signals containing an error correcting pattern;

second encoder/decoder means, electrically identical to said first encoder/decoder means, for receiving blocks of digital signals from said third channel, and in response to said first set of control signals for both performing error processing on each block and providing alternate blocks of output signals in synchronism with corresponding blocks of digital signals transmitted from said buffer memory, each alternate block of output signals containing an error correcting pattern;

correction means, coupled to said first and second encoder/decoder means and to said buffer memory, responsive to said first set of control signals, for receiving;

said alternate blocks of output signals from said first encoder/decoder means, said alternate blocks of output signals from said second encoder/decoder means, and said succession of blocks of digital signals from said buffer memory;

said gating means also being responsive to said second set of control signals for receiving a succession of blocks of digital signals from said processing unit and for transmitting said succession of blocks of digital signals simultaneously into said second channel, into said third channel, and into a fourth channel;

said first encoder/decoder means, in response to said second set of control signals, developing a first error syndrome and providing a first set of output characters representing said first error syndrome for each block of digital signals received through said second channel;

said second encoder/decoder means, in response to said second set of control signals, developing a second error syndrome and for providing a second set of output characters representing said second error syndrome for each block of digital signals received through said third channels;

said error detection means, being responsive to said second set of control signals for receiving blocks of digital signals from said second, third and fourth channels, combining said blocks of digital signals from said fourth channel and said output blocks of digital signals from said first encoder/decoder means, providing a succession of encoded blocks of digital signals corresponding to said blocks of digital signals emanating from said processing unit, comparing said first and second sets of output characters developed for each block of digital signals received on said second and third channels, and providing an error flag when said first and second sets of output characters are not identical;

said correction means correcting each block in said succession of blocks of digital signals received from said buffer memory according to said error correcting pattern in each corresponding block of output signals from said first encoder/decoder means and from said second encoder/decode means.

2. A device as in claim 1 wherein:

said first encoder/decoder further comprises a linear feedback shift register; and

said second encoder/decoder further comprises a linear feedback shift register.