Title :
New efficient MDS array codes for RAID. Part I. Reed-Solomon-like codes for tolerating three disk failures
Author :
Feng, Gui-Liang ; Deng, Robert H. ; Bao, Feng ; Shen, Jia-Chen
Author_Institution :
Center for Adv. Comput. Studies, Louisiana Univ., Lafayette, LA, USA
Abstract :
This paper presents a class of binary maximum distance separable (MDS) array codes for tolerating disk failures in redundant arrays of inexpensive disks (RAID) architecture based on circular permutation matrices. The size of the information part is m×n, the size of the parity-check part is m×3, and the minimum distance is 4, where n is the number of information disks, the number of parity-check disks is 3, and (m+1) is a prime integer. In practical applications, m can be very large and n is from 20 to 50. The code rate is R=n/(n+3). These codes can be used for tolerating three disk failures. The encoding and decoding of the Reed-Solomon-like codes are very fast. There need to be 3mn XOR operations for encoding and (3mn+9(m+1)) XOR operations for decoding.
Keywords :
RAID; Reed-Solomon codes; binary codes; fault tolerance; linear codes; matrix algebra; parity check codes; RAID architecture; Reed-Solomon-like code; XOR operation; binary linear code; binary maximum distance separable array code; circular permutation matrix; decoding; disk failure tolerance; encoding; low density parity-check code; redundant arrays of inexpensive disks; Companies; Decoding; Educational institutions; Government; Hard disks; Information retrieval; Linear code; Parity check codes; Protection; Reed-Solomon codes; Index Terms- Low-density-parity-check codes; MDS array codes; RAID; Reed-Solomon codes.; multiple disk failures;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2005.150