Video 8-2: §8.2 Lower bounds for error correcting codes

0:00 <Untitled Chapter 1>

0:02 Lower Bounds

0:02 in the next section i want to look at lower bounds so these are mathematical proofs that certain qualities of these codes are not possible and we will see that in this in this case in some scenarios we can reach these lower bounds with con with concrete constructions for codes and in other scenarios it's quite open and there is still i mean a research question if it's possible to reach these lower bounds or not and if it's possible how but let's first see what is not possible and for that we have to take a step back and formalize the question a little bit every lower bound needs a specific scenario in which it holds and the same same is true in this case the model here is we want to send a message

0:57 so it's just a sequence of bits remember the the zero one to the star that means a string of arbitrary length i want to send this over some communication channel

1:08 the model for the channel is it can flip a bit but no other errors occur instead of sending the original string we're allowed to change it and basically send something entirely different we send a message c instead of s where the encoder produces s c from s and the receiver hopefully gets s back from c but of course what the decoder receives is not the same c as we put in at the center side because the channel might twist some bits

1:41 Block Codes

1:41 we'll restrict our attention here to block codes and that simply means um we break up the message into blocks of a fixed number of of bits i don't think this is a very severe restriction but it makes the makes the model more concrete so the parameters that you should keep in mind this will occur several times on the next slides is k for the message length so k is the number of bits you want to send and n is the number of bits you actually do send over the channel so that's the length of the message we already argued that we probably need more bits in the sending part than we really want to have in the message um and yeah so all the analysis and all the all the codes uh that i know of uh okay i'll take that back all the codes that we look at are block wise there are other codes uh but they're not so fundamentally different that i want to extend the model and the lower bounds are much cleaner for this one too

2:50 remember in principle any number between no and all bits can be flipped we won't get much into the probabilities of these things happening if you want we can put a certain probability to each bit flip and assume they're all independent and happening with the same probability we won't get into the the probability side of things we'll just ask what types of errors can we tolerate how many flips can we detect reliably and how many flip bits can we correct without re-transmitting the message okay that's that's the two concrete questions and so correct here always means i want to get the exact same message back and we'll ask how many bits are can be flipped before that's no longer possible now if i gave you this question to ponder a bit you would probably come up relatively quickly with the idea that [Music] these these code words these what i send over the channel there are only two to the k different messages and each of these messages is somehow turned into a code into what i send over the channel so i have two to the n bits but only two to the k different messages so there's a smaller set of messages

4:19 and okay did i call these block codes or just codes c doesn't have any name just c of m let's call it just the the code words then i have much a much smaller universe of messages and every message here is mapped to some code word here but it means there's many ministers code many there are many code words left after i assign code words to all the messages that's the whole idea of having redundancy

4:55 so what we what we definitely don't want is two mapping to the same that cannot possibly work for decoding it right if you have two things mapped to the same thing you can't invert it with a function so this is not allowed so what we call this mathematically is an injective function from the set of of messages to the set of code words and that's the function c that the encoder uses

5:15 Injective Function

5:30 and then on the on the right hand side if i take all of these together where they point so this should really go somewhere else right if i take all those then i get a certain subset of these code words and that's that's this set calligraphic c that's all the code words i can get if i put in all the messages and that's not all possible code words more specifically here this is spelled out again i think i said this already in this model we can make the decoder conceptually very simple and for the lower bounds that's good enough for sure we could say if i receive a code word i just if i receive any n-bit string i find the closest code word and that code word stands for some message and that's the message i output okay

6:28 and with that convention a key property of a code is this distance of the code so we look at all those code words and they live in this space of n dimension and long bit vectors

6:50 and then i take the smallest distance between any of these and the distance is the hamming distance remember we've talked about that in unit 6 that's just the number of positions where the two strings differ

7:14 so we ask for any pair of code words how many bits do you have that are not in common and then we take the smallest of this of these numbers over all pairs of code words so you can imagine you put a ball around each of these code words of of size d

7:36 and if you do that these balls are not allowed to overlap and for some pair they will touch but they're not allowed to overlap i should say this is a d half right if they are not supposed to overlap the other formulation is it's size d then no code word should be contained in the ball i think the picture with with d half is is what we'll need later so let's let's use that

8:15 and you can draw some immediate conclusions from this if the distance of a code is d the best thing we can hope for is correcting d minus one errors because if i have two code words that are a distance d then i could have a message that gives me one code word i flip d bits and i end up with a different code word well then that other different code word is indistinguishable from what i would have gotten if i started with the other message so i can't distinguish those two cases anymore so i definitely need a distance d if i want to detect d minus one bits of error if you want to turn it the other way around right then if you want to detect want to correct want to detect kbit flips you need at least k plus 1 as the code distance and similarly if you want to correct things

9:19 then think about this decoder it finds the closest code word so the worst case here is you have some message that's here and you have some code words and they're at equal distance from from the message

9:47 so the decoder has to pick one of the two so say it it maps the message to this one now uh that will correct some error some number of errors but at the point where this message is at the same distance from these two code words it could have been either of the two so we have to pick a code distance that's big enough so that this never happens that every point in the space of possible received n-bit strings is closest to one of the code words and then the again this is the picture of the of the balls from before

10:31 if you draw these these balls around all the code words and you make sure that each point in the space is is closest to one of those code words then the radius of these balls that gives you the number of bits you can correct because whenever you have something that's just so many bits away from a code word you can find the unique code word that it is mapped to

