US 7,398,456 B2 · Information encoding by shortened Reed-Solomon codes

Abstract

The present invention concerns an encoding method in which encoding is performed of any information word a of length k in the form of a word ν belonging to a Reed-Solomon code C of dimension k′ and length n′ (with n′−k′=n−k) such that the components of ν′ situated in (n′−n) arbitrary predetermined positions be systematically equal to respective predetermined constants (for example, all zero). The possibility then exists of deleting those components of fixed value to obtain a word ν of length n belonging to a code C, which thus constitutes a code that is shortened with respect to code C. The invention also relates to devices and apparatuses adapted to implement the encoding method. The invention may be used for encoding by means of an algebraic geometric code, when such encoding may be implemented by encoding by means of a plurality of shortened Reed-Solomon codes.

Claims18

Dependent claims

A method of encoding over a Galois field Fq, where q is an integer greater than 2 and equal to a power of a prime number, in which a word v′=(v′0,v′1, . . . , v′n′−1) is calculated, where n′≧3, belonging to an MDS linear cyclic code C′ of dimension (n′−m), where 1≦m≦n′−2, on the basis of a word a=(a0, a1, . . . , an−m−1) of information symbols, where m<n<n′, in which a set s=(s0,s1, . . . , sn−1) of strictly increasing integers, with s0≧0 and sn−1≦n′−1, having been predetermined, the method comprising the steps of:

a) forming the polynomial
a
⁡
(
x
)
≡
∑
i
=
m
n
-
1
⁢
a
i
-
m
⁢
x
s
i
,
b) calculating the remainder r(x) of the Euclidean division of a(x) by the polynomial
g
⁡
(
x
)
≡
∑
p
=
0
m
⁢
g
p
⁢
x
p
generating said code C′,
c) calculating the polynomial
v
*
⁡
(
x
)
=
a
⁡
(
x
)
-
r
⁡
(
x
)
≡
∑
i
=
0
n
′
-
1
⁢
v
i
*
⁢
x
i
,
corresponding to the word v*=(v*0, v*1, . . . , v*n′−1), and
d) taking v′=v* if sm−1=m−1;
otherwise obtaining said word v′ by taking:
v
_
′
=
v
*
+
∑
j
=
0
s
m
-
m
-
1
⁢
f
j
⁢
Γ
_
j
(
1
)
in which the words Γj of length n′ are defined by:
Γji=gi−j for j≦i≦j+m, and Γji=0 otherwise, and in which the elements fj of Fq are calculated by means of the equations (1) in which, for the (sm−m) values of i<sm not belonging to the set s, each component v′i;
is taken equal to a respective predetermined constant.

109 more elements

A device (102) for encoding over a Galois field Fq, where q is an integer greater than 2 and equal to a power of a prime number, in which a word v′=(v′0, v′1, . . . , vn′−1) is calculated, where n′≧3, belonging to an “MDS” linear cyclic code C′ of dimension (n′−m), where 1≦m≦n′−2, on the basis of a word a=(a0, a1, . . . , an−m−1) of information symbols, where m<n<n′, characterized in that, a set s=(s0,s1, . . . , sn−1) of strictly increasing integers, with s0≧0 and sn−1≦n′−1, having been predetermined, it is adapted to:

a) form the polynomial
a
⁡
(
x
)
≡
∑
i
=
m
n
-
1
⁢
a
i
-
m
⁢
x
s
i
,
b) calculate the remainder r(x) of the Euclidean division of a(x) by the polynomial
g
⁡
(
x
)
≡
∑
p
=
0
m
⁢
g
p
⁢
x
p
generating said code C′,
c) calculate the polynomial
v
*
⁡
(
x
)
=
a
⁡
(
x
)
-
r
⁡
(
x
)
≡
∑
i
=
0
n
′
-
1
⁢
v
i
*
⁢
x
i
,
corresponding to the word v*=(v*0, v*1, . . . , v*n′−1), and
d) take v′=v* if sm−i=m−1;
otherwise to obtain said word v′ by taking:
⁢
v
_
′
=
v
_
*
+
∑
j
=
0
s
m
-
m
-
1
⁢
f
j
⁢
Γ
_
j
,
(
1
)
in which the words Γj of length n′ are defined by:
Γji=gi−j for j≦i≦j+m, and Γji=0 otherwise, and in which the elements fj of Fq are calculated by means of the equations (1) in which, for the (sm−m) values of i<sm not belonging to the set s, each component v′i is taken equal to a respective predetermined constant.

111 more elements

Dependencies are inferred from the claim text.

Information encoding by shortened Reed-Solomon codes

Life of this patent

Information encoding by shortened Reed-Solomon codes

Life of this patent

Abstract

Claims18