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