Error Correction - Computerphile

Подписаться 2,4 млн

Просмотров 248 тыс.

50% 1

What good is knowing you have a problem if you can't fix it? - Professor Brailsford explains Hamming Codes and how errors can not just be detected, but also corrected.
Original Compression film: • Compression - Computer...
Entropy in Compression: • Entropy in Compression...
Error Detection: • Error Detection and Fl...
Home-made Video Arcade: • Homemade Video Arcade ...
BASIC & Sorting: • Programming BASIC and ...
/ 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. See the full list of Brady's video projects at: bit.ly/bradychannels

Опубликовано:

9 сен 2013

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 314

@ArrayPro 9 лет назад

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

@AlexanderBollbach 9 лет назад

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.

@damiensadventure 9 лет назад

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

@AaronCZim 11 лет назад

This is my favorite series in computerphile so far.

@RobbieMelvin 11 лет назад

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.

@aafaqin 9 лет назад

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 ...

@JMPDev 11 лет назад

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 :)

@SharpblueCreative 9 лет назад

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.

@Ykulvaarlck 8 лет назад

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

@steve5390 8 лет назад

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

@AlexN5142 11 лет назад

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

@Imrooniel 11 лет назад

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 :)

@elliottmcollins 11 лет назад

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.

@TorgieMadison 10 лет назад

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.

@landmanland 11 лет назад

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

@AlexanderTrefz 11 лет назад

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!

@ThatAnnoyingGuyFrom 11 лет назад

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.

@hellterminator 10 лет назад

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.

@HiAdrian 11 лет назад

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.

@RedEyedJedi 7 лет назад

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

@Qladstone 9 лет назад

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

@ButzPunk 11 лет назад

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

@yvrelna 11 лет назад

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.

@lmpeters 11 лет назад

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.

@LeandroConsentinoFerreira 11 лет назад

Just discovered the channel! Loved it!

@iismitch55 11 лет назад

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

@luketimothy 10 лет назад

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.

@AllElectronicsGr 11 лет назад

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

@SpySappingMyKeyboard 11 лет назад

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

@nehemiah7914 11 лет назад

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

@phelpsio 11 лет назад

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

@immortal_coil 11 лет назад

Fantastic video!

@lejink 11 лет назад

yyyeeeaaaa new computerphile video!!

@Bryan6446 11 лет назад

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.

@Andrei5656 10 лет назад

he is an amazing teacher. thank you

@pcljet 11 лет назад

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).

@subach 11 лет назад

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

@ryPish 11 лет назад

Computers are amazing D: And Professor Brailsford is really good at explaining how they work. More please :V

@thomasbladykas2245 10 лет назад

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

@Jenny_Digital 11 лет назад

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!

@jmoneyjmoneyjmoney 11 лет назад

Anyone else love this guy's voice?

@zol404 11 лет назад

This chap is epic at explaining stuff

@MikhailChernoskutov 11 лет назад

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.

@yvrelna 11 лет назад

(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.

@CamboInteractive 11 лет назад

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".

@Paul-A01 8 лет назад

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.

@thecassman 11 лет назад

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

@Keskivertomies 11 лет назад

Fascinating stuff!

@LittlePeng9 11 лет назад

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

@aBetterHumanBeing 11 лет назад

Thanks, very clear and simple explanation :)

@GlennSimpkins 11 лет назад

Professor Brailsford is is WIN!

@CoolJosh3k 11 лет назад

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.

@3snoW_ 11 лет назад

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.

@coder_extreme6389 5 месяцев назад

Loved it Sir.

@DIYTAO 11 лет назад

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.

@nadi106100 11 лет назад

Very nice answer!

@kellypainter7625 6 лет назад

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.

@jeebersjumpincryst 11 лет назад

wow - that was very very good!!! thankyou for that so much!!! u explain so very very well Professor :)

@gravityhatfilms 11 лет назад

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.

@Space-Industries 10 лет назад

awesome video! SUBSCRIBED!

@kayvee256 11 лет назад

Do hamming codes next!

@kayvee256 11 лет назад

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. ^_^

11 лет назад

Here are a few great ideas for the next Computerphile videos: Field theory, rings, groups and/or cosets :D

@elliottmcollins 11 лет назад

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.

@owenb111 11 лет назад

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

@MateuszZwierzycki 11 лет назад

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.

@ProxxSMGxGods 6 лет назад

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.

@iabervon 11 лет назад

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).

@JumpingNoCrime 11 лет назад

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.

@AlderDragon 11 лет назад

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

@whtiequillBj 11 лет назад

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

@Vulcapyro 11 лет назад

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

@oblioblivion6138 10 лет назад

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

@KutuluMike 11 лет назад

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.

@recklessroges 11 лет назад

"Other lovely stuff like that" == Error Correction with Reed-Solomon, and Golomb rulers.

@NathanaelNewton 11 лет назад

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

@thecassman 11 лет назад

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.

@ancmoto 11 лет назад

Great teacher

@_philipp__ 10 лет назад

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

@subvind 8 лет назад

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

@magicvortex 11 лет назад

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

@xshortguy 11 лет назад

this guy's a boss at drawing cubes.

@nehemiah7914 11 лет назад

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!

@blidge8282 11 лет назад

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

@AaronBowersable 8 лет назад

I love this old reel feed paper!

@ArichManas 11 лет назад

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.

@rudyeilabouni 7 лет назад

First semester Computer Science here and I have my information theory test next week! Wish me luck!

@frepi 11 лет назад

What video is he referring to in the beginning?

@Gewath 10 лет назад

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 (RU-vid) 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).

@orphyn09 11 лет назад

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

@TheViolaBuddy 11 лет назад

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

@joeproozen2936 10 лет назад

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

@insrtclevrnamehere 11 лет назад

great video! you should make one on how graphics/physics engines for games/3d render. or how the GUI uses resources and displays information from the system and its directory's. hope u like my suggestions :)

@RodrigoGraca31 11 лет назад

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

@rsnilssen 11 лет назад

I want all the other stuff he mentions!

@Gewath 11 лет назад

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.

@luisdanielmesa 10 лет назад

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...

@mathiaschunnoo1904 11 лет назад

Hi computephile, i just started programming opengl shaders and i would love if you could make a video on graphic cards.

@BGBTech 11 лет назад

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?

@ItohKuni 10 лет назад

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.