Error correction method and apparatus

Claim 3

The method of claim 1, wherein a value for each bit position b x included in each block E i is derived from performing an exclusive OR operation using values of the bits having bit position b x .

Claim 4

The method of claim 1, wherein said storage medium is magnetic tape, further comprising recording said blocks B r ,c on said storage medium, and wherein all blocks B r ,c in the same column are recorded together in a helical stripe on the magnetic tape.

Claim 5

The method of claim 3, wherein k=8, q=1, and m=8.

Claim 6

The method of claim 4, wherein n=16.

Claim 7

The method of claim 1, wherein said m number of error correction blocks E i are the last of the blocks in said group of blocks B r ,c recorded on said storage medium.

Claim 8

The method of claim 6, wherein said storage medium is magnetic tape, further comprising recording said blocks B r ,c on said storage medium, and wherein said step of recording comprises recording all blocks B r ,c having the same column in a helical stripe and subsequently recording said error correction blocks E i in m/q number of helical stripes.

Claim 9

The method of claim 7, further comprising providing in said error correction blocks E i an indication that said block is an error correction block.

Claim 10

The method of claim 1, further comprising using a codeword to operate upon bit positions b x (where x ranges from integer Y to integer Z) to obtain error correction bits for inclusion at additional bit positions in said block B r ,c.

Claim 11

The apparatus of claim 1, further comprising means for recording said blocks B r ,c on said storage medium, wherein said storage medium is magnetic tape, and wherein all blocks B r ,c in the same column are recorded together in a helical stripe on the magnetic tape.

Claim 12

The apparatus of claim 10, wherein k=8, q=1, and m=8.

Claim 13

The apparatus of claim 11, wherein n=16.

Claim 16

The method of claim 13, wherein a value for each bit position b x included in each block E i is derived from a sum of bits having bit position b x for all blocks B r ,c where i=(r+k(c mod q)+INT(c/q)) mod m in which INT(c/q) is the largest integer not greater than c/q).

Claim 17

The method of claim 13, wherein said subgroups are organized so that no blocks in a same column are in a same subgroup.

Claim 18

The method of claim 13 wherein said subgroups are organized so that no sequence of m contiguous blocks in the same row are in the same subgroup.

Claim 19

The method of claim 13, wherein said storage medium is magnetic tape, further comprising recording said blocks B r ,c on said storage medium, and wherein all blocks B r ,c in a same column are recorded together in a helical stripe on the magnetic tape.

Claim 20

The method of claim 17, wherein k=8, q=1, and m=8.

Claim 21

The method of claim 18, wherein n=16.

Claim 22

The method of claim 13, further comprising providing in said error correction blocks E i an indication that said block is an error correction block.

Claim 23

The method of claim 13, further comprising using a codeword to operate upon bit positions b x (where x ranges from integer Y to integer Z) to obtain error correction bits for inclusion at additional bit positions in said block B r ,c.

Claim 26

The method of claim 22, further comprising: including in said error correction blocks E i an indication that said blocks are error correction blocks; and, including in blocks B r ,c which are written as a first stripe of said group of blocks B r ,c that said blocks are not error correction blocks E i .

Claim 27

The method of claim 23, further comprising repeating steps (a) through (c) for a plurality of groups of blocks B r ,c.

Claim 28

Apparatus for encoding informational data for transmission to a storage medium, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived from a sum of the bits having bit position b x in all blocks B r ,c where i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q).

Claim 29

Apparatus for encoding informational data for transmission to a storage medium, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived from a sum of the bits having bit position b x in all blocks B r ,c where i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q).

Claim 30

The apparatus of claim 25, wherein a value for each bit position b x included in each block E i is derived from performing an exclusive OR operation using values of the bits having bit position b x .

Claim 31

The apparatus of claim 25, further comprising means for recording said blocks B r ,c on said storage medium, wherein said m number of error correction blocks E i are the last of the blocks in said group of blocks B r ,c recorded on said storage medium.

Claim 32

The apparatus of claim 25, further comprising means for providing in said error correction blocks E i an indication that said block is an error correction block.

Claim 33

The apparatus of claim 25, further comprising means for using a codeword to operate upon bit positions b x (where x ranges from integer Y to integer Z) to obtain error correction bits for inclusion at additional bit positions in said block B r ,c.

Claim 34

Apparatus of encoding informational data for transmission to a storage medium, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for organizing said blocks B r ,c into subgroups; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, with each block E i being included in one of said subgroups and each subgroup including one of said error correction blocks E i , wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived by performing an exclusive OR operation upon values of the bits having bit position bx for all blocks B r ,c included in the same subgroup; means for recording said blocks B r ,c on said storage medium, wherein all blocks B r ,c having a same column are recorded in a same helical stripe; and for subsequently recording said error correction blocks E i in m/q number of helical stripes.

Claim 35

Apparatus of encoding informational data for transmission to a storage medium, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for organizing said blocks B r ,c into subgroups; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, with each block E i being included in one of said subgroups and each subgroup including one of said error correction blocks E i , wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived by performing an exclusive OR operation upon values of the bits having bit position bx for all blocks B r ,c included in the same subgroup; means for recording said blocks B r ,c on said storage medium, wherein all blocks B r ,c having a same column are recorded in a same helical stripe; and for subsequently recording said error correction blocks E i in m/q number of helical stripes.

