XOR's, Lower Bounds and MDS Codes for Storage

James S. Plank.

May, 2011.

Technical Report UT-CS-11-672
EECS Department
University of Tennessee
Knoxville, TN 37996

This paper is appearing in the 2011 Information Theroy Workshop,, Paraty, Brazil. Please see this link for citation information and PDF of that paper.

PDF of the paper.


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.

Citation Information