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

0:00 <Untitled Chapter 1>

0:01 discuss some lower bounds

0:03 in the next subsection i want to discuss some lower bounds these will be mathematical mathematically proven impossibility results showing what is not at all possible with codes it's not always possible to reach these guarantees sometimes these bounds are are weak so they they tell you uh it's not possible with zero bits and you say thanks i was kind of expecting that but you're also convinced that one bit is not enough say [Music] what is happening

0:43 that's not the window i wanted other than that okay back to lower bounds sometimes these bounds are fairly weak but they're at least provably correct and often this is the best we can get they're uh they sometimes uh only go so far and leave a lot uh in the unknown now i made that sound that like the lower bounds are not really useful that is uh in the opposite that's that's not true the lower bounds are very useful um in in giving us thought or building a firm ground on on where to look um it's just in this in this context usually challenging to get matching upper and lower bounds but without further ado let's look at this before we can talk about lower bounds we always need a model for what is possible we need a lower bound as a statement about all algorithms all algorithms need at least such and such so in so many bits to correct errors so that's a statement about all algorithms about all codes in this case so we need to say what is a code you've seen this for sorting you've seen this previously when we discussed lower bounds so here the model is the following we have a stream of bits so the star means it could be any length it's a string of

2:11 unknown length and we communicate across a channel um this is like what i sketched in the last subsection when we discussed when i ask the slider question so any any individual bit might flip from zero to one or one to zero and no other errors occur in particular you could imagine other situations but our assumption here is just that the channel is so that this is not possible for example the channel is strictly timed and you take a signal out of the channel in every time slot and average it or integrate it so that's uh triple e questions that i don't want to get into you convert what you read from the channel in that time slot to a bit either zero one and that's all that is so you never get out of sync time wise but bits can get flipped instead of the original string we send an encoded bit stream and so the sender realizes the encoding from the source to the coded text that's the same terminology as in the compression chapter and the receiver does the inverse and hopefully gets the same source message back

3:31 okay and then the question is what what errors can be detected or corrected and or corrected that's the the abstract model it turns out this is this is too general for for lower bounds that that i know of we'll have to restrict things a little bit further and what we do is we focus on block codes the difference here is here we had an arbitrary length input stream what we do now instead is we assume a single message of a fixed length so we encode k bits at a time of course you can take the stream and break it up into blocks of length k and then transmit that individually that's what applications do

4:21 for the theoretical model we start with a message of k bits that's the message length and we encode each message separately uh in with a code word and that one has n bits and of course um we know we have to add some bits uh of redundancy the block length is bigger than the the message link okay so we restrict our attention to one block at a time that makes it a little more convenient to work with

4:45 restrict our attention to one block at a time

4:57 now any number between zero and n bits might get flipped in the channel and we have to think about what we can do um if up to everything can be flipped there's no way we can detect this so we will only be able to detect a certain number of bit flips or correct a certain number of bit flips

5:16 and how do we detect that something went wrong how do we detect errors we can usually find that what we receive is not a valid code word it's not c of m for some actual message if we find that we know something has happened and error correction goes a little further can we somehow go from what we receive to a closest valid code word and how many how many bits can i recover from this if they were flipped that's the setup that's the model um let me switch to the the q a so if you have if you have questions about this pop them in the q a but so far so good um we start with with messages of k bits we encode them with n bits bit more than k what can we do with it

6:17 it turns out a key a key number for a code is the so-called code distance and to define that we need a little bit of terminology first of all a block code is just a mapping that takes any message and transforms it into some code word and it has to be injective if i give it two different messages it better had produce two different code words otherwise there's no way i can decode that correctly right so injective just means it produces different codes for different messages

6:56 then we define this curly c as the set of all code words in that code so that's well this notation i don't know if this is uh something you've seen in math that's just a lifting that's the uh range of a function so it's all um blocks in 0 1 to the n

7:19 for which there exists a message in 0 1 to the k so that that's supposed to be curly so that this block is what comes out of the message if you apply the code that is what this what this notation means a function applied to a set is the set of all values you can get if you insert the elements from the inner set into the function this is a subset of all the n-bit bit strings by definition and just because of the injective property the size of this is always 2 to the k so we have 2 to the k valid code words but in a in a bigger universe of two to the n n bit strings

8:18 and then we can we can say that uh decoding can always just mean finding the closest valid code word so i'm i'm starting with an arbitrary 2n bit string and i try to find what's the fewest number of bits that i flip that i have to flip so that i end up with a valid code word one in in this set courtesy okay so graphically you can think about this as follows if there's um if there's a code word c here then there might be uh other valid other other n bits bit strings so x is just

8:24 starting with an arbitrary 2n bit string

9:01 some n bit bit string but it's not in curly c then you want to find a way to map that to a valid c so this one here is is a valid one c is in the code words and you want to find a way

9:25 to map that um to this to map this uh to the closest valid thing so if the other ones are further away if the next c is here you find that the distance here is bigger so you want to map it to this one okay that's that's what's meant with uh decoding is finding the the closest valid code word

9:53 define the distance of the code

9:55 and then we can define the distance of the code as follows this little d is the smallest hamming distance of any two code words if for this code so formally you can write this as the minimum for any x and y in the set of code words and then take their hamming distance remember hamming distance is just counting how many bits differ very simple thing okay that's a simple definition but uh it has it has very nice consequences for codes namely if a code has distance d it can detect all errors with up to d minus 1 bit flips

