Details

Autor(en) / Beteiligte

• Stones, Rebecca J.

Titel

K-Plex 2-Erasure Codes and Blackburn Partial Latin Squares

Ist Teil von

• IEEE transactions on information theory, 2020-06, Vol.66 (6), p.3704-3713

Ort / Verlag

IEEE

Erscheinungsjahr

2020

Quelle

IEEE Xplore

Beschreibungen/Notizen

• A k -plex of order n is an <inline-formula> <tex-math notation="LaTeX">{n} \times {n} </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-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 <inline-formula> <tex-math notation="LaTeX">{n} \times {n} </tex-math></inline-formula> partial Latin square on n symbols in which if distinct cells <inline-formula> <tex-math notation="LaTeX">({i},{j}) </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">({i}',{j}') </tex-math></inline-formula> contain the same symbol, then the cells <inline-formula> <tex-math notation="LaTeX">({i}',{j}) </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">({i},{j}') </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">{n} \geq \lceil (\sqrt {2}+1){k}-2 \rceil </tex-math></inline-formula>. We describe how to construct strong k -plexes of order n when <inline-formula> <tex-math notation="LaTeX">k \in \{2,3,4,5\} </tex-math></inline-formula> for all possible orders n , and we give a simple construction of strong k -plexes of order <inline-formula> <tex-math notation="LaTeX">{k}^{2} </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX">k \geq 2 </tex-math></inline-formula>.