ONE-SUB-SYMBOL LINEAR REPAIR SCHEMES

Abstract

A method for repairing a single erasure in a Reed Solomon code in a system of a plurality of n storage nodes and a controller, wherein a content of each storage node is a codeword and each node stores a vector v. The method includes identifying a failed storage node; transmitting an index of the failed storage node to each surviving storage node; multiplying the content of each node i by a j-th component of a vector that is a permutation of elements of vector v that correspond to the surviving storage nodes; determining a trace map of the result and converting the result from an mr bit representation into a reduced representation of r bits; reconstructing the content of the failed storage node from the reduced representation of each surviving node's content; and outputting the reconstructed content of the failed storage node.

Claims

1. A method for repairing a single erasure in a Reed-Solomon (RS) code over a finite field F.sub.2.sup.mr with an evaluation set V={u.sub.0=0, u.sub.1, . . . , u.sub.n1} that is a subspace of size n=2.sup.d, for d<mr and divisible by m, wherein a normalized repair bandwidth b(n1)/m and a number of information symbols is k<=2.sup.d2.sup.ddim, in a system of a plurality of n storage nodes and a controller, wherein a content c.sub.i of each storage node i is an element of the finite field F.sub.2.sup.mr and each node stores a sector v whose entries are inverses of non-zero elements of the evaluation set V, the method comprising the steps of identifying, by the controller, a failed storage node; transmitting, by the controller, an index j.sub.0 of the failed storage node to each surviving storage node; multiplying, by each surviving storage node i, the content c.sub.i of each said node i by a j-th component of vector w(i) wherein $j=j\left(i,j_0\right)=\{\begin{array}{cc}{j}_0& \mathrm{if}.Math..Math.j_0<i\\ j_0-1& \mathrm{if}.Math..Math.j_0>i\end{array},$ wherein w(i).sub.j(i,j.sub.0.sub.):=v.sub.j for all i {0, . . . , j.sub.01, j.sub.0+1, . . . , n} is a pennotation of elements of vector v that correspond to the surviving storage nodes, wherein j is a unique index in {1, . . . , n1} such that u.sub.j=u.sub.j.sub.0+u.sub.i: determining a trace map of a result out, of said multiplication and converting, by each surviving storage node, the result from an mr bit representation into a reduced representation .sub.i of r bits; reconstructing, by the controller, content of the failed storage node from the reduced representation of each surviving node's content; and outputting the reconstructed content of the failed storage node,

2. The method of claim 1, wherein j is calculated by the controller and transmitted to the surviving storage nodes,

3. The method of claim 1, wherein each surviving storage node calculates j based on an index of each surviving storage node and an index of the failed storage node.

4. The method of claim 1, wherein j is pre-calculated for each storage node.

5. The method of claim 1, wherein multiplying, by each surviving storage node i, the content c.sub.i of each said node i by j-th component of vector w(i) comprises calculating, by each node i, i j.sub.0, wherein j.sub.0 is the identifier of the failed node, out.sub.i:=Tr(w(i).sub.j(i,j.sub.0.sub.).Math.c.sub.i)=.sub.=0.sup.m1(w(i).sub.j(i,j.sub.0.sub.).Math.c.sub.i).sup.2.sup.r.

6. The method of claim 5, wherein converting the result from an in mr bit representation into a reduced representation of r bits comprises, when elements of field F.sub.2.sub.mr are represented as length-m vectors in vector space (F.sub.2.sub.r).sup.m according to a basis 1, , . . . .sup.m1 of F.sub.2.sub.mr over F.sub.2.sub.r, and transmitting by each node node i, i j.sub.0, the first coordinate of out.sub.i to the controller.

7. The method of claim 5, wherein converting the result from an in mr bit representation into a reduced representation of r bits comprises, when elements of field F.sub.2.sub.mr are represented as length-mr vectors of bits in vector space F.sub.2.sup.mr according to a basis 1, , . . . , .sup.mr1 of F.sub.2.sub.mr over F.sub.2, wherein is a primitive element of field F.sub.2.sub.mr, transmitting, by each node i, i j.sub.0, a product M.Math.out.sub.i to the controller, wherein matrix M F.sub.2.sup.rmr.

8. The method of claim 7, wherein matrix M F.sub.2.sup.rmr is r rows of a matrix T F.sub.2.sup.mrmr with indices supporting rr identity matrix in TM.sub.1, wherein M.sub.1 F.sub.2.sup.mrr is a matrix whose j-th column, j=0, . . . , m1 is a length-mr binary representation of .sup.j according to a basis {1, , . . . , .sup.mr1} of field E over field F.sub.2, E:=F.sub.2.sub.mr, and is a primitive element of field F.sub.2.sub.r=F.

9. The method of claim 1, wherein reconstructing content of the failed storage mode from the reduced representation of each surviving node's content comprises: calculating t.sup.T=(t.sub.1, . . . , t.sub.m).sup.T:=Az.sup.T (F).sup.m using a matrix A (F) .sup.m(n1), wherein F:=F.sub.2[X](p.sub.1(X)), wherein p.sub.1(X) is a minimal polynomial of , wherein vector z:=(z.sub.1, . . . , z.sub.n1) (F).sup.n1 wherein z.sub.a:=.sub.1 for all =1, . . . , n1 and for i j.sub.0 for which j=a, wherein n is a total number of storage nodes and .sub.i is the reduced representation of surviving: node i's content; wherein matrix A is a matrix obtained by replacing each entry .sub.ij of A by M.sub.ij when .sub.ij is regarded as a column vector in F.sub.2.sup.mr according a basis {1, , . . . , .sup.mr1} of F.sub.2.sub.mr over F.sub.2, wherein matrix A F.sup.m(n1) is a matrix with rows c.sub.1, . . . , c.sub.m that are m linearly independent vectors F.sup.n1 that complete a basis of C to be a basis of C, wherein C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix H, and C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix H, $\mathrm{wherein}.Math..Math.H^{}{E}^{k\left(n-1\right)}:=\left(\begin{array}{c}v\\ H^{}\end{array}\right),.Math.H^{}{E}^{\left(k-1\right)\left(n-1\right)}:=G^{}.Math.\left(\begin{array}{ccc}{v}_1& & \\ & & \\ & & v_{n-1}\end{array}\right),.Math.G^{}{E}^{\left(k-1\right)\left(n-1\right)}:=\left(\begin{array}{ccc}{u}_1& \mathrm{.Math.}& u_{n-1}\\ u_1^2& \mathrm{.Math.}& u_{n-1}^2\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ u_1^{k-1}& \mathrm{.Math.}& u_{n-1}^{k-1}\end{array}\right),$ (v.sub.1, . . . , v.sub.n1) are elements of vector v, and (u.sub.1, . . . , u.sub.n1) are non-zero elements of evaluation set V, and wherein matrix M F.sub.2.sup.rmr is r rows of a matrix T F.sub.2.sup.mrmr with indices supporting an rr identity matrix in wherein TM.sub.1, wherein M.sub.1 F.sub.2.sup.mrr is a matrix whose j-th column, j=0, . . . , m1, is the length-mr binary representation of .sup.j according to the basis {1, , . . . , .sup.mr1} over of E over F.sub.2, wherein is a primitive element of field F.sub.2.sub.r=F and is a primitive element of field F.sub.2.sub.mr; embedding elements of t (F).sup.m in field E:=F.sub.2.sub.mr to obtain a vector w F.sup.m; and restoring the content of the failed storage node by calculating y.sub.i=.sub.=1.sup.m w.sub.x.sub., wherein {x.sub.1, . . . , x.sub.m} E form a dual basis for E over F with respect to a basis whose elements are entries of vector y=(y.sub.1, . . . , y.sub.m).sup.T:=Av.sup.T E.sup.m.

10. The method of claim 9, wherein embedding elements of t (F).sup.m in E to obtain a vector w F.sup.m comprises calculating w.sub.:=M.sub.1.Math.t.sub. for =1, . . . , m, wherein each coordinate t.sub.a of t represented as a length-r binary column vector according to the basis 1, , . . . , ().sup.r1 of over F.sub.2, and outputting w:=(w.sub.1, . . . , w.sub.m), wherein each entry of w is a vector representation of an element of E, according to the basis {1, , . . . , .sup.m1}.

11. A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for repairing a single erasure in a Reed-Solomon (RS) code over a finite field F.sub.2.sup.mr with an evaluation set V={u.sub.0=0, . . . , u.sub.n1} that is a subspace of size n=2.sup.d, for d<mr and divisible by m, wherein a normalized repair bandwidth b(n1)/m and a number of information symbols is k<=2.sup.d2.sup.ddim, in a system of a plurality of n storage nodes and a controller, wherein a content c.sub.i of each storage node i is an element of the finite field F.sub.2.sup.mr and each node stores a vector v whose entries are inverses of non-zero elements of the evaluation set V, the method comprising the steps of identifying, by the controller, a failed storage node; transmitting, by the controller, an index j.sub.0 of the failed storage node to each surviving storage node; multiplying, by each surviving storage node i, the content c of each said node i by a j-th component of vector w(i) wherein $j=j\left(i,j_0\right)=\{\begin{array}{cc}{j}_0& \mathrm{if}.Math..Math.j_0<i\\ j_0-1& \mathrm{if}.Math..Math.j_0>i\end{array},$ wherein w(i).sub.j(i,j.sub.0.sub.):=v.sub.j for all i {0, . . . , j.sub.01, j.sub.0+1, . . . , n} is a permutation of elements of vector v that correspond to the surviving storage nodes, wherein j is a unique index in {1, . . . , n1} such that u.sub.j=u.sub.j.sub.0+u.sub.i; determining a trace map of a result out.sub.i of said multiplication and converting, by each surviving storage node, the result from an mr bit representation into a reduced representation .sub.i of r bits; reconstructing, by the controller, content of the failed storage node from the reduced representation of each surviving node's content; and outputting the reconstructed content of the failed storage node.

12. The computer readable program storage device of claim 11, wherein j is calculated by the controller and transmitted to the surviving storage nodes.

13. The computer readable program storage device of claim 11, wherein each surviving storage node calculates j based on an index of each surviving storage node and an index of the failed storage node.

14. The computer readable program storage device of claim 11, wherein j is pre-calculated for each storage node.

15. The computer readable program storage device of claim 11. wherein multiplying, by each surviving storage node i, the content c.sub.i of each said node i by a j-th component of vector w(i) comprises calculating, by each, node i, i k.sub.0, wherein j.sub.0 is the identifier of the failed node; out.sub.i:=Tr(w(i).sub.j(i,j.sub.0.sub.).Math.c.sub.i)=.sub.=0.sup.m1(w(i).sub.j(i,j.sub.0.sub.).Math.c.sub.i).sup.2.sup.r.

16. The computer readable program storage device of claim 15, wherein converting the result from an in mr hit representation into a reduced representation of r bits comprises, when elements of field F.sub.2.sub.mr are represented as length-m vectors in vector space (F.sub.2.sub.r).sup.m according to a basis 1, , . . . , .sup.m1 of F.sub.2.sub.mr over F.sub.2.sub.r, and transmitting, by each node node i, i j.sub.0, the first coordinate of out.sub.i to the controller.

17. The computer readable program storage device of claim 15, wherein converting the result from an mr bit representation into a reduced representation of r bits comprises, when elements of field F.sub.2.sub.mr are represented as length-mr vectors of bits in vector space F.sub.2.sup.mr according to a basis 1, , . . . , .sup.mr1 of F.sub.2.sub.mr over F.sub.2, wherein is a primitive element of field F.sub.2mr, transmitting, by each node i, i j.sub.0, a product M.Math.out.sub.i to the controller, wherein matrix M F.sub.2.sup.rmr.

18. The computer readable program storage device of claim 17, wherein matrix M F.sub.2.sup.rmr is r rows of a matrix T F.sub.2.sup.mrmr with indices supporting an rr identity matrix in TM.sub.1, wherein M.sub.1 F.sub.2.sup.mrmr is a matrix whose j-th column, j=0, . . . , m1, is a length-mr binary representation of .sup.j according to a basis {1, , . . . , .sup.mr1} of field E over field F.sub.2, E:=F.sub.2.sub.mr, and is a primitive element of field F.sub.2.sub.r=F.

19. The computer readable program storage device of claim 11, wherein reconstructing content of the failed storage node from the reduced representation of each surviving node's content comprises: calculating t.sup.T=(t.sub.1, . . . , t.sub.m).sup.T:=Az.sup.T (F).sup.m using a matrix A (F).sup.m(n1), wherein F:=F.sub.2[X]/(X)), wherein p.sub.1 is a minimal polynomial of , wherein vector z:=(z.sub.1, . . . , z.sub.n1) (F).sup.n1 wherein z.sub.:=.sub.i for all =1, . . . , n1 and for i j.sub.0 for which j=, wherein n is a total number of storage nodes and .sub.i is the reduced representation of surviving node i's content; wherein matrix A is a matrix obtained by replacing each entry of .sub.ij of A by M.sub.ij when .sub.ij regarded as a column vector in F.sub.2.sup.mr according a basis {1, , . . . , .sup.mr1} of F.sub.2.sub.mr over F.sub.2. wherein matrix A F.sup.m(n1) is a matrix with rows c.sub.1, . . . , c.sub.m that are m linearly independent vectors F.sup.n1 that complete a basis of C to be a basis of C, wherein C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix to H, and C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix H, wherein $H^{}{E}^{k\left(n-1\right)}:=\left(\begin{array}{c}v\\ H^{}\end{array}\right),.Math.H^{}{E}^{\left(k-1\right)\left(n-1\right)}:=G^{}.Math.\left(\begin{array}{ccc}{v}_1& & \\ & & \\ & & v_{n-1}\end{array}\right),.Math.G^{}{E}^{\left(k-1\right)\left(n-1\right)}:=\left(\begin{array}{ccc}{u}_1& \mathrm{.Math.}& u_{n-1}\\ u_1^2& \mathrm{.Math.}& u_{n-1}^2\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ u_1^{k-1}& \mathrm{.Math.}& u_{n-1}^{k-1}\end{array}\right),$ (v.sub.1, . . . , v.sub.n1) are elements of vector v, and (u.sub.1, . . . , u.sub.n1) are non-zero elements of evaluation set V, and wherein matrix M F.sub.2.sup.rmr r is r rows of a matrix T F.sub.2.sup.mrmr with indices supporting rr identity matrix in TM.sub.1, wherein M.sub.1 F.sub.2.sup.mrr is a matrix whose j-th column, j=0, . . . , m1, is the length-mr binary representation of .sup.j according to the basis {1, , . . . , .sup.mr1} of E over F.sub.2, wherein a primitive element of field F.sub.2.sub.r=F and is a primitive element of field F.sub.2.sub.mr; embedding elements of t (F).sup.m field E:=F.sub.2.sub.mr to obtain a vector w F.sup.m; and restoring the content of the failed storage node by calculating y.sub.i=.sub.=1.sup.mw.sub.x.sub., wherein {x.sub.1, . . . , x.sub.m} E form a dual basis for E over F with respect to a basis whose elements are entries of vector y=(y.sub.1, . . . , y.sub.m).sup.T:=Av.sup.T E.sup.m.

20. The computer readable program storage device of claim 19, wherein embedding elements of t (F).sup.m in E to obtain a vector w F.sup.m comprises calculating w.sub.:=M.sub.1.Math.t.sub. for =1, . . . , m, wherein each coordinate t.sub.of t is represented as a length-r binary column vector according to the basis 1, , . . . , ().sup.r1 of F over F.sub.2, and outputting w:=(w.sub.1, . . . , w.sub.m), wherein each entry of w is a vector representation of an element of E, according to the basis {1, , . . . , .sup.mr1}.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] FIGS. 1A-B is a flowchart of an offline part of an algorithm;for repairing corrupted Reed-Solomon codes, according, to embodiments of the disclosure.

[0029] FIG. 2 is a flowchart of an online part of an algorithm for repairing corrupted Reed-Solomon codes according to embodiments of the disclosure.

[0030] FIG. 3 is a flowchart of a method for reconstructing an erased symbol from reduced-size data, according to an embodiment of the disclosure.

[0031] FIG. 4 is a block diagram of a system for repairing corrupted Reed-Solomon codes, according to an embodiment of the disclosure,

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0032] Exemplary embodiments of the invention as described herein generally provide systems and methods for repairing corrupted Reed-Solomon codes. While embodiments are susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. Herein, when two or more elements are described as being about the same as each other, such as AB, it is to be understood that the elements are identical to each other, indistinguishable from each other, or distinguishable from each other but functionally the same as each other as would be understood by a person having, ordinary skill in the art.

