Video 6-2: §6.2 Lower bounds for error correcting codes

0:02 in the next subsection we'll look at some lower bounds for what you can possibly achieve with uh codes and the goal was to have codes that can detect or correct errors or maybe both right um I motivated last time a bit why communication even for a computer where we thinks things are stored in binary has noise sometimes and just as a reminder we'll we'll look at specifically the type of noise where one bit can be flipped or Twisted from its actual value to the negation we won't look so much at other types of Errors although they are potentially also relevant but in the situation where you transmit some some uh signal over a wire where the timing is is somewhat given and just the the value that you receive is U is Disturbed that's the right model to look at so we'll focus on that and we'll start with um as always lower bounds are proofs about what's possible so you have to say uh what are all possible things so we'll start with formalizing this a bit so our model will be as follows we start with the source message s that's an arbitrary bitstream so remember this just a a string over over that alphabet of arbitrary length and uh we have some Communication

1:25 channel um which will basically just mean that whenever we send something uh any bit could be flipped so instead of s directly we will send the encoded version of s hopefully um adding enough redundancy to correct these flips so instead we'll actually send C so another string that's the same notation as in the compression unit but remember the goal is the opposite we're not trying to store reduce storage space we're trying to add red D see in and then there's uh two functions we need to encode into decode encoding happens at the center decoding happens at the receiver and hopefully they get the same answer all right um that model is overall a bit too uh generic um to make any re interesting statements so instead here we'll focus our attention to block codes and all that means is that instead of sending the entire string here of arbitrary length we only look at M bits at a time that's a block so we'll send K block K bit blocks over uh uh from The Source text but what will send will have more bits namely n um and that's what comes out of the encoder so I'll just write this as C of M here so C is the um uh the output the

2:59 coded text and the function that produces that I hope it's clear from the context in each time whether it's the output or or the function that computes it now of course the way you use this is as you would obviously expect you take the first K bits of your Source message encode that in the first nend bits send those then you go to the next block and the receiver inverts that in the obvious way it takes nend bits that uh they receive then they decode that 2 K bits and then they go on to the next end bits that are received uh this works perfectly if you never ever lose bits if there would be a channel that inserts or deletes bits then uh you might miss what the block boundaries are and then you have to work around problems there uh because we don't look at that a block code is essentially General and there's there's nothing lost by looking at things

4:01 blockwise if I send a block of n Bits anything between zero and n Bits might might be flipped in an actual scenario of course we would assume that it's not so likely that all the bits get flipped uh but we won't get into the probabilities here all that we show is essentially worst case results and we'll make guarantees what the codes can do and if there's more things flipped then they can handle then uh we won't receive the original message and so again the two things we try to do is detect and correct um and the question for a block code then will be how many bits can we flip to tolerate so that we can still detect there is a mes an uh some error happening and how many can we flip so that we can still correct to the original message without

5:03 okay there's one key um key property of codes um that only becomes possible by looking at at these block codes but that will be very useful that's the notion of code distance um so here's here's the first simple observation if I have an encoding that takes two different Source messages and Maps them to the same coded text the same uh same coded block uh that can never work because it's impossible for the decod to uh even without errors to know which which was the source message so the encoding function is always injective it produces different different outputs for different inputs and that means um we can't have uh an arbitrary number of of those so let me be more specific if we design if we Define the set of code words curly c as all the code words you obtains so this is the set of all um n bit strings so it's the set of all

6:22 um of K bits which produces this block then we call that a code word so it's all bit strings that you can obtain from a message when you encode it without any bit

6:44 flips now because uh of this injective property it means for every message I have a different code word so I have um at least as many code words as I have messages and I only have so many because I can't have more there's no others coming around so the size of uh the set of code words will always be the same it's always two to the K because that's the number of different messages I can send but the code words themselves are n Bits long so I have two to the k n bit words or n bit strings and these are my code words now if I Define a coding function like this I can do a generic decoding which is in a way always best possible like that where I say I just decode it to the closest valid code

7:47 word uh we we'll see examples of this later um if if you fix this decoding which is I think a natural thing to do because it assumes makes the assumptions that more errors are less likely so you always decode to the thing that would have resulted in this with the fewest number of bit flips then you can can Define the distance of a code as the minimal distance of um of any two code words and here's this this notion Hamming

8:20 distance that's just the number of positions where these these words uh so in particular if I had just to practice that a little um have a fun example let's do a boring

