XOR's, Lower Bounds and MDS Codes for Storage

James S. Plank, EECS Department, University of Tennessee.

Appearing in IEEE Information Theory Workshop (ITW) Paraty, Brazil, October, 2011.

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:

.inproceedings	p:11:xlb
author		J. S. Plank
title		{XOR's}, Lower Bounds and {MDS} Codes for Storage
booktitle	IEEE Information Theory Workshop (ITW)
month           October
year            2011
address		Paraty, Brazil
where		http://web.eecs.utk.edu/~jplank/plank/papers/ITW-2011.html

Bibtex:

@INPROCEEDINGS{p:11:xlb,
	author = "J. S. Plank",
	title = "{XOR's}, Lower Bounds and {MDS} Codes for Storage",
	booktitle = "IEEE Information Theory Workshop (ITW)",
	month = "October",
	year = "2011",
	address = "Paraty, Brazil",
	where = "http://web.eecs.utk.edu/~jplank/plank/papers/ITW-2011.html"
}