1. Overview

[0033] It was recently shown by V. Guruswami and M. Wootters, Repairing Reed-Solomon. Codes, arXiv:1509.04764v1, the contents of which are herein incorporated by reference in their entirety, hereinafter Guruswami, that if C is a Reed-Solomon code of length n:=q.sup.m over .sub.q.sub.m, where q is a prime power, and m , and ndim(C)n/q, then any erased coordinate in C can be repaired by transmitting only one .sub.q-element from each one of the non-erased coordinates. Embodiments of the disclosure consider such simple repair schemes: .sub.q-linear repair schemes in which repairing a single erased coordinate in an .sub.q.sub.m-linear code requires transmitting at most one .sub.q-symbol from each non-erased coordinate.

[0034] According to embodiments, a necessary and sufficient condition for a code to have a simple repair scheme is provided. A condition according to an embodiment is closely related to the task of finding the dimension of subfield-subcodes. In the case where the code to be repaired is a Reed-Solomon code, a condition according to an embodiment is closely related to the task of calculating the dimension of alterant codes. As a first application of the condition, it is used to re-prove the above result of Guruswami.

[0035] According to embodiments, the case of Reed-Solomon codes over .sub.2.sub.2r with an evaluation set hat is an .sub.2-subspace of .sub.2.sub.2r is considered. Here, q=2.sup.r, while m=2. In this context, it is shown that for all even d4, if rd1+log.sub.2(d), then there exists a d-dimensional .sub.2-subspace U of .sub.2.sub.2r such that the Reed-Solomon code defined on U has a simple repair scheme.

[0036] For the special case where d=4, it is shown that for all r2, there exists an appropriate .sub.2-subspace U .Math. .sub.2.sub.2r such that the Reed-Solomon code defined on U has a simple repair scheme. Shortening such a code, a shortened Reed-Solomon code is obtained that requires reading a total of only 52 bits for repairing any single erased coordinate. Note that in the best existing repairing scheme for the Hadoop distributed file system (HDFS) code, repairing a single erased coordinate requires reading a total of 64 or 60 bits, depending on the erased coordinate, from the non-erased coordinates. In addition, the Hitchhiker-nonXOR code of Rashmi et al., A Hitchhiker's Guide to Fast and Efficient Data Reconstruction in Erasure coded Data Centers, SIGCOMM'14, Aug. 17-22, 2014, Chicago, USA, the contents of which are herein incorporated by reference in their entirety, achieves the same saving in repair bandwidth as a code according to embodiments, but only for the 10 information coordinates, and at the cost of coupling pairs of bytes,

[0037] In addition to the above case of of Reed-Solomon codes over .sub.2.sub.2r, for which there is a proof that many subspaces result in a simple repair scheme for any r and even d, as long as the dimension k satisfies k2.sup.d2.sup.d/2, embodiments of the disclosure also consider the case of Reed-Solomon codes over .sub.2.sub.mr for m>2. For this case, there exist some concrete examples of subspaces U of dimension d divisible by m, such that for an RS code of dimension

[00003]$k{2}^d-2^{d-\frac{d}{m}}$

with evaluation set U, there is a simple .sub.2.sub.r-linear repair scheme. With such a scheme, when a single node fails, the surviving nodes need transmit only 1/m of their content to restore the failed node.

2. Preliminaries

[0038] Throughout this disclosure, q is a prime power and m .sup.+. If F is a field and M F.sup.rn, for r, n .sup.+, then ker(M) represents the kernel of the map F.sup.n.fwdarw.F.sup.r defined by xMx. If F is a finite field, then for k, n , an [n, k].sub.F code is an F-linear code of dimension k in F.sup.n.

2,1. The Trace Map

[0039] Definition 2.1: The trace map, Tr=:.sub.z.sub.m.fwdarw..sub.q, is defined by

[00004]$\begin{array}{c}\mathrm{Tr}.Math.\left(x\right):=.Math.x+\left(x\right)+{}^2\left(x\right)+\mathrm{.Math.}+{}^{m-1}\left(x\right),\\ =.Math.x+x^q+x^{q^2}+\mathrm{.Math.}+x^{q^{m-1}},\end{array}$

where :xx.sup.q is the Frobenius automorphism of .sub.q.sub.m over .sub.1. For x, Y .sub.q.sub.m, the notation x.Math..sub.Try:=Tr(xy) will be used. In addition, for x .sub.q.sub.m and y=(y.sub.0, . . . , y.sub.n1) .sub.q.sub.m.sup.n for some n .sup.+, write

x.Math..sub.Try;=(x.Math..sub.Try.sub.0, . . . , x.Math..sub.Try.sub.n1) .sub.q.sup.n,

and similarly for column vectors,

[0040] Since a polynomial of degree q.sup.m1 cannot have q.sup.m roots, the trace is not identically zero, and hence (x, y)Tr(xy)=x.Math..sub.Try is a non-degenerate symmetric .sub.q-bilinear form. As usual in this case of finite dimension, the map :xx.Math..sub.Try) is an isomorphism of .sub.q-vector spaces between .sub.q.sub.m and its dual space.

[0041] Let b.sub.1, . . . , b.sub.m be a basis of .sub.q.sub.m over .sub.q. The elements b.sub.1, . . . , b.sub.m that map under to the dual basis of b.sub.1, . . . , b.sub.m are referred to as the trace-dual basis of b.sub.1, . . . , b.sub.m. By definition, b.sub.1.Math..sub.Trb.sub.j=1.sub.(i=j), so that if x .sub.q.sub.m is represented as x=.sub.i a.sub.ib.sub.i f with a.sub.i .sub.q for all i, then for all i, a.sub.i=x.Math..sub.Trb.sub.i. [0042] Remark 2.2 Note that for all x,y,z .sub.q.sub.m, (xy).Math..sub.Trz=x.Math..sub.Tr(yz).

2.2, Linear Repair Schemes

[0043] Linear repair schemes are defined in Guruswami, incorporated by reference above, as follows. [0044] Definition 2.3 Let n , let C .sub.q.sub.m.sup.n be a linear code, and let i {0, . . . , n1}. An .sub.q-linear repair scheme for coordinate i of C comprises: [0045] 1. For all j {0, . . . , n1}\{i}, a set L.sub.j of .sub.q-linear functionals .sub.q.sub.m.fwdarw..sub.q; [0046] 2. An .sub.q-linear function f: .sub.q.sup..sup.ji.sup.|L.sup.j.sup.|.fwdarw..sub.q.sub.m, such that for all (c.sub.0, c.sub.1, . . . , c.sub.n1) C:

[00005]$c_i=f\left({\left\{\left(c_j\right)\right\}}_{\underset{t{L}_j}{ji}}\right).$

The repair bandwidth b.sub.i of the above repair scheme for coordinate i of C is defined as b.sub.i:=log.sub.2(q).Math..sub.ji|L.sub.j|. This is the total number of bits that have to be read from the non-erased coordinates to restore the erased coordinate i. The normalized repair bandwidth b.sub.i is the repair bandwidth divided by the number of bits stored in a single node.

[0047] If for all ji, |L.sub.j|1, then the linear repair scheme for coordinate i is simple.

