Error Detection and Flipping the Bits

Error Detection and Flipping the Bits - Computerphile

Рет қаралды 119,252

11 жыл бұрын

Devising codes for different weather states is all well and good, but what if the weather strikes back? Electrical storms can distort codes and noisy lines can confuse things, Professor Brailsford shows us one way of building redundancy into the system.
Is Zero Even? - Numberphile: • Is Zero Even? - Number...
Mainframes and the Unix Revolution: • Mainframes and the Uni...
A Career in Video Games: • A Career in Video Game...
Professor Brailsford on Compression: • Compression - Computer...
Professor Brailsford on Entropy in Compression: • Entropy in Compression...
Sound Effects courtesy of www.freesfx.co.uk/
/ 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:periodicvideos.blogspot.co.uk/...

Пікірлер: 290

@heyandy889 11 жыл бұрын

I love error correction. When I learned about it in Digital Logic, I was pretty floored that the simple rules could detect, and (in the case of Hamming code) even correct the error! I was floored. Of course, it's not practical, as I have the full network stack between me and the bits. But it is shades of things to come as far as what can be automated.

@riskinhos 10 жыл бұрын

really. this guy is great. makes this things look so easy. love it.

@lejink 11 жыл бұрын

This is my new favorite channel of yours Brady, glad to see so much activity with it lately

@chrisharrison763 11 жыл бұрын

Another excellent video from Brailsford. When Computerphile was announced, this is exactly the kind of video I envisioned the channel would be creating. Nice work!

@benjaminjarrell2758 11 жыл бұрын

Wow, i've never thought of that was to preform the xor logic function, adding the 2 inputs together and rather or not the sum is even is the exact same output as an XOR function

@Random2 11 жыл бұрын

Yes, a video on forward error correction and/or cyclic redundancy checks would be a very nice sequel to this video. I doubt the channel takes suggestions, but I'll still leave it here :) (Also, good job so far on the videos, keep up the good work!)

@Truthiness231 11 жыл бұрын

Been writing an RLE solution for a program I'm working on (probably why KZfaq recommend this), and this was JUST what I needed to see. Very, very good thought provoking discussion here, I was so worried about compression I forgot all about error proofing and recovery.

@aqcd 11 жыл бұрын

Professor Brailsford is great! id love to see more from him. Keep the vids coming

@onecanina 11 жыл бұрын

I have learned so much from your videos Brady, thank you so much! Mad props to you!

@TheYxxy 11 жыл бұрын

Well, now you have to show us the distance 3 and more codes! Can't wait :D

@TopShelfization 11 жыл бұрын

Great stuff, loved the weather analogy, it helps me understand better..

@JMPDev 11 жыл бұрын

Please have more in this series! I'm curious to see the other error protection.

@SuperSteveAnon 11 жыл бұрын

I really like this topic, and look forward to there being more along these lines.

@MostlyLoveOfMusic 11 жыл бұрын

good video, very thorough and nicely explained

@Magykman 11 жыл бұрын

What a magical voice. Bravo!

@navetal39 11 жыл бұрын

1:48 "it's sunny in san-francisco! No, it's foggy!" But you just said there was a thunderstorm!

@FernandoPazin 11 жыл бұрын

Professor Brailsford is very good at explaining. I liked a lot.

@Crillboltheadgehog 9 жыл бұрын

Thanks so much buddy! You are making my AS computing course so much easier to understand! Thanks so much and keep up the good work!!

@opaldragon75 11 жыл бұрын

love this channel! A lot!!

@autom4 11 жыл бұрын

These videos are just fine thank you very much.

@buzzert1 11 жыл бұрын

I'd love to see a video about error correction as well!

@lesconrads 11 жыл бұрын

Amazing! Love this series :D

@MrShysterme 11 жыл бұрын

I love these information theory videos. Information theory is so rich. It is useful in many fields besides data compression and signal transmission. For example, an important part of statistics is going toward information theory.

@iabervon 11 жыл бұрын

