Title: Design of Coherent Space-Time Codes

The design of bit-interleaved coded modulations (BICM) for multiple antenna channels (MIMO) under iterative coherent detection and decoding is described. Binary QAM mappings and linear space-time precoders are fine tuned by the mean of a genie method that assumes perfect a priori information. We also present a modified singleton bound on the diversity order of a BICM with linear precoding. It is shown how the minimal space-time spreading factor (e.g. via cyclotomic rotations) should be selected in order to attain full diversity at the decoder output. Finally, we propose a low complexity APP detector (i.e. soft output sphere decoder) for BICM-QAM constellations transmitted on a MIMO channel. The APP detector starts by applying an accelerated sphere decoder to find the maximum likelihood (ML) point. Then, using a double recursion Pohst enumerator, a shifted list is built around the ML point to evaluate the output APP. The list radius is selected in order to control the list size and to cope with the boundaries of the finite multiple antenna constellation. Detailed papers can be found at http://www.enst.fr/~boutros/coding.

Title: On Computing Largest Correcting Codes and their Estimates Using Optimization on Specially Constructed Graphs

Error correcting codes lie in the heart of digital technology, making cell phones, compact disk players and modems possible. A fundamental problem of interest is to send a message across a noisy channel with a maximum possible reliability. This problem is related to the problem of finding the largest error correcting codes for certain types of errors. Computing estimates of the size of correcting codes is important from both theoretical and practical perspectives. In many cases, the problem of finding the largest correcting codes and their estimates can be formulated in terms of combinatorial optimization problems on specially constructed graphs. We present new results obtained using this approach. In particular, we report new lower bounds and exact sizes for the largest codes correcting the following types of errors: single-deletion, two-deletion, single-transposition, and errors in asymmetric channel.

Title: A Four Dimensional Generalization of the 2x2 Alamouti Space-Time Code

We abstract the concept of a 2x2 array with orthogonal rows from the complex numbers to the quaternions.

Title: Biological Coding Theory: The Emerging Paradigm?

After the discovery of Shannon?s Information theory in 1948 there was a lot of excitement about its application in biology. Motivated by the discovery of genetic codes even several people worked on comma-free codes (example, Golomb). However this trend could not continue further and people found around 1956 that application of Shannon?s ideas to biology has not yielded much results. Similar things happened to Coding theory. Now after 50 years our understanding of biology is increasing day by day and we have sequenced first time genome of mouse and man. Biology is at the place where chemistry was about 200 years back. In this talk we will explore how far we have come in this area giving known results and possibly posing several open questions.

Title: A Classification of Posets Admitting MacWilliams Identity

All poset structures are classified which admit the MacWilliams Identity, and the MacWilliams identities for poset weight enumerators corresponding to such posets are derived. We prove that being a hierarchical poset is a necessary and sufficient condition for a poset to admit MacWilliams identity. An explicit relation is also derived between P-weight distribution of a hierarchical poset code and $\bar P}-weight distribution of the dual code.aa

Title: A Unified Construction of Space-Time Codes with Optimal Rate-Diversity Tradeoff

For a space-time block code having a fixed, finite signal constellation, there is a tradeoff between the transmission rate and the transmit diversity gain achieved by the code. In this paper, for any $M \leq T$, a unified construction of $(M \times T)$ space-time codes is provided, for a class of signal constellations that includes pulse-amplitude-modulation (PAM), quadrature-amplitude- modulation (QAM) and $2^K$-ary phase-shift-keying (PSK) as special cases. The construction is optimal as measured by the rate-diversity tradeoff. The unified construction can also be applied to build space-time trellis codes. The extension to the case of multiple fading blocks will also be provided.

Title: A New Mathematical Approach for the Design of Digital Communication Systems

In this paper we consider the use of surfaces or 2-dimensional manifolds as topological spaces in the design of digital communication systems. The main idea behind this approach is to identify the surface topology (geometric and algebraic properties) associated with each block diagramforming the traditional model of a communication system, however starting this procedure with the graph associated with the discrete memoryless channel, DMC channel. Once the geometric and algebraic properties of the DMC channel are known, the design of the remaining block diagrams will have to be matched to these properties. The procedure employed to achieve this goal is based on the following steps: knowing the graph associated with a given discrete memoryless channel, 1) to determine the set of surfaces in which the graph is embedded; 2) to determine the fundamental group, and its subgroups, associated with each previous surface; and 3) to identify the regular tessellations which may be used in the design of signal constellations matched to subgroups of the fundamental group associated with the corresponding Riemann surfaces. As a consequence of the third step, we extend the concept of geometrically uniform codes, formerly employed in Euclidean spaces, to the hyperbolic spaces (or to spaces with constant negative curvature). We also show a characterization of the generalized coset codes through the concept of G-linear codes. Since the previous three steps may be extended to n-dimensional manifolds, we consider the performance analysis of the corresponding digital communication system in Riemannian manifolds. To do that it is necessary to extend the concepts related to signal constellations, symbol error probability, and average energy of the signal constellation to the theory of differentiable manifolds. One of the important results coming out of this formalism is that the sectional curvature of the manifold is a relevant parameter in the design and in the performance analysis of signal constellations. As a consequence, we show that the best performance is achieved when the sectional curvature is constant and negative.

