Contact:
Marcus Greferath
School of Math. Sciences
University College Dublin
Belfield, Dublin 4, Ireland
Phone:
+353-1-716-2588 (UCD)
+353-85-153-0951 (mobile)

Joachim Rosenthal
Institut of Mathematics
University of Zurich
Winterthurerstrasse 190
8057 Zurich, Switzerland
Phone:
+41-44-63 55884 (office)

ITW 2010 Dublin
IEEE Information Theory Workshop
Dublin, August 30 - September 3, 2010

LDPC codes

Wed 01 Sep, 09.55-12.45, Room 1

Invited session
Organizers: David Burshtein and Simon Litsyn

David Burshtein and Idan Goldenberg Improved Linear Programming Decoding and Bounds on the Minimum Distance of LDPC Codes

Abstract: We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code. Wed 01 Sep, 09.55-10.20, Room 1

Michael Chertkov, Jason Johnson, Shrinivas Kudekar Loop-based Relaxation in Combinatorial Problems of Graphical Coding

Abstract: We discuss and provide algorithmic solutions to three inter-related problems posed for a given LDPC code: (a) How to improve LP decoding and thus to reduce the error-floor of the code? (b) How to find the provably smallest stopping set of the code? (c) How to lower bound and/or estimate efficiently Hamming distance of the code? Wed 01 Sep, 10.20-10.45, Room 1

Farzad Farnoud (Hassanzadeh), Chien-Yu Chen, Olgica Milenkovic, and Navin Kashyap A Graphical Model for computing the Minimum Cost Transposition Distance

Abstract: We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For metric-path costs, we describe exact polynomial-time decomposition algorithms. For extended-metric-path cost functions, we describe polynomial-time constant-approximation decomposition algorithms. Our algorithms rely on graphical representations of permutations and graph-search techniques for minimizing the permutation decomposition cost. The presented algorithms have applications in information theory, bioinformatics, and algebra. Wed 01 Sep, 10.45-11.10, Room 1

Meir Feder Low density lattice codes: from theory to practice

Low density lattice codes (LDLC) are recently-proposed lattice codes, designed directly in the Euclidean space and can be decoded, iteratively, in linear time. In the original paper, it was shown, experimentally, that LDLC with iterative decoding can approach the capacity of the unconstrained additive white Gaussian noise (AWGN) channel. However, for practical implementation several advancement were required: 1. Shaping: Using a finite power lattice and provide a mapping of the information bits to lattice points 2. More efficient decoding: Algorithms whose complexity is competitive with the alternative schemes based on finite alphabet codes 3. Ability to work at low SNR and at fading channels In a series of recent works we provide solutions to these issues that make LDLC a practical, attractive alternative in many realistic communication scenaria. This work includes contributions by Naftali Sommer, Yair Yona, Ofir Shalvi and Joseph Boutros. Wed 01 Sep, 11.30-11.55, Room 1

S. Hamed Hassani, Nicolas Macris, and Ruediger Urbanke Coupled Graphical Models and Their Thresholds

Abstract: The excellent performance of convolutional low-density parity-check codes is the result of the spatial coupling of individual underlying codes across a window of growing size, but much smaller than the length of the individual codes. Remarkably, the belief-propagation threshold of the coupled ensemble is boosted to the maximum-a-posteriori one of the individual system. We investigate the generality of this phenomenon beyond coding theory: we couple general graphical models into a one-dimensional chain of large individual systems. For the later we take the Curie-Weiss, random field Curie-Weiss, K-satisfiability, and Q-coloring models. We always find, based on analytical as well as numerical calculations, that the message passing thresholds of the coupled systems come very close to the static ones of the individual models. The remarkable properties of convolutional low-density parity-check codes are a manifestation of this very general phenomenon. Wed 01 Sep, 11.55-12.20, Room 1

Vitaly Skachek Characterization of Graph-cover Pseudocodewords of Codes over F3

Abstract: Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becomes more involved. In this work, a characterization of the fundamental cone for codes over F3 is discussed. Wed 01 Sep, 12.20-12.45, Room 1

Back to previous page

Return to conference mainpage

SPONSORS