EVENODD code

EVENODD code[1]

Description

Binary array code \(\mathcal{EO}_2(m)\) with independent horizontal and diagonal parity columns, designed to retain optimal double-erasure protection while simplifying small updates [2].

Protection

Corrects any two erased columns whenever \(m\) is prime, and has minimum column distance three in that case [2].

Decoding

Efficient decoding algorithm against two erasures [1].

Realizations

Can be implemented on standard RAID-5 controllers without extra finite-field hardware [2].

Cousin

B-code— EVENODD avoids the recursive parity updates of \(\mathcal{B}_2(m)\) while retaining optimal two-erasure correction [2].

Member of code lists

Primary Hierarchy

Classical Domain

Matrix Kingdom

Matrix-based codeECC

Array codeDistributed-storage ECC

Generalized EVENODD code

Parents

Generalized EVENODD code

Generalized EVENODD codes reduce to EVENODD codes for \(r=2\) [2].

MDS array codeArray Distributed-storage ECC

EVENODD codes are examples of MDS array codes [3].

EVENODD code

References

[1]: M. Blaum, J. Brady, J. Bruck, and Jai Menon, “EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures”, IEEE Transactions on Computers 44, 192 (1995) DOI
[2]: M. Blaum, P. G. Farrell, and H. C. A. van Tilborg, “Array codes,” in Handbook of Coding Theory, Vol. II, Part 3, eds. V. S. Pless and W. C. Huffman (Elsevier, 1998), pp. 1855-1909
[3]: I. Tamo, Z. Wang, and J. Bruck, “Zigzag Codes: MDS Array Codes With Optimal Rebuilding”, IEEE Transactions on Information Theory 59, 1597 (2013) arXiv:1112.0371 DOI

Page edit log

Victor V. Albert (2024-08-19) — most recent

Cite as:

“EVENODD code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/evenodd

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/array/evenodd/evenodd.yml.