Mass storage error correction and detection system, method and article of manufacture

• US 6,467,060 B1
• Filed: 06/25/1999
• Issued: 10/15/2002
• Est. Priority Date: 06/26/1998
• Status: Expired due to Term

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Tsang, Kinhing Paul, Malakapalli, Krishna Rameshwara
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/344,759
• Time in Patent Office: 1,208 Days
• Field of Search: 714/755, 714/758, 714/769, 714/805
• US Class Current: 714/758
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: G11B 20/1813 by adding special bits or symbols to the coded information G11B20/1809 takes precedence
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation

Abstract

Data integrity is increased on mass-storage devices through a scheme whereby, a frame-based cyclic redundancy code (CRC) for each sector is recorded. A frame-based CRC is generated from the CRCs of the frames that compose a sector of data. In recording data, a CRC is generated from each frame, later, a master CRC is generated from the frame CRCs, then sector and master CRC are recorded on the mass-storage device medium. In retrieving data, the sector composed of frames and a master CRC are read, a plurality of CRCs are generated from each of the frames, a second master CRC is generated from the frame CRCs, and the master CRCs are compared to determine data integrity. In another embodiment, an input/output error detection and correction checksum (IOEDC), an error correction code (ECC) and a CRC are generated from a sector of data, and the IOEDC, ECC and CRC are stored on disc with the data sector.

Claims

1. A method for generating a master cyclic redundancy code, the method comprising steps of:

(a) receiving a plurality of data frames and an equal number of frame cyclic redundancy codes associated with each of the frames;

(b) generating a master cyclic redundancy code from the plurality of frame cyclic redundancy codes;

(c) discarding the frame cyclic redundancy codes;

(d) assembling the plurality of data frames into a contiguous buffer of data;

(e) generating error correction code for the contiguous buffer; and

(f) transmitting the buffer, the master cyclic redundancy code and the error correction code to a destination medium.

2. The method of claim 1 wherein:

the receiving step (a) includes;

(a)(i) receiving a plurality of bytes;

(a)(ii) aggregating the plurality of bytes into a frame;

(a)(iii) generating a first cyclic redundancy code from the frame; and

(a)(iv) buffering the data frame and the first cyclic redundancy code; and

the buffering step (a)(iv) includes;

(a)(iv)(1) storing the frame and the first cyclic redundancy code in memory;

(a)(iv)(2) retrieving the frame and the first cyclic redundancy code from memory; and

(a)(iv)(3) verifying the integrity of the retrieved frame and the retrieved first cyclic redundancy code.

3. The method of claim 2 wherein:

the storing step (a)(iv)(1) includes storing the frames sequentially in a first portion of the memory, and storing the cyclic redundancy codes sequentially in a second portion of the memory; and

the verifying step (a)(iv)(3) includes generating a third cyclic redundancy code from the retrieved frame, comparing the first cyclic redundancy code to the third cyclic redundancy code, and discarding the retrieved frame and the first cyclic redundancy code and continuing at the retrieving step (a)(iv)(2) if the comparison does not indicate equality.

4. A method for verifying integrity based on a master cyclic redundancy code, the method comprising steps of:

(a) receiving from a source medium a sector of data, a logical block address of the sector, and a first master cyclic redundancy code, wherein the first master cyclic redundancy code is generated by;

(1) receiving a plurality of data frames of the sector and an equal number of frame cyclic redundancy codes associated with each of the frames of the sector;

(2) generating the first master cyclic redundancy code from the plurality of frame cyclic redundancy codes;

(3) discarding the frame cyclic redundancy codes;

(4) assembling the plurality of data frames into a contiguous buffer of data;

(5) generating error correction code for the contiguous buffer; and

(6) transmitting the contiguous buffer, the first master cyclic redundancy code and the error correction code to the source medium; and

(b) verifying the integrity of the sector and the first master cyclic redundancy code.

5. The method of claim 4 wherein the verifying step (b) includes:

(b)(i) dividing the sector into a plurality of frames;

(b)(ii) generating one cyclic redundancy code from each of the plurality of frames;

(b)(iii) generating a second master cyclic redundancy code from the frame cyclic redundancy codes;

(b)(iv) comparing the first master cyclic redundancy code to the second master cyclic redundancy code; and

(b)(v) discarding the received sector and the first master cyclic redundancy code and requesting retransmission from the source medium, if the comparison in step (b)(iv) does not indicate equality.

6. The method of claim 4 further comprising steps of:

(c) dividing the sector into a plurality of frames; and

(d) transmitting the plurality of frames to a receiving medium.

7. The method of claim 6 wherein the transmitting step includes buffering the data frames and a plurality of cyclic redundancy codes generated from the plurality of frames and the buffering including steps of:

(d)(i) storing a frame and a cyclic redundancy code in memory;

(d)(ii) retrieving the frame and the cyclic redundancy code from memory; and

(d)(iii) verifying the integrity of the retrieved frame and the retrieved cyclic redundancy code.

8. The method of claim 7 wherein:

the storing step (d)(i) includes storing the frame sequentially in a first portion of the memory, and storing the cyclic redundancy code sequentially in a second portion of the memory;

