Error Correction - Computerphile

[@ArrayPro]

I could seriously sit and listen to this guy all day, he's so goddamn interesting.

[@AlexanderBollbach]

only issue i have with this channel is the videos that are part of a series of videos are not labeled. Sometimes you give them the "continued.." but that doesn't help if there are more than 2.

[@RobbieMelvin]

Flashbacks to 12 months ago. and my grad course. This is one of the foundation pieces guys! Can't have our lovely wi-fi without it.

[@JMPDev]

Definitely my favorite series on computerphile so far! Would love it if we could venture further into the 'hairy' stuff, even if we'd only scratch the surface in such a short format :)

[@aafaqin]

this channel ND numberphile i love it.. i am doing my computer engineering and sometimes when i get frustrated of my hectic life schedule and want a productive break these are the two channels i come to... i hope you guys make more and more videos .. so that it can make my course more interesting and also encourage young minds to perceive career in computer also it would help ordinary people to know how the devices they use so casually work... guys please make more videos... i love them all and it makes my course really more interesting ...

[@damiensadventure]

Professor Brailsford is video GOLD for education about this field and it's history!

[@AlexanderTrefz]

I have to say that in general the computerphile videos are not all that interesting to me (a programmer), which suprised me a lot because i liked the idea. But the videos with Professor Brailsford are always really really good and i feel they are explained well even for those that are not that deeply familiar with the things he talks about. Keep it up!

[@hellterminator]

You should make a video about creating Hamming codes for larger numbers/multiple errors. You said it was very complicated but I disagree. It is one of the simpler algorithms, it is absolutely beautiful and anyone who ever took algebra should be able to understand it.

[@steve5390]

It'd be great if we could have "Part 1" and so on in the title, I often stumble onto Part 2 from a video that interested me, without knowing it'd been there

[@elliottmcollins]

As he mentioned at the end, modern error correction methods are based on sophisticated versions of this method. This channel is more about the origins and foundations of CS than about teaching cutting edge methods.

[@yvrelna]

The arrangement of bits in that cube has a very special property that makes the detection possible, notice how every sides in the cube connects two points that differs in exactly one bit. The cube looks a little pointless here because there's only 3-bits, but with larger number of bits, when you're sending n-bits with larger correction distance, you can construct an n-dimensional hypercube to help visualize and correction simply becomes finding the nearest "good neighbors" in the hypercube.

[@AaronCZim]

This is my favorite series in computerphile so far.

[@RedEyedJedi]

This man has to be one of the best teachers in the world.

[@luketimothy]

In any case, the point of the ACK and NAK is so that the receiver can say to the transmitter "Got your message, thanks" or "Could you send that again, please?" respectively. So, on decoding that received ACK or NAK the transmitter will know what happened to the original message. The original message could also implement a similar system to what the Professor describes here for error correction, and so the receiver could attempt to correct errors before giving up and sending a NAK.

[@AlexN5142]

Just programmed a hamming encoder/decoder for my programming class! Really cool stuff, I'd like to learn how multiple bit error detection/correction works

[@TorgieMadison]

Why use the cube at all? Why over complicate this? If you got two zeroes, it's an ACK. If you got two ones, it's a NAK. The point is that, minus the perfect 000/111 case, you're tolerating at most one bit of corruption. So 110, 101, 011 = the only possible ways to corrupt one bit of three ones. Likewise, 001, 010, 100 = the only possible ways to corrupt one bit of three zeroes. Keep It Simple, Smarty.

[@lmpeters]

RAID 1 and 10 have error correction in that there's at least one identical copy of everything. RAID 4 and 5 reserve one disk's worth of space to store parity bits (which follow the same rules that Professor Brailsford has been describing), and if one disk fails, you can use those parity bits along with the contents of the surviving disks to figure out what would have been on the disk that failed.

[@ThatAnnoyingGuyFrom]

To break down a concept an demonstrate it in basic terms it's always good to go back many generations before modern error correction algorithms for example like the streaming video data in this video.

[@pcljet]

First, it actually is possible to have signals with different lengths (look up "variable-length code" for some examples). Second, a "0" signal is not the absence of power, because then a "1" signal would be indistinguishable from a "01" signal or a "10" signal. A "0" signal would be a low-voltage signal and a "1" signal would be a high-voltage signal (or some other representation of what is technically a 3 character language with "no power" being a "space" or null character).

