K-Plex 2-Erasure Codes and Blackburn Partial Latin Squares
Rebecca J. Stones · IEEE Transactions on Information Theory · 2020
A k-plex of order n is an n × n matrix on n symbols, where every row contains k distinct symbols, every column contains k distinct symbols, and every symbol occurs exactly k times. Yi et al. (2019) introduced 3-plex codes which are 2-erasure codes (2-erasure tolerant array codes) derived from 3-plexes. In this paper, we generalize 3-plex codes to k-plex codes. We introduce the notion of a “strong” k-plex which implies the derived k-plex code is 2-erasure tolerant. Moreover, k-plex codes derived from strong k-plexes have a straightforward algorithm for reconstruction. These general k-plex codes offer greater flexibility when choosing a suitable code for a storage system, enabling the operator to better optimize the unavoidable trade-offs involved. Blackburn asked for the maximum number of entries in an n × n partial Latin square on n symbols in which if distinct cells (i, j) and (i', j') contain the same symbol, then the cells (i', j) and (i, j') are empty. A “strong” k-plex satisfies the Blackburn property (along with two other properties related to erasure coding). We investigate the necessary conditions for the existence of Blackburn k-plexes (and hence necessary conditions for the existence of strong k-plexes). We show that any Blackburn k-plex has order n ≥ [(√2 + 1)k - 2]. We describe how to construct strong k-plexes of order n when k ∈ {2, 3, 4, 5} for all possible orders n, and we give a simple construction of strong k-plexes of order k2for k ≥ 2.