About Information Theory

ABOUT UNCERTAINTY
"Nothing is certain, except death and taxes"

This page is intended for the students at the Institut National des Télécoms who are studying Information Theory. Nevertheless, it can be read by anyone interested in learning basics in Information Theory.
Most of the links it contains refer to files in HTML (Hypertext Markup Language), so you should have no problem viewing them with your browser. However, some files are in PS (post-script) format and you will need Ghost View to read them. Others are in PDF (Portable Document Format) and require Adobe Acrobat Reader for displaying.

Before starting studying Information Theory, it has to be said that basic concepts in Probability are required. If your memory needs to be refreshed about this subject, an interactive tutorial giving a comprehensive view of Probability and Statistics is available here.

To begin with, we can try to answer the question: What is information and how to measure it?

Information theory is useful when storing or transmitting information.
Information storage consumes considerable space as quality criteria are high and images and videos contain many binary digits. Accordingly, compression data algorithm have kept on building up to meet these demands.
As for transmitting information, two questions are to be answered:

How much information can be transmitted reliably through a given channel ? The answer was given by Claude Shannon. He wrote a famous article in October 1948 which states the most important results in Information Theory.

How to design the codec (encoder and decoder) so that errorson the transmitted signal can be corrected?

Most scientists agree that Information Theory began in 1948 with Shannon's famous article. Accordingly, it deserves some comments.

It is made of four parts:

Part I "Discrete Noiseless Systems"

The entropy of an information source is introduced and a proof of the noiseless coding theorem (theorem 9 page 16) is established.

Part II " The Discrete Channel with noise"

The most important result in Information Theory known as Shannon's second theorem lies on page 22 as theorem 11.

Part III "Mathematical Preliminaries"

Deals with continuous random variables. The connection between continuous and discrete random variables is the sampling theorem (theorem 13 page 34).

Part IV "The Continuous Channel"

A useful result in this part is the capacity of a Gaussian channel.

Part V "The Rate for a Continuous Source"

As a continuous source can take on an infinite number of values, the output of such a source requires a channel of infinite capacity (in bits per second) to be recovered exactly. Since channels are noisy, their capacities are finite and an exact transmission of the output of the source is impossible. This part intends to assign a definite rate to meet a certain fidelity of recovery.

The course can be divided into four parts:

information measure and entropy
data compression
transmission channel
error correcting codes

For those who are in a hurry, notes on coding by Jean Walrand will give them an overview. For the others, links to tutorials are listed in the tables below, according to the topics.

Information measure and entropy:

LINKS	AUTHORS	COMMENTS
Information Theory Primer	Tomas D. Schneider	A basic but nice introduction to uncertainty and information
A Short Course in Information Theory	David J.C MacKay	Lectures 1 and 2
Information Theory, Excess Entropy and Statistical Complexity	David Feldman	The first chapter
Shannon's famous article	Claude E Shannon	The first 12 pages
Digital Communications	Janak Sodha	Lectures 1 to 6
Eléments de Théorie de l'Information	Marc Uro	Chapter 1 (in French)

Exercises and solutions (in French) are available here.

Data compression:

LINKS	AUTHORS	COMMENTS
The Basis of redundancy	Bill Cherowitzo	Introduces the notion of redundancy and how to measure it.
Information Theory, Excess Entropy and Statistical Complexity	David Feldman	Chapter 2 is about source entropy and chapter 3 deals with Markov chains, introducing recurrent and transient states. Lots of referencies are available.
Beginner's Introduction to Simple T-Codes	Gavin Higgie	A nice introduction to coding theory. Deals with uniquely decodable codes, instantaneous codes, prefix codes and Huffman codes. Develops concepts of codeword synchronisation. Contains many referencies and a glossary.
Data Compression	Debra A. Lelewer and Daniel S. Hirschberg	A comprehensive course about static and adaptive coding methods.
Compression Techniques Tutorial	Derek Sansom	The first part is about run length coding, Huffman and Lempel Ziv coding. Contains applets as for examples and to test your knowledge of coding and decoding. Second part explains JPEG and MPEG standards. There are also comparisons between JPEG and GIF images.
Lectures and Homework	John C. Kieffer	In addition to a traditional course, it contains Matlab applications. A series of homework and transparencies are available as well.
Shannon's famous article	Claude E Shannon	In part I, English language is given as for an example of information source.
Eléments de Théorie de l'Information	Marc Uro	Chapter 2 (in French).

Among uniquely decodable codes, Huffman codes are the most efficient in the sense that they have the minimum expected length, provided that the sourcewords length is fixed. Here is a quick demonstration of how a Huffman code is designed.

