Plural channel error correcting methods and means using adaptive reallocation of redundant channels among groups of channels

• US 4,201,976 A
• Filed: 12/23/1977
• Issued: 05/06/1980
• Est. Priority Date: 12/23/1977
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Patel, Arvind M.
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/863,653
• Time in Patent Office: 865 Days
• Field of Search: 340/146.1 AL, 340/146.1 AV
• US Class Current: 714/804
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

Where data is recorded on logically independent sets of parallel channels or tracks, the correction of error of very long (infinite) length cannot be advantageously treated by conventional coding methods unlike finite length error such as single shot or burst noise. To ensure the correction of channels in error from data recovered from a multi-channel storage medium, a fixed number of channels per set are dedicated to error checking bits. In this invention, more than the usual number of channels in error in any one set are made correctable by adaptively reallocating the unused redundant channels in the other set. This is accomplished by encoding and recording in the first redundant channel in each set vertical parity checks limited to that set while encoding and recording in the second redundant channel of each set, the parity of data taken over both sets of channels in a predetermined positively or negatively sloped direction. With this type of parity information so recorded, then the data obtained from up to three known erroneous channels in any one set may be corrected, provided that two sets together aggregate not more than four channels in error. Advantageously, the vertical and cross-parity checking information can also be used to generate an internal channel-in-error pointer for the first erroneous track in each set. Additionally, this data can be made to yield a second internal channel-in-error pointer in at least one of the sets. Lastly, error patterns are identified upon decoding at the intersection of at least two error syndromes one of which is derived from cross-parity checking bits.

Claims

1. In combination:

a parallel multi-channel data handling system (FIG. 1-3, 5,

     7), the channels (FIG.

     6) being partitioned into a first and second set;

means for ascertaining channels in error externally and generating pointer signals (i,j,k,x,y,z); and

apparatus (9,

     19) for correcting up to three channels in error in any one set, the other set having no more than one channel in error;

said apparatus comprising;

means (9) for encoding and writing into a first channel in each set vertical parity checks limited to that set;

means (9, 193-207, FF1-FF7) for encoding and writing into a second channel of each set parity checks taken over both sets of channels in a predetermined positively or negatively sloped direction;

means (25, 27, FIGS. 7 and

     8) for determining syndromes (Sv_m^a, Sv_m^b, Sd_m+i^a, Sd_m+x^b, S_A, S_B) from the parity checks and data written into the channels;

means (29, FIG.

     10) responsive to the external pointer signals designating at least one known channel in error for generating correction signals (e_m^a, e_m^b) from at least two syndromes intersecting the same error in the known error channel; and

means (31, FIG.

     11) for correcting said errors by logically combining the correction signals (e_m^a, e_m^b) with the original known channel data (A_m, B_m).

2. In a parallel multichannel data handling system according to claim 1, wherein said apparatus further comprises:

means (401, 407, 405, 406, FIG. 13b ) responsive to the syndrome determining means (25) for generating an internal pointer (415,

     417) to an unknown channel in error (channel I-FIG. 12c, channel K-FIG. 12d) in the first set having a first known channel in error (channel J FIGS. 12c&

d) and the remaining set having one known channel in error.

3. In a parallel multi-channel data handling system according to claim 1, wherein of the two intersecting syndromes, one of which is a diagonal syndrome.

4. In a parallel multi-channel data handling system according to claim 1, wherein said means for generating correction signals include means for selecting as between two diagonal syndromes the one closest to the channel in error.

5. In a parallel multi-channel data handling system according to claim 1, wherein the means for generating correction signals includes means for modifying the diagonal check syndrome by logically combining said syndrome with the correction signal in the same manner as the correction signal is combined with the original channel data.

6. In combination:

a parallel muti-channel data handling system, the channels being partitioned into a first and second set;

means for ascertaining channels in error externally and generating pointer signals thereto (i,j,k,x,y,z); and

apparatus for correcting up to three channels in error in any one set, the other set having no more than one channel in error;

said apparatus comprising;

means (9, 193-207, FF1-FF7, FIGS. 2-4) for encoding and writing into a first channel in each set vertical parity checks limited to that set and for encoding and writing into a second channel of each set parity checks taken over both sets of channels in a predetermined positively or negatively sloped direction;

means (25, 27, FIGS. 7,8) for determining syndromes from the parity checks and data written into the channels;

means (423, 425, FIG. 13b) for detecting mismatches between the vertical and diagonal syndromes intersecting the same error (FIGS. 12C,D) in a known error channel, one syndrome intersecting an unknown error channel; and