9:00 example what's the Hamming distance of those two question well we can just look at which which letters are the same so a is the same and the last a is the same but then these two are are swapped but for the hemming code all that matters is that this is different and this is different so it's a Hamming distance two right it's two positions where the letters are not the same Heming distance is only defined if the two strings are the same length so we never have to worry about uh what happens if one string is shorter uh that's not a thing so if I take the hemming distance of all the code words all pairwise distances that's what this minimum is doing it picks any two code words uh I guess um any two code words that are not the same otherwise we get a zero uh then that minimal hemming distance that's called the code distance so far that's just the definition and um I hope the next few slides convince you that it's it's a reasonable definition and the first property that follows from this um comes straight away when um I want to it to uh detect up to D minus one bits of an error so if I I want to be able to

10:30 correctly detect that something went wrong or up to D minus one bits flipped then I need code distance d uh and the reason for that is simple if there were any two code words um I I'll draw them like this I mean they live in some high dimensional discrete space but uh I'll I'll just draw them in the plane as an intuition uh so it's done this is not exactly um to scale in any sense but uh okay and that's not the

11:12 middle uh okay sorry for that picture I should just put that here so what what should these dots mean that's one code um if that is D then uh I can definitely not detect errors where D bits have been flipped not correctly detect because there's a way to get from X to Y by flipping D bits that's what the code distance says the hemming distance between X and Y is D so if I started with x I had a message that produced access code word now my channel flips de bits then I arrive at the code word I would have gotten for message Y and it looks exactly like the code word for message y there's no way for me to know that I actually started with X and had this D bit flips uh and distinguish that from the situation where I started with with code word

12:30 y so there's there's two possible explanations for receiving um um one is we send a message so that that exactly gives you why as a code word it is a code word X and Y are in this curly

13:07 C uh Y is a code word so there is some message that gives you that or other possible alternative Universe M was sent the block for that is X the code word and D bits flipped

13:35 uh that's that's the proof why if you have if you want to detect D minus one bit errors you need distance D you cannot detect D errors uh dbit flipped with the dis code of distance D at least there's one input where it doesn't work that's the first part the second is a little more interesting because that gets closer to um error correcting what the point of the whole unit is and it say a similar statement if you um if you want a certain number of bits to be able to be corrected you need a certain minimal distance and the reason for that let me draw a similar

14:18 picture and we will again have these two situations A and B so we send a message and then FP uh D minus one oh let me let me give that another uh name flip T bits so one option is I started with X and then I somehow went to X Prime which lies in a radius of of uh size d

14:56 t so imagine this these balls are hemming distance circles which are more like weird squares or Cubes but it's nicer to draw it like that uh and then the other situation is we have um a code word

15:22 here second situation is we started from another message and then we flip to T other bits but we end up at the same um same thing that is sent over the wire so we both in both cases end up with X Prime uh that would mean that X Prime also lies in a circle around y

15:55 of uh radius Hing radius DT okay so that means for sure here the Hamming distance of X and Y directly is at most 2 T right because I can get from X to Y by flipping first T bits and then more more T bits maybe some of these flips are at the same positions then the distance is actually smaller but at at most it's two * T if you invert that statement you get the claim here so this shows you if the code has distance 2T or less there's an instance where you can start from two legit messages you get the code words and you flip T bits each and you Collide on the same thing so if a receiver receives X Prime there's no way for them to know whether it was uh whatever whether it was M or M Prime that was originally sent because both have a way by flipping T bits to arrive at the same uh bit pattern okay so if you want to be able to correct T bits you need to have at least 2 t + one as a distance for the code otherwise no chance and if you invert that and write it nicely that's that's the second line so um you need distance D to have D

17:20 minus one half bits and then you can say that's your T now important remark the way these things are formulated they are correct but there are only implications in the One Direction they say if you want a certain number of Errors to be correctable your code definitely needs distance at least so and so but it doesn't tell you that any code with that distance guarantees that you can correct errors that's not necessarily the same thing okay so as they're written there are just implications in the One Direction but we're in this in in the section on Lower bounds so we'll uh we'll make statements like this in this case

