Search

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).

In this paper we investigate known Singleton-like bounds in the Lee metric and characterize optimal codes, which turn out to be very few. We then focus on Plotkin-like bounds in the Lee metric and present a new bound that extends and refines a previously known, and out-performs it in the case of non-free codes. We then compute the density of optimal codes with regard to the new bound. Finally we fill a gap in the characterization of Lee-equidistant codes.

In this paper we introduce a new class of extremal codes, namely the $i$-BMD codes. We show that for this family several of the invariants are determined by the parameters of the underlying code. We refine and extend the notion of an $i$-MRD code and show that the $i$-BMD codes form a proper subclass of the $i$-MRD codes. Using the class of $i$-BMD codes we then obtain a relation between the generalized rank weight enumerator and its corresponding generalized zeta function. We also establish a MacWilliams identity for generalized rank weight distributions., 27 pages

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.

In this paper we focus on modules over a finite chain ring $\mathcal{R}$ of size $q^s$. We compute the density of free modules of $\mathcal{R}^n$, where we separately treat the asymptotics in $n,q$ and $s$. In particular, we focus on two cases: one where we fix the length of the module and one where we fix the rank of the module. In both cases, the density results can be bounded by the Andrews-Gordon identities. We also study the asymptotic behaviour of modules generated by random matrices over $\mathcal{R}$. Since linear codes over $\mathcal{R}$ are submodules of $\mathcal{R}^n$ we get direct implications for coding theory. For example, we show that random codes achieve the Gilbert-Varshamov bound with high probability.

In the theory of classical matroids, there are several known equivalent axiomatic systems that define a matroid, which are described as matroid cryptomorphisms. A q-matroid is a q-analogue of a matroid where subspaces play the role of the subsets in the classical theory. In this article we establish cryptomorphisms of q-matroids. In doing so we highlight the difference between classical theory and its q-analogue. We introduce a comprehensive set of q-matroid axiom systems and show cryptomorphisms between them and existing axiom systems of a q-matroid. These axioms are described as the rank, closure, basis, independence, dependence, circuit, hyperplane, flat, open space, spanning space, non-spanning space, and bi-colouring axioms.

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. European Commission Horizon 2020 ESF-COST

We present the theory of rank-metric codes with respect to the 3-tensors that generate them. We define the generator tensor and the parity check tensor of a matrix code, and describe the properties of a code through these objects. We define the tensor rank of a code to be the tensor rank of its generating tensors, and propose that this quantity is a significant coding theoretic parameter. By a result on the tensor rank of Kruskal from the 1970s, the tensor rank of a rank-metric code of dimension $k$ and minimum rank distance $d$ is at least $k+d-1$. We call codes that meet this bound minimal tensor rank (MTR) codes. It is known from results in algebraic complexity theory that an MTR code implies the existence of an MDS code. In this paper, we also address the converse problem, that of the existence of an MTR code, given an MDS code. We identify several parameters for which the converse holds and give explicit constructions of MTR codes using MDS codes. We furthermore define generalized tensor ranks, which give a refinement of the tensor rank as a code invariant. Moreover, we use these to distinguish inequivalent rank-metric codes.

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 matrices in over ${\mathbb F}_q$ is said to hold a subspace design 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 subspace design.

We introduce the class of partition-balanced families of codes, and show how to exploit their combinatorial invariants to obtain upper and lower bounds on the number of codes that have a prescribed property. In particular, we derive precise asymptotic estimates on the density functions of several classes of codes that are extremal with respect to minimum distance, covering radius, and maximality. The techniques developed in this paper apply to various distance functions, including the Hamming and the rank metric distances. Applications of our results show that, unlike the F q m -linear MRD codes, the F q -linear MRD codes are not dense in the family of codes of the same dimension. More precisely, we show that the density of F q -linear MRD codes in F q n × m in the set of all matrix codes of the same dimension is asymptotically at most 1/2, both as q → + ∞ and as m → + ∞ . We also prove that MDS and F q m -linear MRD codes are dense in the family of maximal codes. Although there does not exist a direct analogue of the redundancy bound for the covering radius of F q -linear rank metric codes, we show that a similar bound is satisfied by a uniformly random matrix code with high probability. In particular, we prove that codes meeting this bound are dense. Finally, we compute the average weight distribution of linear codes in the rank metric, and other parameters that generalize the total weight of a linear code.