means (401, 407, 405,

     406) responsive to an external pointer (i,j) designating a known error channel in the first set and to the detected mismatches for generating an internal pointer to the unknown error channel in the same set as a function of the displacement between the first and a subsequent mismatch.

7. In a parallel multi-channel data handling system according to claim 6, wherein the means for generating an internal pointer includes:

a counter initialized to the number of the known channel in error;

means for selectively incrementing or decrementing said counter; and

logic means coupling the syndrome determining means for causing the incrementing means to change the counter value such that if a near or far diagonal syndrome is unequal in the first mismatch then the counter is incremented until a vertical syndrome is detected as being unequal in a second mismatch.

8. In a parallel multi-channel data handling system according to claim 7, wherein the means for generating an internal pointer includes:

means for pointing to the first redundant channel if the vertical syndrome is unequal in the first syndrome mismatch.

9. In combination with a paralled multi-channel data handling system, the channels being partitioned into a plurality of logically independent sets of channels including a set of common channels;

means for ascertaining channels in error externally and generating pointer signals thereto;

an apparatus for correcting up to three channels in error in any one set, there being no more than one other channel in error in the aggregate of the other sets;

said apparatus comprising;

means for encoding in a first channel in each set other than the common set, vertical parity checks limited to that set;

means for encoding respectively in a first and second channel of the common set parity checks taken over all of the sets of channels respectively in a predetermined positively or negatively sloped direction;

means for determining syndromes from the parity checks and data recorded in the channels;

means responsive to external pointer designating known channels in error for generating correction signals from at least two syndromes intersecting the same error in the known channel; and

means for correcting said errors by logically combining the correction signals with the original channel data.

10. In an apparatus for encoding and writing of data into a plurality of parallel channels, said channels being partitioned into logically independent sets, the combination comprising:

means for encoding and writing into a first channel of each set vertical parity checks limited to that set; and

means for encoding diagonal parity checks taken over all of the channels in a predetermined positively or negatively sloped direction and writing said encoded diagonal parity checks in a format selected from the group consisting of bits written in a second channel in each set, and regularly spaced bytes written in the cross-channel direction.

11. In an apparatus for decoding data written into a plurality of parallel channels, means for ascertaining channels in error externally and generating pointer signals thereto, said channel plurality being partitioned into logically independent sets, a first channel of each set containing vertical parity checks limited to that set, diagonal parity checks taken over all channel sets in a predetermined positively or negatively sloped direction being formatted from one of a group consisting of bits written into a second channel in each set, and regularly spaced bytes written in the cross-channel direction;

the combintion comprising;

means for determining syndromes from the parity checks and data written into the channels;

means for detecting mismatches between the vertical and diagonal syndromes intersecting the same error in a known error channel, one syndrome intersecting an unknown error channel; and

means responsive to an external pointer signal designating a known error channel in a first set and to the detected mismatches for generating an internal pointer to an unknown error channel in the first set as a function of the displacement between the first and subsequent vertical and diagonal syndrome mismatch, the number of channels in error in any one set not exceeding three while the aggregate of channels in error cannot exceed four.

12. In an apparatus for decoding data written into a plurality of parallel channels, said channel plurality being partitioned into logically independent sets, a first channel of each set containing vertical parity checks limited to that set, diagonal parity checks taken over all channel sets in a predetermined positively or negatively sloped direction, said diagonal parity checks being formatted from one of a group consisting of bits written into a second channel in each set, and regularly spaced bytes written in the cross-channel direction;

the combination comprising;

means for determining syndromes from the parity checks and data written into the channels; and

means (401, 407, 405, FIG. 13a) responsive to vertical (63) and diagonal (75) syndromes intersecting the same error (FIGS. 12a, b) for generating a first channel in error pointer (504, pointer j) as a function of the bit position displacement in the in-channel direction between the vertical and diagonal checking bit positions, the errors being confined to only one unknown channel in the first set and at most two channels in the second set.

13. In an apparatus according to claim 12, wherein the channel pointer means includes a free-running ring counter of the count-down type;

first means responsive to the occurrence of a diagonal syndrome for setting the ring counter to a predetermined value; and

second means responsive to the occurrence of a vertical syndrome for inhibiting the ring counter and gating out its contents.

14. In an apparatus for decoding data according to claim 12, wherein the means for generating a pointer to an unknown error channel responsive to a pointer designating a known error channel includes a first and second free running cyclic counter, said first counter being of the count-down type while the second counter being of the count-up type;

and means responsive to the external pointer for setting both counters to a value indicative of the known channel in error, the counters respectively being decremented or incremented each time the bit position along the channel changes until a vertical syndrome is detected as not being equal to the other syndromes in the first set.