[0048] So, in a simple linear repair scheme for coordinate i, at most 1 sub-symbol, i.e., a symbol from the subfield .sub.q, has to be read from each non-erased coordinate to restore coordinate i. Hence, the repair bandwidth is not larger than (n1)log.sub.2(q). [0049] Remark 2.4 If a linear code C .Math. .sub.q.sup.n has a transitive automorphism group, then the existence of a simple .sub.q-linear repair scheme for some coordinate of C is equivalent to the existence of a simple .sub.q-linear repair scheme for all coordinates. Recall that the automorphism group of C is the set Aut(C) of all permutations of {0, . . . , n1} such that .Math.C=C, where for c=(c.sub.0, . . . , c.sub.n1) C, the action of defined by .Math.c=(c.sub.(0), . . . , c.sub.(n1)), the group operation on Aut(C) is composition. Aut(C) is called transitive if for all i,j, there exists Aut(C) with (i)=j. More generally, if there exists a linear repair scheme for some coordinate i of C and C has a transitive automorphism group, then the repair scheme can be permuted to become a linear repair scheme for any coordinate in detail, let be an automorphism of C with (i)=i. By re-labeling the coordinates, the task of restoring coordinate i of (c.sub.0, . . . , c.sub.n1) C is transformed to the task of restoring coordinate i of d:=(c.sub.(0), . . . , c.sub.(i), . . . , c.sub.(n1) C. So, using the notation of Definition 2.3, to restore coordinate i, for all ji( (j)(i)=i), node (j) should use the functionals from L.sub.j to calculate the sub-packets it transmits. [0050] Remark 2.5 Suppose that a code C has a simple .sub.q-linear repair scheme for some coordinate i. Then the same holds also for any subcode Consequently, if C has a simple repair scheme for all coordinates, so does any code obtained by shortening C.

3. The Repairing Theorem

[0051] According to an embodiment of the disclosure, a necessary and sufficient condition for the existence of a simple .sub.q-linear repair scheme is presented. A result according to an embodiment of the disclosure is Theorem 3.2, which specifies a condition in terms of the dimensions of some sub field subcodes.

[0052] For a vector v, write diag(v) for the diagonal matrix with v on its main diagonal. [0053] Lemma 3.1 For n , let C .Math. .sub.q.sub.m.sup.n be a linear code of dimension k with the first coordinate not identically zero, so that C has a generator matrix of the form

[00006]$\begin{array}{cc}G:=\left(\begin{array}{ccccc}1& g_{01}& g_{02}& \mathrm{.Math.}& g_{0,n-1}\\ 0& g_{11}& g_{12}& \mathrm{.Math.}& g_{1,n-1}\\ 0& g_{21}& g_{22}& \mathrm{.Math.}& g_{2,n-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& g_{k-1,1}& g_{k-1,2}& \mathrm{.Math.}& g_{k-1,n-1}\end{array}\right)=:\left(\begin{array}{cc}1& g_0\\ 0^T& G^{}\end{array}\right).& \left(1\right)\end{array}$

Then the code C has a simple .sub.q-linear repair scheme for the first coordinate if and only if the following condition holds: [0054] Condition (*): There exists a vector v:=(v.sub.1, . . . , v.sub.n1) .sub.q.sub.m.sup.n1 such that, writing C .Math. .sub.q.sup.n1 for the code with parity-check matrix H:=Gdiag(v), where C is the .sub.q-subfield subcode of ker(H), there exists an .sub.q-linear subcode D .Math. C with [0055] (1) dim(D)=m and [0056] (2) D ker(g.sub.0diag(v))={0}. [0057] Proof: A general codeword of C has the form

c=(c.sub.0, c.sub.1, . . . , c.sub.n1):=(x.sub.0, x.sub.1, . . . , x.sub.k1)G

for some x.sub.0, . . . , x.sub.k1 .sub.q.sub.m. A task is to restore c.sub.0=x.sub.0 from the known c.sub.1, . . . , c.sub.n1. For all j {1, . . . , n1}, there is

[00007]$c_j=g_{0.Math.j}.Math.x_0+\underset{i=1}{\overset{k-1}{.Math.}}.Math.g_{\mathrm{ij}}.Math.x_i.$

A general .sub.q-linear functional of the form v.sub.j .Math..sub.Tr(), for some v.sub.i .sub.q.sub.m, can be applied to c.sub.j while recalling Remark 2.2, to get

v.sub.j.Math..sub.Trc.sub.j=(v.sub.jg.sub.0j).Math..sub.Trx.sub.0+.sub.i=1.sup.k1(v.sub.jg.sub.ij).Math..sub.Trx.sub.i. (2)

Collecting EQS. (2) for all j (1, . . . , n1):

{v.sub.j.Math..sub.Trc.sub.j}.sub.j=1.sup.n1=x.sub.0.Math..sub.Tr{v.sub.j.sup.g.sub.0j}.sub.j=1.sup.n=1+.sub.i=1.sup.k1x.sub.i.Math..sub.Tr{v.sub.jg.sub.ij}.sub.j=1.sup.n1. (3)

Because .sub.q.sub.m25 .sub.q.sup.m as an .sub.q-vector space, the map f of Definition 2.3 might as well have a codomain of .sub.q.sup.m. So, let A .sub.q.sup.m(n1), and consider the vector

A{v.sub.j.Math..sub.Trc.sub.j}.sub.j=1.sup.n1=x.sub.0.Math..sub.Tr(A{v.sub.jg.sub.0j}.sub.j=1.sup.n1)+.sub.i=1.sup.k1x.sub.i.Math..sub.Tr(A{v.sub.jg.sub.ij}.sub.j=1.sup.n1),

where the equality follows from EQ. (3) and the .sub.q-bilinearity of (-).Math..sub.Tr(-),which implies that, for all i and all l:

[00008]$\begin{array}{c}{\left(A.Math.\left(x_i.Math.{.Math.}_{\mathrm{Tr}}.Math.{\left\{v_j.Math.g_{\mathrm{ij}}\right\}}_j\right)\right)}_{}=.Math.{\mathrm{row}}_{}\left(A\right).Math.\left(x_i.Math.{.Math.}_{\mathrm{Tr}}.Math.{\left\{v_j.Math.g_{\mathrm{ij}}\right\}}_j\right)\\ =.Math.x_i.Math.{.Math.}_{\mathrm{Tr}}.Math.\left({\mathrm{row}}_{}\left(A\right).Math.{\left\{v_j.Math.g_{\mathrm{ij}}\right\}}_j\right).Math.\left(\mathrm{bilinearity}\right)\\ =.Math.{\left(x_i.Math.{.Math.}_{\mathrm{Tr}}.Math.\left(A.Math.{\left\{v_j.Math.g_{\mathrm{ij}}\right\}}_j\right)\right)}_{}.\end{array}$

[0058] Because the x.sub.i are arbitrary, a necessary condition for reconstruction is that

[0059] (i) i {1, . . . , k1}: A{v.sub.jg.sub.ij}.sub.j=1.sup.n1=0, and

[0060] (ii) The m elements of the vector A{v.sub.jg.sub.0j}.sub.j=1.sup.n1=A(g.sub.0diag(v)).sup.T .sub.q.sub.m.sup.m are .sub.q-linearly independent, that is, these elements form a basis for .sub.q.sub.m/.sub.q.

But (i) and (ii) is clearly also a sufficient condition: given (i), then

A{v.sub.j.Math..sub.Trc.sub.j}.sub.j=1.sup.n1=x.sub.0.Math..sub.Tr(A{v.sub.jg.sub.0j}.sub.j=1 .sup.n1),

and given (ii), the elements of this vector are the coefficients in the description of x.sub.0 as a linear combination of the elements of the dual of the basis in (ii). So, there exists a simple repair scheme for the first coordinate of C if there exist v and A such that conditions (i) and (ii) bold.

[0061] Note that condition (i) is equivalent to

[00009]$\left(\begin{array}{cccc}{v}_1.Math.g_{11}& v_2.Math.g_{12}& \mathrm{.Math.}& v_{n-1}.Math.g_{1,n-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ v_1.Math.g_{k-1,1}& v_2.Math.g_{k-1,2}& \mathrm{.Math.}& v_{n-1}.Math.g_{k-1,n-1}\end{array}\right).Math.A^T=0.$

Recalling that H:=G diag(v), it can be seen that condition (i) is equivalent to HA.sup.T=0.

[0062] To, complete the proof, it will be verified that condition (*) there exists v and A such that conditions (i) and (ii) hold.

[0063] Suppose that condition (*) holds. Let the m rows of A be a basis of the code D. Then by the definition of D, it follows that HA.sup.T=0, so that condition (i) holds. For condition (ii), suppose that there exists a row vector t .sub.q.sup.m such that t(A(g.sub.0diag(v)).sup.T)=0. Then A.sup.Tt.sup.T is in D ker(g.sub.0diag (v)), and hence must be the zero vector. Since the rows of A are independent, this implies that t is the zero vector, as required.

[0064] Suppose that there exist v and A such that conditions (i) and (ii) hold. Because of condition (ii), the rows of A must be .sub.q-linearly independent. Let D be the .sub.q-span of the rows of A. Then dim(D)=m. In addition, since by condition (i) HA.sup.T=0, it holds that D .Math. C. Finally, a vector in D is of the form tA for some row vector t .sub.q.sup.m. If (t A).sup.T ker(g.sub.0diag (v)), then

(g.sub.0diag(v)A.sup.T)t.sup.T=0.

Because the elements of the vector g.sub.0diag(v)A.sup.T .sub.q-linearly independent by condition (ii), it can be seen that t is the zero vector, as required. [0065] Theorem 3.2 The code C of of Lemma 3.1 has a simple .sub.q-linear repair scheme for the first coordinate if and only if the following condition holds: [0066] Condition (**): There exists a vector v:=(v.sub.1, . . . , v.sub.n1) .sub.q.sub.m.sup.n1 such that the following condition holds:

[0067] Writing C .Math. .sub.q.sup.n1 for the code with parity-check matrix H:=Gdiag(v) and C .Math. .sub.q.sup.n1 for the code with parity-check matrix

[00010]$H^{}:=\left(\begin{array}{c}{g}_0\\ G^{}\end{array}\right).Math.\mathrm{diag}.Math.\left(v\right),$

it follows that dim(C)dim(C)m, which is equivalent to dim(C)=dim(C)m. Note that adding one line to a check matrix over .sub.q.sub.m for a code over .sub.q can decrease the dimension by at most m. [0068] Proof. It will be shown that Condition (**) of the theorem Condition (*) of Lemma 3.1.

[0069] Suppose that (**) holds. Then it is possible to choose c.sub.1, . . . , c.sub.m .sub.q.sup.n1 that complete a basis of C to a set of dim(C)+m linearly independent elements in C. Let D be the .sub.q-span of c.sub.1, . . . , c.sub.m). Then by construction D C, and dim(D))=m. Also,

[00011]$\begin{array}{c}D.Math.\ker \left(g_0.Math.\mathrm{diag}\left(v\right)\right)=.Math.\left(D.Math.C^{}\right).Math.\ker \left(g_0.Math.\mathrm{diag}\left(v\right)\right).Math.\left(\mathrm{sinceD}.Math.C^{}\right)\\ =.Math.D.Math.\left(C^{}.Math.\ker \left(g_0.Math.\mathrm{diag}\left(v\right)\right)\right)\\ =.Math.D.Math.C^{}\\ =.Math.\left\{0\right\},\end{array}$

where the last equality follows front the way the basis of D as constructed.

[0070] Suppose that Condition (*) holds. Then

C (C ker(g.sub.0diag(v)))D.

But C ker(g.sub.0diag(v)) is just C, so that C C D. Since dim(D)=m by assumption, it follows that dim(C)dim(C)m.
4. Reed-Solomon Codes of Length q.sup.m over .sub.q.sub.m

[0071] As a first example for an application of Theorem 3.2, Theorem 1 of Guruswami, incorporated above, will be re-proven. According to embodiments of the disclosure, from this to point on, a Reed-Solomon code of dimension k over .sub.q.sub.m is the code obtained by evaluating polynomials of degreek1 from .sub.q.sub.q[X] on a subset comprising at least k points of .sub.q.sub.m. [0072] Theorem 4.1 (Theorem 1 of Guruswami): Write n:=let k be such that nkn/q, that is, such that kq.sup.mq.sup.m1. Then the Reed-Solomon code of length n and dimension k over .sub.q.sub.m has a simple .sub.q-linear repair scheme for any coordinate. [0073] Proof. First, since a linear repair scheme, for at code is automatically also a linear repair scheme for any subcode, it suffices to consider the case k=q.sup.mq.sup.m1. Also, since the code has a (doubly) transitive automorphism group, it suffices to establish a simple linear repair scheme for the first coordinate (see Remark 2.4, above).

[0074] Now, suppose that k=q.sup.mq.sup.m1, and let .sub.q.sub.m be a primitive element. Then the following generator matrix for the Reed-Solomon code of dimension k and length q.sup.m is already in the form of EQ. (1)

[00012]$\begin{array}{c}G:=.Math.\left(\begin{array}{cccccc}1& 1& 1& 1& \mathrm{.Math.}& 1\\ 0& 1& & {}^2& \mathrm{.Math.}& {}^{n-2}\\ 0& 1& {}^2& {\left({}^2\right)}^2& \mathrm{.Math.}& {\left({}^{n-2}\right)}^2\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 1& {}^{q^m-q^{m-1}-1}& {\left({}^2\right)}^{q^m-q^{m-1}-1}& \mathrm{.Math.}& {\left({}^{n-2}\right)}^{q^m-q^{m-1}-1}\end{array}\right)\\ =:.Math.\left(\begin{array}{cc}1& 1\\ 0^T& G^{}\end{array}\right),\end{array}$

where g.sub.0=1, the all ones row vector of length q.sup.m1.

[0075] For j {1, . . . , q.sup.m31 1}, let v.sub.j:=.sup.(j1). Then H=Gdiag(v) is a check matrix of the cyclic code over .sub.q of length q.sup.m1 and zeros the elements of Z:={1, , . . . , .sup.q.sup.m.sup.q.sup.m1.sup.2} and their conjugates over .sub.q, while

[00013]$H^{}=\left(\begin{array}{c}{g}_0\\ G^{}\end{array}\right).Math.\mathrm{diag}\left(v\right),$

is a check matrix of the cyclic code over .sub.q with zeros the elements of Z:=Z {.sup.1} and their conjugates.

[0076] By Theorem 3.2, it is sufficient to, show that Z does, not contain an element of the orbit of .sup.1 under the action of Gal(.sub.q.sub.m/.sub.q), and that the orbit of .sup.1 has m elements. In this regard, recall that for a cyclic code C of length n with generator polynomial g, it follows that dim(C)=ndeg(g). Translating to the language of cyclotomic cosets, it should he shown that, the cyclotomic cosets modulo q.sup.m1 the numbers in {0,1, . . . , q.sup.mq.sup.m12} do not include the cyclotomic coset of (1)q.sup.m2, and that this last cyclotomic coset has m elements.

[0077] According to embodiments of the disclosure, it will be convenient to represent numbers in {0, . . . , q.sup.m2} as their length-m base-q expansions. So, for i {0, . . . , q.sup.m2}, write [i].sub.q=(i.sub.m1, i.sub.m=2, . . . , i.sub.0) for its base-q expansion, so that i=.sub.j=0.sup.m1 i.sub.jq.sup.j.

[0078] Now,

[q.sup.m2].sub.q=(q1, q1, . . . , q1, q2). (4)

Since all m cyclic shifts of this vector are distinct, the cyclotomic coset of q.sup.m2 indeed has m elements.

[0079] Also, since q.sup.mq.sup.m11=(q.sup.m1)q.sup.m1, then

[q.sup.mq.sup.m11].sub.q=(q2, q1, . . . , q1, q1). (5)

It follows from EQS. (4) and (5) that q.sup.mq.sup.m11 is the smallest element in the cyclotomic coset of q.sup.m2. Hence this cyclotomic coset does not contain any number in {0,1, . . . , q.sup.mq.sup.m12}.
5. Reed-Solomon Codes on .sub.2-Subspaces of .sub.2.sub.2r

[0080] According to embodiments, this section presents simple repair schemes for Reed-Solomon codes defined on an .sub.2-subspace of .sub.q.sub.2, where q=2.sup.r. A result according to an embodiment is Theorem 5.11, which states that for all even dimension d and for all rd1+log.sub.2(d), there exists an .sub.2-subspace U .Math. .sub.2.sub.2r with dim.sub.2(U)=d, such that the [2.sup.d, 2.sup.d Reed-Solomon code defined on U has a simple repair scheme. Moreover, the probability that a randomly selected subspace results in a simple repair scheme is 1O(1/2.sup.r).

[0081] In general, to check if Condition (**) holds, there is a need for an exact formula for the dimension of subfield subcodes, as lower bounds are insufficient. For this, some results from H. Stichtenoth, On the dimension of Subfield Subcodes, IEEE Trans. Inform. Theory, Vol. 36, No. 1, January 1990, the contents of which are herein incorporated by reference in their entirety, will be used, as follows. In what follows, let operate on vectors coordinate-wise. [0082] Proposition 5.1 (Lemmas 1, 2 and Corollary 1 of Stiehtenoth): For q a prime power and m , let :xx.sup.q be the Frobenius automorphism of .sub.q.sub.m/.sub.q. For n , let D .Math. .sub.q.sub.m.sup.nbe a linear code. Write D.sup.0;.sub.i=0.sup.m1 .sup.i(D) and D.sup.:=.sub.i=0.sup.m1 .sup.i(D). Then [0083] 1. dim()=dim(D.sup.0) [0084] 2. (D.sup.0).sup.=(D.sup.).sup. [0085] 3. dim()=Ndim (D.sup.).sup.

[0086] It will be convenient to state explicitly a special case of Proposition 5.1. [0087] Corollary 5.2 With the notation of Proposition 5.1, suppose that m=2. Then

[00014]$\begin{array}{cc}\dim \left(D.Math.{|}_{{}_q}\right)=n^{}-\dim \left(D^{}+\left(D^{}\right)\right)& \left(6\right)\\ .Math.=n^{}-\left(2.Math.\dim \left(D^{}\right)-\dim \left(D^{}.Math.\left(D^{}\right)\right)\right).& \left(7\right)\end{array}$

[0088] Before considering Reed-Solomon codes defined on .sub.2-vector subspaces of .sub.q.sub.2, need some additional background is needed. [0089] Definition 5.3 Let K L be finite fields. A K-linearized polynomial over L is a polynomial of the form .sub.i=0.sup.l a.sub.iX.sup.|K|.sup.l L[X]. Note that such a polynomial defines a K-linear map L.fwdarw.L. [0090] Theorem 5.4 (Theorem 3.52 of R. Lidl and H. Niederreiter, Finite Fields, Vol. 20 of Encyclopedia of Math. and its Applications, 2nd Ed., CUP, 1997, p. 110) Let K L be finite fields. Let U L be a K-linear subspace. Then .sub.xU (Xx) is a K-linearized polynomial over L.

[0091] From this point on, q is always a power of 2. Turn now to Reed-Solomon codes defined on .sub.2-vector subspaces of .sub.q.sub.2. Note that these codes have a transitive automorphism group: For a subspace U and for y U, the map .sub.y:xx+y permutes U , and is therefore an automorphism of the Reed-Solomon code defined on U, for the reason that the variable change XX+y does not increase the degree of a polynomial.

[0092] Let U be an .sub.2-subspace of .sub.q.sub.2, and set d:=dim(U). Let n:=|U|=2.sup.d, and let N:=n1 For l , ln1, let C=C(U, l) be the Reed-Solomon code obtained by evaluating polynomials of degreel from .sub.q.sub.2[X] on the points of U. Since C has a transitive automorphism group, it is sufficient to consider repairing schemes for the coordinate corresponding to 0 U.

[0093] From this point on, according to embodiments, it will be assumed that the vector v of Theorem 3.2 is defined by v.sub.u:=1/u for all u U\{0}, assuming that coordinates are labeled by elements of U. With this choice of v, the rows of the matrix H of Theorem 3.2 can be considered as a basis for the space of polynomial functions U\{0}.fwdarw..sub.q.sub.2 coming from polynomials of .sub.q.sub.2[X] of degreel1.

[0094] Let f.sub.U(X):=.sub.xU (Xx). Then by Theorem 5.4, there are some a.sub.0, . . . , a.sub.d1 .sub.q.sub.2 such that

f.sub.U(X)=X.sup.2.sup.d+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X,

and with a.sub.00 (since f separable by definition). There is an isomorphism of .sub.q.sub.2-algebras

:.sub.q.sub.2[X]/f.sub.U/X){tilde over (.fwdarw.)}{polynomial functions U\{0}.fwdarw..sub.q.sub.2}

g+(f.sub.U/X)(xg(x)).

For a polynomial g(X) .sub.q.sub.2[X], write g for the image of g in .sub.q.sub.2[X]/(f.sub.U/X).

[0095] Let D .Math. .sub.q.sub.2.sup.n1 defined by D:=ker(H) for the matrix H of Theorem 3.2, recalling that the vector v is fixed and defined by v.sub.u:=1/u for all u U\{0}). Note that C=D|.sub.q. Then 1, X, . . . , X.sup.l1 is a basis for .sup.1(D.sup.). Hence,

