On Maximally Recoverable Codes for Product Topologies

Abstract

Given a topology of local parity-check constraints, a maximally recoverable code (MRC) can correct all erasure patterns that are information-theoretically correctable. In a grid-like topology, there are $a$ local constraints in every column forming a column code, $b$ local constraints in every row forming a row code, and $h$ global constraints in an $(m\times n)$ grid of codeword. Recently, Gopalan et al. initiated the study of MRCs under grid-like topology, and derived a necessary and sufficient condition, termed as the regularity condition, for an erasure pattern to be recoverable when $a=1,h=0$. In this paper, we consider MRCs for product topology ($h=0$). First, we construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition for product topology (any $a,b$, $h=0$) and show that there exists a complete matching in this graph. We then present an alternate direct proof of the sufficient condition when $a=1,h=0$. We later extend our technique to study the topology for $a=2,h=0$, and characterize a subset of recoverable erasure patterns in that case. For both $a=1,2$, our method of proof is uniform, i.e., by constructing tensor product $G_{\text{col}}\otimes G_{\text{row}}$ of generator matrices of column and row codes such that certain square sub-matrices retain full rank. The full-rank condition is proved by resorting to the matching identified earlier and also another set of matchings in erasure sub-patterns.

6 pages, accepted to National Conference of Communications (NCC) 2018