ITA Workshop : coding theory

I’m by no means an expert on coding theory, but I went to a few talks on coding that were interesting. Some were definitely geared for the specialist.

  • Decoding LDPC codes through tree pruning (Yi Lu and Andrea Montanari, Stanford)

    This was one of those talks where I got the big picture and then lost the details, since I haven’t really studied LDPC decoding algorithms in sufficient detail. Their idea is to use a new construction/technique by Dror Weitz to compute the marginals in the graph of an LDPC code. The idea is to create a tree rooted at xi whose marginal at the root is the same as the marginal at xi in the original graph. This tree is constructed by taking self-avoiding random walks through the graph and putting a leaf when the walk crosses itself. But such a tree is too big — truncating at a fixed level gives an approximate algorithm for decoding.

  • Communication over channels with varying sampling rate (Lara Dolecek, UC Berkeley)

    This paper looked at what happens when there is a sampling error in the received signal before the decoding block. Some symbol may be sampled twice or some symbol may be missed entirely and deleted. One way around this is to build better timing recovery blocks, and the other is to build better codes (which she does) that are resistent to these kind of repetition and deletion errors. This work comes up with number-theoretic formulation of the code design constraints, shows that existing codes can be modified to take into account these types of errors, as well as a modified belief-propagation decoding algorithm.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.