[00015]$\begin{array}{c}\dim \left(D^{}.Math.\left(D^{.Math.}\right)\right)=.Math.\dim \left({}^{-1}\left(D^{.Math.}.Math.\left({D^{}}^{}\right)\right)\right)\\ =.Math.\dim ({}^{-1}\left(D^{}\right).Math.{}^{-1}\left(\left(D^{.Math.}\right)\right)\\ =.Math.\dim \left(\begin{array}{c}{\mathrm{Span}}_{{}_{q^2}}.Math.\left\{\stackrel{\_}{1},\stackrel{\_}{X},\mathrm{.Math.}.Math.,{\stackrel{\_}{X}}^{-1}\right\}.Math.\\ {\mathrm{Span}}_{{}_{q^2}}.Math.\left\{\stackrel{\_}{1},{\stackrel{\_}{X}}^q,\mathrm{.Math.}.Math.,{\left({\stackrel{\_}{X}}^q\right)}^{-1}\right\}\end{array}\right).\end{array}$

[0096] Similarly, let D .sub.q.sub.2.sup.n1 be defined by D:=ker(H) for the matrix H of Theorem 3.2 and for our fixed v. Then 1, X, . . . , X.sup.l1, X.sup.1 span .sup.1(D.sup.), (this is, in fact, a basis for .sup.1(D.sup.): Since X.sup.1=a.sub.0.sup.1X.sup.2.sup.d.sup.2+a.sub.0.sup.1 a.sub.d1X.sup.2.sup.d1.sup.2+ . . . +a.sub.0.sup.1a.sub.1 (see below), the assumption l1<2.sup.d2 implies that X.sup.1 .Math. Spa {1, X, . . . , X.sup.l1}) and 1, X.sup.q, . . . , (X.sup.q).sup.l1).sup.q span .sup.1((D.sup.)).

[0097] Recalling that f.sub.U(X)/X=X.sup.2.sup.d.sup.1+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0 (where a.sub.0 0), then

X.sup.1=a.sub.0.sup.1X.sup.2.sup.d.sup.2a.sub.0.sup.1a.sub.d1X.sup.2.sup.d1.sup.2+ . . . +a.sub.0.sup.1a.sub.1,

and

(X.sup.1 ).sup.q=a.sub.0q(X.sup.q).sup.2.sup.d.sup.2+a.sub.0.sup.qa.sub.d1.sup.q(X.sup.q).sup.2.sup.d1.sup.2+ . . . +a.sub.0.sup.qa.sub.1.sup.1.

This implies the following lemma. [0098] Lemma 5.5 with the above notation, if lb2.sup.d12, then

Spa{1, X, . . . , X.sup.L1, X.sup.1}=Spa{1, X, . . . , X.sup.l1, X.sup.2.sup.d.sup.2},

and

Spa{1, X.sup.q, . . . , (X.sup.q).sup.l1, (X.sup.1).sup.q}=Spa{1, X.sup.q, . . . , (X.sup.q).sup.l1, (X.sup.q).sup.2.sup.d.sup.2}. [0099] Proof. Clear. [0100] Definition 5.6. For j , let wt.sub.2(j) be the number of 1's in the binary expansion of j: If j=.sub.i=0.sup.r a.sub.i2.sup.i with a.sub.i {0,1} for all i, then wt.sub.2(j):=.sub.i=0.sup.r a.sub.i. [0101] Lemma 5.7 For all j.sub.1, J.sub.2 , wt.sub.2(j.sub.1+j.sub.2)wt.sub.2(j.sub.1)+wt.sub.2(j.sub.2). [0102] Proof. Suppose first that j.sub.2=2.sup.s for some s. Write j.sub.1=.sub.i=o.sup.r a.sub.i2.sup.i, where

r:=max{([log.sub.2(j.sub.1)],s}+1,

so that r>s and a.sub.r=0. If a.sub.s=0, then clearly wt.sub.2(j.sub.1+j.sub.2)=wt.sub.2(j.sub.1)+wt.sub.2(j.sub.2) Otherwise, let s>s be the smallest such that a.sub.x=0. The single 1 from the binary expansion of j.sub.2 propagates as a carry, so that for all i {s,s+1, . . . , s1}, the i-th digit of the binary expansion of j.sub.i+j.sub.2 is 0, the s-th digit of this binary expansion is 1, and all other digits of this expansion are the same as those of the expansion of j.sub.1. All in all, the total, number of 1's is wt.sub.2(j.sub.1)+1(ss)wt.sub.2(j.sub.1)+wt.sub.2(j.sub.2)(ss)<wt.sub.2(j.sub.1)+wt.sub.2(j.sub.2), as required

[0103] For the general case, suppose that wt.sub.2(j.sub.2)2, and assume the assertion true for all j.sub.2 with smaller weight (note that the case j.sub.2=0 is obvious). Then, write j.sub.2=j.sub.2+j.sub.2 with wt.sub.2(j.sub.2)=1 and wt.sub.2(j.sub.2)=wt.sub.2(j.sub.2)1. Then

[00016]$\begin{array}{c}{\mathrm{wt}}_2\left(j_1+j_2\right)=.Math.{\mathrm{wt}}_2\left(\left(j_1+j_2^{}\right)+j_2^{}\right)\\ .Math.{\mathrm{wt}}_2\left(j_1+j_2^{}\right)+{\mathrm{wt}}_2\left(j_2^{}\right).Math.\left(\mathrm{induction}.Math..Math.\mathrm{hypothesis}\right)\\ .Math.{\mathrm{wt}}_2\left(j_1\right)+{\mathrm{wt}}_2\left(j_2^{}\right)+{\mathrm{wt}}_2\left(j_2^{}\right).Math.\left(\mathrm{induction}.Math..Math.\mathrm{basis}\right)\\ =.Math.{\mathrm{wt}}_2\left(j_1\right)+{\mathrm{wt}}_2\left(j_2\right),\end{array}$

as required. [0104] Proposition 5.8 Using the terminology of the paragraphs receding EQ. (8), for all d2, for all j with wt.sub.2(j)d1, and for all s .

(X.sup.2.sup.s).sup.j Spa{X.sup.i|i {1, . . . , 2.sup.d2}and wt.sub.2(i)wt.sub.2(j)}. (9) [0105] Remark it is clear that 1, X, . . . , X.sup.2.sup.3.sup.2 span .sub.q.sub.2[X]/(f.sub.u/X), and for all i {0, . . . , 2.sup.d2}, wt.sub.2(i)d1. Hence the maximum weight of an exponent in a spanning set is d1 even if wt.sub.2(j)>d1. Hover while not really necessary for the rest of this disclosure, the condition wt.sub.2(j)d1 is required for stating that 1 is not in the spanning set on the right-hand side of EQ. (9). [0106] Proof of Proposition 5.8: First note that since wt.sub.2(2.sup.sj)=wt.sub.2(j), there is no loss of generality in assuming s=0. According to embodiments, let s=0 and proceed b induction on wt.sub.2(j). For the basis, suppose that wt.sub.2(j)=1, that is, that j=2.sup.r for some r. Hence, it should be shown that for all r,

X.sup.2.sup.r Spa{X.sup.i|i {1, . . . , 2.sup.d2.sup.d2} and wt.sub.2(i)=1},

for which induction on r will be used. If r<d the assertion is clear. Suppose, therefore, that rd and that there exist b.sub.0, . . . , b.sub.d1 such that

X.sup.2.sup.r1=.sub.n=0.sup.d1 b.sub.uX.sup.2.sup.u.

Squaring this equation:

X.sup.2.sup.r=.sub.u=0.sup.d2 b.sub.u.sup.2X.sup.2.sup.u+1+b.sub.d1.sup.2X.sup.2.sup.d.

But since f.sub.U(X)=X.sup.2.sup.d+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X, then X.sup.2.sup.d=a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X, as required. This establishes the basis of the induction on wt.sub.2(j).

[0107] For the induction step, suppose that wt.sub.2(j)2 and the assertion is true for all j with wt.sub.2(j)<wt.sub.2(i). Write j=2.sup.j.sup.1+ . . . +2.sup.j.sup.w for the binary expansion of j, where j.sub.1< . . . <j.sub.w and w=wt.sub.2(j)2. Then, by the induction basis,

[00017]$\begin{array}{cc}\begin{array}{c}{\stackrel{\_}{X}}^j=.Math.{\stackrel{\_}{X}}^{2^{j_1}}.Math.{\stackrel{\_}{X}}^{2^{j_2}}.Math..Math.\mathrm{.Math.}.Math..Math.{\stackrel{\_}{X}}^{2^{j_w}}\\ =.Math.\left(\underset{i_1=0}{\overset{d-1}{.Math.}}.Math.{}_{i_1}^{\left(1\right)}.Math.{\stackrel{\_}{X}}^{2^{i_1}}\right).Math.\left(\underset{i_2=0}{\overset{d-1}{.Math.}}.Math.{}_{i_2}^{\left(2\right)}.Math.{\stackrel{\_}{X}}^{2^{i_2}}\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(\underset{i_w=0}{\overset{d-1}{.Math.}}.Math.{}_{i_{w.Math.}}^{\left(w\right)}.Math.{\stackrel{\_}{X}}^{2^{i_{w.Math.}}}\right)\end{array}& \left(10\right)\end{array}$

for some .sub.0.sup.(1), . . . , .sub.d1.sup.(1), . . . , .sub.0.sup.(w) .sub.q.sub.2. Hence, X.sup.j is a linear combination of elements the form

X.sup.2.sup.i1.sup.+ . . . +2.sup.iw 11)

Two cases can be distinguished as follows,
Case I. If there are some l.sub.1, l.sub.2 such that i.sub.l.sub.1=.sub.l.sub.2, then 2.sup.l.sup.i1+2.sup.l.sup.i2=2.sup.l.sup.i1 .sup.+1, so that

X.sup.2.sup.i1.sup.+ . . . +2.sup.iw=X.sup.2.sup.111.sup.+1.Math.X.sup..sup.r11, .sup.l2.sup.2.sup.ir. (12)

By Lemma 5.7, wt.sub.2(.sub.rl.sub.1.sub.,l.sub.2 2.sup.i.sup.r)w2l =wt.sub.2(j)2, so that it follows from the induction hypothesis and EQ. (12) that

[00018]${\stackrel{\_}{X}}^{2^{i_1}+\mathrm{.Math.}+2^{i_w}}=\left(\underset{i=1}{\overset{d-1}{.Math.}}.Math.{}_i.Math.{\stackrel{\_}{X}}^{2^i}\right).Math.\left({.Math.}_{\underset{{\mathrm{wt}}_2\left(k\right){\mathrm{wt}}_2\left(j\right)-2}{k\left\{1,\mathrm{.Math.}.Math.,2^d-2\right\}}}.Math.{}_k.Math.{\stackrel{\_}{X}}^k\right)$

for some coefficients {.sub.i}, {.sub.k}. This last expression is itself an .sub.q.sub.2-linear combination of elements of the form X.sup.2.sup.i.sup.+k with wt.sub.2(2.sup.i+k)1+wt.sub.2(k)wt.sub.2(j)1, by lemma 5.7. Using the induction hypothesis again, the desired result is obtained.
Case 2. All the i.sub.l are distinct. Since by assumption w=wt.sub.2(j)d1 and wt.sub.2(2.sup.d1)=d, 2.sup.i.sup.1+ . . . +2.sup.i.sup.w2.sup.d2. Also, in this case wt.sub.2(2.sup.i.sup.1+ . . . +2.sup.i.sup.w)=w, so that EQ. (11) is already in the desired form. [0108] Proposition 5.9 Maintaining the above notation, for all g .sub.q.sub.2[X], g.sup.q=0 iff g=0). Also, if g.sub.1, . . . , g.sub.4 .sub.q.sub.2[/x]/(f.sub.uX) are .sub.q.sub.2 linearly independent, then so are g.sub.1.sup.q, . . . , g.sub.r.sup.q. [0109] Proof: For the first assertion, note that

[00019]${\stackrel{\_}{g}}^q=0\frac{f_U}{X}\left|g^q\frac{f_U}{X}\right|g,$

where the rightmost implication holds because f.sub.U, and hence also

[00020]$\frac{f_U}{X},$

is separable. Hence g=0 g=0, as required.

[0110] For the second assertion, suppose that .sub.i=1.sup.r .sub.ig.sub.i.sup.q=0 for some .sub.1, . . . , .sub.r .sub.q.sub.2. Then

(.sub.i=1.sup.r .sup.1(.sub.i)g.sub.i).sup.q=0,

so that .sub.i=1.sup.r .sup.1(.sub.i)g.sub.i=0 by the first part. Since the g.sub.i are linearly independent, then .sup.1(.sub.i)=0 for all i, and hence also.sub.i =0 for all i. [0111] Proposition 5.10 Using the terminology of the paragraphs preceding EQ. (8). Suppose that the dimension of the .sub.2-subspace U of .sub.q.sub.2 is d, so that the Reed-Solomon code C defined on U is a code. Suppose that the vector v of Theorem 3.2 is given by v.sub.u1/u for all u U\(0). Suppose also that

