EVENODD Coding Scheme

The EVENODD Code introduced by M. Blaum and J. Bruck (IEEE Trans. Comp., Vol. 44, Feb. 95) is an MDS array code which has applications in distributed storage, reliable communication and dynamic load balancing. It achieves optimal redundancy with a much lower computational complexity than Reed-Solomon codes. Unlike Reed-Solomon codes, which require computations over finite fields, the EVENODD code requires only cyclic shifts and parity operations.

The following is an illustration of the EVENODD Coding scheme for the case of a RAIN cluster of four nodes. An image file is encoded into four symbols, each half the size of the original image. Given any 2 symbols, we can reconstruct the original image.

Select two symbols.

Symbol 0
Symbol 1
Decoded Image
Symbol 2
Symbol 3

Note that this can be generalized to a scheme which reconstructs the data from any m symbols out of n symbols.