Array combinatorial decoding with multiple error and erasure detection and location using cyclic equivalence testing

• US 5,644,695 A
• Filed: 07/15/1994
• Issued: 07/01/1997
• Est. Priority Date: 01/03/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vardy, Alexander, Blaum, Mario
• Primary Examiner(s): CHUNG, PHUNG M
• Application Number:
  US08/276,074
• Time in Patent Office: 1,082 Days
• Field of Search: 395/575, 395/182.04, 395/185.01, 371/10.1, 371/68.3, 371/54, 371/50.1, 371/49, 371/48, 371/37.4, 371/37.7, 371/38, 371/39
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/1162 Array based LDPC codes, e.g. array codes
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/2927 Decoding strategies

Abstract

An apparatus and method for detecting and locating up to two symbols in error or erasures in an n×m A(n,m,t) parity coded bit array previously recorded on a multi-track storage device where n is a prime number, m≦n, wherein at least one non-zero syndrome of m rotated and column summed syndromes is derived. The method includes an iterative process using an incremented tracking variable and testing of the cyclic equivalence of three derived vectors to isolate the number and location of the array column or columns containing the error or errors. Each derived vector is the modulo 2 sum of a selected syndrome and a selected rotated vector. Cyclic equivalence of between a derived vector and a selected rotated one of the other derived vectors for any given iteration establishes the error or errors and their column location or locations. An extension is shown for detecting and locating up to three errors or erasures. Correction of the errors involves parity recoding the array following parity traverses of different slopes.

Claims

1. In a computer system comprising a central processing unit and a storage medium, a method for detecting and locating up to two symbols in error or erasures in an n×

mA (n,m,4) parity coded bit array where n is a prime number, m≦

n comprising the steps of;

(a) rotating, using said computer system, m column vectors in said n×

m A(n,m,4) parity coded bit array by predetermined amounts;

(b) forming, using said computer system, m modulo 2 summed syndromes from said rotated m column vectors, and in a presence of any error, deriving at least one non-zero syndrome;

(c) computing, using said computer system, first, second, and third test vectors, each test vector being a modulo 2 sum of a unique selected syndrome and a unique selected rotated syndrome; and

(d) initializing, using said computer system, a tracking variable L and incrementing L for each repetition of step (d) and;

(1) either providing signal indication of exactly one error at a column location defined by L in a presence of first and second null test vectors,

(2) providing signal indication of exactly two errors and said two errors'"'"' column locations in a presence of the second test vector, said second test vector being equivalent of the first test vector rotated by L positions and the third test vector being equivalent of the second test vector rotated by K positions, L<

K,

(3) repeating steps (d) in an absence of cyclic equivalence among the test vectors, or

(4) providing signal indication of more than two errors either in a presence of at least two zero test vectors or when L=m.

2. In a computer system comprising a central processing unit and a storage medium, a method for locating up to two symbols in error or two columns in error in a n×

m parity coded bit data array, m≦

n, n being prime, the method comprising the steps of;

(a) forming, using said computer system, a plurality of syndromes from predetermined cyclic rotations and modulo 2 addition across the data array columns for each syndrome;

(b) in an event of at least one non-zero syndrome, initializing, using said computer system, at least one tracking variable L and iteratively;

(1) incrementing, using said computer system, said tracking variable L by a predetermined amount,

(2) forming, using said computer system, first, second, and third test vectors each as a modulo 2 sum of a different selected syndrome and a selected rotated syndrome; and

(3) either;

providing signal indication of exactly one error at column location L≦

(m-1) when the first and second test vectors are zero,

providing signal indication of exactly two errors at column locations L and L≦

K≦

(m-1) where the second and third test vectors are respective Kth rotations of the first and second test vectors,

repeating step (b) where (when) the first and second test vectors are not L-th rotations of each other or when the second and third test vectors are not the K-th rotations of each other, or

providing signal indication of more than two errors if the incremented value L=m.

3. The method according to claim 2, wherein said method further comprises the step of:

(c) responsive to an indication of exactly one or two errors, encoding, using said computer system, said n×

m parity coded bit data array by

(1) traversing m parity lines projected onto said n×

m parity coded bit data array for each one of a set of slopes consisting of slope magnitudes 0, 1, 2, and 3, and extending cyclically over said n×

m parity coded bit data array; and

(2) inserting Boolean values into the n×

m parity coded bit data array during each traverse such that logically combined (XORed) values of the data encountered over each of the traverses sum to zero modulo 2 (even parity), said n×

m parity coded bit data array being fully encoded in multiple parity line traverses.

4. The method according to claim 2, wherein step (a) includes forming, using said computer system, four syndromes and further wherein each i-th column of each syndrome j≦

m being rotated (i-1)*j bit positions relative to a first array column in a predetermined wrap-around direction, each syndrome j≦

m being the modulo 2 bitwise sum across the rotated array columns.

5. A computer system having at least one multi-tracked storage device, means for recording an n×

m coded bit array across counterpart tracks of said storage device, buffer means, and insane for copying selected ones of said recorded n×

m coded bit arrays from said device into said buffer means where m≦

n, n being prime, said computer system further comprises;

means for determining each of j≦

m syndromes s_j from the n×

m coded bit array in said buffer means in which ##EQU10## where ρ

