DIMACS Workshop on Codes and Complexity

December 4-7, 2001
DIMACS Center, CoRE Bldg., Room 431, Rutgers University, Piscataway, NJ

Amin Shokrollahi, Digital Fountain, amin@digitalfountain.com
Daniel Spielman, MIT, spielman@math.mit.edu
Ruediger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL), rudiger.urbanke@epfl.ch
Presented under the auspices of the:
Special Focus on Computational Information Theory and Coding and the
Special Focus on Mathematics and the Foundations of Computer and Information Science.



Properties of Extrinsic Information Transfer Curves
Authors: Alexei Ashikhmin, Gerhard Kramer, and Stephan ten Brink

The extrinsic information transfer (EXIT) chart has been used to study
the convergence of iterative decoding of concatenated codes.  We study
some properties of EXIT charts for the case of the binary erasure
channel. In particular we show that for any block code the area under
the transfer curve of the outer code is the entropy of the code, e.g.,
the area is the code rate if the code is linear.  We further show that
the transfer curves of a linear code and its dual are connected by an
analytical expression.

2. Amir Banihashemi, Carleton University Iterative coding schemes: new schedulings and optical implementations In the first part of this talk, we discuss new message-passing schedules for the decoding of low-density parity-check (LDPC) codes. We show that scheduling plays an important role in iterative decoding and that a schedule that matches the structure of the Tanner graph and the reliability of received information can improve the performance/complexity trade-off of coding schemes considerably. In the second part of the talk, we propose using optical components for decoding digital information, based on the so-called iterative coding schemes, such as turbo codes and LDPC codes. This suggests a significant increase in speed compared to the conventional electronic decoding.
3. Alexander Barg, Bell Labs Error exponents of expander codes under linear-complexity decoding A class of codes is said to reach capacity $\cC$ of the binary symmetric channel (BSC) if for any rate $R<\cC$ and any $\epsilon>0$ there is a sufficiently large $N$ such that codes of length $\ge N$ from this class provide error probability of decoding at most $\epsilon$, under some decoding algorithm. Expander codes are known to reach capacity of the binary symmetric channel under linear-complexity iterative decoding. Error probability for iterative decoding of expander codes was shown by Barg and Z{\'e}mor (2001) to decrease exponentially with code length for all code rates $0<R<\cC$. In this work we focus on the most important region of code rates, close to the channel capacity. For this region we estimate the error exponent for a randomized ensemble of expander codes, obtaining the best known error exponent provided by binary codes under linear-time decoding. Joint work with Gilles Zemor.
4. Louay Bazzi, MIT Encoder Complexity versus Minimum distance The general problem under investigation is the study of the minimum distance of a code given constraints on the computational complexity of it's encoder. We argue that if the encoder is a branching program of linear depth and subexponential width -- or equivalently, if the encoder is a (nonuniform) RAM with sublinear space and linear time -- then the minimum relative distance of the code must go to zero. We give applications to Turbo-Like codes. Our argument uses Branching Techniques introduced by Ajtai. We investigate also the case when the encoder is a cascade of branching programs or a bounded depth circuit, in the addition to case when the testing whether a given string is a a codeword is doable by a bounded depth circuit. Joint Work with Sanjoy Mitter and Dan Spielman.
5. Louay Bazzi, MIT Some Codes Constructions from Group Actions The general problem under investigation is the randomized and explicit constructions of binary linear codes that are invariant under the action of some group on the bits of the codewords. We analyze an Abelian randomized construction, a related explicit construction connected to hyperelliptic curves, and a nonabelian randomized construction. We started by looking at one of the simplest randomized constructions of such codes, namely rate half quasi-cyclic codes of prime message length. So we have a cyclic Abelian group of prime order acting on two disjoint copies of itself. There is an old result on such codes that says that a random rate half codes from this ensemble achieves the Gilbert-Varshamov (GV) assuming that the Extended Riemann Hypothesis (ERH) holds to get infinitely many special primes. We argue that this result holds without the need to assume the Extended Riemann Hypothesis. Namely, for almost all primes a random quasi-cyclic code achieves the GV bound. In this ensemble of codes there is a natural explicit code based on quadratic residues. We conjecture that this codes achieves the binary GV bound. We show that the codewords in this codes are in one to one correspondence with special hyperelliptic curves over a finite field of prime order. We can express the minimum distance of the code in terms of the maximum numbers of rational points on a curves from this family of curves, or equivalently in terms of the corresponding character sums. This leads to a conjecture about a bound tighter than the general estimates from Weil's theorem for a special class of curves. Finally, we relate the code to a special cyclic quadratic residue code over a nonbinary alphabet. Next, we move to a slightly more general randomized construction. We consider the randomized construction of codes that are in invariant under the action of an abelian group on a constant number of disjoint copies of itself. We argue that (when the order of the group is odd) : If the smallest dimension of a nontrivial irreducible $\F_2$-representation of the group grows faster than logarithmically in terms of the number of elements in the group, then the resulting codes achieve the Gilbert-Varshamov bound with a high probability. We list many infinite families of groups satisfying the above property. When the group is nonabelian, we note that the story sounds different since we can establish by counting arguments that the action of the group on a single copy to itself can lead to asymptotically good codes in the case of one of first nontrivial nonabelian groups -- namely the dihedral group. We argue that for infinitely many block lengths a random rate half ideal in the binary group algebra of the dihedral group is asymptotically good with a high probability. Our result is the first provably good randomized construction of codes that are ideals in the group algebra of a group. This leads to the question of looking at randomized constructions in the group algebra of other nonabelian groups. Joint work with Sanjoy Mitter and Dan Spielman
6. Marc Fossorier, University of Hawaii Enhanced Iterative Decoding of Finite Length LDPC and Turbo Like Codes In this presentation, the use of a reliability-based decoding algorithm is examined to address and overcome the suboptimality of iterative decoding for finite length codes. The a posteriori probabilities fed by the iterative decoding are regarded as reliability information and an efficient algorithm for the overall linear block code is applied at certain iterations. Simulation results show that the suboptimality of iterative decoding for moderate length codes can be at least partially compensated by this combined approach. Some insights about the potential additional coding gains achievable by the combined approach are investigated based on the characteristics of the constituent decoders, which highlights the nature of suboptimality in iterative decoding. Joint work with Motohiko Isaka and Hideki Imai.
7. Parikshit Gopalan, Georgia Tech Adversaries, Codes and Information. Abstract: In this talk we describe simple techniques called Code Scrambling that allow us to relate the average performance of a code to the worst-case performance of its scrambled version C'. The performance of a scrambled code against any adversary (even a computationally unbounded one), equals the performance of the unscrambled code against a symmetric channel. A symmetric channel is a Markov chain that makes random changes to random positions. Scrambled versions of some codes can correct errors beyond the classical error correction distance with negligible probability of failure. We will show that Scrambled Reed Solomon codes of low rate can correct nearly twice the number of errors that conventional Reed Solomon codes can. We discuss other codes whose performance is likely to improve with scrambling. We discuss some open questions that this work raises. Joint work with Richard J. Lipton and Yan Zong Ding.
8. Ido Kanter, Bar-Ilan University Statistical Physics, Error Correcting Codes and Cryptography Gallager-type error-correcting codes that nearly saturate Shannon's bound are constructed using insight gained from mapping the problem onto that of an Ising spins system. The construction is based on the introduction of complex matrices, used in both encoding and decoding, which comprise sub-matrices of cascading connection values. The finite size effects are estimated for comparing the results to the bounds set by Shannon. The critical noise level achieved for certain code-rates and infinitely large systems nearly saturates the bounds set by Shannon even when the connectivity used is low. The performance of the suggested codes is evaluated for both Gaussian and binary symmetric channels. In the second part of the talk a public-key cryptosystem based on a Gallager-type parity-check error-correcting code is presented. The complexity of the encryption and the decryption processes scale linearly with the size of the plaintext. The linear complexity is based on the observation that as long as the average connectivity, (number of non-zero elements per column) of a square matrix B is smaller than 2, the graph representing the matrix is below the percolation threshold and $B^{-1}$ is sparse too.
9. Ralf Koetter, UIUC Soft Decoding of Reed Solomon and AG Codes Reed Solomon codes and algebraic geometric codes play a prominent role in the construction of concatenated codes. The recent list decoding algorithm of Guruswami-Sudan extends the correction radius of Reed Solomon codes substantially beyond half the minimum distance. The central problem in using this algorithm in a concatenated coding system is to find an assignment of weights to the received positions that maximized the correction radius. We address and solve this issue for discrete channels and in particular channels that correspond to concatenation with simple inner codes. Using these optimized weights we can construct codes that on a binary symmetric channel and for rates less that 0.125 perform essentially as well as codes achieving the Gilbert-Varshamov bound.
10. P. Vijay Kumar, University of Southern California - Los Angeles A [ N log(N) ]^3 Algorithm for the Construction of Algebraic Geometric Codes better than the Gilbert-Varshamov Bound Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic geometric (AG) codes with asymptotic performance exceeding the Gilbert-Varshamov (G-V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward in 1995-96, Garcia and Stichtenoth (G-S) provided an explicit description of algebraic curves, such that AG codes constructed on them would have performance better than the G-V bound. We present here the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of G-S. The symbol alphabet of the AG code is the finite field of q^2 >= 49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF(q^2), is upper bounded by [N log_q(N)]^3 where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G-V bound. Some examples of such concatenation are included. This is joint work with K. Shum, I. Aleshnikov, H. Stichtenoth and V. Deolalikar. This research is supported by NSF under grant CCR-0073555.
11. Michael Luby, Digital Fountain Invited talk: Content distribution and Coding Theory This talk will describe a new class of codes, called LT codes in the commercial world. The basic properties of the codes, and their commercial applications to reliable massively scalable data distribution, will be described.
12. Muriel Medard, MIT Network Coding for Capacity and Robustness We present an overview of results in the area of network coding for capacity and for robustness against permanent network failures. We also address the relation between network coding and network management. The first part of the talk addresses network capacity. Recent work by Li, Yeung, Ahlswede and Cai examined the issue of network capacity for multicast networks. These results showed that linear network coding is sufficient for multicast networks and showed that the min-cut max-flow theorem determines feasibility of multicast connections. More recently, Koetter and Medard considered an algebraic approach to network coding and extended the results to non-multicast networks. In particular, they showed that min-cut max-flow necessary and sufficient conditions can be extended to a much larger class of connections than multicast connections, but also showed that in general min-cut max-flow conditions are necessary but not sufficient. In general, the feasiblity of a connection can be found in polynomial time, athough the complexity of finding network codes that satisfy these conditions may not be polynomially bounded. Network codes may be used not only to achieve capacity, but also to provide robustness from permanent (non-ergodic) link or node failures. The second part of the talk examines the issue of coding for robustness. We overview traditional means of providing recovery in networks using switching rather than coding. All of these methods can be shown to reduce to codes. Koetter and Medard have shown the rather surprising fact that, for multicast networks, recovery can be achieved using static codes in the interior of the network. Thus, only the terminal nodes need to react to network changes for multicast connections. The issue of network codes for recovery is tightly linked to that of network management, the topic of the third and final part of our talk. The log of the number of codes that we may need to use in order to respond to different failure scenarios may be taken to represent the number of network management bits necessary to recover from network failures. We present some new results by Ho, Medard and Koetter regarding the number of codes needed to recover from failures. In particular, they have shown some tight upper and lower bounds for the number of codes necessary when using receiver-based and network-wide codes.
13. Michael Mitzenmacher, Harvard University Title: Verification codes Current LDPC codes for error-correction focus on the bit level or on symbols consisting only of a few bits. We introduce new LDPC codes designed to handle data at the packet level, where a packet consists of a large number of bits. By using a pseudorandom transformation of the input data, we find simple linear time LDPC codes that can cope with a large number of packet level errors with high probability. Our novel framework uses check packets to verify the correctness of message packets as well as correct erroneous message packets. We provide an analysis of our verification codes and suggest several open problems. Joint work with Michael Luby.
14. Andrea Montanari, ENS Why "practical" decoding algorithms are not as good as "ideal" ones? Good codes are usually characterized by the critical noise $n_c$ for perfect error correction under ideal decoding. The conceptual frame for understanding the abrupt phenomenon occurring at the critical noise (namely the transition from an error-free regime to a noise-dominated regime) is given by the Shannon theory. On the other hand many practical (i.e. linear time) algorithms have a no-error regime which ends at a lower "dynamical" critical noise. We shall argue that one can define an optimal dynamical noise $n_d$ and that $n_d$ is characterized by an algorithm independent phenomenon. Our argument is based on the analysis of simulated annealing decoding and its comparison with belief propagation decoding.
15. Omer Reingold, IAS Constant Degree Lossless Expanders and their Expander Codes We present the first explicit construction of constant degree "lossless" expanders. In these graphs, the expansion factor is almost as large as possible: (1-e)D, where D is the degree and e is an arbitrarily small constant. The best previous explicit constructions gave expansion factor D/2. The D/2 bound was obtained via the eigenvalue method, and is the best possible using this method [Kahale95]. We then discuss the expander codes [Gallager, Tanner, Sipser-Spielman] that correspond to our lossless expanders. These are new explicit linear codes of relative rate (1-delta) and minimum distance (delta / polylog(1/delta)), which is quite close to the Gilbert-Varshamov bound for small delta. Moreover, the losslessness of our graphs implies a very simple linear-time decoding algorithm (taken from [Sipser-Spielman]).
16. David Saad, NCRG MAP, Typical Set Decoding and the Magnetization Enumerator in LDPC - A Statistical Physics View We study the roles of both weight and magnetization enumerators in decoding corrupted messages encoded using low density parity check error correcting codes, using the methods of statistical physics. The analysis, based on the replica method [1], provides an intuitive interpretation of the relation between different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM). The predictions obtained for the critical noise level below which successful decoding is theoretically possible, are more optimistic than those derived via the methods of information theory and are in excellent agreement with results obtained elsewhere, combining Gallager's method and the statistical physics approach [2]. We also show that the critical noise levels for typical pairs, MAP and MPM decoding must coincide (as also proved in [3]), and provide an intuitive explanation to the difference between MAP and MPM decoding within the statistical physics framework. [1] Nishimori, H.: Statistical Physics of Spin Glasses and Information Processing. Oxford University Press, Oxford UK (2001). [2] Kabashima, Y., Sazuka, N., Nakamura, K., Saad, D.: Tighter Decoding Reliability Bound for Gallager's Error-Correcting Code: Phys.Rev.E 64, 046113 (2001). [3] MacKay, D.J.C.: On Thresholds of Codes: unpublished, http://wol.ra.phy.cam.ac.uk/~mackay/CodesTheory.html (2000). Joint work with Jort van Mourik and Yoshiyuki Kabashima.
17. Amin Shokrollahi, Digital Fountain Complexity of AG codes In this talk we will review some of the results on the running times of various algorithms pertaining to Algebraic-Geometric codes.
18. Emina Soljanin, Bell Labs Bit-Optimal Decoding of Codes whose Tanner Graphs are Trees We introduce a group algebra formulation for bit optimal decoding of binary block codes. We use this new framework to give a simple algebraic proof that Pearl's and Gallager's belief propagation decoding algorithms are bit-optimal when the Tanner graph of the code is a tree. We believe that these derivations of known results give new i nsights into the issues of decoding on graphs from the algebraic coding theorist's point of view.
19. Nicolas Sourlas, ENS Statistical Mechanics and Capacity Approaching Codes It is known that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. I will show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.
20. Amnon Ta-Shma, Tel Aviv University Extractor Codes Shannon showed that data can be communicated over every channel with positive capacity. In particular even highly noisy channels, e.g., when every received signal can originate from some half of the symbols in the alphabet, can be used to transmit information as long as noise on different symbols is independent. Hamming studied the adversarial noise model where noise on different symbols may be correlated and may depend on the whole message being sent. In this paper we study error correcting codes for highly noisy channels (as the one above) in this adversarial model. Our main conceptual contribution is an equivalence between error correcting codes for such channels and extractors. Our main technical contribution is a new explicit error correcting code based on Trevisan's extractor that can handle such (and even noisier) channels. Our new code has both polynomial time encoding and polynomial time soft-decision decoding algorithms. We note that Reed-Solomon codes can not handle such channels, and our study exposes some limitations on list decoding Reed-Solomon codes. Our results are also the key tool in a recent work solving the seemingly unrelated question of storing a set of elements in a way that membership in the set can be determined by looking at only one bit of the representation. We also show that our results improve previous results on the hardcore bits problem. Joint work with David Zuckerman and Shmuel Safra.
21. Salil Vadhan, Harvard University Applications of Local List-Decoding Algorithms In the past few years, very fast "local" list-decoding algorithms for Reed-Muller codes have been found. These probabilistic decoding algorithms manage to meaningfully solve the list-decoding problem while only reading a tiny portion of the received word. In this talk, we will focus on some recent applications of these algorithms in complexity theory. In particular: - Strong results relating worst-case complexity and average-case complexity, with applications to derandomization. - Extracting nearly uniform bits from sources of biased and correlated bits, for sources which are generated by an efficient sampling algorithm. Joint works with Madhu Sudan and Luca Trevisan.
22. Pascal Vontobel, ETH Zuerich Algebraic Code constructions for iterative decoding Channel codes can be pictorally represented with the help of so-called Tanner/factor graphs. Decoding of these codes with the help of the sum-product algorithm can then be represented as message-passing along the edges and processing at the vertices. For codes whose graphs fulfill certain properties this decoding algorithm gives near maximum-likelihood performance. Among the desirable properties of these graphs is that they look locally tree-like or equivalently that they have no short cycles. Starting from graphs with large girth (the girth is the length of the smallest cycle), we discuss several different possibilities to construct regular and irregular low-density parity-check (LDPC) and turbo codes.
23. Avi Wigderson, IAS Cayley Expanders from Linear Codes Theorem: The cyclic shifts of almost every two n-vectors over F_2 form a generating matrix of an assymptotivally good linear code In this theorem, the cyclic group on n elements acts on the coordinates of the vector space, and the generating matrix is the orbit of only two vectors. More generally, we consider the action of any group with n elements on the coordinates. We study when such constant number of orbits can generate an assymptotically good code. We give a sufficient condition on the distribution of dimensions of the irreducible representations of G which ensures the existence of such succinctly described codes. We then relate this condition to the expansion properties of the group G. Finally we show how to use such orbits in an iterative construction of expanding Cayley graphs of near-constant degree. Joint work with Roy Meshulam.
24. Jonathan Yedidia, MERL Projection Algebra Analysis of Error-Correcting Codes We explain how to use the projection algebra technique to analyze an arbitrary parity-check code as decoded by the belief propagation (BP) algorithm on the binary erasure channel (BEC). Using this technique, we can exactly compute the block error rates and the bit error rates of every bit at every iteration of the decoding process. Our motivation is that the results of such computations can serve as an objective function in a search for good codes. The pioneering paper by Luby, Mitzenmacher, Shokrollahi, and Spielman, which analyzed and optimized irregular low-density parity-check (LDPC) codes decoded by a BP decoder and used over the BEC, demonstrated that one could design capacity-approaching codes by optimizing the codes for their performance as measured using the density evolution technique. Our technique builds on density evolution, but ameliorates its major flaw by exactly accounting for the statistical dependencies that exist in finite blocklength codes. Recently, Di, Proetti, Teletar, Richardson, and Urbanke have shown how to perform a finite length analysis of regular LDPC codes used over the BEC. They were able to analyze both BP decoding and maximum likelihood decoding, but their analyses was limited to averages over ensembles of regular LDPC codes. Our analysis as presented here also only applies to the BEC, and we are further limited to BP decoding, but the advantage of our technique is that we are able to analyze the performance of a single, specific, parity-check code. Although the exact projection algebra technique is computationally intractable for codes of large block-length, it can be efficiently approximated in a way that give results that are still asymptotically exact in the limit of small erasure rates. We discuss how to use the information obtained by our techniques to optimize finite length parity check codes. Joint work with Erik Sudderth (MIT) and Jean-Philippe Bouchaud (Saclay).
25. Junan Zhang, UCSD Finite Length Analysis of LDPC Codes with Large Left Degrees The asymptotic performance of LDPC codes under density evolution was studied in a number of papers. However, the finite block length behavior of LDPC codes is less understood. A recent paper by C.Di, D.Proietti, T.J. Richardson, E.Telatar and R.Urbanke considered this finite-length error probability when the codes are used over erasure channels and decoded iteratively. The authors derived recursions for maximum stopping sets to yield the (average) block- and bit- error probability for a given regular (ensemble) LDPC codes. Although these recursions apply to all regular LDPC codes, their computational complexity rendering them feasible only for small block lengths. To calculate the error probability for large block lengths, the authors derived efficient recursions for left degrees 2 and 3. In this paper we extend their work and derive an efficient recursion for general left degree, which can be used to determine the block- and bit- error probability of two types of LDPC codes: regular codes with large left degree and irregular codes with simple left degree sequences. We apply this recursion to determine the block error probability of several codes for different block lengths and relate the behavior of their error floors, when the block length increases, to their lowest left degrees.
26. Codes in Theoretical Computer Science David Zuckerman, UT Austin We survey applications of error-correcting codes in theoretical computer science. The most natural applications are to fault tolerance; we focus on more unexpected applications in pseudorandomness and other areas. We explore which properties of codes are used, notably minimum distance, list decodability, and local decodability.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center

Document last modified on November 30, 2001.