18:09 only based on this um based on this observation there's there's two lower bounds that tell you something about specific codes and um uh I want to show you these very briefly uh just because I think they're they're useful um to keep in mind and they're useful thinking patterns so um in this in this case we fix the block length and we'll fix the message length and we fix the code distance three parameters flying around and then we'll have certain statements that mean these parameters have to relate in a certain way okay let's see the first example the Singleton bound it's by a person called Singleton not that it's necessarily a no other meaning of the word it's just the name um um the way it's easy to show is is this inequality but because it's 2 to the k 2 the N minus D minus1 you can just take logs on both sides and then you get this um you can rearrange to this nicer statement which is more intuitive um if you have these three parameters given usually the message length and the code distance is what you want to fix and then you want to know how big do my encoded messages have to be how much redundancy do I have to add

19:27 and this tells you okay if you if you want a message length k and a distance D you at least have to add those up and subtract one that's your that's your minimum code length for sure you definitely can't do better it doesn't promise you that this is doable and it usually isn't let's briefly um prove why this is true this this uh this first part um remember what I said before about the code words every message gives you a different code word injective uh encoding so we can write down all those code words after blow each other and again I'll just sketch this here schematically not for any specific set of

20:19 parameters that keeps going so these are your uh two to the K code now we know more we know that they have distance D so whenever I pick two of these code words I know there's at least K uh D positions where they um where they differ same notation as in the string matching chapter the little little bold is just there's a a distance a difference there between the

21:05 characters so um if we now take the first D+ one bits so in all of those we chop off the first D minus one bits and we now only look at the code words that remain after that line

21:27 okay because I only removed D minus one bits and every pair of code words differed by at least D positions there will be one difference to the right of the bar the worst case would be if they all lie here but then there's at least one more on the right just not enough left that's all that this proof says it's a very simple proof so uh if all of these 2 to the K strings are different afterwards uh then we must must have that the lengths relate like this uh because there's on on this side the strings that remain are n minus D minus one

22:15 right uh in in parentheses the substraction and there's two to that length many different bit strings with that many bits and uh we've just shown that they're all different so there must be enough of these more than two to the C okay that's that's the proof of the Singleton bound that's all there is um and it gives you this nice statement about how these three parameters relate and it's particularly nice because it tells you straight away give me K and d and I'll compute you a lower Bound for the block

22:50 length it's often not tight often you can't uh achieve that bound you can't find a code that that gives you straightly this so there's a second bound which is often a bit more powerful and um indeed we'll see instances where we match exactly that bound so in in a way that bound is best possible or strictest possible that's the Hamming bound um and this is more complicated I can't easily give you a formula that given K and D tells you how big n has to be it still has the same flavor n is bigger than something you can rearrange this right it's the same as saying to D the N is at least 2 to the K and then times this lovely

23:39 sum uh let me let me use this abbreviation T again it's defined below here anyways and I'll remind people that these are binomial coefficients uh you should you should know what these are otherwise ask Wikipedia afterwards so this is also a an inequality of these parameters and it in a way tells you that n should be bigger than this but it's a little less explicit uh why is that

24:15 true that uses again um the picture from before if we have our our balls around a certain code word then we know that the code has distance D so if I go from here to there I need to flip at least D

24:43 bits and uh if you look at how T is chosen is the same as before it's half of that distance but round it down if it's odd um and okay I subtract one and then round it down so I uh I always make it straight strictly smaller than half so the the radius of these balls can be

25:10 T but they don't touch the the balls are disjointed okay that's step one maybe I should put the whole thing in quotes uh the quotes are just because it's not really round um but you can still imagine the set of all all bit strings that have hemming distance at most uh T so um that's what we'll do here we count all the Hamming dist all the the bits that have hemming distance at most T from a given code word and how many are there well if you do this more seriously than in this graphical representation

26:04 um uh okay I don't know if I can can draw this properly let me let me stick with that image there's a few that are just around X at distance one these are flipping one bit okay and I can pick any position in in X so any of the uh n positions I can flip so that gives you the size of this set of of things of at most distance T from X is one for X itself plus n for all the strings that I get from flipping one bit plus n choose two for choosing any two positions to flip two bits and so on so I sum those up f is the number of flip bits and I can flip at most T and these are all disjoint sets so I can all uh sum them

26:59 up so we count this that's the ball size and that's this um okay now um every code word gives you one of one ball of that size namely code words we know the balls are all disjointed so every code word gives you a full ball of code word of of bit strings that are taken we know all the balls are disjointed so if I sum up all the ball sizes number of balls times how big they are I cannot use any any bit string twice so that's that product has to be at most two to the end and that's precisely what's written here so that's a a more delicate bound but it's much more uh tight to what is actually doable to achieve code with a small distance