The connection between secret sharing and matroid theory is well established. In this paper, we generalize the concepts of secret sharing and matroid ports to q-polymatroids. Specifically, we introduce the notion of an access structure on a vector space, and consider properties related to duality, minors, and the relationship to q-polymatroids. Finally, we show how rank-metric codes give rise to secret sharing schemes within this framework.

Tensor codes are a generalisation of matrix codes. Such codes are defined as subspaces of$r$-th order tensors for which the ambient space is endowed with the tensor-rank as a metric. A class of these codes was introduced by Roth, who outlined a decoding algorithm for low tensor-rank errors for particular cases. They may be viewed as a generalisation of the well-known Delsarte-Gabidulin-Roth maximum rank distance codes. We study a generalised class of these codes. We investigate the properties of these codes and outline decoding techniques for different metrics that leverage their tensor structure. We first consider a fibre-wise decoding approach, as each fibre of a codeword corresponds to a Gabidulin codeword. We then give a generalisation of Loidreau's decoding method that corrects errors with properties constrained by the dimensions of the slice-spaces and fibre-spaces. The metrics we consider are upper bounded by the tensor-rank metric, and therefore these algorithms also decode tensor-rank weight errors.11This work has emanated from research conducted with the financial support of the European Union MSCA Doctoral Networks, (HORIZON-MSCA-2021-DN-01, Project 101072316), the French Agence Nationale de la Recherche project ANR-21-CE39-0009-BARRACUDA and by Plan France 2030 ANR-22-PETQ-0008. Link to GitHub repository with programs:https://github.com/lucienfrancois/RothTensorCodes

Abstract We introduce the concept of a sum–rank saturating system and outline its correspondence to covering properties of a sum–rank metric code. We consider the problem of determining the shortest length of a sum–rank- $$\rho $$ ρ -saturating system of a fixed dimension, which is equivalent to the covering problem in the sum–rank metric. We obtain upper and lower bounds on this quantity. We also give constructions of saturating systems arising from geometrical structures.

Abstract A perfect matroid design (PMD) is a matroid whose flats of the same rank all have the same size. In this paper we introduce the q -analogue of a PMD and its properties. In order to do so, we first establish a new cryptomorphic definition for q -matroids. We show that q -Steiner systems are examples of q -PMD’s and we use this q -matroid structure to construct subspace designs from q -Steiner systems. We apply this construction to the only known q -Steiner system, which has parameters S (2, 3, 13; 2), and hence establish the existence of a new subspace design with parameters 2-(13, 4, 5115; 2).

Abstract. In 1991, Roth introduced a natural generalization of rank-metric codes, namely, tensor codes. The latter are defined to be subspaces of [Formula: see text]-tensors, where the ambient space is endowed with the tensor rank as a distance function. In this work, we describe the general class of tensor codes and we study their invariants corresponding to different families of anticodes. In our context, an anticode is a perfect space that has some additional properties. A perfect space is one that is spanned by tensors of rank 1. Our use of the anticode concept is motivated by an interest in capturing structural properties of tensor codes. In particular, we indentify four different classes of tensor anticodes and show how these gives different information on the codes they describe. We also define the binomial moments and the weight distribution of a code with respect to a family of anticodes and establish a bijection between these invariants. We use the binomial moments to define the concept of a binomial moment determined code, which is an extremal code in relation to an inequality arising from them. Finally, we give MacWilliams identities for binomial moments.

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.

In this work we study both the index coding with side information (ICSI) problem introduced by Birk and Kol in 1998 and the more general problem of index coding with coded side information (ICCSI), described by Shum et al. in 2012. We estimate the optimal rate of an instance of the index coding problem. In the ICSI problem case, we characterize those digraphs having min-rank one less than their order and we give an upper bound on the min-rank of a hypergraph whose incidence matrix can be associated with that of a 2-design. Security aspects are discussed in the particular case when the design is a projective plane. For the coded side information case, we extend the graph theoretic upper bounds given by Shanmugam et al. in 2014 on the optimal rate of index code.

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.

Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. A well-known application is satellite communications, as described in one of the earliest papers on the subject (Birk and Kol, 1998). It is readily seen that if the sender has knowledge of its clients' requests and their side-information sets, then the number of packet transmissions required to satisfy all users' demands can be greatly reduced if the data are encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance I of the index coding with side-information (ICSI) problem. The encoding function is called the index code of I, and the number of transmissions, resulting from the encoding is referred to as its length. The main ICSI problem is to determine the optimal length of an index code and instance I. As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. These questions have been addressed by several authors (e.g., see Alon et al. 2008, Bar-Yossef et al. 2011, Blasiak et al. 2013), often taking a graph-theoretic approach. Two interesting generalizations of the problem that have appeared in the literature are the subject of this paper. The first of these is the case of index coding with coded side information (Dai et al. 2014), in which linear combinations of the source data are both requested by and held as users' side-information. This generalization has applications, for example, to relay channels and necessitates algebraic rather than combinatorial methods. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise (Dau et al. 2013). In this paper, we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal δ-error correcting code for an instance of the ICCSI problem and obtain bounds analogous to those described in (Dau et al. 2013), both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors.

Recent advances in the area of wireless body area networks (WBANs) open new horizons in areas ranging from mHealth to entertainment. Reliability of communications and power consumption are paramount to widespread adoption of this technology. In this paper, we use ambulatory electroen-cephalography (EEG) monitoring in the context of WBANs and describe some network topologies and coding performance using graph theoretic techniques.

In this paper we compute the Fourier spectra of some recently discovered binomial almost perfect nonlinear (APN) functions. One consequence of this is the determination of the nonlinearity of the functions, which measures their resistance to linear cryptanalysis. Another consequence is that certain error-correcting codes related to these functions have the same weight distribution as the 2-error-correcting Bose–Chaudury–Hocquenghem (BCH) code. Furthermore, for field extensions of $\mathbb{F}_2$ of odd degree, our results provide an alternative proof of the APN property of the functions.

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linear-programming problem. In this paper, we study different polytopes for use with linear-programming decoding, and show that for many classes of codes these polytopes yield a complexity advantage for decoding. These representations lead to polynomial-time decoders for a wide variety of classical non-binary linear codes.

We investigate a class of Lee (1958) metric alternant codes with symbols in Z/sub pn/, establishing a lower bound on the minimum Lee distance where certain restrictions are placed on the code parameters. Corresponding to this bound, we have devised a decoding algorithm which is implemented over a finite field. The algorithm proceeds by finding a Grobner basis of the module M of solutions to a key equation. We obtain a necessary characterization of the solution module by solving iteratively a linear sequence over a Galois ring and show that the particular solution sought by the decoder is minimal in M. The required solution can then be found in an appropriate Grobner basis of M.

The standard decoding procedure for alternant codes over fields centers on solving a key equation which relates an error locator polynomial and an error evaluator polynomial by a syndrome sequence. We extend this technique to decode alternant codes over Galois rings. We consider the module M={(a, b): as/spl equiv/b mod x/sup r/} of all solutions to the key equation where s is the syndrome polynomial and r, is the number of rows in a parity-check matrix for the code. In decoding we seek a particular solution (/spl Sigma/, /spl Omega/)/spl isin/M which we prove can be found in a Grobner basis for M. We present an iterative algorithm which generates a Grobner basis modulo x/sup k+1/ from a given basis modulo x/sup k/. At the rth step, a Grobner basis for M is found, and the required solution recovered.