I've told you a bit about information.
Bits. Labels. Probabilities.
I is equal to minus the sum over i of
P sub i, log to the base 2 of P sub i
The fundamental formula of
information theory
I told you about mutual information
which is if I have two variables,
such as the input and output to a channel.
The mutual information tells you... is
equal to the amount of information that is
shared in common between input and output.
It is the information
that passes through
or gets through the channel.
And in fact, from Claude Shannon,
it's actually equal to
the practical channel capacity.
Or if I take the input probabilities, or
frequencies that maximize the mutual
information, that mutual information is the
rate at which information can be sent
reliably down this channel. You cannot
send information at a higher rate, and
you can send information at that rate.
This is a tremendously practical
application of information theory. Because
it tells us that if we have noisy channels
or lossy channels, channels where we're
using sound, channels where we're using light,
chanels if we're using electromagnetic
radiation, channels where we send information
through the mail, any such channel has
a capacity, and Shannon's theorem tells us
what that capacity is, it tells us that we
can't surpass it, and it tells us how to
achieve it. And this is at the basis of
the application of information theory to
practical communications, for instance via
fiber-optic cables.
So, there are some fun examples of this.
A nice way to look at this picture is that
here we have this channel. We have x in...
we have P of x sub i. Here we have
the output. We have P of y sub j,
y out, given x sub i in.
And then we have the associated mutual
information.
So here we have I(x), this is the
information in.
Here we have I(y), this is the
information that comes out.
The information that goes through
the channel like this is the mutual
information between the input and
the output. We can also look at
some things that I'm going to call "loss,"
and another thing that I'm going to call
"noise." So, what is loss? Loss is
information that goes into the channel,
but does not come out. Like the roaches
going into a roach motel. So, what is that?
It's information that we don't know about
the input, given that we know the output.
So, if we know the output, this is
residual stuff that went in, bits that
went in, that never came out. Similiarly,
the noise is information that came out
that didn't go in. So noise is stuff where
if we know exactly what went in, it's
residual bits of information that came
out that had no explanation in terms of
what went in. So we have a nice picture
in terms of the whole set of processes
that are going on in information. We have
the information going in, we have the
information going out. We have the loss,
which is information that goes in that
doesn't come out. We have noise, which is
informaiton that came from nowhere
that didn't go in - of course, it actually
comes from physical processes. And finally
we have the mutual information, which is
the information that actually goes through
the channel and that represents the
channel capacity.
So, I also talked a bit about computation.
So, if you have a digital computer. Here is
what digital computers looked like when
I was a kid... You had, like, a tape thing,
you had a bunch of little lights on the
front and switches, and then you
read the tape, and then it spewed out some
output, maybe on some paper tape -
you could even
put some input on paper tape - it would
have some memory like this. All a digital
computer is doing is
breaks up information
into bits which are the smallest chunks of
information, typically called 0 and 1, or
true and false, in a digital computer.
And then flips those bits
in a systematic fashion.
So for all their power and
all their stupidity, all that these
digital computers that we have, including
things like our smart phones, as well as
our desktops and supercomputers, all
they're doing is registering and storing
information as bits and then flipping
those bits in a systematic fashion.
And let me just remind you about this
fundamental theorem about computation
which is that any digital computation
can be written in some kind of
circuit diagram.
Here's x, here's y, here's z. Here's
something where I make a copy of x,
I take an OR gate... This is "OR",
you will recall.
Here's a copy of X, here's X here.
This is X or Y.
Also known as X or Y.
And here i can say
for example, take an AND gate, and
I can here send this through a NOT gate
And then I can combine them in another
AND gate, And in the end, I think that
what I have is NOT X AND Z AND
(X OR Y).
So, when I have a digital computer,
what happens is that it takes bits of
information, it performs simple AND, OR,
NOT, and copy operations, and
by doing these sequentially, in whatever
order you wanted to do it, you end uo
evaluating arbitrary logical expressions...
NOT X and Z AND X or Y... whatever
that means, I have no idea what it means.
But it is what it is, it means what it is.
So, if we talk about digital computation,
all digital computers are is taking
information and processing it.
And if we put together computation
and communication,
and probabilities,
what we find is that taking together
the idea of information, processing
information as computation,
sending information reliably from
one place to another is communication
this information refers at bottom to the
probabilities of events... being sunny,
being rainy. Probability that a photon
going into a channel makes it out the
other side. Probability of 0,
probability of 1, probability of heads,
probability of tails... but when we put
together these three pieces
interlocking, what we get is the theory
of information.
And I hope that in the course
of these brief lectures here, I've been
able to convince you that these remarkable
processes that are going on all
around us, the fault, or result of the
information processing revolution that began
in the mid-twentieth century and continues
in fact, continues at an accelerating rate
to this day, can be understood with
a simple set of mathematical ideas that
are interlinked with each other, and give
a set of ideas of very profound richness
and impact on human society with
implications for... I don't know what!
Thank you for your attention,
Do well on the homework,
Exam will be multiple choice, I am sure
you will all do well.