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.
A broad range of scientific simulations involve solving large-scale computationally expensive linear systems of equations. Iterative solvers are typically preferred over direct methods when it comes to large systems due to their lower memory requirements and shorter execution times. However, selecting the appropriate iterative solver is problem-specific and dependent on the type and symmetry of the coefficient matrix. Gauss-Seidel (GS) is an iterative method for solving linear systems that are either strictly diagonally dominant or symmetric positive definite. This technique is an improved version of Jacobi and typically converges in fewer iterations. However, the sequential nature of this algorithm complicates the parallel extraction. In fact, most parallel derivatives of GS rely on the sparsity pattern of the coefficient matrix and require matrix reordering or domain decomposition. In this article, we introduce a new algorithm that exploits the convergence property of GS and adapts the parallel structure of Jacobi. The proposed method works for both dense and sparse systems and is straightforward to implement. We have examined the performance of our method on multicore and many-core architectures. Experimental results demonstrate the superior performance of the proposed algorithm compared with GS and Jacobi. Additionally, performance comparison with built-in Krylov solvers in MATLAB showed that in terms of time per iteration, Krylov methods perform faster on CPUs, but our approach is significantly better when executed on GPUs. Lastly, we apply our method to solve the power flow problem, and the results indicate a significant improvement in runtime, reaching up to 87 times faster speed compared with GS.
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.
Dr. Machado joined the SMSS in August 2021 and his expertise are in coding theory and its applications to privacy and security.
Dr. Skelton joined the RTG group in August 2021. His expertises are in commutative algebra and combinatorics and will assist the RTG group in answering fundamental questions in coding theory and crypotography.
His research interest was in number theory and is now expanding it to coding theory and cryptography.
Her research interest is in post-quantum cryptography and is co-advised with Dr. Cartor.