1 00:00:00,000 --> 00:00:05,440 In our previous video we talked about how to evaluate whether a code, an error 2 00:00:05,440 --> 00:00:09,545 correcting code, could correct single bit errors or not. 3 00:00:09,545 --> 00:00:13,203 What I didn't talk about, though, was actually how does a code that has that 4 00:00:13,203 --> 00:00:15,950 capability, how does it actually correct the errors? 5 00:00:15,950 --> 00:00:18,652 That's what we're going to talk about in this video. 6 00:00:18,653 --> 00:00:24,466 So to review we have the digital communication model. 7 00:00:24,466 --> 00:00:28,440 And a channel coder is what we're talking about. 8 00:00:28,440 --> 00:00:33,494 It takes in K bits at once, puts out N bits. 9 00:00:33,494 --> 00:00:42,606 And the way it does it is through the matrix equation when c equals g b, and the 10 00:00:42,606 --> 00:00:46,284 g defines the code. It's called the generator matrix. 11 00:00:46,284 --> 00:00:51,597 And the bits, the N bits that it sends through goes through the additional 12 00:00:51,597 --> 00:00:55,438 channel. The channel has a probability, Pe of 13 00:00:55,438 --> 00:01:01,572 flipping a bit, changing the 0 to a 1, or a 1 to a 0, and it does so randomly. 14 00:01:01,572 --> 00:01:08,218 So, what comes out of the channel, these N data, N bits that come out of the channel 15 00:01:08,218 --> 00:01:12,778 the received code work could have errors in it may not. 16 00:01:12,778 --> 00:01:17,758 It's up to the channel decoder to not only determine if that an error occurred in the 17 00:01:17,758 --> 00:01:23,200 transmission but also to fix it. Fix those errors so we can produce the 18 00:01:23,200 --> 00:01:29,320 original data discs that were sent and we know that this error correcting code for 19 00:01:29,320 --> 00:01:34,670 the 7, 4 Hamming code obeys the properties that we are looking for. 20 00:01:34,670 --> 00:01:39,918 We have to have the minimum distance between any two any pair of code words has 21 00:01:39,918 --> 00:01:45,112 to be greater than or equal to three. We know that this G works, but we haven't 22 00:01:45,112 --> 00:01:49,948 actually figured out how the channel decoder does it's job and that's what 23 00:01:49,948 --> 00:01:56,482 we'll be talking about today. So, here's our source coder and our G, and 24 00:01:56,482 --> 00:02:01,907 it's worthwhile going over the sizes of things here. 25 00:02:01,908 --> 00:02:07,113 This is an N. A tall matrix, and it's Ky. 26 00:02:07,113 --> 00:02:15,344 So, that agrees with the fact it's taking in K bits, and it's producing N. 27 00:02:15,344 --> 00:02:22,286 And it's also worthwhile to note that the top K part of this is the identity matrix, 28 00:02:22,286 --> 00:02:29,120 and the bottom N minus K part Is a special matrix that has the properties we need to 29 00:02:29,120 --> 00:02:33,352 kind of deem N greater than or equal to three. 30 00:02:33,352 --> 00:02:40,119 Here's what comes out of the channel, what the channel decoder receives is not C, 31 00:02:40,119 --> 00:02:45,820 which was transmitted by the general coder that are received c hat. 32 00:02:45,820 --> 00:02:53,689 And we can write express, the occurrence of errors in this way, where e is a 33 00:02:53,689 --> 00:02:58,828 vector. It has a 1 in every position where there 34 00:02:58,828 --> 00:03:04,646 was an error in the transmitted codeword. Error upon reception. 35 00:03:04,647 --> 00:03:10,978 If we remember the properties of exclusive or addition, when you put a one as one of 36 00:03:10,978 --> 00:03:17,116 the area you're adding together, that flips the bit of the other, the match, 37 00:03:17,116 --> 00:03:21,614 match, mounts to get flipping. And so this is a very nice way of 38 00:03:21,614 --> 00:03:25,400 describing the fact that an error was in transmission. 39 00:03:25,400 --> 00:03:28,480 In this case the third bit occurred in error. 40 00:03:28,480 --> 00:03:33,645 Of course the channel decoder doesn't know which one occurred in error, it has to 41 00:03:33,645 --> 00:03:37,692 figure that out. But this was is going to be very helpful 42 00:03:37,692 --> 00:03:42,284 for us. Well, how does the decoder work? 43 00:03:42,285 --> 00:03:47,100 And what it does is it forms the following result. 44 00:03:47,100 --> 00:03:53,615 It has, creates the S vector as given by H another matrix times C hat. 45 00:03:53,615 --> 00:04:00,623 And the way H is created is as follows, you first take the lower portion of G. 46 00:04:02,480 --> 00:04:11,483 You stick it in down there. Remember, this is an n minus k tall bottom 47 00:04:11,483 --> 00:04:14,933 part. And it's k wide. 48 00:04:14,933 --> 00:04:20,833 You then tack on to this lower portion of G part, you tack on the identity matrix. 49 00:04:20,834 --> 00:04:27,844 Matrix, well that makes this matrix N minus K tall or it makes it N wide which 50 00:04:27,844 --> 00:04:34,009 is what we need and so that everything, all the dimensions agree. 51 00:04:34,009 --> 00:04:42,210 So again, the dimension of S is N minus K. Well, this seems to come out of thin air. 52 00:04:42,210 --> 00:04:44,957 How does this work and that's what I'm about to show. 53 00:04:44,958 --> 00:04:50,437 Is that this formula for h, this use of h will do what we want. 54 00:04:50,438 --> 00:04:56,070 So let's look at what this matrix multiply does. 55 00:04:56,070 --> 00:05:00,938 We have sin c hat is given by this, we substitute again. 56 00:05:00,938 --> 00:05:05,828 Use the properties of matrix multiply and that's the result. 57 00:05:05,829 --> 00:05:14,847 And when I substitute it was c is, what the channel code is, we get this. 58 00:05:14,847 --> 00:05:20,327 What I'm about to show you is H times Gb is zero. 59 00:05:20,328 --> 00:05:28,026 This choice for H here is it based on which G is, is such, is chosen such that 60 00:05:28,026 --> 00:05:36,216 each time G is 0, no matter what b is, and if its 0 that means that you multiply the 61 00:05:36,216 --> 00:05:44,295 received code word by H is simply e equals to H times the order of sequence. 62 00:05:44,296 --> 00:05:48,790 If the error sequence is zero. This result is zero. 63 00:05:48,790 --> 00:05:54,298 There are no errors and we're happy. If's when e is not zero which gives a 64 00:05:54,298 --> 00:05:59,846 nonzero value for S. That's when we get we know we have to 65 00:05:59,846 --> 00:06:02,970 correct errors. That's called the detection process. 66 00:06:02,970 --> 00:06:09,350 We know that there is a, a error that occurred, and this is not equal to zero. 67 00:06:09,350 --> 00:06:13,087 So we still have to talk about how you actually correct the errors. 68 00:06:13,088 --> 00:06:22,900 So let me prove to you first that, that property H time G is 0, is true. 69 00:06:22,901 --> 00:06:29,829 So remember how G was constructed. Identity up top, G lower at the bottom. 70 00:06:29,830 --> 00:06:35,882 So that when you multiply times the data block, you get the following result for c, 71 00:06:35,882 --> 00:06:44,080 which can be written this way. Now H, it is of course formed in the, in 72 00:06:44,080 --> 00:06:50,088 this following way. G lower is stuck down there and then I is 73 00:06:50,088 --> 00:06:56,964 added on. Now what happens when you look at H times 74 00:06:56,964 --> 00:06:58,360 c. Okay. 75 00:06:58,360 --> 00:07:08,510 So that's HG times b and so, let's see. We have multiplied this times that. 76 00:07:08,510 --> 00:07:15,194 We get G lower times b plus identity times G lower times b. 77 00:07:15,195 --> 00:07:20,740 Well, whenever you add together, two binary vectors that have exactly same 78 00:07:20,740 --> 00:07:26,665 components with the exclusive or. You get 0. 79 00:07:26,665 --> 00:07:33,304 So it doesn't matter what B is because these two things are the same you get 0 80 00:07:33,304 --> 00:07:38,256 all the time. So this H, this choice of H always results 81 00:07:38,256 --> 00:07:44,450 in when a code word arrives without error the result is going to be 0. 82 00:07:44,450 --> 00:07:49,294 And the interesting thing is, is that, when there is an error. 83 00:07:49,295 --> 00:07:55,738 It's only this H times c property being 0 means that H times c hat. 84 00:07:55,738 --> 00:08:00,963 It depends only on the error sequence. Not on the transmitted code word. 85 00:08:00,963 --> 00:08:06,669 That's really very cool. So for each received code word. 86 00:08:06,670 --> 00:08:10,705 We formed H times c hat and we know that's H times e. 87 00:08:10,706 --> 00:08:15,871 And if it's nonzero, we know that there was an error. 88 00:08:15,872 --> 00:08:21,789 And what you simply go through is you write down all of the N possible, N 89 00:08:21,789 --> 00:08:29,748 possible single bit error sequences for E. You do the matrix multiplying from this 90 00:08:29,748 --> 00:08:34,761 table, and all the decoder has to do is it says oh I got 111. 91 00:08:34,761 --> 00:08:36,810 That means there was an error. I look in this table. 92 00:08:36,810 --> 00:08:41,283 I figure out that the second bit was an error and I correct it by adding it to it 93 00:08:41,283 --> 00:08:45,000 as you see. Now the entries in this table may seem 94 00:08:45,000 --> 00:08:50,227 kind of mysterious, but what they amount to are the columns of H. 95 00:08:50,228 --> 00:08:54,863 That's because each of these single bit error sequences do the multiplying just 96 00:08:54,863 --> 00:08:59,282 picks out a column. And so, this table may seem kind of random 97 00:08:59,282 --> 00:09:04,320 but it's really just the columns of H. So, it's pretty easy to figure out. 98 00:09:04,320 --> 00:09:12,860 So, now that the decoder has a good idea what the error sequence is. 99 00:09:12,860 --> 00:09:21,949 It turns out if you adds that error sequence to what it received since c hat 100 00:09:21,949 --> 00:09:27,514 is c plus e, you add e again. Well, if you add 2 vectors, they're the 101 00:09:27,514 --> 00:09:30,654 same. That's 0, and you get back the original 102 00:09:30,654 --> 00:09:33,903 codeword. It has corrected the error. 103 00:09:33,904 --> 00:09:39,345 All that you could do now is determine what the data bits were now that you have 104 00:09:39,345 --> 00:09:43,090 the actual codeword that the channel code produced. 105 00:09:43,090 --> 00:09:47,954 And for the set four code, the top four bits, the first four bits correspond to 106 00:09:47,954 --> 00:09:50,942 the data bits. So that's pretty easy and we have 107 00:09:50,942 --> 00:09:55,030 corrected the error. So, it's very cool. 108 00:09:55,031 --> 00:10:01,524 All single bit errors can be corrected. Now there's a little detail here and that 109 00:10:01,524 --> 00:10:06,604 we can correct the errors but we did so at a, at a small price. 110 00:10:06,604 --> 00:10:13,157 We have to send the data at the same, at the same rate whether we code or not. 111 00:10:13,158 --> 00:10:19,968 So the time taken to send K bits with no coding, no error correcting coding has to 112 00:10:19,968 --> 00:10:26,457 be the same as if we instead used seven bits to send the same data when we add on 113 00:10:26,457 --> 00:10:31,454 the error correction. Well, that means that we have to cut down 114 00:10:31,454 --> 00:10:37,350 the bit interval by the efficiency of the code and that means the single bit error 115 00:10:37,350 --> 00:10:41,365 probability PE goes up In the error collection case. 116 00:10:41,366 --> 00:10:47,264 That's because we were using last time. So, the question is does that, that's bad 117 00:10:47,264 --> 00:10:50,430 if that P goes up. So doing N over O. 118 00:10:50,430 --> 00:10:57,256 So Y product here is the combo of the block of there for two cases, one in I use 119 00:10:57,256 --> 00:11:03,626 simply send four bits as a block. And in the case where I employ my (7,4) 120 00:11:03,626 --> 00:11:09,801 Code you wish PE is slightly hal higher given by the formal reply rather than 121 00:11:09,801 --> 00:11:14,134 through these videos. And what you discover when you find a plot 122 00:11:14,134 --> 00:11:19,059 the resulting combo is a function of the signal-to-noise ratio in the channel. 123 00:11:19,060 --> 00:11:25,330 That turns out the uncoded case always results in a bigger probability of error 124 00:11:25,330 --> 00:11:30,400 any of your code. So we win and in some cases it can be big, 125 00:11:30,400 --> 00:11:34,064 above 10db. That's almost a factor of 10 better in 126 00:11:34,064 --> 00:11:37,457 terms of overall probability getting it through. 127 00:11:37,458 --> 00:11:44,337 So error correction wins, we certainly do, as long as you have an efficient code. 128 00:11:44,338 --> 00:11:47,860 So what you'd like, you'd like the code efficiency to go up. 129 00:11:47,860 --> 00:11:52,892 Now I should comment that the repitition code that we've already talked about the 130 00:11:52,892 --> 00:11:57,941 one three one code. If you look at it and plot the same plot, 131 00:11:57,941 --> 00:12:05,200 it turns out you now get a coded error that's bigger than if you employed no 132 00:12:05,200 --> 00:12:08,604 code. So the efficiency of this is way too 133 00:12:08,604 --> 00:12:12,686 small, it's only one third, and that really hurts. 134 00:12:12,686 --> 00:12:18,877 So efficiency of this code is 4 7th. That's better but we, you want that 135 00:12:18,877 --> 00:12:23,627 efficiency even better to get more, gain in the [unknown]. 136 00:12:23,627 --> 00:12:30,777 Let me talk about what a 7 4 code is and what in particular what this hamming code 137 00:12:30,777 --> 00:12:33,576 is . What constitutes a hamming code and I'll 138 00:12:33,576 --> 00:12:38,779 show you how the efficiency can go up. So as we've seen in a, in a N K code the 139 00:12:38,779 --> 00:12:45,103 number of single bid errors is equal to the lenght of the code word which is N 140 00:12:45,103 --> 00:12:50,676 bit. Okay, now the number of nonzero values for 141 00:12:50,676 --> 00:12:55,354 H times C hat is 2 to the N minus K minus 1. 142 00:12:56,670 --> 00:13:01,569 N minus one is because we exclude the all zero sequence because that means no errors 143 00:13:01,569 --> 00:13:06,514 occurred. So, the dimension of S is N minus K and 144 00:13:06,514 --> 00:13:16,738 the number of numbers you can express in N minus K bits of course is 2 to the N minus 145 00:13:16,738 --> 00:13:22,142 K, tip off the minus 1. And that's the number of non zero values, 146 00:13:22,142 --> 00:13:27,537 so that's the number of possible values for S at which it better be greater than 147 00:13:27,537 --> 00:13:32,642 the number of single bit errors. We couldn't form that table neatly so 148 00:13:32,642 --> 00:13:38,739 that's the result we have to have in order to correct all single bit errors we have 149 00:13:38,739 --> 00:13:43,855 to have this property. The question to point is we get a maximum 150 00:13:43,855 --> 00:13:51,570 efficient code when we apply equality. So what values of N and K work? 151 00:13:51,570 --> 00:13:56,863 So we have this maximum efficient code and when you have that occur, you have what 152 00:13:56,863 --> 00:14:01,676 are called the Hamming codes. So, the thing to note is, in this 153 00:14:01,676 --> 00:14:06,135 expression. That n here, has to be a power of 2 minus 154 00:14:06,135 --> 00:14:09,885 1. So all I did in, in this table was form, 155 00:14:09,885 --> 00:14:15,183 list the powers of 2 minus 1. So this is 2 squared minus 1. 156 00:14:15,183 --> 00:14:21,078 2 cubed minus 1, et cetera. And then search for a value of K that 157 00:14:21,078 --> 00:14:24,587 works. It turns out 1 always can be found. 158 00:14:24,588 --> 00:14:30,040 And you can see that, as you make the code word longer, the efficiency goes up and up 159 00:14:30,040 --> 00:14:33,452 and up. Look at that for any 63 code, the 160 00:14:33,452 --> 00:14:38,266 efficiency is 90%. So we're only cutting down the, a bit 161 00:14:38,266 --> 00:14:41,110 interval by 10%. Which is really nice. 162 00:14:41,110 --> 00:14:45,160 Which means we're really going to gain over using the old coding. 163 00:14:45,160 --> 00:14:51,668 These error correcting coding. Probably, all those bits are being in 164 00:14:51,668 --> 00:14:55,957 there after decoding is really, really small. 165 00:14:55,958 --> 00:15:03,689 So, that's great but there's a problem. And we've seen that the Hamming code, 166 00:15:03,689 --> 00:15:08,724 which is very efficient can correct all single bit errors. 167 00:15:08,724 --> 00:15:14,360 But, if you make the code longer and longer, double bit errors may become more 168 00:15:14,360 --> 00:15:19,661 probable than single bit errors. When a double-bit error occurs in a 169 00:15:19,661 --> 00:15:25,772 Hamming code, it is only designed to correct single-bit errors, and what it 170 00:15:25,772 --> 00:15:32,659 does, it thinks the double-bit error was some strange single-bit error and corrects 171 00:15:32,659 --> 00:15:39,546 accordingly, and usually totally fouls up, and results in a data block is totally 172 00:15:39,546 --> 00:15:42,406 wrong. So, in some sense, the errors become 173 00:15:42,406 --> 00:15:47,021 catastrophic when a double-bit error occurs and we have to figure out when 174 00:15:47,021 --> 00:15:50,670 that's more likely. But if you think about it for a second 175 00:15:50,670 --> 00:15:55,724 some, the longer the code word is, the more likely it is that a double-bit error 176 00:15:55,724 --> 00:16:03,560 will occur rather than a single-bit error. And it's like, you flip a coin that has a 177 00:16:03,560 --> 00:16:08,257 probability of a tenth coming up heads in ten trials. 178 00:16:08,258 --> 00:16:14,107 You sort of expect there to be maybe 1 or 0, but 1 is okay. 179 00:16:14,107 --> 00:16:19,958 If you flipped a million times, what's the probability in that length In a million 180 00:16:19,958 --> 00:16:25,771 flips, only one flip came up heads. Very unlikey, it's much more likely to get 181 00:16:25,771 --> 00:16:29,901 many, many more errors. So that's the situation I'm trying to 182 00:16:29,901 --> 00:16:33,806 analyze here. So, all we have to do is compare the 183 00:16:33,806 --> 00:16:39,216 probability of a single-bit error with a double-bit error. 184 00:16:39,216 --> 00:16:47,604 So, on the left hand side, is the probability of a single bit error's p e, 185 00:16:47,604 --> 00:16:56,074 the probability that all the rest are correct is p e, 1 minus p e n minus 1. 186 00:16:56,074 --> 00:16:59,704 N possible choices. Something similar on the right hand side. 187 00:16:59,705 --> 00:17:11,591 On for the double-bit error. So, we've just simply compare the two and 188 00:17:11,591 --> 00:17:18,691 it's easy to do this compilation, and what you discover is that double-bit errors are 189 00:17:18,691 --> 00:17:24,617 more likely when pe divided by 1 minus pe is greater than 2 over N minus 1. 190 00:17:24,618 --> 00:17:30,381 Well lets assume that pe is small, so we can drop it down makes little bit easier 191 00:17:30,381 --> 00:17:34,692 to see what's going on. So as long as, when ever pe gets greater 192 00:17:34,692 --> 00:17:38,762 than 2 over N minus 1 double-bit errors are much more likely. 193 00:17:38,762 --> 00:17:47,275 But you can see as N gets big, really big, and that can, fall below the[UNKNOWN] 194 00:17:47,275 --> 00:17:51,975 error that you get. So this means that we, despite the fact we 195 00:17:51,975 --> 00:17:57,426 can have a very efficient single bit error correcting code where it may not work all 196 00:17:57,426 --> 00:18:01,116 the time. And certainly even in the 74 code, we 197 00:18:01,116 --> 00:18:08,234 talked about we only have saving database. It is, it is a nonzero probability that 2 198 00:18:08,234 --> 00:18:12,387 bits can arrive in error. So it may be a nice code in that it can 199 00:18:12,387 --> 00:18:15,619 correct those single-bit errors, but it can't correct them all. 200 00:18:15,620 --> 00:18:20,365 Well, how do you correct them all? Well, it turns out you have to make the 201 00:18:20,365 --> 00:18:25,275 code word longer and longer and longer. Well, do, do we, can we find a code that 202 00:18:25,275 --> 00:18:28,085 can correct, no matter how many errors there are? 203 00:18:28,086 --> 00:18:34,486 And that turns out to be our only problem. So, error correcting codes. 204 00:18:34,486 --> 00:18:39,971 Yet we have seen, the good is, is that, even though the channel can introduce 205 00:18:39,971 --> 00:18:44,697 errors in the transmission because the channel flips the bits. 206 00:18:44,698 --> 00:18:48,670 Error correcting codes can repair the errors as long as there aren't too many of 207 00:18:48,670 --> 00:18:51,590 them. However, it would seem that no matter what 208 00:18:51,590 --> 00:18:57,152 we do the errors are always going to be present in digital communication problems. 209 00:18:57,152 --> 00:19:01,728 Well now this is where a somewhat surprising result comes up. 210 00:19:01,728 --> 00:19:08,534 [unknown] his 1948 paper showed that it is possible to send bits through a channel 211 00:19:08,534 --> 00:19:15,739 that introduces error and find an error correcting code that fixes all the errors. 212 00:19:15,740 --> 00:19:18,210 And here's a theory general criterian for that. 213 00:19:18,210 --> 00:19:20,433 And that's what we're going to talk about next.