Details: use GF(2^n) instead of normal arithmetic, which means that addition, subtraction, multiplication, and division all "work" and don't require more than n-bit numbers. Treat your 15-number sequence as a big number without carrying from one place to another. Valid sequences are multiples of 1,1,1,1. Invalid sequences are a multiple of 1,1,1,1 plus a

@jeanguylouisbourg 11 жыл бұрын

man, i could listen to this guy talks for hours on ends. this stuff is super interesting!

@flatdragonfruit5 11 жыл бұрын

Seriously dude... This channel is about computer science, and comuter science is all about thinking. :)

@instormental 11 жыл бұрын

This video takes me back...to the digital systems test I had this morning. Maybe I should've been watching this yesterday instead of studying and avoiding KZfaq :P

@AdamBreitkreutz 11 жыл бұрын

I was expecting to hear about that too. If you're interested, error correction (and detecting multiple errors) is done with a cyclic redundancy check (CRC).. There are longer and shorter CRCs that can detect/correct more or less errors in the transmission.

@Computerphile 11 жыл бұрын

thanks will have a look >Sean

@ragnkja 11 жыл бұрын

That was discussed in the video about compression; if you sent a 1, it could, in your system, be either "foggy" or the beginning of "cloudy" or "rainy". If the system needs to be able to send many messages with as little space between them as possible, they need to be possible to identify without wondering whether the next bit is part of the message or not.

@MrShysterme 11 жыл бұрын

This channel has a different intended audience. I'm sure you can find tons of other videos on youtube that fit your needs.

@bakh554321 11 жыл бұрын

I love these videos

@Ubeogesh 11 жыл бұрын

Error correction is a very interesting topic, could you do more on this?

@trefod 11 жыл бұрын

If only all teachers were as clear and understandable as this guy, far more people would know far more stuff.

@A3roboy 11 жыл бұрын

I can explain that in a sentence. IP's aren't distributed randomly, they are assigned: certain countries get a certain batch of codes, certain ISPs within get a subset of those codes, and so on, so one can easily look up which country, region, ISP, etc. your IP belongs to. However ISPs *do* assign them randomly, so at best someone can find out where the last non-random element along the line was.

@Jelle_NL 11 жыл бұрын

Is there then a way to detect or even restore an error with 2 errors or more?

@noupoi 11 жыл бұрын

Would love to see a video about error correction!

@Whateverworksism 11 жыл бұрын

What makes you think that this channel accepts no suggestions? May I remind you that it was the heavy amount of suggestions that made this channel possible to begin with. If we do not suggest things to Brady he will be blind on what to do next.

@tomasbarry1 11 жыл бұрын

What if the acknowledge or the not acknowledge message gets distorted?

@TensionFreeTape 11 жыл бұрын

Sure are. One really simple extension of this idea is to use a "distance 3" coding, which means that each valid code has at least 3 digits different to any other code. Now if any single digit is flipped, the error can be detected in the same way as explained in the video. This time though the received message will differ from the correct code by only 1 digit, but differ from every other code by at least 2 digits. This new system can detect errors of 2 digits, OR correct single digit errors.

@CoolJosh3k 11 жыл бұрын

Hopefully you'll go a little into forward error correction. The way forward error correction works is quite ingenious.

@yvrelna 11 жыл бұрын

Well, not easily, but it is actually possible to track the physical address from the IP if you control the destination network (i.e. you're the ISP) or have cooperation from someone who does. ISP owns/lease the cable line from your home to their server, and they know exactly which IP address belongs to which router. This information usually isn't available to the general public, but they are available and trackable.

@Zyztematic 11 жыл бұрын

Are you going to make more videos on error detection/correction? Maybe stuff like XOR and Reed-Solomon, and where they are used today? For instance, a distance 2 code is used for error detection in TCP.

@funduk89 11 жыл бұрын

more of this guy!

@xPel20 11 жыл бұрын

Some english subtitles would be great for foreign ppl like me! It will help a lot!!! nice vids!!

@Vulcapyro 11 жыл бұрын

I would also like to clarify that it's called a 2-distance code because the minimum Hamming distance between any two codewords is 2. That is, any two codewords differ in a minimum of 2 places. This naturally means that if there are two errors in a transmitted codeword, it's possible that it would be read as a different valid codeword, and so what Brailsford said was essentially the same thing. I just want to make it clear why it's called a "distance" code.

@xway2 11 жыл бұрын

There's a video on Numberphile about a similar thing. It talks about error checking in ISBN codes (for books).

@Doc_Fartens 11 жыл бұрын

Wasn't a fan of computerphile at first to be honest, but its growing on me as time goes by.

@Whateverworksism 11 жыл бұрын

and just btw: I agree very much with your suggestions to a sequel :)

