Efficient implementation of reed-solomon erasure resilient codes in high-rate applications
A high-rate Reed-Solomon erasure resilient codes (ERC) system and method for generating and implementing Reed-Solomon erasure-resilient codes for use in high-rate applications. High-rate applications are applications where the number of coded messages is significantly higher (such as an order of magnitude) than the number of original messages. The Reed-Solomon ERC system uses a scalar vector multiplication and addition technique and a direct inversion technique. The direct inversion technique uses specific generator matrices, including a modified Vandermonde Matrix and a Cauchy Matrix, to directly calculate an inverse of the sub-generator matrix of receiving ERC-coded messages. The scalar vector multiplication and addition technique generates high-rate Reed-Solomon codes and performs scalar vector multiplication and addition on the Galois Field for the Reed-Solomon erasure encoding/decoding operations. In effect, the Reed-Solomon codes are “tuned” for use in the high-rate environment.
1. A method for encoding and decoding original messages in a high-rate erasure resilience coding application having a coded message space that is at least an order of magnitude larger than a number of original messages, the method comprising:
performing high-rate Reed-Solomon erasure resilient code encoding and decoding operations on the original messages using a scalar vector multiplication and addition technique represented by the equation y=y+αx, where x and y are vectors of symbols of a Galois Field, GF(p), and where y is an order of the Galois Field, and where alpha, α, is a scalar number in GF(p), and where y is an update vector and x is a content vector; the scalar vector multiplication and addition technique further comprising:
establishing a logarithm lookup table and an exponential lookup table in advance of the encoding and decoding operations;
calculating a logarithm of alpha, α, using the logarithm lookup table;
calculating a logarithm of an element of the content vector, x i ;
testing whether the element of the content vector, x i , is equal to zero;
for zero x i ; performing nothing;
for non-zero x i , calculating an exponential of a sum of log(α) and a logarithm of the element of the content vector, x i , using the exponential lookup table to generate an intermediate result;
generating an updated element of the update vector, y i , by adding on the Galois Field the intermediate result to a current element of the update vector, y i to obtain scalar vector multiplication and addition results; and
using the scalar vector multiplication and addition results to encode the original messages and decode encoded messages to recover the original messages.
2. The method of claim 1 , wherein the Galois Field is GF(2 q ).
3. The method of claim 2 , wherein the adding on the Galois Field is a bitwise xor operation.
4. The method of claim 1 , further comprising testing whether the scalar number, α, is equal to zero.
5. The method of claim 4 , further comprising:
determining that the scalar number, α, is equal to zero; and
taking no further action for the current element.
6. The method of claim 1 , further comprising using a generator matrix that is a Vandermonde matrix.
7. The method of claim 1 , further comprising using a generator matrix that is a Cauchy matrix.
8. A computer-implemented process for using high-rate Reed-Solomon erasure resilient codes in a Galois field to perform encoding and decoding of k number of original messages in a high-rate erasure resilience coding application, wherein high-rate means that a number of coded message space is at least an order of magnitude larger than a the k number of original messages, comprising:
using a generator matrix, G, to encode the original messages and decode encoded messages to recover the original messages, the generator matrix, G, being a modified Vandermonde matrix given by:
G
=
[
0
0
0
1
⋯
0
k
1
0
1
1
⋯
1
k
⋮
⋮
⋰
⋮
(
n
-
1
)
0
(
n
-
1
)
1
⋯
(
n
-
1
)
k
]
;
generating an encoded message, c i , which is indexed as i, using the equation:
c
i
=
[
i
0
i
1
⋯
i
k
-
1
]
[
x
0
x
1
⋮
x
k
-
1
]
;
and
calculating the encoded message, c i , wherein calculating further comprises:
setting an update element, y, to be zero; and
performing k scalar vector multiplication and addition on original messages x 0 , x 1 , . . . , x k−1 , the scalar vector multiplication and addition represented by the equation y=y+αx, where x and y are vectors of symbols of a Galois Field, GF(p), and where p is an order of the Galois Field, and where alpha, α, is a scalar number in GF(p), and where y is an update vector and x is a content vector.
9. The computer-implemented process as set forth in claim 8 , further comprising:
receiving k distinctive coded messages {C′ 0 , c′ 1 , . . . , c′ k−1 }, which are indexed as {t 0 , t 1 , . . . , t k−1 }; and
decoding the original messages by calculating:
[
x
0
x
1
⋮
x
k
-
1
]
=
G
k
-
1
[
c
0
′
c
1
′
⋮
c
k
-
1
′
]
,
where
G
k
=
[
t
0
0
t
0
1
⋯
t
0
k
t
1
0
t
1
1
⋯
t
1
k
⋮
⋮
⋰
⋮
t
k
-
1
0
t
k
-
1
1
⋯
t
k
-
1
k
]
.
10. The computer-implemented process as set forth in claim 9 , wherein G k −1 is calculated using a direct inversion technique:
G
k
-
1
=
QD
-
1
,
where
Q
=
[
q
k
-
1
(
t
0
)
q
k
-
1
(
t
1
)
⋯
q
k
-
1
(
t
k
-
1
)
q
k
-
2
(
t
0
)
q
k
-
2
(
t
1
)
⋯
q
k
-
2
(
t
k
-
1
)
⋮
⋮
⋮
q
0
(
t
0
)
q
0
(
t
1
)
⋯
q
0
(
t
k
-
1
)
]
,
D
-
1
=
[
1
d
0
1
d
1
⋰
1
d
k
-
1
]
,
with
d
i
=
∏
j
≠
i
(
t
j
-
t
i
)
,
and
q
j
(
x
)
=
{
q
j
-
1
(
x
)
x
+
a
j
,
j
>
0
1
,
j
=
0
,
and a j is a coefficient of the polynomial:
f
(
x
)
=
∏
i
=
0
k
-
1
(
x
-
t
i
)
=
∑
j
=
0
k
a
j
x
j
.
11. The computer-implemented process as set forth in claim 10 , further comprising calculating each original message by applying k scalar vector multiplication and addition, with scalar parameter being the calculated coefficient in G k −1 , vectors being the coded messages c′ 0 , C′ 1 , . . . , C′ k−1 .
12. A computer-implemented process for using high-rate Reed-Solomon erasure resilient codes in a Galois field to perform encoding and decoding of k number of original messages in a high-rate erasure resilience coding application, wherein high-rate means that a number of coded message space is at least an order of magnitude larger than a the k number of original messages, the process comprising:
using a generator matrix, G, which is in a Cauchy matrix form of:
G
=
[
I
k
1
k
+
0
1
k
+
1
⋯
1
k
+
(
k
-
1
)
1
(
k
+
1
)
+
0
1
(
k
+
1
)
+
1
⋯
1
(
k
+
1
)
+
(
k
-
1
)
⋮
⋮
⋰
⋮
1
(
n
-
1
)
+
0
1
(
n
-
1
)
+
1
⋯
1
(
n
-
1
)
+
(
k
-
1
)
]
;
wherein I k is an identity matrix:
generating an encoded message, c i , with key i, wherein:
if 0≦i>k, the encoded message is an original message c i =x i ,
if i≧k, the encoded message is a parity message given by the equation:
c
i
=
[
1
i
+
0
1
i
+
1
⋯
1
i
+
(
k
-
1
)
]
[
x
0
x
1
⋮
x
k
-
1
]
;
and
calculating the encoded message, c i , wherein calculating further comprises:
setting an update element, y, equal to zero; and
performing k scalar vector multiplication and addition on original messages x 0 , x 1 , . . . , x k−1 , the scalar vector multiplication and addition represented by the equation y=y+αx, where x and y are vectors of symbols of a Galois Field, GF(p), and where p is an order of the Galois Field, and where alpha, α, is a scalar number in GF(p), and where y is an update vector and x is a content vector.
13. The computer-implemented process of claim 12 , further comprising:
receiving k distinctive coded messages, wherein s messages are parity messages with keys {t 0 , t 1 , . . . , t s−1 } and k−s messages are original messages with keys {r s , r s+1 , . . . , r k−1 }, and keys of remaining non-received original messages are {r 0 , r 1 , . . . , r s−1 }; and
decoding the original messages from the coded messages by calculating:
[
x
0
x
1
⋮
x
k
-
1
]
=
G
k
-
1
[
c
0
′
c
1
′
⋮
c
k
-
1
′
]
,
where
G
k
=
[
I
k
-
s
0
A
B
]
,
where A is a sx(k−s) Cauchy matrix of the form:
A
=
[
1
t
0
+
r
s
1
t
0
+
r
s
+
1
⋯
1
t
0
+
r
k
-
1
1
t
1
+
r
s
1
t
1
+
r
s
+
1
⋯
1
t
1
+
r
k
-
1
⋮
⋮
⋮
1
t
s
-
1
+
r
s
1
t
s
-
1
+
r
s
+
1
⋯
1
t
s
-
1
+
r
k
-
1
]
,
and B is a sxs Cauchy matrix of the form:
B
=
[
1
t
0
+
r
0
1
t
0
+
r
1
⋯
1
t
0
+
r
s
-
1
1
t
1
+
r
0
1
t
1
+
r
1
⋯
1
t
1
+
r
s
-
1
⋮
⋮
⋮
1
t
s
-
1
+
r
0
1
t
s
-
1
+
r
1
⋯
1
t
s
-
1
+
r
s
-
1
]
.
14. The computer-implemented process of claim 13 , further comprising calculating G k −1 using a direct inversion technique, wherein G k −1 is given by the equation:
G
k
-
1
=
[
I
k
-
s
0
0
B
-
1
]
[
I
k
-
s
0
-
A
I
s
]
,
the direct inversion technique further comprising:
calculating a determinant of an arbitrary Cauchy matrix, B, using the equation:
det
(
B
)
=
∏
i
<
j
(
t
i
-
t
j
)
∏
i
<
j
(
r
i
-
r
j
)
∏
i
,
j
=
0
s
-
1
(
t
i
+
r
j
)
,
and
using a cofactor to directly calculate an inverse of the Cauchy matrix as:
B
-
1
=
[
d
i
,
j
]
i
,
j
=
0
,
…
,
s
-
1
,
where
:
d
i
,
j
=
(
-
1
)
i
+
j
e
j
f
i
a
j
b
i
(
t
j
+
r
i
)
,
a
m
=
{
∏
i
<
m
(
t
i
-
t
m
)
}
{
∏
i
<
m
(
t
m
-
t
i
)
}
,
b
m
=
{
∏
i
<
m
(
r
i
-
r
m
)
}
{
∏
i
>
m
(
r
m
-
r
i
)
}
,
e
m
=
∏
i
(
t
m
+
r
i
)
,
f
m
=
∏
i
(
t
i
+
r
m
)
.
15. The computer-implemented process of claim 14 , further comprising calculating each non-received original messages (total s messages) by applying k scalar vector multiplication and addition, with the scalar parameter being a coefficient in matrix −A and B −1 , and vectors being the coded messages c′ 0 , c′ 1 , . . . , c′ k−1 .