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.


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 )

Google+ photo

You are commenting using your Google+ 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


%d bloggers like this: