Introduction to coding theory (CMU, Spr 2010)

April 7, 2010

Lecture 20 summary

Filed under: Lecture summary — Venkat Guruswami @ 6:46 pm

We touched upon some aspects relating to the combinatorics of list decoding Reed-Solomon codes. We discussed the geometric intuition underlying Reed-Solomon decoding, and presented Sudan’s algorithm for polynomial reconstruction/list decoding RS codes. We analyzed it by optimizing individual degrees leading to an algorithm working for agreement parameter t > 2 \sqrt{kn} where k is the degree and n is the number of points. By optimizing the (1,k)-weighted degree, we improved this to t \ge \sqrt{2kn}.

We motivated the method of using multiple zeroes in the interpolation with an example, and then presented the details of how to enforce multiple (say w) zeroes at a point for a bivariate polynomial, why it buys us w zeroes for each point of agreement, and why this should improve the agreement t needed by a further \sqrt{2} factor thus matching the Johnson bound.

April 2, 2010

Lecture 19 summary

Filed under: Lecture summary — Venkat Guruswami @ 7:54 pm

We pinned down the “list decoding capacity” for q-ary codes as 1-h_q(p), and saw that for large q this implies codes of rate R list-decodable up to a fraction 1-R-\epsilon of errors. We recalled the Johnson bound and how it implies a way to argue about list decoding properties knowing only the distance of the code. For Reed-Solomon codes this suggests that list-decoding from a fraction 1-\sqrt{R} of errors should be possible. This trade-off between rate and list decoding radius is best possible if one only appeals to the Johnson bound.

We then began the algorithmic segment of list decoding, setting up the stage for list decoding Reed-Solomon codes. In particular, we gave an algorithm for a toy problem where given a string which is the “mixture” of two codewords encoding polynomials p_1 and p_2, we recover both p_1 and p_2.

March 31, 2010

Lecture 18 summary

Filed under: Lecture summary — Venkat Guruswami @ 3:07 pm

We discussed a method for distance amplification using expander graphs, and how the resulting codes can be decoded via a majority logic algorithm. We discussed how to get near-MDS codes of rate R that enable linear-time correction of a fraction (1-R-\epsilon)/2 of errors.

We motivated list decoding as a primitive to bridge between the Shannon random errors model and the Hamming worst-case error model. We stated and proved the existence of list-decodable codes that achieve a rate vs error-correction radius trade-off similar to the Shannon capacity for the q-ary symmetric channel. We commented on why the proof does not work as such for linear codes.

Notes on lectures 16,17

Filed under: Lecture notes — Venkat Guruswami @ 11:15 am

A draft of the notes on expander codes and their decoding that was covered in last week’s lectures are now posted on the course webpage. Also posted are related notes (that includes some illustrative figures) from a previous offering of the course.

March 29, 2010

Problem set 3

Filed under: Problem sets — Venkat Guruswami @ 5:19 pm

The 3rd (and final) problem set is now posted on the course webpage. It is due before the beginning of lecture on Friday, April 23.  As always, I encourage you to start thinking about the problems early. You can use the comments section of this post to raise any questions or requests for clarification.

March 26, 2010

Lecture 17 summary

Filed under: Lecture summary — Venkat Guruswami @ 9:58 pm

We proved the distance property of Tanner codes based on (spectral) expanders using a simple application of the expander mixing lemma. We discussed an decoding algorithm for the codes (to correct up to a number of errors about 1/4 the bound on minimum distance), based on O(\log n) iterations of decoding the local codes. We saw a distance amplication technique using dispersers which yield codes of relative distance 1-\epsilon over an alphabet of size \exp(O(1/\epsilon)).

I’d like to make two clarifications about the lecture. The first one concerns the calculation in the analysis of the decoding algorithm where we argued that the set T_1 was a constant factor smaller than S_1. If we are content with ensuring that |T_1| \le \frac{|S_1|}{1+\epsilon}, then it suffices to take the degree d of the expander to be at least 3\lambda/\delta_0 (like I had originally intended to set; in particular the degree need not grow as 1/\epsilon).

