README
1This program uses Forward Error Correction (FEC) based on Vandermonde (VDM)
2matrices to recover lost blocks of files. Its primary application is
3intended to be in recovering data from unreliable media such as diskettes.
4(Note that you must write the data to the diskette using this program
5in the first place in order to be able to recover the data!)
6
7To install, configure and make install. Three programs are copied into
8$bindir:
9 vdmfec
10 vdm_encode
11 vdm_decode
12these files are all hard links to each other, the latter being equivalent
13to calling 'vdmfec -d'.
14
15CFLAGS and LDFLAGS default to -O3 and -s, resp. For debugging you might
16want to 'configure CFLAGS="-O2 -g" LDFLAGS=""'.
17
18The Notes file gives the file format.
19
20VDMFEC is based on the Vandermonde FEC C code written by Luigi Rizzo.
21The home page for fec.c is http://www.iet.unipi.it/~luigi/fec.html
22
23The files README.fec, fec.3, fec.c, fec.h, and fec_ccr.ps.gz are from
24Rizzo's 980624 distribution, sans assembly code, and with a few changes
25to make for better autoconfiguration. The vdmfec code will only work
26with GF_BITS=8 (because the block id is stored as a byte).
27
README.fec
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