|
Information theory is:
Noisy channel coding is the second half of the course. For now, understand how reliable communication can happen at all. As communication includes passing messages within a computer (and between storage and main memory), what I really mean is “understand how modern digital computing is possible at all”. The result of Shannon’s 1948 paper was that for a given channel there is a critical rate (called the capacity). As long as we don’t try to exceed that rate, there are codes that make error probabilities as small as we like. We don’t have to decrease the rate to improve the error probability. Something for nothing! One of the top most surprising and useful theoretical results in computer science.
Source coding means “lossless compression”. How to store things with the minimum number of symbols. It could also be viewed as high-rate noisy channel coding in the simplest case where there’s no noise. So we need to understand source coding first, and it’s where we’ll continue next lecture.
Things you should be able to do after the lecture:
Required: To represent an item from a set of size S, we can use an integer from 0. . (S − 1). If we use a fixed number of bits to represent an arbitrary integer in this range, how many bits do we need? How would you compute it using a log base e (loge or ln) function?
To get ahead: Can you write a program/script to plot the bit error probability vs rate of different repetition codes, as in the slides or on p8 of MacKay (the class text)? If you try and have any problems, please report them on NB!
Maths background: MacKay textbook p1, pp22–24. If at all worried, work through the sheet on expectations on the website. You should be able to do the questions, not just read the answers. Otherwise, please pick a different course!
More detail on the lecture: MacKay pp3–8, pp14–15.
This page maintained by Iain Murray.
Last updated: 2014/09/18 12:19:41
|
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 |
