The weighted-Hamming metric generalizes the Hamming metric by assigning different weights to blocks of coordinates. It is well-suited for applications such as coding over independent parallel channels, each of which has a different level of importance or noise. From a coding-theoretic perspective, the actual error-correction capability of a code under this metric can exceed half its minimum distance. In this work, we establish direct bounds on this capability, tightening those obtained via minimum-distance arguments. We also propose a flexible code construction based on generalized concatenation and show that these codes can be efficiently decoded up to a lower bound on the error-correction capability.

We investigate the applications of ovals in projective planes to distributed storage, with a focus on the Service Rate Region problem. Leveraging the incidence relations between lines and ovals, we describe a class of non-systematic MDS matrices with a large number of small and disjoint recovery sets. For certain parameter choices, the service-rate region of these matrices contains the region of a systematic generator matrix for the same code, yielding better service performance. We further apply our construction to analyze the PIR properties of the considered MDS matrices and present a one-step majority-logic decoding algorithm with strong error-correcting capability. These results highlight how ovals, a classical object in finite geometry, re-emerge as a useful tool in modern coding theory.

We develop a duality theory of locally recoverable codes (LRCs) and apply it to establish a series of new bounds on their parameters. We introduce and study a refined notion of weight distribution that captures the code's locality. Using a duality result analogous to a MacWilliams identity, we then derive an LP-type bound that improves on the best known bounds in several instances. Using a dual distance bound and the theory of generalized weights, we obtain non-existence results for optimal LRCs over small fields. In particular, we show that an optimal LRC must have both minimum distance and block length relatively small compared to the field size.

We investigate the asymptotic number of equivalence classes of linear codes with prescribed length and dimension. While the total number of inequivalent codes of a given length has been studied previously, the case where the dimension varies as a function of the length has not yet been considered. We derive explicit asymptotic formulas for the number of equivalence classes under three standard notions of equivalence, for a fixed alphabet size and increasing length. Our approach also yields an exact asymptotic expression for the sum of allq-binomial coefficients, which is of independent interest and answers an open question in this context. Finally, we establish a natural connection between these asymptotic quantities and certain discrete Gaussian distributions arising from Brownian motion, providing a probabilistic interpretation of our results.

The coverage depth problem in DNA data storage is about minimizing the expected number of reads until all data is recovered. When they exist, MDS codes offer the best performance in this context. This paper focuses on the scenario where the base field is not large enough to allow the existence of MDS codes. We investigate the performance for the coverage depth problem of codes defined over a small finite field, providing closed formulas for the expected number of reads for various code families. We also compare the results with the theoretical bounds in asymptotic regimes. The techniques we apply range from probability, to duality theory and combinatorics.

Phased Burst Errors (PBEs) are bursts of errors occurring at one or more known locations. The correction of PBEs is a classical topic in coding theory, with prominent applications such as the design of array codes for memory systems or distributed storage. We propose a general yet finegrained approach to this problem, accounting not only for the number of bursts but also the error structure in each burst. By modeling PBEs as an error set in an adversarial channel, we investigate bounds on the maximal size of codes that can correct them. The PBE-correction capability of generalized concatenated codes is analyzed, and asymptotically good PBE-correcting codes are constructed, recovering a classical construction in a specific problem instance.

This paper builds a novel bridge between algebraic coding theory and mathematical knot theory, with applications in both directions. We give methods to construct error-correcting codes starting from the colorings of a knot, describing through a series of results how the properties of the knot translate into code parameters. We show that knots can be used to obtain error-correcting codes with prescribed parameters and an efficient decoding algorithm.

