The Perfect Code - Computerphile

Summing up why Hamming's error correcting codes are regarded as 'Perfect' - Professor Brailsford explains.
EXTRA BITS: • EXTRA BITS: More on Pe...
For more background on this: • Multiple Dimension Err...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@TrekkerUK]

0:38 "I want to try and keep this as accessible as possible..." 5:20 "... a seven-dimensional hyper-cube" I could listen to this man for hours, but did I miss something in the middle there?

[@rana4410]

I would say you missed about 4:42 of the video

[@SellamAbraham]

@@rana4410 I would say you missed @8:27.

[@nachoijp]

Well, he said he wanted to try, not that he'd succeed

[@Xvladin]

I don't think saying "hypercube" is that inaccessible. It's just a cube but in higher than 3 dimensions.

[@jhonbus]

😂😂 To everyone disagreeing: you're arguing with a joke.

[@xPROxSNIPExMW2xPOWER]

man this dude should make computer science documentaries, his voice is engaging

[@Joshua-ym7ei]

I was just about to comment how i don't know what it is entirely, but i like this guy haha

[@tuneboyz5634]

shut up

[@donquixoteupinhere]

Yeah man he should start teaching or something ¯\_(ツ)_/¯

[@FilSapia]

He is basically the David Attenborough of Computer Science :)

[@DanielFoland]

Meanwhile, inside the computer... "Sir, we got the message." "Is it Yes or No?" "Well, it's kind of neither. Something's wrong." "Okay, well, map it into hyperdimensional space then get back to me."

[@paulmag91]

On point!

count the zeroes and the ones and tell me which is more, that will win

[@firstnamesurname6550]

ROFL

[@Friek555]

If it's a hypercube then the message is more than one bit, so not just Yes or No

[@pilotavery]

"Sir... I think it's a quantum bit"

[@vijethpoojary9815]

prof.Brailsford is david attenborough of computer science even sound like him

[@MatthewHarrold]

Ha! I was just thinking the same.

[@benjaminbrady2385]

VIJeTH Poojary true

[@TomatoBreadOrgasm]

Even sort of looks like him, but then they are both elderly Brits.

[@SteveParkin]

Yes, this professor is one of my favourites on this channel. Let's try and reason why it's perfect by waving our hands around ... a lot.

[@simoncarlile5190]

Here we see the hypercube in its native habitat as it scavenges for food

[@y__h]

Long live and prosper, Professor.

[@kellykitkat40]

Live prosper and long?

[@clayton8or]

Prosper long and live?

[@stokesy887]

Dave Null and long live prosper

[@AfonsodelCB]

long prosper live and.

[@paulmag91]

prosper and long live

[@kittenkillzu]

Could you start over? I missed the part where everything was explained

[@KnakuanaRka]

KittenKillzU Long story short, this is supposed to be part of a series, not seen by itself. They should have mentioned it somewhere.

[@Kotesu]

I'd love to see you explain Reed-Solomon error correction. They're used everywhere and are very interesting from the maths side of it. The BBC have an amazing paper on the topic and have a neat example with a toy RS(15,11) code setup - but it still took me an insanely long time to wrap my head around the decoding side of it.

[@daniellewilson8527]

What’s the name of the paper?

[@Person-vj4fq]

For what I am understanding from this is: use 3 bits to represent 1 bit, so its ultimate data remains the same as its initial data when copied or moved. Imagine sending the value of 0 as 000, then one of its bits gets corrupted so that it displays 010. When the receiver gets 010, it is supposed to assume that it was 000, since it has more 0's than 1's. After that, the receiver would translate 000 to 0.

[@Booskop.]

And, 313 is the licence plate number of Donald Duck.

[@Keyakina]

Now THATS something I understand!

[@ZLau13]

INSANE NL Nice. Used to read tons of Donald Duck comics as a kid.

[@Zupernova91]

That was my first though as well :)

[@mickelodiansurname9578]

INSANE NL Donald duck is so two dimensional...

[@neshmicc]

Also the area code for Detroit.

[@i-heart-google7132]

07:01 the definition of 'perfect code': "That is what a perfect code is all about; it's about using up the corners on your hypercube to the absolute maximum." ... I wish I knew this when I started programming :D

[@eidiazcas]

This deserves way more likes

