Information and Entropy (MIT 6.050J)

Preface

These notes, and the related freshman-level course, are about information. Although you may have

a general idea of what information is, you may not realize that the information you deal with can be

quantified. That’s right, you can often measure the amount of information and use general principles about

how information behaves. We will consider applications to computation and to communications, and we will

also look at general laws in other fields of science and engineering.

One of these general laws is the Second Law of Thermodynamics. Although thermodynamics, a branch of

physics, deals with physical systems, the Second Law is approached here as an example of information pro-

cessing in natural and engineered systems. The Second Law as traditionally stated in thermodynamics deals

These notes and the course based on them are intended for first-year university students. Although they

were developed at the Massachusetts Institute of Technology, a university that specializes in science and

engineering, and one at which a full year of calculus is required, calculus is not used much at all in these

notes. Most examples are from discrete systems, not continuous systems, so that sums and differences can

be used instead of integrals and derivatives. In other words, we can use algebra instead of calculus. This

course should be accessible to university students who are not studying engineering or science, and even to

well prepared high-school students. In fact, when combined with a similar one about energy, this course

could provide excellent science background for liberal-arts students.

The analogy between information and energy is interesting. In both high-school and first-year college

physics courses, students learn that there is a physical quantity known as energy which is conserved (it cannot

proven to be so important and fundamental that whenever a “leak” was found, the theory was rescued by

defining a new form of energy. One example of this occurred in 1905 when Albert Einstein recognized that

mass is a form of energy, as expressed by his famous formula E = mc

2

. That understanding later enabled

the development of devices (atomic bombs and nuclear power plants) that convert energy from its form as

mass to other forms.

But what about information? If entropy is really a form of information, there should be a theory that

i

ii

not conserved: the Second Law states that entropy never decreases as time goes on—it generally increases,

but may in special cases remain constant. Also, information is inherently subjective, because it deals with

what you know and what you don’t know (entropy, as one form of information, is also subjective—this point

makes some physicists uneasy). These two facts make the theory of information different from theories that

deal with conserved quantities such as energy—different and als o interesting.

The unified framework presented here has never before been developed specifically for freshmen. It is

not entirely consistent with conventional thinking in various disciplines, which were developed separately. In

fact, we may not yet have it right. One consequence of teaching at an elementary level is that unanswered

questions close at hand are disturbing, and their resolution demands new research into the fundamentals.

Trying to explain things rigorously but simply often requires new organizing principles and new approaches.

In the present case, the new approach is to start with information and work from there to entropy, and the

new organizing principle is the unified theory of information.

This will be an exciting journey. Welcome aboard!

Chapter 1

Bits

˚

besides bits are sometimes used; in the context of physical system s information is often measured in Joules

per Kelvin.

How is information quantified? Consider a situation or experiment that could have any of several possible

outcomes. Examples might be flipping a coin (2 outcomes, heads or tails) or selecting a card from a deck of

playing cards (52 possible outcomes). How compactly could one person (by convention often named Alice)

tell another person (Bob) the outcome of such an experiment or observation?

First consider the case of the two outcomes of flipping a coin, and let us suppose they are equally likely.

If Alice wants to tell Bob the result of the coin toss, she could use several possible techniques, but they

are all equivalent, in terms of the amount of information conveyed, to saying either “heads” or “tails” or to

(to the base 2) of the number of equally likely outcomes.

Note that conveying information requires two phases. First is the “setup” phase, in which Alice and Bob

agree on what they will communicate about, and exactly what each sequence of bits means. This common

understanding is called the c ode. For example, to convey the suit of a card chosen from a deck, their code

might be that 00 means clubs, 01 diamonds, 10 hearts, and 11 spades. Agreeing on the code may be done

before any observations have been made, so there is not yet any information to be sent. The setup phase can

include informing the recipient that there is new information. Then, there is the “outcome” phase, where

actual sequences of 0 and 1 representing the outcomes are sent. These sequences are the data. Using the

agreed-upon code, Alice draws the card, and tells Bob the suit by sending two bits of data. She could do so

repeatedly for multiple experiments, using the same code.

2 1.1 The Boolean Bit

1.1 The Boolean Bit

As we have s een, information can be communicated by sequences of 0 and 1 values. By using only 0 and

1, we can deal with data from many different types of sources, and not be concerned with what the data

Algebra is a branch of mathematics that deals with variables that have certain possible values, and with

functions which, when presented with one or more variables, return a result which again has certain possible

values. In the case of Boolean algebra, the possible values are 0 and 1.

First consider Boolean functions of a single variable that return a single value. There are exactly four of

them. One, called the identity, simply returns its argument. Another, called not (or negation, inversion, or

complement) changes 0 into 1 and vice versa. The other two simply return either 0 or 1 regardless of the

argument. Here is a table showing these four functions:

0

NOT

1

ZERO

0

ONE

1

patterns (00, 01, 10, and 11). Think of each Boolean function of two variables as a string of Boolean values

0 and 1 of length equal to the number of possible input patterns, i.e., 4. There are exactly 16 (2

) different

ways of composing such strings, and hence exactly 16 different Boolean functions of two variables. Of these

16, two simply ignore the input, four assign the output to be either A or B or their complement, and the

other ten depend on both arguments. The most often used are AND, OR, XO R (exc lusive or), NAND (not

3 1.1 The Boolean Bit

x f(x)

It is tempting to think of the Boolean values 0 and 1 as the integers 0 and 1. Then AND would correspond

to multiplication and OR to addition, sort of. However, familiar results from ordinary algebra simply do not

hold for Boolean algebra, so such analogies are dangerous. It is important to distinguish the integers 0 and

1 from the Boolean values 0 and 1; they are not the sam e.

There is a standard notation used in Boolean algebra. (This notation is sometimes confusing, but other

notations that are less confusing are awkward in practice.) The AND function is represented the same way

as multiplication, by writing two Boolean values next to each other or with a dot in between: A AND B is

written AB or A B. The OR function is written using the plus sign: A + B means A OR B. Negation,