[@Imrooniel]

Just wanted to say that prof. Brailsford has amazingly soothing voice, it's pure pleasure to listen to. I'd love to see more videos about this other lovely stuff :)

[@subach]

Interesting; 1 Qbit Quantum error correction uses two additional bits as well. The Qbit has the superposition state Y= a|0> + b|1> where the information in the Qbit is contained in the complex numbers "a" and "b". We entangle the state with two addition bits which gives us Y' = a|000> + b|111>. Then no matter which bit gets damaged we can recover the original state /w 100% certainty by applying a set procedure. The bonus is that we can actually lose 2 bits and still recover the original state

[@Jenny_Digital]

I was working on sending small packets of no more than 256 bytes of data over IR using a a NRZ scheme really meant for TV remotes. I wanted good error correction but I think a few braincells upped and left me in the effort. I had to settle for error detection only in the end. Excellent work and thumbs up!

[@Ykulvaarlck]

I'm feeling proud that I know what he was talking at the end.

[@yvrelna]

(cont.) say you want to send 32-bit data with correction distance of 4 (i.e. it can correct when up to 4 bits are flipped). Given this requirements, all you need to do is to create a hypercube that can fit 2^32 good points where each good points are at least 9 steps away from all the other good points. How to create the smallest hypercube that satisfies that property and can be easily transformed back and forth from the original 32-bit is more involved, but it's easy to visualize why that works.

[@SpySappingMyKeyboard]

This way of explaining it converts very well into the mathematics behind it.

[@nehemiah7914]

Lol, everything is understandable and fascinating when your teacher's got a british accent! I just love this channel! ^_^

[@kayvee256]

To expand on QuotePilgrim: 1) Pay your internet company for a fixed IP address 2) Use a domain registration company to register (and possibly pay for) a domain name to be mapped to your fixed IP address - takes a day or so for this information to propagate through the internet 3) Configure your home PC firewall and router to let incoming traffic through 4) Install a web server and a website onto your home PC 5) Your home PC is now a 'sever' Oversimplified but hopefully informative. ^_^

[@MikhailChernoskutov]

CDs use so-called Reed-Solomon codes. With them you are able to restore up to 25% corrupted info. The idea behind it is basically to distribute information, so that if you scratch a surface, then erased bits can still be built up from other parts of CD. Same principle is used in QR-codes.

[@CamboInteractive]

That was a very complex way of explaining how to correct the errors. Instead of representing it as a cube, you could've just said "if one bit is wrong, then change it so all three bits are the same".

[@iismitch55]

Man now I want a video on each of the things he mentioned at the end!

[@Paul-A01]

Drawing it as a cube makes me think that it's just a distance calculation from each corner. errors have a distance 1, sqrt (2) or sqrt (3). That seems like it would make large problems easier.

[@JumpingNoCrime]

It may seem weird, but I am genuinely interested in the way harder stuff. To be honest, for me personally it was fatiguing that he took like 5 min to explain that there is no way you can get from 000 to 111 with 1 error - although he is an amazingly interesting speaking teacher. You said you read the comments so I like to leave my feedback :) I'd really watch maybe 30 min videos which go in depth when it's such an excited teacher. Maybe here or on numberphile.

[@3snoW_]

I think the whole point of doing this is not having to make a call. And when you solve this problem, you can apply it to any other city and have the whole country constantly updated on how the weather is like everywhere.

[@Bryan6446]

You can also use methods like cyclic coding where the information is encoded into more bits. This allows you detect and correct wrong bits at the receiving end.

[@thecassman]

It's in the description under "Error Detection".

[@gravityhatfilms]

What you are talking about though is synonymous with geometry. Steps are essentially distance. The reason why he used a cube is because it's a nice analog that works even better when the systems get much more complicated.

[@landmanland]

I like this clear step by step explanation. A well done video!

[@DIYTAO]

Also the CD player hides some smaller errors from the user. So even if some data samples have been lost, the user usually can't detect the difference. Only if the error rate gets too high, there will be audible crackle or a short silence.

[@nehemiah7914]

The process of correcting something is one thing, but how to know an error occurred in the first place? How to know without a shadow of a doubt where things went wrong? And what is the most likely answer? All of those are answers that the cube solves. Flipping bits, babies can do it, but flipping the right bits and doing something meaningful with that, people have devoted their entire lives to that sort of problems, trust me, at some point in history that cube seemed like pure magic!

