Method and apparatus for reconstructing a data block

• US 10,644,726 B2
• Filed: 10/06/2014
• Issued: 05/05/2020
• Est. Priority Date: 10/18/2013
• Status: Active Grant

• Current Assignee: Centre National De La Recherche Scientifique, Universite De Nantes
• Original Assignee: Universite De Nantes
• Inventors: David, Sylvain, Evenou, Pierre, Guedon, Jean-Pierre, Normand, Nicolas, Parrein, Benoit
• Primary Examiner(s): Nguyen, Steve N
• Application Number:
  US15/030,338
• Publication Number:
  US 20160254826A1
• Time in Patent Office: 2,038 Days
• CPC Class Codes: H03M 13/2942 wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables

Abstract

A method for reconstructing a data block of size N is proposed. The data block was encoded using an erasure code to generate a set of N_s systematic symbol vectors and a set of N_p parity projection vectors from a mapping of the data block onto a two-dimensional convex support. The method comprises: for each input vector that contains at least an erasure, updating the value of each erased symbol to a predetermined value; mapping the N_s input vectors with updated values onto the two-dimensional convex support, generating a reconstruction projection vector from the mapping of the N_s input vectors with updated values onto the two-dimensional convex support using an encoding projection direction; and generating an updated parity projection vector from the reconstruction projection vector and the parity projection vector generated using said encoding projection direction.

Claims

1. A computer-implemented method for data storage and retrieval from a network, the method comprising:

reconstructing within a data storage memory a data block of size N, wherein the data block was encoded using an erasure code to generate a set of N_s systematic symbol vectors and a set of N_p parity projection vectors from a mapping of the data block onto a two-dimensional convex support, wherein the systematic symbol vectors correspond to symbols of the data block mapped onto the support, and the parity projection vectors respectively correspond to N_p projections of symbols of the data block mapped onto the support using respective encoding projection directions, the data block being reconstructed from a set of N_s input vectors using the set of N_p parity projection vectors;

for each input vector that contains at least an erasure, updating the value of each erased symbol to a predetermined value, said update being performed by a processor;

mapping the N_s input vectors with updated values onto the two-dimensional convex support, said mapping being performed by the processor,

generating a reconstruction projection vector from the mapping of the N_s input vectors with updated values onto the two-dimensional convex support using an encoding projection direction, said generation being performed by the processor; and

generating an updated parity projection vector from the reconstruction projection vector and the parity projection vector generated using said encoding projection direction, said generation being performed by the processor;

reconstructing the data block based on the updated parity projection vector and the N_s input vectors, and

retrieving the data block from the data storage memory.

2. The method of claim 1, wherein the predetermined value is zero, and the generating the updated parity projection vector comprises obtaining each value of the updated parity projection vector by subtracting the corresponding value of the reconstruction projection vector from the corresponding value of the parity projection vector generated using said encoding projection direction.

3. The method of claim 1, further comprising:

iteratively back-projecting on the two-dimensional convex support values of the updated parity projection vector, and updating the updated parity projection vector based on the values calculated from the back-projection.

4. The method of claim 1, wherein the N_p projections of symbols of the data block mapped onto the support using respective encoding projection directions are projections of the symbols f(k;

l) of the mapped data block according to respective projection directions vectors of coordinates (p_i,q_j), j(k;

l) being the symbol of the mapped data block in a position (k;

l) of the two-dimensional convex support where the value at position b_n in the projection vector proj_pi(b_n) is such that proj_pi(b_n)=Σ

_k=0Σ

_l=0f(k;

l)·

Δ

(b_n+q_i·

k−

p_i·

l), where k, l, p_i, q_i, b_n are integers, and Δ

(.) is the Kronecker function, that is, the function such that Δ

(0)=1 and Δ

(h)=0 if h≠

0.

5. The method according to claim 1, wherein the two-dimensional convex support is rectangular shaped, of size P×

Q, where P×

Q≥

N, and wherein (P≤

P_Np) or (Q≤

Q_Np), where P_Np and Q_Np are respectively defined as P_Np=Σ

_i=0<sup>Np−

1</sup>|p_i|, and Q_Np=Σ

_i=0<sup>Np−

1</sup>q_i and p_i and q_i are integer coordinates of projection direction vectors.

6. The method according to claim 5, wherein the value at position b_n in the projection vector proj_pi(b_n) is such that proj_pi(b_n)=Σ

_k=0^P-1Σ

_i=0^Q-1(k;

l)·

Δ

(b_n+k−

p_i·

l) and wherein f(k;

l) is the symbol of the mapped data block in a position (k;

l) of the two-dimensional convex support, where k, l, and b_n are integers and Δ

