Thanks once again to all of you who took the course and hung in there for the semester! I certainly had a great time with the course, and we covered a lot of ground despite the few Friday classes that had to be cancelled.
I have entered the grades on the electronic web form and I think you should be able to access it soon.
If you have not done so already, please fill in the course evaluation at my.cmu.edu under Academics. You probably also got an email with instructions on where to fill this out.
There was some request for notes on the 3-query LDCs we covered in the final lecture. I may not be able to write full blown notes, but I’ll try to expand the lecture summary for that post with some details of the construction and analysis when I find time.
is 
. We then saw the higher degree generalization of Hadamard codes, where the message is interpreted as a degree 
homogeneous multilinear polynomial (i.e., all terms have degree exactly 
). This gave us codes of encoding length 
, and we discussed a 
-query local decoding algorithm. This was based on interpolating the restriction of the multilinear polynomial on a line in a random direction. Thus for any constant 
, we got codes that are locally decodable using 
.
monomials are allowed. (This actually reduces the rate compared to our earlier construction, but the big gain is that one is able to locally decode using only three queries instead of about 
such that 
is prime (such a prime is called a Mersenne prime), we gave a construction of 
-query LDCs of encoding length 
. Since very large Mersenne primes are known, we get 3-query LDCs of encoding length less than 
. We presented a 3-query algorithm and proved its correctness assuming the stated properties of the “matching sets” 
used in the construction, and then explained how to construct families of such subsets of 
of size 
.
(resp. 
) is the fraction of edges incident on degree 
variable (resp. check) nodes, an define the generating functions 
and 
. Then the rate of the LDPC code is given by
for every 
, and some constant 
, we argued why the message passing algorithm succeeds with high probability on 
for any constant 
.
— we can achieve a rate 
with decoding complexity 
(since the average variable node degree is 
).
-regular graphs on the binary erasure channel, and derived an expression for threshold erasure probability for which the algorithm guarantees vanishing bit error probability. We then turned to the binary symmetric channel, and discussed Gallager’s “Algorithm A” and derived the recurrence equation for the decay of the bit error probability. We briefly discussed Gallager’s “Algorithm B” as well, where a variable node flips its value if more than a certain cut-off number (typically majority after a few iterations) of its neighboring check nodes suggest that the node flips its value. We mentioned the values of the threshold crossover probability for some small values of 
and 
.
iterations which is smaller than the girth of the graph, for Algorithm A the BER is at most 
for some 
, and for Algorithm B for 
with an optimized cut-off for flipping, the BER is at most 
for some 
.
was 
-list decodable w.h.p. For random linear codes over 
, the result (or rather proof) was weaker, and only guaranteed a rate of 
. I had mentioned that this discrepancy in list-size between linear and general codes was recently resolved, showing that a random linear code of rate 
is 
possible choices for each codeword position does not affect the ability to correct with agreement 
(where 
is the rate), and we can “absorb” the effect of 
that are list-decodable up to a fraction 
of errors. The alphabet size is not far from the optimal bound of 
, and nicely combines ideas from the algebraic coding and expander decoding parts of the course.
.
) when the agreement fraction is more than 
. This was based on the extension of the Welch-Berlekamp algorithm to higher order interpolation (in 
variables). Unfortunately, this result falls well short of our desired target, and in particular is meaningless for 
.
-variate algorithm on a folded RS code with folding parameter 
, to list decode when the agreement fraction is more than 
. Picking 
, say 
and 
, then enables list decoding from agreement fraction 
. We will revisit this final statement briefly at the beginning of the next lecture, and also comment on the complexity of the algorithm, bound on list-size, and alphabet size of the codes.
and use higher degrees for the 
‘s in the polynomial 
as well as multiple zeroes at the interpolation points. In the lecture, however, we were content, for sake of simplicity and because it suffices to approach agreement fraction 
to be linear in the 
for rate 
of errors with 
rate and list-size 
. While the rate is positive for every 
bound. (We will soon see how this can be improved substantially by using codes with more powerful list-decoding properties than Reed-Solomon codes at the outer level.) Finally we defined (a version of) folded Reed-Solomon codes (we will give a list decoding algorithm for these next lecture).
Introduction to coding theory (CMU, Spr 2010) 