[@HansPeter-qg2vc]

Should've started like this: "First, imagine a 7-dimensional cube ..."

[@mrbrianparker]

Best explanation of hamming code correction I've ever seen. I already knew how it worked but now I really understand it - Brilliant stuff!

[@frostyusername5011]

I love Professor Brailsford, he always captures my love for computer science with his soft spoken explanations and anecdotes. source: developer

[@codediporpal]

Trying to imagine 7 dimensional space is kind of a non-starter.

[@lincolnpepper816]

you don't need to imagine 7 dimensional space to understand this video

[@akinoreh]

​@@lincolnpepper816 _continued_ : ... if you didn't plan understanding the video in the first place.

[@MarshmallowMadnesss]

It's heavy, but an adequate understanding of binary and a vague grasp of programmatic looping helps a little. A second watch also helps. Either way, I am in awe of this guy's knowledge.

[@crazydog3307]

its not that hard

[@markuspfeifer8473]

Just imagine an n-dimensional space and then set n=7

[@newbie4789]

I was really having a hard time doing my Coding Theory assignment as I was having hard time connecting Hamming codes with Hypercubes. This helps

[@peterfiser]

6:25 gotta love this good old chap, Prof Brailsford got me hooked on Computerphile back in the days.

[@bennylofgren3208]

+Computerphile, please please please list the earlier videos this series, at least in the description. When reading through the comments it's obvious that this video by itself makes little sense to many viewers, and the title doesn't really reveal that it is a part of a series either.

[@bennylofgren3208]

ProfDaveB Thanks! Love the content as always. :-)

[@bobbyborsalino5037]

0:27 those 2 buttons are stronger than all relationships I've been in.

[@PETAJOULE543]

Hamming codes notation meaning explained well, and that there exist many Hamming codes, and that Hamming codes can only correct single error. Plus their nice usage 'density'. I also recommend to look at hamming bound formula V(n,t) and also size of t-error-correcting code to understand whole explanation of numbers 8, 16, and 128.

[@dmaster20ify]

I have no idea what this great man is talking about. Thought the video was writing the perfect computer code.

[@tobiasgertz7800]

Error correction codes in electronic communication

[@niccatipay]

The 'Perfect Code' is only perfect in a perfect scenario and in this world there is none. ~ Edge Hog

[@IronicHavoc]

It's just a name

[@jamestaylor1934]

Every time I hear professor Brailsford speak he blows my mind. 10/10

[@WAYAWAYWithAsh]

I love that as I watch this I THINK I understand, but in no way can I apply this personally. Haha.

[@MrGoatflakes]

Why not? You might need to some time transmit some data reliably in one of your projects. Or make a way to store your files that is tolerant of errors.

[@HansPeter-qg2vc]

He's saying that he would not be able to implement it or be able to pass an exam testing his knowledge about it.

[@lazarstojanovic1915]

You don't need this in every day coding , but it might prove useful in the future

[@GFlCh]

+MrGoatflakes - "Why not? You might need to some time transmit some data reliably ...". Realistically, if I needed to send it reliably, I'd use an error correction (EC) scheme that would protect against multiple bit errors. The "EC" in this video (Hamming Code) is for trivial cases at best. Perhaps a case where the EC is performed entirely with hardware (gates/flip-flops...) or where the scheme is used for only for error detection, along with re-transmission.

[@arom4chology]

after rewind the video a couple of times, I am proud to say I have understood this perfect code hehe

[@gabetower]

I love this series on error correction

[@abhishekshah11]

I could listen to this man talk about computer theory for hours.

[@kyoai]

This guy is so enjoyable to listen to. :D

[@Derbauer]

that cube animation reminded me of the code deciphering scene from the movie 'Contact'.

[@bennybob444]

My man needs a bigger shirt

[@TheRovardotter]

That shirt button is getting a workout

[@kaoti]

@The Absolute Madman and you need a bigger brain.

[@NeilRoy]

I love listening to him. Such a nice person.

[@CharlesVanNoland]

Reminds me of neural networks coalescing a pattern of neural inputs into one response, or output. i.e. in the case of a 7-bit 'perfect code' it would be outputting a 4-bit response... This also reminds me of sparse distributed vectors and Hierarchical Temporal Memory.

[@pid8307]

Finally a new video! I had signs of withdrawal.