@nitelite78 11 жыл бұрын

Is there going to be a part 2? Surely there needs to be. What happens when you don't know whether a code is valid or not e.g. for a sound file?

@silentcod3r 11 жыл бұрын

If he thinks that, then he would really hate a Data Structures class. This video is really good.

@mattlm64 11 жыл бұрын

Are you going to do a video about hamming code?

@Kaslai 11 жыл бұрын

I've actually played around a bit with TCP/IP on the wire, and that's exactly how the protocol does its error checking. IP will sum all the "on" bits in the IP header itself, and TCP will sum up all the "on" bits in the message and TCP header. This method is more robust than a single check bit, but it's still only able to detect 1 error in the worst case. Any transposition of bits can't be detected.

@InternetsBeloved 11 жыл бұрын

If the ACK/NAK you're sending back is only one bit, what is there to stop that bit from being flipped? There's no parity or checksum there, so it seems like it'd be easy enough for some electrical disturbance to turn a ACK into a NAK or vice-versa.

@metacarpo10 11 жыл бұрын

totoritko I understand that, but whats the necessity of 8 bits in total to pass the information, as in {00, 01, 10, 11}, wich would be more expensive, when you could only spend 6 bits, as in {0, 1, 10, 11}? And thanks for the reply!

@andraip 11 жыл бұрын

Now that you mention it, getting the time complexity of mathematical relations was indeed a pain in the ass, had completely forgotten that part XD but fortunately we didn't spend to much time on it.

@isaacmonge3210 11 жыл бұрын

Makes sense. The code should always have an even number of 1's and if for whatever reason it is distorted, it will change it from having an even number of 1's to having an odd number of 1's. Therefore it would not be acknowledged. Very, very interesting topic.

@totoritko 11 жыл бұрын

You're going to have to either add parity info to the ACK message as well, or handle it in some other fashion (e.g. you'll see the remote end start behaving in an unexpected manner, sending messages when they shouldn't, or not sending them when they should).

@ALacunae 11 жыл бұрын

I love this guy.

@sonoftunk 11 жыл бұрын

The next episode will be about correcting 1 bit errors and detecting 2 bit errors using Hamming Codes.

@antiHUMANDesigns 11 жыл бұрын

I was writing some simple networking code, once. I dont' usually do networking. I decided to add an integer at the end of all messages that sum up the total value of all the bytes before it. Should be pretty robust in detecting errors, I believe. Just one bit wrong, and the sum won't match up, and it's unreasonable to think that many errors could occur precicely so that the sum matches. Good or bad idea?

@Vulcapyro 11 жыл бұрын

Audio and video files are very lenient in that you can have a lot of errors in the transmitted file and still end up with basically the same thing. When sending actual files we generally want to keep the file perfect, but in applications like streaming where things are time-sensitive, we often just let the errors happen so we can preserve transmission speed. Anyways, the examples in this video are very simplified. There are much more rigorous methods of error-checking that work for large files.

@Vulcapyro 11 жыл бұрын

Brady, I'm guessing there will be more entries in this series? Brailsford only got to 2-distance codes, while mentioning that you could detect one error and not correct any. I'm assuming that the next video will introduce a 3-distance code, show that it can detect two errors and correct one, and then generalize by showing how many errors an n-distance code can detect and correct. Am I on the right track?

@TheOverCaste 11 жыл бұрын

The receiving end calculates the bit aswell, and if they don't match it's changed. If what you're asking is if two total bits get changed, that can't be detected with this method, but the odds of that happening are of course quite a bit lower.

@utkua 11 жыл бұрын