[00021]$l{l}_0:=\{\begin{array}{cc}{2}^d-2^{d/2}-1& \mathrm{if}.Math..Math.d.Math..Math.\mathrm{is}.Math..Math.\mathrm{even}\\ d^2-d^{\left(d+1\right)/2}-1& \mathrm{if}.Math..Math.d.Math..Math.\mathrm{is}.Math..Math.\mathrm{odd}.\end{array}$

Then for C of Theorem 3.2, dim(C)2.

Remarks:

[0112] 1. Informally, this proposition states that half of Condition (**) is satisfied for any subspace of dimension d if ll.sub.0. Note that l.sub.0 depends on d, but not on q. For example, for even d and for all q with q.sup.22.sup.d, the proposition shows that half of Condition (**) is satisfied for codes of length n=2 and dimension up to n{square root over (n)} in .sub.q.sub.2.sup.n. In the sequel, it will be shown that for r large enough, all of condition (**) is satisfied for some [2.sup.d, 2.sup.d Reed-Solomon codes.

[0113] 2. Note that for odd d, the codimension is the same as that for d+1. Hence, the parameters of an odd d can be achieved by shortening a code designed for the even dimension d+1. Therefore, apart from the current proposition, only even d will be considered.

[0114] 3. Note that for a choice according to an embodiment of v, there do exist some subspaces U .Math. .sub.q.sub.2 with dim(U)=d for which Condition (**) does not bold. For example, if d=q, then Condition (**) does not hold for U=.sub.q .sub.q.sub.2, since a single additional row with entries front .sub.q in the check matrix cannot decrease the .sub.q-dimension by more than 1. Similarly, the condition does not hold for subspaces of the form z.Math..sub.q for z *.sub.q.sub.2. [0115] Proof of Proposition 5.10: Recall that D .Math. .sub.q.sub.2 is the code with parity-check matrix H, so that C=D|.sub.q. By EQ. (7) of Corollary 5.2,

[00022]$\begin{array}{cc}\begin{array}{c}\dim \left(C^{}\right)=2^d-1-2.Math.\dim \left(D^{}\right)+\dim \left(D^{}.Math.\left(D^{}\right)\right)\\ =\dim .Math.\left(D^{}.Math.\left(D^{}\right)\right)+2^d-1-2.Math.l,\end{array}& \left(13\right)\end{array}$

where dim(D.sup..Math.)=l has been used, and recalling that that 1, X, . . . , X.sup.l1 is a basis for .sup.1(D.sup..Math.). Hence, to prove the assertion, it is sufficient to prove that

dim(D.sup..Math. (D.sup..Math.))2l+32.sup.d.

In view of EQ. (8), it should be shown that

dim(Spa{1, X, . . . , X.sup.l=1} Spa{1, X.sup.q, . . . , (X.sup.q).sup.l1{)2l+3<2.sup.d. (14)

In other words, it should be shown that

Spa{1, X.sup.q, . . . , (X.sup.q).sup.l1}(15)

contains 2l+32.sup.d independent elements that can be written as linear combinations of 1, X, . . . , X.sup.l1. Note first that 1, X.sup.q, . . . , (X.sup.q).sup.l1 are .sub.q.sub.2-linearly independent, because 1, X, . . . , X.sup.l1 are linearly dependent and, by Proposition 5.9, the map gg.sup.q preservers this property.

[0116] Write

A:=|{i {0, . . . , l1}|wt.sub.2(i)>wt.sub.2(l1)}|

and

B:=|{i {l, . . . , 2.sup.d2}|wt.sub.2(i)wt.sub.3(l1)}|.

It follows from Proposition 5.8 that for each of the lA values of i in {0, . . . , l1} with wt.sub.2(i)wt.sub.2(l1), (X.sup.q) a linear combination of classes X.sup.j with wt.sub.2(j)wt.sub.2(l1). Each such linear combination involves at most B classes X.sup.j with jl. Hence, up to B of the lA elements (X.sup.q).sup.i can be used to cancel all classes X.sup.j with jl in the remaining LAB elements. This can be done by choosing elements (X.sup.q).sup.i whose projections to the coordinates X.sup.j with jl and wt.sub.2(j)wt.sub.2(l1) form a basis to the projection of all lA elements (X.sup.q).sup.i to the same coordinates. Since the projection is to B coordinates, the number of elements in this basis is at most B. This results in at least lAB linearly independent elements in the intersection appearing in (14). Hence, if lAB2l+32.sup.d, then EQ. (14) is satisfied and dim(C)2. In Appendix A it is shown that for l=l.sub.0, it indeed holds that 2.sup.d3lA+B. So, for l=l.sub.0, then dim(C)2, and consequently the same holds for all ll.sub.0.

[0117] Theorem 5.11 Let d4 be even. Suppose that q=2.sup.r and that d elements x.sub.0, . . . , x.sub.d1 are drawn uniformly and independently from .sub.q.sub.2. Let U:=Span.sub.2{x.sub.0, . . . , x.sub.d1}. Suppose that l=l.sub.0=2.sup.d2.sup.d/21, so that if dim(U)=d, then the Reed-Solomon code C defined on U is a code. Suppose that the vector v, is given by v.sub.u=1/u for all u U\{0}. Then the probability that both dim(U)=d and Condition (**) holds is at least

[00023]$1-\frac{\left(1+\frac{d}{2}.Math.\left(q-1\right)\right).Math.\left(2^d-1\right)-d}{q^2-1},$

[0118] and is positive for rd1+log.sub.2(d). [0119] Remark 5.12

[0120] 1. The case of r=d/2 is a special case of Theorem 4.1, above.

[0121] 2. Some examples (see below) seem to suggest that the result should hold for all rd/2, and that the probability of drawing a good subspace U is much higher than in the theorem.

[0122] 3. For d=4, the theorem proves the existence of a good subspace for all r5, and Theorem 4.1 covers the case r=2. Since the two remaining cases of r=3, 4 are considered in the examples below, it can be seen that for d=4, a good subspace exists for all rd/2.

[0123] Before proving the theorem, some auxiliary results are needed. [0124] Proposition 5.13 Using the terminology of Proposition 5.10 and continue to assume that the vector v is given by v.sub.u=1/u for all u U\{0}. Suppose that l12.sup.d12, which holds for l=l.sub.0 if d2. Then Condition (**) for the [2.sup.d, l+ Reed-Solomon code defined on U is equivalent to the following condition: For all .sub.1, .sub.2 .sub.q.sub.2,

.sub.1X.sup.2.sup.d.sup.2+.sub.2(X.sup.q).sup.2.sup.2.sup.2 Spa{1, X, . . . , X.sup.l1, X.sup.q, (X.sup.q).sup.2, . . . ,(X.sup.q).sup.l1}.Math..sub.1.sub.2=0.

or, equivalently, to

X.sup.2.sup.d.sup.2 .Math. Spa{1, X, . . . , X.sup.l1, X.sup.q, (X.sup.q).sup.2, . . . , (X.sup.q).sup.l1}(16)

and

(X.sup.q).sup.2.sup.d.sup.2 .Math. Spa{1, X, . . . , X.sup.l1, X.sup.q, (X.sup.2).sup.2, . . . , (X.sup.q) .sup.l1, X.sup.2.sup.d.sup.2}. (17) [0125] Proof. By EQ. (6) of Corrolary 5.2,

[00024]$\begin{array}{c}\dim \left(C^{}\right)-\dim \left(C^{}\right)=\dim \left(D^{}.Math.{}_{{}_q}\right)-\dim \left(D^{}.Math.{}_{{}_q}\right)\\ =\dim \left(D^{}+\left(D^{}\right)\right)-\dim \left(D^{}+\left(D^{}\right)\right)\end{array}$

Since D.sup..Math.D.sup..Math.+Spa{v}, then

D.sup..Math.+(D.sup..Math.)=D.sup..Math.+(D.sup..Math.)+Spa{v,(v)}.

Hence Condition (**) holds iff for .sub.1, .sub.2 .sub.q.sub.2,

.sub.1v+.sub.2(v) D.Math.+(D.sup..Math.) .Math. .sub.1=.sub.2=0.

Applying the isomorphism .sup.1, it can be seen that Condition (**) holds iff for .sub.1, .sub.2 .sub.q.sub.2,

.sub.1X.sup.1+.sub.2(X.sup.1).sup.q Spa{1, X, . . . , X.sup.l1, X.sup.q, (X.sup.q).sup.2, . . . , (X.sup.q).sup.l1}, .Math..sub.1=.sub.2=0.

which, from Lemma 5.5, is equivalent to

.sub.1X.sup.2.sup.d.sup.2+.sub.2(X.sup.q).sup.2.sup.d.sup.2 Spa{1, X, . . . , X.sup.l1, X.sup.q, (X.sup.q).sup.2, . . . , (X.sup.q).sup.l1}.Math..sub.1=.sub.2=0.

This concludes the proof [0126] Definition 5.14 (The numbers i.sub.j) Recall that that d is assumed even, and note that the numbers i {0, . . . , 2.sup.d2) with wt.sub.2(i)=d1 are those numbers i of the form 2.sup.d12.sup.j with j {0, . . . , d1}. Hence, there are d such numbers, and d/21 of them are <l.sub.0=2.sup.d2.sup.d/21, namely, those with j {d/2+1, . . . , d1}. For j in the above range, write i.sub.j:=2.sup.d12.sup.d1j, so that

2.sup.d11=i.sub.0<i.sub.1< . . . <i.sub.d12.sup.d2

are all the numbers I {0, . . . , 2.sup.d2} with wt.sub.2(I)=d1, and i.sub.0, . . . , i.sub.d/22 are all the numbers i {0, . . . , l.sub.01} with wt.sub.2(i)=d1. [0127] Definition 5.15: (The matrices M.sub.r {tilde over (M)}.sub.r) for r0 and for i, j {0, . . . , 2.sup.d2}, define coefficients .sub.i,j.sup.(r) .sub.q.sub.2 by setting (X.sup.2.sup.r).sup.i=.sub.j=0.sup.2.sup.d.sup.2 .sub.i,j.sup.(r)X.sup.j. Define a matrix M.sub.r .sub.q.sub.2.sup.dd/2 as follows:

##STR00001##

Note that each column of M.sub.r includes some of the coefficients corresponding to (X.sup.2.sup.r).sup.i for some i with i=2.sup.d2 or i<l.sub.0 and wt.sub.2(i)=d1, and the coefficients appearing in each column correspond to all basis elements X.sup.j with wt.sub.2(j)=d1.

[0128] Define also a matrix {tilde over (M)}.sub.r .sub.q.sub.2.sup.d/2d/2 by letting {tilde over (M)}.sub.r include the last d/2 rows of M.sub.r, the part below the horizontal line in EQ. (18)). [0129] Proposition 5.16: Using the terminology of Proposition 5.13, if det({tilde over (M)}.sub.r) 0 for r=log.sub.2(q), then Condition (**) holds for l=l.sub.0, and hence for all ll.sub.0. [0130] Proof. Observe that the conditions of EQS. (16) and (17 can be written as follows:

[0131] (i) X.sup.2.sup.d.sup.2 is not in the .sub.q.sub.2-span of the projections of X.sup.q, (X.sup.q).sup.2, . . . , (X.sup.q).sup.l.sup.0.sup.1 to coordinates X.sup.l.sup.0, X.sup.l.sup.0.sup.+1, . . . , X.sup.2.sup.d.sup.2, and

[0132] (ii) to the projection of (X.sup.q).sup.2.sup.d.sup.2 to coordinates X.sup.l.sup.0, X.sup.l.sup.0.sup.+1, . . . , X.sup.2.sup.d.sup.3 is not in the .sub.q.sub.2-span of the projections of X.sup.q, (X.sup.q).sup.2, . . . , (X.sup.q).sup.l.sup.0.sup.1 to the same coordinates.

[0133] Consider (i) above. By Proposition 5.8, if X.sup.2.sup.d.sup.2 appears in a sum of the form .sub.i=1.sup.l.sup.0.sup.1 .sub.i(X.sup.q).sup.i, then at least one .sub.i with wt.sub.2(i)=d1 must be non-zero. In addition, by the same proposition, only elements of the form (X.sup.q).sup.i with wt.sub.2(i)=d1 may contribute to the projection to coordinates X.sup.j for j {l.sub.0, . . . , 2.sup.d3} with wt.sub.2(j)=d1. Hence, if the projections of (X.sup.q).sup.i for i {1, . . . , l.sub.01} with wt.sub.2(i)=d1 to the above coordinates are .sub.q.sub.2-linearly independent then (i) must hold in other words, linear independence of the last d/21 columns of {tilde over (M)}.sub.r is sufficient for (i).

[0134] Similarly, by Proposition 5.8 if the projection of (X.sup.q).sup.2.sup.d.sup.2 to the coordinates X.sup.j for j {l.sub.0, . . . , 2.sup.d3} with wt.sub.2(j)=d1 is not in the span of the projections of (X.sup.q).sup.i for i {1, . . . , l.sub.01} with wt.sub.2(i)=d1 to the same coordinates, then (ii) must hold, since by Proposition 5.8, since only coordinates j with wt.sub.2(j)=d1 are being considered, only i's with wt.sub.2(i)=d1 need be taken into account. For the other i's, (X.sup.q).sup.i has zero projection to the above coordinates, by the proposition. This shows that if det({tilde over (M)}.sub.r) 0, then both (i) and (ii) hold, as required.

[0135] To continue, parametrize the problem. Instead of working in .sub.q.sub.2[X], work in .sub.2[X, T.sub.0, . . . , T.sub.d1] for free variables T.sub.0, . . . , T.sub.d1. For this, let T:=(T.sub.0, . . . , T.sub.d1) be a vector of free variables over .sub.2[X], and let f (X, T) .sub.2[X, T] be defined by

f(X, T):=X.sup.2.sup.d+T.sub.d1X.sup.2.sup.d1+T.sub.d2X.sup.2.sup.d2+ . . . +T.sub.1X.sup.2+T.sub.0X.

Re-define (gg) to be the canonical homomorphism .sub.2[X, T].fwdarw..sub.2[X, T]/(f/X). Since .sub.2[T] .Math. .sub.2[X, T].fwdarw..sub.2[X, T]/(f/X) is an injection, which follows from deg.sub.X(uv)=deg.sub.X(u)+deg.sub.X(v), .sub.2[T] can be thought of as a subring of .sub.2[X, T]/(f/X). In addition, .sub.2[X, T]/(f/X) is a free .sub.2[T]-module with basis 1, X, . . . , X.sup.2.sup.d.sup.2. Note that 1, X, . . . , X.sup.2.sup.d.sup.2 do generate .sub.2[X, T]/(f/X) as an .sub.2[T]-module, since the coefficient of X.sup.2.sup.d.sup.1 in f/X is a unit.

[0136] The idea is that for any finite dimensional .sub.2-subspace U of any extension field K of .sub.2 (e.g., K=.sub.q.sub.2)the coefficients of f.sub.U can be substituted for the T.sub.i. [0137] Definition 5.17: (The matrices .sub.r and .sub.r). For integer r, define matrices .sub.r .sub.2[T].sup.dd/2 and .sub.r .sub.2[T].sup.d/2d/2 as follows. The matrix .sub.r is defined as the right-band side of EQ. (18), where now .sub.i,j.sup.(r) .sub.2[T] are the unique polynomials in (X.sup.2.sup.r).sup.i=.sub.j=0.sup.2.sup.d.sup.2 .sub.i,j.sup.(r)(T)X.sup.j. The matrix .sub.r is defined as the last d/2 rows of .sub.r. Note that by Lemma B.1, if for an .sub.2-subspace U .sub.q.sub.2, a.sub.0, . . . , a.sub.d1 .sub.q.sub.2 are such that f.sub.U(X)=X.sup.2.sup.d+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X, then M.sub.r=.sub.r(a.sub.0, . . . , a.sub.d1) and {tilde over (M)}.sub.r=.sub.r(a.sub.0, . . . , a.sub.d1). Consequently, det({tilde over (M)}.sub.r)=(det(.sub.r)) (a.sub.0, . . . , a.sub.d1).

[0138] Next, it will be shown that for rd/2, det(.sub.r) is not the zero polynomial in .sub.2[T]. To this end, begin with the following lemma. [0139] Lemma 5.18: (Update Lemma) Write

[00025]$A\left(T\right):=\left(\begin{array}{ccccccc}{T}_1& 1& T_{d-1}& T_{d-2}& \mathrm{.Math.}& T_3& T_2\\ 0& 0& T_0& 0& \mathrm{.Math.}& 0& 0\\ 0& 0& 0& T_0& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& \mathrm{.Math.}& T_0& 0\\ 0& 0& 0& 0& \mathrm{.Math.}& 0& T_0\\ T_0& 0& 0& 0& \mathrm{.Math.}& 0& 0\end{array}\right){{}_2\left[y\right]}^{dd}$

For all i and r, and for the i.sub.j's of Definition 5.14, the .sub.i,j.sup.(r)=.sub.i,j.sup.(r)(T) of Definition 5.17 satisfy

[00026]$\begin{array}{cc}\left(\begin{array}{c}{}_{i,2^d-2}^{\left(r+1\right)}\\ {}_{i,i_0}^{\left(r+1\right)}\\ {}_{i,i_1}^{\left(r+1\right)}\\ \mathrm{.Math.}\\ {}_{i,i_{d-2}}^{\left(r+1\right)}\end{array}\right)=A\left(\begin{array}{c}{\left({}_{i,2^d-2}^{\left(r\right)}\right)}^2\\ {\left({}_{i,i_0}^{\left(r\right)}\right)}^2\\ {\left({}_{i,i_1}^{\left(r\right)}\right)}^2\\ \mathrm{.Math.}\\ {\left({}_{i,i_{d-2}}^{\left(r\right)}\right)}^2\end{array}\right).& \left(19\right)\end{array}$ [0140] Proof: It holds that

[00027]$\begin{array}{c}{\left({\stackrel{\_}{X}}^{2^{r+1}}\right)}^i={\left({\left({\stackrel{\_}{X}}^{2^T}\right)}^i\right)}^2\\ ={\left(\underset{f=0}{\overset{2^d-2}{.Math.}}.Math.{}_{i,j}^{\left(r\right)}\left(T\right).Math.{\stackrel{\_}{X}}^j\right)}^2\\ =\underset{\underset{=:S_1}{}}{\underset{j=0}{\overset{2^{d-1}-1}{.Math.}}.Math.{{}_{i,j}^{\left(r\right)}\left(T\right)}^2.Math.{\stackrel{\_}{X}}^{2.Math.j}}+\underset{\underset{=:S_2}{}}{\underset{j=2^{d-1}}{\overset{2^d-2}{.Math.}}.Math.{{}_{i,j}^{\left(r\right)}\left(T\right)}^2.Math.{\stackrel{\_}{X}}^{2.Math.j}}.\end{array}$

From Proposition 5.8, only j's with wt.sub.2(j)=d1 can contribute to .sub.i,k.sup.(r+1) for k With wt.sub.2(k)=d1. In the sum S.sub.1, there is only such j, namely 2.sup.d11. In the sum S.sub.2, the relevant j's are those of the form j=2.sup.d12.sup.j for j {0,1, . . . , d2}, from Definition 5.14, Hence, the partial sum

S.sub.3:=(.sub.i,2.sub.d1.sub.1.sup.(r)).sup.2X.sup.2.sup.d.sup.2+.sub.j=0.sup.d2 (.sub.i,2.sub.d.sub.12.sub.j.sup.(r)).sup.2X.sup.2.sup.d+1.sup.22.sup.j+1

includes all contributions to the .sub.i,k.sup.(r+1) for k with wt.sub.2(k)=d1.

[0141] Now

[00028]$\begin{array}{c}{\stackrel{\_}{X}}^{2^{d+1}-2-2^{j+1}}={\stackrel{\_}{X}}^{2^d}.Math.{\stackrel{\_}{X}}^{2^d-2-2^{j+1}}\\ =\left(\underset{l=0}{\overset{d-1}{.Math.}}.Math.T_l.Math.{\stackrel{\_}{X}}^{2^l}\right).Math.{\stackrel{\_}{X}}^{2^d-2-2^{j+1}}\\ =\underset{l=0}{\overset{d-1}{.Math.}}.Math.T_l.Math.{\stackrel{\_}{X}}^{2^l+2^d-2-2^{j+1}}.\end{array}$

Substitute is S.SUB.3 .to get

[0142]
S.sub.3:=(.sub.i,2.sub.d1.sub.1.sup.(r)).sup.2X.sup.2.sup.d.sup.2+.sub.j=0.sup.d2 (.sub.i,2.sub.d.sub.12.sub.j.sup.(r)).sup.2.sub.l=0.sup.d1 T.sub.lX.sup.2.sup.l.sup.+2.sup.d.sup.22.sup.j+1.

Once again, only those exponents with wt.sub.2(.Math.)=d1 can contribute to .sub.i,k.sup.(r+1) for k with wt.sub.2(k)=d1 and should be kept. For j+1 {1, . . . , d1}, the binary representation of 2.sup.d22.sup.j+1=(2.sup.d1)12.sup.j+1 has exactly two zeros (the coefficients of 2.sup.0 and 2.sup.j+1), and so wt.sub.2(2.sup.l+2.sup.d22.sup.j+1)=d1 iff l {0, j+1}. It follows that all contributions to the .sub.i,k.sup.(r+1) for k with wt.sub.2(k)=d1 appear in

[00029]${\left({}_{i,2^{d-1}-1}^{\left(r\right)}\right)}^2.Math.{\stackrel{\_}{X}}^{2^d-2}+\underset{j=0}{\overset{d-2}{.Math.}}.Math.{\left({}_{i,2^d-1-2^j}^{\left(r\right)}\right)}^2.Math.\left(T_0.Math.{\stackrel{\_}{X}}^{2^d-1-2^{j+1}}+T_{j+1}.Math.{\stackrel{\_}{X}}^{2^d-2}\right)={\stackrel{\_}{X}}^{2^d-2}\left({\left({}_{i,2^{d-1}-1}^{\left(r\right)}\right)}^2+\underset{j=0}{\overset{d-2}{.Math.}}.Math.{\left({}_{i,2^d-1-2^j}^{\left(r\right)}\right)}^2.Math.T_{j+1}\right)+\underset{j=0}{\overset{d-2}{.Math.}}.Math.{T_0\left({}_{i,2^d-1-2^j}^{\left(r\right)}\right)}^2.Math.{\stackrel{\_}{X}}^{2^d-1-2^{j+1}}.$

Recalling that 2.sup.d12.sup.j=i.sub.d1j and using a variable change j.Math.d1j in the last sum, the above expression reads

X.sup.2.sup.d.sup.2((.sub.i,i.sub.0.sup.(r)).sup.2+.sub.j=0.sup.d2(.sub.i,i.sub.d1j.sup.(r)).sup.2T.sub.j+1)+.sub.j=1.sup.d1 T.sub.0(.sub.i,i.sub.j.sup.(r)).sup.2X.sup.I.sup.j1.

This concludes the proof. [0143] Definition 5.19: (The Matrices A.sub.i and .sub.2A). For the matrix A of Lemma 5.18, let A.sub.1 .sub.2[T].sup.dd/2 include the first d/2 columns of A, and let .sub.2A .sub.2[T].sup.d/2d include the last d/2 rows of A. Explicitly,

[00030]$A_1=\left(\begin{array}{ccccccc}{T}_1& 1& T_{d-1}& T_{d-2}& T_{d-3}& \mathrm{.Math.}& T_{d/2+2}\\ 0& 0& T_0& 0& 0& \mathrm{.Math.}& 0\\ 0& 0& 0& T_0& 0& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& 0& 0& 0& \mathrm{.Math.}& T_0\\ 0& 0& 0& 0& 0& \mathrm{.Math.}& 0\\ 0& 0& 0& 0& 0& \mathrm{.Math.}& 0\\ 0& 0& 0& 0& 0& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& 0& 0& 0& \mathrm{.Math.}& 0\\ T_0& 0& 0& 0& 0& \mathrm{.Math.}& 0\end{array}\right){{}_2\left[T\right]}^{dd/2},$

in particular, using 0,1, . . . , to number rows, rows number d/21, . . . , d2 are zero, and

[00031]${}_2.Math.A=T_0\left(\begin{array}{ccccccccc}0& 0& \mathrm{.Math.}& 0& 0& 1& 0& \mathrm{.Math.}& 0\\ 0& 0& \mathrm{.Math.}& 0& 0& 0& 1& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 1\\ 1& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0\end{array}\right){{}_2\left[y\right]}^{d/2d}$ [0144] Definition 5.10 (The operation (.Math.).sup.k). For a matrix M={m.sub.ij} with entries in some ring and for an integer k, let M.sup.k be the matrix obtained by raising each entry of M to the power of k: M.sup.k:={m.sub.ij.sup.k}. [0145] Remark 5.11 Note that for matrices with entries in a ring of characteristic 2, in particular, in .sub.2[T], it holds that for all j , (M.sub.1M.sub.2).sup.2.sup.j=M.sub.1.sup.2.sup.j whenever M.sub.1M.sub.2 is defined. This fact will be used without farther mention below. Note also that in the case of characteristic 2, det(M.sup.2)=det(M).sup.2 for a square matrix M. [0146] Lemma 5.22 It holds that

[00032]$\begin{array}{cc}{0}_{}=\left(\begin{array}{c}{I}_{d/2}\\ 0_{d/2d/2}\end{array}\right)& \left(20\right)\end{array}$

and for r1,

.sub.r=A.Math.A.sup.2.Math.A.sup.4 . . . A.sup.2.sup.r2.Math.A.sub.1.sup.2.sup.r1, (21)

a total of r multiplied matrices. Consequently.

.sub.r=.sub.2A.Math.A.sup.2.Math.A.sup.4 . . . A.sup.2.sup.r2.Math.A.sub.1.sup.2.sup.r1. (22) [0147] Remark 5.23 For clarity, EQ. (21) is expressed explicitly for the cases where r2<1, that is, for r3:.sub.1=A.sub.1, .sub.2=A.Math.A.sub.1.sup.2, .sub.3=A.Math.A.sup.2.Math.A.sub.1.sup.4. [0148] Proof of Lemma 5.23: EQ. (20) follows directly from the definition of .sub.r, and then EQ. (24) follows from Lemma 5.18 by induction. Finally, EQ. (22) follows from EQ. (21) and the definition of .sub.r as the last d/2 rows of .sub.r.

[0149] It can now be proven that det(.sub.r) is not the zero polynomial. [0150] Lemma 5.24: For even d4 and rd/2, det(.sub.r) .sub.2[T] is a non-zero polynomial of total

[00033]$\mathrm{degree}\frac{d}{2}.Math.\left(2^r-1\right)$ [0151] Proof. First, it will be proven by induction on r that det(.sub.r) is not the zero polynomial. For the basis, consider the case r=d/2. Note that B:=A(1,0, . . . , 0) represents the cyclic shift left operator. Hence, if d/23,

N:=B.sup.2 . . . B.sup.2.sup.d/22=B.sup.d/22

represents the cyclic shift left by d/22 operator. Therefore,

N:=N.Math.A.sub.1(1,0, . . . , 0).sup.2.sup.d/21=N.Math.A.sub.1(1,0, . . . , 0)

is given by

[00034]$N^{}=\left(\begin{array}{ccccc}0& 0& \mathrm{.Math.}& 0& 1\\ 0& 0& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& 0& 0\\ 0& 0& \mathrm{.Math.}& 0& 0\\ 1& 0& \mathrm{.Math.}& 0& 0\\ 0& 1& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& 1& 0\end{array}\right).$

It follows that .sub.d/2(1,0, . . . , 0)=.sub.2 A(1,0, . . . , 0)N=I.sub.d/2, and

(det(.sub.d/2)) (1,0, . . . , 0)=1. (23)

For d/2=2, where .sub.d/2=.sub.2A.Math.A.sub.1.sup.2, it can be verified directly that .sub.d/2(1,0, . . . , 0)=I.sub.d/2, so that EQ. (23) holds also for this case. This shows that det(.sub.d/2) 0 .sub.2[T] and establishes the induction basis.

[0152] For the induction step, assume that rd/2+1 and the assertion is true for r1. Write .sub.2A:=.sub.2 A/T.sub.0 .sub.2.sup.d/2d, and note that .sub.2A=(.sub.2A).sup.2. When by EQ. (22),

[00035]$\begin{array}{cc}\begin{array}{c}\det .Math.\left(r_{}\right)=.Math.T_0^{d/2}.Math.\det \left({{(}_2.Math.A^{})}^2.Math.A^2.Math..Math.\mathrm{.Math.}.Math..Math.A^{2^{r-2}}.Math.A_1^{2^{r-1}}\right)\\ =.Math.T_0^{d/2}({\det \left({(}_2.Math.\left(A^{}\right).Math.A.Math..Math.\mathrm{.Math.}.Math..Math.A^{2^{r-3}}.Math.A_1^{2^{r-2}})\right)}^2.\end{array}& \left(24\right)\end{array}$

Now, using 0,1, . . . to index rows:

[00036]${(}_2.Math.A^{}).Math.A=\left(\begin{array}{c}{\mathrm{row}}_{d/2+1}\left(A\right)\\ {\mathrm{row}}_{d/2+2}\left(A\right)\\ \mathrm{.Math.}\\ {\mathrm{row}}_{d-1}\left(A\right)\\ {\mathrm{row}}_0\left(A\right)\end{array}\right).$

Cyclically shifting the rows results in the matrix

[00037]$\begin{array}{cc}\left(\begin{array}{ccccccccccc}{T}_1& 1& T_{d-1}& \mathrm{.Math.}& T_{d/2+2}& T_{d/2+1}& T_{d/2}& T_{d/2-1}& \mathrm{.Math.}& T_3& T_2\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& T_0& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& T_0& 0\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& T_0\\ T_0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& 0\end{array}\right){{}_2\left[T\right]}^{d/2d}.& \left(25\right)\end{array}$

Write .sub.3A for the matrix in EQ. (25), and let

.sub.r:=.sub.3 A.Math.A.sup.2.Math.A.sup.2.sup.2 . . . A.sup.2.sup.r2.Math.A.sub.1.sup.2.sup.r2.

It follows from EQ. (24) that det(.sub.r) 0 iff det(.sub.r) 0. By the .sub.2[T]-linearity of the determinant in the first row, it is shown that

[00038]$\det \left(r_{}\right)=T_{d/2}.Math.\det \left[\left(\begin{array}{ccccccccccc}0& 0& 0& \mathrm{.Math.}& 0& 0& 1& 0& \mathrm{.Math.}& 0& 0\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& T_0& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& T_0& 0\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& T_0\\ T_0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& 0\end{array}\right).Math.A^2.Math..Math.\mathrm{.Math.}.Math..Math.A^{2^{r-3}}.Math.A_1^{2^{r-2}}\right]+\det \left[\left(\begin{array}{ccccccccccc}{T}_1& 1& T_{d-1}& \mathrm{.Math.}& T_{d/2+2}& T_{d/2+1}& 0& T_{d/2-1}& \mathrm{.Math.}& T_3& T_2\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& T_0& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& T_0& 0\\ 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& T_0\\ T_0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& \mathrm{.Math.}& 0& 0\end{array}\right).Math.A^2.Math..Math.\mathrm{.Math.}.Math..Math.A^{2^{r-3}}.Math.A_1^{2^{r-2}}\right].$

Note that the following fact was used: for rows r.sub.0, r.sub.0, r.sub.1, r.sub.2, . . . and for a matrix. M,

[00039]$\det \left(\left(\begin{array}{c}{r}_0+r_0^{}\\ r_1\\ r_2\\ \mathrm{.Math.}\end{array}\right).Math.M\right)=\det \left(\left(\begin{array}{c}{r}_0.Math.M+r_0^{}.Math.M\\ r_1.Math.M\\ r_2.Math.M\\ \mathrm{.Math.}\end{array}\right)\right)=\det \left(\left(\begin{array}{c}{r}_0\\ r_1\\ r_2\\ \mathrm{.Math.}\end{array}\right).Math.M\right)+\det \left(\left(\begin{array}{c}{r}_0^{}\\ r_1\\ r_2\\ \mathrm{.Math.}\end{array}\right).Math.M\right).$

[0153] Note also that the first determinant in the above sum equals det(.sub.r1)/T.sub.0, and is therefore non-zero by the induction hypothesis. In addition, the first summand (T.sub.d/2.Math.det( . . . )) is the only one in which T.sub.d/2 may appear in an odd degree, and as the first determinant is non-zero and T.sub.d/2 appears in all its monomials in an even degree, the first summand must contain monomials whose T.sub.d/2-degree is odd. As such monomials cannot be canceled by monomials in the second determinant, whose T.sub.d/2-degree is essentially even, it can be concluded that det(.sub.r) 0, so that det(.sub.r) 0. This completes the proof that det(.sub.r) 0 for all rd/2.

[0154] As for the assertion regarding the total degree, note first that combining EQ. (22), the fact that all polynomials in A are either 1 or some T.sub.j, and the additivity of the total degree, it can be seen that the total degree of each entry in .sub.r is at most 1+2+ . . . +2.sup.r1=2.sup.r1. As the determinant of a d/2d/2 matrix is a sum of products of d/2 entries, it follows that tot. deg(.sub.r)(d/2) (2.sup.r1), as required.

[0155] Theorem 5.11 can now be proven. [0156] Proof of Theorem 5.11: Take some x.sub.0, . . . , x.sub.d1 .sub.q.sub.2. The condition that the x.sub.i are .sub.2-linearly independent can be expressed as g(x.sub.0, . . . , x.sub.d1) 0 for

g(X.sub.0, . . . , X.sub.d1):=(X.sub.0+X.sub.1) (X.sub.0+X.sub.2) . . . (X.sub.d2+X.sub.d1) . . .(X.sub.0+ . . . +X.sub.d1),

a product of 2.sup.dd1 linear polynomials. In addition, assuming that x.sub.0, . . . , x.sub.d1 are , .sub.2-linearly independent and writing U for the subspace that they span, the coefficients a.sub.0, . . . , a.sub.d1 of f.sub.U=.sub.xU (X+x)=X.sup.2.sup.d+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X are obtained by substituting (x.sub.0, . . . , x.sub.d1) in polynomials of total degrees2.sup.d2.sup.j for j=0,1, . . . , d1, respectively, in .sub.2[X.sub.0, . . . , X.sub.d1]. Substituting these polynomials from .sub.2[X.sub.0, . . . , X.sub.d1] for the T.sub.i in det(.sub.r) with r=log.sub.2(q), results in a polynomial h .sub.2[X.sub.0, . . . , X.sub.d1] of total degree at most

[00040]$\begin{array}{cc}\left(2^d-1\right).Math.\mathrm{tot}.\mathrm{deg}\left(\det \left(r_{}\right)\right)\left(2^d-1\right).Math.\frac{d}{2}.Math.\left(q-1\right),& \left(26\right)\end{array}$

where EQ. (26) follows from Lemma 5.24 and the fact that for a field K, a polynomial u K[Y.sub.0, . . . , Y.sub.n.sub.1.sub.1] and polynomials v.sub.0, . . . , v.sub.n.sub.1.sub.1 K[Z.sub.0, . . . , Z.sub.n.sub.1.sub.1],

tot. deg(u(v.sub.0, . . . , v.sub.n.sub.1.sub.1))tot. deg(u).Math.max{tot. deg(v.sub.i)}.sub.i.

To see the validity of the previous equation, take a monomial Y.sub.0.sup.i.sup.0 . . . Y.sub.n.sub.1.sub.1.sup.i.sup.n11 appearing in u, then by definition, i.sub.jtot. deg(u). Substituting the v.sub.j for the Y.sub.j and using tot. deg(fg)=tot. deg(f)+tot. deg(g), it is clear that the total degree after substitution is not greater than i.sub.0.Math.tot. deg(v.sub.0)+ . . . +i.sub.n.sub.1.sub.1.Math.tot. deg(v.sub.n.sub.1.sub.1)(i.sub.j)max{tot. deg(v.sub.i)}.

[0157] Write X:=(X.sub.0, . . . , X.sub.d1). According to an embodiment, it should be shown that (gh) (X) has a non-zero in .sub.q.sub.2.sup.d. This will be accomplished with the Schwartz-Zippel lemma, which states that if f K[Y.sub.0, . . . , Y.sub.m1] is non-zero and has total degree (where K is some field, m , and ), and if S .Math. K is a finite set, then the number of (y.sub.0, . . . , y.sub.m1) S.sup.m for which f (y.sub.0, . . . , y.sub.m1)=0 is at most .Math.|S|.sup.m1. However, it first needs to be shown that gh 0. Since g(X) is obviously non-zero, it only needs to be shown that h(X) 0. If h(X) is the zero polynomial in .sub.2[X], then for any extension field K of .sub.2 and for any d-dimensional .sub.2-subspace U of K , the result of substituting the .sub.i coming from .sub.xU (Xx)=X.sup.2.sup.d+a.sub.d1X.sup.2.sup.d1+ . . . +a.sub.0X for the T.sub.i in det(.sub.r) is 0 K. Suppose that |K|=Q where Q2.sup.d is some power of 2. Noting that distinct subspaces result in distinct vectors (a.sub.0, . . . , a.sub.d1), this means that the non-zero polynomial det(.sub.r) has at least

[00041]$N_1:=\frac{\left(Q-1\right).Math.\left(Q-2\right).Math.\left(Q-4\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(Q-2^{d-1}\right)}{\left(2^d-1\right).Math.\left(2^d-2\right).Math.\left(2^d-4\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(2^d-2^{d-1}\right)}$

zeroes. However, since .sub.r 0 and tot. deg(det(.sub.r))d/2) (q1), it follows from the Schwartz-Zippel lemma that the number of zeros of det(.sub.r) in K.sup.d is at most Q.sup.d1(d/2)(q1), which is in O(Q.sup.d1) for fixed d and q. As N.sub.1=O(Q.sup.d), a contradiction is obtained for large enough Q. This shows, that h(X) 0.

[0158] As gh .sub.2[X] is a non-zero polynomial and

[00042]$\mathrm{tot}.\mathrm{deg}\left(\mathrm{gh}\right)=\mathrm{tot}.\mathrm{deg}\left(g\right)+\mathrm{tot}.\mathrm{deg}\left(h\right)\left(1+\frac{d}{2}.Math.\left(q-1\right)\right).Math.\left(2^d-1\right)-d,$

it follows from the Schwartz-Zippel lemma that the probability that a randomly drawn point (x.sub.0, . . . , x.sub.d1) from (.sub.q.sub.2).sup.d is a non-zero of gh is at least

[00043]$p:=1-\frac{\left(1+\frac{d}{2}.Math.\left(q-1\right)\right).Math.\left(2^d-1\right)-d}{q^2-1}.$

For fixed d, p>0 if

[00044]$L\left(q\right):=\left(\frac{1}{q-1}+\frac{d}{2}\right).Math.\left(2^d-1\right)<q+1:=R\left(q\right).$

Note that since L is monotonically decreasing with q while R is monotonically increasing with q, if L(2.sup.r)<R(2.sup.r) for some r, then the same is true for all rr.

[0159] Now, for even d4 and r=log.sub.2(d2.sup.d1), it follows that

[00045]$\begin{array}{c}L\left(2^r\right)=.Math.\left(\frac{1}{d.Math..Math.2^{d-1}-1}+\frac{d}{2}\right).Math.\left(2^d-1\right)\\ <.Math.\left(\frac{1}{d.Math..Math.2^{d-1}-1}+\frac{d}{2}\right).Math.2^d\\ =.Math.\frac{2}{d-\frac{1}{2^{d-1}}}+d.Math..Math.2^{d-1}\\ .Math.1+d.Math..Math.2^{d-1}\\ =.Math.R\left(2^r\right),\end{array}$

as required.
6. The Case d=4 and Additional Examples

[0160] For d=4, it follows that l.sub.0=11, and the only integers j2.sup.d2=14 with wt.sub.2(j)=d1=3 are j=7, 11, 13, 14, of which only 7 is <l.sub.0. Hence, by definition

[00046]$\begin{array}{cc}.Math.r_{}=\left(\begin{array}{cc}{}_{14,11}^{\left(r\right)}& {}_{7,11}^{\left(r\right)}\\ {}_{14,13}^{\left(r\right)}& {}_{7,13}^{\left(r\right)}\end{array}\right),.Math..Math.\mathrm{and}.Math..Math.\det \left(r_{}\right)={}_{14,11}^{\left(r\right)}.Math.{}_{7,13}^{\left(r\right)}+{}_{7,11}^{\left(r\right)}.Math.{}_{14,13}^{\left(r\right)}.Math.\stackrel{\mathrm{(*})}{=}.Math.a_0\left({\left({}_{7,13}^{\left(r\right)}\right)}^3+{{}_{7,11}^{\left(r\right)}\left({}_{7,14}^{\left(r\right)}\right)}^2\right),& \left(27\right)\end{array}$

recalling that a.sub.0 0 is the free coefficient of f.sub.U/X, where (*) follows from Lemma 5.18 by noting that by definition, .sub.2i,j.sup.(r)=.sub.i,j.sup.(r+1), as (X.sup.2.sup.r).sup.2i=(X.sup.2.sup.r+1).sup.i. In the following examples, the simplified notation .sub.j will be used for .sub.7,j.sup.(r). With this notation, it follows from EQ. (27) that det({tilde over (M)}.sub.r) 0 iff .sub.13.sup.3+.sub.11.sub.14.sup.2 . By Proposition 5.16, this is a sufficient condition for a simple repair scheme for the [16,12].sub.2.sub.2r Reed-Solomon code defined on the subspace U. [0161] Example 6.1 Consider the .sub.2-linearized polynomial f(X):=X.sup.16+X.sup.4+X .sub.2[X]. It can be verified by direct substitution that this polynomial splits in .sub.2.sub.6. Hence, for q=2.sup.3=8, the set U of roots of f in .sub.q.sub.2 is an .sub.2-subspace. It can also be verified directly that

(X.sup.8).sup.7=X.sup.2+X.sup.8+X.sup.11+X.sup.14,

so that with the above notation, .sub.13=0, .sub.11 0, and .sub.14 0, and it follows that .sub.13.sup.3+.sub.11.sub.14.sup.2 0. Hence, Condition (**) holds, and the [16,12].sub. Reed-Solomon code defined on U has a simple repair scheme. [0162] Example 6.2 Consider the case q=2.sup.r with r=4, represent .sub.q.sub.2=.sub.2.sub.8 s as .sub.2[X]/(X.sup.8+X.sup.4+X.sup.3+X.sup.2+1), and let be the image of X. It can be verified that is a primitive element of .sub.2.sub.8. Consider the .sub.2-subspace U spanned by {1, , .sup.2, .sup.3} and the Reed-Solomon code C defined on U. Using any computer algebra software, it can be verified that .sub.11=.sup.249, .sub.13=.sup.171, .sub.14=.sup.176, and .sub.11.sub.14.sup.2+.sub.13.sup.3.sup.431 0. Hence, C has a simple repair scheme. Note that an alterative way to see this is to calculate the dimensions involved in Condition (**) directly, say, by Gaussian elimination.

[0163] C can be shortened to obtain a [14, shortened Reed-Solomon code. For this shortened code, repairing any single erased coordinate requires reading ,a total of only 13.Math.4=52 bits from the remaining coordinates. Note that in the best existing repairing scheme for the [14, Facebook FUNS code, repairing a single erased coordinate requires reading a total of 64 or 60 bits, depending on the erased coordinate, from the non-erased coordinates. [0164] Example 6.3 The cases of q=2.sup.r with r {5,6,7} can be considered in a similar way. The following table presents for each r {5,6,7} the minimal polynomial of a primitive element of .sub.2.sub.2r, as well as the relevant coefficients from the above discussion. In all cases, U is the .sub.2-subspace spanned by {1, , .sup.2, .sup.3}. It can be seen that .sub.11.sub.14.sup.2+.sub.13.sup.3 0 in all cases, and hence the Reed-Solomon code defined on U has a simple repair scheme,

TABLE-US-00001 minimal polynomial .sub.11.sub.14.sup.2 + r of .sub.11 .sub.13 .sub.14 .sub.13.sup.3 parameters 5 X.sup.10 + X.sup.3 + 1 .sup.699 .sup.872 .sup.583 .sup.431 [16, 6 X.sup.12 + X.sup.6 + .sup.2119 .sup.2676 .sup.1516 .sup.2855 [16, X.sup.4 + X + 1 7 X.sup.14 + X.sup.10 + .sup.12908 .sup.9078 .sup.15325 .sup.11665 [16, X.sup.6 + X + 1 [0165] Example 6.4 This example considers the case of dimension d=6. Let q=2.sup.4, so that q.sup.2=2.sup.8, and let U be .sub.2-subspace spanned by 1, , . . , .sup.5, where a is as in Example 6.2. Then it can be verified by direct Gaussian elimination that Condition (**) holds for l=l.sub.0=55. This gives a [64, Reed-Solomon code with a simple .sub.2.sub.4-linear repair scheme.

7.Extensions of Degree>2

[0166] While the proofs given in the previous sections consider only the case of extensions .sub.2.sub.2r/.sub.2.sub.r of degree 2, some concrete examples below show that it is also possible to work with extensions .sub.2.sub.mr/.sub.2.sub.r of degree m>2. In such a case. .sub.2-subspaces U .Math. .sub.2.sub.2r of degree d divisible by m are considered. As demonstrated in examples below, it is possible in many cases to choose a subspace U as above such that an RS code of dimension k with evaluation set U has a simple .sub.2.sub.r-linear repair scheme, as long as

[00047]$k{2}^d-2^{d-\frac{d}{m}}.$

Recall that in such a case, if a single coordinate is erased, then each of the non-erased cc ordinates has to transmit only 1/m of its content to reconstruct the erased coordinate. [0167] Example 7.1. Let the field .sub.2.sub.12 be represented as .sub.2[X]/X.sup.12+X.sup.6+X.sup.4+X+1), and let be the image of X. Then it can be verified that is a primitive element. Let U .Math. .sub.2.sub.12 be the .sub.2-span of {1, , . . . , .sup.7}. Then d:=dim(U)=8. Consider the subfield .sub.2.sub.3 of .sub.2.sub.12, with m:=[.sub.2.sub.12:.sub.23]=4. Then it can be verified by Gaussian elimination that Condition (**) holds for the RS code of dimension

[00048]$k:=2^d-2^{d-\frac{d}{m}}=192$

defined on U. This gives a [256,192].sub.2 12 RS code with a simple .sub.2.sub.3-linear repair scheme. If a single coordiante is erased, then each non-erased coordinate has to transmit only3 bits, that is, of its content, for repairing the erased coordinate. [0168] Example 7.2, For the field .sub.2.sub.12 represented as in the previous example, consider the subfield .sub.2.sub.4, for which m:=[.sub.2.sub.12:.sub.2.sub.4]=3. Let U .sub.2.sub.12 be the .sub.2-span of {1, , . . . , .sup.5}, with d:=dim(U)=6. Then it can be verified by Gaussian elimination that Condition (**) holds for the RS code of dimension

[00049]$k:=2^d-2^{d-\frac{d}{m}}=48$

defined on U. This gives a [64, RS code with a simple .sub.2.sub.4-linear repair scheme. If a single coordiante is erased, then each non-erased coordinate has to transmit only 4 bits, that is, of its content, for repairing the erased coordinate. [0169] Example 7.3. Let the field .sub.2.sub.0 be represented as .sub.2[X]/(X.sup.9+X.sup.4+1), and let a he the image of X. Then it can be verified that is a primitive element. Let U .sub.2.sub.9 be the .sub.2-span of {1, , . . . , .sup.5}. Then d:=dim(U)=6. Consider the subfield .sub.2.sub.3 of .sub.2.sub.9, with extension degree m=3. Then it can be verified by Gaussian elimination that Condition (**) holds for the RS code of dimension

[00050]$k:=2^d-2^{d-\frac{d}{m}}=48$

defined on U. This gives a [64, RS code with a simple .sub.2.sub.3-linear repair scheme. If a single coordinate is erased, then each non-erased coordinate has to transmit only 3 bits, that is, of its content, for repairing the erased coordinate.

8. Low-Bandwidth Repair Algorithm For Reed-Solomon (RS) Codes

[0170] A repair algorithm according n an embodiment of the disclosure includes two parts: an offline pre-processing part, and an online part. In the offline part, the various blocks used by the online part are prepared, In the online part, data is encoded using the RS code constructed in the offline part, and erasures are decoded if necessary.

[0171] If there is a single erasure, then, using the blocks constructed in the of part, the single erased coordinate can, be corrected with a low repair bandwidth, in that only a small, part of the content of the non-erased coordinates is transmitted to reconstruct the erased coordinate, where small part will be defined below.

[0172] If there are two or more erasures, then standard erasure-decoding techniques for RS codes are used, and there is no gain in repair bandwidth. However, since single erasures are much more common in practice than multiple erasures, there is it in supporting low-bandwidth repairs for the case of a single erasure.

[0173] In what follows, for a field E to be defined below, 1:=(1, . . . , 1) E.sup.n1 is the vector of n1 ones, 0:=(0, . . . , 0) E.sup.n1 is the vector of n1 zeros, and (.Math.).sup.T stands for vector and matrix transposition. In addition, for a field L, a subset I .Math. L, and a positive integer k|l|, the RS code with evaluation set I and dimension k is defined as the set of length-|l| vectors in L.sup.|l| obtained by evaluating all polynomials f L[X] of degree up to k1 on the points of I. Explicitly, letting I={x.sub.1, . . . , x.sub.n}, with n:=|I|, then the above RS code can be defined as

{(f(x.sub.1), . . . , f(x.sub.n))|f L[X], deg(f)k1{.

In addition, a stripe according to an embodiment can have up to

[00051]$k:=2^d-2^{d-\frac{d}{m}}$

symbols of information, and

[00052]$2^{d-\frac{d}{m}}$

symbols of parity, where d, m are as defined above. For example, when d=4 and m=2, there can be up to 12 symbols of information, and 4 symbols of parity.

Offline Part

[0174] The inputs of an offline part of an algorithm according to an embodiment are as follows, [0175] Integers r1, m2 defining finite fields F:=F.sub.2.sub.r .Math. F.sub.2.sub.mr=:E. Note that as an F-vector space, E is isomorphic to F.sup.m. [0176] A primitive element F.sub.2.sub.r=F and its minimal polynomial p.sub.1(X) F.sub.2[X] over F.sub.2, so that deg(p.sub.1(X))=r. Let F:=F.sub.2[X]/(p.sub.1(X)), Note that FF, as these are two isomorphic copies of F.sub.2.sub.r. In addition let be the image of the polynomial X in F:=F.sub.2[X]/(p.sub.1(X)), that is :=X+(p.sub.1(X)). [0177] A primitive element F.sub.2.sub.r=E and its minimal polynomial p.sub.2(X) F.sub.28 X] over F.sub.2, so that deg(p.sub.2(X))=mr. [0178] A positive integer dmr, the dimension over F.sub.2, divisible by m. The length n constructed codes according to embodiments is then n:=2.sup.d, and their maximum possible dimension is

[00053]$k:=2^d-2^{d-\frac{d}{m}},$ [0179] i.e., can have up to k symbols of information, and

[00054]$2^{d-\frac{d}{m}}$ [0180] symbols of parity, where d, m are as defined above. For example, when d=4 and m=2, there can be up to 12 symbols of information, and 4 symbols of parity.

[0181] Note that lengths 2.sup.d1<n.sub.0<2.sup.d can be obtained by shortening For simplicity, embodiments will only consider the case of n.sub.0=n=2.sup.d.

[0182] The outputs of an offline part of an algorithm according to an embodiment are as follows. [0183] An F.sub.2-vector subspace V .Math. E with dim.sub.F.sub.2 (V)=d, that is, with |V|=2.sup.d=n, which will be the evaluation set for the constructed RS code. According to an embodiment, V is given by stating its n elements, which will be enumerated for convenience as follows: V={0=u.sub.0, u.sub.1, . . . , u.sub.n1}, where the u.sub.j are elements of E. [0184] A vector of projections v E.sup.n1 whose n1 entries will be used by the n1 non-erased coordinates in the reconstruction process of a single erased coordinate. [0185] A gluing matrix A (F).sup.m(n1) that will be used for gluing individual transmissions from the n1 non-erased coordinates. [0186] An embedding matrix M.sub.1 F.sub.2.sup.mrr. [0187] An inverse embedding matrix M F.sub.2.sup.rmr. [0188] A particular basis B.sub.F/E={x.sub.1, . . . , x.sub.m} .Math. E for E as an F-vector space. This particular basis will be used in the final step of reconstructing a single erased coordinate. [0189] A matrix G.sub.1 F.sup.kx(nk) used for systematic encoding

[0190] With the inputs and outputs defined as above, an offline part of an, algorithm according to an embodiment is as follows, with reference to the steps of the flowchart of FIGS. 1A-B. The flowchart starts on FIG. 1A. [0191] Step 101: For i=0, . . . , d1, let b.sub.i:=.sup.i, and let B.sub.V/F.sub.2:={b.sub.0, . . . b.sub.d1}. [0192] Alternatively, according to other embodiments, B.sub.V/F.sub.2 can be a random set of F.sub.2-independent elements in E. Such a random set, may be obtained by successively drawing d elements, until the d drawn elements are indeed linearly independent. [0193] Step 102: Let V={u.sub.0=0, u.sub.n1} E be the F.sub.2-subspace spanned by B.sub.V/F.sub.2. [0194] Note that |V|=n, for n=2.sup.d. According to an embodiment, if the binary expansion of i {0, . . . , 2.sup.d1} is (i.sub.0, i.sub.1, . . . , i.sub.d1) {0,1}.sup.d, so that i=.sub.=0.sup.d1 i.sub.2.sup., then u.sub.i:=.sub.=0.sup.d1 i.sub.b.sub. [0195] Step 104: For i=1, . . . , n1, set v.sub.i:=1/u.sub.i and output v:=(v.sub.1, . . . , v.sub.n1) [0196] Step 105: Define the following matrices G E.sup.kn, H, G E.sup.(k1)(n1), and H E.sup.k(n1), [0197] where:

[00055]$G:=\left(\begin{array}{cccc}1& 1& \mathrm{.Math.}& 1\\ 0& u_1& \mathrm{.Math.}& u_{n-1}\\ 0& u_1^2& \mathrm{.Math.}& u_{n-1}^2\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& u_1^{k-1}& \mathrm{.Math.}& u_{n-1}^{k-1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 0^T& G^{}\end{array}\right),.Math.\left(\mathrm{this}.Math..Math.\mathrm{defines}.Math..Math.\mathrm{both}.Math..Math.G.Math..Math.\mathrm{and}.Math..Math.G^{}\right),.Math.H^{}:=G^{}.Math.\left(\begin{array}{ccc}{v}_1& & \\ & & \\ & & v_{n-1}\end{array}\right),.Math.\mathrm{and}.Math..Math.H^{}:=\left(\begin{array}{c}v\\ H^{}\end{array}\right).$ [0198] Step 106: Calculate dim.sub.F(C) and dim.sub.F(C), where C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix H, and C:={c F.sup.n1|Hc.sup.T=0}, the F-subfield subcode of the code with parity-check matrix H. According to embodiments, these two dimensions can be found, e.g., by Gaussian elimination. According to an embodiment, dim.sub.F(C) can be calculated as follows: first, replace each entry of H by a the length-m column vector of coefficients according to some basis of E/F. This results in an [m(k1)](n1) matrix with entries in F. After performing Gaussian elimination to this last matrix, let a be the number of non-zero rows. Then dim.sub.F(C)=n1a. [0199] Step 107: Check if :=dim.sub.F(C)dim.sub.F(C)=m. If =m, then continue to the next step. [0200] Otherwise, in which case essentially <m, then let B.sub.V/F.sub.2 be a new random set of F.sub.2-independent elements in E, drawn independently from any previous drawing, and return. to Step 102. [0201] Step 108: Output the vector space V. [0202] The flowchart continues on FIG. 1B. [0203] Step 109: Find m linearly independent vectors c.sub.1, . . . , c.sub.m F.sup.n1 that complete a basis, of C to be a basis of C. According to an embodiment, this can be done as follows. [0204] (1) Let F.sup.dim.sup.F.sup.(C)(n1) be a generator matrix for C of the form =(l|.sub.1), where the identity matrix appears in columns j.sub.1, . . . , j.sub.dim.sub.F.sub.(C). [0205] (2) Let F.sup.dim.sup.F.sup.(C)(n1) be some generator matrix for C, and let .sub.1 F.sup.dim.sup.F.sup.(C)dim.sup.F.sup.(C) be the matrix comprising the columns of with indices j.sub.1, . . . , j.sub.dim.sub.F.sub.(C), where the rows of .sub.1 are the coefficients of the rows of with respect to the basis for the larger code C. [0206] (3) After performing Gaussian elimination to , let j.sub.1, . . . , j.sub.dim.sub.F.sub.(C) {1, . . . , dim.sub.F(C)} be column indices for an identity matrix appearing in the resulting matrix. [0207] (4) Let c.sub.1, . . . , c.sub.m be the rows of with indices not in {j.sub.1, . . . , j.sub.dim.sub.F.sub.(C)}. [0208] Step 110: Let A F.sup.m(n1) be a matrix with rows c.sub.1, . . . , c.sub.m. [0209] At this stage, according to an embodiment, the m elements of the vector y=(y.sub.1, . . . , y.sub.m).sup.T:=Av.sup.T E.sup.m are linearly independent over F, and hence constitute a basis for E over F. An offline part of an algorithm according to an embodiment continues as follows.

[0210] Step 111: Let B.sub.F/E={x.sub.1, . . . , x.sub.m} E be the dual basis of {y.sub.1, . . . , y.sub.m} with respect to the trace map E.fwdarw.F, and output B.sub.F/E. The trace tap Tr:E.fwdarw.F, defined above in Def. 2.1, can equivalently be defined by u.sub.i=0.sup.m1 u.sup.|f|.sup.i. For a basis {y.sub.1, . . . , y.sub.m} of E/F, the dual basis is the set {x.sub.1, . . . , x.sub.m} satisfying

[00056]$\mathrm{Tr}\left(x_i.Math.y_j\right)=\{\begin{array}{cc}1& \mathrm{if}.Math..Math.i=j\\ 0& \mathrm{if}.Math..Math.ij\end{array}.Math..Math.\mathrm{for}.Math..Math.\mathrm{all}.Math..Math.i,j.$ [0211] Step 112: Let M.sub.1 F.sub.2.sup.mrr be the matrix whose j-th column, j=0, . . . , r1, is the length-mr binary representation of .sup.j according to the basis {1, , . . . , .sup.mr1} of E over F.sub.2. Output M.sub.1. [0212] Step 113: Find a matrix T F.sub.2.sup.mrmr such that the rr identity matrix appears in TM.sub.1. [0213] According to an embodiment, such a matrix can be found by, e.g., Gaussian elimination. Let M F.sub.2.sup.rmr be r rows of T with indices supporting an rr identity matrix in TM.sub.1. Output M. [0214] Step 114: Let each entry of the matrix A from step 110 be a column vector in F.sub.2.sup.mr according to the basis {1, , . . . , .sup.mr1} of E over F.sub.2, and let A (F).sup.m(n1) be the matrix obtained by replacing each entry a.sub.ij of A by Ma.sub.ij, where this last column vector in F.sub.2.sup.r is the representation of an element of F according to the basis {1, , . . . , ().sup.r1} of F over F.sub.2. Output A.