ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
May 2016 , Volume 10 , Issue 2
Select all articles
Export/Reference:
2016, 10(2): 209-220
doi: 10.3934/amc.2016001
+[Abstract](3148)
+[PDF](377.6KB)
Abstract:
For projective varieties defined over a finite field ${\mathbb F}_q$ we show that they contain a unique subvariety that satisfies the Finite Field Nullstellensatz property [1,2], for homogeneous linear polynomials over ${\mathbb F}_q$. Using these subvarieties we construct linear codes and estimate some of their parameters.
For projective varieties defined over a finite field ${\mathbb F}_q$ we show that they contain a unique subvariety that satisfies the Finite Field Nullstellensatz property [1,2], for homogeneous linear polynomials over ${\mathbb F}_q$. Using these subvarieties we construct linear codes and estimate some of their parameters.
2016, 10(2): 221-228
doi: 10.3934/amc.2016002
+[Abstract](3163)
+[PDF](531.3KB)
Abstract:
Triangular transformation method (TTM) is one of the multivariate public key cryptosystems (MPKC) based on the intractability of tame decomposition problem. In TTM, a special class of tame automorphisms are used to construct encryption schemes. However, because of the specificity of such tame automorphisms, it is important to evaluate the computational complexity of the tame decomposition problem for secure use of MPKC. In this paper, as the first step for security evaluations, we focus on Matsumoto-Imai cryptosystems. We shall prove that the Matsumoto-Imai central maps in three variables over $\mathbb{F}_{2}$ is tame, and we describe the tame decompositions of the Matsumoto-Imai central maps.
Triangular transformation method (TTM) is one of the multivariate public key cryptosystems (MPKC) based on the intractability of tame decomposition problem. In TTM, a special class of tame automorphisms are used to construct encryption schemes. However, because of the specificity of such tame automorphisms, it is important to evaluate the computational complexity of the tame decomposition problem for secure use of MPKC. In this paper, as the first step for security evaluations, we focus on Matsumoto-Imai cryptosystems. We shall prove that the Matsumoto-Imai central maps in three variables over $\mathbb{F}_{2}$ is tame, and we describe the tame decompositions of the Matsumoto-Imai central maps.
2016, 10(2): 229-254
doi: 10.3934/amc.2016003
+[Abstract](3922)
+[PDF](564.0KB)
Abstract:
This article aims to explore the bridge between the algebraic structure of a linear code and the complete decoding process. To this end, we associate a specific binomial ideal $I_+(\mathcal C)$ to an arbitrary linear code. The binomials involved in the reduced Gröbner basis of such an ideal relative to a degree-compatible ordering induce a uniquely defined test-set for the code, and this allows the description of a Hamming metric decoding procedure. Moreover, the binomials involved in the Graver basis of $I_+(\mathcal C)$ provide a universal test-set which turns out to be a set containing the set of codewords of minimal support of the code.
This article aims to explore the bridge between the algebraic structure of a linear code and the complete decoding process. To this end, we associate a specific binomial ideal $I_+(\mathcal C)$ to an arbitrary linear code. The binomials involved in the reduced Gröbner basis of such an ideal relative to a degree-compatible ordering induce a uniquely defined test-set for the code, and this allows the description of a Hamming metric decoding procedure. Moreover, the binomials involved in the Graver basis of $I_+(\mathcal C)$ provide a universal test-set which turns out to be a set containing the set of codewords of minimal support of the code.
2016, 10(2): 255-273
doi: 10.3934/amc.2016004
+[Abstract](3169)
+[PDF](473.1KB)
Abstract:
In this paper, cyclic codes over the Galois ring ${\rm GR}({p^2},s)$ are studied. The main result is the characterization and enumeration of Hermitian self-dual cyclic codes of length $p^a$ over ${\rm GR}({p^2},s)$. Combining with some known results and the standard Discrete Fourier Transform decomposition, we arrive at the characterization and enumeration of Euclidean self-dual cyclic codes of any length over ${\rm GR}({p^2},s)$.
In this paper, cyclic codes over the Galois ring ${\rm GR}({p^2},s)$ are studied. The main result is the characterization and enumeration of Hermitian self-dual cyclic codes of length $p^a$ over ${\rm GR}({p^2},s)$. Combining with some known results and the standard Discrete Fourier Transform decomposition, we arrive at the characterization and enumeration of Euclidean self-dual cyclic codes of any length over ${\rm GR}({p^2},s)$.
2016, 10(2): 275-290
doi: 10.3934/amc.2016005
+[Abstract](3383)
+[PDF](413.8KB)
Abstract:
This paper revisits strongly-MDS convolutional codes with maximum distance profile (MDP). These are (non-binary) convolutional codes that have an optimum sequence of column distances and attains the generalized Singleton bound at the earliest possible time frame. These properties make these convolutional codes applicable over the erasure channel, since they are able to correct a large number of erasures per time interval. The existence of these codes have been shown only for some specific cases. This paper shows by construction the existence of convolutional codes that are both strongly-MDS and MDP for all choices of parameters.
This paper revisits strongly-MDS convolutional codes with maximum distance profile (MDP). These are (non-binary) convolutional codes that have an optimum sequence of column distances and attains the generalized Singleton bound at the earliest possible time frame. These properties make these convolutional codes applicable over the erasure channel, since they are able to correct a large number of erasures per time interval. The existence of these codes have been shown only for some specific cases. This paper shows by construction the existence of convolutional codes that are both strongly-MDS and MDP for all choices of parameters.
2016, 10(2): 291-306
doi: 10.3934/amc.2016006
+[Abstract](2721)
+[PDF](459.0KB)
Abstract:
The projection construction has been used to construct semifields of odd characteristic using a field and a twisted semifield [Commutative semifields from projection mappings, Designs, Codes and Cryptography, 61 (2011), 187--196]. We generalize this idea to a projection construction using two twisted semifields to construct semifields of odd characteristic. Planar functions and semifields have a strong connection so this also constructs new planar functions.
The projection construction has been used to construct semifields of odd characteristic using a field and a twisted semifield [Commutative semifields from projection mappings, Designs, Codes and Cryptography, 61 (2011), 187--196]. We generalize this idea to a projection construction using two twisted semifields to construct semifields of odd characteristic. Planar functions and semifields have a strong connection so this also constructs new planar functions.
2016, 10(2): 307-319
doi: 10.3934/amc.2016007
+[Abstract](3102)
+[PDF](381.0KB)
Abstract:
The interpolation-based decoding that was developed for general evaluation AG codes is shown to be equally applicable to general differential AG codes. A performance analysis of the decoding algorithm, which is parallel to that of its companion algorithm, is reported. In particular, the decoding capacities of evaluation AG codes and differential AG codes are seen to be interrelated symmetrically. As an interesting special case, a decoding algorithm for classical Goppa codes is presented.
The interpolation-based decoding that was developed for general evaluation AG codes is shown to be equally applicable to general differential AG codes. A performance analysis of the decoding algorithm, which is parallel to that of its companion algorithm, is reported. In particular, the decoding capacities of evaluation AG codes and differential AG codes are seen to be interrelated symmetrically. As an interesting special case, a decoding algorithm for classical Goppa codes is presented.
2016, 10(2): 321-331
doi: 10.3934/amc.2016008
+[Abstract](2906)
+[PDF](394.0KB)
Abstract:
A sequence is called perfect if its autocorrelation function is a delta function. In this paper, we give a new definition of autocorrelation function: $\omega$-cyclic-conjugated autocorrelation. As a result, we present several classes of $\omega$-cyclic-conjugated-perfect quaternary Golay sequences, where $\omega=\pm 1$. We also considered such perfect property for $4^q$-QAM Golay sequences, $q\ge 2$ being an integer.
A sequence is called perfect if its autocorrelation function is a delta function. In this paper, we give a new definition of autocorrelation function: $\omega$-cyclic-conjugated autocorrelation. As a result, we present several classes of $\omega$-cyclic-conjugated-perfect quaternary Golay sequences, where $\omega=\pm 1$. We also considered such perfect property for $4^q$-QAM Golay sequences, $q\ge 2$ being an integer.
2016, 10(2): 333-354
doi: 10.3934/amc.2016009
+[Abstract](3295)
+[PDF](448.1KB)
Abstract:
Communication over channels that may vary in an arbitrary and unknown manner from channel use to channel use is studied. Such channels fall in the framework of arbitrarily varying channels (AVCs), for which it has been shown that the classical deterministic approaches with pre-specified encoder and decoder fail if the AVC is symmetrizable. However, more sophisticated strategies such as common randomness (CR) assisted codes or list decoding are capable to resolve the ambiguity induced by symmetrizable AVCs. AVCs further serve as the indispensable basis for modeling adversarial attacks such as jamming in information theoretic security related communication problems. In this paper, we study the arbitrarily varying multiple access channel (AVMAC) with conferencing encoders, which models the communication scenario with two cooperating transmitters and one receiver. This can be motivated for example by cooperating base stations or access points in future systems. The capacity region of the AVMAC with conferencing encoders is established and it is shown that list decoding allows for reliable communication also for symmetrizable AVMACs. The list capacity region equals the CR-assisted capacity region for large enough list size. Finally, for fixed probability of decoding error the amount of resources, i.e., CR or list size, is quantified and shown to be finite.
Communication over channels that may vary in an arbitrary and unknown manner from channel use to channel use is studied. Such channels fall in the framework of arbitrarily varying channels (AVCs), for which it has been shown that the classical deterministic approaches with pre-specified encoder and decoder fail if the AVC is symmetrizable. However, more sophisticated strategies such as common randomness (CR) assisted codes or list decoding are capable to resolve the ambiguity induced by symmetrizable AVCs. AVCs further serve as the indispensable basis for modeling adversarial attacks such as jamming in information theoretic security related communication problems. In this paper, we study the arbitrarily varying multiple access channel (AVMAC) with conferencing encoders, which models the communication scenario with two cooperating transmitters and one receiver. This can be motivated for example by cooperating base stations or access points in future systems. The capacity region of the AVMAC with conferencing encoders is established and it is shown that list decoding allows for reliable communication also for symmetrizable AVMACs. The list capacity region equals the CR-assisted capacity region for large enough list size. Finally, for fixed probability of decoding error the amount of resources, i.e., CR or list size, is quantified and shown to be finite.
2016, 10(2): 355-365
doi: 10.3934/amc.2016010
+[Abstract](3576)
+[PDF](332.3KB)
Abstract:
We present bounds on the number of points in algebraic curves and algebraic hypersurfaces in $\mathbb{P}^n(\mathbb{F}_q)$ of small degree $d$, depending on the number of linear components contained in such curves and hypersurfaces. The obtained results have applications to the weight distribution of the projective Reed-Muller codes PRM$(q,d,n)$ over the finite field $\mathbb{F}_q$.
We present bounds on the number of points in algebraic curves and algebraic hypersurfaces in $\mathbb{P}^n(\mathbb{F}_q)$ of small degree $d$, depending on the number of linear components contained in such curves and hypersurfaces. The obtained results have applications to the weight distribution of the projective Reed-Muller codes PRM$(q,d,n)$ over the finite field $\mathbb{F}_q$.
2016, 10(2): 367-377
doi: 10.3934/amc.2016011
+[Abstract](2771)
+[PDF](316.8KB)
Abstract:
The geometric structure of any relative one-weight code is determined, and by using this geometric structure, the support weight distribution of subcodes of any relative one-weight code is presented. An application of relative one-weight codes to the wire-tap channel of type II with multiple users is given, and certain kinds of relative one-weight codes all of whose nonzero codewords are minimal are determined.
The geometric structure of any relative one-weight code is determined, and by using this geometric structure, the support weight distribution of subcodes of any relative one-weight code is presented. An application of relative one-weight codes to the wire-tap channel of type II with multiple users is given, and certain kinds of relative one-weight codes all of whose nonzero codewords are minimal are determined.
2016, 10(2): 379-391
doi: 10.3934/amc.2016012
+[Abstract](3554)
+[PDF](350.1KB)
Abstract:
We study codes over the commutative local Frobenius rings of order 16 with maximal ideals of size 8. We define a weight preserving Gray map and study the images of these codes as binary codes. We study self-dual codes and determine when they exist.
We study codes over the commutative local Frobenius rings of order 16 with maximal ideals of size 8. We define a weight preserving Gray map and study the images of these codes as binary codes. We study self-dual codes and determine when they exist.
2016, 10(2): 393-399
doi: 10.3934/amc.2016013
+[Abstract](3845)
+[PDF](321.8KB)
Abstract:
Ternary constant weight codes of length $n=2^m$, weight $n-1$, cardinality $2^n$ and distance $5$ are known to exist for every $m$ for which there exists an APN permutation of order $2^m$, that is, at least for all odd $m \geq 3$ and for $m=6$. We show the non-existence of such codes for $m=4$ and prove that any codes with the parameters above are diameter perfect.
Ternary constant weight codes of length $n=2^m$, weight $n-1$, cardinality $2^n$ and distance $5$ are known to exist for every $m$ for which there exists an APN permutation of order $2^m$, that is, at least for all odd $m \geq 3$ and for $m=6$. We show the non-existence of such codes for $m=4$ and prove that any codes with the parameters above are diameter perfect.
2016, 10(2): 401-411
doi: 10.3934/amc.2016014
+[Abstract](2787)
+[PDF](387.3KB)
Abstract:
A sequence of period $n$ is called a nearly perfect sequence of type $\gamma$ if all out-of-phase autocorrelation coefficients are a constant $\gamma$. In this paper we study nearly perfect sequences (NPS) via their connection to direct product difference sets (DPDS). We prove the connection between a $p$-ary NPS of period $n$ and type $\gamma$ and a cyclic $(n,p,n,\frac{n-\gamma}{p}+\gamma,0,\frac{n-\gamma}{p})$-DPDS for an arbitrary integer $\gamma$. Next, we present the necessary conditions for the existence of a $p$-ary NPS of type $\gamma$. We apply this result for excluding the existence of some $p$-ary NPS of period $n$ and type $\gamma$ for $n \leq 100$ and $\vert \gamma \vert \leq 2$. We also prove the similar results for an almost $p$-ary NPS of type $\gamma$. Finally, we show the non-existence of some almost $p$-ary perfect sequences by showing the non-existence of equivalent cyclic relative difference sets by using the notion of multipliers.
A sequence of period $n$ is called a nearly perfect sequence of type $\gamma$ if all out-of-phase autocorrelation coefficients are a constant $\gamma$. In this paper we study nearly perfect sequences (NPS) via their connection to direct product difference sets (DPDS). We prove the connection between a $p$-ary NPS of period $n$ and type $\gamma$ and a cyclic $(n,p,n,\frac{n-\gamma}{p}+\gamma,0,\frac{n-\gamma}{p})$-DPDS for an arbitrary integer $\gamma$. Next, we present the necessary conditions for the existence of a $p$-ary NPS of type $\gamma$. We apply this result for excluding the existence of some $p$-ary NPS of period $n$ and type $\gamma$ for $n \leq 100$ and $\vert \gamma \vert \leq 2$. We also prove the similar results for an almost $p$-ary NPS of type $\gamma$. Finally, we show the non-existence of some almost $p$-ary perfect sequences by showing the non-existence of equivalent cyclic relative difference sets by using the notion of multipliers.
2016, 10(2): 413-427
doi: 10.3934/amc.2016015
+[Abstract](3492)
+[PDF](358.3KB)
Abstract:
It is well known that the main problem of decoding the extended Reed-Solomon codes is computing the error distance of a word. Using some algebraic constructions, we are able to determine the error distance of words whose degrees are $k+1$ and $k+2$ to the extended Reed-Solomon codes. As a corollary, we can simply get the results of Zhang-Fu-Liao on the deep hole problem of Reed-Solomon codes.
It is well known that the main problem of decoding the extended Reed-Solomon codes is computing the error distance of a word. Using some algebraic constructions, we are able to determine the error distance of words whose degrees are $k+1$ and $k+2$ to the extended Reed-Solomon codes. As a corollary, we can simply get the results of Zhang-Fu-Liao on the deep hole problem of Reed-Solomon codes.
2016, 10(2): 429-436
doi: 10.3934/amc.2016016
+[Abstract](2773)
+[PDF](279.9KB)
Abstract:
Compressed sensing is a technique which is to used to reconstruct a sparse signal given few measurements of the signal. One of the main problems in compressed sensing is the deterministic construction of the sensing matrix. Li et al. introduced a new deterministic construction via algebraic-geometric codes (AG codes) and gave an upper bound for the coherence of the sensing matrices coming from AG codes. In this paper, we give the exact value of the coherence of the sensing matrices coming from AG codes in terms of the minimum distance of AG codes and deduce the upper bound given by Li et al. We also give formulas for the coherence of the sensing matrices coming from Hermitian two-point codes.
Compressed sensing is a technique which is to used to reconstruct a sparse signal given few measurements of the signal. One of the main problems in compressed sensing is the deterministic construction of the sensing matrix. Li et al. introduced a new deterministic construction via algebraic-geometric codes (AG codes) and gave an upper bound for the coherence of the sensing matrices coming from AG codes. In this paper, we give the exact value of the coherence of the sensing matrices coming from AG codes in terms of the minimum distance of AG codes and deduce the upper bound given by Li et al. We also give formulas for the coherence of the sensing matrices coming from Hermitian two-point codes.
2016, 10(2): 437-457
doi: 10.3934/amc.2016017
+[Abstract](3295)
+[PDF](481.4KB)
Abstract:
Let $\mathbb{F}_{p^m}$ be a finite field with $p^m$ elements, where $p$ is an odd prime, and $m$ is a positive integer. Let $h_1(x)$ and $h_2(x)$ be minimal polynomials of $-\pi^{-1}$ and $\pi^{-\frac{p^k+1}{2}}$ over $\mathbb{F}_p$, respectively, where $\pi $ is a primitive element of $\mathbb{F}_{p^m}$, and $k$ is a positive integer such that $\frac{m}{\gcd(m,k)}\geq 3$. In [23], Zhou et al. obtained the weight distribution of a class of cyclic codes over $\mathbb{F}_p$ with parity-check polynomial $h_1(x)h_2(x)$ in the following two cases:
• $k$ is even and $\gcd(m,k)$ is odd;
• $\frac{m}{\gcd(m,k)}$ and $\frac{k}{\gcd(m,k)}$ are both odd. In this paper, we further investigate this class of cyclic codes over $\mathbb{F}_p$ in other cases. We determine the weight distribution of this class of cyclic codes.
Let $\mathbb{F}_{p^m}$ be a finite field with $p^m$ elements, where $p$ is an odd prime, and $m$ is a positive integer. Let $h_1(x)$ and $h_2(x)$ be minimal polynomials of $-\pi^{-1}$ and $\pi^{-\frac{p^k+1}{2}}$ over $\mathbb{F}_p$, respectively, where $\pi $ is a primitive element of $\mathbb{F}_{p^m}$, and $k$ is a positive integer such that $\frac{m}{\gcd(m,k)}\geq 3$. In [23], Zhou et al. obtained the weight distribution of a class of cyclic codes over $\mathbb{F}_p$ with parity-check polynomial $h_1(x)h_2(x)$ in the following two cases:
• $k$ is even and $\gcd(m,k)$ is odd;
• $\frac{m}{\gcd(m,k)}$ and $\frac{k}{\gcd(m,k)}$ are both odd. In this paper, we further investigate this class of cyclic codes over $\mathbb{F}_p$ in other cases. We determine the weight distribution of this class of cyclic codes.
2016, 10(2): 459-474
doi: 10.3934/amc.2016018
+[Abstract](3159)
+[PDF](423.1KB)
Abstract:
In this paper we study the family of cyclic codes such that its minimum distance reaches the maximum of its BCH bounds. We also show a way to construct cyclic codes with that property by means of computations of some divisors of a polynomial of the form $x^n-1$. We apply our results to the study of those BCH codes $C$, with designed distance $\delta$, that have minimum distance $d(C)=\delta$. Finally, we present some examples of new binary BCH codes satisfying that condition. To do this, we make use of two related tools: the discrete Fourier transform and the notion of apparent distance of a code, originally defined for multivariate abelian codes.
In this paper we study the family of cyclic codes such that its minimum distance reaches the maximum of its BCH bounds. We also show a way to construct cyclic codes with that property by means of computations of some divisors of a polynomial of the form $x^n-1$. We apply our results to the study of those BCH codes $C$, with designed distance $\delta$, that have minimum distance $d(C)=\delta$. Finally, we present some examples of new binary BCH codes satisfying that condition. To do this, we make use of two related tools: the discrete Fourier transform and the notion of apparent distance of a code, originally defined for multivariate abelian codes.
2020
Impact Factor: 0.935
5 Year Impact Factor: 0.976
2020 CiteScore: 1.5
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]