DATA ENCODING METHODS, DATA DECODING METHODS, DATA RECONSTRUCTION METHODS, DATA ENCODING DEVICES, DATA DECODING DEVICES, AND DATA RECONSTRUCTION DEVICES

• US 20140152476A1
• Filed: 12/08/2010
• Published: 06/05/2014
• Est. Priority Date: 07/14/2010
• Status: Active Grant

• Current Assignee: Nanyang Technology University
• Original Assignee: Nanyang Technology University
• Inventors: Oggier, Frederique, Datta, Anwitaman
• Granted Patent: US 8,928,503 B2
• Time in Patent Office: Days
• US Class Current: 341/94
• 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/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37

Abstract

In an embodiment, a data encoding method may be provided. The data encoding method may include: inputting data to be encoded; determining a polynomial so that an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point, wherein coefficients of the polynomial are determined based on the data to be encoded; and generating a plurality of encoded data items by evaluating the polynomial at a plurality of supporting points.

Claims

1. A data encoding method, comprising:

inputting data to be encoded;

determining a polynomial so that an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point, wherein coefficients of the polynomial are determined based on the data to be encoded; and

generating a plurality of encoded data items by evaluating the polynomial at a plurality of supporting points.

2. The data encoding method of claim 1, further comprising:

dividing the data to be encoded into a plurality of encoding blocks.

3. The data encoding method of claim 2,

wherein at least one coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

4. The data encoding method of claim 3,

wherein each coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

5. The data encoding method of claim 2,

wherein each block of the plurality of blocks is used in one coefficient of the polynomial.

6. The data encoding method of claim 2,

wherein at least one encoding block of the plurality of encoding blocks is an element of a finite field.

7. The data encoding method of claim 6,

wherein each encoding block of the plurality of encoding blocks is an element of the finite field.

8. The data encoding method of claim 1,

wherein the polynomial is a polynomial p of the form

9. A data decoding method, comprising:

inputting a plurality of encoded data items;

determining a polynomial that corresponds to the encoded data items based on a pre-defined similarity criterion so that an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point;

determining coefficients of the polynomial; and

generating decoded data based on the coefficients.

10. The data decoding method of claim 9,

wherein a supporting point is assigned to each of the encoded data items;

wherein the polynomial is determined so that the evaluation of the polynomial at a supporting point assigned to an encoded data item of the plurality of data items corresponds to the encoded data item.

11. A data reconstruction method, comprising:

determining, for an encoded data item that is to be reconstructed, at least two other encoded data items based on a pre-determined polynomial for which an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point; and

reconstructing the encoded data item that is to be reconstructed, based on the determined at least two other encoded data items.

12. The data reconstruction method of claim 11,

wherein a supporting point is assigned to each of the encoded data item that is to be reconstructed and the at least two other encoded data items.

13. The data reconstruction method of claim 11, further comprising:

determining a generator of a multiplicative group.

14. The data reconstruction method of claim 13, further comprising:

for a monomial of a pre-determined degree of the generator, determining a polynomial of the generator with a degree lower than the pre-determined degree of the monomial, so that the polynomial corresponds to the monomial.

15. The data reconstruction method of claim 14,

wherein the at least two other encoded data items are determined based on the determining of the polynomial of the generator.

16. A data encoding device, comprising:

an input circuit configured to input data to be encoded;

a polynomial determining circuit configured to determine a polynomial so that an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point, wherein the coefficients of the polynomial are determined based on the data to be encoded; and

a generating circuit configured to generate a plurality of encoded data items by evaluating the polynomial at a plurality of supporting points.

17. The data encoding device of claim 16, further comprising:

a dividing circuit configured to divide the data to be encoded into a plurality of encoding blocks.

18. The data encoding device of claim 17,

wherein at least one coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

19. The data encoding device of claim 18,

wherein each coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

20. The data encoding device of claim 17,

wherein each block of the plurality of blocks is used in one coefficient of the polynomial.

21. The data encoding device of claim 17,

wherein at least one encoding block of the plurality of encoding blocks is an element of a finite field.

22. The data encoding device of claim 21,

wherein each encoding block of the plurality of encoding blocks is an element of the finite field.

23. The data encoding device of claim 16,

wherein the polynomial is a polynomial p of the form

24. A data decoding device, comprising:

an input circuit configured to input a plurality of encoded data items;

a polynomial determining circuit configured to determine a polynomial that corresponds to the encoded data items based on a pre-defined similarity criterion so that an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point;

a coefficients determining circuit configured to determine coefficients of the polynomial; and

a decoded data generating circuit configured to generate decoded data based on the coefficients.

25. The data decoding device of claim 24,

wherein a supporting point is assigned to each of the encoded data items;

wherein the polynomial determining circuit is further configured to determine the polynomial so that the evaluation of the polynomial at a supporting point assigned to an encoded data item of the plurality of data items corresponds to the encoded data item.

26. A data reconstruction device, comprising:

an encoded data determining circuit configured to determine, for an encoded data item that is to be reconstructed, at least two other encoded data items based on a pre-determined polynomial for which an evaluation of the polynomial at a sum of a first supporting point of the polynomial and a second supporting point of the polynomial corresponds to the sum of an evaluation of the polynomial at the first supporting point and an evaluation of the polynomial at the second supporting point; and

a reconstructing circuit configured to reconstruct the encoded data item that is to be reconstructed, based on the determined at least two other encoded data items.

27. The data reconstruction device of claim 26,

wherein a supporting point is assigned to each of the encoded data item that is to be reconstructed and the at least two other encoded data items.

28. The data reconstruction device of claim 26, further comprising:

a generator determining circuit configured to determine a generator of a multiplicative group.

29. The data reconstruction device of claim 28, further comprising:

a generator polynomial determining circuit configured to, for a monomial of a pre-determined degree of the generator, determine a polynomial of the generator with a degree lower than the pre-determined degree of the monomial, so that the polynomial corresponds to the monomial.

30. The data reconstruction device of claim 29,

wherein the encoded data determining circuit is further configured to determine the at least two other encoded data items based on the determining of the polynomial of the generator.