Low-Complexity Array Codes for Random and Clustered 4-Erasures

作者：Cassuto Yuval^*; Bruck Jehoshua

来源：IEEE Transactions on Information Theory, 2012, 58(1): 146-158.

DOI：10.1109/TIT.2011.2171518

• Array codes
• clustered erasures
• correlated failures
• storage arrays

A new family of low-complexity array codes is proposed for correcting 4 column erasures. The new codes are tailored for the new error model of clustered column erasures that captures the properties of high-order failure combinations in storage arrays. The model of clustered column erasures considers the number of erased columns, together with the number of clusters into which they fall, without pre-defining the sizes of the clusters. This model addresses the problem of correlated device failures in storage arrays, whereby each failure event may affect multiple devices in a single cluster. The new codes correct essentially all combinations of clustered 4 erasures, i.e., those combinations that fall into three or less clusters. The new codes are significantly more efficient, in all relevant complexity measures, than the best known 4-erasure correcting codes. These measures include encoding complexity, decoding complexity and update complexity.

• 出版日期2012-1