We investigate the fundamental limits of the recently proposedrandom access coverage depth problemfor DNA data storage. Under this paradigm, it is assumed that the user information consists ofkinformation strands, which are encoded intonstrands via a generator matrixG. During the sequencing process, the strands are read uniformly at random, as each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) required to decode a specific information strand requested by the user. This problem heavily depends on the generator matrixG, and besides computing the expectation for different choices ofG, the goal is to construct matrices that minimize the maximum expectation over all possible requested information strands, denoted byTmax(G). In this paper, we introduce new techniques to investigate the random access coverage depth problem, capturing its combinatorial nature and identifying the structural properties of generator matrices that are advantageous. We establish two general formulas to determineTmax(G) for arbitrary generator matrices. The first formula depends on the linear dependencies between columns ofG, whereas the second formula takes into account recovery sets and their intersection structure. We also introduce the concept ofrecovery balanced codesand provide three sufficient conditions for a code to be recovery balanced. These conditions can be used to computeTmax(G) for various families of codes, such as MDS, simplex, Hamming, and binary Reed-Muller codes. Additionally, we study the performance of modified systematic MDS and simplex matrices, showing that the best results forTmax(G) are achieved with a specific combination of encoded strands and replication of the information strands.

Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.

We investigate the fundamental limits of the recently proposed random access coverage depth problem for DNA data storage. Under this paradigm, it is assumed that the user information consists of$k$information strands, which are encoded into$n$strands via some generator matrix$G$. In the sequencing process, the strands are read uniformly at random, since each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) until it is possible to decode a specific information strand, which is requested by the user. The goal is to minimize the maximum expectation over all possible requested information strands, and this value is denoted by$T_{\max}(G)$. This paper introduces new techniques to investigate the random access coverage depth problem, which capture its combinatorial nature. We establish two general formulas to find$T_{\max}(G)$for arbitrary matrices. We introduce the concept of recovery balanced codes and combine all these results and notions to compute$T_{\max}(G)$for MDS, simplex, and Hamming codes. We also study the performance of modified systematic MDS matrices and our results show that the best results for$T_{\max}(G)$are achieved with a specific mix of encoded strands and replication of the information strands.

This paper studies two crucial problems in the context of coded distributed storage systems directly related to their performance: 1) for a fixed alphabet size, determine the minimum number of servers the system must have for its service rate region to contain a prescribed set of points; 2) for a given number of servers, determine the minimum alphabet size for which the service rate region of the system contains a prescribed set of points. The paper establishes rigorous upper and lower bounds, as well as code constructions based on techniques from coding theory, optimization, and projective geometry.

Abstract We investigate the asymptotic density of error-correcting codes with good distance properties and prescribed linearity degree, including (sub)linear and nonlinear codes. We focus on the general setting of finite translation-invariant metric spaces, and then specialize our results to the Hamming metric, to the rank metric, and to the sum-rank metric. Our results show that the asymptotic density of codes heavily depends on the imposed linearity degree and the chosen metric.

We introduce a formal framework to study the multiple unicast problem for a coded network in which the network code is linear over a finite field and fixed. We show that the problem corresponds to an interference alignment problem over a finite field. In this context, we establish an outer bound for the achievable rate region and provide examples of networks where the bound is sharp. We finally give evidence of the crucial role played by the field characteristic in the problem.

We consider the problem of deriving upper bounds on the parameters of sum-rank-metric codes, with focus on their dimension and block length. The sum-rank metric is a combination of the Hamming and the rank metric, and most of the available techniques to investigate it seem to be unable to fully capture its hybrid nature. In this paper, we introduce a new approach based on sum-rank-metric graphs, in which the vertices are tuples of matrices over a finite field, and where two such tuples are connected when their sum-rank distance is equal to one. We establish various structural properties of sum-rank-metric graphs and combine them with eigenvalue techniques to obtain bounds on the cardinality of sum-rank-metric codes. The bounds we derive improve on the best known bounds for several choices of the parameters. While our bounds are explicit only for small values of the minimum distance, they clearly indicate that spectral theory is able to capture the nature of the sum-rank-metric better than the currently available methods. They also allow us to establish new non-existence results for (possibly nonlinear) MSRD codes.

