Lecture 16, Tuesday w9, 2014-11-11
==================================

Today's lecture proved the "what's achievable" part of the noisy channel
coding theorem, following the notes in the slides week 8, up to slide 11,
very closely. MacKay pp161--167 covers the same material. Please ask
questions on the slides in NB if anything is unclear.

The one thing I didn't explicitly say at the end was the effect on the rate
of *expurgation*. The rate is $(\log S)/N$, so discarding half the
codewords reduces the rate to $R=R'-1/N$. In the large-$N$ limit,
no change at all!


Check your understanding
------------------------

Why is it that the proof initially gives the performance averaged over
codes, rather than for any particular random code?

How do we show that a vector lands in the typical set for any $\beta$ and
$\delta$, as long as $N$ is large enough?

How have we reconciled wanting to use the optimal input distribution of a
channel, with our other desire to restrict the inputs we use to a small set
that are non-confusable?

Are you confident you could justify each step to someone else? I'm not
going to ask you to regurgitate the whole proof. But I reserve the right to
remind you of parts of it, and then ask related questions.


Extra reading
-------------

Someone noticed that I didn't actually prove that communication at
arbitrarily low error probabilities isn't possible at rates $R>C$. You
should know that part of the theorem exists. And we've seen an argument for
the BSC. But I decided to omit the general proof and details from the
course. I may say a little bit about communicating at $R>C$, *rate
distortion theory*, in the last lecture, but it's non-examinable. If you're
keen, keeping reading Chapter 10, sections 10.4--10.5, pp167--168, which
gives the details.