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.

Abstract

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

Plain Text:

.techreport	p:11:xor
author		J. S. Plank
title		XOR's, Lower Bounds and MDS Codes for Storage
institution     University of Tennessee
month           May
year            2011
number          CS-11-672
where		http://web.eecs.utk.edu/~jplank/plank/papers/CS-11-672.html

Bibtex:

@TECHREPORT{p:11:xor,
	author = "J. S. Plank",
	title = "{XOR's}, Lower Bounds and {MDS} Codes for Storage",
	institution = "University of Tennessee",
	month = "May",
	year = "2011",
	number = "CS-11-672",
	where = "http://web.eecs.utk.edu/~jplank/plank/papers/CS-11-672.html"
}