METHOD FOR DATA RECOVERY

• US 20150095747A1
• Filed: 09/29/2014
• Published: 04/02/2015
• Est. Priority Date: 09/30/2013
• Status: Abandoned Application

• Current Assignee: Alexander Barg, Tamo, Itzhak
• Original Assignee: Alexander Barg, Tamo, Itzhak
• Inventors: Tamo, Itzhak, Barg, Alexander
• Application Number:
  US14/499,349
• Publication Number:
  US 20150095747A1
• Time in Patent Office: Days
• US Class Current: 714/781
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/617 Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials

Abstract

A method for encoding multiple data symbols, the method may include receiving or calculating, by a computerized system, multiple (k) input data symbols; wherein the multiple input data symbols belong to a finite field F of order q; q being a positive integer that may exceed n; mapping the multiple input data symbols, by an injective mapping function, to a set of encoding polynomials; wherein the set of encoding polynomials comprises at least one encoding polynomial; and constructing a plurality (n) of encoded symbols that form multiple (t) recovery sets by evaluating the set of encoding polynomials at points of pairwise disjoint subsets (A₁, . . . , A_t) of the finite field F; wherein each recovery set is associated with one of the pairwise disjoint subsets of the finite field F.

Claims

1. A method for encoding multiple data symbols, the method comprising:

receiving or calculating, by a computerized system, multiple (k) input data symbols;

wherein the multiple input data symbols belong to a finite field F of order q;

q being a positive integer;

mapping the multiple input data symbols, by an injective mapping function, to a set of encoding polynomials;

wherein the set of encoding polynomials comprises at least one encoding polynomial; and

constructing a plurality (n) of encoded symbols that form multiple (t) recovery sets by evaluating the set of encoding polynomials at points of pairwise disjoint subsets (A₁, . . . , A_t) of the finite field F;

wherein each recovery set is associated with one of the pairwise disjoint subsets of the finite field F.

2. The method according to claim 1 wherein the injective mapping maps multiple (k) elements of the finite field F to a product of multiple (t) spaces of polynomials, wherein a dimension of the i'"'"'th space of polynomials does not exceed the size of the i'"'"'th pairwise disjoint subset of the finite field F.

3. The method according to claim 1 wherein the injective mapping maps elements of the finite field F to a direct sum of spaces.

4. The method according to claim 3 wherein x is a variable, wherein index i ranges between 1 and t, wherein an i'"'"'th recovery set of multiple (t) recovery sets has a size n_i, wherein index r does not exceed (n_i−

1), and a space (F[x]) of polynomials that are constant on each of the pairwise disjoint subsets (A₁, . . . , A_t) of the finite field F, wherein a direct sum of spaces of polynomials equals ⊕

_i=0<sup>r−

1</sup>F[x]xⁱ.

5. The method according to claim 1 further comprising reconstructing a failed encoded symbol of a certain recovery set by processing non-failed encoded symbols of the certain recovery set.

6. The method according to claim 1 wherein the processing comprises calculating, for each recovery set of the multiple recovery sets, a recovery set that is responsive to (a) elements that belong to the recovery set, (b) an annihilator polynomial of the recovery set, and (c) a mapped polynomial to which the recovery set is mapped to by an injective mapping function.

7. The method according to claim 6 wherein for every value of i that ranges between 1 and t, the symbols comprising the i'"'"'th recovery set are calculated using the Chinese Remainder Theorem algorithm as follows:

8. The method according to claim 1 wherein at least two recovery sets of the multiple recovery sets differ from each other by size.

9. The method according to claim 1 wherein all recovery sets of the multiple recovery sets have a same size.

10. The method according to claim 1 wherein all recovery sets of the multiple recovery sets have a size that equals r+1, wherein t equals n/(r+1), wherein r exceeds one and is smaller than k.

11. The method according to claim 10 wherein r+1 divides n and r divides k.

12. The method according to claim 10 comprising reconstructing at least two failed encoded symbols by processing non-failed encoded symbols.

13. The method according to claim 10 comprising calculating an encoding polynomial in response to r coefficient polynomials.

14. The method according to claim 13 comprising calculating an i'"'"'th coefficient polynomial

15. The method according to claim 1 wherein the mapping and the constructing comprises multiplying a k-dimensional vector that comprises the multiple input symbols by an encoding matrix G that has k rows and n columns and is formed of elements of the finite field F.

16. The method according to claim 1 wherein the mapping and the constructing comprises multiplying a k-dimensional vector that comprises the multiple input symbols by an encoding matrix G′

that has k rows and n columns, wherein encoding matrix G′

