X-code: MDS array codes with optimal encoding
We present a new class of MDS array codes of size n x n (n a prime number) called X-code. The X-codes are of minimum column distance, namely, they can correct either one column error or two column erasures. The key novelty in X-code is that it has a simple geometrical construction which achieves encoding/update optimal complexity, i.e, a change of any single information bit affects exactly two parity bits. The key idea in our constructions is that all parity symbols are placed in rows rather than columns.
array codes balanced computation mds codes optimal updates update complexity