sound file is transmitted as smaller blocks called bytes, 8 bits, which are validated just like weather codes, so the same thing. TCP stands for transmission control protocol, you have botch control and acknowledgment support, which is how internet works.

@Vulcapyro 11 жыл бұрын

These messages themselves have error-detection and correction methods in their protocols. Very good question, but considering we've just started talking about these things, you're jumping ahead of the simplifications made for the scenario.

@iabervon 11 жыл бұрын

It's somewhat similar, except that you've got longer packets (something like 60 bits with 44 bits of data and 16 bits of checksum). This is composed of 4-bit numbers, and you can ask if there's the right group of 4 of these numbers at the end. It's a distance 4 code, except that you get a bonus-- additional errors in the same number is free. Also, if you assume that there are only 2 numbers with errors, you can calculate which numbers have the errors and what the right answers are.

@totoritko 11 жыл бұрын

Not all communication channels allow for two-way communication (for instance, your TV set is receive-only), or may not have symmetric bandwidths (e.g. the 'A' in ADSL is for asymmetric, you get different uplink/downlink speeds). You need to consider various constraints.

@MartijnvandeStreek 11 жыл бұрын

Will there be one about error correction as well?

@captain_ironbutt 11 жыл бұрын

Hi, any videos incoming about error correction ?

@ArjanGroenenboom 11 жыл бұрын

The problem with that method is that the checksum will get as long as your message and you will want to keep your transmission as compact as possible. By applying modular arithmatic on your checksum you can keep it compact and still have a fairly reliable errordectection!

@stellarfirefly 11 жыл бұрын

There are obviously many other methods to detect situations with different sequences and types of errors. We could, for example, expand the original 2-bit code into a 4-bit (or even more) and that would detect more types of errors, but then we are defeating the reason for making a nice, short 2-bit code in the first place. So other methods exist, but are a bit too complex to just type out here. :) Look up "cyclic redundancy check" or CRC for one good example.

@GaryHemitt 11 жыл бұрын

Computerphile, can he talk about how single bits are read from memory? I like the way he explains stuff.

@Darknesblaze 11 жыл бұрын

he wants that good old ''this is a mouse, this is a monitor and that ladies and gentlemen is a keyboard'' xD

@JimCullen 11 жыл бұрын

What if the not acknowledged message got distorted? If it's just one bit, surely it could just as easily get messed up?

@367henry 11 жыл бұрын

Why is it that when I try to access my external hard drive or micro ad card it says access denied. And it's not the USB ports I can access these thing on other computers or on my computer in safe mode

@ruashua 11 жыл бұрын

The end of this video seems like a good point to leave off and next discuss hashes and checksums

@mysss29 11 жыл бұрын

Wait, you mean you didn't have to program in your Data Structures class?? Mine also introduced C++, so we had to deal with creating nodes and preventing memory leaks and segfaults, which gets tricky really quickly. I didn't have a heck of a lot of trouble with it conceptually, but others did and I wouldn't describe it as easy.

@silentcod3r 11 жыл бұрын

Ok if you are that smart to understand the new terms and concepts without much thinking or you were not given too complex projects, then that is good for you. When I was a first time student new to Computer Science, just learning the differences and how Big O, and other time complexities relate along with mathematical relations took some studying and thinking; however, I enjoyed the class. I start Advanced DS this fall.

@kd1s 11 жыл бұрын

And I gotta say, when he said "I'm not a mathematician but a computer scientist.." was great.

@realldonaldtrump 11 жыл бұрын

Not sure what you mean by "bit for bit", but transmitting data in smaller chunks doesn't necessarily make the transmission magically more efficient. Protocols exist to solve problems with realtime systems, like streaming data for audio/video. For example, if I can send a big chunk of data with added bits for error detection and correction, then, even if the data gets corrupted, it can be corrected at the receiving end.

@totoritko 11 жыл бұрын

Bits by definition can only assume two values. At the physical link level you can of course encode multiple bits into a single transmission unit (called a symbol), but that doesn't influence the information theory behind it.

@QasimMustafa 11 жыл бұрын

Thanks!

@aggeman2 11 жыл бұрын