Index coding, the problem of efficient broadcast to many receivers with side-infomation, is a rich and active research area. It has applications to a range of multi-user broadcast scenarios such as video-on-demand and satellite communications. It has attracted significant theoretical interest both as a hard problem in its own right and due to its connections to other network capacity problems. The central problem of index coding, that of determining the optimal rate of an index code, is still open. We describe recent advances on the index coding problem and its generalizations in the context of broadcast with side-information. The two main approaches to bounding the optimal rate of an index code, namely rank-minimization methods and linear programming models, are discussed in detail. The latter of these, based on graph-theoretical ideas in the classical case, can be extended even to generalizations of the index coding problem for which there is no associated side-information hypergraph. We discuss error-correction in the index coding problem, the corresponding bounds on the optimal transmission rate and decoding algorithms. We also illustrate the connections to network coding, interference alignment and coded caching.

We investigate properties of two-weight codes over finite Frobenius rings, giving constructions for the modular case. A $$\delta $$?-modular code (in: Honold T, Honold in Proceedings of the fifth international workshop on optimal codes and related topics, White Lagoon, Bulgaria, 2007) is characterized as having a generator matrix where each column $$g$$g appears with multiplicity $$\delta |gR^\times |$$?|gR×| for some $$\delta \in \mathbb {Q}$$??Q. Generalizing (Delsarte in Discret Math 3:47---64, 1972) and (Byrne et al in Finite Fields Appl 18(4):711---727, 2012), we show that the additive group of a two-weight code satisfying certain constraint equations (and in particular a modular code) has a strongly regular Cayley graph and derive existence conditions on its parameters. We provide a construction for an infinite family of modular two-weight codes arising from unions of submodules with pairwise trivial intersection. The corresponding strongly regular graphs are isomorphic to graphs from orthogonal arrays.

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 ${ \mathcal I}$ of the index coding with side-information (ICSI) problem. The encoding function is called the index code of $ \mathcal 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 $ \mathcal 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 $\delta $ -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.

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. Swiss National Science Foundation

In this article we investigate Berlekamp's negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp's original papers: our codes have minimum Lee distance at least 2t + 1, where the generator polynomial of the code has roots ?, ? 3, . . . , ? 2t-1 for a primitive 2nth root ? of unity in a Galois extension of $${\mathbb {Z}_4}$$ ; no restriction on t is imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight ? t. Our treatment uses Grobner bases, the decoding complexity is quadratic in t.

We give further results on the question of code optimality for linear codes over finite Frobenius rings for the homogeneous weight. This article improves on the existing Plotkin bound derived in an earlier paper (Greferath and O’Sullivan, Discr Math 289:11–24, 2004) and suggests a version of a Singleton bound. We also present some families of codes meeting these new bounds.

We introduce two new infinite families of APN functions, one on fields of order 22k for k not divisible by 2, and the other on fields of order 23k for k not divisible by 3. The polynomials in the first family have between three and k+2 terms, the second family's polynomials have three terms.

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.

We develop a theory of Gröbner bases over Galois rings, following the usual formulation for Gröbner bases over finite fields. Our treatment includes a division algorithm, a characterization of Gröbner bases, and an extension of Buchberger’s algorithm. One application is towards the problem of decoding alternant codes over Galois rings. To this end we consider the module M= {(a, b) :aS≡b modxr} of all solutions to the so-called key equation for alternant codes, where S is a syndrome polynomial. In decoding, a particular solution (Σ, Ω) ∈M is sought satisfying certain conditions, and such a solution can be found in a Gröbner basis of M. Applying techniques introduced in the first part of this paper, we give an algorithm which returns the required solution.

We investigate a class of Lee-metric alternant codes with symbols in Z p n , 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 two decoding algorithms. The first operates entirely over a Galois ring, while the second must be implemented over the associated residue field. The algorithms proceed by finding a Grobner basis of the module M of solutions to a key equation. We obtain a necessary characterisation 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 . Hence the required solution can be found in an appropriate Grobner basis of M .

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.

