Let's get started. So we're in the home stretch. We've got one more of these topics in coding theory. Peter will be covering a related topic next week, but that'll be a bit of a different flavor. So today, we're going to cover one of the other great results in coding theory, which has to do with error correction.
So far, we've been exclusively talking about compression, how you can take a message and reduce the number of bits you need to transmit in order to reliably be able to recover what was the original message. Now, today, we're going to talk about a very realistic scenario, which is when the way that you're transmitting introduces errors.
So there's a very simple model, which is a good way to get started, which is called the binary symmetric channel, or BSC for short. The way that this channel works is that every time you input a bit, which is either 0 or 1, then it has some probability of flipping the outcome, the output of the bit.
So this BSC channel is going to be governed by some parameter p. And it's going to have the property that, with p probability, it ends up flipping the input and output. And with the remaining probability, 1 minus p, it just sends through whatever bit you sent along the channel.
The trouble is that you don't know when and where these errors have occurred. So the question is, you can think about p just for concreteness as being something like 1/3. If I'm trying to send a message along the channel to you, and I've already done my compression to get it down to the shortest possible string of 0's and 1's, now, when I send it along to you, and each bit gets flipped independently with probability of 1/3, what hope do you have of recovering the original message? And what are schemes you can design that combat the fact that you're anticipating there'll be errors?
So just to be clear, we're talking about each bit is flipped independently with this probability p. And now we can ask all of the natural questions about communication and the presence of errors. So the main thing we care about, which will be what we'll address today, is it still possible to transmit information reliably?
So let's think about what this question means with some simple ideas for how to combat the errors. So one simple example you can come up with for how to transmit along a noisy channel is to use what are called repetition codes.
So here, the idea is that I take my original message. Let's say it's a string of 0's and 1's. And what I'm going to do for what I'll transmit along the channel is I'm just going to keep repeating each input bit a certain number of times so that, even if some of them get corrupted, maybe it's OK. So I'll take my first bit, which is a 1, and I'm going to repeat it T times. And I'll do the same thing for my next bit. That's a 0. I'm going to repeat it T times. And I'll do the same thing for all of the bits in my original message.
So now you can see that, already, the way that I'm combating the fact that the channel is introducing errors is that I'm increasing the length of my transmission. I'm padding it with extra information in such a way that, hopefully, I can detect and correct whatever errors the channel has introduced. So the name of the game for today will be, what are the best possible schemes for how to pad the extra-- with extra information, in such a way that I can reliably figure out what my original message was?
So just to think about this, so let's say that the original message had length k. Then what I can do is I claim a good choice for how many times to repeat each message. There's maybe something like 100 log k. So my original message was length k. And then each bit, I repeat 100 log k times.
So intuitively, if I took this transmission and I sent it through the channel, some of these 1's get flipped to 0's independently. Some of these 0's get flipped to 1's independently. How would you try and decode what you receive to figure out what the original message is? Any ideas?
And keep in mind, just to be concrete, you can think about the failure of the flip probability as being something like 1/3. So maybe a bit is more likely to come through in the clear without being flipped than it is of being flipped. So if I sent you this long, padded transmission, how do you think I'd figure out what the first symbol is based on what I receive? Any ideas? Yeah?
Perfect, the majority vote because, intuitively, if I'm repeating this T times, then I would expect that the number of bit flips that I have is around T over 3. And so that means the majority of them should actually correspond to what my original bit was.
In fact, what I care about is not just what the expected number of bit flips are, but I care about getting bounds on how likely it is that my decoding rule would fail. So what kind of tool that we've talked about earlier in class might be relevant here? So I started off with bit flip probability, 1/3. And then I sent this bit through the channel with a repetition code. Now, my chance of getting the wrong bit for my majority vote decoding is the chance that the expected number of flips is 1/3. But really, the true number of flips is much larger because it's larger than 1/2. That's the only way I would get the wrong decoding for this bit is if I ended up with half errors instead of 1/3. So what kind of tool that we've covered earlier in class might be useful to get a bound on the failure probability, the chance that my decoder fails here? Yeah?