Transcription
Hi everyone, um, welcome back. Uh, lecture two. So today we will talk about prefix-free codes and Kraft's inequality, which we will learn about shortly. Right, so let's start with the quiz from last time, uh, which will also function as a recap of the last lecture. Okay, so we want to design fixed codes for an alphabet of size 9. And the first question was, what is the length in bits per symbol for such a code? Right, and in last class, we saw this formula that if your alphabet is like this, X, then the bits per symbol is log base 2, the, the size of the alphabet, the ceiling of that. So, in simple words, basically you find the nearest power of two which is bigger than your size. Right, so, so 9 lies between 8 and 16. So you take 16, you take like log base 2 of 16, which is 4. And so 4 is the number of bits you need if you are going to represent this in a, uh, fixed-length code. Is everybody okay with that? I think most of you got this one right, so that's good.
Uh, okay, so one thing you will immediately observe is like, if you, if your alphabet has size 8, then you're spending log 8 equal to 3, right? If it's 16, you are spending log 16, which is 4. So powers of two, this seems to be working really nicely. But for 9, you see like clearly like you want this, right? This is what you want. This is somewhere between 3 and 4. But, but this is not what you got. You got 4, which just seems like suboptimal. So this question was trying to introduce to you to one idea to make it better, right? So the idea is simple: rather than encoding one symbol at a time, you encode symbols in blocks of two. Right, so, so if your alphabet was like A, B, C, D up to like H, I, right? So the original code, what you would do is like A becomes 000, B becomes 0001, so on, right? Up to I. Now, what you will do is you will create a new code which is like AA, AC, AD, dot dot dot, right? Up to II. So, so effectively, what you're doing is you're creating an alphabet of size 81, right? You are creating the product alphabet of these two. And then we asked, what is the length in bits per symbol for this code, like a fixed-length code applied on applied on blocks of two? Um, here there were mistakes both on our side because we made a typo in the next question, uh, and, and which led to some of the students getting this wrong. But I, I think you got the concept right. So, so again, we use the same trick. We know that 81 is less than or equal to 128 and greater than 64. Right? This is 2^7, this is 2^6. So really, if you calculate this, this will be 7. So many of you got got it correct that you need 7 bits to represent this pair, right? So AA becomes like 7 bits. So it just becomes 0000000 and then so on for the other guys. However, the question we asked was bits per symbol, not bits per block. So here the bits per symbol is, each block has two symbols, right? So just to make it very clear, block is like AA, and symbol is like A, right? So each symbol, and then you have a block of two. Um, so the length in bits per symbol is this divided by two, which is this divided by two, which is 3.5. Yeah. Uh, and those who wrote 7, we will still give you marks because we, we made a mistake in the next part where, so let me read the question. So now the alphabet size is 81 because we will be encoding pairs of symbols together. So the length in bits per, so this was the typo we made. It should be bits per block is log 81, 7. However, we are encoding blocks of two symbols. So the length in bits per symbol is this divided by 2, 3.5. And did working in blocks of two give a better compression ratio? And I think most of you got it right. The answer is yes, right? So we, we went from 4 bits per base, uh, 4 bits per symbol when we were encoding them one at a time versus like 3.5. I wanted to do this. Can, can someone be kind and tell me what is log 9 base 2? I just want to see how close we got to that. Okay, yeah, it's, it's 9 is very close to 8, right? So we assume it's only a little bit above log, log 8, which is 3. So, so we got to 3.5. We didn't quite get to log 9. Can somebody suggest how I can get even closer to to this many bits per symbol? Larger. Yeah, very good. Good. The, the answer was larger blocks. Right? Simple idea. Instead of doing two at a time, you do three at a time. So you have like 9 cubed possibilities and so on. And you can keep going. And you will, you can show actually, uh, if you, if you work, just do some math, that you will actually eventually convert to 3.17. And we will see this sort of scheme and even better ideas to achieve this because you can see that this is not particularly optimal. Like your alphabet is just growing exponentially as you make your block bigger and bigger. So we will come back to this. For now, I guess just notice that it, you can do better than fixed-length codes by using some clever ideas. Okay. And any questions on this, this, this first question? Okay. Second one is very simple, right? This is the sort of quiz question. Like you listen in class and you solve it like in a second, basically. So, yeah, I think everybody saw got this right, but let me quickly do it. So the length, so the question is, you are given a random sequence which is sampled from some probability distribution, and you, you encode it with this code. You want to compute the expected code length, right? Which is our usual, like, metric for, uh, determining the goodness of a code. So the length of each codeword, you can just write 1, 2, 2. And then you can calculate the expectation. This is just making sure you remember your probability. So PA * length of A + PB * length of B + PC * length of C, which is 1 + 3 * 2. Okay, 1.5. I hope I got it right. Bits per symbol, right? I find it useful to always write the unit, bits per symbol, because that way you don't make mistakes like the mistake that we made in the question. Um, yeah. Okay. Uh, any questions on this? Okay, good.
Okay, I gave an exercise in the last class to decode this. Was anybody able to decode? So this was the code we gave, and I, I wrote down a sort of encoded sequence, and I wanted you to get back to the original sequence. Uh, I see a couple of answers. Anybody else? Uh, okay, let me ask you for the first, and then I will ask you for the second. Uh, so what's the first symbol, first decoded symbol? So the answer given is D. And why is it D? Because the only that starts with one and has another one and has another one, right? And, and, and the answer is that like the reason why, why it can only be D, right? Because you have a codeword which is like 111. Like if it was A, then it must have a zero somewhere. And if it is B, then 10, so on, right? So there is only one possibility, really. And, and we'll come back to this later in the lecture. The next one. Yes, the next one would be like C. And then like, we basically can just keep reading each letter until we get to like a zero. Ah, that, that's a good way of thinking, right? Like, so, so the answer was, you just keep going until you hit a zero because of the particular way this code is structured, right? When you hit a zero, if you have like three ones in a row without a zero, then you know it's a D, right? If you have two ones and then a zero, then you know it's a C, and so on. Uh, let me decode a couple now. So after this, you have one. So when, when you see a one, you know it's either B, C, or D, right? It can't be A. So that's eliminated. And then you see a zero. So you imagine, you know, it has to be a B, because if, if it was a C, then it will have a 11, and D also will have a 11. So it has to be a B. Sorry. And then you see a zero, and you know only one codeword starts with a zero, which is an A. And so on, right? Uh, I hope you decoded this at home, but, but, but I hope you get the gist that, even if you have a variable-length code, right? This was a variable-length code, and last lecture we had some concerns from students that how will you decode it, but, but you can see like there are variable-length, variable-length codes that can be decoded, and this is one example. And we, we'll look at it in more detail and like characterize when, when exactly can you decode these things. Um, any, any questions on this? Uh, anybody who wasn't able to decode and doesn't fully understand the process right now? Okay, okay. And we will go through, like, an actual algorithm for those who like to think in that way.
Right, okay. So the outline for today. No, no sense going through the list. Like, you will get, we'll get to them when we get to them. But the first item is, we will define what do we mean by lossless compression in, in this context. And then we'll discuss two specific categories of codes.
[Applause]
So, yep, okay. So I, I, I will, I will make a, I will write down a few codes and I will ask you whether they are lossless or not. Okay. Is this lossless? Uh, I hear no. Uh, why is it not lossless? What? Yeah, because of the ambiguity in the sense that A and B have the same encoding. So clearly, if, if you see a zero, like, you only see zeros, so you can never tell whether A or B was transmitted, right? So this is not lossless. This is very much not lossless. Okay. Now, this one is, is this lossless? Is it lossless or not? It is. Sorry, it's not. Anybody else who has a differing opinion? What do we mean by lossless, I guess, right? Like, if you're, if you know you're only going to ever send like one symbol, then this is lossless, right? If you see one zero, then it's an A. If you see two zeros, then it's a B, right? So in that sense, it is lossless. But very rarely do you want to send only one symbol. Most often, you want to send a sequence of symbols. Uh, and in that context, if you see like, AA will encode to 00, B will also encode to 00. So if you receive a 00, you don't know whether the original person sent AA or AB. Uh, right? So, so in that sense, it's not lossless. But, but, but you already start saying that like the definition of lossless is not obvious, right? Like, you, you need to define it carefully, otherwise it's not clear what do you mean when you say it's a lossless code. Um, yeah, so, so let's define it. Yeah.
Okay, so we will define something called a uniquely decodable code, and it's a very simple definition. Um, so a code is uniquely decodable if no two input sequences, say Xn, Ym, where M and N are greater than or equal to 1, are encoded to the same code, or I guess let's call it same output. Are we happy with the definition? Any question on this definition? Right. So with this definition, if we go back, or let me draw that again. Uh, so like this code that we saw, A was 0, B was 00, is not uniquely decodable.
[Music]
Before we move on, so, so, so when we talk, for example, right? We have a sequence of words, right? And, and sometimes you have two words such that like they are individually words, but when you join them, that's another word. That's possible in English, for example. So when you talk, right? And you talk to someone, how does the other person know when does the word end and when does the other word start? Forget about codes for a second, just like very generally. Spaces. You have spaces. Very good. Very good, right? So often times, like this is one way of thinking about it, right? Because the way we are thinking about it is, when you have AA, AA is encoded to 00 without any gap, right? It's just zero followed by zero. There isn't a gap. B is also 00, no gaps anywhere. So, so that, that's like, that's the sort of setting where we are thinking about these uniquely decodable codes. And most often, when you're working in any real application today with, with computers and so on, uh, you don't, you can't afford gaps because you have a binary alphabet, you're working with, you have zero or you have one, right? You don't have a third symbol to signify that, okay, like now one code has, one codeword has ended, now we will pause for a sec. In the old days, some of you might have heard of Morse code. So this was used in the telegraph, which was the only mode of like intercontinental communication for a long period. And even like during my dad's time, like that was the way people sent fast messages in India. So, so Morse code is comprised of dots and dashes. So it's a way to like, you, you, you can represent any letter or any number in this code, and you have a dot or you have a dash. So let's look at the code and then we'll come back. You can see this, right? Yeah. So for example, E is a dot. S is a dot dot dot. Q is a dash dash dot dash, right? So you just send a sequence of these, and on the other side, just listening to do dash, the other person can decode it. Uh, so this was the Morse code, and how did the Morse code denote the separation? So, so I, I guess if you look at this, you will immediately see that you have E, you have A, and you have T. Right? If you look at these three, so E followed by A followed by T is a dot followed by a dash. But an A is also a dot followed by a dash. Right? So Morse code, in our sense, is not uniquely decodable, right? So this is not uniquely decodable in the way we think about it. But clearly, it was used for communication for a long period. And why is that? Because between letters, you would just put a space. Like you will pause, you will not send anything for a bit, and then you will start sending the next letter, right? And then the receiver would know how to, like, I guess, initially some human used to do it, and then they made machines. But, but, but the idea is that in different types of communication systems, you can have different ways of doing things, right? Like for us, like this, this is very important. This is what we'll be working with, and this is how most modern, uh, compression algorithms work. But there are other systems also. So you should be aware. Putting a comma after every letter, in a way.
Okay, anything interesting somebody observes? Like anything that we saw in the last class and you see reflected here? Like look at the length of the different codewords. Anybody wants to, like, what do you see here? Anything interesting with the letters and which letters are getting shorter codes and which letters are getting longer codes? Go ahead. Yeah, so, so, um, the vowels are shorter. That's one suggestion. And that's true. E is a single dot. I is a dot dot. Some of the vowels are a bit longer, like U is a dot dot dash. But you see T is very short, right? And, and if you study, like, the frequency of letters in English, you will see that E and T are the two most commonly used, uh, letters, right? So the vowels are shorter because they are also usually very commonly used. Um, so even in the Morse code, in those old days, they knew that for more frequently used letters, you should use a shorter symbol, so that your, your overall, like, message becomes shorter. Uh, right? So that, that's just, I think, an interesting fact. Um, any questions with this? Go back to the previous. This one? Yeah, yeah, yeah. Ah, so there are just two input sequences, right? So, uh, if we were to give an example, right, here, if you take X2, so which is like two tuples, S of X1, X2, which is like A, A, or you to Y, or you take Y1, which is just a single input, which is B, then you can see that the, like the encoding of X2 is the same as the encoding of Y1, which is 00. Uh, yeah, so that, that's what we meant. Sorry, if the notation is new, I think, uh, I will define it more properly in the next part, but you will also get used to it. But yeah, that, that's just a T. X2 or Xn. So we are saying that like it's not like N and M, no, don't need to be the same, right? Any two sequences with different lengths, they should never map to the same, same output, right? It'd be unique. Like, given the output, you, you're not able to decode, you also know how many input symbols there are. So, so it's a very strict property in that. Is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options, really. Um, is that clear? Okay.
So we will not talk about uniquely decodable codes for the rest of the class. You will see a question in the homework, and I will explain later why, why we don't talk about these. It's a very powerful property, but you don't really need this very powerful property. We'll see, see a much smaller class of codes which is very, very easy to deal with, and we'll just stick to those. So, so that's our next topic. Um, yeah, but there will be a homework question where you will look at these and do some proofs with this. Okay, let me find the old code we had. Yeah, don't set up for. So, so this is a proposed decoding algorithm for, for this code. Let, let me talk through this in words. So you start with an empty, you, you have a variable called C, which is like storing your sort of, um, code, like the encoding. You start with empty. You look at the next bit, you add it to C. You check if C is in the table, right? So if C is in one of these four entries, if C is there, you decode, and then you set C again to like empty. And if C is not in the table, you just continue and then look for the next bit, and you keep adding the bit, right? So very simple algorithm, linear time, and so on. I will do an example, but, uh, before that, anybody, do people like generally understand the idea behind the thing? Okay, let me do an example. I think that should help. Yeah. And as Pulkit said, like apologies if you have done information theory and all this, you know, I think, uh, yeah, probably this lecture and the next lecture will be mostly recap for the info theory experts. But after that, you will see, uh, a lot of new material. Okay. So, so let's do an example for the same code. Um, so, so we have, let's say, 01100Z, something. Okay. So we do it step by step, right? First step, C is equal to zero. Sorry, first step, C is nothing, so null. Okay. Then C is zero. You decode A, right? Because, because you immediately see that Z is in this table here. So you decode. This is your codeword. You're trying to decode. Then C again becomes empty. Then you put C equal to 1. You can't decode here. There is no codeword which is 1. Then you see C is 11. Again, there is no codeword which is 11. Then you see C is 1110. And here you can decode C. Okay, can somebody help me with the next, next few steps? What happens next in this? So after I decode C, what, what is the value of my variable C? Yeah, C becomes empty again, right? After you decode, you reset C. Okay, next step. Uh, so we, we are here, basically. We, next symbol is this one. Yeah. So next step, you insert zero in C, right? Are we ready to decode? Yeah, yeah. Why are we ready to decode? Because, because zero is one of the codewords, right? Zero is the encoding of A. So you immediately decode A, and so on. Let's not do it too much. Okay.
Um, so let's think about this. First of all, any confusion with this? Are we happy with the decoding? Uh, right. Why do we think this works? What is the property of the code that makes this possible? Basically, like no code is like the prefix at the beginning of any other. Yeah. So the answer given by student, which is the correct answer, is that no codeword is a prefix of another codeword. So you see, zero is not a prefix of any of these. So as soon as you see a zero, you immediately know that it has to be A, because there is no other codeword that starts with a zero, right? B, 1Z, 1Z is not a prefix of any of the other guys. So as soon as you see a 1Z, you know it has to be a B. It can't be C, it can't be D, it can't be A. Uh, and so on for the other ones. So let me define it. Uh, so there are a few different names for some historical reasons, I assume. So they are called prefix codes. They are called prefix-free codes. They're also called instantaneous codes. Okay, instantaneous codes, right? So no codeword is a prefix of another codeword. Right. Stop me if you don't follow. Um, why are they called instantaneous? We, we just saw that property, right? As we were trying to decode, as soon as we saw the symbol, we were able to decode it like instantly, right? We saw zero, we decoded A. We saw 1110, we decoded C. You don't need to look ahead. Right? You can do it in a more streaming way. As your symbols are, as your bits are coming in, you immediately able to decode. That's why it's called instantaneous code. Um, why is it called prefix-free code? Just the definition. And, yeah, why is it called prefix codes? I think just people didn't want to write prefix-free all the time. Um, okay. Uh, so just a simple property. Prefix-free codes are uniquely decodable, right? So the property we saw earlier, right? The uniquely decodable property, that no two sequences map to the same same code. Prefix-free codes satisfy that condition. Can somebody intuitively describe why? We won't do a formal proof of this, but, uh, just intuitively, can somebody suggest like why, why are prefix-free codes uniquely decodable? Why are they lossless? When you go through the algorithm and you find C in the table, you are 100% guaranteed that it's not just a part of another codeword. It's that it is going to be exactly, or exactly. Yeah, yeah, very good. Yeah. So, so the answer was, as you're doing the decoding, right? And you decode 110 to C, you know it has to be C. There's no other option, really, right? Uh, so in a way, the decoding algorithm proves that it's decodable uniquely, right? There is that decoding algorithm, and if you like, if you have done math, you will want to be more formal, and we will leave you to read the textbook if you want, like, very formal proofs. But, but, but it's intuitively correct, and you just like write that in math, and you get the actual proof. But they are uniquely decodable because there is a decoding algorithm, which there is no confusion. Like, you start from the beginning and you can just decode the sequence. There are no options,
The next, like, uh, they come very close to the optimal, but they are not necessarily optimal. Next Monday, we'll learn about the code which is optimal. And, uh, but for now, I guess we will live with what we have got. And this is the code. Um, okay.
So now show that this construction. So if you like, if you read this construction carefully, what you will observe is, step one is obvious. There's nothing there. Step two is obvious. You can always sort things. Step three depends on the fact that like, when you're trying to assign a leaf, there should be a leaf available. If there is no leaf available, then, then, then you can't assign anything, right? So, actually, if you have done like greedy algorithms, like if you have done like the minimum spanning tree or something, you always need to prove that the next greedy step, step is indeed possible, right? So, so really the thing to prove here, which we'll prove now, it's like an inductive proof. So we need to, we need to prove that this construction always works. So we need to prove a leaf at LX depth is always available. Yeah, um, always available without, uh, violating like the prefix condition.
Okay, so let me go through the proof. Um, and stop me if you have questions. If you have not done proofs before, don't worry too much. Like, only a very small part of the course hinges on this. Uh, I hope you find the proof intuitive. It's like, it's not like one of those proofs where suddenly you get the result and you have no idea what happened. Uh, it's very like obvious in some ways. Okay, so proof. So, so if we like take all the things, we take this sum. This sum is 2 power. We know that the length is log base 2 of 1 / P of X. If you have forgotten, forgotten the properties of logs, now is a good time to refresh. Now you know that the ceiling of something is bigger than the original. Like, ceiling of X is bigger than, bigger than or equal to the, bigger than or equal to X. So, minus ceiling of X will be smaller than or equal to X. So after a bunch of, after like two steps basically, you can convert this to, you can remove the ceiling function which just causes problems. And then just properties of logs, right? 2 power minus log 1 / P of X is just, this whole thing is just, this whole thing is just P of X. So this is summation P of X. And this, I think all of you know, what is the sum of probabilities? One. Yes, I'm saying one's okay. One, right? So let me note this down as 0.1. 2 power minus LX less than or equal to 1. Right? This is one. Okay. Okay, let's, let's keep going. Okay, so say we assigned. So this is an inductive proof. So you say that you have already done M steps and now you will prove that the M plus 1th step is possible. So, so we assigned X1 to XM. So next is XM + 1. So then we already saw above that the sum of all the probabilities is less than or equal to 1. So therefore, if you add from 1 to M and then you add the next one, this is clearly smaller than the total sum. So this will be less than one, right? So this is like based on one, right? Because this is a partial sum. This is only part of the, the total sum. The, the, the, this one, this one was over all, all symbols in your alphabet. We are now just restricting to first m+1 symbols or so. What I will do now is the sort of the key. Is I will multiply both sides by 2 power L XM + 1 and then I will move one of the terms to the right to get minus one. Okay, uh, until now, it's just multiplying things, moving around things. No, no special logic until now. So let me move this to the next page and then we will like look at some actual like logic. So I, I will copy over the last point again. So I = 1 to M, 2 power L XM + 1 minus LX I less than or equal to 2 power LX M + 1 minus 1. Okay, um, let's call it two. Now, this is the part where, like, a visual representation is much, much easier to interpret, right? Let's look at this. Um, if you have a tree and you are at depth, let's say you are at depth Li, I, you have a node at depth Li and you have a subtree below this with total depth L M + 1. Okay, so first simple question, how many nodes do I have at depth L for a binary tree? 2 to the L, right? So at, in a binary tree, at depth L, I have 2 to the L nodes. Okay, now if I have this node at Li, I, and then I create a subtree, right, a tree below that node with overall depth L M + 1, how many nodes do I have here? How many nodes do I have here, like, how many nodes of depth L M + 1 are children of a node or descended of a node at depth Li? Yes. So, let, let me write that down. So, so number of leaves at L M + 1 that are descendants of depth Li node are 2 to the L M + 1 minus Li. Okay, now, now let's come back to this inequality. What is it saying really, right? Uh, each of these terms, what is it saying? So, so this term, this is number of descendants of the codeword of Xi, basically, that leaf at depth LX M + 1. What is this term? This term is the total number of leaves at LX M + 1. So what we are saying is, if you take all the nodes you have already added, like all the leaves you have already added, you extend each of them to depth LX + M + 1, you see that there is still one, at least one node left. And let me draw, draw it for you, but, uh, so what we are saying, and please think about this at home as well, um, is so what we did was, so you assigned X1 here, you assigned X2 here, X3 here, maybe you assigned X4 here, right? You now at X5, X5 it has a certain depth, so this is like your LX5, right? Now we are saying, let's take each of these guys, extend them to the level, right, like this, this, this. So all of these areas are like invalid, why? Because, because any, any node here will be a child, a descendant of the X1 node. So X1 will be a prefix if you try to assign it here. That's not good. Similarly, any node in this area is bad, right? For example, if X1 was 00, these nodes will be like 00110000, all of these guys. So these are just not allowed. These are not allowed. These are not allowed. These are not allowed. So what we are trying is, we are trying to eliminate all the nodes that are disallowed by the prefix-free property. And what we are showing is that even after you remove every node that is illegal, like which is not allowed, you are still left with one node which is, which is still valid. Um, right, any questions on this? I will, I will give you time to digest. I guess this is also written up in the notes which are available on the website. Um, okay, yeah, yeah.
Uh, so, so just to finish off, uh, the proof, right? So if you just write it like this, this is the total number of leaves at LX M + 1 depth minus summation 1 to M. So this is the number of leaves not allowed because they are descended from existing codeword. So what we have basically shown is that this is greater than or equal to one. So there is at least one leaf left at every step which you can assign to your next symbol to XM + 1. So at depth LX M + 1, there is at least one leaf which is left. Uh, so that, that is basically the proof. Uh, yeah, yeah. So, so sorry if it was too much, but I guess, uh, you have to see it. Uh, next class, we'll see another proof which is very similar. So I think that will help. Uh, uh, yeah, and we will put these up. [Applause] Right. And I think I will not have time to cover the last topic, Kraft's inequality, which we'll do next lecture. Um, I will leave it here and answer any questions. Otherwise, thank you. Don't, don't be scared of the proofs. If, if you are scared because they're only for two lectures, then it's mostly algorithmic. Uh, and about it, make, make, make examples. I think that that will really help. Just make some trees and, uh, uh, see, see, see what these quantities are at various steps, right? Thank you.