Technical Program

Paper Detail

Paper Title Efficient MDS Array Codes for Correcting Multiple Column Erasures
Paper IdentifierWE2.R3.5
Authors Zhijie Huang, Hong Jiang, Hao Che, University of Texas at Arlington, United States; Nong Xiao, Sun Yat-sen University, China; Ning Li, University of Texas at Arlington, United States
Session Coding for Memories
Location Monge, Level 3
Session Time Wednesday, 10 July, 11:40 - 13:20
Presentation Time Wednesday, 10 July, 13:00 - 13:20
Manuscript  Click here to download the manuscript
Abstract The R$\Lambda$-Code is an efficient family of maximum distance separable (MDS) array codes of column distance 4, which involves two types of parity constraints: the row parity and the $\Lambda$ parity formed by diagonal lines of slopes 1 and -1. Benefitting from the common expressions between the two parity constraints, the encoding and decoding complexities are distinctly lower than other triple-erasure-correcting codes. It was left as an open problem generalizing the R$\Lambda$-Code to arbitrary column distances. In this paper, we present such a generalization, namely, we construct a family of MDS array codes being capable of correcting any prescribed number of erasures/errors by introducing multiple $\Lambda$ parity constraints. Essentially, the generalized R$\Lambda$-Code is derived from a certain variant of the Blaum-Roth codes, and hence retains the error/erasure correcting capability of the latter. Compared with the Blaum-Roth codes, the generalized R$\Lambda$-Code has two advantages: a) by exploiting common expressions between row parity and different $\Lambda$ parity constraints, and reusing the intermediate results during the syndrome calculations, it can encode and decode faster; b) the memory footprint during encoding/decoding, and the I/O cost caused by degraded reads, are both reduced by $50\%$.