[@LittlePeng9]

I hope there will be video on fields, rings, groups and cosets, either here or on Numberphile.

[@ButzPunk]

I love this channel so much. Could you do an episode (or several) on file systems and RAID?

[@thomasbladykas2245]

Please do a video on ECC RAM vs. non-EEC RAM, and DDR RAM vs. GDDR RAM

[@MateuszZwierzycki]

Let's say : there is 25% chance for one (any) bit in 000 to get distorted. So there is 25% chance to go from 000 to 010,001,100. This doesn't bother us, as we know it was 000 before (with the "cube" error correction). So there is 1/4 * 1/4 = 1/16 chance (6,25%) chance to distort 2 bits. To get them all wrong we have 1/4 * 1/4 * 1/4 = 1/64 chance (1,5625%). That all means to interpret the AKN / NAK in a wrong way we have 7,8125% chance.

[@KutuluMike]

because that only works for the simplest case where your valid bit patterns are all 0 or all 1. For complex messages you probably have multiple messages with the same bit counts but that are still 3 edges away from each other in your graph.

[@owenb111]

2 points! 1: This is quicker 2: This is over-engineered madness and is therefore better!

[@Qladstone]

Loved the way he ended it off. Gets me excited to learn more mathematics!

[@elliottmcollins]

Only if only need to do it a small number of times. Speaking is a very slow method of transferring data; I could spend all day calling places and getting only a few hundred weather reports. But if I need to know the wind speed and visibility around a weather drone every few miliseconds to make sure I don't crash, this method will do better than a phone call.

[@phelpsio]

I'd like to spend a day with this man.

[@HiAdrian]

Very well explained, thanks! I had wondered about this before, but I'm not a good learner by reading just text. Visual explanations I grasp much quicker.

[@AllElectronicsGr]

Please more videos about this!!!!!!!

[@iabervon]

If you liked the set of integers from 0 to 255, well, Beyonce can tell you how you should have used it for error correction (and also encryption).

[@thecassman]

A parity bit is the easiest form of a checksum. A checksum is any method of changing the data to allow error detection to occur at the receiving end. In this example, he did just use a parity bit, but he wasn't incorrect in calling it a checksum.

[@SharpblueCreative]

Different idea in cd error correction Reed Solomon I believe in 1960s - love to see him demonstrate that correction code. If memory serves a 16x16 grid. Though it's years since I studied theory.

[@NathanaelNewton]

You should do a video on RAID 0,1,5,10 etc and explain how the error correction is done.

[@jmoneyjmoneyjmoney]

Anyone else love this guy's voice?

[@ArichManas]

I could be totally wrong, but I feel like he is stepping up a 3-D graph and using it as a proof of theory. Same idea as using the limit definition of a derivative to find the derivative of X^2, or just knowing the 'rule' of making the exponent the coefficient and reducing the exponent by one. Same result, one is a trick, one is the proof.

[@gh0stmast3r]

not quite, i think you would just be adding faces to the 3 dimensional object. four bits for instance would probably resemble a truncated icosahedron and so on. i would assume the shape of a 8 bit spherical polyhedron would need a single point (00000000) with six other geometric points of interest around the sphere before hitting the far point(11111111). all points of course converging in. essentially it would need eight paths and six or seven points between on each path.

[@Gewath]