Delsarte showed that for any projective linear code over a finite field GF ( p r ) with two nonzero Hamming weights w 1 w 2 there exist positive integers u and s such that w 1 = p s u and w 2 = p s ( u + 1 ) . Moreover, he showed that the additive group of such a code has a strongly regular Cayley graph. Here we show that for any regular projective linear code C over a finite Frobenius ring with two integral nonzero homogeneous weights w 1 w 2 there is a positive integer d , a divisor of | C | , and positive integer u such that w 1 = d u and w 2 = d ( u + 1 ) . This gives a new proof of the known result that any such code yields a strongly regular graph. We apply these results to existence questions on two-weight codes.

Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to an APN Gold function if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2^n where n = 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function., 13 pg

We give a survey of results and applications relating to the theory of Grobner bases of ideals and modules where the coefficient ring is a finite commutative ring. For applications, we specialize to the case of a finite chain ring. We discuss and compare the main algorithms that may be implemented to compute Grobner and (in the case of a chain ring) Szekeres-like bases. We give an account of a number of decoding algorithms for alternant codes over commutative finite chain rings.

Miniaturized NMR is of growing importance in bio-, chemical, and -material sciences. Other than the magnet, bulky components are the radio-frequency power amplifier and the power supply or battery pack. We show that constant flip-angle excitation with phase modulation following a particular type of polyphase perfect sequences results in low peak excitation power at high response peak power. It has ideal power distribution in both the time domain and the frequency domain. A savings in peak excitation power of six orders of magnitude has been realized compared to conventionally pulsed excitation. Among others, the excitation promises to be of use for button-cell operated miniature NMR devices as well as for complying with specific-absorption-rate regulations in high-field medical imaging.

We present two infinite families of APN functions where the degree of the field is divisible by 3 but not 9. Our families contain two already known families as special cases. We also discuss the inequivalence proof (by computation) which shows that these functions are new., 12 pages, submitted to Cryptography and Communications

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates linear-programming based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the 'maximum-likelihood certificate' 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 linear-programming 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 the [11,6] ternary Golay code with ternary PSK modulation over 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 LDPC codes with corresponding PSK modulations over AWGN., To appear in the IEEE Transactions on Information Theory. 54 pages, 5 figures

In this paper we compute the Fourier spectra of some recently discovered binomial 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 BCH code. Furthermore, for fields of odd degree, our results provide an alternative proof of the APN property of the functions., 20 pages. Submitted to the SIAM Journal on Discrete Mathematics

We compute the Walsh spectrum and hence the nonlinearity of a new family of quadratic multi-term APN functions. We show that the distribution of values in the Walsh spectrum of these functions is the same as the Gold function.

It is known that a linear two-weight code $C$ over a finite field $\F_q$ corresponds both to a multiset in a projective space over $\F_q$ that meets every hyperplane in either $a$ or $b$ points for some integers $a, Comment: to appear in Designs Codes and Cryptography

In traditional algebraic coding theory the linear-programming bound is one of the most powerful and restrictive bounds for the existence of both linear and non-linear codes. This article develops a linear-programming bound for block codes on finite Frobenius rings.

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., Comment: 5 pages, to appear in 2008 IEEE International Symposium on Information Theory

We consider codes defined by a system of sparse polynomial parity check equations in F /sub 2/[x/sub 1/,...,x/sub n/]. We suggest that, defined in the right way, such codes admit an encoding comparable in efficiency with their linear counterparts (LDPC codes), and are suitable for iterative decoding.

We give a new algorithm for the solution of the Hamming metric decoding problem for alternant codes over a Galois ring R. First we develop a comprehensive theory of Grobner bases over R|x/sub 1/,...,x/sub n/|, which is of independent interest. By specialising to the case of one variable, we show that the solution of the key equation can be determined as a certain minimal element in a Grobner basis of the solution module.

The authors discovered some mistakes in the article that appeared on pp. 289---301 of the March volume of DCC 42 (2007). The validity of its results is not affected, nor is that of the examples since their computation did not involve the dual version of the LP bound. In any case, we feel the errors need to be rectified here.

We introduce the concept of a rank saturating system and outline its correspondence to a rank-metric code with a given covering radius. We consider the problem of finding the value of $s_{q^m/q}(k,\rho)$, which is the minimum $\mathbb{F}_q$-dimension of a $q$-system in $\mathbb{F}_{q^m}^k$ which is rank $\rho$-saturating. This is equivalent to the covering problem in the rank metric. We obtain upper and lower bounds on $s_{q^m/q}(k,\rho)$ and evaluate it for certain values of $k$ and $\rho$. We give constructions of rank $\rho$-saturating systems suggested from geometry.