Advances in Mathematics of Communications
May 2008 , Volume 2 , Issue 2
Select all articles
We extend the definition of the Costas property to functions in the continuum, namely on intervals of the reals or the rationals, and argue that such functions can be used in the same applications as discrete Costas arrays. We construct Costas bijections in the real continuum within the class of piecewise continuously differentiable functions, but our attempts to construct a fractal-like Costas bijection there are successful only under slight but necessary deviations from the usual arithmetic laws. The situation over the rationals is different: there, we propose a method of great generality and flexibility for the construction of a Costas fractal bijection. Its success, though, relies heavily on the enumerability of the rationals, and therefore it cannot be generalized over the reals in an obvious way.
Space-time codes for a wide variety of channels have the property that the diversity of a pair of codeword matrices is measured by the vanishing or non-vanishing of polynomials in the entries of the matrices. We show that for every such channel: I) There is an appropriately-defined notion of approximation of space-time codes such that each code is arbitrarily well approximated by one whose alphabet lies in the field of algebraic numbers; II) Each space-time code whose alphabet lies in the field of algebraic numbers is an appropriately-defined lift from a corresponding space-time code defined over a finite field or a ''scaled'' lift from a Galois ring of arbitrary characteristic. This implies that all space-time codes can be designed over finite fields or over Galois rings of arbitrary characteristic and then lifted to complex matrices with entries in a number field.
We investigate properties of subspace subcodes of Gabidulin codes. They are isomorphic to Gabidulin codes with the same minimum rank distance and smaller parameters. We design systematic encoding and decoding algorithms for subspace subcodes. We show that the direct sum of subspace subcodes of Gabidulin codes is isomorphic to the direct product of Gabidulin codes with smaller parameters. Thanks to this structure there is a great deal of correctable error-patterns whose rank exceeds the error-correcting capability. Finally we show that for particular sets of parameters, subfield subcodes of Gabidulin codes can be uniquely characterised by elements of the general linear group GL$_n(GF(q))$ of non-singular $q$-ary matrices of size $n$.
In Signal Processing and Cryptography a non-standard number representation, called Double Base Number System (DBNS) has found many applications. This representation has many interesting and useful properties. In traditional number systems, there is one radix used to represent numbers. For example in decimal systems, numbers are expressed as sum of powers of 10. In DBNS numbers are represented as sum of product of powers of 2 radices. In the current article we present a scheme to represent numbers in double (and multi-) base format by combinatorial objects like graphs and diagraphs. The combinatorial representation leads to proof of some interesting results about the double and multibase representation of integers. These proofs are based on simple combinatorial arguments. In this article we have provided a graph theoretic proof of the recurrence relation satisfied by the number of double base representations of a given integer. The result has been further generalized to more than 2 bases. Also, we have uncovered some interesting properties of the sequence representing the number of double (multi-) base representation of a positive integer $n$. It is expected that the combinatorial representation can serve as a tool for a better understanding of the double (and multi-) base number systems and uncover some of the mysteries still associated with it.
We extend some results of Bras-Amorós concerning the order bound on the minimum distance of algebraic geometry codes related to acute semigroups. In particular we introduce a new family of semigroups, the so called near-acute semigroups, for which similar properties hold.
We consider the symmetric group $S_n$ in the special case where $n$ is composite: $n = pq$ (both $p$ and $q$ being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of $S$ pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup $S_p^q$, whereas the second one is an element of the dual Young subgroup $S_q^p$. This leads to synthesis methods for arbitrary reversible logic circuits of logic width $w$. These circuits form a group isomorphic to $S$2w. A particularly efficient synthesis is found by choosing $p=2$ and thus $q=2$w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.
We investigate the security of $n$-bit to $m$-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input $x$ but of free degree in the output $z = F(x)$. The complexity for computing the generalized nonlinearity for this new attack is reduced from $2$2m×n+n to $2$2n. Based on experimental results, we show that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attack. We confirm this with a theoretical upper bound for generalized nonlinearity, which is much lower than for the unrestricted non-linearity (for Zhang-Chan's attack) and a fortiori for usual nonlinearity. We also prove a lower bound for generalized nonlinearity which allows us to construct vector Boolean functions with high generalized nonlinearity from bent and almost bent functions. We derive the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions. Finally, we prove that if a vector Boolean function has high nonlinearity or even a high unrestricted nonlinearity, it cannot ensure that it will have high generalized nonlinearity.
The first examples of perfect $e$-error correcting $q$-ary codes were given in the 1940's by Hamming and Golay. In 1973 Tietäväinen, and independently Zinoviev and Leontiev, proved that if q is a power of a prime number then there are no unknown multiple error correcting perfect $q$-ary codes. The case of single error correcting perfect codes is quite different. The number of different such codes is very large and the classification, enumeration and description of all perfect 1-error correcting codes is still an open problem.
This survey paper is devoted to the rather many recent results, that have appeared during the last ten years, on perfect 1-error correcting binary codes. The following topics are considered: Constructions, connections with tilings of groups and with Steiner Triple Systems, enumeration, classification by rank and kernel dimension and by linear equivalence, reconstructions, isometric properties and the automorphism group of perfect codes.
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]