Video 6-1: §6.1 Error correcting codes introduction

0:03 welcome back to uh efficient algorithms come 5 to six in in unit six we'll do a brief Excursion to error correcting codes this will be a much shorter unit than the compression unit not because there's much less interesting things to say about error correcting codes uh but I think for an algorithms class there is indeed more interesting algorithms in compression than on this topic but maybe it's also my personal bias I do want to show you a few uh a few nice little highlights of error correcting codes though uh the B the outcomes are that you have some uh understanding of the context uh you know what's what's possible there and the distinction between detecting errors and correcting them you should understand the terminology of block codes we'll come to that and we'll have essentially one concrete set of codes the Hamming codes that we'll look at in detail uh and then again finally applying the knowledge is more important than knowing all the details alone you should be able to to judge when that such a code is suitable to solve a problem that you're

1:17 facing very short unit as I said I'll give a quick introduction and then tomorrow we'll look at the what's not possible and then what is possible so I said there's some some philosophical connection to the previous section uh what what it is about is um we're somehow in both these units thinking about getting data from one point to another and if you if you do that in a computer you have to encode things in bits and then you have to get those bits from A to B now it's useful if you have few bits to get from A to B because then communication is is faster and so on so compression is often used used to reduce the amount of information you need to transmit but then for the transmission itself you often have noise in the communication channels that you're using uh we're very used to this so when I speak to you there's acoustic noise from the room hopefully in a good lecture theater and with using the mic properly not as much but it's never zero um I might not pronounce things very clearly sometimes or other people U Maybe I'm doing this perfectly but other people aren't or whatever uh make your pick but you can certainly imagine uh situations where that's a problem and

2:39 then of course there's more semantic things to it too that's what um humans have uh clearly in their forms of communication as well now we've also found ways to work around that uh one option is if you can't understand what someone says if the the noise is too much much compared to the signal then you just ask them to speak up or maybe uh repeat what they said or speak more slowly or various options like this um often we can still make out what someone said despite all the noise and if you think about this a bit more abstractly or uh a bit more more from the higher level how how is it even possible that we don't get all the information from the other communication partner from the sender and we can still make out what they meant okay some of that might be uh we just fabricate a meaning that they may never have intended but that's not what I'm getting at here uh what I mean is our language and the way we communicate has a lot of redundancy built in there's a lot of things you can do to for example the spelling of English that doesn't affect how well you can read it now this this is a bit dependent on how well you're trained

3:59 with reading English uh but for for most um most people that have English as a first language they can easily read this sentence and they can properly produce the the right spelling so there's redundancy in in the language in that it doesn't actually matter if you scrambled a few letters you can still undo these errors uh but then if you overdo it uh you can see that something went wrong but there's no way you can I mean it's just too far away from any meaningful sentence for you to say what it could have meant before and that leads me to um that this first Distinction on the technical side uh there's a it's a different thing to detect that something went wrong and to uh just correct these errors automatically or from the information you're you're given so here it starts out fine and then you notice okay some some someone fell asleep on the keyboard or something uh whereas if there's just a few little things you may even not notice them while reading now okay I try to keep the examples Concrete in in writing the same happens with with voice right there's there's okay I'm I'm not so good I'm not out of my depth here but uh I think there's certain variations in frequency

5:23 and so on that we're completely oblivious to if I have a more high or low pitched voice you can still make out the uh the patterns of of language and sound and pronunciation so there's certain things that are irrelevant but then there's this lovely game depending where you come from but the game is you whisper someone in the ear in in their ears some some sentence and they have to pass this on by a chain of whispering into people's ears and what comes out at the end often has nothing to do with what you started with so people are very eager to correct what they hear into something that's close enough in what in meaning to what they they think might have been the original thing and we're sometimes too eager doing

6:15 that okay so detecting errors correcting errors both things that intuitively we do all the time and of course also the options are if you can correct the errors then hopefully corrected it correctly whereas if you just make out I couldn't get it you just as to repeat it the same as what computers can do as uh as a countermeasure uh you can try to build in redundancy so that you can still make out what the original meaning was or you can ask the other side please send me that package again internet protocols have that all built in um but that's a bit boring from the from the coding side so we'll we'll mostly focus on those on correcting codes but um detecting is a prerequisite

7:03 uh yeah to the Computer World so where does noise come from for us um computers typically communicate with electrical signals but that's not the only thing uh so if you have copper cables there could be inference from magnetic fields electromagnetic fields that just uh interfere with the signal that you get um we usually abstract away from the physical details we'll just transmit a string of bits and you can think of different ways of what could go wrong what we'll basically assume is that the time the clock is not perturbed but the signal might be so it could happen that one of the bits was a one and flipped to a zero or vice versa uh but we we assume that the timing is U is correct uh it's much more tricky if you also allow that there could be bits inserted or deleted from your bit string uh if you if you think about transmitting something across a wire that's actually a reasonable assumption you usually have a separate clock signal and that is somewhat stable whereas inter interference might be twisting a bit to the other side and the goal is to have a way to send send data across such an unreliable Communication channel to still allow reliable communication uh as as for humans we

8:23 have the two options if we just detect an error we can request a retransmit um sometimes if sometimes that's the best option but for some communication channels there's no option of resubmitting then you want to build in enough redundancy to correct it straight

8:46 away I think it's quite clear that you need some form of redundancy to correct errors or even detect errors simply because if you have no redundancy built in any kind of change that the channel does to your message the receiver will just have to take as oh you meant this other message and there's no way for them to know so uh you have to send more bits than the plain text the plain message that you're trying to to transmit in a way that's the opposite of compression we're making things longer now whereas we tried to make them shorter before but you should think of them as going hand inand again it's a pipeline if you send something across a communication Channel you first want to compress so that the message becomes short and then you blow it up but you blow it up in in a specific uh judicious way with building redundancy and that's helpful not random

9:41 things okay um I want to close this part with getting your thoughts on two questions just now I know that many well some of you maybe have seen this if you've done some more electrical engineering undergrad maybe this is uh I'm telling you baby stuff here um if not then you may never have seen this and it's totally fine so it's just your gut feeling uh what do you think should be or could be possible here and the first question is if I if I want to send 100 bits as a message and uh I want to detect whether there's one bit that flipped um how many bits of redundancy would I need to do that what do you think um I think I'll yeah we can discuss the results briefly but I'll only really show you the answer tomorrow keep up the tension a

11:13 yeah maybe we should have specified just send one number or uh you can say you can send no idea if you really feel like you want to send no idea uh but several people send so and so many bits and so on uh send just the numbers so that we get a nicer nicer word cloud

12:02 all right I mean you can you can finish sending your things but because uh quite a bunch of people are are done here's just uh what people sent I won't comment on whether any of these are correct right uh we'll see tomorrow um of course a bit disappointed that nobody said

12:25 42 uh so I have a second question which is the very same thing but with correct instead of detect so probably we need more bits for that but other than that maybe is not obvious so here's the second

12:56 question again just send the number no uh no units unless the unit is clowns I guess that's fair I don't well as before I said I won't comment on on any of it we'll uh I I'll keep them on slider and we'll discuss tomorrow