Video 8-1: §8.1 Error correcting codes introduction

0:00 Introduction

0:04 in the next unit unit 8 of com5 to 6 i want to talk about error correcting codes in a sense this is the opposite form of compression compression we try to store as little information as little bits a few the fewest number of bits we could to represent the same data now we're going in the opposite direction we add a few bits to make up for potential mistakes errors in the communication it's a different lens but the two things often go hand in hand both in applications you often first compress and then apply error correcting codes for transmission and also the theory behind it has many touching points this will be a fairly short unit and will only just scratch the surface of error correcting codes but i want to introduce you to the nice hamming codes as one example and a few lower bounds the math and the theory behind it in in a very short excursion so i think this is a very enjoyable unit as well and there we go it will have three little parts i'll give you a quick introduction what the setup is what uh what is communication error correcting codes why do we need those then we'll talk quickly about uh lower bounds what is what is not possible with with these

1:09 Overview

1:25 codes and then i'll show you the classic example of error correcting codes the hamming codes which gets close to these lower bounds but also leaves some things on the wish list still open so this is also an active area of research still with occasionally very smart and exciting new inventions let's get going

1:59 Communication

2:01 in this in this unit we'll talk about communication and the communication is between some two parties one person wants to communicate to some other person some information or it could be it could be computer systems where we'll get to in a second the key feature of communication is that it's usually not perfect it's noisy in a vague sense for humans it could have a multitude of different reasons there could be a construction site outside outside that creates a lot of noise and you just acoustically don't hear what the other person is saying it could be weird forms of pronunciation maybe the person has a very strong accent that that affects pronunciation or maybe they have a disability that makes makes speaking different for them there could also be on a more semantic conceptual level misunderstandings we use the same words but we mean different things or humans use irony and all these uh separate layers beyond the superficial literal layer of of language and of course languages to start with ever since the tower of babel if you believe in that story

3:23 or just naturally by evolution people living in different areas have found different languages different words for the same things and we can translate from one to the other but if you've ever had a conversation where you used google translate or something like that you see how easy uh you will have seen how easily things get lost in translation so these are things that happen when humans communicate now we've actually have built in error correction method mechanisms into the way we communicate how do humans cope with the fact that someone doesn't understand or hasn't understood uh what they said in the first in the first great place hopefully that person uh realizes that and then slows down speaks up a bit or maybe the other person is proactive and says sorry i didn't get that can you repeat so that's another form of error correction you just try again right so this is how humans cope with this noisiness of communication

4:35 and indeed this works very well and language itself or at least the written language but also the spoken language itself has quite an amount of error correction built into it so you can you can try to read out this sentence and even if you don't if you don't uh carefully look at it you might be able to read this sentence at least if you're experienced in english or are a native speaker then it will be very natural for you to read that this is because it seems that natural language has a lot of redundancy built into it and there's uh misspellings there's flipped characters etc but if you look at this it might even take you a second to realize how many mistakes there are in there and our brain is just great at glossing over these but there are limits um there are limits to that and of course you want to see the comic uh if if a sentence has too many errors like like in this example we can easily detect that something went wrong this doesn't it starts it starts like an english sentence and then there's gibberish so something has gone wrong but there's no way we can figure out what this might have meant because there's just too much uh errors happening it's too

5:52 far away from anything we can identify as a as a valid english sentence but if if there's not too many errors then we can correct those and our brain is in in fact very eager to do this whenever we uh this is so uh built into us that we do this even if we don't want to or shouldn't and there's even games that exploit that fact so it's quite remarkable how deeply ingrained this is into our brains we automatically make these error corrections without even thinking about it sometimes without even consciously realizing it

6:35 and uh well you can read this on your own this is a bit of nerd humor communication is definitely about two parties one person tries to communicate to another person and often it's two ways but for we will always restrict it to the case that there's a sender and a receiver and they might switch roles uh once in a while but uh in scenarios like this current lecture is actually quite close to this theoretical scenario where there's one sender and receivers and we don't really switch roles a lot so this uh this nicely fits our situation

