Method and apparatus for error detection and correction in systems comprising floppy and/or hard disk drives

• US 4,667,326 A
• Filed: 12/20/1984
• Issued: 05/19/1987
• Est. Priority Date: 12/20/1984
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Shebanow, Michael C., Young, Mark S., Drew, John
• Primary Examiner(s): Ruggiero, Joesph
• Assistant Examiner(s): Beausoliel, Jr., Robert W.
• Application Number:
  US06/685,018
• Time in Patent Office: 880 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40
• US Class Current: 714/762
• 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: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/2789 Interleaver providing variable interleaving, e.g. variable block sizes

Abstract

A method and apparatus for generating a check sum and a syndrome for detecting errors in a series of bytes comprising a plurality of stages, each stage comprising a plurality of networks of exclusive OR gates, a memory and an exclusive OR gate for exclusively ORing the outputs of the networks resulting from a byte transmitted therethrough with the results stored in a memory in a previous stage due to a previous byte. Each of the stages and the networks therein correspond to a term in a Reed-Solomon polynomial. Except for differences in the number and construction of the networks in each stage, each of the stages are substantially identical and can be selectively used for detecting single and double burst errors.

Claims

1. In an error detection and correction apparatus comprising a series of stages, each of said stages having a first and a second network of exclusive OR gates, a single exclusive OR gate having a first input, a second input and an output, a memory device, means for selectively coupling said first input to said first network and said first location, means for coupling said output to said memory device, means for selectively coupling said second input to the output of the memory device in another stage and to said second network and means for coupling the output of said memory device in each stage to said second network;

a method for detecting and correcting errors in data being transferred between a first location and a second location comprising the steps of;

(a) initializing the contents of the memory device in each of said stages;

(b) transferring each byte in said series of bytes from said first location through said first network in each of said stages;

(c) exclusively ORing the output of said first network in each of said stages with said output of said memory device in said other stage which was generated in response to a preceding byte in said series;

(d) storing the results of said latter step in said memory device of said stage;

(e) repeating steps (b)-(d) until each of said bytes in said series has been transferred through said series of stages and the contents of the memory device in each of said stages comprises a check sum;

(f) storing said series of bytes and said check sum in the memory device in each of said stages to said second location;

(g) initializing the contents of the memory device in each of said stages;

(h) exclusively ORing each of said bytes in said series and said check sum stored therewith at said second location with an output from said second network of exclusive OR gates which is generated in response to the contents of the memory device in said stage;

(i) storing the results of said latter step in said memory device;

(j) repeating steps (h) and (i) until each of said bytes in said series and said check sum has been transferred from said second location through said series of stages and the contents of the memory device in each of said stages comprises a syndrome; and

(k) providing an error detect signal if any one of said bytes in said syndrome comprises a predetermined logical level.

2. In an error detection and correction apparatus comprising a series of stages, each of said stages having a first and a second network of exclusive OR gates, a single exclusive OR gate having a first input, a second input and an output, a memory device, means for selectively coupling said first input to said first network and said first location, means for coupling said output to said memory device, means for selectively coupling said second input to the output of the memory device in another stage and to said second network and means for coupling the output of said memory device in each stage to said second network;

a method of detecting and correcting errors in data being transferred between a first location and a second location comprising the steps of;

(a) initializing the contents of the memory device in each of said stages;

(b) transferring a first byte in said series from said first location through a first network of exclusive OR gates in each of said series of stages;

(c) exclusively ORing the output of each of said first networks in each of said stages with the initial contents of said memory in another stage;

(d) storing the output of said single exclusive OR gate in said memory in each of said stages;

thereafter

(e) transferring the next byte in said series from said first location through each of said first networks in each of said stages;

(f) exclusively ORing the output of each of said first networks in each of said stages resulting from said previous step with the contents of said memory in said other stage of said series of stages which resulted from the immediate previous byte in said series;

(g) replacing the contents of each of said memories in each of said stages due to said immediate previous byte with the results of said preceding step;

