Name: The Perfect Code - Computerphile
Uploaded: 2020-04-13T17:07:41.000Z
Duration: 8 min 27 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Fundamentally the question is this: you've got a message that you want to

Gerund

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

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?