Placeholder Image

字幕表 動画を再生する

  • 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?

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

字幕と単語

動画の操作 ここで「動画」の調整と「字幕」の表示を設定することができます

A2 初級

パーフェクトコード - コンピュータマニア (The Perfect Code - Computerphile)

  • 0 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語