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
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BLAieeetit96
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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||04 Nov 2007|
|Last Modified:||26 Dec 2012 09:46|
Repository Staff Only: item control page