New Efficient MDS Array Codes for RAID Part II: Rabin-Like Codes for Tolerating Multiple (greater than or equal to 4) Disk Failures
Gui-Liang Feng, Robert Huijie Deng, Feng Bao, Jia-Chen Shen · IEEE Transactions on Computers · 2005
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.