An important application of Huffman coding concerns JPEG (Joint Picture Expert Group) standard. A JPEG tutorial describes how JPEG works and compares JPEG images according to their quality factors.
To learn more about Huffman codes.
GIF (Graphic Image File Format) is another image compression standard which uses the LZW (Lempel Ziv Welch) algorithm.
A basic description of techniques used in audio and video compression is available in Video Compression Techniques and Standards by Gopal Lakhani. For more details about MPEG (Moving Picture Experts Group) standards, here is the MPEG site.

Exercises and solutions (in French) are available here.

Transmission channel

LINKS	AUTHORS	COMMENTS
Notes on Coding	Jean Walrand	Comments about channel coding theorem are available in Information Theory paragraph.
A Short Course in Information Theory	David J.C MacKay	Lectures 5 and 6 deal with channel capacity and channel coding theorem.
Shannon's famous article	Claude E Shannon	Part II
Digital Communications	Janak Sodha	Lectures 6 and 7 deal with channel coding theorem. In lecture 17, you will find the capacity of a gaussian channel and, as an application, the maximum rate for a modem transmitting information.
Eléments de Théorie de l'Information	Marc Uro	Chapter 3 (in French).

Exercises and solutions (in French) are available here.

Error correcting codes

LINKS AUTHORS COMMENTS

An Introduction to Error Correcting Codes Todd Rosenquist Basic concepts on linear and cyclic codes.

ECC FAQs ECC Technologies A list of 11 frequently asked questions about error correction.

Coding Theory and Cryptology Lecture Notes Bill Cherowitzo Coding Theory I, II, and III deal with linear codes, perfect and Hamming codes and decoding linear codes.

Error Control Coding Vajda Istv&aacuten Basics on linear codes with examples.

Bit Commitment Protocol over a Noisy Channel Adam Smith A funny demonstration animated with Java applets.

Error Correcting Codes for the Binary Symmetric Channel David JC MacKay About repetition codes, block codes, coding and decoding Hamming codes. Contains pictorial view of Hamming codes and a summary of codes' performances.

Eléments de Théorie de l'Information Marc Uro Chapter 4 (in French).

The best known error correcting codes are Hamming codes.
The cyclic code Encoder/Decoder is a Java applet where you can enter any generator polynomial, the default state of program is C(7,4) Hamming code generator polynomial. At the Encode/Decode output, you will get respectively the check-bits and syndrome.
Try it out.

Exercises and solutions (in French) are available here.

Fancy working out a solution to a practical problem by using your knowledge of Information Theory? Here is the problem:
At the game of mastermind, player A chooses an ordered sequence of four pieces, which is concealed from player B. The pieces are of the same shape and may be of different colours. Six colours are available, so that the chosen sequence may consist of one, two, three or four colours. Player B has to guess the sequence by submitting ordered sequences of four pieces. After considering the combination put forth by B, player A tells player B the number of pieces in the correct position and the number of pieces in the wrong position, but without indicating which pieces or positions are correct.
For the first submitted sequence, what kind of combination will provide the greatest average information?

Are you good enough at Information Theory to pass the exam?
You can consult previous years' exam questions and their solutions.

Further Reading

In A Discipline Independent by Robert M. Losee, you will find interesting thoughts about the notion of Information.
Lectures 9 and 10 of Digital Communications by Janack Sodha are an introduction to convolutional codes and turbo codes.
About cyclic codes, you can consult lectures 13 and 14 in Coding Theory and Cryptology Notes by Bill Cherowitzo.
Entropy on the World Wide Web by Chris Hillman provides articles about applications of entropy in economics, biology, ...
Code Design via Selection of a Statistical Model by John Kieffer gives a survey of methods to design a code when the data generating model is unknown.
Neil J.A Sloane's Home Page contains lots of references.

A Standard Bibliography in Information Theory has been drawn up by Ioannis Kontoyiannis.
If you are looking for the meaning of a word, you can look it up at What is ? or The Web Dictionary of Cybernetics and Systems.
Willing to improve your reading and listening skills in English? BBC World Service's site contains plenty of articles to be read or listened to, not to mention the Learning English section.

I hope you will have enjoyed browsing among the links of this page.
Should you have any question, remark or request, please do not hesitate to me.

This page is maintained by Marc Uro. The background comes from Roxanne's Graphix Gallery. The animated GIFs have been taken from the Animation Library and the Animation Factory.
The counter below has been provided kindly by SiteMeter.
Last updated on 17 January 2002.

"Jesus Christ was not only the Son of God - He was also of a very good family on His mother's side"

Don't click on the image below... unless you want to learn more about Oscar.