New efficient MDS array codes for RAID. Part II. Rabin-like codes for tolerating multiple (/spl ges/ 4) disk failures

摘要

For pt.1 see ibid., vol.54, no.9, p.1071-1080 (2005). A new class of binary maximum distance separable (MDS) array codes which are based on circular permutation matrices are introduced in this paper. These array codes are used for tolerating multiple (/spl ges/ 4) disk failures in redundant arrays of inexpensive disks (RAID) architecture. The size of the information part is m /spl times/ n, where n is the number of information disks and (m + 1) is a prime integer; the size of the parity-check part is m /spl times/ r, the minimum distance is r + 1, and the number of parity-check disks is r. In practical applications, m can be very large and n ranges from 20 to 50. The code rate is R = n/(n+r). These codes can be used for tolerating up to r disk failures, with very fast encoding and decoding. The complexities of encoding and decoding algorithms are O(rmn) and O(m/sup 3/r/sup 4/), respectively. When r = 4, there need to be 9mn XOR operations for encoding and (9n + 95)(m + 1) XOR operations for decoding.