Encoding device for error correction, encoding method for error correction and encoding program for error correction

• US 8,365,052 B2
• Filed: 04/03/2012
• Issued: 01/29/2013
• Est. Priority Date: 09/12/2006
• Status: Active Grant

• Current Assignee: Tamagawa K-12 & University
• Original Assignee: Tamagawa K-12 & University
• Inventors: Hamada, Mitsuru
• Primary Examiner(s): BRITT, CYNTHIA H
• Application Number:
  US13/438,564
• Publication Number:
  US 20120192040A1
• Time in Patent Office: 301 Days
• Field of Search: 714/746, 714/755, 714/781, 714/786
• US Class Current: 714/781
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/63 Joint error correction and other techniques H03M13/31 and H03M13/33 take precedence
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece

Abstract

The present invention aims at providing an encoding device for error correction, encoding method for error correction and encoding program for error correction wherein countermeasures against eavesdropping are taken into account. To achieve this, in accordance with an aspect of the present invention there is provided an encoding device for error correction, the device comprises a generation means for generating randomly a vector u=(x_k+1, . . . , x_m) composed of m-k digit(s); a creation means for creating an x′=[xu]=(x₁, . . . , x_m) by concatenating the vector u=(x_k+1, . . . , x_m) composed of m-k digit(s) randomly created by the creation means to data x=(x₁, . . . , _k) to send; and an output means for outputting a vector of length n by carrying out [n, m] encoding of the x′ created by the creation means.

Claims

1. An encoding device for error correction, said device comprising:

a first encoding means for encoding data to send into the following vector of length N′

by [[N′

, K′

]] encoding designated by an M′

×

N′

generator matrix F on Galois field GF(q),

y=(y₁⁽¹⁾, . . . , y_k1⁽¹⁾, y₁⁽²⁾, . . . , y_k2⁽²⁾, . . . , y₁^(N), . . . , y_kN^(N));

a second encoding means for encoding, for i=1, . . . , N,

(y₁⁽ⁱ⁾, . . . , y_ki⁽ⁱ⁾)

into the following vector of length n_i by [[N′

, K′

]] encoding designated by a generator matrix G_i,

w⁽ⁱ⁾=(w₁⁽ⁱ⁾, . . . , w_ni⁽ⁱ⁾);

and

an output means for outputting [w⁽¹⁾ . . . w^(N)] obtained by concatenating w⁽¹⁾, . . . , w^(N) as an encoded result.

2. The encoding device for error correction according to claim 1, wherein said device further comprises a second output means for outputting information that is outputted from said output means after encrypting with a function g expressing any encrypting system.

3. An encoding method for error correction, said method comprising the steps of:

(a) encoding data to send into a following vector of length N′

by [[N′

, K′

]] encoding designated by an M′

×

N′

generator matrix F on Galois field GF(q),

y=(y₁⁽¹⁾, . . . , y_k1⁽¹⁾, y₁⁽²⁾, . . . , y_k2⁽²⁾, . . . , y₁^(N), . . . , y_kN^(N));

(b) encoding, for i=1, . . . , N,

(y₁⁽ⁱ⁾, . . . , y_ki⁽ⁱ⁾)

into the following vector of length by [[n_i, k_i]] encoding designated by a generator matrix G_i,

w⁽ⁱ⁾=(w₁⁽ⁱ⁾, . . . , w_ni⁽ⁱ⁾); and

(c) outputting [w⁽¹⁾ . . . w^(N)] obtained by concatenating w⁽¹⁾, . . . , w^(N) as an encoded result.

4. The method for error correction encoding according to claim 3, wherein said method further comprises the steps of:

(d) outputting information that is outputted from step (c) after encrypting with a function g expressing any encrypting system.

5. A non-transitory machine-readable storage medium having an encoding program for error correction stored thereon executable by a computer, said program comprising the steps of:

(a) encoding data to send into a following vector of length N′

by [[N′

, K′

]] encoding designated by an M′

×

N′

generator matrix F on Galois field GF(q),

y=(y₁⁽¹⁾, . . . , y_k1⁽¹⁾, y₁⁽²⁾, . . . , y_k2⁽²⁾, . . . , y₁^(N), . . . , y_kN^(N));

(b) encoding, for i=1, . . . , N,

(y₁⁽ⁱ⁾, . . . , y_ki⁽ⁱ⁾)

into the following vector of length n_i by [[n_i, k_i]] encoding designated by a generator matrix G_i

w⁽ⁱ⁾=(w₁⁽ⁱ⁾, . . . , w_ni⁽ⁱ⁾); and

(c) outputting [w⁽¹⁾ . . . w^(N)] obtained by concatenating w⁽¹⁾, . . . , w^(N) as an encoded result.

6. A non-transitory machine-readable storage medium having a program for error correction encoding stored thereon that is executable by a computer, said program comprising the steps of:

(a) encoding data to send into the following vector of length N′

by [[N′

, K′

]] encoding designated by an M′

×

N′

generator matrix F on Galois field GF(q),

y=(y₁⁽¹⁾, . . . , y_k1⁽¹⁾, y₁⁽²⁾, . . . , y_k2⁽²⁾, . . . , y₁^(N), . . . , y_kN^(N));

(b) encoding, for i=1, . . . , N,

(y₁⁽ⁱ⁾, . . . , y_ki⁽ⁱ⁾)

into the following vector of length n_i by [[n_i, k_i]] encoding designated by a generator matrix G_i

w⁽ⁱ⁾=(w₁⁽ⁱ⁾, . . . , w_ni⁽ⁱ⁾);

(c) outputting [w⁽¹⁾ . . . w^(N)] obtained by concatenating w⁽¹⁾, . . . , w^(N) as an encoded result; and

(d) outputting information that is outputted from step (c) after encrypting with a function g expressing any encrypting system.