DIMACS Workshop on Codes and Complexity
December 4-7, 2001
DIMACS Center, CoRE Bldg., Room 431, Rutgers University, Piscataway, NJ
- Organizers:
- 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.
Abstracts:
1.
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.