10:45 let's try that picture again so we have a code c nope it's not red we have a code c here and now uh the distance is d so that means within distance d

11:05 there is no other code word so there cannot be any other c then the closest can be at distance d but if i go only to d minus 1 there's no other code word in here so whenever i have a valid code word and flip up to d minus 1 bits i end up somewhere in this circle

11:29 and so i know something has gone wrong because this is not a valid code word so i detect that something went wrong that's that part now uh how about correcting the error if i take the same example here's my c if i were to draw a circle with d minus 1 around this there would be a big overlap between those circles and for correction we have to map to the to the closest code word now if i have something in here

12:09 it's not clear whether i should it should map it to this one or to this one and i might make the wrong decision but if i take a smaller radius just d minus one half then let's call this t

12:36 so i can make a radius of a ball of size t then i'm guaranteed that these don't overlap so the green circles don't overlap and any of these points inside the green circle can uniquely be mapped to its code in the center

13:00 whereas this blue point here it's too far away from any valid code words to be sure which one it was before all those bits got twisted okay i hope that picture makes it intuitive why this is the case it's essentially drawing circles around code words in the space of hamming distance but it behaves for all intents and purposes it behaves the same as if this was euclidean distance where a circle is is a normal geometric circle

13:38 prove lower bounds on the block length

13:39 now we can use these observations to prove lower bounds on the block length so we can fix a certain message length k and show what is the smallest n the smallest block length that can achieve a correction of three bits okay because i can use this mapping to translate between how many bits do i want to detect correct bit flips do i want to detect or correct into a code distance for example if i want to detect a single bit error i definitely need at least distance two right and if i want to correct one bit so maybe this is something that's worth writing down

15:09 because then three minus one half is still one rounded down is still one at least okay so uh for proving lower bounds we still need an additional argument so we know what distance for codes to look for but how can we make that into an argument for the size of blocks i'll show you two such lower bounds and the first one is is called the singleton bound by a person called singleton and it's very it's very simple which is fitting the name it says uh 2 to the k has to be smaller than 2 to the n minus d minus 1 where d is the the code distance so that means no matter what you do you need a block of at least k plus d minus 1. so you have to add at least d minus one bits to your code to get um a certain uh error detection

15:22 proving lower bounds

16:06 add at least d minus one bits to your code

16:17 well to get uh now this is uh the distance you need to add at least d minus one bits to your message if you want distance d okay before we discuss the proof let's apply it to a simple case say we have uh 100 bits like in our example before we want distance at least two to detect one bit errors so that says n must be at least 101. so we have to add at least one bit that's not saying that it's possible with one bit necessarily but it says it's not possible with not adding anything thanks not very useful but it's a valid lower bound if we make d little bigger then it becomes a little more a little more telling now how can we prove this bounds suppose we write all the two to the k code words

17:34 they all differ in at least d positions so whenever i take two i can find d positions where they are different but of course these positions can be different between any pair

17:48 now what i'll do is i'll take away the first d minus 1 positions and just look at the remaining code words because i only take d minus 1 away i still have at least one of the mistake positions the differences still in the remaining one so even if i delete the first d minus one bits the remaining code words are still all distinct they might only differ in one bit but they're all different but they're only two to the n minus d minus one such shorter subs such shorter bit strings just by counting and that's all the bounce says it says if i want to have distance d initially then 2 to the k can be at most this because that's what's left after deleting the first d minus 1 bits it's a very simple argument and a very simple bound it's also fairly weak bound but it's uh occasionally useful because it uh it can nicely be rewritten in terms of a bound for n and not just an inequality that we have to check by inserting numbers the second lower bound is the hamming bound and it has a bit more of a more complicated form so this these are binomial coefficients read about those on wikipedia if you've never heard about them

19:12 but without discussing the details the idea is to count how many things we cover with balls of a certain on off a certain size so we we have two to the k code words and each of these code words is a center of a circle and i take again this d minus one half so i have these non-overlapping circles

19:52 okay and one more i wanted to have this in red and the circle around it so this is with length t as given here so we know the circles don't overlap they don't touch there's no element that they share so that means if i count how many elements there are in this circle

20:30 and that's what's done here i'm including the red one and i multiply the size of of this ball with the number of balls i should be able to uh i get a certain number of of bit strings and that cannot be more than the universe otherwise they would have to overlap if they don't overlap they have to all fit into the space of two to the n bit strings i have so many balls this is the size of each ball this thing so that has to be at most to the n and rearranging for 2 to the k gives you the the hamming bound so this is again a fairly a fairly simple bound it's fairly simple argument to come up with the bound this requires a bit of counting to count how many green balls there are you basically count in layers that's the number of ways you can flip f bits out of n it's not not deep combinatorics but i don't want to get into the details of this okay and uh we'll we'll revisit those later but these are these are two bounds uh this one gives you a nice expression your code has to be at least that long this one only tells you if you insert n k and d

21:44 and this bound is violated good luck finding such a code it doesn't exist if you insert your n k d and it comes out true it says this might be possible it doesn't guarantee that it is it's only a lower bound