If that is a distance 2 error correction, what does more advanced programs (like online games for instance) use? I can't imagine that this has seen much use since the 60's or 70's ^^

@Seegalgalguntijak 11 жыл бұрын

So, the more bits you put in, the more resilience against errors you get. Then, with more bits, you can even correct the error at the receiving side without having to send the code again. So there will be a point to where it makes sense to put more errors in, either to make the transmission more error-tolerant, or to incorporate an error-correction into it, or both. So how to find out, where the limit is, at which more bits don't help any more for resilience nor error correction?

@pikuorguk 11 жыл бұрын

Yeah there is, and they're pretty clever. Ever watched digital TV and seen bits of the image go green or break up into little blocks? That's the error correction making _most_ of the image still understandable. I think the next step up from simple parity checks are CRC algorithms.

@frollard 11 жыл бұрын

I look forward to seeing error correction/checking - encoding, parity, and checksum. Like you say, unless its in a message, 00 is not useful.

@thesheepscribbler 11 жыл бұрын

Wouldnt your acknowledgement code have the same distortion issues?

@totoritko 11 жыл бұрын

Ah, I understand now what you mean. The problem is that you're going to have to use more information for dealing with the variable message length. In other words, how does the receiver know whether the message they should expect is 1 or 2 bits long? You'll need to prefix a message, meaning you'll spend another bit where you were trying to save one bit. Some physical transport mediums allow you to use physical characteristics of the link for this, but in the general case there's no way around it.

@Vulcapyro 11 жыл бұрын

The mathematical efficiency of using said redundant bits quickly becomes far more important than the space being used, so while it's a good question to pose, I don't think it's necessary. Really, it's just a few bits amongst hundreds, thousands etc bytes. How many you use doesn't really matter when you consider most practical uses as long as it isn't too few to perform well; the really important parts come with how it's done and how that compares in various areas against other methods.

@rafagd 11 жыл бұрын

Usually acks/nacks are sent along with other messages inside bigger packages, so they usually follow the same idea of parity bits.

@chmis3 11 жыл бұрын

I think the simplest way for checking errors is to ping the code. Weather station sends 101, you receive 101, so you send it back. If weather station receives the code it didn't send, it sends it again.

@andraip 11 жыл бұрын

Yh, I just had to grasp the concept. XD I had to program some of the Data Structures I learned there in my programming classes, but that was easy too, basically you just had to convert a given algorithm into a java class (and I already knew you to program). But in Computer Graphics thinks got pretty tricky, when I had to implement a 3D k-d-tree in my ray-tracer (in C++), and there I also had to prevent memory leaks and that stuff. Now that required I hell of a lot of thinking XD.

@MaxBonnefin 11 жыл бұрын

Any chance of a Hamming code video?

@SuperYerkers 11 жыл бұрын

What if your one bit acknowledgement to say that the code had an error in it was scrambled making the 0 into a 1 making them think that you got the weather correctly :/

@boenrobot 11 жыл бұрын

AFAIK, modern networking protocols work in a similar fashion. Rather than sending back the whole data though (which would be disasterous if you're sending huge data - think multiple megabytes or gigabytes), they send the so called "check sum". Different protocols use different means of generating it (e.g. the number of 1s across the message, which itself is divided into fixed "packets" so that the sum fits into 1 byte), but the point is to send back meta data that can be checked by both ends.

@chirag06 11 жыл бұрын

a video on Virtualization would be really cool.

@TrAnMu 11 жыл бұрын

Ok but what if there's a distortion on the nack or ack call?

@barryallen9932 2 жыл бұрын

couldn't you double the bit message like 10 = 1010, in order to change it to a valid code it would have to have a bit error in the exact same part twice

@RealCadde 11 жыл бұрын

You could always have ACK/NAK be a two bit code. 10 for ACK and 01 for NAK. It would still have the same issues with 2 errors though. In reality, TCP/IP always has a 16 bit checksum and there is very little chance of an error slipping by there. There are 65535 different combinations to chose from instead of just 2. It works by adding all bytes together. For instance, "I am a message" has a checksum of 1213 in decimal, 0x4BD in hex and 0b10010111101 in binary.