New constructions for moderate-density parity-check (MDPC) codes using finite geometry are proposed. We design a parity-check matrix for the main family of binary codes as the concatenation of two matrices: the incidence matrix between points and lines of the Desarguesian projective plane and the incidence matrix between points and ovals of a projective bundle. A projective bundle is a special collection of ovals which pairwise meet in a unique point. We determine the minimum distance and the dimension of these codes, and we show that they have a natural quasi-cyclic structure. We consider alternative constructions based on an incidence matrix of a Desarguesian projective plane and compare their error-correction performance with regards to a modification of Gallager's bit-flipping decoding algorithm. In this setting, our codes have the best possible error-correction performance after one round of bit-flipping decoding given the parameters of the code's parity-check matrix.

We develop three approaches of combinatorial flavor to study the structure of minimal codes and cutting blocking sets in finite geometry, each of which has a particular application. The first approach uses techniques from algebraic combinatorics, describing the supports in a linear code via the Alon--Füredi theorem and the combinatorial Nullstellensatz. The second approach combines methods from coding theory and statistics to compare the mean and variance of the nonzero weights in a minimal code. Finally, the third approach regards minimal codes as cutting blocking sets and studies these using the theory of spreads in finite geometry. By applying and combining these approaches with each other, we derive several new bounds and constraints on the parameters of minimal codes. Moreover, we obtain two new constructions of cutting blocking sets of small cardinality in finite projective spaces. In turn, these allow us to give explicit constructions of minimal codes having short length for the given field and dimension.

Low-rank parity-check (LRPC) codes are rank-metric codes over finite fields, which have been proposed by Gaborit et al. (Proceedings of the workshop on coding and cryptography WCC, vol 2013, 2013) for cryptographic applications. Inspired by a recent adaption of Gabidulin codes to certain finite rings by Kamche et al. (IEEE Trans Inf Theory 65(12):7718-7735, 2019), we define and study LRPC codes over Galois rings-a wide class of finite commutative rings. We give a decoding algorithm similar to Gaborit et al.'s decoder, based on simple linear-algebraic operations. We derive an upper bound on the failure probability of the decoder, which is significantly more involved than in the case of finite fields. The bound depends only on the rank of an error, i.e., is independent of its free rank. Further, we analyze the complexity of the decoder. We obtain that there is a class of LRPC codes over a Galois ring that can decode roughly the same number of errors as a Gabidulin code with the same code parameters, but faster than the currently best decoder for Gabidulin codes. However, the price that one needs to pay is a small failure probability, which we can bound from above.

We propose reducible algebraic curves as a mechanism to construct partial maximum distance separable codes geometrically. We obtain new general existence results, new explicit constructions, and improved estimates on the smallest field sizes over which such codes can exist. Our results are obtained by combining ideas from projective algebraic geometry, combinatorics, and probability theory.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may eitherfailto return a codeword ormiscorrectto an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of decodable error matrices by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an [n,k,d]qlinear block code, we are able to prove the existence of a permutation code in the symmetric group of degree n, having minimum distance at least d and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code.

Upper and lower bounds on the largest number of weights in a cyclic code of given length, dimension and alphabet are given. An application to irreducible cyclic codes is considered. Sharper upper bounds are given for the special cyclic codes (called here strongly cyclic), whose nonzero codewords have period equal to the length of the code. Asymptotics are derived on the function Γ(k, q), that is defined as the largest number of nonzero weights a cyclic code of dimension k over Fq can have, and an algorithm to compute it is sketched. The nonzero weights in some infinite families of Reed-Muller codes, either binary or q-ary, as well as in the q-ary Hamming code are determined, two difficult results of independent interest.

We investigate the largest number of nonzero weights of quasi-cyclic codes. In particular, we focus on the function ΓQ(n, ℓ, k, q), that is defined to be the largest number of nonzero weights a quasi-cyclic code of index gcd(ℓ, n), length n and dimension k over Fqcan have, and connect it to similar functions related to linear and cyclic codes. We provide several upper and lower bounds on this function, using different techniques and studying its asymptotic behavior. Moreover, we determine the smallest index for which a q-ary Reed-Muller code is quasi-cyclic, a result of independent interest.

We show that the sequence of dimensions of the linear spaces, generated by a given rank-metric code together with itself under several applications of a field automorphism, is an invariant for the whole equivalence class of the code. These invariants give rise to an easily computable criterion to check if two codes are inequivalent. With this criterion we then derive bounds on the number of equivalence classes of classical and twisted Gabidulin codes.