Posted by: atri | November 6, 2007

## Lectures 29 & 30: Achieving Capacity for the BSC

We started today by completing the description of the deterministic GMD algorithm that can correct up to half the design distance of certain concatenated codes. We then saw how to use certain explicit concatenated codes to achieve the capacity of the $BSC_p$ for every $0\le p<\frac{1}{2}$ with polynomial time encoding and decoding algorithms. This answers in the affirmative the main question left open by Shannon’s work.

Next lecture, we will look at another interesting property of certain concatenated codes.