[@j7ndominica051]

This video was easier to follow than most others in this section, despite the hypercube. Does a ball with cut edges to produce those corners fit as an illustration?

[@4grammaton]

I swear something extremely similar was discussed in the computerphile video about sending compressed messages and digital compression in general.

[@mrv1264]

Another challenge is determining which bit is in error. The point is moot for one bit of data transmitted. For data comprising more than one bit, you need to determine which bit or bits flipped during transmission. Identification of the position of the erroneous bits requires more complex or more sophisticated codes.

[@nO_d3N1AL]

Better explanation than previous video

[@frostyusername5011]

How about a collaboration with your Numberphile channel and do a video about the Fast Inverse Square Root function? That would be amazing!

[@giuseppeugo2716]

thatusername a video on the Power of two?

[@frostyusername5011]

The thing how a binary floating point number, when treated as an integer and the bits shifted once and subtracted from a constant, following a round or two of Newton's method, gives a rough approximation for the inverse square root. IE: 0x5f3759df

[@nittssu]

Man I love computerphile

[@hassiaschbi]

so, you are computerphilephile?

[@3117master]

I like people who like computerphile. that would make me a computerphilephilephile

[@lazarstojanovic1915]

I like people who like people who like computerphile , that makes me a computerphilephilephilephile

[@adamfirth3082]

moment of silence

[@willhendrix86]

So if I understand this correctly it is essentially: The alternative is the transmit both the original and OR version for verification, AND them both, if results to zeroed bytes, pass, if failed, re-transmit... So a 8bit message requires 16bits transmitted and twice that again if it fails, NACK if you prefer. With this method, the datagram is essentially computationally self correcting resulting in no re-transmission?

[@Qbe_Root]

Alright, so the perfect codes are Donald Duck’s car (2:47) and a Touhou boss battle (5:48). Did I get it right?

[@NoNameAtAll2]

Touhou fans unite

[@joshrakes4354]

I just realized that "Computerphile" is an oronym for "Computer File"

[@tj8870]

"Suffixes with the common part -phil are used to specify some kind of attraction or affinity to something".

[@novelnouvel]

@@juanmanuelespanabolacuenta4048 You win. Now get out. 😂

[@skylarkenneth3784]

@@juanmanuelespanabolacuenta4048 Peta File

[@claudesedillo2828]

Not even close

[@samarthpandya1194]

I want this man to explain to me everything in life

[@andytroo]

I like the concept of fountain codes; generate a practically infinite set of error correcting chunks, until the reciever is able to respond "i got it" -- with very high probability, if you have a message N chunks long, then any N+1 chunks out of the original data and the "error recovery" data can be used to recover the original message. The cool thing is there is no limit to the amount of extra error correcting chunks able to be generated ; unlike a hamming code where there is only 1 way to transmit the message. That way you can perfectly tune your transmition for the error rate of the channel;

[@filipve73]

The shortest distance between two points A and B is a straight line. (euclid-space, 2D) The minimum Hamming distance of a code is the smallest distance between two (different) words in the code. (hyper-space, 4D)

[@ramnrmeul]

5:11 Based on the pattern, I'd say that the n-th "proper" Hamming code is 2^(n+1)-1 bits in length.

[@xDMrGarrison]

Very interesting! I love learning about new concepts like this? :D

[@Deepak-vl8pf]

"It's so Eco-friendly." Indeed, sir.

[@Marcara081]

Reminds me of the networking from the map colors video.

[@turen1234]

its funny cos the more error correction bits you put in the higher your probability that one of those bits can become corrupted, i think you really needs a checksum logic which resends the packet

[@ManuTheGreat79]

Hi guys, You guys should talk about the CD, it's got a lot of cool features, one of them being Hamming correction. ... And it's got it all. Why 44k Samples/s ? -> twice the bandwidth of sound (20 - 20kHz)... So 28 bits per sample, it's stereo, so 14 bits each. 10 for the value, 4 for error correction (If I remember well) Lots of cool aspects :)

[@mrv1264]

You should explain that the procedure of going to the nearest corner reflects the notion that is there is a greater probability that one bit flipped in transmission than two or three bits.

[@vasiapatov4544]

love this guy

[@VeteaTOOMARU]

perfect explaination !

[@kingburrito7773]

