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

• US 7,219,289 B2
• Filed: 03/15/2005
• Issued: 05/15/2007
• Est. Priority Date: 03/15/2005
• Status: Expired due to Fees

• Current Assignee: Tandberg Data Corporation
• Original Assignee: Tandberg Data Corporation
• Inventors: Dickson, Lawrence John
• Primary Examiner(s): Baker; Stephen M.
• Application Number:
  US11/080,093
• Publication Number:
  US 20060218470A1
• Time in Patent Office: 791 Days
• Field of Search: 714/752, 714/770, 714/759
• US Class Current: 714/752
• 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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

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.

Claims

1. A method for encoding input data including d data symbols (b₀, b₁, . . . b_d−

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<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{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 {i₂, . . . i_M} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

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.

2. The method of claim 1, where N=8, m=4 and d<

=33, and α

satisfies the polynomial equation in FN

α

⁸+α

⁷+α

³+α

¹+1=0.

3. The method of claim 1, where N=16, m=4 and d<

=255, and α

satisfies the polynomial equation in FN

α

¹⁶+α

¹⁰+α

⁷+α

³+1=0.

4. The method of claim 1, where N=32, m=4 and d<

=255, and α

satisfies the polynomial equation in FN

α

³²+α

²¹+α

²⁰+α

¹⁹+1=0.

5. The method of claim 1, where N=8, m=4 and d<

=33, and α

satisfies the polynomial equation in FN

α

⁸+α

⁴+α

³+α

¹+1=0.

6. The method of claim 1, where N=16, m=5 and d<

=102, and α

satisfies the polynomial equation in FN

α

¹⁶+α

¹⁰+α

⁷+α

³+1=0.

7. The method of claim 1, where N=16, m=5 and d<

=120, and α

satisfies the polynomial equation in FN

α

¹⁶+α

¹⁴+α

¹⁰+α

⁸+α

⁷+α

³+1=0.

8. The method of claim 1, where N=32, m=5 and d<

=255, and α

satisfies the polynomial equation in FN

α

³²+α

²¹+α

²⁰+α

¹⁹+1=0.

9. The method of claim 1, where N=32, m=5 and d<

=255, and α

satisfies the polynomial equation in FN

α

³²+α

³⁰+α

²³+α

¹⁶+1=0.

10. The method of claim 1, wherein s=−

(m−

1)/2 for odd m and s=−

(m−

2)/2 for even m.

11. The method of claim 1, wherein the step of calculating m parity symbols comprises, for each k-th parity symbol:

(a) calculating acc=(b<sub>d−

1</sub>*x)+b<sub>d−

2</sub>;

(b) calculating acc=(acc*x)+b<sub>d−

3</sub>;

(c) repeating step (b) using successive values b<sub>d−

4</sub>, b<sub>d−

5</sub>, . . . b₀ in place of b<sub>d−

3</sub> in the calculation to evaluate the parity polynomial

p_b(x)=b₀+x(b₁+x(b₂+. . . x(b<sub>d−

1</sub>) . . . )).

12. The method of claim 1, wherein step (c) comprises:

storing a different one of the d data blocks in each of d data storage devices; and

storing a different one of the m parity blocks in each of m parity storage devices.

13. The method of claim 1, wherein N is a power of 2.

14. The method of claim 13, where α

satisfies an irreducible polynomial equation in FN

α

^N+α

^h+α

^g+α

^f+1=0

where f, g and h are integers satisfying 0<

f<

g<

h<

N.

15. The method of claim 14, where N=8, 16, or 32 and m=4 or 5.

16. A data encoder for encoding input data having d data blocks (b₀, b₁, . . . b_d−

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<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{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 {i₂, . . . i_m} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

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.

17. The data encoder of claim 16, wherein N*K>

32.

18. The data encoder of claim 16, wherein the means for calculating m parity blocks includes, for each k-th parity symbol, a means for calculating a variable acc

acc=(acc*x)+b_i.

19. A data storage system comprising the data encoder of claim 16, wherein the means for storing or transmitting comprises:

d data storage devices each for storing a different one of the d data blocks; and

m parity storage devices each for storing a different one of the m parity blocks.

20. A data encoder for encoding input data including d data blocks (b₀, b₁, . . . b_d−

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 {i₂, . . . i_M} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

is nonzero in the field FN.

21. The data encoder of claim 20, wherein m>

3.

22. The data encoder of claim 20, wherein K*N>

32.

23. The data encoder of claim 20, further comprising:

an external input including N*K bits indexed by the width-wise coordinate i and the depth-wise coordinate j; and

an external output including N*K bits indexed by the width-wise coordinate i and the depth-wise coordinate j,

wherein the trunk input is selectably connected to either the trunk output or the external input, and the trunk output is selectably connected to either the trunk input or the external output.

24. The data encoder of claim 23, further comprising a controller connected to each of the m accumulators, the controller being operable on each accumulator to:

(a) coupling data block b<sub>d−

1</sub> to the trunk input and coupling data block b<sub>d−

2</sub> to the side input of the accumulator, whereby a trunk output block is generated by the accumulator based on the trunk input and side input;

(b) coupling the trunk output block thus generated to the trunk input of the accumulator and coupling the next data block b<sub>d−

3</sub> to the side input of the accumulator, whereby new trunk output block is generated by the accumulator based on the trunk input and side input;

(c) repeating step (b), each time using the next data block until data block b₀ is coupled to the side input; and

(d) coupling the trunk output generated in step (c) to the accumulator output.

25. The data encoder of claim 24, wherein the controller is operable to perform each step simultaneously for all m accumulators.

26. A method for encoding input data having d data symbols (b₀, b₁, . . . b_d−

1) to generate coded data having d+3 symbols, each symbol consisting of N bits, where d is an integer greater than 1, and N is an integer greater than 1, the method comprising;

(a) receiving the d data symbols;

(b) calculating 3 parity symbols from the d data symbols, wherein each k-th parity symbol for integer k between 0 and 2 is calculated by evaluating a parity polynomial

$p_b<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{k-1},$

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, a being nonzero and the order of a in the multiplicative group of FN being greater than or equal to d,

(c) storing or transmitting the d data symbols and the 3 parity symbols as the d+3 symbols of the coded data.

27. A data encoder for encoding input data having d data blocks (b₀, b₁, . . . b_d−

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 1, N is an integer greater than 1, K is an integer greater than 0, N*K>

32, 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<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{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 {i₂, . . . i_M} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

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.

28. 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<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{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 {i₂, . . . i_M} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

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=\left(\begin{array}{ccccc}1& {\mathrm{\alpha <br><br>}}^s& {\mathrm{\alpha <br><br>}}^{2<br><br>s}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>s}\\ 1& {\mathrm{\alpha <br><br>}}^{s+1}& {\mathrm{\alpha <br><br>}}^{2<br><br>\left(s+1\right)}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>\left(s+1\right)}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}<br><br><br><br>\mathrm{⋮<br><br>}<br><br>& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{s+m-1}& {\mathrm{\alpha <br><br>}}^{2<br><br>\left(s+m-1\right)}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>\left(s+m-1\right)}\end{array}\right)$

 

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.

29. The method of claim 28, where N is a power of 2.

30. The method of claim 28, wherein the first and second mappings are different mappings,

wherein in the first one-dimensional tables the powers of α

are stored in a bit matrix form under the first mapping, and

wherein in the second one-dimensional tables the powers of α

are stored in a bit vector form under the second mapping;

wherein step (b) further comprises;

if the square submatrix is 2×

2 or larger,

(b4) converting each entry of the square decoding matrix into a bit matrix form under the first mapping.

31. The decoding method of claim 28, wherein the first and second mappings are different mappings,

wherein multiplication and inversion under the second mapping are performed as combinations of addition, multiplication, inversion, squaring, and constant multiplication on one or more subfields of FN, and

wherein the decoding method further comprises storing tables of products and inverses in the one or more subfields of FN.

32. The method of claim 28, wherein the first one-dimensional table of powers of α

is stored in a bit matrix form under the first mapping.

33. The method of claim 28, wherein the first and second mappings are the same mapping.

34. The decoding method of claim 28, wherein step (d) includes reordering the bits of the decoding matrix into a number of bit fields treated as unsigned integers, each integer corresponding to an XOR accumulate of a subset of a set of syndrome data fields onto a subset of the decoded data;

and performing matrix multiply by looping over all of the integers.

35. 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<br><br>\left(x\right)=\underset{i=0}{\overset{d-1}{\sum <br><br>}}<br><br>b_i<br><br>x^i$ $\mathrm{at}$ $x={\mathrm{\alpha <br><br>}}^{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 {i₂, . . . i_M} between 1 and d−

1, and every ordered subset of M−

1 integers {j₂, . . . j_M} between 1 and m−

1, the determinant of the matrix

$\left(\begin{array}{cccc}1& 1& \mathrm{\cdots <br><br>}& 1\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_2}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_2}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\cdots <br><br>}& \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{\dots <br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{i_2<br><br>j_M}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{i_M<br><br>j_M}\end{array}\right)\hspace{1em}<br><br>$

 

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=\left(\begin{array}{ccccc}1& {\mathrm{\alpha <br><br>}}^s& {\mathrm{\alpha <br><br>}}^{2<br><br>s}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>s}\\ 1& {\mathrm{\alpha <br><br>}}^{s+1}& {\mathrm{\alpha <br><br>}}^{2<br><br>\left(s+1\right)}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>\left(s+1\right)}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& & \mathrm{⋮<br><br>}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}<br><br><br><br>\mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}\\ 1& {\mathrm{\alpha <br><br>}}^{s+m-1}& {\mathrm{\alpha <br><br>}}^{2<br><br>\left(s+m-1\right)}& \mathrm{\cdots <br><br>}& {\mathrm{\alpha <br><br>}}^{\left(d-1\right)<br><br>\left(s+m-1\right)}\end{array}\right)$

 

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.

