| 1 |
root |
1.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 |
|
|
|
