Lecture 1, Tuesday w1, 2014-09-17 ================================= Admin ----- * Post questions and requests for more detail on the class forum (NB). * All information and notes are at: http://tinyurl/itmsc * Questions? Email i.murray@ed.ac.uk. Please call me Iain. Mile-high course overview ------------------------- Information theory is: * Noisy channel coding * Source coding * Things I won't cover: cryptography, quantum stuff. Sorry! **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. Recommended lecture review -------------------------- 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$ ($\log_e$ 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! Recommended reading ------------------- **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.