ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
August 2011 , Volume 5 , Issue 3
Select all articles
Export/Reference:
2011, 5(3): 417-424
doi: 10.3934/amc.2011.5.417
+[Abstract](3232)
+[PDF](299.9KB)
Abstract:
Improved binary constant weight codes with minimum distance 4 are constructed. A table with bounds on the chromatic number of small Johnson graphs is given.
Improved binary constant weight codes with minimum distance 4 are constructed. A table with bounds on the chromatic number of small Johnson graphs is given.
2011, 5(3): 425-433
doi: 10.3934/amc.2011.5.425
+[Abstract](3921)
+[PDF](319.5KB)
Abstract:
Steganography is an information hiding application which aims to hide secret data imperceptibly into a cover object. In this paper, we describe a novel coding method based on $\mathbb{Z}_2\mathbb{Z}_4$-additive codes in which data is embedded by distorting each cover symbol by one unit at most ($\pm 1$-steganography). This method is optimal and solves the problem encountered by the most efficient methods known today, concerning the treatment of boundary values. The performance of this new technique is compared with that of the mentioned methods and with the well-known rate-distortion upper bound to conclude that a higher payload can be obtained for a given distortion by using the proposed method.
Steganography is an information hiding application which aims to hide secret data imperceptibly into a cover object. In this paper, we describe a novel coding method based on $\mathbb{Z}_2\mathbb{Z}_4$-additive codes in which data is embedded by distorting each cover symbol by one unit at most ($\pm 1$-steganography). This method is optimal and solves the problem encountered by the most efficient methods known today, concerning the treatment of boundary values. The performance of this new technique is compared with that of the mentioned methods and with the well-known rate-distortion upper bound to conclude that a higher payload can be obtained for a given distortion by using the proposed method.
2011, 5(3): 435-448
doi: 10.3934/amc.2011.5.435
+[Abstract](2282)
+[PDF](384.2KB)
Abstract:
The number of degrees of freedom of Costas permutations is considered, and found to be surprisingly small, while partial results about the degrees of freedom of Golomb and Welch Costas permutations are proved. For Golomb Costas permutations, in particular, the curious observation is made that arbitrarily long sequences of distinct positive integers seem to exist, with the property that two or more Golomb Costas permutations, constructed in a suitably large field, start with such a sequence; other types of constraints, related to their cycle structure, are studied; and finally it is shown that, in any extension field containing non-quadratic subfields, Lempel Costas permutations are obtainable through the iterated composition of other Golomb Costas permutations.
The number of degrees of freedom of Costas permutations is considered, and found to be surprisingly small, while partial results about the degrees of freedom of Golomb and Welch Costas permutations are proved. For Golomb Costas permutations, in particular, the curious observation is made that arbitrarily long sequences of distinct positive integers seem to exist, with the property that two or more Golomb Costas permutations, constructed in a suitably large field, start with such a sequence; other types of constraints, related to their cycle structure, are studied; and finally it is shown that, in any extension field containing non-quadratic subfields, Lempel Costas permutations are obtainable through the iterated composition of other Golomb Costas permutations.
2011, 5(3): 449-471
doi: 10.3934/amc.2011.5.449
+[Abstract](4241)
+[PDF](438.3KB)
Abstract:
Associative division algebras are a rich source of fully diverse space-time block codes (STBCs). In this paper the systematic construction of fully diverse STBCs from nonassociative algebras is discussed. As examples, families of fully diverse $2\times 2$, $2\times 4$ multiblock and $4\times 4$ STBCs are designed, employing nonassociative quaternion division algebras.
Associative division algebras are a rich source of fully diverse space-time block codes (STBCs). In this paper the systematic construction of fully diverse STBCs from nonassociative algebras is discussed. As examples, families of fully diverse $2\times 2$, $2\times 4$ multiblock and $4\times 4$ STBCs are designed, employing nonassociative quaternion division algebras.
2011, 5(3): 473-488
doi: 10.3934/amc.2011.5.473
+[Abstract](3018)
+[PDF](413.8KB)
Abstract:
We present a new one-time signature scheme having short signatures. Our new scheme is also the first one-time signature scheme that supports aggregation, batch verification, and which admits efficient proofs of knowledge. It has a fast signing algorithm, requiring only modular additions, and its verification cost is comparable to ECDSA verification. These properties make our scheme suitable for applications on resource-constrained devices such as smart cards and sensor nodes.
We present a new one-time signature scheme having short signatures. Our new scheme is also the first one-time signature scheme that supports aggregation, batch verification, and which admits efficient proofs of knowledge. It has a fast signing algorithm, requiring only modular additions, and its verification cost is comparable to ECDSA verification. These properties make our scheme suitable for applications on resource-constrained devices such as smart cards and sensor nodes.
2011, 5(3): 489-504
doi: 10.3934/amc.2011.5.489
+[Abstract](4339)
+[PDF](378.6KB)
Abstract:
The order bound for the minimum distance of algebraic geometry codes was originally defined for the duals of one-point codes and later generalized for arbitrary algebraic geometry codes. Another bound of order type for the minimum distance of general linear codes, and for codes from order domains in particular, was given in [1]. Here we investigate in detail the application of that bound to one-point algebraic geometry codes, obtaining a bound d* for the minimum distance of these codes. We establish a connection between d* and the order bound and its generalizations. We also study the improved code constructions based on d*. Finally we extend d* to all generalized Hamming weights.
The order bound for the minimum distance of algebraic geometry codes was originally defined for the duals of one-point codes and later generalized for arbitrary algebraic geometry codes. Another bound of order type for the minimum distance of general linear codes, and for codes from order domains in particular, was given in [1]. Here we investigate in detail the application of that bound to one-point algebraic geometry codes, obtaining a bound d* for the minimum distance of these codes. We establish a connection between d* and the order bound and its generalizations. We also study the improved code constructions based on d*. Finally we extend d* to all generalized Hamming weights.
2011, 5(3): 505-520
doi: 10.3934/amc.2011.5.505
+[Abstract](3126)
+[PDF](446.0KB)
Abstract:
We prove that $[g_3(6,d),6,d]_3$ codes for $d=253$-$267$ and $[g_3(6,d)+1,6,d]_3$ codes for $d=302, 303, 307$-$312$ exist and that $[g_3(6,d),6,d]_3$ codes for $d=175, 200, 302, 303, 308, 309$ and a $[g_3(6,133)+1,6,133]_3$ code do not exist, where $g_3(k,d)=\sum_{i=0}^{k-1} \lceil d / 3^i \rceil$. These determine $n_3(6,d)$ for $d=133, 175, 200, 253$-$267, 302, 303, 308$-$312$, where $n_q(k,d)$ is the minimum length $n$ for which an $[n,k,d]_q$ code exists. The updated $n_3(6,d)$ table is also given.
We prove that $[g_3(6,d),6,d]_3$ codes for $d=253$-$267$ and $[g_3(6,d)+1,6,d]_3$ codes for $d=302, 303, 307$-$312$ exist and that $[g_3(6,d),6,d]_3$ codes for $d=175, 200, 302, 303, 308, 309$ and a $[g_3(6,133)+1,6,133]_3$ code do not exist, where $g_3(k,d)=\sum_{i=0}^{k-1} \lceil d / 3^i \rceil$. These determine $n_3(6,d)$ for $d=133, 175, 200, 253$-$267, 302, 303, 308$-$312$, where $n_q(k,d)$ is the minimum length $n$ for which an $[n,k,d]_q$ code exists. The updated $n_3(6,d)$ table is also given.
2011, 5(3): 521-527
doi: 10.3934/amc.2011.5.521
+[Abstract](2862)
+[PDF](311.6KB)
Abstract:
Codebooks achieving the Welch bound on the maximum correlation amplitude are desirable in a number of applications. Recently, codebooks meeting (resp., nearly meeting) the Welch bound were constructed from difference sets (resp., almost difference sets). In this paper, a general connection between complex codebooks and relative difference sets is introduced. Several classes of codebooks nearly meeting the Welch bound are then constructed from some known relative difference sets using the general connection.
Codebooks achieving the Welch bound on the maximum correlation amplitude are desirable in a number of applications. Recently, codebooks meeting (resp., nearly meeting) the Welch bound were constructed from difference sets (resp., almost difference sets). In this paper, a general connection between complex codebooks and relative difference sets is introduced. Several classes of codebooks nearly meeting the Welch bound are then constructed from some known relative difference sets using the general connection.
2011, 5(3): 529-541
doi: 10.3934/amc.2011.5.529
+[Abstract](2816)
+[PDF](392.7KB)
Abstract:
Combinatorial batch codes were introduced by Ishai et al. [36th ACM STOC (2004), 262-271] and studied in detail by Paterson et al. [Adv. Math. Commun., 3 (2009), 13-27] for the purpose of distributed storage and retrieval of items of a database on a given number of servers in an economical way. A combinatorial batch code with parameters $n,k,m,t$ means that $n$ items are stored on $m$ servers such that any $k$ different items can be retrieved by reading out at most $t$ items from each server. If $t=1$, this can equivalently be represented with a family $\mathcal F$ of $n$ not necessarily distinct sets over an $m$-element underlying set, such that the union of any $i$ members of $\mathcal F$ has cardinality at least $i$, for every $1\le i\le k$. The goal is to determine the minimum $N(n,k,m)$ of $\sum$$F\in\mathcal F$$|F|$ over all combinatorial batch codes $\mathcal F$ with given parameters $n,k,m$ and $t=1$.
We prove $N(n,k,m)= (k-1)n- \lfloor \frac{(k-1){m \choose k-1}-n}{m-k+1} \rfloor$ for all ${m\choose k-2} \le n \le (k-1){m\choose k-1}$. Together with the results of Paterson et al. for $n$ larger, this completes the determination of $N(n,3,m)$. We also compute $N(n,4,m)$ in the entire range $n\ge m\ge 4$. Several types of code transformations keeping optimality are described, too.
Combinatorial batch codes were introduced by Ishai et al. [36th ACM STOC (2004), 262-271] and studied in detail by Paterson et al. [Adv. Math. Commun., 3 (2009), 13-27] for the purpose of distributed storage and retrieval of items of a database on a given number of servers in an economical way. A combinatorial batch code with parameters $n,k,m,t$ means that $n$ items are stored on $m$ servers such that any $k$ different items can be retrieved by reading out at most $t$ items from each server. If $t=1$, this can equivalently be represented with a family $\mathcal F$ of $n$ not necessarily distinct sets over an $m$-element underlying set, such that the union of any $i$ members of $\mathcal F$ has cardinality at least $i$, for every $1\le i\le k$. The goal is to determine the minimum $N(n,k,m)$ of $\sum$$F\in\mathcal F$$|F|$ over all combinatorial batch codes $\mathcal F$ with given parameters $n,k,m$ and $t=1$.
We prove $N(n,k,m)= (k-1)n- \lfloor \frac{(k-1){m \choose k-1}-n}{m-k+1} \rfloor$ for all ${m\choose k-2} \le n \le (k-1){m\choose k-1}$. Together with the results of Paterson et al. for $n$ larger, this completes the determination of $N(n,3,m)$. We also compute $N(n,4,m)$ in the entire range $n\ge m\ge 4$. Several types of code transformations keeping optimality are described, too.
2011, 5(3): 543-546
doi: 10.3934/amc.2011.5.543
+[Abstract](3126)
+[PDF](235.7KB)
Abstract:
A new class of perfect 1-error correcting binary codes, so called RRH-codes, are identified, and it is shown that every such code is linearly equivalent to a perfect code obtainable by the Phelps construction.
A new class of perfect 1-error correcting binary codes, so called RRH-codes, are identified, and it is shown that every such code is linearly equivalent to a perfect code obtainable by the Phelps construction.
2011, 5(3): 547-553
doi: 10.3934/amc.2011.5.547
+[Abstract](4193)
+[PDF](345.7KB)
Abstract:
The results of the enumeration of Costas arrays of order 29 are presented: except for 16 arrays out of a total of 164, all other arrays found are accounted for by the Golomb and Welch construction methods. These 16 arrays, however, cannot be considered to be new, as they were discovered in the past through a semi-empirical technique. The enumeration was performed on several computer clusters and required the equivalent of 366.55 years of single CPU time.
The results of the enumeration of Costas arrays of order 29 are presented: except for 16 arrays out of a total of 164, all other arrays found are accounted for by the Golomb and Welch construction methods. These 16 arrays, however, cannot be considered to be new, as they were discovered in the past through a semi-empirical technique. The enumeration was performed on several computer clusters and required the equivalent of 366.55 years of single CPU time.
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]