(h) repeating steps (e)-(g) for each remaining byte in said series whereupon, at the completion thereof, the combined contents of said memories in said stages comprises a check sum comprising a plurality of bytes to be stored with said series of bytes;

(i) initializing the contents of the memory device in each of said stages;

(j) exclusively ORing the first byte in said series of bytes and check sums with the output of each of the said second networks;

(k) storing the result of said latter step in each of said memories in each of said stages;

thereafter

(l) transferring the contents of each of said memories through a second network in each of said stages;

(m) exclusively ORing the output of each of said second networks with the next byte in said series of bytes and check sum;

(n) replacing the contents of each of said memories resulting from said previous byte with the results of said latter step;

thereafter;

(o) repeating steps (l)-(n) for each byte in said series of bytes and check sum whereupon, at the completion thereof, the combined contents of said memories in said stages comprises a syndrome comprising a plurality of bytes; and

(p) detecting whether any of said bytes in said syndrome comprises a bit having a predetermined logical level.

3. A method according to claim 2 wherein each of said stages and said networks therein corresponds to a predetermined term in a Reed-Solomon error detection polynomial.

4. A method according to claim 2 comprising the step of storing the bytes forming said check sum at the end of said series of bytes.

5. A method for generating a check sum for detecting errors in a series of bytes in an apparatus having a memory in each of a series of stages comprising the steps of:

(a) applying each byte in said series to a network exclusive OR gates in each of said series of stages;

(b) applying simultaneously to inputs of an exclusive OR gate in each of said stages the output of the network in said stage and the contents of the memory in a preceding stage

(c) storing in said memory in each of said stages the output of said exclusive OR gate in said stage for use in processing the next byte in the next stage such that upon completion of the processing of all of said bytes in said series, said memories contain a check sum to be stored with said series.

6. A method of generating a syndrome for detecting errors in a series of bytes comprising a data record and a check sum comprising the steps of:

(a) applying simultaneously to the inputs of an exclusive OR gate in each of a plurality of stages, each byte in said series of bytes and the output of a network of an exclusive OR gate;

thereafter

(b) storing the output of said OR gate in a memory in said stage for use by said network in processing the next byte such that upon completion of the processing of all bytes in said series, the combined contents of the memories in all of said stages comprise a syndrome; and

(c) providing a predetermined output if said syndrome comprises a bit having a predetermined logical level.

7. An apparatus for generating a check sum and a syndrome for detecting errors in a series of bytes comprising:

(a) a write data bus;

(b) a read data bus; and

(c) a plurality of stages, each comprising;

(i) a first and a second network of exclusive OR gates;

(ii) means for coupling said first of said networks to said write data bus;

(iii) an exclusive OR gate;

(iv) a memory for receiving outputs from said exclusive OR gate;

(v) first means for selectively coupling said exclusive OR gate to said first network in response to a write control signal and to said read data bus in response to a read control signal;

(vi) means for coupling an output of said memory to said second network; and

(vii) second means for selectively coupling said OR gate to an output of said second network in response to said read control signal and to an output of said memory in another of said stages in response to said write control signal.

8. An apparatus according to claim 7 wherein said first and said second selective coupling means comprises a first and a second multiplexer.

9. An apparatus according to claim 7 comprising means coupled to said memory in each of said stages for indicating when one of said memories is storing a bit having a predetermined logical level.

10. An apparatus according to claim 7 wherein said first network in each of said stages comprises a plurality of networks of exclusive OR gates and said first selective coupling means comprises means responsive to a control signal for selectively coupling the output of each of said plurality of networks to said exclusive OR gate.

11. An apparatus according to claim 7 comprising means for reading out the contents of said memory in each of said stages to an internal data bus.

12. An apparatus according to claim 7 wherein each of said networks comprises a network of exclusive OR gates corresponding to a term in a Reed-Solomon error detection and correction polynomial.

13. An apparatus according to claim 7 wherein said memory in each of said stages comprises means for storing a plurality of bytes.

14. An apparatus according to claim 13 wherein said memory in each of said stages comprises means for presetting said memory.