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