De Bruijn sequences are cyclic sequences of length that contain every binary word of length exactly once. The construction of many such sequences of a given order is useful for the generation of stream ciphers. One method of constructing sequences makes use of a homomorphism from the de Bruijn graph of order to the graph of order . The preimages of a de Bruijn sequence under this homomorphism form two cycles which may be joined at certain points. We examine a par- ticular method for identifying such points when the sequence in question is recursively constructed in this manner. Using the structure of the con- struction, we are able to calculate sums of subsequences in time, and the location of a given word in time. Together, these functions allow a check to be made for the validity of any potential toggle point. This provides a method for efficiently generating a recursive specification for such sequences, each successful step of which takes , for from 3 to n.
Let be an odd prime and consider the finite field . Given a linear code , we use algebraic number theory to construct an associated lattice for an algebraic number field and the ring of integers of . We attach a theta series to the lattice and prove a relation between and the complete weight enumerator evaluated on weight one theta series.
We investigate the structure of the code graph of a multicast network that has a characteristic shape of an inverted equilateral triangle. We provide a criterion that determines the validity of a receiver placement within the code graph, present invariance properties of the determinants corresponding to receiver placements under symmetries, and provide a complete study of these networks’ receivers and required field sizes up to a network of 4 sources. We also improve on various definitions related to code graphs.
A linear code with the property that is said to be a linear complementary dual, or LCD, code. In this paper, we consider generalized affine Cartesian codes which are LCD. Generalized affine Cartesian codes arise naturally as the duals of affine Cartesian codes in the same way that generalized Reed–Solomon codes arise as duals of Reed–Solomon codes. Generalized affine Cartesian codes are evaluation codes constructed by evaluating multivariate polynomials of bounded degree at points in an m-dimensional Cartesian set over a finite field K and scaling the coordinates. The LCD property depends on the scalars used. Because Reed–Solomon codes are a special case, we obtain a characterization of those generalized Reed–Solomon codes which are LCD along with the more general result for generalized affine Cartesian codes. These results are independent of the characteristic of the underlying field.
A skew polynomial ring is a ring of polynomials with non-commutative multiplication. This creates a difference between left and right divisibility, evaluations, and roots. A polynomial in such a ring may have more roots than its degree, which leads to the concepts of closures and independent sets of roots. In , this leads to the matroids and of right independent and left independent sets, which are isomorphic via the extension of the map defined by , where . Extending the field of coefficients of R results in a new ring of which is a subring, and if the extension is taken to include roots of an evaluation polynomial of , then all roots of in are in the same conjugacy class.
Batch codes, introduced by Ishai et al., encode a string into an -tuple of strings, called buckets. In this paper we consider multiset batch codes wherein a set of -users wish to access one bit of information each from the original string. We introduce a concept of optimal batch codes. We first show that binary Hamming codes are optimal batch codes. The main body of this work provides batch properties of Reed-Muller codes. We look at locality and availability properties of first order Reed-Muller codes over any finite field. We then show that binary first order Reed-Muller codes are optimal batch codes when the number of users is 4 and generalize our study to the family of binary Reed-Muller codes which have order less than half their length.
We approach the problem of linear network coding for multicast networks from different perspectives. We introduce the notion of the coding points of a network, which are edges of the network where messages combine and coding occurs. We give an integer linear program that leads to choices of paths through the network that minimize the number of coding points. We introduce the code graph of a network, a simplified directed graph that maintains the information essential to understanding the coding properties of the network. One of the main problems in network coding is to understand when the capacity of a multicast network is achieved with linear network coding over a finite field of size q. We explain how this problem can be interpreted in terms of rational points on certain algebraic varieties.
This paper considers distributed storage systems (DSSs) from a graph theoretic perspective. A DSS is constructed by means of the path decomposition of a 3-regular graph into paths. The paths represent the disks of the DSS and the edges of the graph act as the blocks of storage. We deduce the properties of the DSS from a related graph and show their optimality.
Over a finite field , the evaluation of skew polynomials is intimately related to the evaluation of linearized polynomials. This connection allows one to relate the concept of polynomial independence defined for skew polynomials to the familiar concept of linear independence for vector spaces. This relation allows for the definition of a representable matroid called the -matroid, with rank function that makes it a metric space. Specific submatroids of this matroid are individually bijectively isometric to the projective geometry of equipped with the subspace metric. This isometry allows one to use the -matroid in a matroidal network coding application.
Skew polynomials are elements of a noncommutative ring that, in recent years, have found applications in coding theory and cryptography. Skew polynomials have a well-defined evaluation map. This map leads to the definition of a class of codes called Generalized Skew-Evaluation codes that contains Gabidulin codes as a special case as well as other related codes with additional desirable properties. A Berlekamp-Welch-type decoder for an important class of these codes can be constructed using Kötter interpolation in skew polynomial rings.
A spread code is a set of vector spaces of a fixed dimension over a finite field with certain properties used for random network coding. It can be constructed in different ways which lead to different decoding algorithms. In this work we consider one such representation of spread codes and present a minimum distance decoding algorithm which is efficient when the code words, the received space and the error space have small dimension.
A constant dimension code consists of a set of k-dimensional subspaces of . Orbit codes are constant dimension codes which are defined as orbits of a subgroup of the general linear group, acting on the set of all subspaces of . If the acting group is cyclic, the corresponding orbit codes are called cyclic orbit codes. In this paper, we show how orbit codes can be seen as an analog of linear codes in the block coding case. We investigate how the structure of cyclic orbit codes can be utilized to compute the minimum distance and cardinality of a given code and propose different decoding procedures for a particular subclass of cyclic orbit codes.
Skew polynomials are a noncommutative generalization of ordinary polynomials that, in recent years, have found applications in coding theory and cryptography. Viewed as functions, skew polynomials have a well-defined evaluation map; however, little is known about skew-polynomial interpolation. In this work, we apply Kötter’s interpolation framework to free modules over skew polynomial rings. As a special case, we introduce a simple interpolation algorithm akin to Newton interpolation for ordinary polynomials.
In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size with entries in a finite field . Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires operations over an extension field . Our algorithm is more efficient than the previous ones in the literature, when the dimension of the codewords is small with respect to . The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.
Orbit codes are a family of codes applicable for communications on a random linear network coding channel. The paper focuses on the classification of these codes. We start by classifying the conjugacy classes of cyclic subgroups of the general linear group. As a result, we are able to focus the study of cyclic orbit codes to a restricted family of them.
We introduce a new class of constant dimension codes called orbit codes. The basic properties of these codes are derived. It will be shown that many of the known families of constant dimension codes in the literature are actually orbit codes.
In this paper we introduce the class of spread codes for the use in random network coding. Spread codes are based on the construction of spreads in finite projective geometry. The major contribution of the paper is an efficient decoding algorithm of spread codes up to half the minimum distance.
In this article, we illustrate an algorithm for the computation of the weight distribution of CRC codes. The recursive structure of CRC codes will give us an iterative way to compute the weight distribution of their dual codes starting from some “representative” words. Thanks to MacWilliams’ Theorem, the computation of the weight distribution of the dual codes can be easily brought back to that of CRC codes.
Her research project of on interference alignment of multiple unicast networks over finite fields.
Ryann joined the RTG group in August 2019. Her work during her doctoral studies was on multivariate key encryption.
Harrison is a master student workin on quantum error fault tollerant codes.
Travis is on track to complete his doctoral studies this academic year. His most recent research project is on de Bruijn sequences.