We consider (symmetric, non-degenerate) bilinear spaces over a finite field and investigate the properties of their$\ell $-complementary subspaces, i.e., the subspaces that intersect their dual in dimension$\ell $. This concept generalizes that of a totally isotropic subspace and, in the context of coding theory, specializes to the notions of self-orthogonal, self-dual and linear-complementary-dual (LCD) codes. In this paper, we focus on the enumerative and asymptotic combinatorics of all these objects, giving formulas for their numbers and describing their typical behavior (rather than the behavior of a single object). For example, we give a closed formula for the average weight distribution of an$\ell $-complementary code in the Hamming metric, generalizing a result by Pless and Sloane on the aggregate weight enumerator of binary self-dual codes. Our results also show that self-orthogonal codes, despite being very sparse in the set of codes of the same dimension over a large field, asymptotically behave quite similarly to a typical, not necessarily self-orthogonal, code. In particular, we prove that most self-orthogonal codes are MDS over a large field by computing the asymptotic proportion of the non-MDS ones for growing field size.

We initiate the study of the duality theory of locally recoverable codes, with a focus on the applications. We characterize the locality of a code in terms of the dual code, and introduce a class of invariants that refine the classical weight distribution. In this context, we establish a duality theorem analogous to (but very different from) a MacWilliams identity. As an application of our results, we obtain two new bounds for the parameters of a locally recoverable code, including an LP bound that improves on the best available bounds in several instances.

We consider the problem of determining the one-shot, zero-error capacity of a coded, multicast network over a small alphabet. We introduce a novel approach to this problem based on a mixed-integer program, which computes the size of the largest unambiguous codebook for a given alphabet size. As an application of our approach, we recover, extend and refine various results that were previously obtained with case-by-case analyses or specialized arguments, giving evidence of the wide applicability of our approach. We also provide two simple ideas that reduce the complexity of our method for some families of networks. We conclude the paper by outlining a research program we wish to pursue to investigate the one-shot capacity of large networks affected by adversarial noise and, more generally, the role played by the alphabet size in network coding.

Abstract. We investigate two fundamental questions intersecting coding theory and combinatorial geometry, with emphasis on their connections. These are the problem of computing the asymptotic density of MRD codes in the rank metric, and the Critical Problem for combinatorial geometries by Crapo and Rota. In the first part of the paper, we use methods from semifield theory to derive two lower bounds for the density function of full-rank, square MRD codes. The first bound is sharp when the matrix size is a prime number and the underlying field is sufficiently large, while the second bound applies to the binary field. We then take a new look at the Critical Problem for combinatorial geometries, approaching it from a qualitative, often asymptotic, viewpoint. We illustrate the connection between this very classical problem and that of computing the asymptotic density of MRD codes. Finally, in the third part of the paper we study the asymptotic density of some special families of codes in the rank metric, including the symmetric, alternating, and Hermitian ones. In particular, we show that the optimal codes in these three contexts are sparse.

We consider the problem of error control in a coded, multicast network, focusing on the scenario where the errors can occur only on a proper subset of the network edges. We model this problem via an adversarial noise, presenting a formal framework and a series of techniques to obtain upper and lower bounds on the network’s (1-shot) capacity, improving on the best currently known results. In particular, we show that traditional cut-set bounds are not tight in general in the presence of a restricted adversary, and that the non-tightness of these is caused precisely by the restrictions imposed on the noise (and not, as one may expect, by the alphabet size). We also show that, in sharp contrast with the typical situation within network coding, capacity cannot be achieved in general by combining linear network coding with end-to-end channel coding, not even when the underlying network has a single source and a single terminal. We finally illustrate how network decoding techniques are necessary to achieve capacity in the scenarios we examine, exhibiting capacity-achieving schemes and lower bounds for various classes of networks.

