EECS Publication
XOR's, Lower Bounds and MDS Codes for Storage
James S. Plank
MDS erasure codes are ubiquitous in storage systems that must tolerate failures. While classic Reed-Solomon codes can provide a general-purpose MDS code for any situation, systems that require high performance rely on special-purpose codes that employ the bitwise exclusive-or (XOR) operation, and may be expressed in terms of a binary generator matrix. There are known lower bounds on the density of the generator matrix; however the number of XOR operations required to encode the generator matrix, while related to the density of the matrix, has not been explored. This paper presents a stunning and counter-intuitive result - that the encoding of k message symbols in an MDS code may require fewer than k-1 XOR operations per coding symbol. The result brings into question the lower bounds on the performance of encoding and decoding MDS erasure codes.
Published 2011-05-13 04:00:00 as ut-cs-11-672 (ID:34)