|
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 (logS) / N, so discarding half the codewords reduces the rate to R = Rʹ − 1 / N. In the large-N limit, no change at all!
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 β and δ, 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.
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.
This page maintained by Iain Murray.
Last updated: 2014/11/11 15:56:13
|
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |
