We've, I think, done about five, or maybe even six, videos counting the Extra Bits
in this area of Information Theory and a little bit of Coding Theory. We got
to a reasonably good state with this but the story needs finishing off. So I'd
like to finish off the story and go back to our old example of San Francisco weather
states. I'll try and make this completely understandable in a free-standing way
but if you do get a bit lost go to the playlist and just catch up with the bits
and pieces that you're not quite sure about. What we've done here is split them
up into four good codes that are meaningful and four bad ones ....
We've been working, for ages now, with this very accurate model of San Francisco weather :-)
that it's either foggy, sunny, cloudy or rainy. And you get about twenty five
percent of each of those states, so the probability [of each of them] is a quarter.
It's a two-bit code: foggy 00, sunny 01, cloudy 10, rainy 11. Fine. Four states, four
different bit-patterns. Two bits needed. What we, I think, then did, right at the very
end, was this: what happens if you get a disturbance - electrical disturbance - on
the line which either turns a 0 into a 1 or a 1 into a 0 ?
Now, this is a good stage at which to say something which I've never actually
emphasised before. We're assuming what Claude Shannon calls a "symmetric channel"
In other words there is as .... if a bit gets clobbered it could be a zero turning
into a one, or it could be a one turning into a zero. But if that happens it's equally
probably either way. In other words there's nothing about a 1-bit that makes it different
from a zero bit - in terms of its noise immunity. So it's a binary symmetric
channel. We said, all right let us add a third bit to these two-bit codes
And let us keep what's called the overall parity even. In other words there must have been an even
number of ones. So here we go, look, what could you add to
two 0s as a third bit on the right and still keep it even parity? Well, it's even
parity already so you can add a 0 If you send three bits then so long as they
arrive looking like one of these patterns, that's fine. But then you get things like: "Oh well
suppose at Sacramento they get 010 - that's not one of these four!"
So what does 010 tell you? Well, it tells you that something went wrong because it's
not in the allowed set! But the problem is there's no end of ways that 010 could
have arisen. So you can detect, but you can't correct.
Then we got on to talking about how would Sacramento say, back to San
Francisco: "I got it! I love it!". Or "not acknowledged - I don't like it, it's a bad code"
So we invented ACK and NAK back from Sacramento to San Francisco. Then you
go through the same argument. And finally we said: "What do we have to do to
make a 1-bit error be correctable? " And this ACK and NAK got us started famously.
And we're going to carry this story on today. We drew a cube and we decorated around its
vertices - its corners - with all the possible 3-bit combinations. But I
carefully arranged so that the 000 which I'm now using for ACK and 111 is NAK,
I put them at the diametrically opposite corners of the cube. And what is magic
about doing that is that, if there is a one-error corruption of the code, you can
correct it because it is so close - it's nearest-neighbour matching of the bad
code against what it must have been. So what we discovered then is that in three
bits you can have two so-called 'codewords' -
bit-patterns which are correctable, as well as detectable. But you can only have
two. Nothing else will fit. The remaining corners of the cube are needed to put
things right when it goes wrong. This is OK actually, we've got a nice situation now.
You send a message and you wait for the ACK or NAK to
come back. So you went out with 3-bit codes for four weather states and Sacramento
comes back and either says 'acknowledge' or 'not acknowledge' but because of this
protection the ACK and the NAK are going to get through 99.99999% of the time.
Well there's nothing wrong with that y'know, as a communications protocol, because
this is exactly what happens on local area networks [i.e. re-transmit the packet if we get a NAK] Here we are then: how do we
say we've got four weather states but what we'd like to do is not do the ACK/NAK
protocol. We'd like to send them out with sufficient extra bits that the far
end, Sacramento, could put it right.
Let's assumes that San Francisco and Sacramento were miles apart, y' know. You want to
transmit it once and have done with it. You don't want repeats. Well,
3 bits clearly isn't going to be enough. 3 bits can accommodate two so-called 3-bit
codewords that are distinguishable from one another, but no more.
And your first thought may well be: "Well let's try four bits". Now the number of
bits you use in your code-strings equates, if you like, to the dimensionality of the
cube and we've gone beyond the cube now to hypercube. This is a topologically
correct projection of a four-dimensional hypercube onto two-dimensional flat
paper. There's lots of ways to depict it. I've always liked this one. I think I saw it
in Martin Gardner's, Scientific American, "Recreational Maths." column, many many years ago.
You draw a cube and then inside it you draw another cube - almost, sort of,
suspended in mid-air inside the original cube. You then connect all of the
corresponding corners on the outer cube to the inner cube.
I've put those in in this diagram as dots [dotted lines], but the dots don't mean anything.
They're just something that makes it easier for me to see the structure. So
don't worry about the dots! Every line in here is a projection of an edge in
the hypercube. It's got exactly the right topology but it's been distorted so that
you can understand it. So here's your challenge, audience. If you think visually
like this - oh! by the way, we're going to stop at
four dimensions [in terms of drawing hypercubes]. I have no intention of going to five dimensions when we
get up to 5-bit codes. Four dimensions is enough but just look at this.
The challenge is to say we've got four 0s [and] four 1s, maybe, as our two
codewords still on the outer cube 4-bit coding. On the inner cube can
you choose any pair of corners which are not only three apart from each other, on
the inner cube, but are also three jumps away from the existing codewords on the outer
cube. Well, if I choose that corner it's hopeless. It's only one away from [an]
existing codeword. Even if I choose this one, up here, is that any good?
No, it's 1 2 away from here. Choose this one, down here, y'know, is that one any
good, down at the lower right? No, it's 1 2 away. No matter which of the
eight corners you choose, on the inner cube, and try to get them diametrically
opposite, so maybe you can pack in two more. You just can't do it - you can't even pack in
one more because it's always no better than two jumps away from existing codewords.
In other words four-dimensional space has let us down. Big Time! But now
we go over to a much more - if you like - algebraic bit-pattern, computer science,
way and we say we will conjecture - mathematicians would say this all the time -
even as a computer scientist I conjecture that five bits might be
enough to encode four weather states for San Francisco,
with some sort of protection in it, so that the far end can correct and not need to
ask for a re-transmit. And this, basically, is the classic Hamming code.
We're going to go against tradition a little bit.
You're very used to me putting up a bit pattern, numbering it from the right and
saying that's a zero bit - that measures the ones, the twos. and go right-to-left.
For constructing Hamming codes you go left to right and you start numbering at 1 not at 0.
OK, what's special about 1? Well, in
terms of powers of 2, it's two to the power 0. I'm sure you will all remember [that] anything to
the power 0 is 1. Two is no exception. Two to the power 0 is 1. Two, of course, can be written as 2
to the power 1. Let's just put lines under these. Another exact power of 2 here,
four, is two squared. So what Hamming said was this: "Think of your position which
are exact powers of 2, as being where you put the parity-check bits. And then you
use the other bits in your pattern to hold all the information bits. And then I
will give you a methodology for working out what the parity-check bits would be".
So instead of having one parity-check bit now, like we did in the 3-bit
codes, we're now going to end up adding no fewer than three parity check bits. I will
stick to even parity. Nothing special about that - you can do it odd [parity] if you
want to. But you must be consistent, of course. OK - those are our column headings. What was
the state of weather in San Francisco, on the left, the first code was 00, if you
remember, and I put the information bits of the codes in the three and five
positions where they are not powers of two. You've got to remember that bit 1
acts as a checkpoint for positions 1, 3 and 5. Bit 2 is a check for bit 2 and bit 3.
Bit 4, up here, is the third parity-check bet, that checks 4 and 5.
What you are doing is, basically, breaking down these odd numbers into sums of
powers of two. Let's just see if this .... I'm taking up too much space for green! Let's
see if the blue works here - what I'm pointing out to you is that
3 can be thought of as 1 + 2. 5, in terms of sums of powers of two
can be thought of as 1 + 4. So this is how it works. You write in your
information bits and then you say: "What about my parity bits?" And you use these
rules, here, which effectively says that bits 1, 3 and 5, taken together, must be
even parity. Well look! Bits 3 and 5 - the information bits, are 0 and 0. So if
1 + 3 + 5, in parity terms ... of course a lot of you will realize we're doing
exclusive ORs here of 1s and 0s ... 0 + 0 it's even already, so to keep the 3-bit grouping,
including 1, even, it needs to be 0. Bit 2 checks 2 and 3 but 3 is already 0. So two plus
three's parity bits must add up to be even. Zero already so we get another 0. Finally
what about bit four? Unknown at the moment it's got to be a parity-check. Ah! well, 4 and 5
taken together, must form an even parity pair. Oh! that's dead easy.
What it has predicted is [that] it's a simple binary repetition code for one of the states.
OK - but everything is guided by your
information bits. We're now going to move on to 01 - same rule look, Bit 1
checks 1, 3 and 5. OK? 3 and 5 are in there already.
they are data bits. Aha! but there's a 1 and a 0 now. To make the whole thing even parity, then,
what have I got to do to the 1 bit? Make it a 1, because 1 + 1 give you even
parity. And then check out bit 2. Bit 2
combined with bit 3 must give an even parity combination. Well, bit 3 is in
there as a 0. So [bit] two combined with [bit] three - you've got to have a zero. And then,
finally, bit 4. Well, 4 and 5, taken together, must form an even-parity
combination. So, therefore, if [bit] 5 is 1 - I'm sorry folks - [bit] 4 has got to be 1.
The next information code I put in there, which my notes say is the cloudy code, 1 and 0.
Here we go again. 1, 3 and 5, taken together, must form an even parity
combination. But you got a 1 there and a 0 there. So you need a 1 here to
balance it off - even number of ones, right? And then bit 2: well [bit] 2 and [bit] 3,
taken together? Well [bit] 3 is 1 - we're stuck with that - it's part of the data. So we put a
1 in here to make it even and then [bit] 4 and [bit] 5, taken together, that's a 0.
And finally "rainy". Here we go again. So our final bit pattern that we've got
to locate in here is 11 for rainy. OK [bits] 1, 3 and 5, taken together must be even.
Well 1 + 1 - [bits] 3 and 5 -,that's even, so keep it even by putting a 0 in there. Bits 2 and 3 taken
together? Well [bit] 3 is a 1, so 2 and 3 taken together and to be even
parity must have be a 1 there. 4 and 5 - that's a 1 - so you need another 1 in here
to make 4 + 5. So there we are folks! Those are our so-called codewords for all
of the states of weather. Look at them. If you look at "foggy" and "sunny", in how many places
do the bit patterns differ? 0 and 1, that's a difference; 0 and 1
that matches, that matches, that's different, that's different.
Three differences. They are distance three apart and remember distance three is
magic! We saw that on the cube. If you keep your code words three bits apart
from one another then everything follows absolutely beautifully.
And that works fine but we are now in a situation where we can send all this
stuff off to Sacramento and they can blooming well sort it out for themselves!
So long as you don't get more than one error in that then, fine, you can correct it
by using these Hamming codes. And you say: "Well, how do you correct it?"
Well, the answer that is you do various simple Exclusive-OR operations on these
parity check bits, at the power of two positions, you know, like the 1, 2 and 4
positions. You use various combinations of those very much along the lines of how we
encoded it in the first place, and depending on the outcome of those, you'll
find some of them check out all right "Yes, it is even". Some of them are bad and
wrong and it's odd [parity]. And by combining the start positions for the odd ones that
are bad, you can uniquely home in on the bit that's gone wrong. And if you want to
know more about that - just write in and ask Sean. And we'll see what we can do.