Search

A well studied problem in algebraic complexity theory is the determination of the complexity of problems relying on evaluations of bilinear maps. One measure of the complexity of a bilinear map (or 3-tensor) is the optimal number of non-scalar multiplications required to evaluate it. This quantity is also described as its tensor rank, which is the smallest number of rank-1 matrices whose span contains its first slice space. In this paper we derive upper bounds on the tensor ranks of certain classes of 3-tensors and give explicit constructions of sets of rank-1 matrices containing their first slice spaces. We also show how these results can be applied in coding theory to derive upper bounds on the tensor rank of some rank-metric codes. In particular, we compute the tensor rank of some families of F q m -linear codes and we show that they are extremal with respect to Kruskal's tensor rank bound. [ABSTRACT FROM AUTHOR]

In this paper we focus on modules over a finite chain ring R of size q s. We compute the density of free modules of 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 R. Since linear codes over R are submodules of R n we get direct implications for coding theory. For example, we show that random codes achieve the Gilbert-Varshamov bound with high probability. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of list decoding of linear codes over an integer residue ring Z q , where q is a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Z p r , called the standard form, and the p -adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Z p r . From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field p r − 1 Z p r . This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. [ABSTRACT FROM AUTHOR]

Quantum maximal-distance-separable (MDS) codes are an important class of quantum codes. Recently, many scholars utilize constacyclic codes to construct some quantum MDS codes. In this paper, several new families of optimal asymmetric quantum codes and optimal quantum convolutional codes are constructed by using constacyclic codes. Moreover, these quantum codes constructed in this paper are different from the ones in the literature. [ABSTRACT FROM AUTHOR]

For any admissible value of the parameters n and k there exist [ n , k ] -Maximum Rank Distance F q -linear codes. Indeed, it can be shown that if field extensions large enough are considered, almost all rank metric codes are MRD. On the other hand, very few families up to equivalence of such codes are currently known. In the present paper we study some invariants of MRD codes and evaluate their value for the known families, providing a new characterization of generalized twisted Gabidulin codes. [ABSTRACT FROM AUTHOR]

In this paper we introduce symplectic Grassmann codes, in analogy to ordinary Grassmann codes and orthogonal Grassmann codes, as projective codes defined by symplectic Grassmannians. Lagrangian–Grassmannian codes are a special class of symplectic Grassmann codes. We describe all the parameters of line symplectic Grassmann codes and we provide the full weight enumerator for the Lagrangian–Grassmannian codes of rank 2 and 3. [ABSTRACT FROM AUTHOR]

In this paper we introduce a Cayley-type graph for group–subgroup pairs ( G , H ) and certain subsets S of G . We present some elementary properties of such graphs, including connectedness, degree and partition structure, and vertex-transitivity, relating these properties with those of the underlying group–subgroup pair. From the properties of the underlying structures, some of the eigenvalues can be determined, including the largest eigenvalue of the graph. We present a sufficient condition on the group–subgroup pair ( G , H ) and the size of S that results on bipartite Ramanujan graphs. Among those Ramanujan graphs there are graphs that cannot be obtained as Cayley graphs. As another application, we propose the use of group–subgroup pair graphs to model linear error-correcting codes. [ABSTRACT FROM AUTHOR]

Let Fq be a finite field with q elements and denote by θ: Fq → Fq an automorphism of Fq. In this paper, we deal with linear codes of Fq ninvariant under a semi-linear map T: Fq n → Fq n for somen ≥2. In particular, we study three kinds of their dual codes, some relations between them and we focus on codes which are products of module skew codes in the non-commutative polynomial ring as a subcase of linear codes invariant by a semi-linear map T. In this setting we give also an algorithm for encoding, decoding and detecting errors and we show a method to construct codes invariant under a fixed T. [ABSTRACT FROM AUTHOR]

Abstract: The projective space of order n over the finite field , denoted here as , is the set of all subspaces of the vector space . The projective space can be endowed with distance function which turns into a metric space. With this, an code in projective space is a subset of of size M such that the distance between any two codewords (subspaces) is at least d. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an code can correct t packet errors and packet erasures introduced (adversarially) anywhere in the network as long as . This motivates new interest in such codes. In this paper, we examine the two fundamental concepts of “complements” and “linear codes” in the context of . These turn out to be considerably more involved than their classical counterparts. These concepts are examined from two different points of view, coding theory and lattice theory. Our results reveal a number of surprising phenomena pertaining to complements and linearity in and gives rise to several interesting problems. [Copyright &y& Elsevier]

Abstract: In this paper two-dimensional convolutional codes with finite support are considered, i.e., convolutional codes whose codewords have compact support indexed in and take values in , where is a finite field. The main goal of this work is to analyze the (free) distance properties of this type of codes of rate and degree . We first establish an upper bound on the maximum possible distance for these codes. We then present particular constructions of two-dimensional convolutional codes with finite support of rate and degree that attain such a bound and therefore have the maximum distance among all two-dimensional convolutional codes with finite support with the same rate and degree. We call such codes maximum distance separable two-dimensional convolutional codes. [Copyright &y& Elsevier]

Abstract: Campopiano [C.N. Campopiano, Bounds on burst error correcting codes, IRE Trans. IT-8 (1962) 257–259] obtained an upper bound for burst error correction in classical coding systems where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F q equipped with the Hamming metric. In [S. Jain, Bursts in m-metric array codes, Linear Algebra Appl., in press], the author introduced the notion of burst errors for m-metric array coding systems where m-metric array codes are subsets/subspaces of the space Mat m×s (F q ), the linear space of all m × s matrices with entries from a finite field F q , endowed with a non-Hamming metric and obtained some lower bounds for burst error correction. In this paper, we obtain various construction upper bounds on the parameters of m-metric array codes for the detection and correction of burst errors. [Copyright &y& Elsevier]

Abstract: Fire [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959] introduced the concept of bursts for classical codes where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F q . In this paper, we introduce the notion of bursts for m-metric array codes where m-metric array codes are subsets/subspaces of the space Mat m×s (F q ), the linear space of all m × s matrices with entries from a finite field F q , endowed with a non-Hamming metric. We also obtain some bounds (analogous to Fire’s bound [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959], Rieger’s bound [S.H. Reiger, Codes for the correction of clustered errors, IRE-Trans., IT-6 (1960), 16–21] etc. in classical codes) on the parameters of m-metric array codes for the detection and correction of burst errors. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain bounds on the number of parity check digits for Lee weight codes correcting errors of Lee weight 1, errors of Lee weight 2 or less, errors of Lee weight 3 or less and errors of Lee weight 4 or less over Z q (q ⩾5, a prime) respectively. We also examine these bounds with equality to check for perfect codes and have shown the existence of perfect codes correcting errors of Lee weight 1 over Z 5 and perfect codes correcting errors of Lee weight 2 or less over Z 13. We have also shown the nonexistence of perfect codes correcting errors of Lee weight 2 or less over Z q when q =4n +3 (q prime) and correcting errors of Lee weight 3 or less and errors of Lee weight 4 or less over Z q (5⩽ q ⩽97, a prime). We further conjecture that there does not exist a perfect code correcting errors of Lee weight t or less (t ⩾3) over Z q (q ⩾5, a prime). [Copyright &y& Elsevier]

This paper is devoted to presenting two counterexamples to Shiromoto's (1999) results [2] on MacWilliams type identities with respect to Lee weight enumerators and Euclidean weight enumerators over Z ℓ . [ABSTRACT FROM AUTHOR]