My point is (was), it's just an extremely complicated way of saying 'we send the bit three times and use whatever pops up the most times'. The schematic used, while accurate, over-complicates it, especially with the (KZbin) audience in mind, as it should be described in as simple and general terms as possible. It's also portrayed to provide something like flawless accuracy, which it does not (unless it's near-flawless to begin with).

[@CoolJosh3k]

Perhaps go into explaining the difference between Back Error Correction and Forward Error Correction? I think it could be interesting to hear your explanation of this.

[@blidge8282]

There is a carrier signal agreed by both (or all) ends of the network. This signal is then manipulated to represent 1 or 0.

[@ItohKuni]

What do you mean by "isn't either like 010"? And If the ack/nak is warped then yes the message probably is warped. I thought the whole ack/nack thing was for like single characters, so each letter in the text file would have their own ack/nak test.

[@SpaceKiwiGames]

A 1 vrs. 2 bit code would be hard to tell apart. Since by default there is no data coming down the line, you could imagine the default 'no signal' message being a trail of 0's. So sending either 01 or 1, it would look like 00001000. (Is it 01, or 1 that was sent?). To solve this, all messages should be the same length and have a start bit to mark the beginning of a message. Now if you get 0000010100000 or 00000100100000, you can tell whether it was 010 or 001 that was sent. I hope that helps. :)

[@luketimothy]

The cube is simply an easy way of visualizing something he didn't specifically name, which is hamming distances. In Information Theory, there is a rule which says that in order to correct one bit in a bitstream, each code must be at least a hamming distance of 3 away from each other. Any less and you can't do it.

[@magicvortex]

I made example in other comment. You can count steps needed to reach any expected combination without graphic representation.

[@gravityhatfilms]

You don't have to physically draw the cube. That was just to illustrate a point. However many problems are simpler to solve when taking into account geometry. For example netflix's suggestion system. They compare you to other members and suggest movies that people have rated highly and those people are close to you in Euclidean space i.e. people who rated movies you've rated similarly.

[@3snoW_]

All these error correcting mechanisms are done in the assumption that getting an error is, to a certain point, highly unlikely. So, when you receive a 010 it is much more likely that the original message was 000 and the middle bit was swapped, than it is that the original message was 111 and both the corner bits were swapped. It is still not 100% reliable, but it's much more reliable and quicker than to send acks and naks back and forth.

[@frepi]

What video is he referring to in the beginning?

[@TheViolaBuddy]

What happens if the error doesn't change a bit, but instead adds or deletes a bit? (000 becomes 0010, for example)

[@Gewath]

You effectively just pick the binary digit that's most often represented in the trio, and assume that's the digit. In 001, there's two 0s, so go with 0. If there'd been five, it could be 00111, and there's more 1s, so go with 1.

[@BGBTech]

usually these things are time-based, so an inserted bit would likely result in further data looking like garbage. presumably, there would be a mechanism in place for the hardware to re-align with the communication stream, then it reports a bad value or similar?

[@_philipp__]

Could you please make a video about the Reed-Solomon algorithm?

[@fredlllll]

when the hole is at a position where there is no data, its no problem. the cd is filled from the inside out. so if the cd is only half full its likely there is no data on the outer parts. but i think the cd player could have some problems with a disc which isnt balanced anymore.

[@RodrigoGraca31]

Can anyone give me the names the he said in the end? "some theory, rings, groups"???

[@Seegalgalguntijak]

The dear Professor may be in an age where he actually could have met the great Alan Touring, greatest mathematician in the 20th century. So, Professor Brailsford, if you have actually met him, it would be really interesting to talk a little bit about what he did with his beautiful mind.

[@luisdanielmesa]

based on? why not a polyhedron with 4294967296 vertices (eulers polyhedron formula), choose a number of edges and it'll tell you the number of polygons that make up the faces of said polyhedron... - correcting just 1 bit: then 4294967294 vertices are wrong. - have 2 rings of 2147483647 vertices each plus the 2 good vertices. - and a total of 10737418233 edges (imagine a wheel) - the number of faces of such a polyhedron is: 6442450939 It all depends on how many bits you want to correct.

[@ProxxSMGxGods]

Would it not be more efficient to send maybe n bits for ACK and n+1 bits for NACK? Then you don't have to check the contents of either response just the length. So if a bit gets distorted it becomes irrelevant to the problem.

[@kellypainter7625]

Wow, where does this guy get old school computer printout fanfold paper? I haven't seen that stuff since I was writing Fortran 77 code for our CDC Cyber 170 something like 35 years ago.

[@joeproozen2936]

What's the name of the videotool the animations are made with?

[@AlderDragon]

Love the videos, Brady. Have you heard of the Oculus Rift headset? Very cool piece of hardware.

[@lejink]

yyyeeeaaaa new computerphile video!!

[@LeandroConsentinoFerreira]

Just discovered the channel! Loved it!

[@richard1701able]

what phone error are you referring to?

[@IceDave33]

I spent a while trying to understand what (cool) structure you're describing - but it's not right unfortunately... Eg: - If you had 32 bits, why would you only use 2 correct codes and with path length 3 between? - How would you assign numbers to nodes? (so that each edge represents a corruption of 1 bit) More fundamentally, a 32 bit code has a space consisting of 2^32 different numbers. Each bit would be assigned a dimension, giving a 32D hypercube. (Independent of all the hamming stuff)

[@orphyn09]

I'll admit I'm only at 3:19 at the time of writing, but what would happen if your acknowledge code got scrambled from say: "00" to "11"?

[@Ninquo]

for a distance one correction of any bit length couldn't you just convert the codes to the decimal form and check if the wrong code has a difference of 2^n (1, 2, 4, 8 etc.) compared to the correct codes? That should be only one bit difference

[@luisdanielmesa]

That's science :) read my comment again and notice the "why not" near the beginning... thank you for your reply, certainly a specific situation might require a specific solution... my proposal is not universal or a panacea when it comes to error correction schemes... it is just a simplification of the 32 bit problem on a 3 dimensional space...

[@Vulcapyro]

"3-dimensional" only means that each vertex in the graph would be adjacent to three other vertices, just as a two-dimensional "cube" is just every vertex being adjacent to two others. Adding extra bits you could imagine as duplicating the existing k-cube and adding an edge between the "same" vertices. Adding a bit to {000, 100, 110, 010, 011, 001, 101, 111} would become {0000, 0100, 0110, 0010, 0011, 0001, 0101, 0111, 1000, 1100, 1110, 1010, 1011, 1001, 1101, 1111}. See how this is the 4-cube?

[@1998goodboy]

ok....but what if 2 or 3 of the e bits are changed??

[@AntonioVerlotta]

I am not sure i understood what you intend. What do you mean is that if more than one bit are flipped? Well in this case you are not lucky since the assumption of these simple codes is that the probability of 2 or more bits flip at the same time is really low. In the case, the code fails in this context.

[@gulllars]

Maybe Reed Solomon could be a good continuation of this at a later point? Once you start getting into noisy transmission on lines of more bits.

[@HighMansx]

Is it possible for all the bits to be distorted?

[@subvind]

Would it be more beneficial to ACK that it is cloudy outside (101) rather than sending back a Boolean state (111) or (000)? Or even go back to (10) but instead do a double ACK? A: 01 -> B B: 01 -> A A: 01 -> B B: 01 -> A

[@luketimothy]

It is obvious, but it is also a very simple coding scheme that nobody really uses in practice anymore... it's used for teaching because of its simplicity. The problem with it is that for every bit of information your sending, you're actually sending 3 bits... so bandwidth becomes more limited as you are using more bits than are necessary to transmit the information. The difficult thing to do is to find/design a code that approaches the 1 bit per bit of information limit as closely as possible.

[@isgdre]

Yea, I did watch the entire thing. Caught that, and the 'simple' remark. The thing was more.... Is this useful any more? i.e. is it used in memory catch controllers? or anything anymore?

[@Vulcapyro]

A parity bit is a kind of checksum, just a very simple case.

[@SquallTheBlade]

You do realize the call would go as bits to the other city and those bits could get "flipped" as well?

[@oblioblivion6138]

good starting point. thanks. I'm going to go deeper and hope my brain doesn't smoke.

[@necromancerpencil]

It would be easier in this specific case but this is a general solution for all possible codes. What if the codes you're expecting are 010101 and 101010? What if you're expecting one of ten codes, not just two?

[@whtiequillBj]

I'd be interested to see a video on networking TCP/IP and how it relates.

[@coopergates9680]

***** So it works best with any odd number of bits in the original ack or nak signal. On the receiving end (after possible errors), just count up the 1s and 0s. More 0s = ack, more 1s = nak. For instance, let's try it with seven-bit outputs: ack: 0000000 --> 0101100 // That's fine, four zeros and 3 1s, it's still an ack result. nak: 1111111 --> 0011101 // That is acceptable as well. Four 1s and three 0s, still a nak. This allows up to 3 bits to be corrupted. If you want to allow for x corrupted bits, you simply need 2x+1 0s for the ack, and 2x+1 1s for the nak. Honestly one of the simplest problems your videos have dealt with.

[@herauthon]

Cooper Gates simple CRC works with comparing bit sets - more complex corrections use larger blocks and calculate a hash - if the hash fails to comply at the other side - this block is at fault and can be sent again. but what if electric interference is the cause of the fault ? What if one changes the frequency on the bus.. and lower the error rate with it ?

[@cgvedant]

How is 010 different from 001? If the zeros are detectable,why not send a 1 bit code for ACK and a 2 bit code for NAK, since the number of bits never change?