this man is brilliant

[@lazergurka-smerlin6561]

When will the ytp come?

[@MichaelKire]

What if we use these Hamming's error correcting codes together with the same technique as balanced cables use, where the same signal get sent twice (on two different cables), but one of them is reversed. Then you would reverse the bits on one of them back and then compare them bit by bit. If there's any changes, you know that you have errors.

[@swaveydavey1113]

hey would it be possible to ask u a question about computers Computerphile

[@David_Last_Name]

Is this guy also the narrator for every BBC wildlife documentary I've ever seen?

[@randallanderson4999]

No, that would be Sir David Attenborough, who is the narrator for the BBC wildlife documentaries.

[@VL4DST3R]

3:40 "313... >_> hmm..." cracked me up.

[@jugganot101]

I love this guy

[@DaveWhoa]

but at the very end he explains how they're NOT perfect ... so what are the better error correction algorithms?

[@DerekFolan]

With 3D printing can the computer builders make more efficient shapes generated via 3D drawing tool using fractal filters or other type of shape generators.

[@frankharr9466]

You know, I could make an argument for a playlist including all these Hammond Code related videos.

[@bjornolson6527]

Frank Harr Hamming

[@tedkraan9348]

Hamming code is also used in RAID2. A RAID level that is rarely used.

[@kormsd]

This is magic

[@isakenstrom3375]

These codes only detect and correct one error per transmitted message but couldn't you somehow get an estimate on the errors in some process and stack these codes somehow so they all correct some part of the erroneous whole?

[@icarusswitkes986]

I think I don’t fully understand this but at the end where he said they could only detect one error, what if there were a bunch of hyper cubes all connected? And each one detected one error.

[@liammorrison4284]

you can tell by the size and shape of this man's skull, that is brain is absolutely massive!

[@kalebdodge3488]

That thumbnail has a high power level

[@kevnar]

The most amazing thing is I actually understood all that.

[@uncletom1971]

The art of computer programming.

[@bryanfuller4465]

11 days after Buckminster Fuller passed away and 112 Years After he was born on 7-12-1895

[@BluntInnit]

so when you are correcting a 4 bit message do you still have to send the entire message 3 times? if so and you can only correct 1 bit then why send in chunks of more than 1 bit? as you may as well just send each bit 3 times and use the 2/3 majority. as then as long as long as no more than 1 out of 3 bits for a single bit sent are corrupt every bit could be corrected perfectly, but if it takes 12 bits to send a correctable 4 bit message then there is a much greater chance that more than 1 of the 12 bit sequence could be corrupted. or did i completely miss something?

[@dannygjk]

It's more time efficient to send the bits in a group in one packet.

[@alfiechenery4146]

Why is it that these only occur with higher dimensional cubes. Could other Platonic solids like a tetrahedron work, or for that matter any polyhedra?

[@thesimulacre]

I love this fellow

[@tigergoldfish17]

What exactly is the middle bit? He said something like the number of those bits that evoke into the real message. In [7,4,3], what does the 4 mean?

[@rustygear447]

if i understand it correctly [3,1,3] you're sending a total of 3 bits of data to convey 1 bit of message. [7,4,3] you're sending 7 bits in total to convey 4 bits of message.

[@tigergoldfish17]

How would 7 bits convey 4 bits of message?

[@bennylofgren3208]

tigergoldfish17 That's the whole point of Hamming codes. With seven bits, you can protect four data bits from one-bit corruption and detect two-bit corruption. With 15 bits, you can protect 11 bits of payload, with 31 one bits you'll get 26 data bits safely across (within the constraints I mentioned). There are several earlier videos on this topic that are more or less required viewing if you are to understand this concept without prior experience, but they were unfortunately not mentioned in the video or description.

[@rustygear447]

tigergoldfish17 In [3,1,3]: to send a [1] you send a packet of 3 identical bits [111]. this way, if one of the bits is corrupted it would become one of the following [011], [101], [110] and you can assume that the majority bits are the real message. That also means this method only works when the corruption is no more than 1 bit. In [7,4,3]: to send the 4 bits data, you first need to look up the 7 bits *codeword* from the hypercube map like shown in the video. this codeword guarantee that it is 3 distance away from all other codeword. this is the same as with the [3,1,3] except in [3,1,3] it's much easier to visualize since it's only 3d cube. The rest is the same, you send the 7 bits codeword, and the receiver will take the code and match it to the closest node in the hypercube to find the 4 bits of data you want to convey. again, it only works if the data doesn't corrupt more than one bit. This also means the higher bits it goes, the more unreliable this method becomes as the more bits you send, the more likely it'll get corrupted more than 1 bit.

