# US 2014/0152476 A1 · Data encoding methods, data decoding methods, data reconstruction methods, data encoding devices, data decoding devices, and data reconstruction devices

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0152476 A1
- Document ID: US20140152476A1
- Status: Published application
- Kind: A1
- Application number: 13/809,823
- Filed: 2010-12-08
- Published: 2014-06-05
- Earliest claimed: 2010-12-08
- Assignees: Nanyang Technological University
- Inventors: Frederique Oggier; Anwitaman Datta
- Web page: https://patentgrep.com/patent/US20140152476A1

## CPC

- H03M 13/47: Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
- 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}
- 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}
- H03M 13/1515: {Reed-Solomon codes}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## 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

### Claim 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.

### Claim 2 (depends on 1)

The data encoding method of claim 1, further comprising:
dividing the data to be encoded into a plurality of encoding blocks.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

The data encoding method of claim 3,
wherein each coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

### Claim 5 (depends on 2)

The data encoding method of claim 2,
wherein each block of the plurality of blocks is used in one coefficient of the polynomial.

### Claim 6 (depends on 2)

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.

### Claim 7 (depends on 6)

The data encoding method of claim 6,
wherein each encoding block of the plurality of encoding blocks is an element of the finite field.

### Claim 8 (depends on 1)

The data encoding method of claim 1,
wherein the polynomial is a polynomial p of the form
p

(
X
)
=
∑
i
=
0
k
-
1

p
i

X
2
i
,
wherein k is a positive integer, and pi is an element of a finite field with a number of elements corresponding to a power of 2.

### Claim 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.

### Claim 10 (depends on 9)

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.

### Claim 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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 11)

The data reconstruction method of claim 11, further comprising:
determining a generator of a multiplicative group.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 14)

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.

### Claim 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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 18)

The data encoding device of claim 18,
wherein each coefficient of the polynomial corresponds to an encoding block of the plurality of encoding blocks.

### Claim 20 (depends on 17)

The data encoding device of claim 17,
wherein each block of the plurality of blocks is used in one coefficient of the polynomial.

### Claim 21 (depends on 17)

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.

### Claim 22 (depends on 21)

The data encoding device of claim 21,
wherein each encoding block of the plurality of encoding blocks is an element of the finite field.

### Claim 23 (depends on 16)

The data encoding device of claim 16,
wherein the polynomial is a polynomial p of the form
p

(
X
)
=
∑
i
=
0
k
-
1

p
i

X
2
i
,
wherein k is a positive integer, and pi is an element of a finite field with a number of elements corresponding to a power of 2.

### Claim 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.

### Claim 25 (depends on 24)

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.

### Claim 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.

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 26)

The data reconstruction device of claim 26, further comprising:
a generator determining circuit configured to determine a generator of a multiplicative group.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 29)

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.