10:58 and so if the code has distance d the the best you can do is require d minus one half rounding down then if the code has distance d that balls never touch if you take radius d minus one half okay

11:24 so maybe i can add this to the picture if the distance between those two then the safe balls end here so we have to exclude the case that the message can be at equal distance we go one smaller than we have balls that don't overlap and every message is is mapped to unique code word

11:59 now this doesn't doesn't say that this is possible it's just if you want to correct so many bits you will need a certain radius you will need a certain code distance

12:15 based on these ideas we can prove to lower bounds and the first one is called the the singleton bound i think these these lower bounds are a bit more concrete to understand than the previous slide what this bound says is uh that 2 to the k must be smaller than 2 to the n minus d minus 1 if you want to correct d bit so if you have

12:50 what is d here it's the distance of the code these are bounds that say if you want a code with a certain distance then uh how much redundancy do you have to add to your message so the the way to read these is the second part that's the pro the part that we will prove and if you take this inequality take the logarithm on both sides and rearrange you get the right hand side what it says is if if you have messages of length k and you want the code of distance d then you definitely need to put the message size

13:54 and the reason for this inequality is we have to decay code words these are bit strings of length n and for each pair of these there must be say when we have distance three for each of pair of these there must be three positions where they differ that's the definition of the code distance if i take any pair of code words there's at least three positions where they don't agree and so this is true for all of them

14:44 we don't know which positions these are and they might differ and this is also true for the first and third and so on well the singleton bound now says the proof says if we delete the first d minus one of these bits

15:14 that leaves you with code words that are uh not as long they only have uh n minus d plus one bits but definitely they also all still differ because every pair of these they must still have a position where they don't agree that is not among the first d minus one just because there must be d positions and we only remove d minus one of the coordinates

15:43 so we went from having code words that are at hamming distance at least d to shorter strings about which we only know that they're all different but if they're all different we know um that uh we can only have 2 to the n minus d minus 1 of them this that's the length and the remaining length of this is n minus d minus 1

16:12 and if i take 2 to the length that's the number of such bit strings so there's no way i can squeeze in more code words of length n than this and if my message length is k that says i have two decay different messages i need at least one code word per message okay so the number of code words must be bigger than the number of messages otherwise i lose the injectivity so that means this needs to be true so it's a it's a way if you start with a certain message length and you want a certain code distance you need to add at least so many bits

16:58 the singleton bound is not usually achievable so this is a true lower bound you need at least that many extra bits but you usually need more than that there's a second bound the hamming bound that is often a bit um is the second bound is often a bit more useful in terms of giving strict results unfortunately the inequality we prove is a little more complicated and so it doesn't have a very nice way to translate it into an inequality for n the only thing you can do if you have a message length k that you would like to support and you have a code distance d that you would like to achieve then you can guess an n plug it in and if it doesn't fulfill this inequality you know it's not possible okay that's the way to use this

17:50 maybe i should put this here so you know k and d that's what you want from your application then the bound tells you if it's at all thinkable and the way to read this potentially possible is if the bound says it's impossible it is impossible if the bound says it is not impossible it might still be impossible it might not just not be something that this bound shows to be impossible

18:34 how can we prove this bound the argument will be similar we want to argue that if you have a certain code distance there's not there's not more code words that you can squeeze into the space than a certain number and that number has to be at least as big as the number of messages otherwise you lose injectivity again this time this time we look at balls around bit strings same idea as before so we use sets of bit strings that have a hamming distance at most a certain number from a code word

19:14 and we will count all those and the distance that we use is is t d minus one half that's exactly the distance i argued before if you have um some string that's at this distance at most t from a code word in a code of distance d you can map it uniquely to that code word

19:36 what that means is if you take all those balls for each of the code words you take each code word put the ball around it of distance t then all those balls don't overlap there's no no bit string that belongs to two balls and that means if i take the size of these balls times the number of balls i need the number of messages i have to represent i only count each bit vector once and i only have two to the n so if if what i require the number of balls times the size of the ball if that's more than there are bit strings in my universe i'm out of luck

20:19 okay that's that's the idea behind this so what's left is to count these bit strings of a certain distance and that comes down to this formula so we have

20:43 and then we can look at different distances for distance 0 there's only exactly this code word itself right for distance one i can choose exactly one position where i flip a bit so i have if that code word has length n i have n choices to flip a bit

21:26 and in general if i have d equals f i have to pick f positions out of n to flip and that's counted by these binomial coefficients and choose f that's exactly the number of subsets of size f out of an n element set

21:44 if you're rusty in your combinatorics we don't really need this here so you can just use this as a magic formula that both from alpha can evaluate for you it's called the binomial coefficient if you have seen this i think as if you will have seen this at some stage then you might remember and so what this what this sum here does is just summing up all the vectors of a certain length of a certain distance you start with distance zero and you go up to this distance t and you sum up how many choices you have to flip away from your code word okay so that's where this inequality comes from to the k times the ball size times this must be less than two to the n and you just rearrange then you get the hamming bound

22:29 so again let me repeat this this part here for both of these bounds the way you use them is you have to fix the message length and you have to fix the distance of the code that you want and remember if you want to correct d minus 1 bits if you want to detect d minus 1 bit flips you need distance d if you want to correct d minus one half rounded down bits you need at least distance d so if you know you want to correct three bit errors you you can work out what the minimum distance is like so these bounds by plugging in all these values can tell you if that's at all thinkable or not