US 7,219,289 B2 · Multiply redundant raid system and XOR-efficient method and apparatus for implementing the same

Abstract

An improved and extended Reed-Solomon-like method for providing a redundancy of m≧3 is disclosed. A general expression of the codes is described, as well as a systematic criterion for proving correctness and finding decoding algorithms for values of m≧3. Examples of codes are given for m=3, 4, 5, based on primitive elements of a finite field of dimension N where N is 8, 16 or 32. A Horner's method and accumulator apparatus are described for XOR-efficient evaluation of polynomials with variable vector coefficients and constant sparse square matrix abscissa. A power balancing technique is described to further improve the XOR efficiency of the algorithms. XOR-efficient decoding methods are also described. A tower coordinate technique to efficiently carry out finite field multiplication or inversion for large dimension N forms a basis for one decoding method. Another decoding method uses a stored one-dimensional table of powers of α and Schur expressions to efficiently calculate the inverse of the square submatrices of the encoding matrix.

Claims39

Dependent claims

A method for encoding input data including d data symbols (b0, b1, . . . bd−1) to generate coded data having d+m symbols, each symbol consisting of N bits, where d is an integer greater than 1, m is an integer greater than 3, N is an integer greater than 1, and s is an integer, the method comprising:

(a) receiving the d data symbols;
(b) calculating m parity symbols from the d data symbols, wherein each k-th parity symbol for integer k between 0 and m−1 is calculated by evaluating a parity polynomial
p
b
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
b
i
⁢
x
i
at
x
=
α
s
+
k
,
where α is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a mapping which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−1 integers {i2, . . . iM} between 1 and d−1, and every ordered subset of M−1 integers {j2, . . . jM} between 1 and m−1, the determinant of the matrix
(
1
1
⋯
1
1
α
i
2
⁢
j
2
⋯
α
i
M
⁢
j
2
⋮
⋮
⋯
⋮
⋮
⋮
…
⋮
1
α
i
2
⁢
j
M
⋯
α
i
M
⁢
j
M
)
is nonzero in the field FN;
and
(c) storing or transmitting the d data symbols and the m parity symbols as the d+m symbols of the coded data.

73 more elements

A data encoder for encoding input data having d data blocks (b0, b1, . . . bd−1) to generate coded data having d+m blocks, each data block consisting of N*K bits, where d is an integer greater than 1, m is an integer greater than 3, N is an integer greater than 1, K is an integer greater than 0, the bits of every block being indexed by indices i,j, where 0≦i<N and 0≦j<K, and where s is an integer, the encoder comprising:

means for receiving the d data blocks;
means for calculating m parity blocks from the d data blocks, wherein each k-th parity block for integer k between 0 and m−1 is calculated by evaluating a parity polynomial
p
b
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
b
i
⁢
x
i
at
x
=
α
s
+
k
,
where α is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a mapping which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−1 integers {i2, . . . im} between 1 and d−1, and every ordered subset of M−1 integers {j2, . . . jM} between 1 and m−1, the determinant of the matrix
(
1
1
⋯
1
1
α
i
2
⁢
j
2
⋯
α
i
M
⁢
j
2
⋮
⋮
⋯
⋮
⋮
⋮
…
⋮
1
α
i
2
⁢
j
M
⋯
α
i
M
⁢
j
M
)
is nonzero in the field FN,
wherein the means for calculating m parity blocks comprises, for each parity block, K identical copies of means for calculating N bits of the block having the same index j;
and
means for storing or transmitting the d data symbols and the m parity symbols as the d+m symbols of the coded data.

74 more elements

A data encoder for encoding input data including d data blocks (b0, b1, . . . bd−1) to generate coded data including m parity blocks, each data block and parity block consisting of N*K bits, where d is an integer greater than 1, m is an integer greater than 1, N is an integer greater than 1, K is an integer greater than 0, and s is an integer, the encoder comprising:

