CEOInterviews.AI
Start App
Get an email when Ankur Moitra gives a new interview
One email per new interview. Unsubscribe in one click.
Ankur Moitra
Professor of Mathematics, MIT

Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem

📅 Dec 17, 2025 MIT OpenCourseWare 72 MIN 2002 VIEWS 92 SEGMENTS · 2 SPEAKERS
MIT 18.200 Principles of Discrete Applied Mathematics, Spring 2024 Instructor: Ankur Moitra View the complete course: https://ocw.mit.edu/courses/18-200-pr... YouTube Playlist:    • MIT 18.200 Principles of Discrete Applied ...   How do you transmit information reliably over noisy channels? We first discuss simple codes: repetition codes. Shannon’s noisy coding theorem shows much better codes exist. We prove the simplest case of this theorem — for the binary symmetric channel. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/terms More courses at https://ocw.mit...

Questions asked in this interview

1
  1. 1:08:04Sorry, can you explain the epsilon over 2 part?
Ankur Moitra 0:10 ↗
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?
Audience Member 6:00 ↗
The majority of the block.
Ankur Moitra 6:02 ↗
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?
Audience Member 7:22 ↗
Markov.
Ankur Moitra 7:23 ↗
Markov would do it. So I could certainly use Markov. That's an example of a tail bound. Now, one problem, though, is that Markov uses very little information about the random variables. So if I did this, what I care about is, what's the probability that I fail for this bit? What's the probability that I fail for this bit and so on? And it turns out that if you used Markov, if you wanted to argue that, with good chance, I fail on none of these bits and I use the union bound, I would end up having to pad the length of the message by a factor of k instead of log k. So are there any ideas for how I could hope to get sharper bounds on how much I need to increase the padding by? Yeah.
Audience Member 8:09 ↗
Chernoff.

7 more exchanges in this transcript

Sign in free to read the rest of this interview. No card required.

Sign in to read the full transcript

Cite this transcript

APA, MLA, BibTeX
APA

Moitra, A. (2025, December 17). Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem [Interview transcript]. MIT OpenCourseWare. CEOInterviews.AI. https://ceointerviews.ai/interview/3287810/

MLA

Ankur Moitra. "Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem." MIT OpenCourseWare, 17 Dec. 2025. Transcript, CEOInterviews.AI, https://ceointerviews.ai/interview/3287810/.

BibTeX
@misc{moitra2025_3287810,
  author       = {Ankur Moitra},
  title        = {Lecture 18: Transmitting Information Reliably over a Noisy Channel \& Shannon’s Noisy Coding Theorem},
  howpublished = {Interview transcript, MIT OpenCourseWare. CEOInterviews.AI},
  year         = {2025},
  month        = {dec},
  url          = {https://ceointerviews.ai/interview/3287810/},
  note         = {Speaker-attributed transcript with timestamps}
}