EE 553 Introduction to Information Theory

Information Theory contributes to and draws results from a number of other fields including:

Communication Theory

Its origins, however, are in Shannon's work in Communication Theory. Consider the block diagram Figure 1. To be specific, consider a discrete source (discrete-time, discrete-alphabet). The encoder maps sequences of source symbols into channel symbols. The decoder maps sequences of channel symbols into user (source) symbols.

Let the probability of error, P sub e, denote the probability of making an error in one symbol decision. Prior to Shannon, it was thought that to make P sub e arbitrarily small the information rate through the channel must go to zero. Shannon showed that there is a rate (capacity) such that for all information transmission rates less than this, P sub e can be made arbitrarily small! He also introduced methods to achieve this.

These results rely on quantitative measures of information: entropy, mutual information, relative entropy, etc. The capacity is determined by a maximization of mutual information over input distributions for the channel.

Usually the encoder and decoder are separated as in the block diagram in Figure 2. The source encoder achieves data compression; the limits are determined by the source entropy. The channel encoder introduces redundancy to combat errors due to channel noise; it can be designed to shape the input distribution to approach capacity.

Complexity Theory.

A large research component of Computer Science studies complexity theory. Included here are quantities such as time-complexity, space-complexity, and Kolmogorov complexity. The third of these is most closely related to information theory and equals the length of the smallest program that can be written to reproduce the data. This quantity is approximately equal to the entropy.

Physics.

In statistical physics (statistical mechanics), the fundamental quantities studied are energy and entropy. The fundamental laws of physics include a statement that the entropy of systems must increase (subject to other constraints).

Statistics.

The Fisher information determines a lower bound on the variance of any estimator. Also, relative entropy determines the exponent in the probability of error in optimal detection algorithms as the data set grows.

Other areas will be discussed during the semester.

This file is created and maintained by Joseph A. O'Sullivan. Respond to him via jao@essrl.