m accumulators each for calculating one of the m parity blocks, each accumulator comprising:
a trunk input including N*K bits logically indexed by a width-wise coordinate i and a depth-wise coordinate j, i being an integer variable between 0 and N−1 and j being an integer between 0 and K−1, the bits having the same j logically forming a j-th trunk input vector;
a side input including N*K bits indexed by the width-wise coordinate i and the depth-wise coordinate j, the bits having the same j logically forming a j-th side input vector;
a trunk output including N*K bits indexed by the width-wise coordinate i and the depth-wise coordinate j, the bits having the same j logically forming a j-th trunk output vector;
for each value of j, zero or more shifts and XOR combiners forming a mapping circuit, the mapping circuit connected to the N bits of the j-th trunk input vector as input and generating as output N mapped bits logically forming a j-th mapped vector;
for each value of j, N XOR combiners each for combining one bit of the j-th mapped vector with a corresponding bit of the j-th side input vector to generate a corresponding bit of the j-th trunk output vector,
wherein the mapping circuits are identical for all j within each of the m accumulators,
wherein for an integer k between 0 and m−1, the mapping circuit for the k-th one of the m accumulators generates a mapped vector capable of being expressed as a product of the trunk input vector and x=αs+k, where α is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a mapping which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−1 integers {i2, . . . iM} between 1 and d−1, and every ordered subset of M−1 integers {j2, . . . jM} between 1 and m−1, the determinant of the matrix
(
1
1
⋯
1
1
α
i
2
⁢
j
2
⋯
α
i
M
⁢
j
2
⋮
⋮
⋯
⋮
⋮
⋮
…
⋮
1
α
i
2
⁢
j
M
⋯
α
i
M
⁢
j
M
)
is nonzero in the field FN.

48 more elements

A method for decoding data, wherein the data comprises d data symbols and m parity symbols and wherein up to a total of m data and parity symbols are unavailable, each symbol consisting of N bits, where d is an integer greater than 1, m is an integer greater than 1, N is an integer greater than 1, and s is an integer, wherein each k-th of the m parity symbols for integer k between 0 and m−1 has been calculated from the d data symbols by evaluating a parity polynomial

p
b
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
b
i
⁢
x
i
at
x
=
α
s
+
k
,
where α is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a first and a second mapping each of which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, the first and second mapping being either the same or different mappings, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−1 integers {i2, . . . iM} between 1 and d−1, and every ordered subset of M−1 integers {j2, . . . jM} between 1 and m−1, the determinant of the matrix
(
1
1
⋯
1
1
α
i
2
⁢
j
2
⋯
α
i
M
⁢
j
2
⋮
⋮
⋯
⋮
⋮
⋮
…
⋮
1
α
i
2
⁢
j
M
⋯
α
i
M
⁢
j
M
)
is nonzero in the field FN,
the decoding method comprising:
(a) storing a first one-dimensional table of powers of α in a form under the first mapping and a second one-dimensional table of powers of α in a form under the second mapping, each table being indexed by the power to which α is raised, where the index ranges from an integer value by steps of 1 to a greater integer value,
(b) generating a square decoding matrix by inverting a square submatrix of a parity matrix P:
P
=
(
1
α
s
α
2
⁢
s
⋯
α
(
d
-
1
)
⁢
s
1
α
s
+
1
α
2
⁢
(
s
+
1
)
⋯
α
(
d
-
1
)
⁢
(
s
+
1
)
⋮
⋮
⋮
⋮
⁢
⁢
⋮
⁢
⋮
⋮
⋮
⋮
⋮
⋮
1
α
s
+
m
-
1
α
2
⁢
(
s
+
m
-
1
)
⋯
α
(
d
-
1
)
⁢
(
s
+
m
-
1
)
)
and the square submatrix is defined based on identities of the unavailable data symbols and available parity symbols, the inverting step including:
if the square submatrix is 1×1,
(b1) obtaining a power of a from the first one-dimensional table by table lookup using an index determined by the square submatrix entry;
and
if the square submatrix is 2×2 or larger,
(b2) calculating a plurality of indices based on an expression of inverse matrix entries as minors of the square submatrix of the parity matrix;
and
(b3) obtaining powers of a from the second one-dimensional table by table lookup using the calculated indices;
(c) calculating syndrome data using the parity matrix and the available data and parity symbols;
and
(d) multiplying the syndrome data by the square decoding matrix to obtain data symbols corresponding to the unavailable data symbols.

175 more elements

A data decoder for decoding data, wherein the data comprises d data symbols and m parity symbols and wherein up to a total of m data and parity symbols are unavailable, each symbol consisting of N bits, where d is an integer greater than 1, m is an integer greater than 1, N is an integer greater than 1, and s is an integer, wherein each k-th of the m parity symbols for integer k between 0 and m−1 has been calculated from the d data symbols by evaluating a parity polynomial

