Stored data error correction system

• US 4,908,826 A
• Filed: 01/05/1988
• Issued: 03/13/1990
• Est. Priority Date: 01/05/1988
• Status: Expired due to Fees

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Hertrich, Friedrich R.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): BEAUSOLIEL JR, ROBERT W
• Application Number:
  US07/141,061
• Time in Patent Office: 798 Days
• Field of Search: 371/38, 371/39, 371/40, 371/37, 371/2, 371/40.1, 371/40.2, 371/39.1, 371/38.1, 371/37.4, 371/37.1, 371/2.2, 360/38.1, 360/48, 360/53
• US Class Current: 714/755
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

In a multi-track digital recording medium, data blocks on different tracks are algebraically combined to generate an error correction code (ECC) stored in an ECC block on one of the tracks. Unrecoverable errors due to horizontal and vertical clustering of dropouts on magnetic tape, for example, are reduced by XOR-ing data blocks along a diagonal path traversing several tracks to form the ECC.

Claims

1. A method of generating an error correction code (ECC) for parallel track data recording on a recording medium in which several adjacent tracks are defined, each track including a series of blocks of recorded information arranged in a repeating alternating sequence of a group of data blocks and at least one associated ECC block, comprising

defining an ECC entity having a predetermined width encompassing several adjacent tracks and a predetermined length encompassing several consecutive data blocks in each track, and

algebraically combining data destined for a first set of data blocks on one track within said ECC entity with data destined for a second set of other blocks on other tracks within said ECC entity to form an ECC for an ECC block within said ECC entity on said one track,

whereby the data in any single missing or defective one of said first or second set of blocks can be algebraically reconstructed.

2. The method of claim 1, wherein no two of said other data blocks are on the same track.

3. The method of claim 1, wherein said other data blocks are diagonally space on neighboring tracks within said ECC entity.

4. The method of claim 1, wherein the step of combining said data blocks includes XORing data in said first and second set of data blocks in said ECC entity to form said ECC.

5. The method of claim 1, wherein said other blocks include one block from each other track within said ECC entity.

6. The method of claim 1, wherein said ECC entity forms an n x n matrix having n tracks each with at least n-1 data blocks and 1 ECC block.

7. The method of claim 6, wherein said ECC is determined by the algorithm:

##EQU10## where E_t is the ECC for track t and the tracks are numbered from 1 to n, respectively, b is the block number, the blocks being numbered from 1 to n-1, respectively, the ECC block being the nth block in the ECC entity, mod n designating arithmetic within the wraparound number set comprised of a repeating sequence of integers from 1 to n.

8. The method of claim 1, wherein each track in said ECC entity has an ECC block, further comprising performing said algebraic combination so that a combination of all the ECC blocks in the ECC entity produces a known fixed result, whereby a single missing or defective ECC block can be reconstructed from the parity relationship between all of the ECC blocks.

9. A recording medium with prerecorded digital data in a format including an error correction facility, comprising

a plurality of adjacent tracks defined in said recording medium, each track including a series of blocks of recorded information arranged in a series of data blocks and at least one associated ECC block, and

an ECC entity defined in said medium having a predetermined width encompassing several adjacent tracks and a predetermined length encompassing several consecutive data blocks in each track, and

an ECC recorded in an ECC block on one track being an algebraic combination of data in a first set of data blocks on said one track with data in a second set of other blocks on other tracks of said recording medium,

whereby the data in any single missing or defective one of said first or second set of blocks can be algebraically reconstructed.

10. The medium of claim 9, wherein no two of said other data blocks are on the same track.

11. The medium of claim 9, wherein said other data blocks are diagonally spaced on neighboring tracks.

12. The medium of claim 9, wherein said ECC is formed by XOR-ing data in said first and second sets of data blocks.

13. The medium of claim 9, wherein said other blocks include one block from each other track within an ECC entity.

14. The medium of claim 9, wherein the tracks and blocks corresponding to said ECC form an n x n matrix having n tracks each with at least n-1 data blocks and one ECC block.

15. The medium of claim 14, wherein the ECC is determined by the algorithm:

##EQU11## where E_t is the ECC for track t and the tracks are numbered from 1 to n, respectively, b is the block number, the blocks being numbered from 1 to n-1, respectively, the ECC block being the nth block in the ECC entity, mod n designating arithmetic within the wraparound number set comprised of a repeating sequence of integers from 1 to n.

16. A method of generating an error correction code (ECC) for parallel track data recording on a recording medium in which several adjacent tracks are defined, each track including a series of blocks of recorded information arranged in a repeating alternating sequence of a group of data blocks and at least one associated ECC block, comprising

defining an ECC entity having a predetermined width encompassing several adjacent tracks and a predetermined length encompassing several consecutive data blocks in each track, and

algebraically combining data destined for a first set of data blocks on one track within said ECC entity with data destined for a second set of other blocks on other tracks within said ECC entity to form an ECC for an ECC block within said ECC entity on said one track,

wherein said ECC entity forms an n x n matrix having n tracks each with at least n-1 data blocks and 1 ECC block,

wherein said ECC is determined by the algorithm:

##EQU12## ##EQU13## where E_t is the ECC for track t and the tracks are numbered from 1 to n, respectively, b is the block number, the blocks being numbered from 1 to n-1, respectively, the ECC block being the nth block in the ECC entity, mod n designating arithmetic within the wraparound number set comprised of a repeating sequence of integers from 1 to n.

whereby the data in any single missing or defective one of said first or second set of blocks can be algebraically reconstructed.

17. A recording medium with precorded digital data in a format including an error correction facility, comprising

a plurality of adjacent tracks defined in said recording medium, each track including a series of blocks of recorded information arranged in a series of data blocks and at least one associated ECC block, and

an ECC entity defined in said medium having a predetermined width encompassing several adjacent tracks and a predetermined length encompassing several consecutive data blocks in each track, and

an ECC recorded in an ECC block on one track being an algebraic combination of data in a first set of data blocks on said one track with data in a second set of other blocks on other tracks of said recording medium,

wherein the tracks and blocks corresponding to said ECC form an n ×

n matrix having n tracks each with at least n-1 data blocks and one ECC block,

wherein the ECC is determined by the algorithm;

##EQU14## where E_t is the ECC for track t and the tracks are numbered from 1 to n, respectively, b is the block number, the blocks being numbered from 1 to n-1, respectively, the ECC block being the nth block in the ECC entity, mod n designating arithmetic within the wraparound number set comprised of a repeating sequence of integers from 1 to n.

whereby the data in any single missing or defective one of said first or second set of blocks can be algebraically reconstructed.