Fundamentally the question is this: you've got a message that you want to
send and it's either "yes" or "no". Or sometimes in signalling they call that
"acknowledge" and "not acknowledge" -- ACK and NAK; yes and no. It's all very well but they might get
damaged - they might get corrupted. Coding theorists, in the very simplest case, did
realize that in order to be able to correct an error - just a 1-bit error - you needed to
repeat it three times. On Computerphile, here, we have talked about this stuff in
more detail but I want to try and keep this as accessible as possible for
people who are just coming at this for the first time. And to try and explain what it is
about these 3-bit codes that makes life so much easier. And the answer, my
friends, lies in putting them at diametrically opposite corners of a cube.
What you're saying is, if you send three 0s that's fine; if you send three 1s, that
don't get corrupted, that's fine. Just look at how far away they are from each
other. it doesn't matter how you get from there
to there, or backwards, you have to go one, two, three.
So, that's technically called the "distance" between these two codewords.
So, there's two buzz phrases straight away: "codewords" and "distance" between them. If
you, on either side of these accurate codewords, you write in what you might get
if one of the bits gets corrupted and flipped. You now have a situation where
if you receive 010 the answer is sometimes called "majority logic". The
overwhelming decision of this point is that it's got two 0s and one 1.
So, therefore, if you're going to correct it, it's far better to correct it to three 0s
going down one edge than to try and go all the way around the cube and correct it
to that [i.e. three 1s]. We're using a total of three bits, right?
111 - three bits. But the actual message we're trying to get across is
yes or no, ACK or NAK. Zero or one. So of those three bits the
only bit that counts, as far as the message is concerned, is just one of those bits.
However, in the course of keeping the codewords far apart, we have agreed they
are distance three from one another, in terms of a walk you do around the cube
along the edges. So here we are: total number of bits; number of those
bits that are devoted to the real message - only one. How many journeys
around sides of the cube would you have to take to get from one codeword to another.
So, it's a [3,1,3] code. [3,1,3] is the simplest "full" Hamming code and it is
"perfect". What do I mean by saying it is "perfect"? Every single corner
- all 8 of them - serves a purpose. A corner is either a codeword - the actual thing
you're trying to get through and hope it doesn't get damaged - or if it's not a codeword
it's a correction vector. It's a corner
of the cube that's adjacent which gives you the clue that if you get *that* [points at "100"]
received you go to the nearest code word [000] along a cube edge. So every single
corner is concerned with either the proper message or how to correct it.
Nothing goes to waste. [3,1,3], hmmm! where do you think the next one of
the perfect ones would occur - that occupy all the corners? Not on a cube this time - it woud have to be on a hypercube.
>> Sean: So, a hypercube's going to have what ... ? Another four? Another eight corners ?
>> DFB: Well it could be 4. It could be a 4-dimensional hypercube ... a 5-dimensional ... six, whatever.
>> Sean: I feel like it's going to be a round number
Let's go for 6. [6, 1 something] ? >> DFB: Close! [But] it's not. I will reveal the answer
and then we'll will try and justify it later on. That's the simplest "proper" Hamming code.
Next full Hamming code is not at 6; it's at 7. And in this notation .... >> Sean: Is this prime-number related then ?
>> DFB: No it's not actually prime-number related but you'll see a pattern emerging.
This right-hand thing of three [e.g. in 7,4,3 ] is always there. Even if you're on a
hyper-cube you keep your codewords three edges apart and what happens with more
bits in use is you can afford more bits to hold the message.
Whereas, before, you had a 1-bit message - two possibilities - here we've got a 4-bit
message which equates to 16 possibilities 16 possible code words two to the power of 4.
All wrapped up in a 7-bit message. Now your final clue: the next one
after this is [15, 11, 3]. There is a pattern emerging here, folks, particularly on that
leading digit. 3, 7, 15 - always one less than a power of two.
That's a necessary condition, together with distance 3 between codewords,
for these to be "proper" full Hamming codes And what I'm saying to you is: [7,4,3] is
also perfect. Let's try and reason why it's perfect by waving our hands around a lot!
OK - it goes like this. You've got 4 codewords They're on a 7-dimensional
hypercube. If it's a 7-dimensional hypercube out of every codeword corner
there are - try and imagine it - seven edges going out to correction points for it,
plus the corner itself. So 7 + 1 is 8. Right? You've got eight
possible things that are either the thing itself ot its correction points.
Every codeword counts 8 in terms of corners of the hypercube but how many of these code
words can you have? 2 to the power of 4 is 16. And every one takes up 8 corners 16 x 8?
>> DFB: 128 do we agree? >> Sean: Er, 128, yeah - eventually! [laughs]
So you need 128 corners just by reasoning from a cube, right up to a
7-dimensional hypercube you can say you would occupy 128 corners.
But consider: 7-bit codes - which is what we're talking about in
this hyperspace - what's 2 to the power 7? >> Sean: 128 >> DFB: Bingo! So, you've got 128 corners and they are exactly
used up. That is what a perfect code is all about. It's about using up the
corners on your hypercube to the absolute maximum. It's so eco-friendly!
y'know, absolutely nothing goes to waste!
The big problem with these Hamming codes is that they only correct one error. That
is the stopper in the end. That they're just not suitable for the kinds of
situations that occurin real life or, at least, out in noisy Wi-Fi setups, or out
in interplanetary space. Very comparable really in terms of background noise
bursts of horrible, y'know, [electrical] activity going on that ruin your code. You need
something rather more robust than a code that can detect only one error. But
nevertheless as a thing to learn about first and the ability to entirely cover
certain hypercubes with the codes, and the way to correction them, they're very nice.
I'm very fond of perfect codes! >> Sean: Does this mean that other codes in between these are unusable?
>> DFB: No! For those in the know we've done one already. We used Richard
Hamming's methodology to develop it, but we didn't admit to its shortcomings, right?