字幕表 動画を再生する 英語字幕をプリント 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  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?