
ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
February 2009 , Volume 3 , Issue 1
Select all articles
Export/Reference:
2009, 3(1): 1-11
doi: 10.3934/amc.2009.3.1
+[Abstract](3119)
+[PDF](163.6KB)
Abstract:
A type I presentation $S=R/J$ of an affine (order) domain has a weight function injective on the monomials in the footprint $\Delta(J)$. This can be extended naturally to a presentation, $\overline{R}/\overline{J}$, of the integral closure $ic(S)$. This presentation over $P$:$=F[x_n,\ldots,x_1]$ as an affine $P$-algebra relative to a corresponding grevlex-over-weight monomial ordering is shown to have a minimal, reduced Gröbner basis (for the ideal of relations $\overline{J}$) consisiting only of $P$-quadratic relations defining the multiplication of the $P$-module generators and possibly some $P$-linear relations if those generators are not independent over $P$. There then may be better choices for $P$ to minimize the number of $P$-module generators needed. The intended coding theory application is to the description of one-point AG codes, not only from curves (with $P=F[x_1]$) but also from higher-dimensional varieties.
A type I presentation $S=R/J$ of an affine (order) domain has a weight function injective on the monomials in the footprint $\Delta(J)$. This can be extended naturally to a presentation, $\overline{R}/\overline{J}$, of the integral closure $ic(S)$. This presentation over $P$:$=F[x_n,\ldots,x_1]$ as an affine $P$-algebra relative to a corresponding grevlex-over-weight monomial ordering is shown to have a minimal, reduced Gröbner basis (for the ideal of relations $\overline{J}$) consisiting only of $P$-quadratic relations defining the multiplication of the $P$-module generators and possibly some $P$-linear relations if those generators are not independent over $P$. There then may be better choices for $P$ to minimize the number of $P$-module generators needed. The intended coding theory application is to the description of one-point AG codes, not only from curves (with $P=F[x_1]$) but also from higher-dimensional varieties.
2009, 3(1): 13-27
doi: 10.3934/amc.2009.3.13
+[Abstract](4177)
+[PDF](275.6KB)
Abstract:
In this paper, we study batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky and Sahai in [4]. A batch code specifies a method to distribute a database of $n$ items among $m$ devices (servers) in such a way that any $k$ items can be retrieved by reading at most $t$ items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by $N$, over all $m$ servers.
We restrict out attention to batch codes in which every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a ''combinatorial batch code''. We only study the special case $t=1$, where, for various parameter situations, we are able to present batch codes that are optimal with respect to the storage requirement, $N$. We also study uniform codes, where every item is stored in precisely $c$ of the $m$ servers (such a code is said to have rate $1/c$). Interesting new results are presented in the cases $c = 2, k-2$ and $k-1$. In addition, we obtain improved existence results for arbitrary fixed $c$ using the probabilistic method.
In this paper, we study batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky and Sahai in [4]. A batch code specifies a method to distribute a database of $n$ items among $m$ devices (servers) in such a way that any $k$ items can be retrieved by reading at most $t$ items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by $N$, over all $m$ servers.
We restrict out attention to batch codes in which every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a ''combinatorial batch code''. We only study the special case $t=1$, where, for various parameter situations, we are able to present batch codes that are optimal with respect to the storage requirement, $N$. We also study uniform codes, where every item is stored in precisely $c$ of the $m$ servers (such a code is said to have rate $1/c$). Interesting new results are presented in the cases $c = 2, k-2$ and $k-1$. In addition, we obtain improved existence results for arbitrary fixed $c$ using the probabilistic method.
2009, 3(1): 29-34
doi: 10.3934/amc.2009.3.29
+[Abstract](2721)
+[PDF](123.3KB)
Abstract:
It is known that $m_6(2,9)=48$, where $m_r(2,q)$ denotes the maximum value of $m$ for which an $(m,r)$-arc exists in PG$(2,q)$. We prove that $(48,6)$-arcs in PG$(2,9)$ are unique up to projective equivalence.
It is known that $m_6(2,9)=48$, where $m_r(2,q)$ denotes the maximum value of $m$ for which an $(m,r)$-arc exists in PG$(2,q)$. We prove that $(48,6)$-arcs in PG$(2,9)$ are unique up to projective equivalence.
2009, 3(1): 35-52
doi: 10.3934/amc.2009.3.35
+[Abstract](2651)
+[PDF](211.3KB)
Abstract:
We investigate the distance vectors contained in individual Costas arrays and in pairs of Costas arrays, and prove some rigorous results in the case of the algebraically constructed arrays. Overall, it appears that the set with the property that every Costas array has a distance vector in this set, or that every pair of Costas arrays with a common vector have a common vector in this set, is in both cases surprisingly small. Further, we study Costas arrays with the additional property that they represent configurations of non-attacking kings or queens: in the former case, we demonstrate that such arrays are either sporadic or produced by a sub-method of the Lempel construction; in the latter case, partially answering a question asked by S. Golomb 26 years ago, we prove that (non-trivial) such arrays can only be sporadic and conjecture they do not exist at all.
We investigate the distance vectors contained in individual Costas arrays and in pairs of Costas arrays, and prove some rigorous results in the case of the algebraically constructed arrays. Overall, it appears that the set with the property that every Costas array has a distance vector in this set, or that every pair of Costas arrays with a common vector have a common vector in this set, is in both cases surprisingly small. Further, we study Costas arrays with the additional property that they represent configurations of non-attacking kings or queens: in the former case, we demonstrate that such arrays are either sporadic or produced by a sub-method of the Lempel construction; in the latter case, partially answering a question asked by S. Golomb 26 years ago, we prove that (non-trivial) such arrays can only be sporadic and conjecture they do not exist at all.
2009, 3(1): 53-58
doi: 10.3934/amc.2009.3.53
+[Abstract](2640)
+[PDF](134.3KB)
Abstract:
In coding theory, we are often interested in finding codes with a ''good'' relative minimum distance. To create a code that transmits information efficiently, we would like to see the ratio of bits containing information to total codeword length be large. In particular, for families of codes this means that as the codeword length increases, we do not significantly decrease the amount of information transmitted; for each fixed prime $q$ we can construct a family of $q$-ary codes with lengths $p$ and minimal distances $d_p$ with the property that as the length of these codes approaches infinity, the ratio of their minimal distance to their total length tends towards $\epsilon > 0$.
In this paper, we examine families of generalized binary quadratic residue codes, named $q$-th power residue codes, where $q$ is a fixed odd prime, and find an asymptotically bad subfamily of these codes. For each prime $l$ we will construct a $q$-th power residue code of length $p$ (determined by our choice of $l$ ) and minimal distance $d_p$, with the property that as $l$ approaches infinity, $p$ also tends towards infinity, and $\lim_{l to \infty} \frac{d_p}{p} = 0$.
In coding theory, we are often interested in finding codes with a ''good'' relative minimum distance. To create a code that transmits information efficiently, we would like to see the ratio of bits containing information to total codeword length be large. In particular, for families of codes this means that as the codeword length increases, we do not significantly decrease the amount of information transmitted; for each fixed prime $q$ we can construct a family of $q$-ary codes with lengths $p$ and minimal distances $d_p$ with the property that as the length of these codes approaches infinity, the ratio of their minimal distance to their total length tends towards $\epsilon > 0$.
In this paper, we examine families of generalized binary quadratic residue codes, named $q$-th power residue codes, where $q$ is a fixed odd prime, and find an asymptotically bad subfamily of these codes. For each prime $l$ we will construct a $q$-th power residue code of length $p$ (determined by our choice of $l$ ) and minimal distance $d_p$, with the property that as $l$ approaches infinity, $p$ also tends towards infinity, and $\lim_{l to \infty} \frac{d_p}{p} = 0$.
2009, 3(1): 59-81
doi: 10.3934/amc.2009.3.59
+[Abstract](6061)
+[PDF](288.3KB)
Abstract:
Following an example in [12], we show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that our approach can be used to construct a ''non-quadratic'' APN function. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic. An equivalent function has been found independently by Brinkmann and Leander [8]. However, they claimed that their function is CCZ equivalent to a quadratic one. In this paper we give several reasons why this new function is not equivalent to a quadratic one.
Following an example in [12], we show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that our approach can be used to construct a ''non-quadratic'' APN function. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic. An equivalent function has been found independently by Brinkmann and Leander [8]. However, they claimed that their function is CCZ equivalent to a quadratic one. In this paper we give several reasons why this new function is not equivalent to a quadratic one.
2009, 3(1): 83-95
doi: 10.3934/amc.2009.3.83
+[Abstract](3122)
+[PDF](163.4KB)
Abstract:
The $m$-covering radii of codes are natural generalizations of the covering radii of codes. In this paper we analyze the 2-covering radii of double error correcting BCH code. In particular, we show that the 2-covering radius of the double error correcting BCH code is $(n+1)/2$ for sufficiently large $n$.
The $m$-covering radii of codes are natural generalizations of the covering radii of codes. In this paper we analyze the 2-covering radii of double error correcting BCH code. In particular, we show that the 2-covering radius of the double error correcting BCH code is $(n+1)/2$ for sufficiently large $n$.
2009, 3(1): 97-114
doi: 10.3934/amc.2009.3.97
+[Abstract](3245)
+[PDF](260.9KB)
Abstract:
Consider a connected, undirected graph $G=(V,E)$ and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centred at $v$, i.e., the set of all vertices linked to $v$ by a path consisting of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(v)$ are different, then we say that $G$ is $r$-twin-free.
In $r$-twin-free graphs, we prolong the study of the extremal values that can be achieved by the main classical parameters in graph theory, and investigate here the number of edges, the minimum degree, the size of a maximum independent set, as well as radius and diameter.
Consider a connected, undirected graph $G=(V,E)$ and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centred at $v$, i.e., the set of all vertices linked to $v$ by a path consisting of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(v)$ are different, then we say that $G$ is $r$-twin-free.
In $r$-twin-free graphs, we prolong the study of the extremal values that can be achieved by the main classical parameters in graph theory, and investigate here the number of edges, the minimum degree, the size of a maximum independent set, as well as radius and diameter.
2020
Impact Factor: 0.935
5 Year Impact Factor: 0.976
2020 CiteScore: 1.5
Readers
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]