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