1 00:00:00,510 --> 00:00:03,568 So in this video. We're going to consider Shannon's crowning 2 00:00:03,568 --> 00:00:06,152 result. That it called this in 1948. 3 00:00:06,152 --> 00:00:08,983 The so called, Noisy Channel Coding Theorem. 4 00:00:08,983 --> 00:00:14,231 What this theorem states, that it is possible to communicate through a digital 5 00:00:14,231 --> 00:00:18,812 channel that introduces errors. So that the error correcting code can 6 00:00:18,812 --> 00:00:21,832 correct all the errors. Not just the single bit errors but all the 7 00:00:21,832 --> 00:00:24,324 errors. And we'll be very interested in the 8 00:00:24,324 --> 00:00:29,102 conditions under which you can do that. This is going to lead us to find the 9 00:00:29,102 --> 00:00:35,366 capacity of a channel which is the magic number that summarizes the error behavior 10 00:00:35,366 --> 00:00:38,630 of the channel. And once we understand that result, this 11 00:00:38,630 --> 00:00:41,380 will lead us to understand why is everything digital. 12 00:00:41,381 --> 00:00:45,565 There's no longer really much left anymore that's analog. 13 00:00:45,565 --> 00:00:47,906 And we'll see why that is in just a second. 14 00:00:47,907 --> 00:00:51,400 So let's review the Digital Communication Model. 15 00:00:51,401 --> 00:00:58,732 We have a digital source. And it goes through the compression stage. 16 00:00:58,732 --> 00:01:05,746 And It then goes through the channel coder which introducues the erorr corerecting 17 00:01:05,746 --> 00:01:09,163 cods. It gets sent through a channel that has a 18 00:01:09,163 --> 00:01:14,354 probability of Pe of flipping a bit. And we've already seen there are error 19 00:01:14,354 --> 00:01:19,814 correcting codes such that the decoder can correct those errors as long as there 20 00:01:19,814 --> 00:01:23,411 aren't too many of them. We worry about the single bit error 21 00:01:23,411 --> 00:01:27,485 correcting code. And once you correct those errors, you 22 00:01:27,485 --> 00:01:33,333 have now the, the same you can get out the bits that you were sent which allows you 23 00:01:33,333 --> 00:01:37,211 to reconstruct the signal and, and you are very happy. 24 00:01:37,211 --> 00:01:41,305 However this only mitigates the channel errors. 25 00:01:41,305 --> 00:01:47,845 If there happens to be two bits an error. Set of one, there's nothing that, that 26 00:01:47,845 --> 00:01:52,697 code we talked about can do. It will totally foul up. 27 00:01:52,698 --> 00:01:57,670 So we can reduce the errors with those error, a single bit error correcting 28 00:01:57,670 --> 00:02:02,835 schemes but we can't make it go to zero. Well Shannon asked, can we remove all 29 00:02:02,835 --> 00:02:07,750 channel induced errors? Is there such a powerful error corrupting 30 00:02:07,750 --> 00:02:12,664 code that we can use it and not worry about any kind of errors that the channel 31 00:02:12,664 --> 00:02:18,526 may be introducing. And clearly the answer was yes you can but 32 00:02:18,526 --> 00:02:23,567 let's see what the statement or the result is. 33 00:02:23,568 --> 00:02:29,568 So the noisy channel coding theorem. Says, says let e be the efficiency of the 34 00:02:29,568 --> 00:02:33,396 code. So if you recall, we have an NK where N is 35 00:02:33,396 --> 00:02:38,240 the length of the codeword that's used to represent K bits. 36 00:02:38,240 --> 00:02:42,453 K data bits. If that efficiency is less than the 37 00:02:42,453 --> 00:02:47,765 capacity C of the channel, then there is an error correcting code that has the 38 00:02:47,765 --> 00:02:52,197 probability. That, as the length of the, the code word 39 00:02:52,197 --> 00:02:58,964 goes to infinity, the probability that you, that you can decode without the, 40 00:02:58,964 --> 00:03:04,238 that, the decoding will incur an error. Let me get this straight. 41 00:03:04,238 --> 00:03:07,155 So if the decoding will incur in error is 0. 42 00:03:07,155 --> 00:03:11,680 In other words, you can get the data through without error. 43 00:03:11,680 --> 00:03:16,787 And that's so long as the efficiency of the code is less than the capacity and 44 00:03:16,787 --> 00:03:20,272 I'll show you in the next line what the capacity is. 45 00:03:20,272 --> 00:03:25,138 I want to point out some things though first, and that is this limit here means 46 00:03:25,138 --> 00:03:28,594 that the code word length is going to infinity. 47 00:03:28,595 --> 00:03:33,860 Since we're keeping the efficiency at constant that means that more and more 48 00:03:33,860 --> 00:03:37,280 data bits are being used in the error correcting code. 49 00:03:37,280 --> 00:03:42,150 So this code word is going to get very, very long but if you do that despite what 50 00:03:42,150 --> 00:03:47,024 we may have been seeing there exists an error correcting code out there. 51 00:03:47,025 --> 00:03:52,078 So its that you can make the probability of an error occurring in the recovering 52 00:03:52,078 --> 00:03:57,211 data block, 0. He then proved a result which makes this 53 00:03:57,211 --> 00:04:04,143 capacity a very special number. If the code efficiency is greater than C 54 00:04:04,143 --> 00:04:09,828 then all error correcting codes. We'll always incur decoding errors. 55 00:04:09,829 --> 00:04:14,693 In other words, again, as the block then goes to infinity, a probability that 56 00:04:14,693 --> 00:04:18,671 there's an error anywhere in the data block is going to be one. 57 00:04:18,671 --> 00:04:25,084 So you better have a code, use a code, use efficiency less than the capacity. 58 00:04:25,084 --> 00:04:28,020 If you try to use one that's was a bit weaker. 59 00:04:28,020 --> 00:04:33,043 Doesn't add as much error corerection. You will never be able to correct the 60 00:04:33,043 --> 00:04:35,400 errors. So, what is the capacity? 61 00:04:35,400 --> 00:04:41,940 So, if our little channel, the digital channel we've been talking about. 62 00:04:41,940 --> 00:04:50,324 The capacity is given by this formula. And if you seems, say that looks a little 63 00:04:50,324 --> 00:04:55,490 bit familiar. It does look like it's the entropy formula 64 00:04:55,490 --> 00:05:00,787 applied to Pe and 1 minus Pe. In fact 1 minus, it's 1 minus an entropy 65 00:05:00,787 --> 00:05:06,163 formula involved in those quantities. So here's a plot of capacity. 66 00:05:06,164 --> 00:05:17,900 So let's focus on the extremes here first. Let's look at Pe equals zero, the capacity 67 00:05:17,900 --> 00:05:24,135 is 1. And since E of, the efficiency of the code 68 00:05:24,135 --> 00:05:30,680 has been less than C N. Needs to be less than c. 69 00:05:30,680 --> 00:05:36,785 That means that we can have efficiency code of, efficiency of 1, when Pe is 0. 70 00:05:36,786 --> 00:05:41,132 Well, efficiency of 1 means there is no coding. 71 00:05:41,133 --> 00:05:45,156 That all thee, all this in and code words are data bits, and certainly if there are 72 00:05:45,156 --> 00:05:49,185 no errors in the channel will just send the data through, if that's your problem. 73 00:05:49,185 --> 00:05:54,546 On the other hand, on the other extreme, Pe is half, that means that the channel is 74 00:05:54,546 --> 00:06:00,108 randomly flipping the bits. And, it's total chaos, basically coming 75 00:06:00,108 --> 00:06:07,210 out of the channel and there is no error correcting code, because you cannot send 76 00:06:07,210 --> 00:06:12,097 times through the efficiency has 0. And why bother? 77 00:06:12,097 --> 00:06:19,549 So at some intermediate Pe, you cannot use a code that's greater than this capacity 78 00:06:19,549 --> 00:06:25,830 if you have any hope of getting the message through without error. 79 00:06:25,830 --> 00:06:31,406 If you try to use something that has a greater efficiency, greater than capacity, 80 00:06:31,406 --> 00:06:34,778 you're going to have errors. You just can't do it. 81 00:06:34,779 --> 00:06:38,580 What's interesting about this plot is that you can plot it for Pe greater than a 82 00:06:38,580 --> 00:06:42,246 half. There's no reason you can't, and it kind 83 00:06:42,246 --> 00:06:46,300 of falls in on the map that indicates where Pe is 1. 84 00:06:46,300 --> 00:06:52,376 That means if the channel is flipping reliably every bit changing a 0 to a 1, 85 00:06:52,376 --> 00:06:56,586 changing a 1 to a 0. And if the efficiency is 1, you might as 86 00:06:56,586 --> 00:07:01,878 well just send all the data because all the channel decoder has to do, it just 87 00:07:01,878 --> 00:07:06,964 flip the bits back. So, automatically, that result is taken 88 00:07:06,964 --> 00:07:10,943 into account. So a really bad pe, turns out to be 89 00:07:10,943 --> 00:07:17,958 equivalent to a really good one. So Channel's result is symmetric in that 90 00:07:17,958 --> 00:07:21,472 way. So let's talk about a few issues with the 91 00:07:21,472 --> 00:07:26,566 Noisy Channel Coding Theorem. Which are pretty important. 92 00:07:26,566 --> 00:07:32,034 And the first is this phrase that keeps coming up, there exists an 93 00:07:32,034 --> 00:07:37,616 error-correcting code. Well, to this day, we don't know what that 94 00:07:37,616 --> 00:07:40,674 code is. There are two candidates out there that 95 00:07:40,674 --> 00:07:45,418 are being studied today. And they come very close to the so called 96 00:07:45,418 --> 00:07:52,488 capacity limit but no ones proven that they can satisfy the noisy channel coding 97 00:07:52,488 --> 00:07:55,487 theorem. Shannon's proof with the noisey shany, 98 00:07:55,487 --> 00:07:59,099 noisy channel coding theorem is fine. There's nothing wrong with it. 99 00:07:59,100 --> 00:08:02,090 It's just that it's not what we call constructive. 100 00:08:02,090 --> 00:08:06,869 It doesn't give you an example. Proof of it did not use an example code. 101 00:08:06,869 --> 00:08:12,657 It was proven a different way. We still don't know what the code is. 102 00:08:12,658 --> 00:08:20,790 But there is a more practical problem which has to do with this limit, as N goes 103 00:08:20,790 --> 00:08:24,885 to infinity. So this means the code word length has to 104 00:08:24,885 --> 00:08:30,155 go to infinity which means you're also taking in more and more data bits and 105 00:08:30,155 --> 00:08:35,680 encoding them all at once, sending them through the channel and then decoding 106 00:08:35,680 --> 00:08:38,159 them. So this incurs what we call a coding 107 00:08:38,159 --> 00:08:41,484 delay. And you also have to wait for all the data 108 00:08:41,484 --> 00:08:44,151 to come in before you can run your channel code. 109 00:08:44,151 --> 00:08:51,552 Now, that isn't very nice and the capacity that obeys this result is sometimes called 110 00:08:51,552 --> 00:08:58,429 the C infinity capacity, which means you need an infinite length code word. 111 00:08:58,430 --> 00:09:04,405 And what we'd like to talk about is what is the capacity for a finite length code 112 00:09:04,405 --> 00:09:07,659 word. It's certainly, if it exists is going to 113 00:09:07,659 --> 00:09:12,643 be less than C infinity capacity. But we don't know there are a noisy 114 00:09:12,643 --> 00:09:18,216 channel coding theorem for such a thing. It's not clear that you can correct all 115 00:09:18,216 --> 00:09:22,776 codes with a finite length block. But people are certainly working on that, 116 00:09:22,776 --> 00:09:31,744 so we can have practical codes. Well, Shannon also derived a capacity. 117 00:09:31,744 --> 00:09:35,567 When we take into account the fact that underneath our digital channel, there's 118 00:09:35,567 --> 00:09:40,459 really an analog channel. So as we always abstracted the analog 119 00:09:40,459 --> 00:09:48,532 channel, channel it's adding noise, the signal set choice and everything and just 120 00:09:48,532 --> 00:09:53,547 call it a digital channel. But, if you go back down and you talk 121 00:09:53,547 --> 00:09:57,252 about a white noise channel having a bandwidth of W. 122 00:09:57,252 --> 00:10:01,268 And having to have figured out what the signals sets are. 123 00:10:01,268 --> 00:10:08,770 Then Shannon's results says yes. If the datarate of the source is less than 124 00:10:08,770 --> 00:10:16,470 the capacity, then you can have what are called, we call reliable communication, no 125 00:10:16,470 --> 00:10:22,180 errors you can't, will occur. If you have the right error correcting 126 00:10:22,180 --> 00:10:25,550 code. So if the rate is less than capacity, you 127 00:10:25,550 --> 00:10:30,486 can send information through a channel without error, somehow. 128 00:10:30,486 --> 00:10:36,979 And here's the formula for capacity. So, W is the bandwith of the channel in 129 00:10:36,979 --> 00:10:40,388 hertz. The signal to noise ratio is the 130 00:10:40,388 --> 00:10:46,626 signal-to-noise ratio in the channel. And this result is in bps because of the 131 00:10:46,626 --> 00:10:50,534 law of this too. And just as before, if you try to send it 132 00:10:50,534 --> 00:10:55,581 at a data rate greater than capacity, it's impossible to have reliable communication. 133 00:10:55,581 --> 00:11:00,325 You're always going to incur error. So, nowadays when you try to design a 134 00:11:00,325 --> 00:11:06,485 digital communication system, one of the things you do is calculate the capacity to 135 00:11:06,485 --> 00:11:10,024 make sure. And make sure that the data rate your 136 00:11:10,024 --> 00:11:13,800 trying to sent to that channel satisfy this bound. 137 00:11:13,800 --> 00:11:16,445 If they don't, you're going to have errors. 138 00:11:16,446 --> 00:11:21,276 If you use a data rate less than capacity then there's hope that you can, there is a 139 00:11:21,276 --> 00:11:25,668 signal set and error correcting code that'd do the job, but like I said, we 140 00:11:25,668 --> 00:11:30,224 don't know what they are yet. But no one tries to send at a data rate 141 00:11:30,224 --> 00:11:33,949 greater than capacity because there's no hope. 142 00:11:35,710 --> 00:11:42,282 So I'm going to go through our little example that we've done before and if you 143 00:11:42,282 --> 00:11:48,807 recall we were trying to send an analog signal through a channel here. 144 00:11:48,808 --> 00:11:52,689 Th, and the analog signal had a bandwidth of 4 kHz. 145 00:11:52,689 --> 00:11:58,520 So, we're going to send it an A to D converter and sample it. 146 00:11:58,521 --> 00:12:07,649 Now, thing to note is that the anolog signal, incurred a quantization error. 147 00:12:07,650 --> 00:12:12,880 And once we, when it's in that A to D convertor, and you sample it with a finite 148 00:12:12,880 --> 00:12:16,727 number of bits, here four. There is an unrecoverable error. 149 00:12:16,727 --> 00:12:22,326 We cannot get the original signal back. So what I want to ask is can we mitigate 150 00:12:22,326 --> 00:12:26,274 the communication errors? Can you get rid of them? 151 00:12:26,275 --> 00:12:31,475 Simply only have the quantization error of the A to D converter. 152 00:12:31,475 --> 00:12:36,077 So, for this example the sampling rate is, of course, 8 kHz. 153 00:12:36,078 --> 00:12:40,854 Twice the bandwidth of the signal. And I'm using a band, or a number of bits 154 00:12:40,854 --> 00:12:43,317 of 4 and the A to D converter in this example. 155 00:12:43,318 --> 00:12:49,606 So we have a data rate of 32 kilobits. So we want to know, for what channels, is 156 00:12:49,606 --> 00:12:55,915 the capacity greater than 32 kilobits. And I have here a color plot. 157 00:12:55,915 --> 00:13:03,497 That chose of how that works. So, the large area in color here. 158 00:13:03,497 --> 00:13:08,090 All I'm doing is plotting the capacity as a function of SNR. 159 00:13:08,090 --> 00:13:16,535 And channeled down with in hertz. So in the 32 bit kilobit plane is shown. 160 00:13:16,536 --> 00:13:24,494 And so this boundary here forms, shows us which channels can support the data rate 161 00:13:24,494 --> 00:13:31,493 of 32 kilobits, So that you can get the information through without error, at 162 00:13:31,493 --> 00:13:37,247 least in theory. So, we can see that, as the. 163 00:13:37,247 --> 00:13:45,512 The we have approaches, about 4 kHz. You're going to need a very high quality 164 00:13:45,512 --> 00:13:50,624 channel, because the SNR you're going to need is very, very high. 165 00:13:50,624 --> 00:13:56,922 Furthermore, if the SNR gets low, it turns out the bandwidth is going up and up and 166 00:13:56,922 --> 00:14:01,060 up. And, that's kind of standard. 167 00:14:01,060 --> 00:14:06,130 So if you're anywhere in this region, it's impossible. 168 00:14:06,130 --> 00:14:09,732 You're in big trouble. So you want to be in the region that's 169 00:14:09,732 --> 00:14:13,200 inside this boundary. You want to be in there somewhere. 170 00:14:13,200 --> 00:14:17,226 In order to communicate this signal you have a hope whether it's sending the 171 00:14:17,226 --> 00:14:22,612 signal through, with the, the help there. I want to compare this result with the 172 00:14:22,612 --> 00:14:28,822 plot we had for the signal-to-noise ratio. So if you remember this plot, I was 173 00:14:28,822 --> 00:14:34,702 comparing analog communication, which is the resulting message signal-to-noise 174 00:14:34,702 --> 00:14:40,708 ratio was given via that. Y is a function of the channels that 175 00:14:40,708 --> 00:14:47,223 signal is shown, with 4 bits and 8 bits. And, I'm only going to do the 4 bit 176 00:14:47,223 --> 00:14:52,275 example again. So, turning things around a little bit, if 177 00:14:52,275 --> 00:14:56,307 you, you want to know what signal ratio would work? 178 00:14:56,307 --> 00:15:01,893 And the data rate, of course, is the sampling rate, times the number of bits in 179 00:15:01,893 --> 00:15:06,130 the de-converter. And when you work that all out, you get 180 00:15:06,130 --> 00:15:10,351 this. Well, for the case that we were, worrying 181 00:15:10,351 --> 00:15:14,495 about. We were worrying about an 8 kHz, y 182 00:15:14,495 --> 00:15:18,249 channel. Which so that you could use the same 183 00:15:18,249 --> 00:15:24,081 bandwidth as the analog signal requires, modulated analog communication required 8 184 00:15:24,081 --> 00:15:27,925 kHz bandwidth channel. Suppose you made the digital channel live 185 00:15:27,925 --> 00:15:30,844 with eight kilo hertz? What signal noise ration are you going to 186 00:15:30,844 --> 00:15:34,378 need? Well you can do that in this calculation. 187 00:15:34,378 --> 00:15:39,676 Wc and Fs are the same quantity, so you just get 2 to the B minus 1. 188 00:15:39,676 --> 00:15:47,352 So the answer, answer is 15 which in dB turns about to be about 11. 189 00:15:47,353 --> 00:15:57,027 So what results is I can send my information through my channel, my channel 190 00:15:57,027 --> 00:16:01,311 somehow. Yet if the SNR is bigger than this number 191 00:16:01,311 --> 00:16:04,585 then I will incur a no communication error. 192 00:16:04,585 --> 00:16:10,174 The only thing I'm left with is the quantization error, that's this plateau. 193 00:16:10,174 --> 00:16:16,436 But once I drop below this magic number, it turns out to the signal-to-noise ratio 194 00:16:16,436 --> 00:16:20,781 goes to basically 0 and I can't get anything through. 195 00:16:20,781 --> 00:16:26,596 And this is the capacity wall, its called. And once you get, you transmit enough 196 00:16:26,596 --> 00:16:32,168 signal-to-noise ratio so which your above magic threshold, things are fine. 197 00:16:32,168 --> 00:16:36,380 But if you fall below it, things are not very good at all. 198 00:16:36,380 --> 00:16:40,361 You're going to be in big trouble. And as you can see from this plot, you're 199 00:16:40,361 --> 00:16:43,010 better off not using any channel coding at all. 200 00:16:43,010 --> 00:16:49,158 And this is what happens when you use BPSK and don't do any channel coding. 201 00:16:49,159 --> 00:16:54,200 In that situation, in this regime, you're better off not trying to do channel coding 202 00:16:54,200 --> 00:16:58,488 at all, but you're always incurring error, and that's the sad result. 203 00:16:58,488 --> 00:17:02,394 But there is a region with which you can get through and live only with the 204 00:17:02,394 --> 00:17:05,266 quantification there. Very, very nice. 205 00:17:05,266 --> 00:17:07,982 So. Why is everything digital? 206 00:17:07,982 --> 00:17:11,862 So. Sources can be compressed, first of all. 207 00:17:11,862 --> 00:17:18,749 And that's either lossy or lossless, depending on whichever you're going with. 208 00:17:18,749 --> 00:17:24,061 If it's lossy and you could consider running an analog signal through and A to 209 00:17:24,061 --> 00:17:27,530 D converter as being a lossy compression scheme. 210 00:17:27,530 --> 00:17:31,457 It's representing signal bits but you cannot recover it. 211 00:17:31,458 --> 00:17:37,203 Same thing is compressing music with an MP3 compre- compressor as lossy 212 00:17:37,203 --> 00:17:43,201 compression. Be then as it may, you can convert 213 00:17:43,201 --> 00:17:49,755 basically in its any source into a sequence of letters which can be 214 00:17:49,755 --> 00:17:56,919 compressed in the source coders. Somehow, we can find a error cracking code 215 00:17:56,920 --> 00:18:01,981 that's very good. As long as it obeys the noisy channel 216 00:18:01,981 --> 00:18:07,664 coding theorem, we know we can actually decode without error. 217 00:18:07,665 --> 00:18:14,449 So, that means once you are wiling to incur the error in digitizing analog 218 00:18:14,449 --> 00:18:19,294 signals converting it to bits. Turns out that means now. 219 00:18:19,295 --> 00:18:25,008 Digitized signals and inherently digital signals, like text, can now be transmitted 220 00:18:25,008 --> 00:18:30,287 over a common communication scheme without error, and that is really interesting. 221 00:18:30,288 --> 00:18:37,294 So, once you have bits, you got a chance. You can send the bits through a channel 222 00:18:37,294 --> 00:18:42,921 with no error. There is no similar result for analog 223 00:18:42,921 --> 00:18:46,944 channels. Once you have error and noise introduced 224 00:18:46,944 --> 00:18:51,834 in an analog channel you have to live with the errors if you stay analog. 225 00:18:51,834 --> 00:18:56,922 But if you go digital, or if you have a digital source, you can correct those 226 00:18:56,922 --> 00:19:01,301 errors if they channel. Well you could do this if the situation is 227 00:19:01,301 --> 00:19:04,689 correct. In other words, if the data rates is less 228 00:19:04,689 --> 00:19:09,658 than the capacity. Well, this ability to send any kind of 229 00:19:09,658 --> 00:19:14,143 signal once its bit. That leads to repute computer networks. 230 00:19:14,144 --> 00:19:18,339 Well computer networks can carry any kind of signals. 231 00:19:18,340 --> 00:19:22,042 Be it SMS. Be it your voice. 232 00:19:22,043 --> 00:19:25,606 Be it an image. Be it a video. 233 00:19:25,606 --> 00:19:31,630 We all can put all those different kind of sick messages into a common communication 234 00:19:31,630 --> 00:19:35,575 scheme. And the reason for that is Shannon's Noisy 235 00:19:35,575 --> 00:19:37,587 Channel Coding Theorem.