p
b
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
b
i
⁢
x
i
at
x
=
α
s
+
k
,
where α is a primitive element of a finite field FN of dimension N over the bit field {0,1}, all N-bit symbols being mapped onto the field FN by a first and a second mapping each of which is a vector space isomorphism over {0,1} using bitwise AND and XOR operations, the first and second mapping being either the same or different mappings, such that for every integer M between 1 and min(m,d) inclusive, and every ordered subset of M−1 integers {i2, . . . iM} between 1 and d−1, and every ordered subset of M−1 integers {j2, . . . jM} between 1 and m−1, the determinant of the matrix
(
1
1
⋯
1
1
α
i
2
⁢
j
2
⋯
α
i
M
⁢
j
2
⋮
⋮
⋯
⋮
⋮
⋮
…
⋮
1
α
i
2
⁢
j
M
⋯
α
i
M
⁢
j
M
)
is nonzero in the field FN,
the decoder comprising:
a memory storing a first one-dimensional table of powers of α in a form under the first mapping and a second one-dimensional table of powers of α in a form under the second mapping, each table being indexed by the power to which α is raised, where the index ranges from an integer value by steps of 1 to a greater integer value,
means for generating a square decoding matrix by inverting a square submatrix of a parity matrix P:
P
=
(
1
α
s
α
2
⁢
s
⋯
α
(
d
-
1
)
⁢
s
1
α
s
+
1
α
2
⁢
(
s
+
1
)
⋯
α
(
d
-
1
)
⁢
(
s
+
1
)
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⁢
⁢
⋮
⋮
1
α
s
+
m
-
1
α
2
⁢
(
s
+
m
-
1
)
⋯
α
(
d
-
1
)
⁢
(
s
+
m
-
1
)
)
and the square submatrix is defined based on identities of the unavailable data symbols and available parity symbols, the means for generating:
for a 1×1 square submatrix,
means for obtaining a power of α from the first one-dimensional table by table lookup using an index determined by the square submatrix entry;
and
for a 2×2 or larger square submatrix,
means for calculating a plurality of indices based on an expression of inverse matrix entries as minors of the square submatrix of the parity matrix;
and
means for obtaining powers of α from the second one-dimensional table by table lookup using the calculated indices;
means for calculating syndrome data using the parity matrix and the available data and parity symbols;
and
means for multiplying the syndrome data by the square decoding matrix to obtain data symbols corresponding to the unavailable data symbols.

173 more elements

A method of processing input digital signals, wherein the digital signals include one or more input signals each representing an element of a first finite field of dimension 2*N, the method comprising:

(a) for each of the input signals, forming a first and a second intermediate signal representing a first and a second element respectively of a second finite field of dimension N, such that the field element represented by the input signal is the sum of the second element of the second field and the product of the first element of the second field with a constant element A of the first finite field, wherein A satisfies the equation
A2+A+g=0
where g is a constant element of the second finite field such that the equation
X2+X+g=0
does not have a solution X in the second finite field;
(b) performing operations using the intermediate signals formed in step (a), including:
(b1) performing operations using the intermediate signals from step (a) to generate first additional intermediate signals, and
(b2) performing operations using the intermediate signals from step (a) or (b1) to generate further additional intermediate signals,
the operations in steps (b1) and (b2) including a general add which forms the field sum of two intermediate signals, a general multiply which forms the field product of two intermediate signals, or a g-multiply which forms the field product of one intermediate signal with the constant element g;
and
(c) generating an output signal representing an element of the first finite field using intermediate signals formed in step (a) or step (b) such that the field element represented by the output signal is the field product of two field elements represented by two input signals or the field product of an field element represented by an input signal with the constant field element A*g,
wherein if in step (c) the field element represented by the output signal is the field product of two field elements represented by two input signals, then step (b) includes performing zero or more general adds, one or more g-multiplies, and no more than three general multiplies, and
if in step (c) the field element represented by the output signal is the field product of one field element represented by an input signal with the constant field element A*g, then step (b) includes performing zero general multiplies, zero or more general adds, and no more than three g-multiplies.

10 more elements

Dependencies are inferred from the claim text.

Multiply redundant raid system and XOR-efficient method and apparatus for implementing the same

Life of this patent

Multiply redundant raid system and XOR-efficient method and apparatus for implementing the same

Life of this patent

Abstract

Claims39