CaltechAUTHORS
  A Caltech Library Service

MDS array codes with independent parity symbols

Blaum, Mario and Bruck, Jehoshua and Vardy, Alexander (1996) MDS array codes with independent parity symbols. IEEE Transactions on Information Theory, 42 (2). pp. 529-542. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:BLAieeetit96

[img]
Preview
PDF
See Usage Policy.

1406Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BLAieeetit96

Abstract

A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r ≤ 8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2^m), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols.


Item Type:Article
Additional Information:© Copyright 1996 IEEE. Reprinted with permission. Manuscript received September 20, 1994; revised November 6, 1995. Part of this work was performed while the authors were with IBM Research Division, Almaden Research Center, San Jose, CA. The research of J. Bruck was supported in part by the NSF Young Investigator Award CCR-9457811, by the Sloan Research Fellowship, and by grants from the IBM Almaden Research Center and the AT&T Foundation. The research of A. Vardy was supported in part under Grant N00014-9610129 from the Joint Services Electronics Program. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Whistler, BC, Canada, September 1995, and at the 900th Meeting of the American Mathematical Society, Chicago, IL, March 1995. The authors wish to thank M. Eberhardt for his contribution to Section II of this paper. They are also grateful to the anonymous referees for comments which helped improve the presentation of this paper. A. Vardy wishes to thank Hagit Itzkowitz for her invaluable help.
Subject Keywords:MDS codes, array codes, efficient decoding, efficient information updates, error correction codes
Record Number:CaltechAUTHORS:BLAieeetit96
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BLAieeetit96
Alternative URL:http://dx.doi.org/10.1109/18.485722
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9155
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:04 Nov 2007
Last Modified:26 Dec 2012 09:46

Repository Staff Only: item control page