Error correcting code
A system for protecting a codeword u against an error in at least one <7-ary symbol, where q is an r th power of two, r>1 (q=2 r ). The code word u includes information symbols u[0] . . . u[k−1] , k>1 , each information symbol representing an integer in the range {0 . . . 2w−1}, where w=n*r, n≧1. A processor includes an integer processing unit for, under control of a program, calculating a parity symbol u[k] for protecting the information symbols, where the parity symbol includes −(a[0]·u[0]+a[1] ·u[1]+. . . +a[k−1]•u[k−1]) mod M, where the multiplication · and the addition + are integer operations. The constants a[0] . . . a[£−1] lie in {0 . . . M−1}, M>1 and are chosen such that the elements a[i]*d*q i mod M are unique for iε{0, . . . ,k−1}, jε{0 . . . n−1}, −q<d<q, d≠0.
1. A method of generating an error correcting code for correcting at least one q-ary symbol, where q is an r th power of two, r≧1, (q=2 r ); the method includes:
using as the error correcting code a code word u that includes k information symbols u[0], . . . , u[k−1], k≧1 and a parity symbol u[k] for protecting the information symbols (for example, u=(u[0], . . . , u[k−1], u[k])); each information symbol representing an integer in the range {0, . . . 2 w −1}, where w=n*r, n≧1;
including in the parity symbol u[k] a term −(a[0]·u[0]+a[1]·u[1]+ . . . +a[k−1]·u[k−1])mod M, where M≧2n(k+1)(q−1)+1 where the multiplication · and the addition + are integer operations executable by an integer processing unit and where a[0], . . . , a[k−1] are constants in {0, . . . , M−1}; and
choosing the constants a[0], . . . , a[k−1] such that the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . n−1}, −q<d<q, d≠0, where a[k]=1.
2. A method as claimed in claim 1 , including forming a table T for correcting a single error in a q-ary symbol of a received vector x that includes the code word u and an error vector e, where x=u+e=(u[0]+e[0], . . . , u[k−1]+e[k−1], u[k]+e[k]) and the addition + is an integer operation executable by an integer processing unit; the table associating all possible outcomes of a syndrome s(x)=(a[0]·x[0]+a[1]·x[1]+ . . . +a[k−1]·x[k−1]+x[k]) mod M to a respective set (i, j, d) to enable correction of the j-th q-ary symbol in the i-th information symbol x[i] based on the value d.
3. A method as claimed in claim 1 , wherein w>1, including choosing as the modulus M a largest prime number smaller than 2 w .
4. A method as claimed in claim 1 , including choosing the constants a[0], . . . , a[k−1] by randomly selecting values for the constants a[0], . . . , a[k−1] until at least one set of constants has been found for which the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . , n−1}, −q<d<q, d≠0.
5. A method as claimed in claim 4 , including:
choosing an initial upper boundary A=M for each of the constants a[0], . . . , a[k−1];
randomly selecting values for the constants a[0], . . . , a[k−1];
verifying whether the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . , n−1}, −q<d<q, d≠0;
upon a positive outcome of the verification, lowering the boundary A and repeating the selecting and verification, and upon a negative outcome for a predetermined number of successive verifications using for the constants the randomly selected values that gave the last positive outcome of the verification.
6. A method of protecting a codeword u against an error in at least one q-ary symbol, where q is an r th power of two, r≧1 (q=2 r ), the method including:
receiving the code word u including information symbols u[0], . . . , u[k−1], k>1, each information symbol representing an integer in the range {0, . . . , 2 w −1}, where w=n*r, n≧1;
calculating a parity symbol u[k] for protecting the information symbols, where the parity symbol includes −(a[0]·u[0]+a[1]·u[1]+ . . . +a[k−1]·u[k−1]) mod M, where M≧2n(k−1)(q−1)+1 and where the multiplication · and the addition + are integer operations executable by an integer processing unit and where a[0], . . . , a[k−1] are constants in {0, . . . , M−1} chosen such that the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . n−1}, −q<d<q, d≠0, where a[k]=1; and
adding the parity symbol u[k] to the codeword u before transmitting or storing the codeword.
7. A method of correcting a single error in a q-ary symbol of a received vector x that includes a code word u and an error vector e, where x=u+e=(u[0]+e[0], . . . , u[k−1]+e[k−1], u[k]+e[k]) and the addition + is an integer operation executable by an integer processing unit; the code word u including information symbols u[0], . . . , u[k−1], k>1, and a parity symbol u[k] for protecting the information symbols; each information symbol representing an integer in the range {0, . . . , 2 w −1}, where w=n*r, n≧1 and the parity symbol including: −(a[0]·u[0]+a[1]·u[1]+ . . . +a[k−1]·u[k−1]) mod M, where M≧2n(k−1)(q−1)+1, where the multiplication ␣ and the addition + are integer operations executable by an integer processing unit and where a[0], . . . , a[k−1] are constants in {0, . . . , M−1}chosen such that the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . , n−1}, −q<d<q, d≠0, where a[k]=1;
the method including:
calculating a syndrome s(x)=(a[0]·x[0]+a[1]·x[1]+ . . . +a[k−1]·x[k−1]+x[k]) mod M; and
if the outcome of the syndrome is non-zero:
using a table T that associates each possible outcome of the syndrome to a respective set (i, j, d) to determine values of (i, j, d) for the calculated syndrome; and
correcting the j-th q-ary symbol in the i-th information symbol x[i] based on the value d.
8. A system for protecting a codeword u against an error in at least one q-ary symbol, where q is an r th power of two, r≧1 (q=2 r ), the system including:
means for receiving the code word u including information symbols u[0], . . . , u[k−1], k>1, each information symbol representing an integer in the range {0, . . . , 2 w −1}, where w=n*r, n≧1;
a processor including an integer processing unit for, under control of a program, calculating a parity symbol u[k] for protecting the information symbols, where the parity symbol includes −(a[0]·u[0]+a[1]·u[1]+ . . . +a[k−1]·u[k−1]) mod M, where M≧2n(k−1)(q−1)+1, where the multiplication · and the addition + are integer operations and where a[0], . . . , a[k−1] are constants in {0, . . . , M−1}chosen such that the elements a[i]·d·q j mod M are pairwise distinct for iε{0, . . . , k}, jε{0, . . . , n−1}, −q<d<q, d≠0; and
means for adding the parity symbol u[k] to the codeword u before transmitting or storing the codeword.
9. A system as claimed in claim 8 , wherein the system includes:
means for receiving or reading a vector x that includes the code word u and an error vector e, where x=u+e=(u[0]+e[0], . . . , u[k−1]+e[k−1], u[k]+e[k]) and the addition + is an integer operation;
the processor being operative for, under control of a program, correcting a single error in a q-ary symbol of the received vector x by:
calculating a syndrome s(x)=(a[0]·x[0]+a[1]·x[1]+ . . . +a[k−1]·x[k−1]+x[k]) mod M; and
if the outcome of the syndrome is non-zero:
using a table T that associates each possible outcome of the syndrome to a respective set (i, j, d) to retrieve a set of values (i, j, d) for the calculated syndrome; and
correcting the j-th q-ary symbol in the i-th information symbol x[i] based on the value d.
10. A system as claimed in claim 8 , wherein the system includes a memory for storing the code word u where individual memory cells of the memory are physically arranged to store a single q-ary symbol, where q>2.
11. A system as claimed in claim 10 , wherein the memory is of a NAND-flash type.