All Issues

Volume 16, 2022

Volume 15, 2021

Volume 14, 2020

Volume 13, 2019

Volume 12, 2018

Volume 11, 2017

Volume 10, 2016

Volume 9, 2015

Volume 8, 2014

Volume 7, 2013

Volume 6, 2012

Volume 5, 2011

Volume 4, 2010

Volume 3, 2009

Volume 2, 2008

Volume 1, 2007

Advances in Mathematics of Communications

November 2008 , Volume 2 , Issue 4

Select all articles


Zig-zag and replacement product graphs and LDPC codes
Christine A. Kelley, Deepak Sridhara and Joachim Rosenthal
2008, 2(4): 347-372 doi: 10.3934/amc.2008.2.347 +[Abstract](3071) +[PDF](325.2KB)
It is known that the expansion property of a graph influences the performance of the corresponding code when decoded using iterative algorithms. Certain graph products may be used to obtain larger expander graphs from smaller ones. In particular, the zig-zag product and replacement product may be used to construct infinite families of constant degree expander graphs. This paper investigates the use of zig-zag and replacement product graphs for the construction of codes on graphs. A modification of the zig-zag product is also introduced, which can operate on two unbalanced biregular bipartite graphs, and a proof of the expansion property of this modified zig-zag product is presented.
Computation of distributions and their moments in the trellis
Axel Heim, Vladimir Sidorenko and Uli Sorger
2008, 2(4): 373-391 doi: 10.3934/amc.2008.2.373 +[Abstract](3827) +[PDF](275.6KB)
Consider a function whose set of vector arguments with known distribution is described by a trellis. For a certain class of functions, the distribution of the function values can be calculated in the trellis. The forward/backward recursion known from the BCJR algorithm [2] is generalized to compute the moments of these distributions. In analogy to the symbol probabilities, by introducing a constraint at a certain depth in the trellis we obtain symbol distributions and symbol moments, respectively. These moments are required for an efficient implementation of the discriminated belief propagation algorithm in [8], and can furthermore be utilized to compute conditional entropies in the trellis.
The moment computation algorithm has the same asymptotic complexity as the BCJR algorithm. It is applicable to any commutative semi-ring, thus actually providing a generalization of the Viterbi algorithm [10].
Lee weight enumerators of self-dual codes and theta functions
Bram van Asch and Frans Martens
2008, 2(4): 393-402 doi: 10.3934/amc.2008.2.393 +[Abstract](3461) +[PDF](150.8KB)
The theory of modular forms, in particular theta functions, and coding theory are in a remarkable way connected. The connection is established by defining a suitable lattice corresponding to the given code, and considering its theta function. First we define some special theta functions, and determine transformation formulas. Then it is proved that the theta function of the lattice corresponding to the code can be expressed in terms of the Lee weight enumerator. In particular if the code is self-dual and the length is a multiple of $8$ this theta function is a modular form for some subgroup of the modular group. Using the known structure of this space of modular forms we can derive linear relations between the coefficients of the Lee weight enumerator. And from these relations we can get an upper bound for the minimal Lee distance of self-dual $p$-ary codes.
Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity
Emmanuel Charbit, Irène Charon, Gérard Cohen, Olivier Hudry and Antoine Lobstein
2008, 2(4): 403-420 doi: 10.3934/amc.2008.2.403 +[Abstract](3247) +[PDF](267.3KB)
Consider an undirected bipartite graph $G=(V=I\cup A,E)$, with no edge inside $I$ nor $A$. For any vertex $v\in V$, let $N(v)$ be the set of neighbours of $v$. A code $C \subseteq A$ is said to be discriminating if all the sets $N(i) \cap C$, $i \in I$, are nonempty and distinct. We study some properties of discriminating codes. In particular, we give bounds on the minimum size of these codes, investigate graphs where minimal discriminating codes have size close to the upper bound, or give the exact minimum size in particular graphs; we also give an NP-completeness result.
On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables
Joan-Josep Climent, Francisco J. García and Verónica Requena
2008, 2(4): 421-431 doi: 10.3934/amc.2008.2.421 +[Abstract](3504) +[PDF](160.7KB)
In this paper we present a method to construct iteratively new bent functions of $n + 2$ variables from bent functions of $n$ variables using minterms of $n$ variables and minterms of two variables. Also, we provide the number of bent functions of $n+2$ variables that we can obtain with the method here presented.
Weight distribution and decoding of codes on hypergraphs
Alexander Barg, Arya Mazumdar and Gilles Zémor
2008, 2(4): 433-450 doi: 10.3934/amc.2008.2.433 +[Abstract](4011) +[PDF](229.6KB)
Codes on hypergraphs are an extension of the well-studied family of codes on bipartite graphs. Bilu and Hoory (2004) constructed an explicit family of codes on regular $t$-partite hypergraphs whose minimum distance improves earlier estimates of the distance of bipartite-graph codes. They also suggested a decoding algorithm for such codes and estimated its error-correcting capability.
In this paper we study two aspects of hypergraph codes. First, we compute the weight enumerators of several ensembles of such codes, establishing conditions under which they attain the Gilbert-Varshamov bound and deriving estimates of their distance. In particular, we show that this bound is attained by codes constructed on a fixed bipartite graph with a large spectral gap.
We also suggest a new decoding algorithm of hypergraph codes that corrects a constant fraction of errors, improving upon the algorithm of Bilu and Hoory.
Geometric constructions of optimal optical orthogonal codes
T. L. Alderson and K. E. Mellinger
2008, 2(4): 451-467 doi: 10.3934/amc.2008.2.451 +[Abstract](4638) +[PDF](239.2KB)
We provide a variety of constructions of $(n, w, \lambda)$-optical orthogonal codes using special sets of points and Singer groups in finite projective spaces. In several of the constructions, we are able to prove that the resulting codes are optimal with respect to the Johnson bound. The optimal codes exhibited have $\lambda = 1, 2$ and $w-1$ (where $w$ is the weight of each codeword in the code). The remaining constructions are are shown to be asymptotically optimal with respect to the Johnson bound, and in some cases maximal. These codes represent an improvement upon previously known codes by shortening the length. In some cases the constructions give rise to variable weight OOCs.

2021 Impact Factor: 1.015
5 Year Impact Factor: 1.078
2021 CiteScore: 1.8




Email Alert

[Back to Top]