the verifying step (d)(iii) includes generating a second cyclic redundancy code from the retrieved frame, comparing the first cyclic redundancy code to the second cyclic redundancy code, and discarding the retrieved frame and the first cyclic redundancy code and the first cyclic redundancy code continuing at the retrieving step (d)(ii) if the comparison does not indicate equality.

9. An apparatus for generating a master cyclic redundancy code comprising:

a mass-storage device; and

a controller operatively coupled to the mass-storage for receiving through an input port a plurality of frames, generating a frame cyclic redundancy code from each of the frames, generating a master cyclic redundancy code from the frame cyclic redundancy codes, generating an error correction code from the plurality of frames, discarding the frame cyclic redundancy codes, and transmitting to the mass-storage device the plurality of data frames, the master cyclic redundancy code and the error correction code.

10. The apparatus of claim 9 wherein the mass-storage device includes one or more devices selected from the group consisting of a magnetic disc, an optical disc, and a tape cartridge.

11. The apparatus of claim 9 in which the controller comprises:

a receiver, operatively coupled to the input port, that receives from the input port the plurality of frames and a logical block address associated with the frames, and generates a frame cyclic redundancy code from each of the frames, the generating of the frame cyclic redundancy codes being seeded with the logical block address;

a frame-based CRC generator operatively coupled to the receiver that receives the plurality of frames and the frame cyclic redundancy codes generated from the plurality of frames, generates a master cyclic redundancy code from the frame cyclic redundancy codes, and aggregates the frames into a sector, and generates an error-correction code from the sector, the generating of the error-correction code being seeded with the logical block address; and

a transmitter operatively coupled between the frame-based CRC generator and the mass-storage device that receives the sector, master cyclic redundancy code and error-correction code from the frame-based CRC generator and transmits the sector, the master cyclic redundancy code and the error-correction code to the mass-storage device.

12. The apparatus of claim 11 in which the receiver includes:

a frame aggregator operatively coupled to the input port for receiving a plurality of bytes, aggregating the plurality of bytes into a frame;

a first cyclic redundancy code generator operatively coupled to the frame aggregator for receiving the plurality of frames and operatively coupled to the input port for receiving a logical block address, and generating a plurality of frame cyclic redundancy codes from the frames, wherein one frame cyclic redundancy code is generated from each of the frames, the generating of the frame cyclic redundancy codes being seeded with the logical block address; and

a buffer device operatively coupled to the frame aggregator and operatively coupled to the first cyclic redundancy code generator that buffers the frames and the cyclic redundancy codes and sends the frames and the cyclic redundancy codes to the frame-based CRC generator.

13. The apparatus of claim 12 wherein the buffer device includes:

a memory device operatively coupled to the first cyclic redundancy code generator and the memory device responsive to;

a write command to store the frames and the first cyclic redundancy codes in the memory device, and responsive to a read command to retrieve the frame and the first cyclic redundancy code from the memory device; and

a verifier operatively coupled between the memory device and the first frame-based CRC generator that operates to verify an integrity of a retrieved frame and a retrieved frame cyclic redundancy code wherein the verifier includes;

a second cyclic redundancy code generator operatively coupled to the memory device for generating a second cyclic redundancy code from the frame, the generating of the cyclic redundancy code being seeded with the logical block address;

a comparator operatively coupled to the second cyclic redundancy code generator and operatively coupled to the memory device for comparing the first cyclic redundancy code to the second cyclic redundancy code; and

a selector operatively coupled to the comparator for discarding the frame, the first cyclic redundancy code and the second cyclic redundancy code and requesting re-retrieval from the memory device if the comparator does not indicate equality and for transmitting the sector, first cyclic redundancy code and error-correction code to the frame-based CRC generator if the comparator indicates equality.

14. The apparatus of claim 13 wherein the memory device includes:

a first portion operatively coupled between the first cyclic redundancy code generator and the comparator for storing the cyclic redundancy code; and

a second portion operatively coupled between the frame aggregator and the second cyclic redundancy code generator for storing the frame.

15. The apparatus of claim 11 wherein the frame-based CRC generator includes:

a frame-CRC aggregator operatively coupled to the receiver to receive the plurality of frame cyclic redundancy codes, and aggregate the frame cyclic redundancy codes;

a third cyclic redundancy code generator operatively coupled to the frame-CRC aggregator to receive the frame cyclic redundancy codes and generate a master-cyclic redundancy code from the frame cyclic redundancy codes, and send the master-cyclic redundancy code to the transmitter;

a sector aggregator operatively coupled to the receiver to receive frames from the receiver, and aggregate the frames into a sector, and send the sector to the transmitter; and

a error correction code generator to operatively coupled to the sector aggregator to generate an error correction code from the sector, the generating of the error correction code being seeded with the logical block address, and send the error-correction code to the transmitter.

16. A method of protecting data with an input/output error correction and detection checksum, the method comprising steps of:

(a) receiving a data sector, a physical block address and a logical block address;

(b) generating an input/output error detection and correction checksum from the sector, the generating of the input/output error detection and correction checksum being seeded with the logical block address;

(c) generating a cyclic redundancy code from the sector, the generating of the cyclic redundancy code being seeded with the physical block address; and

(d) generating an error correction code from the sector, the generating of the error correction code being seed with the physical block address.