1 |
-------- Erasure codes based on Vandermonde matrices --------- |
2 |
-------- (C) 1996-1998 Luigi Rizzo (luigi@iet.unipi.it) --------- |
3 |
|
4 |
See fec.c for other contributors. |
5 |
|
6 |
fec.c contains an implementation of an encoder/decoder for an erasure |
7 |
code based on Vandermonde matrices computed over GF(2^m), m=2..16 |
8 |
|
9 |
PRINCIPLE OF OPERATION |
10 |
|
11 |
The encoded data is computer as |
12 |
|
13 |
y = E x |
14 |
|
15 |
where x is a k-vector with source data, y is an n-vector with the |
16 |
redundant info, and E is an n*k matrix derived from a Vandermonde |
17 |
matrix. The code is systematic. |
18 |
|
19 |
At the receiver, any subset y' of k elements from y allows the |
20 |
reconstruction of the whole x by solving the system |
21 |
|
22 |
y' = E' x |
23 |
|
24 |
where E' is made of rows from E corresponding to the received |
25 |
elements. |
26 |
|
27 |
The complexity of matrix inversion is O(k*l^2) where l is the number |
28 |
of elements not in x available at the receiver. This might seem |
29 |
large, but data elements are in fact be packets of large size, so |
30 |
the inversion cost can be amortized over the size of the packet. |
31 |
For practical applications (k and l as large as 30, packet sizes |
32 |
of 1KB) the cost can be neglected. |
33 |
|
34 |
In addition, each of the l lost data packets has a reconstruction |
35 |
cost O(k), (obviously) similar to the cost of the encoding phase. |
36 |
Being the code systematic, you can express encoding and decoding costs |
37 |
roughly as |
38 |
|
39 |
Encoding speed: (c_e/l) MB/s |
40 |
Decoding speed: (c_d/l) MB/s |
41 |
|
42 |
|
43 |
PERFORMANCE |
44 |
|
45 |
The values of c_d and c_e (similar) are very sensitive to issues |
46 |
such as cache hit rate, memory speed, field size (8 or 16 bits), |
47 |
etc. Also some machines are better than others in working with |
48 |
bytes or 16-bit words. With the June'98 implementation I have |
49 |
measured the following values for c_e and c_d (8-bit version; 16-bit |
50 |
version has a penalty between 3 and 4). |
51 |
|
52 |
Hardware C version Optimized version(*) |
53 |
|
54 |
PentiumII 266 62 33 |
55 |
PentiumPRO 200 56 30 |
56 |
Pentium133 14.5 18 |
57 |
486dx2/66 4.05 4.55 |
58 |
|
59 |
(*) The 'optimized' version has some manual optimizations of the assembly |
60 |
code generated by the compiler. It is generally faster for machines |
61 |
with a single instruction pipeline, and generally slower for |
62 |
machines with multiple pipelines. |
63 |
|
64 |
See the manpage for detailed usage information. |
65 |
|