We are concerned with linear redundancy storage schemes regarding their ability to provide concurrent (local) recovery of multiple data objects. This paper initiates a study of such systems within the classical coding theory. We show how we can use the structural properties of the generator matrix defining the scheme to obtain a bounding polytope for the set of data access rates the system can support. We derive two dual distance outer bounds, which are sharp for some large classes of matrix families.

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.

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality.

We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality $q^{n-d+1}$ is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties.

A $t$-$(n,d,\lambda)$ design over $\mathbb{F}_{q}$, or a subspace design, is a collection of $d$-dimensional subspaces of $\mathbb{F}_{q}^n$, called blocks, with the property that every $t$-dimensional subspace of $\mathbb{F}_{q}^n$ is contained in the same number $\lambda$ of blocks. A collection of $n \times m$ matrices over $\mathbb{F}_{q}$ is said to hold a $t$-design over $\mathbb{F}_{q}$ if the set of column spaces of its elements forms the blocks of a subspace design. We use notions of puncturing and shortening of rank metric codes and the rank metric MacWilliams identities to establish conditions under which the words of a given rank in a linear rank metric code hold a $t$-design over $\mathbb{F}_{q}$. We show that for $\mathbb{F}_{q^m}$-linear vector rank metric codes, the property of a code being maximum rank distance (MRD) is equivalent to its minimal weight codewords holding trivial subspace designs, and show that this characterization does not hold for $\mathbb{F}_{q}$-linear matrix MRD codes that are not linear over $\mathbb{F}_{q^m}$. Finally, using arguments based on covering radius and external distance, we establish various existence results that apply to both the rank and the Hamming metric.

A combinatorial framework for adversarial network coding is presented. Channels are described by specifying the possible actions that one or more (possibly coordinated) adversaries may take. Upper bounds on three notions of capacity-the one-shot capacity, the zero-error capacity, and the compound zero-error capacity-are obtained for point-to-point channels, and generalized to corresponding capacity regions appropriate for multi-source networks. A key result of this paper is a general method by which bounds on these capacities in point-to-point channels may be ported to networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple adversaries acting on specific network edges. Capacity-achieving coding schemes are described for some of the considered adversarial models.

We propose an algebraic framework for end-to-end physical-layer network coding based on submodules transmission. Our approach is motivated by nested-lattice-based network coding schemes, that naturally induce end-to-end channels where the ambient space has the structure of a module over a principal ideal ring. The setup is compatible with previously proposed approaches for finite chain rings, and extends them to arbitrary principal ideal rings. We introduce a distance function between modules, and describe how it relates to information loss and errors. We also show that computing the distance between modules reduces to computing the length of certain ideals in the base ring. We then propose a definition of submodule error-correcting code, and establish two upper bounds for the cardinality of these codes. Finally, we present some constructions of submodule codes, showing that they have asymptotically optimal cardinality for certain choices of the parameters.

In this paper we study properties and invariants of matrix codes endowed with the rank metric and relate them to the covering radius. We introduce new tools for the analysis of rank-metric codes, such as puncturing and shortening constructions. We give upper bounds on the covering radius of a code by applying different combinatorial methods. The various bounds are then applied to the classes of maximal-rank-distance and quasi-maximal-rank-distance codes.

Optimal rank-metric codes in Ferrers diagrams are considered. Such codes consist of matrices having zeros at certain fixed positions and can be used to construct good codes in the projective space. First, we consider rank-metric anticodes and prove a code-anticode bound for Ferrers diagram rank-metric codes. The size of optimal linear anticodes is given. Four techniques and constructions of Ferrers diagram rank-metric codes are presented, each providing optimal codes for different diagrams and parameters for which no optimal solution was known before. The first construction uses maximum distance separable codes on the diagonals of the matrices, the second one takes a subcode of a maximum rank distance code, and the last two combine codes in small diagrams to a code in a larger diagram. The constructions are analyzed and compared, and unsolved diagrams are identified.