Video 8-1: §8.1 Error correcting codes introduction

0:00 Introduction

0:03 good all all ready to go i think welcome back uh in unit eight of com five to six a short unit we'll look at error correcting codes it's a nice little um construction that we'll look at at the end of this there's a few nice additional lower bounds that fit into this and it's a nice way to complement the the longer compression unit so i think you will enjoy this one and the main construction is also an easy going exercise so

0:38 Learning Outcomes

0:39 without further ado the learning outcomes for this unit are to understand this context where when we talk about communication in computer science we usually mean two machines talking to each other uh but they still make errors in in the communication medium and we have to work around those and there's some some standard constructions how you can achieve this uh you will always have to live with the fact that there's a small probability of failing but we will what we will be able to do is bring that probability down by by using specific codes that can correct certain small errors uh we'll look at certain examples block codes is the general theme hamming codes is the concrete one that we will look at and we will argue a little bit about when or when not such a code is applicable

1:37 the unit has has three short sections a bit of introduction and then the lower bound side first this time and then the hamming codes as a way to achieve some parts of this

1:50 Communication

1:52 so what are we talking about uh we talk i put this title noisy communication but it's maybe true that communication is almost always noisy in some sense uh if if you think about humans when we talk to each other there's all sorts of things that can go wrong i'm sure you know all about about these and how do we cope with that what ways have we found to work around all of these different problems

2:22 i think humans are quite good at sensing whether the other person's following using our mirror and neurons we try to see what the other person's reflecting in in their faces uh well before they ask pardon and so often we automatically slow down speak up try to say things in different terms when you when you're asked to repeat something maybe you don't say it word by word in another way if you feel the other person maybe is not

2:50 english as a first language person maybe you try to rephrase it all these things we do almost automatically but there's quite a lot of things we we do to try to make communication a bit more reliable and we'll see some of these also pop up in the machine context in slightly different forms um another thing is that if you if you read out this sentence maybe you can try it for yourself it's remarkable how much redundancy is built into natural language text we looked at this in the last section i showed in the last unit i showed you this example of compressing the text of the bible down to a quarter that was one way of saying oh three quarters of the bible are just repetition and maybe this is not so much to say about the bible than about english as the the translation of the bible and the flip side of this is even if i jump around some characters you can still read it and assuming that this is an english sentence you will automatically figure out what it was even though there's quite a few characters wrong or missing or jumbled around

4:01 so to make this a little more precise um we can do two different things and there are if you think about them they're quite distinctively different we can detect errors and we can correct some errors in this in this sentence we're pretty good at quickly spotting that something's awfully wrong if that doesn't look at all like english but this is beyond repair there's there's too much i mean you can you can only make make wild guesses what that could have meant whereas in the second case or in this box if there's smaller errors we kind of find the closest possible legal english sentence and this this is something that our brain does automatically because we're so much trained to reading um and well the you can there's this child's uh game where you you whisper something in one person's ear and the person has to say to the next person's ear and if you've gone through uh a row of ten ten kids then what comes out has nothing to do with what the first person said uh it's known of the different names i don't know what do you what do you know this game under what name chinese whispers yeah i think uh telephone is the american version and yeah similar some some similar term

5:20 to chinese whispers is the german one so somehow it's it's associated with chinese which is uh probably just because it's it's very foreign for europeans so we we try to automatically correct something that we hear to something that makes sense to us and we're very eager in doing that sometimes too much so

5:44 okay so that's that's for communication but what we'll take out from from this into the technical context is this distinction detecting errors is not the same as correcting them and clearly the the second is tougher

6:02 for computer communications we'll usually obstruct them to a channel so that's just something that transports information from one end to another for computers these are usually cables or it's some sort of radio signal we'll always pretend we transmit some binary string if not then you know from the last chapter how to encode that in binary so it's not really a restriction and our model will be that this channel occasionally flips a bit it turns a zero into a one and a one into a zero this nicely fits a scenario where the channel has a well synchronized clock so the channel can be in two states it can be high or low and then you read out the state of the channel in regular time intervals and we assume that this time is not uh tampered with but maybe the channel sometimes is ambiguous and then it's jumping into the right in the in the wrong direction that's the model of of noisy channels you can make the game more challenging by looking at different channels you can also assume that maybe sometimes there's an additional bit squeezed in or that other types of errors occur where a whole burst of of bit flips is more likely we'll keep it very simple for this one so there's some probability that each

7:27 individual bit is flipped we think that this probability is not too big but it has to be dealt with because it occasionally happens if you transmit a long message so we're trying to look for a robust code a code that achieves good com good communication even though this channel isn't perfect

7:48 so we definitely want to detect errors so that we can just ask the person to say the same thing again ask the computer to retransmit that package sometimes it's also convenient to correct the errors if possible so we build in more redundancy then we can avoid re-transmitting something and there's also scenarios where re-transmitting is not really an option if you send some [Music] some uh something into outer space and it sends messages back to earth uh telling that thing to just send it again might not even be possible because you can't reach it it's only a one-way communication channel so both are equally important depends on the scenario if if detection is good enough

8:35 for both we will need some form of redundancy i think this is intuitively clear if every possible bit pattern that you can take out of the channel means something different to you then there's just no way you can know that an error was actually meant something else and it's not the message that you received without an error so you need some you need to send a few more bits than the actual payload than the actual message and we would like to reduce this this additional number of bits that redundancy now because you probably don't know much about this the next question is just asking for your intuition um and it will be i think instruct insightful to look at this again later so suppose very simple scenario you want to send 100 bits across a channel and say with with some percentage uh there's a five percent chance that every bit gets flipped let's say a one percent chance then we expect one error um how many extra bits do you feel think just a gut feeling how do you think what do you think how many bits we need to send on top of these 100

9:08 Intuition

10:02 and specifically that a single bit was was flipped that's the error that we're looking at again miraculously more people voting than are in the room or on the live stream i don't want to discourage watching this live stream together in the room maybe that's what's happening it's a very lovely idea

10:57 all right let me just show this uh the guesses very wildly from 1 to 100 200 and i don't want to comment on this much i have a similar question so this was just for detecting the errors now the same question but now i want to be able to correct this error okay so same scenario otherwise but in case your code detects that there is an error i want to be able to also fix that one

11:42 again unless you've seen something about this there's no way you could know so you just just guess i think the the main purpose of these questions is if you look back at your answer from before in an hour it might be interesting for you to see

12:15 yeah we had something like 29 last time um let me show it again i won't comment on this point again widely different guesses the only thing in that probably should be clear uh the number you type for the second question should be at least as much as for the first question if you can correct an error you've already detected that there is one because you know what you received you know what you produced and if these are different then there was an error so that's that's kind of obvious anything beyond that

13:00 at this stage you can't really know from anything i told you at least