7:23 okay communication usually uses some sort of medium to get from the sender to the receiver and these can be of different kinds um for computers it's usually some copper cables or maybe uh optical cables nowadays and these these can be affected by electromagnetic inference interference if it's if it's a copper cable uh i think the the the optical cables are probably also for that reason fairly stable but i suppose there's uh there's um sources of noise also for those um for computers what we do is we transmit a binary string and noise might mean that we occasionally flip a bit so we wanted to say one one zero but it came out as uh one zero zero say okay

8:20 that's the that's the type of noise that we will look at um you can invent different models and do different things uh but this is this is the the standard model it sounds reasonable uh computers are binary there's they're discrete so there's not something that you can say there's a bit of noise and now the one came out as a 0.5 that has no meaning for a computer it's always digitized into a yes or no but it might occasionally flip to the other side if it was too noisy too far away from where it was when it was sent and we'd like to have a way to deal with such errors and again um we'll aim at two different things two fundamentally different types of of goals for for codes we can aim for error detection that sounds not very useful in in itself but uh of course you should you should think about a two-way communication where you can just tell the other person the sender uh sorry didn't get it can you re-transmit please and uh this is this is ubiquitous on the internet tcp has built-in mechanisms for that there are certain codes that are very efficient at just detecting whether an error has occurred and if so it signals that to

9:47 the application and just asks it to us ask for that package again uh we will focus more on the error correction part where we assume it's not so easy to to ask for a re-transmit either because that's um very costly or not um possible at all because it's a strict one-way communication um suppose you're sending some uh some satellite into outer orbit or even further away some some little devices uh what was it called the one that's left our our solar system by now there's there's not a lot of a chance that you will ever reach that by transmitting something it's a one-way communication and you better have a form of error correction built in because over that long distance radio signals won't be undisturbed

10:46 so that's the setup and in both cases we will need redundancy we will need to have more bits in them in the message that we sent than we had in the plane message in the plain thing that we want to transmit so we'll always assume our message is is this we start with a message of just some bits a bit string and then we add some more bits to it and transmit that together and hopefully that will be enough for us to detect or correct mistakes in the communication

11:28 and at this point before i really give you a chance to have an intelligent answer to that question i want to ask for your gut feeling uh what do you think in say we have a message of 100 bits i want to transmit 100 bits to you uh how many bits should i would i need to add so that it becomes possible for you on the receiver side to detect if there was a a bit flipped of these 100 bits so i'm assuming a fairly reliable uh channel where uh i don't expect i don't think it's likely that more than one bit flips at the same time but i i cannot be sure that there's not a single bit that flips we'll see in a second a scenario where this is a physical reality it's fairly unlikely to happen um but it occasionally happens that a bit flips it's very unlikely that two bits flip at the same time or even more that's the scenario i have in mind at this point uh and i want to transmit 100 bits what what do people think is the right number of bits that i need to add to detect any such one bit error

12:53 don't be shy there's no right or wrong at this point i haven't really told you anything about this unless you have seen this before um no one can expect that uh you know this that's totally fine i'm just after um a gut feeling for this and uh i just want to stress that this is about detecting errors right i'll have the same question in a second also for correcting errors so we have both goals and obviously correcting is is more costly than detecting but other than that maybe it's it's not so clear what this should be um and let me just show the results without commenting in any way or another so here you see a bunch of numbers and don't let yourself be influenced too much by what you see just type what you think as your first thought and um at the end of this session you will all be able to answer this question in a more intelligent way by or i mean by intelligent i mean in a more knowledgeable way because you will have learned the answer then

14:14 i'd like to jump to the other question uh so if you have if you want to send your answer please do that in the next like five seconds and uh then let's lock that in and here's here's the second one uh so again same question but this time i want to know how many bits you need to correct a single bit error so same scenario i think it's fairly likely that one bit might get twisted but i don't think that two will be two will be flipped and i want to correct any single bit error what do you think how many bits we have to add to with the 100 bit message to be able to do that uh that is the question and again um just what do you think intuitively if you if you've thought about this for a minute uh what do you think might be a reasonable number i'll just leave that question open um doesn't do much harm now i'll stop it in a in a few minutes and we'll revisit that later in this in this unit