*The author is with the Department of Telematics, FEEC-UNICAMP, Brazil. This work has been supported by FAPESP under grant 02/07473-7, by CNPq under grant 311406-85, and by CAPES-PROCAD under grant 0121/01-0. email: palazzo@dt.fee.unicamp.br

Title: Low Density Parity Check Lattices

Low density parity check codes can have a remarkable performance under iterative decoding algorithms. This idea is used to construct a class of lattices with relatively high coding gain and low decoding complexity.

The lattice construction is based on the so-called Construction $D'$. This lattice construction converts a set of parity check defining a family of nested low density parity check codes into congruences for a lattice called low density parity check lattice (LDPC lattice, for short). Bounds on the minimum distance and coding gain of the corresponding lattice in terms of the minimum distance of the underlying codes are provided. Given a parity check matrix of lattice, a practical way of finding the lattice parameters such as cross sections and label group sizes are given.

A new approach based on iterative decoding of lattices is taken. For the decoding of a low density parity check lattice, the Min-Sum algorithm is generalized to group codes over different alphabet sizes and is applied to the Tanner graph of the lattice. An upper bound on the decoding complexity using generalized Min-Sum algorithm is given. Also for the decoding complexity of LDPC lattices the exact number of computations among lower and upper bounds are derived. The analysis of decoding complexity confirms the use of LDPC codes for the lattice construction. It is shown that the decoding complexity grows linearly with the dimension, exponentially with row weights and is polynomial time in terms of coding gain of the lattice.

The progressive edge growth algorithm is extended to what we call E-PEG algorithm. This algorithm is used to construct a class of nested regular binary codes to generate the corresponding lattice. A class of 2-level lattices is constructed. The performance of this class is compared with the corresponding 1-level construction and other famous constructions.

Title: Covering Codes with Improved Density

We show that for every fixed $R$, $\mu^{\ast}(R)$, the asymptotic (worst) density of binary covering codes of radius $R$ satisfies $\mu^{\ast} (R) \le 4 R\ln R$, for large enough $R$. This significantly improves the best known density estimate $2^R R^R (R+1)/R!$. Our bound also holds for covering codes over arbitrary alphabets.

( This is joint work with Krivelevich and Vu.)

Title: A New Construction of 16-QAM Golay Complementary Sequences

We present a new construction of 16-QAM Golay sequences of length $n=2^m$. The number of constructed sequences is $(14+12m)(m!/2)4^{m+1}$. When employed as a code in an OFDM system, this set of sequences has a peak-to-mean envelope power ratio (PMEPR) of 3.6. By considering two specific subsets of these sequences, we obtain new codes with PMEPR bounds of 2.0 and 2.8 and respective code sizes of $(2+2m)(m!/2)4^{m+1}$ and $(4+4m)(m!/2)4^{m+1}$. These are larger than previously known codes for the same PMEPR bounds.

Title: Graph Covers and Iterative Decoding of Finite-Length Codes

One of the most important developments in coding theory has been the (re)discovery of iteratively decodable code. It is fair to say that iterative decoding has thoroughly changed much of modern communications. Before this backdrop, a thorough understanding of these codes is highly desirable. Indeed, impressive advances have been made in the context of asymptotically long codes.

On the other hand, the behavior of finite length codes is not well understood and, consequently, much work in the field relies on simulations alone.

In this talk we address recent (and not so recent) developments in the analysis of iterative decoding algorithms for finite-length codes. It turns out that there is a systemic penalty for any type of iterative, message-passing algorithm due to the fact that these algorithms only investigate small parts of codewords at each instance in time. The information, thus locally obtained, is recombined to achieve global decoding. However, it turns out that the locality of the algorithms, which is the reason for their low complexity, is also the source of the sub-optimal behavior.

(This talk is based on joint work with Ralf Koetter.)

Title: Current Trends in Coding Theory

We would like to hear opinions on the current trends in coding theory in view of the change of perspective from algebraic constructions to iterative decoding. Are there still problems of general interest in algebraic coding? What is presently the motivation to study algebraic and combinatorial problems of coding theory, apart from purely mathematical interest?