A construction of \(\mathbb{F}_2 \)-linear cyclic, MDS codes (Q2194505)

In this work, the authors introduce a family of codes of length \( n = p-1 \), for a prime \( p \), over the alphabet \( \mathbb{F}_2^b \), with the following properties: The codes are \( \mathbb{F}_2 \)-linear, the code redundancy over \( \mathbb{F}_2^b \), \( r \), satisfies \( n = rb \), the codes are cyclic over the alphabet \( \mathbb{F}_2^b \) (thus \( b \)-quasi-cyclic over \( \mathbb{F}_2 \)) and LDPC (with density going to \( 0 \) as \( n \longrightarrow \infty \)). Moreover, the codes are MDS over the alphabet \( \mathbb{F}_2^b \) in the case \( r = 2 \). The normalized dimension of the codes over the alphabet \( \mathbb{F}_2^b \) is \( k = n-r \) and satisfies \( k = r(b-1) \) since \( n = rb \). In other words, the information rate of the codes is \( k/n = 1 -1/b \), where \( b \) is the number of bits in a symbol of the code alphabet. MDS codes in such a scenario are of interest, for example, in Distributed Storage. The codes are constructed using the concept of index array. They construct the parity-check matrices using such index arrays, which are in turn constructed using a partition of \( \mathbb{Z}_n \) and applying the Zech logarithm to the sets of the partition. The authors explicitly describe generator and parity-check matrices of the codes over \( \mathbb{F}_2 \). They then prove that the codes are MDS over the alphabet \( \mathbb{F}_2^b \) in the case \( r = 2 \) using graph-theoretic methods (including Hamiltonian paths). Finally, the authors provide an error-correcting algorithm for the given codes. However, the computational complexity of the algorithm is not explicitly given. Several examples are given throughout the article to illustrate the ideas.