vdmfec - Block ECC for files
vdmfec [-v] [-d] [-b blocksize] [-n N] [-k K] [file]
vdm_encode [-v] [-b blocksize] [-n N] [-k K] [file]
vdm_decode [-v] [-b blocksize] [-n N] [-k K] [file]
reads an input stream and adds error correction blocks so that
large consecutive sections of the output stream may be corrupted, and the data
recovered. For example, diskettes typically lose whole sectors at once, or
related groups of sectors, or even entire tracks. Data written to a diskette
with this program may be recovered even with many read errors.
The algorithm used is a Forward Error Correction (FEC) code based on Vandermonde
(VDM) matrices in GF(2^8) due to Luigi Rizzo. Given the FEC parameters K and
N, with N greater than K, N blocks are written for every K input blocks in
such a way that any K blocks are sufficient to reconstruct the data. That is,
up to N - K blocks out of every group of N blocks may be lost without loss of
The amount of overhead in the output stream is easily adjustable by varying K. N
and blocksize control the total amount of data written. Depending on the types
of errors you expect, different settings may be more or less useful. For
example, you may not expect to have two or three bad sectors on every track
(if you do it's time to replace the diskette!), but you might expect three bad
sectors on two or three contiguous tracks (diskette errors tend to cluster).
- Print informative messages about the encoding or decoding process to
stderr, including the expansion factor. Use -vv to get
information about each block being read or written.
- Decode the input rather than encoding it. Using this option is equivalent
to invoking the program as vdm_decode.
- -b blocksize
- Set the FEC block size to blocksize bytes. The blocksize may have a 'k' or
'K' appended, in which case the block size is set to blocksize * 1024
bytes. This should usually be a multiple of the output media block or
sector size (e.g., 512, 1024, 18K, etc.), and must be at least 26 bytes in
version 1. Default 1024.
- -n N -k K
- Set the FEC N and K parameters. N must be greater than 2 and less than or
equal to 256. K must be greater than 0 and less than N. Default N=18,
Note that the N, K, and blocksize parameters are NOT written to the output! You
must specify the same
parameters when you run the decoder. (Actually,
the decoder is capable of explicitly detecting an invalid K value, but
incorrect blocksize or N values will result in bad blocks and decode failure.)
The decoder is capable of reading from non-seekable media such as pipes,
however, buffer underruns are not detected and will result in failure. Also,
when reading from a pipe the entire file must be read. Reading from a
seek-able stream can be faster because only K good blocks out of N need to be
The encoder stores chunk and block ids which are used to detect out of order
blocks, but those errors (which can sometimes happen due to filesystem
corruption) are not corrected. The only type of error that can be corrected is
corruption of data. In particular, missing blocks (as from
lost packets) result in decode failure, even when K good blocks are available.
This program is primarily intended to recover data lost due to read errors on
fixed media such as diskettes; several other programs and libraries are
available that use FEC to handle the other (typically network packet) errors.
Consider a diskette with 80 tracks, 2 heads, and 18 512-byte sectors per track
(a standard 1.44MB diskette).
- bzip2 < file | vdmfec > /dev/fd0
uses the default parameters of -b1k -n18 -k14, stores up to ~1.1MB of compressed
input data, written one (double-sided) track (18K) at a time, and allows 4 bad
clusters (8 sectors) per track.
- vdmfec -d /dev/fd0 | bunzip2 > file
recovers the original file.
- vdm_encode -b18k -n80 -k70 file.img > /dev/fd0
writes the entire diskette, stores up to ~1.23MB of data, and allows multiple
errors on 10 different double-sided tracks.
- vdm_decode -b18k -n80 -k70 /dev/fd0 > file.img
recovers the data and reads no less than 70 tracks. Note that vdm_decode exits
with a non-zero status on failure, so that constructions such as
- vdm_decode /dev/fd0 > moo && tar -xvf moo
- dd if=/dev/tape ibs=1024 conv=noerror,sync | \
vdm_decode > file
This might be necessary to recover data from some non-seekable media. You can of
course simply write the encoded output to a normal file, as in
- tar -cf - dir | gzip | vdm_encode -v > dir.tgz.vdm
Report bugs to Tom Holroyd <email@example.com>.