cedricde / fec-rs-vdm Goto Github PK

--------    Erasure codes based on Vandermonde matrices    ---------
--------  (C) 1996-1998  Luigi Rizzo ([email protected])  ---------

See fec.c for other contributors.

fec.c contains an implementation of an encoder/decoder for an erasure
code based on Vandermonde matrices computed over GF(2^m), m=2..16

PRINCIPLE OF OPERATION

The encoded data is computer as
 
	y = E x

where x is a k-vector with source data, y is an n-vector with the
redundant info, and E is an n*k matrix derived from a Vandermonde
matrix. The code is systematic.

At the receiver, any subset y' of k elements from y allows the
reconstruction of the whole x by solving the system

	y' = E' x

where E' is made of rows from E corresponding to the received
elements.

The complexity of matrix inversion is O(k*l^2) where l is the number
of elements not in x available at the receiver. This might seem
large, but data elements are in fact be packets of large size, so
the inversion cost can be amortized over the size of the packet.
For practical applications (k and l as large as 30, packet sizes
of 1KB) the cost can be neglected.

In addition, each of the l lost data packets has a reconstruction
cost O(k), (obviously) similar to the cost of the encoding phase.
Being the code systematic, you can express encoding and decoding costs
roughly as

    Encoding speed:	(c_e/l) MB/s
    Decoding speed:	(c_d/l) MB/s
	

PERFORMANCE

The values of c_d and c_e (similar) are very sensitive to issues
such as cache hit rate, memory speed, field size (8 or 16 bits),
etc.  Also some machines are better than others in working with
bytes or 16-bit words.  With the June'98 implementation I have
measured the following values for c_e and c_d (8-bit version; 16-bit
version has a penalty between 3 and 4).

    Hardware		C version	Optimized version(*)

    PentiumII 266	62		33
    PentiumPRO 200	56		30
    Pentium133		14.5		18
    486dx2/66		 4.05		 4.55

(*) The 'optimized' version has some manual optimizations of the assembly
    code generated by the compiler. It is generally faster for machines
    with a single instruction pipeline, and generally slower for
    machines with multiple pipelines.

See the manpage for detailed usage information.