Indeed, by the expander mixing lemma and using that |S_1| \le (1-\epsilon) \left( \frac{\delta_0}{2} - \frac{\lambda}{d} \right) n, we have, in the notation from the lecture,

\displaystyle \frac{\delta_0 d}{2} |T_1| \le (1-\epsilon) \left( \frac{\delta_0 d}{2} - \lambda \right) |T_1| + \lambda \frac{|S_1|+|T_1|}{2} \ ,

which upon rearranging yields

\displaystyle |T_1| \le \frac{\lambda}{\epsilon \delta_0 d + (1-2\epsilon) \lambda} |S_1| \le \frac{|S_1|}{1+\epsilon} \ .

(The last step follows if d \ge 3\lambda/\delta_0.)

The second clarification concerns the linear time implementation of the decoding algorithm (instead of the obvious O(n \log n) time implementation). The key insight to argue this is to observe that in each iteration, the only vertices (in the relevant side for that iteration) that need to be locally decoded are those that are adjacent to some vertex on the other side that had some neighboring edges flipped in the local decoding of the previous iteration. The latter set shrinks geometrically in size by an argument as above. Let us be somewhat more specific. After the first (left) iteration, for each v \in L, the local subvector y_{|\Gamma(v)} of the current vector y \in \{0,1\}^{E} belongs to the code C_0. Let T(y) \subset R be the set of right hand side vertices u for which y_{|\Gamma(u)} does not belong to C_0. Let z \in \{0,1\}^E be the vector after the running the right side decoding on y. Note that for each w \in L that is not a neighbor of  any vertex in T(y), its neighborhood is untouched by the decoding. This means that in the next iteration (left side decoding), all these vertices w need not be examined at all.

The algorithmic trick therefore is to keep track of the vertices whose local neighborhoods do not belong to C_0 in each round of decoding. In each iteration, we only perform local decoding at a subset of nodes D_i that was computed in the previous iteration. (This subset of left nodes gets initialized after the first two rounds of decoding as discussed above.) After performing local decoding at the nodes in D_i, we prepare the stage for the next round by computing D_{i+1} as the set of neighbors of all nodes in D_i whose local neighborhood did not belong to C_0 prior to decoding.

March 25, 2010

Notes 7: Justesen codes and Reed-Solomon & GMD decoding

Filed under: Lecture notes — Venkat Guruswami @ 10:48 pm

A draft version of the notes for the material we covered on Justesen codes, Reed-Solomon unique decoding, and GMD decoding of concatenated codes is posted on the course webpage. The material from Section 4 (Peterson’s algorithm) onwards has not been proofread and will be edited soon, but I wanted to make this version available now to avoid too much lag.

March 24, 2010

Lecture 16 summary

Filed under: Lecture summary — Venkat Guruswami @ 8:05 pm

We saw a sequential algorithm for expander codes based on successively flipping bits involved in more unsatisfied checks than satisfied checks, and proved that it corrects a constant fraction of errors (related to the size of the sets which expand by a factor of more than 3D/4).  We then considered a generalization called Tanner codes and saw how weaker expansion suffices to argue about its distance. We discussed the expander mixing lemma and its use to lower bound the distance of Tanner codes whose factor graph is the edge-vertex incidence matrix of a spectral expander.

March 20, 2010

Lecture 15 summary

Filed under: Lecture summary — Venkat Guruswami @ 6:04 pm

We finished the analysis of GMD decoding for concatenated codes. We saw how to use concatenation with outer code that can correct a small fraction of worst-case errors to construct codes that achieve the Shannon capacity of the BEC and BSC, together with polynomial time encoding/decoding. We began the discussion of low-density parity-check codes, and saw why unbalanced bipartite expanders with expansion more than D/2 give rise to asymptotically good binary linear codes.

March 17, 2010

Lecture 14 summary

Filed under: Lecture summary — Venkat Guruswami @ 4:35 pm

We discussed Peterson’s algorithm for decoding Reed-Solomon codes up to half the distance, and decoding algorithms for concatenated codes: both a naive algorithm and GMD decoding.

An extension till Monday, Mar 22 (firm deadline) for problem set 2 is allowed.

« Previous PageNext Page »

Blog at WordPress.com.