We've done a lot of work so far on weather scenarios for San Francisco and
for Los Angeles.
I put forward to you this probability model - some of you say it's not very
realistic.
Quite right! This is a teaching example. These are the probabilities because they
suit me and that's what I say they are. But what we did last time was to say if you're
worried that these could get distorted in transmission
what's the best thing to do? What's the easiest thing to do?
Well, the easiest thing to do -- I introduced you to this idea of a checksum digit at
the end.
What it meant was that so long as only one of these bits got distorted in
transmission you had a lovely situation of, if you like, "good codes". But if you
said hmmm!, one bit gets distorted as long as it's only one bit out of the three
you could end up with something like this: 0 becoming a 1. You receive 010
that's not in the list of valid codes - there's an error has happened there
and I think I covered also the fact that you may know that there is an error there.
This could arise in two or three different ways but you don't know how it
occurred. But at least it's nice to know that an error did occur. And at the very
end of the last discussion we said, well, if you want to say to San Francisco:
"I didn't receive your data correctly" you could send either an "Acknowledge" or a
"Not Acknowledge" signal. And I postulated to you that we might decide that an
Acknowledge signal to send back to San Francisco, meaning I got your three bit
code it makes sense to me; I got 000; It's foggy; Wonderful! I like it! If that is
the case send back a zero. On the other hand if I received a 010. It's not in this
allowed set of codes,
I would send back what's technically called a NAK, and we use a 1 bit for that. And
Many of you said:
"What would happen if these acknowledgement codes got clobbered on
their way back to San Francisco?!"
"How on earth would you then cope?" Well, armed with what we know now, the simple
approach instead of Acknowledge being a single 0 will make it a double zero.
Instead of "Not Acknowledge" being a 1
let's make it a 11. If one of these gets altered you might get a 10
you might get a 01. Similarly, here, if just one bit of those gets altered you
could equally end up with 01 or with 10. You expect if you're back in San
Francisco to either see a clean double zero or a clean double one. If you get these
you know that an error has occurred in transmission. But, as ever, you don't know
how it occurred.
Was it a distorted "Acknowledge" signal or a distorted "Not Acknowledge" signal.
Now this could go on forever, if we're not careful, y know San Francisco
sending back to Sacramento
"I've got a Not Acknowledge on your attempted Acknowledge signal". You just ...
... it's not good.
What you'd really like to do here - and this is a very useful lead-in for me to lead
into Hamming codes -
let's see how we can build up a slightly more sophisticated system,
adding one extra bit more. If you do that you can not only detect that an error
has occurred but you can actually correct it.
This gentleman, Richard Hamming, comes slightly after, I think, the person I've
mentioned already - the great Godfather of Information Theory,
Claude Shannon. So those are the two big names around about this era.
Shortly after the Information Theory and optimal codes, and so on, but in noiseless conditions,
Claude Shannon. A few years later comes Richard Hamming saying: "How can we detect
errors and, more to the point, how could we begin to correct to them?"
You've put this on a plate for me because I can discuss it in terms of how to get
an ACK and a NAK back to San Francisco
so that you can decide and correct it, if it gets clobbered?.
From now on the ACK will be to send three zeros. Tthe NAK will be to send
three ones. Suppose you send three.
Why is that magic? What does it do?
If it's a 3-bit pattern that you're sending, then if those get varied for any
reason of noise,
the total number of combinations in three bits - as we know off-by-heart now, is
2 to the power 3: eight combinations.
Let me just pluck out of thin air
the idea of representing those eight combinations possible, as being the
corners of a cube.
Let me not go through the algorithm for creating a Hamming code but just pluck it
out of thin air, as I'm so fond of doing.
Let's call this one, up here, our good code of 000.
Let's call this one - at the back lower corner of the cube - 111. So that one, if
you like, is representing ACK.
This one is representing NAK. So, so long as your properties of your [telephone] line were
such that errors were relatively infrequent, and you got mostly
one-binary-digit errors, then fine.
Here's what would happen. You might send 000 and it ended up as being received
as 010 - the middle bit got damaged.
You might send a 111 and it got received as a 110 - a one got into a zero.
You might, for example, have sent three zeros that I'll represent over here but the
left hand
bit got hit and became looking like a one. Here's 101.
This one is 001 and this one down the bottom is 011.
Let me just circle - these are what was actually transmitted.
So, can you see that what you are now in the lovely position of being able to say is:
if I received three zeros that's bound to be good.
Similarly if you see 111 trust it. It's a NAK
But if you receive a 010 what then should you do?
The rule is "maximum likelihood", if I can spell that, or "nearest neighbour"
correction. You can correct what you've received by saying the following: I
received 010
I know that that is not on my list of good codewords because the only good
ones are 000 and 111.
What's the most likely way to correct 010 back into being something good?
Well, the answer is by going up this line here, that's distance one away,
I change the middle bit back to zero and I've corrected it to 000. If
I receive 001 the most likely thing that's happened - with only one error
taking place - is that the trailing zero here got damaged into a one.
So, my correction should be like this
go distance one along the cube's edges like that. 100 corrects back to 000.
Now, same thing again look, the majority of the bits here - 110, two out of three, match up
with 111. Therefore my best and most likely correction is to turn the
zero back into a one.
How about 101? Oh yeah, obviously this was sent and it was the middle bit
that got hit and turned into a 0. So, correct that one
down here, Finally, over here 011. Again
two-thirds of the bits are correct but the leading 1 got hit and turned into a 0.
I clearly have to correct to that. So, you can see - looking at that - that for all of
the six corners of the cube that are not the good undamaged codes, you have with
nearest-neighbour maximum-likelihood correction, a distance-1 correction
algorithm. But the final thing to notice is that, for this to work and you may
remember - going back to my original example of when you can detect but you
can't correct - the thing there was that the distance between the good codes was two.
Notice that what we're doing here, now, is that between these good codes I shall
use yet another colour.
If you want to get from 000 to 111
you have got to take a journey involving one, two, three steps.
No matter how you get there you can go one two, three go
one, two, three down there,
the good codes are distance-3 apart.
So, this is the simplest example i can think of, of what was generalized by
Richard Hamming into being Hamming codes.
The way you actually build them up, algorithmically, is a bit involved but
let you all look up about this if you want some more information. Essentially
Hamming codes are really really good, and absolutely definitive in their time, for
doing distance-1 corrections, OK?.
For coping with things where only one
bit was in error.
Where things get massively mathematical, utterly fascinating and
deeply involved are the moment you start saying: "Well, I'd like to correct one bit
but not just in a 3-bit pattern.
How about in a 32-bit pattern". Yeah! OK! Well, how many different ways can
that go wrong? And how are we going to keep all of these different 1-bit errors
apart from one another? How can we keep the good codes well apart in a much
bigger bit pattern? And where things get pretty hilariously hairy is if you say
Hmmm! I don't want to correct just one bit
I want to correct three bits, up to four bits, up to seven bits ... And that gets you
seriously involved in stuff with names like field theory, rings, groups, cosets
and other lovely stuff like that.