# American Institute of Mathematical Sciences

ISSN:
1930-5346

eISSN:
1930-5338

All Issues

## Advances in Mathematics of Communications

February 2016 , Volume 10 , Issue 1

Select all articles

Export/Reference:

2016, 10(1): i-i doi: 10.3934/amc.2016.10.1i +[Abstract](1227) +[PDF](98.6KB)
Abstract:
The $4^{th}$International Castle Meeting on Coding Theory and its Applications (4ICMCTA) took place in the Palmela Castle, Portugal, on September 15--18, 2014. It was organized under the auspices of the Research & Development Center for Mathematics and Applications (CIDMA) from the University of Aveiro. Following in the spirit of the previous installments held at La Mota Castle, Spain, in 1999 and 2008, and at Cardona Castle, Spain, in 2011, the meeting has been a good opportunity for communicating new results, exchanging ideas, strengthening international cooperation, and introducing young researchers into the Coding Theory community.

2016, 10(1): 1-10 doi: 10.3934/amc.2016.10.1 +[Abstract](1448) +[PDF](319.4KB)
Abstract:
In previous papers [4,5,6] we gave the first example of a non-abelian group code using the group ring $F_5S_4$. It is natural to ask if it is really relevant that the group ring is semisimple. What happens if the field has characteristic $2$ or $3$? We have addressed this question, with computer help, proving that there are also examples of non-abelian group codes in the non-semisimple case. The results show some interesting differences between the cases of characteristic $2$ and $3$. Furthermore, using the group $SL(2,F_3)$, we construct a non-abelian group code over $F_2$ of length $24$, dimension $6$ and minimal weight $10$. This code is optimal in the following sense: every linear code over $F_2$ with length $24$ and dimension $6$ has minimum distance less than or equal to $10$. In the case of abelian group codes over $F_2$ the above value for the minimum distance cannot be achieved, since the minimum distance of a binary abelian group code with the given length and dimension 6 is at most 8.
2016, 10(1): 11-28 doi: 10.3934/amc.2016.10.11 +[Abstract](1280) +[PDF](385.0KB)
Abstract:
Product codes can be used to correct errors or recover erasures. In this work we consider the simplest form of a product code, this is, the single parity check (SPC) product code. This code has a minimum distance of four and is thus guaranteed to recover all single, double, and triple erasure patterns. The code is actually capable of recovering a higher number of erasure patterns. We count the number of uncorrectable erasure patterns of size $n \times n$ with $t$ erasures, for $t=8$, $2n-3$, $2n-2$ and $2n-1$, using the relation between erasure patterns and bipartite graphs.
2016, 10(1): 29-43 doi: 10.3934/amc.2016.10.29 +[Abstract](1342) +[PDF](422.5KB)
Abstract:
Let $\mathcal{M}_n(\mathbb{F})$be the algebra of $n \times n$ matrices over the finite field $\mathbb{F}$. In this paper we prove that the dual code of each ideal convolutional code in the skew-polynomial ring $\mathcal{M}_n(\mathbb{F})[z;\sigma_U]$ which is a direct summand as a left ideal, is also an ideal convolutional code over $\mathcal{M}_n(\mathbb{F})[z;\sigma_UT]$ and a direct summand as a left ideal. Moreover we provide an algorithm to decide if $\sigma_U$ is a separable automorphism and returns the corresponding separability element, when pertinent.
2016, 10(1): 45-52 doi: 10.3934/amc.2016.10.45 +[Abstract](1489) +[PDF](305.7KB)
Abstract:
For linear codes, the MacWilliams Extension Theorem states that each linear isometry of a linear code extends to a linear isometry of the whole space. But, in general, this is not the situation for nonlinear codes. In this paper codes over a vector space alphabet are considered. It is proved that if the length of such code is less than some threshold value, then an analogue of the MacWilliams Extension Theorem holds. One family of unextendable code isometries for the threshold value of code length is described.
2016, 10(1): 53-61 doi: 10.3934/amc.2016.10.53 +[Abstract](1373) +[PDF](324.2KB)
Abstract:
Minimal linear codes are linear codes such that the support of every codeword does not contain the support of another linearly independent codeword. Such codes have applications in cryptography, e.g. to secret sharing. We pursue here their study and construct improved asymptotically good families of minimal linear codes. We also consider quasi-minimal, $t$-minimal, and $t$-quasi-minimal linear codes, which are new variations on this notion.
2016, 10(1): 63-78 doi: 10.3934/amc.2016.10.63 +[Abstract](1572) +[PDF](374.3KB)
Abstract:
This paper deals with the probability that random linear systems defined over a finite field are reachable. Explicit formulas are derived for the probabilities that a linear input-state system is reachable, that the reachability matrix has a prescribed rank, as well as for the number of cyclic vectors of a cyclic matrix. We also estimate the probability that the parallel connection of finitely many single-input systems is reachable. These results may be viewed as a first step to calculate the probability that a network of linear systems is reachable.
2016, 10(1): 79-94 doi: 10.3934/amc.2016.10.79 +[Abstract](1440) +[PDF](359.7KB)
Abstract:
We propose a variation of Construction A of lattices from linear codes defined using the quotient $\Lambda/\mathfrak{p}\Lambda$ of some order $\Lambda$ inside a cyclic division $F$-algebra, for $\mathfrak{p}$ a prime ideal of a number field $F$. To obtain codes over this quotient, we first give an isomorphism between $\Lambda/\mathfrak{p}\Lambda$ and a ring of skew polynomials. We then discuss definitions and basic properties of skew polynomial codes, which are needed for Construction A, but also explore further properties of the dual of such codes. We conclude by providing an application to space-time coding, which is the original motivation to consider cyclic division $F$-algebras as a starting point for this variation of Construction A.
2016, 10(1): 95-112 doi: 10.3934/amc.2016.10.95 +[Abstract](1738) +[PDF](404.3KB)
Abstract:
In this paper we show how linear network coding can reduce the number of queries needed to retrieve one specific message among $k$ distinct ones replicated across a large number of randomly accessed nodes storing one message each. Without network coding, this would require $k$ queries on average. After proving that no scheme can perform better than a straightforward lower bound of $0.5k$ average queries, we propose and asymptotically evaluate, using mean field arguments, a few example practical schemes, the best of which attains $0.794k$ queries on average. The paper opens two complementary challenges: a systematic analysis of practical schemes so as to identify the best performing ones and design guideline strategies, as well as the need to identify tighter, nontrivial, lower bounds.
2016, 10(1): 113-130 doi: 10.3934/amc.2016.10.113 +[Abstract](1599) +[PDF](366.8KB)
Abstract:
We consider orbit codes, namely subspace codes obtained from orbits of the action of subgroups of $GL_n(\mathbb{F}_q)$ on $m$-dimensional subspaces of $\mathbb{F}_q^n$. We discuss their applicability to design storage codes, in particular in the context of collaborative repair: we identify known storage codes that can be interpreted as orbit codes, motivate why orbit codes provide good candidates for storage codes, and translate the storage code parameters into those of the algebraic objects involved. Two simple families of storage orbit codes are given.
2016, 10(1): 131-150 doi: 10.3934/amc.2016.10.131 +[Abstract](1975) +[PDF](502.5KB)
Abstract:
We recall why linear codes with complementary duals (LCD codes) play a role in counter-measures to passive and active side-channel analyses on embedded cryptosystems. The rate and the minimum distance of such LCD codes must be as large as possible. We recall the known primary construction of such codes with cyclic codes, and investigate other constructions, with expanded Reed-Solomon codes and generalized residue codes, for which we study the idempotents. These constructions do not allow to reach all the desired parameters. We study then those secondary constructions which preserve the LCD property, and we characterize conditions under which codes obtained by direct sum, direct product, puncturing, shortening, extending codes, or obtained by the Plotkin sum, can be LCD.
2016, 10(1): 151-162 doi: 10.3934/amc.2016.10.151 +[Abstract](1522) +[PDF](390.0KB)
Abstract:
We study fibre products of an arbitrary number of Kummer covers of the projective line over $\mathbb{F}_q$ under suitable weak assumptions. If $q-1 = r^a$ for some prime $r$, then we completely determine the number of rational points over a rational point of the projective line. Using this result we obtain explicit examples of fibre products of three Kummer covers supplying new entries for the current table of curves with many points (http://www.manypoints.org, October 31 2015).
2016, 10(1): 163-177 doi: 10.3934/amc.2016.10.163 +[Abstract](1498) +[PDF](354.0KB)
Abstract:
In this paper we introduce a special class of 2D convolutional codes, called composition codes, which admit encoders $G(d_1,d_2)$ that can be decomposed as the product of two 1D encoders, i.e., $G(d_1,d_2)=G_2(d_2)G_1(d_1)$. Taking into account this decomposition, we obtain syndrome formers of the code directly from $G_1(d_1)$ and $G_2(d_2)$, in case $G_1(d_1)$ and $G_2(d_2)$ are right prime. Moreover we consider 2D state-space realizations by means of a separable Roesser model of the encoders and syndrome formers of a composition code and we investigate the minimality of such realizations. In particular, we obtain minimal realizations for composition codes which admit an encoder $G(d_1,d_2)=G_2(d_2)G_1(d_1)$ with $G_2(d_2)$ a systematic 1D encoder. Finally, we investigate the minimality of 2D separable Roesser state-space realizations for syndrome formers of these codes.
2016, 10(1): 179-193 doi: 10.3934/amc.2016.10.179 +[Abstract](1477) +[PDF](560.0KB)
Abstract:
In this paper we address the problem of decoding $2$D convolutional codes over an erasure channel. To this end we introduce the notion of neighbors around a set of erasures which can be considered an analogue of the notion of sliding window in the context of $1$D convolutional codes. The main idea is to reduce the decoding problem of $2$D convolutional codes to a problem of decoding a set of associated $1$D convolutional codes. We first show how to recover sets of erasures that are distributed on vertical, horizontal and diagonal lines. Finally we outline some ideas to treat any set of erasures distributed randomly on the $2$D plane.
2016, 10(1): 195-207 doi: 10.3934/amc.2016.10.195 +[Abstract](1504) +[PDF](319.8KB)
Abstract:
We outline the algorithm for computing the minimum weight of a linear code over a finite field that was invented by A.~Brouwer and later extended by K.-H. Zimmermann. We show that matroid partitioning algorithms can be used to efficiently find a favourable (and sometimes best possible) sequence of information sets on which the Brouwer-Zimmermann algorithm operates. We present a new algorithm for computing the minimum weight of a linear code. We use a large set of codes to compare our new algorithm with the Brouwer-Zimmermann algorithm. We find that for about one third of codes in this sample set, our algorithm requires to generate fewer codewords than the Brouwer-Zimmermann algorithm.

2018  Impact Factor: 0.879