_j*i is a column vector rotational operator, a_i '"'"' are columns of said n×

m coded bit array; and

means responsive to at least one non-zero syndrome s_j for initializing at least one tracking variable L and iteratively;

(1) incrementing said tracking variable L by a predetermined amount,

(2) forming first y_i '"'"', second y₂ '"'"', and third y₃ '"'"' test vectors from the syndromes s_j such that;

y₁ '"'"'=s₁ '"'"'+ρ

_L (s₀ '"'"'), y₂ '"'"'=s₂ '"'"'+ρ

_L (s₁ '"'"'),

y₃ '"'"'=s₃ '"'"'+ρ

_L (s₂ '"'"'), and

(3) either providing signal indication of exactly one error at column location L≦

(m-1) when the y₁ '"'"'=y₂ '"'"'=0, providing signal indication of exactly two errors at column locations L and L≦

K≦

(m-1) when y₂ '"'"'=ρ

_k (y₁ '"'"') and y₃ '"'"'=ρ

_k (y₂ '"'"'), repeating iteratively (1) through (3) when y₂ '"'"'≠

ρ

_k (y₁ '"'"'), or providing signal indication of more than two errors if the incremented value L=m.

6. In a computer system comprising a central processing unit and a storage medium, a method for detecting and correcting errors and erasures in an n×

m A(n,m,4) parity coded data array, comprising the steps of;

(a) deriving, using said computer system, a plurality of syndromes from the parity coded data array, at least one non-zero syndrome being indicative of either error or erasure;

(b) forming, using said computer system, first, second, and third test vectors from the syndromes, each test vector being a sum of a unique syndrome and a unique selected rotated syndrome;

(c) initializing, using said computer system, a tracking variable L and incrementing L for each repetition of step (c) and;

(1) providing signal indicating of exactly a single error at column location L where all the test vectors are null;

(2) providing signal indication of exactly two errors when said two errors'"'"' column locations in the presence of the second test vector being equivalent of the first test vector rotated by L positions and the third test vector being equivalent of the second test vector rotated by K positions, L<

K,

(3) repeating step (c) in an absence of cyclic equivalence among the test vectors, or

(4) providing signal indication of more than two errors either in a presence of at least two zero test vectors or when L=m; and

(d) correcting, using said computer system, any array bits in error by parity encoding said array according to the A(n,m,4) code and the provided signal indications.

7. In a computer system comprising a central processing unit and a storage medium, a method for detecting and locating up to three symbols or three columns in error in an n×

m A(n,m,6) parity encoded data bit array, n being a prime number and m≦

n, comprising the steps of;

(a) deriving, using said computer system, six syndromes from the n×

m A(n,m,6) parity encoded data bit array, a presence of at least one non-zero syndrome being indicative of either error or erasure;

(b) forming, using said computer system, first through fifth test vectors from the syndromes, each first through fifth test vector being a sum of a unique syndrome and a unique rotated syndrome, and forming a sixth through ninth test vectors, each sixth through ninth test vectors being the sum of a unique one of the first through fifth test vectors and a unique rotated one of the first through fifth test vectors;

(c) initializing, using said computer system, a first L and a second tracking variable J and incrementing L and J for each repetition of step (c) and;

(1) providing signal indicating of exactly a single error at a column location L where the first through fifth test vectors are null;

(2) providing signal indication of exactly two errors and said two errors'"'"' column locations L and J where the sixth and seventh test vectors are null;

(3) providing signal indicating of exactly three errors in the presence of the eighth test vector being equivalent of the seventh test vector rotated by K positions and the ninth test vector being equivalent of the eighth test vector rotated by K positions, L<

J<

K;

(4) repeating step (c) in an absence of cyclic equivalence among the sixth through ninth test vectors, or

(5) providing signal indication of more than three errors either when at least three of the sixth through ninth test vectors are null or when L=m.

8. The method according to claim 7, wherein the method further includes the step of:

(d) correcting, using said computer system, any array bits in error by parity encoding said parity encoded data bit array according to the A(n,m,6) code and the provided signal indications.

9. In a computer system having at least one multi-tracked storage device, means for encoding and recording m×

n data bit arrays on counterpart tracks of said storage device, said m×

n data bit arrays being parity encoded with a A(n,m,4) code, m≦

n, n being a prime number, means for accessing, means for copying into a buffer means, and means for decoding an array recorded on said multi-tracked storage device, said decoding means comprising;

means for deriving a plurality of syndromes from the array, at least one non-zero syndrome being indicative of either error or erasure;

means for forming first, second, and third test vectors from the plurality of syndromes, each test vector being a sum of a unique syndrome and a unique selected rotated syndrome;

means for iteratively evaluating the either error or erasure condition of the array by initializing a tracking variable L and incrementing L for each iteration and further including means for either causing another iteration in an absence of cyclic equivalence among the test vectors or providing mutually exclusive signal indication of;

(1) exactly a single error at a column location L where all the test vectors are null,

(2) two errors and said two errors'"'"' column locations in a presence of the second test vector being equivalent of the first test vector rotated by L positions and the third test vector being equivalent of the second test vector rotated by K positions, L<

K,

(3) providing signal indication of more than two errors either in a presence of at least two zero test vectors or where L=m; and

means for correcting any array bits in error by parity encoding said array according to the A(n,m,4) code and the provided signal indications.