(.) is the Kronecker function, that is, the function such that Δ

(0)=1 and Δ

(h)=0 if h≠

0.

7. An apparatus comprising a processor and a data storage memory operatively coupled to the processor, wherein the apparatus is configured to store data and retrieve data from a network, by reconstructing a data block of size N, wherein the data block was encoded using an erasure code to generate a set of N_s systematic symbol vectors and a set of N_p parity projection vectors from a mapping of the data block onto a two-dimensional convex support, wherein the systematic symbol vectors correspond to symbols of the data block mapped onto the support, and the parity projection vectors respectively correspond to N_p projections of symbols of the data block mapped onto the support using respective encoding projection directions, the data block being reconstructed from a set of N_s input vectors using the set of N_p parity projection vectors, the apparatus being further configured to:

for each input vector that contains at least an erasure, update the value of each erased symbol to a predetermined value;

map the N_s input vectors with updated values onto the two-dimensional convex support,

generate a reconstruction projection vector from the mapping of the N_s input vectors with updated values onto the two-dimensional convex support using an encoding projection direction; and

generate an updated parity projection vector from the reconstruction projection vector and the parity projection vector generated using said encoding projection direction; and

retrieving the data block from the data storage memory.

8. The apparatus according to claim 7, wherein the predetermined value is zero, and the apparatus is further configured to generate the updated parity projection vector by obtaining each value of the updated parity projection vector by subtracting the corresponding value of the reconstruction projection vector from the corresponding value of the parity projection vector generated using said encoding projection direction.

9. The apparatus according to claim 7, wherein the apparatus is further configured to iteratively back-project on the two-dimensional convex support values of the updated parity projection vector, and update the updated parity projection vector based on the values calculated from the back-projection.

10. The apparatus according to claim 7, wherein the N_p projections of symbols of the data block mapped onto the support using respective encoding projection directions are projections of the symbols f(k;

l) of the mapped data block according to respective projection direction vectors of coordinates (p_i,q_i)f(k;

l) being the symbol of the data block in a position (k;

l) of the two-dimensional convex support, where the value at position b_n in the projection vector proj_pi(b_n) is such that proj_pi(b_n)=Σ

_k=0Σ

_l=0f(k;

l)·

Δ

(b_n+q_i·

k−

p_i·

l), where k, l, p_i, q_i, b_n are integers, and Δ

(.) is the Kronecker function, that is, the function such that Δ

(0)=1 and Δ

(h)=0 if h≠

0.

11. The apparatus according to claim 7, wherein the two-dimensional convex support is rectangular shaped, of size P×

Q, where P×

Q≥

N, and wherein (P≥

Σ

_i=0<sup>Np−

1</sup>) or (Q≤

Σ

_i=0<sup>Np−

1</sup>q_i) where p_i and q_i are integer coordinates of projection direction vectors (p_i, q_i), p_i and q_i are integers.

12. The apparatus according to claim 7, wherein the value at position b_n of the projection vector proj_pi(b_n) is such that proj_pi(b_n)=Σ

_k=0^P-1Σ

_l=0^Q-1f(k;

l)·

Δ

(b_n+k−

p_i−

l) and wherein f(k;

l) is the symbol of the mapped data block in a position (k;

l) of the two-dimensional convex support and where p_i is integer coordinates of projection direction vectors (p₁,1), where b_n is the position in the projection vector proj_pi(b_n), where k, l, p_i, and b_n are integers and Δ

(.) is the Kronecker function, that is, the function such that Δ

(0)=1 and Δ

(h)=0 if h≠

0.

13. A non-transitory computer-readable storage medium storing a computer program for storing and retrieving data from a data storage memory that, when executed, causes an apparatus comprising a processor operatively coupled with a memory, to perform a method for reconstructing a data block of size N, wherein the data block was encoded using an erasure code to generate a set of N_s systematic symbol vectors and a set of N_p parity projection vectors from a mapping of the data block onto a two-dimensional convex support, wherein the systematic symbol vectors correspond to symbols of the data block mapped onto the support, and the parity projection vectors respectively correspond to N_p projections of symbols of the data block mapped onto the support using respective encoding projection directions, the data block being reconstructed from a set of N_s input vectors using the set of N_p parity projection vectors, the method comprising:

for each input vector that contains at least an erasure, updating the value of each erased symbol to a predetermined value;

mapping the N_s input vectors with updated values onto the two-dimensional convex support,

generating a reconstruction projection vector from the mapping of the N_s input vectors with updated values onto the two-dimensional convex support using an encoding projection direction;

generating an updated parity projection vector from the reconstruction projection vector and the parity projection vector generated using said encoding projection direction, and

retrieving the data block from the data storage memory.