Claim 36

The apparatus of claim 30, wherein a value for each bit position b x included in each block E i is derived from a sum of bits having bit position bx for all blocks B r ,c where i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q).

Claim 37

The apparatus of claim 30, wherein said subgroups are organized so that no blocks in a same column are in a same subgroup.

Claim 38

The apparatus of claim 30, wherein said subgroups are organized so that no sequence of m contiguous blocks in a same row are in a same subgroup.

Claim 39

The apparatus of claim 30, further comprising means for recording said blocks B r ,c on said storage medium; wherein said storage medium is magnetic tape, and wherein all blocks B r ,c in the same column are recorded together in a helical stripe on the magnetic tape.

Claim 40

The apparatus of claim 34, wherein k=8, q=1, and m=8.

Claim 41

The apparatus of claim 35, wherein n=16.

Claim 42

The apparatus of claim 30, further comprising means for providing in said error correction blocks E i an indication that said block is an error correction block.

Claim 43

The apparatus of claim 30, further comprising means for using a codeword to operate upon bit positions b x (where x ranges from integer Y to integer Z) to obtain error correction bits for inclusion at additional bit positions in said block B r ,c.

Claim 44

Apparatus for encoding informational data for transmission to a magnetic tape, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived from a sum of the bits having bit position b x in all blocks B r ,c where i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q); and, means for recording all blocks B r ,c in k number of helical stripes on the magnetic tape, with all blocks B r ,c in a same column c being recorded in a same helical stripe on the magnetic tape, and with error correction blocks E i being recorded as the last m/q number of stripes of the n number of stripes.

Claim 45

Apparatus for encoding informational data for transmission to a magnetic tape, said apparatus comprising: means for formatting informational data into at least some of a group of blocks B r ,c, with each block B r ,c belonging to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for generating m number of error correction blocks E i to be included in said group of blocks B r ,c, wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, each of said error correction blocks E i also including bit positions b x wherein x ranges from integer Y to integer Z, and wherein a value for each bit position b x included in each block E i is derived from a sum of the bits having bit position b x in all blocks B r ,c where i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q); and, means for recording all blocks B r ,c in k number of helical stripes on the magnetic tape, with all blocks B r ,c in a same column c being recorded in a same helical stripe on the magnetic tape, and with error correction blocks E i being recorded as the last m/q number of stripes of the n number of stripes.

Claim 46

The apparatus of claim 39, further comprising: means for including in said error correction blocks E i an indication that said blocks are error correction blocks; and, means for including in blocks B r ,c which are written as a first stripe of said group of blocks B r ,c that said blocks are not error correction blocks E i .

Claim 49

The method of claim 41, wherein said summation is obtained by performing an exclusive OR operation using values of the bits having bit position b x .

Claim 50

The method of claim 42, wherein an address of a block B r ,c not readable from said storage medium is used to determine to what subgroup i said block belongs.

Claim 51

The method of claim 41, wherein k=8, q=1, and m=8.

Claim 52

The method of claim 44, wherein n=16.

Claim 53

Apparatus for decoding informational data obtained from a storage medium, said apparatus comprising: means for obtaining from said storage medium a plurality of blocks B r ,c belonging to group G, wherein each block B r ,c belongs to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for summing, for blocks B r ,c correctly readable from said storage medium, and for each of a plurality m-1 of subgroups i, the bit positions b x of the blocks B r ,c belonging to each subgroup i, thereby obtaining a summation for each of the bit positions b x , wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, and wherein i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q); and, means for using said summation for a subgroup i to derive the bit positions b x of a block B r ,c included in said subgroup i but not readable from said storage medium.

Claim 54

Apparatus for decoding informational data obtained from a storage medium, said apparatus comprising: means for obtaining from said storage medium a plurality of blocks B r ,c belonging to group G, wherein each block B r ,c belongs to a row r and a column c, with r ranging from 0 to k-1 and with c ranging from 0 to n-1, and with each block B r ,c including bit positions b x wherein x ranges from an integer Y to an integer Z; means for summing, for blocks B r ,c correctly readable from said storage medium, and for each of a plurality m-1 of subgroups i, the bit positions b x of the blocks B r ,c belonging to each subgroup i, thereby obtaining a summation for each of the bit positions b x , wherein i ranges from 0 to m-1, wherein m=q×k with q being an integer constant, and wherein i=(r+k(c mod q)+INT(c/q))mod m in which INT(c/q) is the largest integer not greater than c/q); and, means for using said summation for a subgroup i to derive the bit positions b x of a block B r ,c included in said subgroup i but not readable from said storage medium.

Claim 55

The apparatus of claim 46, wherein means for summing comprises an exclusive OR logic gate.

Claim 56

The method of claim 46, wherein an address of a block B r ,c not readable from said storage medium is used to determine to what subgroup i said block belongs.

Claim 57

The method of claim 46, wherein k=8, q=1, and m=8.

Claim 58

The method of claim 49, wherein n=16.