36. The decoder of claim 35, where N is a power of 2.

37. The decoder of claim 35, wherein the first and second mappings are different mappings,

wherein in the first one-dimensional tables the powers of α

are stored in a bit matrix form under the first mapping, and

wherein in the second one-dimensional tables the powers of α

are stored in a bit vector form under the second mapping;

wherein the means for generating a square decoding matrix further comprises;

for the 2×

2 or larger square submatrix, means for converting each entry of the square decoding matrix into a bit matrix form under the first mapping.

38. The data decoder of claim 37, wherein the means for converting includes at least one accumulator, each accumulator comprising:

a trunk input including N*D 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 D−

1, the bits having the same j logically forming a j-th trunk input vector, wherein D is the count of matrix entries handled in a single calculation;

a trunk output including N*D 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;

a side output including N*D bits each connected to the corresponding bits of the trunk output; and

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 the j-th trunk output vector, wherein the j-th trunk output vector is capable of being expressed as a product of the trunk input vector and x=α

^s+k;

wherein in at least one accumulator, each bit of the trunk output is switchably connected to the corresponding bit of the trunk input via a latch, or connected to a corresponding bit of a trunk input of another accumulator.

39. 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

A²+A+g=0

 

where g is a constant element of the second finite field such that the equation

X²+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.