[@WrenAkula]

+tigergoldfish17 Because you have 16 seven bit code words, each of which maps to a unique 4 bit message.

[@coreyburton8]

I am coming at this for the first time.. thanks!

[@mediavormgever]

That is some great notation paper. Wondering where they still sell this.

[@randallanderson4999]

Check e-bay for "line printer paper", or "Continuous Feed Paper".

[@sabirkothiya9977]

Can someone please tell me what type of paper was the professor writing on, cause i'm trying to look for it but I can't find it?

[@randallanderson4999]

Fan fold, line printer paper. Came 5000 sheets to a box.

[@jlxip]

Now the question is: in which scenario should this be implemented?

[@sinansivri939]

Hey guys do you have something to say about mean shift clustering and its initialization , i'd like to hear about it.

[@tothm129]

Ok, i get why it cant be even, because if you have 2n bits then if n are 0 and n are 1, then you would not know if it were 0 or 1, but if its odd, there could either be more 0's or more 1's making the one with more apear to be most likely that one. what am I missing?

[@PrivateSi]

Pretty much on par with a parity check but with error correction (that requires more transistors to implement..)

[@bhuvaneshs.k638]

I hv one question. So it's redundancy ryt 0-> 000 n 1->111 so it's 1 bit data

[@crazydog3307]

its pretty interesting, but i have to wonder why this is used instead of just receiving and interpreting all data, mutated data would obviously fail the check, and produce an error message indicating that the message was either not received or misreceived, at which point the receiver would wait before sending an acknowledgement, and the sender, not receiving an acknowledgement, would resend the information

[@chellendjmeshay]

I need to learn this stuff

[@LimitedWard]

What if you then transmitted 3 3-bit hamming codes? Then you'd be correcting for each individual bit and reducing the chances of larger errors.

[@scvnthorpe__]

I don't think I get this yet, but trying to imagine a 7D cube is a trip

[@quintoncraig9299]

And still more proof that perfection is either non-achievable or the worst flaw to have. (some effort goes in, some comes out, a necessary exchange, true perfection is a group of flawed units whom make up for each others flaws and work together.) example being; A Party of Adventurers, Thief/Rogue; for lock-picking and trap disabling Healer; Keep everyone alive Tank; Divert damage Dps; Harm the enemy Wizard; Magic Utility, Battle Control and some damage Bard; Deal with people and maybe some magic or swordplay Diviner; Find the things: can replace with Wizard, Healer/Cleric, Bard and Rogue.

[@woodywoodlstein9519]

I sure pray that brailsford lives to 115 or so.

[@bryanfuller4465]

Do you think tasing myself in my third eye my pie Neil would actually activate the DNA faster curious question would the electricity activate in the fullerene particles to expand quicker

[@TheNeoxpert]

What does the notation [3,1,3] mean?

[@AnthonyGoodley]

How does this compare to memory's parity bits? Is this better or more efficient in some way?

[@randallanderson4999]

Most memory parity can only 'Detect' one bit errors.

[@bananian]

3-1-3 is the formation i use on EA football. Works every time.

[@calvindibartolo2686]

this is pretty cool, but thanks to this video I also now understand Hypercubes (an idea I've struggled with before)

[@WillToWinvlog]

This is cool!

[@Rising_Pho3nix_23]

and this can be used in code transmission how? lets say i create a chat client on an unstable network. how does this help?

[@OMGitsjustperfect]

I understand that you want to have messages in the protocol. What I don't understand is the correction. Why do you need correction? ty

[@kenichimori8533]

Perfect code is a+b=c conjecture is triangle bytes.Structure Triangle Hypothesis is download scheduling.

[@jamessowin2505]

What's the next video. These codes only correct one error. He mentioned you needed something more robust. What is more robust?

[@gustavderkits8433]

Error: at the end the prof said that you need something more powerful than a code that can detect only one error. But these detect two errors and correct one.