equals a product of a multiplication of matrices A, G and D, wherein matrix G has k rows and n columns and is formed of elements of the finite field, matrix A has k rows and k columns and is an invertible matrix formed of elements of the finite field, and matrix D is a diagonal matrix.

17. The method according to claim 1 wherein each pairwise disjoint subset includes (r+ρ

−

1) elements, wherein there are

18. The method according to claim 1 wherein the injective mapping function is a first mapping function, wherein the recovery sets are first recovery sets;

wherein the set of encoding polynomials is a first set of encoding polynomials, wherein the encoded symbols are first encoded symbols;

wherein the method comprises;

mapping the first encoded symbols, by a second injective mapping function, to a second set of encoding polynomials; and

constructing a plurality (n) of second encoded symbols that form multiple (t) second recovery sets by evaluating the second set of encoding polynomials at points of the pairwise disjoint subsets of the finite field F;

wherein each second recovery set is associated with one of the pairwise disjoint subsets of the finite field F.

19. The method according to claim 1 wherein the injective mapping function is a current mapping function, wherein the recovery sets are current recovery sets;

wherein the set of encoding polynomials is a current set of encoding polynomials, wherein the encoded symbols are current encoded symbols;

wherein t exceeds one;

wherein x is a positive integer that ranges between 1 and (t−

1);

wherein the method comprises repeating for x times the stages of;

mapping the current encoded symbols, by a next injective mapping function, to a next set of encoding polynomials; and

constructing a plurality (n) of next encoded symbols that form multiple (t) next recovery sets by evaluating the next set of encoding polynomials at points of the pairwise disjoint subsets of the finite field F;

wherein each next recovery set is associated with one of the pairwise disjoint subsets of the finite field F.

20. The method according to claim 1, wherein at least two recovery sets comprise content for reconstruction of a same encoded data symbol.

21. A method for encoding multiple data symbols, the method comprising:

receiving or calculating, by a computerized system, multiple (k) input data symbols;

wherein the multiple symbols belongs to a finite field F; and

processing, by the computerized system, the multiple symbols using a Chinese Remainder Theorem algorithm to provide a plurality (n) of encoded symbols that form multiple (t) recovery sets;

wherein each of the recovery set is associated with a pairwise disjoint subset of the finite field F.

22. The method according to claim 21 further comprising reconstructing a failed encoded symbol of a certain recovery set by processing non-failed encoded symbols of the certain recovery set.

23. The method according to claim 21, wherein n does not exceed the number of elements of the finite field F.

24. The method according to claim 21 wherein the processing comprises calculating, for each recovery set of the multiple recovery sets, a recovery set that is responsive to (a) elements that belong to the recovery set, (b) an annihilator polynomial of the recovery set, and (c) a mapped polynomial to which the recovery set is mapped to by an injective mapping function.

25. The method according to claim 24 wherein for every value of i that ranges between 1 and t, an i'"'"'th recovery set is calculated by:

26. The method according to claim 21 wherein at least two recovery sets of the multiple recovery sets differ from each other by size.

27. The method according to claim 21 wherein all recovery sets of the multiple recovery sets have a same size.

28. A method for encoding multiple data symbols that belong to a finite field F, the method comprising:

receiving or calculating, by a computerized system, multiple (k) input data symbols;

wherein the multiple input data symbols belong to a finite field F of order q;

processing the multiple (k) data symbols to provide multiple (n) encoded data symbols that form multiple (t) recovery sets; and

reconstructing a failed encoded symbol of the multiple (n) encoded data symbols;

wherein the reconstructing comprises attempting to reconstruct the failed encoded symbol by utilizing non-failed encoded symbols of at least two recovery sets that are associated with the failed encoded symbol;

wherein the at least two recovery sets belong to the multiple recovery sets.

29. The method according to claim 28 wherein the reconstructing comprises:

performing a first attempt to reconstruct the failed encoded symbol by utilizing non-failed encoded symbols of a first recovery set of the at least two recovery sets;

determining whether the first attempt failed; and

performing a second attempt to reconstruct the failed encoded symbol by utilizing non-failed encoded symbols of a second recovery set of the at least two recovery sets if it is determined that the first attempt failed.

30. The method according to claim 28 wherein a number of recovery sets exceeds two;

wherein the reconstructing comprises;

performing a first attempt to reconstruct the failed encoded symbol by utilizing non-failed encoded symbols of a first recovery set of the at least two recovery sets;

determining whether the first attempt failed; and

performing multiple additional attempts to reconstruct the failed encoded symbol by utilizing non-failed encoded symbols of a multiple other recovery set of the at least two recovery sets if it is determined that the first attempt failed.