Irregular MDS Array Codes
Authors:
- 8 July 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (9) , 5304-5314
Abstract
In this paper, we extend the concept of maximum-distance separable (MDS) array codes to a larger class of codes, where the array columns contain a variable number of data and parity symbols and the codewords cannot be arranged, in general, in a regular array structure with equal column length. These new codes, named irregular MDS array codes, find applications in problems of distributed data storage with multiple sources of information generating data at unequal rates. We solve the problem of finding optimal parity symbol allocations that achieve minimum redundancy for a given level of protection against block erasures. We provide a classification of irregular MDS array codes according to the parameters of their parity symbol allocation and we show how regular MDS array codes are a special case of this wider class. We derive necessary and sufficient conditions for such irregular array codes to be MDS and extend the concept of the lowest density generator matrix. Finally, we show how a simple constructive method allows to design irregular lowest density MDS array codes with alphabet size independent of the size of the array columns.Keywords
This publication has 8 references indexed in Scilit:
- Cyclic Lowest Density MDS Array CodesIEEE Transactions on Information Theory, 2009
- Lowest density MDS codes over extension alphabetsIEEE Transactions on Information Theory, 2006
- On lowest density MDS codesIEEE Transactions on Information Theory, 1999
- Low-density MDS codes and factors of complete graphsIEEE Transactions on Information Theory, 1999
- X-code: MDS array codes with optimal encodingIEEE Transactions on Information Theory, 1999
- MDS array codes with independent parity symbolsIEEE Transactions on Information Theory, 1996
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995
- On generator matrices of MDS codes (Corresp.)IEEE Transactions on Information Theory, 1985