Methods and means for simultaneously correcting several channels in error in a parallel multi channel data system using continuously modifiable syndromes and selective generation of internal channel pointers

• US 4,205,324 A
• Filed: 03/07/1978
• Issued: 05/27/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/884,463
• Time in Patent Office: 812 Days
• Field of Search: 340/146.1 AL
• 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
• CPC Class Codes: H03M 13/1162 Array based LDPC codes, e.g. array codes

Abstract

An apparatus for simultaneously correcting several channels in error is combined with a parallel multi channel data handling system. The apparatus encodes and records vertical parity checks in a first channel and encodes and records parity checks in a second and third channel or equivalent taken over the channels in respective predetermined positively and negatively sloped directions.

Upon readback, syndromes from the parity checks and the recorded data are obtained. Correction signals from at least two syndromes intersecting the same error in a known channel in error are formed. The values of the syndromes diagonally intersecting each error in the known channel are continuously modified as the error is detected by inversion of the simple parity. Correction is attained by logically combining the correction signals with the original known channel in error data.

Internal pointers to either first or subsequent channels in error are generated as a function of the bit position displacement in the in-channel direction between the occurrence of first and subsequent mismatches of vertical and diagonal syndromes. Internal pointers are generated either in the absence of or to supplement any external pointers.

Claims

1. In combination:

A parallel multi-channel data handling system, including one or more data channels, and an apparatus for correcting several channels in error simultaneously, said apparatus comprising;

means for encoding and writing into a first channel, vertical parity checks and for encoding and writing into a second channel diagonal parity checks taken over the channels, including the data channels, in a predetermined, positively or negatively sloped direction;

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

means for detecting a mismatch among the vertical and diagonal syndromes intersecting the same error; and

means responsive to the detected mismatches for generating a pointer to an unknown error channel as a function of the displacement along the channel between the first mismatch and the next subsequent mismatch among the vertical and diagonal syndromes.

2. In a parallel multi-channel data handling system according to claim 1, the means for generating said pointer includes:

a counter initialized to the lowest numbered channel in a set of consecutively numbered channels;

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 a mismatch between the far diagonal and vertical syndrome causes the counter to increment while a mismatch between the near diagonal and vertical syndromes causes the counter to decrement, said change of counter value continuing until the next mismatch between a diagonal and intersecting vertical syndrome determines when the counter is stopped.

3. An apparatus according to claim 1, wherein said apparatus further comprises means responsive to the generated pointer to the channel 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 original known channel data.

4. An apparatus according to claim 1, wherein the means for encoding and writing into the second channel parity checks are limited to parity checks taken over the channel in a predetermined positively sloped direction.

5. In an apparatus for encoding and writing of data into a plurality of parallel channels, the combination comprising:

means for encoding and writing into a first channel vertical parity checks; and

means for encoding diagonal parity checks, taken over all the channels in a predetermined, positively or negatively sloped direction, and writing said encoded diagonal parity checks in a format, consisting either entirely of bits written into a second channel or check bytes regularly dispersed among the data bytes in the cross channel direction.

6. In an apparatus for decoding data written into a plurality of channels, means for ascertaining channels in error externally and generating pointer signals thereto, said channel plurality being partitioned into one or more data channels, a first channel containing vertical parity checks of the data channels, and a second channel containing diagonal parity checks taken over all the channels in a predetermined positively or negatively sloped direction, wherein the improvement comprises the combination of:

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 and to a mismatch among the vertical and diagonal syndromes intersecting the same error in the known channel for generating an internal pointer to an unknown error channel as a function of the displacement between the first and subsequent vertical and diagonal syndrome mismatch.

7. In an apparatus according to claim 6, the combination further includes means responsive to the external and internally generated pointers designating no more than two 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 original known channel data.

8. In combination, a parallel multi-channel data handling system, including one or more data channels, and an apparatus for correcting plural channels in error simultaneously, the apparatus comprising:

means for encoding and writing into a first channel vertical parity checks and for encoding and writing into a second channel diagonal parity checks taken over the channels, including the data channels, in a predetermined, positively or negatively sloped direction;

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;

means responsive to the detected mismatches for generating pointers designating at least one known channel in error;

means responsive to pointers designating at least one known channel in error and to the detected mismatches for generating correction signals from at least two syndromes intersecting the same error in the known channel, said mens including means for continuously modifying the value of syndrome diagonally intersecting each error in the known channel as it is detected; and

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

9. An apparatus according to claim 8 wherein the means for correcting errors includes means for selecting as between two diagonal syndromes, the one closest to the known channel in error.

10. An apparatus according to claim 8, wherein said parity value modification consists of inversion of the instant modulo 2 value.

11. An apparatus according to claim 8, wherein the means for continuously modifying the value of syndromes diagonally intersecting each error in the known channel as it is detected comprises means for executing the modulo 2 addition of the error value to the respective values of the diagonal intersecting syndromes.