1 00:00:00,000 --> 00:00:00,560 2 00:00:00,560 --> 00:00:03,580 PROFESSOR: This time we're actually going to be able to 3 00:00:03,580 --> 00:00:06,070 do a little work that I hope will give you a good idea of 4 00:00:06,070 --> 00:00:10,150 why it is that at least low-density parity-check codes 5 00:00:10,150 --> 00:00:17,510 work and even broader classes of capacity-achieving codes. 6 00:00:17,510 --> 00:00:20,755 But I think we're going to limit ourselves to a week, so 7 00:00:20,755 --> 00:00:24,050 that we can say something next week about everything we've 8 00:00:24,050 --> 00:00:27,270 been talking about as binary codes for the power limited 9 00:00:27,270 --> 00:00:29,520 additive white Gaussian noise channel. 10 00:00:29,520 --> 00:00:33,090 We've completely left aside codes for the bandwidth 11 00:00:33,090 --> 00:00:34,960 limited channel, where we're going to have to talk about 12 00:00:34,960 --> 00:00:37,120 non-binary codes of some kind. 13 00:00:37,120 --> 00:00:41,940 So next week I'll give you a very rushed overview of that 14 00:00:41,940 --> 00:00:43,640 kind of code. 15 00:00:43,640 --> 00:00:50,290 And it's my intention, by the way, that last week, you'll 16 00:00:50,290 --> 00:00:54,310 not be held responsible for on the exams, so that we kind 17 00:00:54,310 --> 00:00:58,760 have a nice, pleasant week without worrying about whether 18 00:00:58,760 --> 00:01:01,430 we're responsible for it or not. 19 00:01:01,430 --> 00:01:04,569 And the last homework set, I will prepare a homework set on 20 00:01:04,569 --> 00:01:06,230 the bandwidth limited type codes. 21 00:01:06,230 --> 00:01:10,690 On Wednesday, I'll hand it out, but I won't expect you to 22 00:01:10,690 --> 00:01:11,340 give it back. 23 00:01:11,340 --> 00:01:13,210 It's good to do it. 24 00:01:13,210 --> 00:01:18,600 I'll hand out solutions on the final day of the exam. 25 00:01:18,600 --> 00:01:20,600 OK, so any questions about where we 26 00:01:20,600 --> 00:01:23,940 are, what we're doing? 27 00:01:23,940 --> 00:01:26,680 All right, let's get into it. 28 00:01:26,680 --> 00:01:31,130 We've been building up to this for a while. 29 00:01:31,130 --> 00:01:33,780 First we did trellis 30 00:01:33,780 --> 00:01:37,030 representations of block codes. 31 00:01:37,030 --> 00:01:40,570 As a warm-up for codes on graphs, we found that some of 32 00:01:40,570 --> 00:01:44,180 the things we discovered about trellises were important 33 00:01:44,180 --> 00:01:46,380 particularly in the context of the cut-set bound. 34 00:01:46,380 --> 00:01:50,100 The cut-set bound says, where you have a cut-set, the 35 00:01:50,100 --> 00:01:53,490 complexity at that point must be at least as great as that 36 00:01:53,490 --> 00:01:57,720 of a trellis diagram which divides the two parts of the 37 00:01:57,720 --> 00:02:00,360 code into two halves, and the past and 38 00:02:00,360 --> 00:02:02,370 future in the same way. 39 00:02:02,370 --> 00:02:04,430 And from that we concluded that we're 40 00:02:04,430 --> 00:02:05,520 going to need cycles. 41 00:02:05,520 --> 00:02:08,639 Because we'd already proved back in chapter 10 that 42 00:02:08,639 --> 00:02:13,890 trellis complexity needed to go up exponentially with block 43 00:02:13,890 --> 00:02:17,500 length, at least for codes that maintained a nonzero 44 00:02:17,500 --> 00:02:20,030 relative minimum distance as well as a 45 00:02:20,030 --> 00:02:22,490 nonzero relative rate. 46 00:02:22,490 --> 00:02:25,180 So we're going to need cycles in our graph we think -- 47 00:02:25,180 --> 00:02:27,120 to get to capacity. 48 00:02:27,120 --> 00:02:30,700 Chapter 12 was a fairly short chapter introducing the 49 00:02:30,700 --> 00:02:31,960 sum-product algorithm. 50 00:02:31,960 --> 00:02:34,240 I believe that you don't really understand the 51 00:02:34,240 --> 00:02:37,720 sum-product algorithm till you do it once, so that's on this 52 00:02:37,720 --> 00:02:38,540 week's homework. 53 00:02:38,540 --> 00:02:41,700 You will do it once for a very simple case, and then I think 54 00:02:41,700 --> 00:02:42,950 you'll understand it. 55 00:02:42,950 --> 00:02:46,900 56 00:02:46,900 --> 00:02:51,230 We developed the sum-product algorithm for cycle-free 57 00:02:51,230 --> 00:02:54,990 graphs, where it's a theorem that the sum-product algorithm 58 00:02:54,990 --> 00:02:59,600 does APP decoding for every variable in any cycle-free 59 00:02:59,600 --> 00:03:02,890 graph in a very systematic and efficient way. 60 00:03:02,890 --> 00:03:05,810 It's a finite and exact algorithm in that case. 61 00:03:05,810 --> 00:03:08,830 It takes a number of steps approximately equal to 62 00:03:08,830 --> 00:03:10,260 diameter of the graph. 63 00:03:10,260 --> 00:03:12,950 And when it's finished you have the exact APPs 64 00:03:12,950 --> 00:03:14,200 everywhere. 65 00:03:14,200 --> 00:03:16,160 66 00:03:16,160 --> 00:03:19,305 OK, but we really want to have a decoding algorithm for 67 00:03:19,305 --> 00:03:20,930 graphs with cycles. 68 00:03:20,930 --> 00:03:22,910 Having developed the sum-product decoding 69 00:03:22,910 --> 00:03:28,490 algorithm, we see that it has a nice, simple update rule at 70 00:03:28,490 --> 00:03:31,050 each computation node. 71 00:03:31,050 --> 00:03:33,630 It's a local kind of algorithm. 72 00:03:33,630 --> 00:03:36,990 Why don't we just let her rip, start it off 73 00:03:36,990 --> 00:03:38,590 and see how it does? 74 00:03:38,590 --> 00:03:44,450 And, in our case, we can make that work by designing graphs 75 00:03:44,450 --> 00:03:48,990 that have, in particular, very large girths such that the 76 00:03:48,990 --> 00:03:50,320 graph looks-- 77 00:03:50,320 --> 00:03:53,200 the term-of-art is locally tree-like. 78 00:03:53,200 --> 00:03:59,140 In the neighborhood of any node, if you go out some fixed 79 00:03:59,140 --> 00:04:02,530 diameter from that node, you won't run into any repetition. 80 00:04:02,530 --> 00:04:05,760 So locally the graph looks like a tree. 81 00:04:05,760 --> 00:04:08,700 And we're going to, ultimately, be looking at 82 00:04:08,700 --> 00:04:12,770 asymptotically long codes, so we'll be able to make that 83 00:04:12,770 --> 00:04:15,470 locally tree-like assumption hold for as far 84 00:04:15,470 --> 00:04:18,829 out as we need to. 85 00:04:18,829 --> 00:04:21,630 Other disciplines are not so fortunate as to 86 00:04:21,630 --> 00:04:23,650 be able to do that. 87 00:04:23,650 --> 00:04:27,700 OK, so in this chapter we're finally going to get capacity 88 00:04:27,700 --> 00:04:29,542 approaching codes. 89 00:04:29,542 --> 00:04:33,080 I'm first just going to mention a couple of classes of 90 00:04:33,080 --> 00:04:37,280 codes, the most famous and important ones, show you what 91 00:04:37,280 --> 00:04:39,940 their graphs look like. 92 00:04:39,940 --> 00:04:44,430 From that, you will know everything up to schedule what 93 00:04:44,430 --> 00:04:48,670 there sum-product decoding algorithm should be. 94 00:04:48,670 --> 00:04:51,610 I'll tell you what the conventional schedules for 95 00:04:51,610 --> 00:04:56,750 decoding these graphs with cycles are. 96 00:04:56,750 --> 00:04:59,200 And that'll be an introduction. 97 00:04:59,200 --> 00:05:04,620 And then we'll get into actual analysis, in particular, for 98 00:05:04,620 --> 00:05:07,910 low-density parity-check codes which are, really, the 99 00:05:07,910 --> 00:05:09,950 simplest of these codes and therefore the 100 00:05:09,950 --> 00:05:12,160 most amenable to analysis. 101 00:05:12,160 --> 00:05:15,010 And we'll see that, under the locally tree-like assumption, 102 00:05:15,010 --> 00:05:18,080 we can do an exact analysis first, on the 103 00:05:18,080 --> 00:05:19,830 binary erasure channel. 104 00:05:19,830 --> 00:05:22,500 Then I'll at least discuss what's involved on more 105 00:05:22,500 --> 00:05:27,590 general channels, where we can do a fairly precise analysis. 106 00:05:27,590 --> 00:05:31,100 So that's where we're going in chapter 13. 107 00:05:31,100 --> 00:05:32,350 Questions, comments? 108 00:05:32,350 --> 00:05:34,800 109 00:05:34,800 --> 00:05:37,590 OK, so let's talk about low-density 110 00:05:37,590 --> 00:05:40,390 parity-check codes. 111 00:05:40,390 --> 00:05:44,500 These codes have a fascinating history. 112 00:05:44,500 --> 00:05:49,240 They were invented by Professor Gallager in his 113 00:05:49,240 --> 00:05:52,910 doctoral thesis in 1961. 114 00:05:52,910 --> 00:05:54,930 He was a student of Peter Elias. 115 00:05:54,930 --> 00:05:57,810 What people were doing at MIT then was trying to figure out 116 00:05:57,810 --> 00:06:02,250 ways to actually build codes that get to capacity. 117 00:06:02,250 --> 00:06:06,880 At MIT the emphasis was on so called probabilistic codes. 118 00:06:06,880 --> 00:06:11,780 Namely ones that had sort of the random-like elements that 119 00:06:11,780 --> 00:06:14,090 Shannon basically prescribed. 120 00:06:14,090 --> 00:06:15,520 People here were not so interested in 121 00:06:15,520 --> 00:06:18,910 the algebraic codes. 122 00:06:18,910 --> 00:06:27,705 And Gallager basically had the idea that if you take a code 123 00:06:27,705 --> 00:06:30,160 -- you can describe it by a generator matrix or 124 00:06:30,160 --> 00:06:31,710 parity-check matrix. 125 00:06:31,710 --> 00:06:34,870 If you make a sparse generator matrix, that's not going to be 126 00:06:34,870 --> 00:06:37,920 any good, a random, sparse generator matrix, because a 127 00:06:37,920 --> 00:06:41,170 sparse generator matrix will naturally have some low-weight 128 00:06:41,170 --> 00:06:42,475 code words in it. 129 00:06:42,475 --> 00:06:44,910 If the rows are sparse, then it will have 130 00:06:44,910 --> 00:06:47,680 low, minimum distance. 131 00:06:47,680 --> 00:06:52,940 But maybe if we make the parity-check matrix sparse, 132 00:06:52,940 --> 00:06:55,890 very few ones in the parity-check matrix, we can 133 00:06:55,890 --> 00:06:59,660 still get a code that's quasi-random. 134 00:06:59,660 --> 00:07:05,100 And therefore we can hope that the codes, as they get along, 135 00:07:05,100 --> 00:07:08,700 will come close to doing what Shannon said random codes 136 00:07:08,700 --> 00:07:10,840 should easily be able to do. 137 00:07:10,840 --> 00:07:13,515 The amazing thing about Shannon's proof is he showed 138 00:07:13,515 --> 00:07:16,140 that you pick any code out of a hat, and it's highly likely 139 00:07:16,140 --> 00:07:17,340 to be good. 140 00:07:17,340 --> 00:07:22,110 So, basically, Gallager was trying to replicate that. 141 00:07:22,110 --> 00:07:25,600 And he came up the idea of sparse or low-density 142 00:07:25,600 --> 00:07:32,290 parity-check matrices and was able to prove quite a few 143 00:07:32,290 --> 00:07:33,810 things about them. 144 00:07:33,810 --> 00:07:36,460 That they couldn't quite get to capacity the way he 145 00:07:36,460 --> 00:07:39,270 formulated them, but that they could get very close. 146 00:07:39,270 --> 00:07:42,350 They had a threshold a little bit below capacity. 147 00:07:42,350 --> 00:07:45,780 He came up with the APP decoding algorithm for them 148 00:07:45,780 --> 00:07:49,170 which is probably the first instance of the sum-product 149 00:07:49,170 --> 00:07:51,640 algorithm in any literature, certainly the first 150 00:07:51,640 --> 00:07:54,150 that I'm aware of. 151 00:07:54,150 --> 00:07:57,340 And he simulated them. 152 00:07:57,340 --> 00:08:00,380 At that time, what MIT had was-- 153 00:08:00,380 --> 00:08:04,890 over in Building 26 on the first floor, where I think 154 00:08:04,890 --> 00:08:05,950 there's a library now. 155 00:08:05,950 --> 00:08:08,350 It sticks out into the adjacent parking lot. 156 00:08:08,350 --> 00:08:13,360 That room was full of IBM equipment, 70, 90 computer. 157 00:08:13,360 --> 00:08:14,980 And there were people in white coats who 158 00:08:14,980 --> 00:08:16,780 attended all that equipment. 159 00:08:16,780 --> 00:08:20,370 And by running that computer for hours, he was able to 160 00:08:20,370 --> 00:08:22,760 simulate low-density parity-check codes down to an 161 00:08:22,760 --> 00:08:25,540 error probability of about ten to the minus fourth. 162 00:08:25,540 --> 00:08:30,360 And he showed that he could get down to 10 to the minus 163 00:08:30,360 --> 00:08:32,650 fourth, pretty close to capacity. 164 00:08:32,650 --> 00:08:35,470 I don't remember exactly how close, but it was enough to be 165 00:08:35,470 --> 00:08:36,720 convincing. 166 00:08:36,720 --> 00:08:39,720 167 00:08:39,720 --> 00:08:43,340 Actually, in 1962 there was a little company form called 168 00:08:43,340 --> 00:08:44,590 Codex Corporation. 169 00:08:44,590 --> 00:08:47,300 170 00:08:47,300 --> 00:08:49,490 It was what we would now call a start-up. 171 00:08:49,490 --> 00:08:53,670 Back then, there was no tradition of start-ups. 172 00:08:53,670 --> 00:08:58,570 And it was basically founded to exploit Gallager's patents, 173 00:08:58,570 --> 00:09:00,550 which he took out on low-density parity-check 174 00:09:00,550 --> 00:09:04,360 codes, and Jim Massey's patents on threshold decoding, 175 00:09:04,360 --> 00:09:07,430 which is an extremely simple decoding technique that we 176 00:09:07,430 --> 00:09:10,980 haven't even talked about, very low complexity. 177 00:09:10,980 --> 00:09:15,130 And I joined that company in 1965 when I finish my thesis. 178 00:09:15,130 --> 00:09:18,030 And I was director of research and advanced product planning. 179 00:09:18,030 --> 00:09:21,030 And I can assure you that in the 20 years that those 180 00:09:21,030 --> 00:09:24,040 patents lived, we never considered once using 181 00:09:24,040 --> 00:09:26,130 Gallager's low-density parity-check codes, because 182 00:09:26,130 --> 00:09:30,140 they were obviously far too complicated for the technology 183 00:09:30,140 --> 00:09:32,160 of the '60s and '70s. 184 00:09:32,160 --> 00:09:36,600 We didn't have rooms full of computers to decode them. 185 00:09:36,600 --> 00:09:40,860 And more generally, in the community, they were pretty 186 00:09:40,860 --> 00:09:43,640 completely forgotten about. 187 00:09:43,640 --> 00:09:47,280 There's a key paper by Michael Tanner in 1981 188 00:09:47,280 --> 00:09:49,380 where he kind of-- 189 00:09:49,380 --> 00:09:52,360 that's the founding paper for the field of codes on graphs. 190 00:09:52,360 --> 00:09:54,880 he puts it all into a codes-on-graphs context, 191 00:09:54,880 --> 00:09:56,710 develops all the basic results. 192 00:09:56,710 --> 00:09:57,540 It's a great paper. 193 00:09:57,540 --> 00:09:59,570 It too, was forgotten about. 194 00:09:59,570 --> 00:10:05,180 And the whole thing was pretty much forgotten about by us 195 00:10:05,180 --> 00:10:08,440 until other people, outside the community, rediscovered it 196 00:10:08,440 --> 00:10:10,740 right after turbo codes were invented. 197 00:10:10,740 --> 00:10:15,750 Turbo codes were first presented in 1993 198 00:10:15,750 --> 00:10:17,730 at the ICC in Geneva. 199 00:10:17,730 --> 00:10:20,430 They had actually been invented some four or five 200 00:10:20,430 --> 00:10:25,350 years before that by Claude Berrou in France. 201 00:10:25,350 --> 00:10:29,140 And nobody could believe how good the performance was. 202 00:10:29,140 --> 00:10:31,690 This guy is not even a communications guy. 203 00:10:31,690 --> 00:10:35,590 He must have made a three dB mistake, didn't 204 00:10:35,590 --> 00:10:39,030 divide by two somewhere. 205 00:10:39,030 --> 00:10:42,260 He showed you could get within about a dB of capacity with 206 00:10:42,260 --> 00:10:43,370 two simple codes. 207 00:10:43,370 --> 00:10:46,700 And we'll see that in a second. 208 00:10:46,700 --> 00:10:51,830 But, sure enough, people went and verified that these codes 209 00:10:51,830 --> 00:10:53,870 work the way he said they did. 210 00:10:53,870 --> 00:10:56,830 And, all of a sudden, there's an explosion of interest. 211 00:10:56,830 --> 00:11:01,010 And low-density parity-check codes were rediscovered by a 212 00:11:01,010 --> 00:11:06,290 couple of people, notably David MacKay who also was a 213 00:11:06,290 --> 00:11:10,380 physicist like Berrou, in England. 214 00:11:10,380 --> 00:11:13,010 But he had an interest in information theory, at least 215 00:11:13,010 --> 00:11:15,050 he was trying to solve the right problem. 216 00:11:15,050 --> 00:11:19,310 And he had similar ideas to what Gallager had had. 217 00:11:19,310 --> 00:11:22,450 And he simulated them-- by now, you can simulate these 218 00:11:22,450 --> 00:11:25,430 codes on a desktop computer-- 219 00:11:25,430 --> 00:11:32,080 and found that they got within a dB of capacity and so forth. 220 00:11:32,080 --> 00:11:34,970 And so then we were off to the races, and the whole paradigm 221 00:11:34,970 --> 00:11:36,400 of coding changed. 222 00:11:36,400 --> 00:11:38,990 But it certainly is an embarrassment to those of us 223 00:11:38,990 --> 00:11:43,160 who were faithfully in the field for 30, 35 years. 224 00:11:43,160 --> 00:11:46,790 Why didn't it occur to us that by the '90s the technology was 225 00:11:46,790 --> 00:11:49,910 far enough advanced that we could go back and look at what 226 00:11:49,910 --> 00:11:54,420 Gallager did and realize that these were actually pretty 227 00:11:54,420 --> 00:11:57,360 good codes and now implementable? 228 00:11:57,360 --> 00:11:59,010 So I think that's a nice story. 229 00:11:59,010 --> 00:12:01,840 It's kind of humbling to those of us in the field. 230 00:12:01,840 --> 00:12:05,670 On the other hand, we can say that, jeez, Gallager did it 231 00:12:05,670 --> 00:12:06,790 back in 1960. 232 00:12:06,790 --> 00:12:09,430 What's the big deal about turbo codes? 233 00:12:09,430 --> 00:12:11,152 Depends what perspective you take. 234 00:12:11,152 --> 00:12:17,790 235 00:12:17,790 --> 00:12:21,070 I never know whether I should tell a lot of stories or not 236 00:12:21,070 --> 00:12:24,840 so many stories in this class. 237 00:12:24,840 --> 00:12:27,205 If you like more stories, just ask. 238 00:12:27,205 --> 00:12:30,000 239 00:12:30,000 --> 00:12:31,560 Anyone have any questions at this point? 240 00:12:31,560 --> 00:12:34,060 241 00:12:34,060 --> 00:12:36,085 All right, low-density parity-check codes, Gallager 242 00:12:36,085 --> 00:12:43,660 in 1961, forgotten until 1995, rediscovered by David MacKay, 243 00:12:43,660 --> 00:12:46,370 Niclas Wiberg, and others. 244 00:12:46,370 --> 00:12:50,050 And this was what they look like. 245 00:12:50,050 --> 00:12:54,570 The basic idea is we have a parity-check representation of 246 00:12:54,570 --> 00:12:58,930 the code, a long code. 247 00:12:58,930 --> 00:13:08,760 So the code is the set of all y such that yht equals 0. 248 00:13:08,760 --> 00:13:15,690 249 00:13:15,690 --> 00:13:17,850 And that's standard. 250 00:13:17,850 --> 00:13:22,570 And the idea now is that this parity-check matrix should be 251 00:13:22,570 --> 00:13:24,055 low density or sparse. 252 00:13:24,055 --> 00:13:27,050 253 00:13:27,050 --> 00:13:29,630 In fact, the number of ones in it-- 254 00:13:29,630 --> 00:13:34,370 It's a matrix, so that you would think a random matrix is 255 00:13:34,370 --> 00:13:36,560 0s and ones. 256 00:13:36,560 --> 00:13:40,660 m minus k by n matrix would have a number of ones that 257 00:13:40,660 --> 00:13:43,260 goes up as n squared. 258 00:13:43,260 --> 00:13:47,010 As n becomes large, let's make sure that the number of ones 259 00:13:47,010 --> 00:13:49,580 only goes up linearly with n, as the block 260 00:13:49,580 --> 00:13:52,760 length n becomes large. 261 00:13:52,760 --> 00:14:07,750 So sparse h means number of ones linear with n. 262 00:14:07,750 --> 00:14:11,140 And we'll see that implies that the complexity of the 263 00:14:11,140 --> 00:14:12,830 graph is linear with n. 264 00:14:12,830 --> 00:14:16,360 265 00:14:16,360 --> 00:14:17,970 The ones are going to correspond to the 266 00:14:17,970 --> 00:14:18,920 edges in the graph. 267 00:14:18,920 --> 00:14:21,950 And we'll have a linear number of edges, also a linear number 268 00:14:21,950 --> 00:14:27,160 of nodes or vertices. 269 00:14:27,160 --> 00:14:36,360 OK, in general, what does a code like this look like? 270 00:14:36,360 --> 00:14:41,910 We have y 0, y one through-- 271 00:14:41,910 --> 00:14:45,150 what does its graph look like, I should say-- 272 00:14:45,150 --> 00:14:46,435 yn minus one. 273 00:14:46,435 --> 00:14:49,150 274 00:14:49,150 --> 00:14:54,180 And then, so we're going to have n symbols, which in 275 00:14:54,180 --> 00:14:57,245 normal graphs we write as equals nodes. 276 00:14:57,245 --> 00:15:00,930 Then over here we're going to have n minus k, a lesser 277 00:15:00,930 --> 00:15:05,765 number of constraints or checks, which in our notation 278 00:15:05,765 --> 00:15:08,470 we've been writing like this. 279 00:15:08,470 --> 00:15:11,090 280 00:15:11,090 --> 00:15:16,660 And we're going to have an edge for each one in here. 281 00:15:16,660 --> 00:15:21,800 You can easily see that every one in the parity-check matrix 282 00:15:21,800 --> 00:15:26,440 ensures that it says that one of the symbols participates in 283 00:15:26,440 --> 00:15:27,700 one of the checks. 284 00:15:27,700 --> 00:15:29,795 And therefore, the number of edges is equal to 285 00:15:29,795 --> 00:15:30,490 the number of ones. 286 00:15:30,490 --> 00:15:37,920 So this is equal number of edges in graph. 287 00:15:37,920 --> 00:15:41,340 Not counting these little half edges out over here, again. 288 00:15:41,340 --> 00:15:45,195 So there's some random number of edges. 289 00:15:45,195 --> 00:15:50,825 290 00:15:50,825 --> 00:15:53,180 We won't have them got to the same place. 291 00:15:53,180 --> 00:15:56,160 292 00:15:56,160 --> 00:15:58,970 But this also is only linear with n, here. 293 00:15:58,970 --> 00:16:05,300 294 00:16:05,300 --> 00:16:14,680 And, in fact, let's choose these edges. 295 00:16:14,680 --> 00:16:17,666 These edges are like a telephone switchboard. 296 00:16:17,666 --> 00:16:23,830 It's just a giant plug board where everything that goes out 297 00:16:23,830 --> 00:16:26,100 here, you can consider going into a socket. 298 00:16:26,100 --> 00:16:29,660 299 00:16:29,660 --> 00:16:33,690 So let's draw, for instance, for a regular code, let's draw 300 00:16:33,690 --> 00:16:37,060 the same number of sockets going out 301 00:16:37,060 --> 00:16:38,540 for each of the symbols. 302 00:16:38,540 --> 00:16:40,210 Each symbol is going to participate in the 303 00:16:40,210 --> 00:16:42,070 same number of checks. 304 00:16:42,070 --> 00:16:45,580 Each one is going to have the same degree, so that's why, in 305 00:16:45,580 --> 00:16:47,490 graph terms, it's regular. 306 00:16:47,490 --> 00:16:51,470 And each one of these checks, we're also going to say has 307 00:16:51,470 --> 00:16:52,720 the same degree. 308 00:16:52,720 --> 00:16:55,160 309 00:16:55,160 --> 00:16:58,320 So this was basically the way Gallager 310 00:16:58,320 --> 00:16:59,970 constructed codes, regular. 311 00:16:59,970 --> 00:17:03,010 We'll later see if there's an advantage to making these 312 00:17:03,010 --> 00:17:07,300 somewhat irregular, these degree distributions. 313 00:17:07,300 --> 00:17:11,770 But this is certainly the simplest case. 314 00:17:11,770 --> 00:17:17,859 All right, how do we make a random parity-check code? 315 00:17:17,859 --> 00:17:20,380 So that we're going to specify n, n minus k. 316 00:17:20,380 --> 00:17:24,460 We're going to specify these degrees. 317 00:17:24,460 --> 00:17:26,440 So that's not random. 318 00:17:26,440 --> 00:17:32,840 But we'll connect the edges through a big switch board 319 00:17:32,840 --> 00:17:39,660 which is denoted by pi, which stands for permutations. 320 00:17:39,660 --> 00:17:42,250 This is basically just a permutation. 321 00:17:42,250 --> 00:17:44,740 We've got to have the same number of sockets on this side 322 00:17:44,740 --> 00:17:46,000 as on this side. 323 00:17:46,000 --> 00:17:48,780 And this is a just a reordering of these sockets. 324 00:17:48,780 --> 00:17:51,580 That's what a telephone switchboard does. 325 00:17:51,580 --> 00:17:57,130 Or it's very often in the literature called an 326 00:17:57,130 --> 00:18:02,160 interleaver, but, probably, permutation would've been a 327 00:18:02,160 --> 00:18:04,150 better word. 328 00:18:04,150 --> 00:18:11,840 All right, so one way of doing it is just to take this edge 329 00:18:11,840 --> 00:18:17,640 here, this socket here and, at random, we have-- let's say, 330 00:18:17,640 --> 00:18:22,080 e, for number of edges-- e sockets over here and just 331 00:18:22,080 --> 00:18:25,610 pick one of those sockets at random. 332 00:18:25,610 --> 00:18:29,170 Take the next one and take the e minus one that are left and 333 00:18:29,170 --> 00:18:32,930 connect that to one of the the e minus one at random. 334 00:18:32,930 --> 00:18:38,160 So this would give you one of the e factorial permutations 335 00:18:38,160 --> 00:18:39,410 of e objects. 336 00:18:39,410 --> 00:18:42,110 337 00:18:42,110 --> 00:18:44,710 And it'll give you one of them equiprobably. 338 00:18:44,710 --> 00:18:48,240 So we're basically talking about an equiprobable 339 00:18:48,240 --> 00:18:54,570 distribution over all possible permutations of e elements. 340 00:18:54,570 --> 00:18:58,350 All right, so we consider all these are equally likely when 341 00:18:58,350 --> 00:19:00,530 we come to our analysis. 342 00:19:00,530 --> 00:19:03,860 This is why these codes are called probabilistic. 343 00:19:03,860 --> 00:19:07,900 We set up some elements of their structure, but then let 344 00:19:07,900 --> 00:19:10,770 others be chosen randomly. 345 00:19:10,770 --> 00:19:13,310 Clearly it's not going to matter for the complexity of 346 00:19:13,310 --> 00:19:15,590 the decoding algorithm how this is done. 347 00:19:15,590 --> 00:19:17,490 It might have something to do with the performance of the 348 00:19:17,490 --> 00:19:21,560 decoding algorithm, but any decoding algorithm is going to 349 00:19:21,560 --> 00:19:22,460 work the same way. 350 00:19:22,460 --> 00:19:24,970 It's just a matter of when you send a message in here, where 351 00:19:24,970 --> 00:19:27,610 does it come out here or vice versa. 352 00:19:27,610 --> 00:19:29,410 So it doesn't really affect complexity. 353 00:19:29,410 --> 00:19:33,100 354 00:19:33,100 --> 00:19:38,530 Let's see, there has to be some relation between the left 355 00:19:38,530 --> 00:19:45,490 degree d lambda and the right degree d rho here in order 356 00:19:45,490 --> 00:19:49,620 that we have the same number of edges on each side. 357 00:19:49,620 --> 00:19:57,370 We have e equals n times d lambda, if we 358 00:19:57,370 --> 00:19:59,410 look at the left side. 359 00:19:59,410 --> 00:20:05,360 But it's also equal to n minus k times the degree on the 360 00:20:05,360 --> 00:20:06,670 right side. 361 00:20:06,670 --> 00:20:09,300 Again, I'm only counting the internal degree here and 362 00:20:09,300 --> 00:20:13,460 leaving aside the external guy. 363 00:20:13,460 --> 00:20:19,020 And this gives us the following relationship that n 364 00:20:19,020 --> 00:20:27,850 minus k over n is equal d lambda over d rho. 365 00:20:27,850 --> 00:20:32,310 Or, equivalently, with this is one minus the rate of the 366 00:20:32,310 --> 00:20:38,850 code, or we can write rate equals one minus d 367 00:20:38,850 --> 00:20:40,250 lambda over d rho. 368 00:20:40,250 --> 00:20:42,770 369 00:20:42,770 --> 00:20:46,490 So that by deciding what left degree and what right degree 370 00:20:46,490 --> 00:20:51,160 to have, we're basically enforcing this relationship 371 00:20:51,160 --> 00:20:54,130 which comes out as the rate of the code. 372 00:20:54,130 --> 00:20:56,990 For instance, the choice that we're going to talk about 373 00:20:56,990 --> 00:20:59,430 throughout is we're going to take a left degree equal to 374 00:20:59,430 --> 00:21:03,200 three, right degree equal to six, as I drew it. 375 00:21:03,200 --> 00:21:06,000 If you do that, then you're going to get a code of 376 00:21:06,000 --> 00:21:07,250 nominal rate 1/2. 377 00:21:07,250 --> 00:21:10,380 378 00:21:10,380 --> 00:21:12,990 It's only a nominal rate because what 379 00:21:12,990 --> 00:21:14,240 could happen here? 380 00:21:14,240 --> 00:21:17,000 381 00:21:17,000 --> 00:21:19,650 I'm basically choosing a random parity-check matrix, 382 00:21:19,650 --> 00:21:24,020 and there's nothing that ensures that all the rows of 383 00:21:24,020 --> 00:21:27,020 this parity-check matrix are going to be independent. 384 00:21:27,020 --> 00:21:31,870 So I could have fewer than n minus k independent rows in 385 00:21:31,870 --> 00:21:35,730 the matrix, which would actually mean the rate would 386 00:21:35,730 --> 00:21:39,960 be higher than my design rate, my nominal rate. 387 00:21:39,960 --> 00:21:42,755 In fact, you can ignore this possibility. 388 00:21:42,755 --> 00:21:45,690 389 00:21:45,690 --> 00:21:48,590 It's very low probability even if you choose it at random. 390 00:21:48,590 --> 00:21:51,350 If it does happen, people are going to forget about the 391 00:21:51,350 --> 00:21:55,040 dependent row and pick another independent row. 392 00:21:55,040 --> 00:21:58,490 So I won't make a big deal. 393 00:21:58,490 --> 00:22:00,690 We'll just call this the rate. 394 00:22:00,690 --> 00:22:03,760 395 00:22:03,760 --> 00:22:10,510 So if this were three here but only four here, then we would 396 00:22:10,510 --> 00:22:12,030 have a rate 1/4 code. 397 00:22:12,030 --> 00:22:14,690 398 00:22:14,690 --> 00:22:17,790 Well, we'd have to have 3/4s as many checks as we have 399 00:22:17,790 --> 00:22:23,040 symbols in order for everything to add up. 400 00:22:23,040 --> 00:22:26,210 401 00:22:26,210 --> 00:22:30,310 So that's really, basically, it. 402 00:22:30,310 --> 00:22:36,280 Let's just specify the degrees on the left, the degree on the 403 00:22:36,280 --> 00:22:44,120 right, pick our permutation at random, pick n or e. 404 00:22:44,120 --> 00:22:49,150 We've designed a low-density parity-check code. 405 00:22:49,150 --> 00:22:52,661 And now, how do we do we decode it? 406 00:22:52,661 --> 00:22:56,098 407 00:22:56,098 --> 00:22:58,130 Well, we use the sum-product algorithm. 408 00:22:58,130 --> 00:22:59,680 We've got a code on a graph. 409 00:22:59,680 --> 00:23:02,370 In fact, it's a very simple graph, notice it's 410 00:23:02,370 --> 00:23:03,220 characteristic. 411 00:23:03,220 --> 00:23:08,530 It's, again, just got equality nodes and zero-sum nodes or 412 00:23:08,530 --> 00:23:09,420 check nodes. 413 00:23:09,420 --> 00:23:12,770 These are really the simplest codes. 414 00:23:12,770 --> 00:23:16,450 We could, more generally, have more elaborate codes here. 415 00:23:16,450 --> 00:23:20,930 That's one of the things Tanner did in is 1981 paper. 416 00:23:20,930 --> 00:23:24,910 But this is very simple. 417 00:23:24,910 --> 00:23:27,360 All of our internal variables are binary. 418 00:23:27,360 --> 00:23:29,990 419 00:23:29,990 --> 00:23:32,360 I, for one, thought that it would be necessary to go 420 00:23:32,360 --> 00:23:35,160 beyond binary internal variables in order to get to 421 00:23:35,160 --> 00:23:38,810 capacity but that proved not to be the case. 422 00:23:38,810 --> 00:23:42,180 Really, this structure is all you need to get to 423 00:23:42,180 --> 00:23:43,520 capacity it turns out. 424 00:23:43,520 --> 00:23:46,030 Except for one thing, you need to make 425 00:23:46,030 --> 00:23:49,640 these degrees irregular. 426 00:23:49,640 --> 00:23:51,760 And for the most part, you only need to make the left 427 00:23:51,760 --> 00:23:54,620 degrees irregular. 428 00:23:54,620 --> 00:23:58,320 So we'll get far enough to see why that is 429 00:23:58,320 --> 00:23:59,570 going to do the trick. 430 00:23:59,570 --> 00:24:01,920 431 00:24:01,920 --> 00:24:04,630 But right now, I talked about the decoding algorithm. 432 00:24:04,630 --> 00:24:07,930 So the decoding algorithm is pretty much what you would 433 00:24:07,930 --> 00:24:08,880 think, I would hope. 434 00:24:08,880 --> 00:24:11,910 Now that you've seen some product decoding. 435 00:24:11,910 --> 00:24:14,980 You receive something on each of these lines, depending what 436 00:24:14,980 --> 00:24:16,910 the channel is. 437 00:24:16,910 --> 00:24:19,140 If it's an additive white Gaussian noise channel, you 438 00:24:19,140 --> 00:24:23,710 get a real number, received vector that gives you some 439 00:24:23,710 --> 00:24:28,550 intrinsic information about the relative likelihoods of 0 440 00:24:28,550 --> 00:24:30,240 and one on each of these lines. 441 00:24:30,240 --> 00:24:34,520 So each of these points, you get an in going message based 442 00:24:34,520 --> 00:24:37,160 on what you receive. 443 00:24:37,160 --> 00:24:44,270 At a repetition node that message is simply propagated, 444 00:24:44,270 --> 00:24:48,030 if you look at the equations of the sum-product algorithm. 445 00:24:48,030 --> 00:24:51,480 Repetition nodes just propagate what they receive at 446 00:24:51,480 --> 00:24:53,940 one terminal on all the output terminals. 447 00:24:53,940 --> 00:24:56,630 448 00:24:56,630 --> 00:24:58,800 All the d minus one terminals are determined 449 00:24:58,800 --> 00:24:59,940 by the by one terminal. 450 00:24:59,940 --> 00:25:03,180 So we get the same thing going as and output message. 451 00:25:03,180 --> 00:25:06,360 This, very often, is drawn as a Tanner graph. 452 00:25:06,360 --> 00:25:08,690 In that case, all we have here is symbols. 453 00:25:08,690 --> 00:25:11,260 That's natural to just take the likelihoods of the symbols 454 00:25:11,260 --> 00:25:13,480 and send them out. 455 00:25:13,480 --> 00:25:16,350 So we haven't done anything more than that. 456 00:25:16,350 --> 00:25:21,970 These messages all arrive here as incoming messages from 457 00:25:21,970 --> 00:25:23,640 various far and distant lands. 458 00:25:23,640 --> 00:25:30,090 459 00:25:30,090 --> 00:25:33,050 To find the outgoing message say, on this line 460 00:25:33,050 --> 00:25:34,360 here, what's our rule? 461 00:25:34,360 --> 00:25:37,890 462 00:25:37,890 --> 00:25:43,410 Our rule is to take the incoming messages on all d 463 00:25:43,410 --> 00:25:48,920 minus one of these nodes and combine their likelihoods 464 00:25:48,920 --> 00:25:54,710 according to which of these is consistent with a 0 output 465 00:25:54,710 --> 00:25:56,370 here, and which of these is consistent with the 466 00:25:56,370 --> 00:25:57,750 one going out here. 467 00:25:57,750 --> 00:25:59,830 We get a bunch of weights for 0, and a bunch 468 00:25:59,830 --> 00:26:00,740 of weights for one. 469 00:26:00,740 --> 00:26:02,000 We add them all up. 470 00:26:02,000 --> 00:26:07,290 And that gives us now, a re-computed likelihood. 471 00:26:07,290 --> 00:26:11,030 A message consisting of probability of 0 given what 472 00:26:11,030 --> 00:26:13,390 we've seen so far, and probability of one given what 473 00:26:13,390 --> 00:26:14,740 we've seen so far. 474 00:26:14,740 --> 00:26:16,550 But now it goes out. 475 00:26:16,550 --> 00:26:21,740 Hopefully that's got some improved information in it now 476 00:26:21,740 --> 00:26:26,280 coming from all different parts of the graph, extrinsic. 477 00:26:26,280 --> 00:26:30,430 So this, eventually, will come back somewhere say, here and 478 00:26:30,430 --> 00:26:33,230 similarly on all the other lines. 479 00:26:33,230 --> 00:26:40,000 And now this will give you additional information. 480 00:26:40,000 --> 00:26:44,340 You combine these, and now what you have coming out here 481 00:26:44,340 --> 00:26:47,590 is a combination of what you had coming in here, which was 482 00:26:47,590 --> 00:26:51,930 originally a state of complete ignorance, but now you combine 483 00:26:51,930 --> 00:26:58,330 these you get more information going out and so forth. 484 00:26:58,330 --> 00:26:59,510 So you iterate. 485 00:26:59,510 --> 00:27:03,090 You basically do a left side iteration, then a right side 486 00:27:03,090 --> 00:27:04,505 iteration, a left side iteration, 487 00:27:04,505 --> 00:27:05,890 a right side iteration. 488 00:27:05,890 --> 00:27:11,600 Hopefully the quality of your APP vectors is continually 489 00:27:11,600 --> 00:27:13,400 increasing during this. 490 00:27:13,400 --> 00:27:16,940 You're somehow incorporating more and more information. 491 00:27:16,940 --> 00:27:19,590 You're hopefully converging. 492 00:27:19,590 --> 00:27:23,930 And so, you just keep going back and forth. 493 00:27:23,930 --> 00:27:26,640 And low-density parity-check codes you can do this 494 00:27:26,640 --> 00:27:29,490 typically 100 times, 200 times. 495 00:27:29,490 --> 00:27:31,700 It's a very simple calculation. 496 00:27:31,700 --> 00:27:33,080 You can do it a lot. 497 00:27:33,080 --> 00:27:36,070 So you can do that. 498 00:27:36,070 --> 00:27:37,320 When do you stop? 499 00:27:37,320 --> 00:27:39,860 500 00:27:39,860 --> 00:27:45,370 A very popular stopping rule is to stop as 501 00:27:45,370 --> 00:27:47,260 soon as you've got-- 502 00:27:47,260 --> 00:27:49,860 If you made hard decisions on the basis of all these 503 00:27:49,860 --> 00:27:53,030 messages, that would give you binary values. 504 00:27:53,030 --> 00:27:59,080 And if all those binary values check at all these places, 505 00:27:59,080 --> 00:28:01,060 then that's a code word. 506 00:28:01,060 --> 00:28:04,640 Or that's a trajectory that's consistent with the code word. 507 00:28:04,640 --> 00:28:07,040 Basically, everything that's over here then has 508 00:28:07,040 --> 00:28:08,630 to be a code word. 509 00:28:08,630 --> 00:28:12,940 So whenever all the checks, check just based on hard 510 00:28:12,940 --> 00:28:14,840 decisions, you stop. 511 00:28:14,840 --> 00:28:17,210 So if there's very little noise to start with, this can 512 00:28:17,210 --> 00:28:18,960 happen very quickly and terminate the 513 00:28:18,960 --> 00:28:20,900 calculation well short. 514 00:28:20,900 --> 00:28:24,296 Or you have some maximum number of iterations you're 515 00:28:24,296 --> 00:28:26,350 going to allow yourself. 516 00:28:26,350 --> 00:28:30,310 If you go 200 iterations, and these things still don't 517 00:28:30,310 --> 00:28:33,130 check, probably you would say this, I've 518 00:28:33,130 --> 00:28:36,280 detected a decoding error. 519 00:28:36,280 --> 00:28:39,560 One characteristic of low-density parity-check 520 00:28:39,560 --> 00:28:43,730 codes, is they tend to have good minimum distance. 521 00:28:43,730 --> 00:28:47,620 They tend to have a minimum distance that's sort of what 522 00:28:47,620 --> 00:28:51,060 you would get in a random-like code, which goes up linearly 523 00:28:51,060 --> 00:28:52,830 with the block length. 524 00:28:52,830 --> 00:29:01,320 So for a rate 1/2 of code of length a 1,000, a random code 525 00:29:01,320 --> 00:29:04,360 would have a minimum distance of about 110. 526 00:29:04,360 --> 00:29:10,440 And a low-density parity-check code would typically have a 527 00:29:10,440 --> 00:29:15,310 large, maybe not 110, but a large minimum distance, unless 528 00:29:15,310 --> 00:29:17,200 you were just unlucky. 529 00:29:17,200 --> 00:29:20,090 So the probability of your actually converging to an 530 00:29:20,090 --> 00:29:22,850 incorrect code word is tiny. 531 00:29:22,850 --> 00:29:25,010 You don't actually make decoding errors. 532 00:29:25,010 --> 00:29:27,020 All of your errors are detectable. 533 00:29:27,020 --> 00:29:30,020 Which is a nice systems advantage some of the time for 534 00:29:30,020 --> 00:29:32,420 low-density parity-check codes. 535 00:29:32,420 --> 00:29:32,750 Yes? 536 00:29:32,750 --> 00:29:36,110 AUDIENCE: [INAUDIBLE] 537 00:29:36,110 --> 00:29:39,950 possible that if you add one variation [INAUDIBLE] 538 00:29:39,950 --> 00:29:42,690 PROFESSOR: Possible in principal but extraordinarily 539 00:29:42,690 --> 00:29:45,250 improbable. 540 00:29:45,250 --> 00:29:50,670 And once you've converged to a code word, basically, you've 541 00:29:50,670 --> 00:29:55,790 got all of all the messages lined up in the same way. 542 00:29:55,790 --> 00:30:00,790 It's like a piece of iron ore where you've got all of 543 00:30:00,790 --> 00:30:04,050 magnets going in the same direction. 544 00:30:04,050 --> 00:30:08,260 What is there in that that's going to cause them to flip? 545 00:30:08,260 --> 00:30:13,040 There's no impetus for any of these to-- 546 00:30:13,040 --> 00:30:16,060 They'll tend to get more and more convinced that what 547 00:30:16,060 --> 00:30:17,460 they're doing is right. 548 00:30:17,460 --> 00:30:20,330 They'll reinforce each other. 549 00:30:20,330 --> 00:30:26,190 So, as a practical matter, I don't think you would ever-- 550 00:30:26,190 --> 00:30:31,840 The kind of landscape of these codes is that there's large 551 00:30:31,840 --> 00:30:35,590 areas of the parameters where it doesn't tell you to go in 552 00:30:35,590 --> 00:30:36,730 any particular direction. 553 00:30:36,730 --> 00:30:43,010 And then there are deep wells around code words. 554 00:30:43,010 --> 00:30:47,270 So, typically, the decoding algorithm is kind of wandering 555 00:30:47,270 --> 00:30:51,300 around the desert here, but then once it gets into a well, 556 00:30:51,300 --> 00:30:55,040 it goes wrong boom, down to the bottom of that well. 557 00:30:55,040 --> 00:31:01,360 And once it's down here, it's extremely unlikely that it'll 558 00:31:01,360 --> 00:31:04,976 spontaneously work itself out come back over here again. 559 00:31:04,976 --> 00:31:07,700 560 00:31:07,700 --> 00:31:10,420 Powerful basins of attraction here. 561 00:31:10,420 --> 00:31:16,180 Which is another reason why when we design the code, we're 562 00:31:16,180 --> 00:31:18,480 basically designing this landscape. 563 00:31:18,480 --> 00:31:19,915 And we can design it to-- 564 00:31:19,915 --> 00:31:24,570 565 00:31:24,570 --> 00:31:27,940 when it starts to converge, it really converges fast. 566 00:31:27,940 --> 00:31:30,020 That's why some classes of these codes are 567 00:31:30,020 --> 00:31:31,270 called tornado codes. 568 00:31:31,270 --> 00:31:35,040 They wander for a while, and then when they get the idea, 569 00:31:35,040 --> 00:31:39,920 then [WOOM], everything checks very quickly. 570 00:31:39,920 --> 00:31:40,070 Yes? 571 00:31:40,070 --> 00:31:41,320 AUDIENCE: [INAUDIBLE] 572 00:31:41,320 --> 00:31:46,516 573 00:31:46,516 --> 00:31:48,424 so you would compute the-- 574 00:31:48,424 --> 00:31:51,850 575 00:31:51,850 --> 00:31:53,100 at each [UNINTELLIGIBLE] 576 00:31:53,100 --> 00:31:57,650 577 00:31:57,650 --> 00:32:04,853 calculate one of the so do you calculate all of the messages 578 00:32:04,853 --> 00:32:06,700 that go back from each [UNINTELLIGIBLE] first and 579 00:32:06,700 --> 00:32:08,200 then propagate then back-- 580 00:32:08,200 --> 00:32:09,900 PROFESSOR: Yes, correct. 581 00:32:09,900 --> 00:32:11,260 I'm sorry. 582 00:32:11,260 --> 00:32:15,570 We nominally calculate this one, but at the same time, we 583 00:32:15,570 --> 00:32:17,440 calculate every other one. 584 00:32:17,440 --> 00:32:20,280 All e of them. 585 00:32:20,280 --> 00:32:24,920 Each one of these is based on the d rho minus one-- 586 00:32:24,920 --> 00:32:26,740 other inputs. 587 00:32:26,740 --> 00:32:30,780 So it ignores the message that's coming in on that 588 00:32:30,780 --> 00:32:32,460 particular edge. 589 00:32:32,460 --> 00:32:38,030 It uses all the other messages to give and extrinsic 590 00:32:38,030 --> 00:32:40,220 message going out. 591 00:32:40,220 --> 00:32:44,520 Which you could combine back here or here, there the same 592 00:32:44,520 --> 00:32:49,660 thing, to give you your best overall APP right now from 593 00:32:49,660 --> 00:32:53,640 your right going in your left going messages. 594 00:32:53,640 --> 00:32:54,340 But you don't. 595 00:32:54,340 --> 00:32:58,000 You now use this new information in your 596 00:32:58,000 --> 00:32:59,100 next round over here. 597 00:32:59,100 --> 00:33:01,230 And the same thing on this side. 598 00:33:01,230 --> 00:33:04,420 You always compute one on the basis of all of the others. 599 00:33:04,420 --> 00:33:08,150 600 00:33:08,150 --> 00:33:13,200 And the initialization is that initially you have no 601 00:33:13,200 --> 00:33:15,180 information coming this way. 602 00:33:15,180 --> 00:33:19,380 You can represent that by an APP vector that's 1/2, 1/2. 603 00:33:19,380 --> 00:33:25,200 Probability of one is 1/2, probability of 0 is 1/2. 604 00:33:25,200 --> 00:33:26,450 Any other questions? 605 00:33:26,450 --> 00:33:28,720 606 00:33:28,720 --> 00:33:32,880 OK, so that's how it works. 607 00:33:32,880 --> 00:33:35,830 And it works great. 608 00:33:35,830 --> 00:33:40,410 And, as we'll see, even with regular 609 00:33:40,410 --> 00:33:44,560 codes you can get within-- 610 00:33:44,560 --> 00:33:47,910 additive white Gaussian noise channel terms, you can get 611 00:33:47,910 --> 00:33:51,460 within about a dB, a dB and a half of capacity. 612 00:33:51,460 --> 00:33:55,660 And merely by making these degree distributions 613 00:33:55,660 --> 00:33:59,290 irregular, this is how, Sae-Young Chung got the 614 00:33:59,290 --> 00:34:02,480 results that I showed, I think, in chapter one, where 615 00:34:02,480 --> 00:34:07,460 you get within 0.04 dB of white Gaussian noise capacity 616 00:34:07,460 --> 00:34:09,500 and that's it. 617 00:34:09,500 --> 00:34:13,530 So we knew how to get to capacity since 1961 almost, we 618 00:34:13,530 --> 00:34:14,839 just didn't realize it. 619 00:34:14,839 --> 00:34:15,219 Yeah? 620 00:34:15,219 --> 00:34:20,539 AUDIENCE: With the LDPC regular [UNINTELLIGIBLE] 621 00:34:20,539 --> 00:34:22,349 PROFESSOR: I'm sorry, I missed-- 622 00:34:22,349 --> 00:34:25,420 AUDIENCE: With regular LDPC you can still have 623 00:34:25,420 --> 00:34:28,646 a certain gap or? 624 00:34:28,646 --> 00:34:33,330 PROFESSOR: With regular LDPC there's a threshold below 625 00:34:33,330 --> 00:34:35,520 which the algorithm works, above which the algorithm 626 00:34:35,520 --> 00:34:39,239 doesn't work, as we'll see shortly. 627 00:34:39,239 --> 00:34:41,170 And the threshold is not capacity. 628 00:34:41,170 --> 00:34:43,719 It's somewhat below capacity. 629 00:34:43,719 --> 00:34:48,210 By going to irregular you can make that threshold as close 630 00:34:48,210 --> 00:34:49,725 to capacity as you like. 631 00:34:49,725 --> 00:34:51,976 You can never make it equal to capacity. 632 00:34:51,976 --> 00:34:57,110 633 00:34:57,110 --> 00:34:59,695 All right, so let's talk about turbo codes. 634 00:34:59,695 --> 00:35:02,240 635 00:35:02,240 --> 00:35:06,350 None of these ideas is very difficult, which is, again, 636 00:35:06,350 --> 00:35:09,130 humbling to those of us in the community who failed to think 637 00:35:09,130 --> 00:35:11,000 of them for 35 years. 638 00:35:11,000 --> 00:35:14,300 639 00:35:14,300 --> 00:35:17,290 And I really hope some historian of science someday 640 00:35:17,290 --> 00:35:22,990 does a nice job on culture, and why some people were blind 641 00:35:22,990 --> 00:35:25,920 to this and some people saw it and so forth. 642 00:35:25,920 --> 00:35:32,570 OK, so this is Berrou, Glavieux, and Thitimajshima-- 643 00:35:32,570 --> 00:35:35,700 which I always have problems spelling-- 644 00:35:35,700 --> 00:35:38,470 in 1993. 645 00:35:38,470 --> 00:35:40,820 And their idea was pretty simple too. 646 00:35:40,820 --> 00:35:44,290 647 00:35:44,290 --> 00:35:49,760 Their idea is based on two, rate 1/2, convolutional codes. 648 00:35:49,760 --> 00:35:52,530 Let me use notation. 649 00:35:52,530 --> 00:35:56,780 We have a certain u of d, which is a set 650 00:35:56,780 --> 00:35:58,460 of information bits. 651 00:35:58,460 --> 00:36:07,650 652 00:36:07,650 --> 00:36:16,770 And to make a rate 1/2 convolutional code, all I have 653 00:36:16,770 --> 00:36:20,770 to do is pass that through a certain g of d. 654 00:36:20,770 --> 00:36:24,960 So I'm saying my generator matrix for the convolutional 655 00:36:24,960 --> 00:36:28,372 code is one and g of d. 656 00:36:28,372 --> 00:36:31,580 That'll make a rate 1/2 code. 657 00:36:31,580 --> 00:36:40,260 And this, I'm going to call that a parity bit sequence, 658 00:36:40,260 --> 00:36:44,100 occurring at the same rate as the information bit sequence. 659 00:36:44,100 --> 00:36:48,090 660 00:36:48,090 --> 00:36:53,720 Easy enough, now, let me take this same information bit 661 00:36:53,720 --> 00:36:58,000 sequence, and let me put it through a large permutation. 662 00:36:58,000 --> 00:37:01,200 Which, again, I'll represent by pi. 663 00:37:01,200 --> 00:37:04,030 And I want you to think of this as taking a 1,000 bit 664 00:37:04,030 --> 00:37:08,200 block and mixing it all up or something like that. 665 00:37:08,200 --> 00:37:11,950 Actually, it's better to use a so-called convolutional 666 00:37:11,950 --> 00:37:16,300 permutation which is kind of stream based, continuous, the 667 00:37:16,300 --> 00:37:18,880 same way that convolutional codes are. 668 00:37:18,880 --> 00:37:24,900 All right, but it's basically the same sequence permuted. 669 00:37:24,900 --> 00:37:31,860 And let's also put that through another g prime of d, 670 00:37:31,860 --> 00:37:33,706 which, very often, is g of d. 671 00:37:33,706 --> 00:37:36,840 So I'll just call that g of d again. 672 00:37:36,840 --> 00:37:40,380 And this is second parity bit sequence. 673 00:37:40,380 --> 00:37:44,330 674 00:37:44,330 --> 00:37:51,140 And this all together, I will call a rate 1/3 code. 675 00:37:51,140 --> 00:37:53,340 For every one information bit in, there are three 676 00:37:53,340 --> 00:37:54,230 information bits out. 677 00:37:54,230 --> 00:37:58,190 Same sense as convolutional. 678 00:37:58,190 --> 00:38:02,880 All right, so the second code, g prime of d is 679 00:38:02,880 --> 00:38:04,130 one g prime of d. 680 00:38:04,130 --> 00:38:07,290 681 00:38:07,290 --> 00:38:13,640 And the interesting thing is, these codes don't need to be 682 00:38:13,640 --> 00:38:16,140 very complicated. 683 00:38:16,140 --> 00:38:19,520 One thing they realized is they do want this to be a 684 00:38:19,520 --> 00:38:22,630 recursive code. 685 00:38:22,630 --> 00:38:31,700 In other words, g of d should look like n of d over d of d. 686 00:38:31,700 --> 00:38:35,140 And one particular purpose of that is that so a single 687 00:38:35,140 --> 00:38:38,280 information bit will ring forever. 688 00:38:38,280 --> 00:38:40,000 The impulse response to a single 689 00:38:40,000 --> 00:38:42,240 information bit is infinite. 690 00:38:42,240 --> 00:38:44,710 It takes at least two. 691 00:38:44,710 --> 00:38:47,770 And you can prove to yourself there's always some sequence 692 00:38:47,770 --> 00:38:51,780 of length two in order to get a finite number of parity 693 00:38:51,780 --> 00:38:53,430 bits, a finite number of nonzero 694 00:38:53,430 --> 00:38:55,820 parity bits out of here. 695 00:38:55,820 --> 00:38:58,010 And when those two bits are permuted, they're going to 696 00:38:58,010 --> 00:38:59,970 come up in totally different places, so they are going to 697 00:38:59,970 --> 00:39:03,440 look like two individual information bits down here, 698 00:39:03,440 --> 00:39:05,930 and therefore they're going to ring for very long time. 699 00:39:05,930 --> 00:39:09,350 The basic idea is, you don't want an information sequence 700 00:39:09,350 --> 00:39:12,890 which gives you a short code word out of here and a short 701 00:39:12,890 --> 00:39:14,430 code word out of here. 702 00:39:14,430 --> 00:39:20,920 And making it recursive, have feedback is what that means, 703 00:39:20,920 --> 00:39:23,560 is what you need to do to prevent that. 704 00:39:23,560 --> 00:39:25,180 It also gives you better codes, but I don't think 705 00:39:25,180 --> 00:39:27,870 that's really why-- 706 00:39:27,870 --> 00:39:31,230 If you have g of d over n of d, this is going to be 707 00:39:31,230 --> 00:39:35,870 equivalent to the code we're multiplying to the 708 00:39:35,870 --> 00:39:39,590 non-recursive feedback free code, which is d 709 00:39:39,590 --> 00:39:40,910 of d, n of d, right? 710 00:39:40,910 --> 00:39:42,380 We worked all that out. 711 00:39:42,380 --> 00:39:45,050 It's equivalent to the code where you multiply through by 712 00:39:45,050 --> 00:39:46,550 the denominator. 713 00:39:46,550 --> 00:39:51,120 And so you get the same code with d of d, n of d, but you 714 00:39:51,120 --> 00:39:53,770 don't want to do that, because you are concerned here about 715 00:39:53,770 --> 00:39:59,280 the input output relationship between input bits and the 716 00:39:59,280 --> 00:40:02,390 encoded bits. 717 00:40:02,390 --> 00:40:05,830 And you want the information bit sequence to come through 718 00:40:05,830 --> 00:40:08,570 by itself, because it's going to be reused. 719 00:40:08,570 --> 00:40:11,980 You want the information bit sequence to be in common 720 00:40:11,980 --> 00:40:12,860 between these two. 721 00:40:12,860 --> 00:40:17,780 That's going to be the length when we decode these codes. 722 00:40:17,780 --> 00:40:20,320 Basically, the messages concerning the information bit 723 00:40:20,320 --> 00:40:22,820 sequences is what's going to go back and forth 724 00:40:22,820 --> 00:40:25,430 between the two codes. 725 00:40:25,430 --> 00:40:27,960 726 00:40:27,960 --> 00:40:30,740 All right, do you get the set up here? 727 00:40:30,740 --> 00:40:34,060 I gave you a very different perspective on it by drawing 728 00:40:34,060 --> 00:40:36,290 the graph of this code. 729 00:40:36,290 --> 00:40:38,290 I mean this is a graph of the code, but 730 00:40:38,290 --> 00:40:39,540 it's not one we want. 731 00:40:39,540 --> 00:40:42,690 732 00:40:42,690 --> 00:40:46,210 Let's draw the graph of this code. 733 00:40:46,210 --> 00:40:53,020 So turbo code graph, I'll draw a normal graph, but again, if 734 00:40:53,020 --> 00:40:58,160 you like to do it as a Tanner style, be my guest. 735 00:40:58,160 --> 00:40:59,410 All right, this first code-- 736 00:40:59,410 --> 00:41:07,490 737 00:41:07,490 --> 00:41:08,630 Let me do this in two steps. 738 00:41:08,630 --> 00:41:12,840 First of all, a rate 1/2 code graph. 739 00:41:12,840 --> 00:41:16,040 So for one of these code, what does it look like? 740 00:41:16,040 --> 00:41:17,670 It's a trellis graph. 741 00:41:17,670 --> 00:41:19,550 Which in the normal graph picture is a very 742 00:41:19,550 --> 00:41:23,880 simple chain graph. 743 00:41:23,880 --> 00:41:25,590 It looks like this. 744 00:41:25,590 --> 00:41:28,100 Here's the information sequence. 745 00:41:28,100 --> 00:41:29,350 Here are the states. 746 00:41:29,350 --> 00:41:31,930 747 00:41:31,930 --> 00:41:33,560 So these might be simple codes. 748 00:41:33,560 --> 00:41:38,850 These are typically four to 16 states, so two to four bits of 749 00:41:38,850 --> 00:41:41,245 state information, not very complicated. 750 00:41:41,245 --> 00:41:44,300 751 00:41:44,300 --> 00:41:46,580 So this is what it looks like. 752 00:41:46,580 --> 00:41:50,500 We get one of these for each. 753 00:41:50,500 --> 00:41:54,750 This is the branch constraint for each unit of time. 754 00:41:54,750 --> 00:42:01,500 This would be y0, y1, y2, y3, you get two bits out for each 755 00:42:01,500 --> 00:42:02,750 unit of time. 756 00:42:02,750 --> 00:42:05,640 757 00:42:05,640 --> 00:42:08,990 And this case, one of these is actually the input at that 758 00:42:08,990 --> 00:42:12,502 time, u0, u2. 759 00:42:12,502 --> 00:42:17,190 Or we could adopt some other indexing scheme. 760 00:42:17,190 --> 00:42:22,940 It's systematic so, we think of these as the inputs sort of 761 00:42:22,940 --> 00:42:25,430 driving an output. 762 00:42:25,430 --> 00:42:29,510 So maybe a better way to do this is-- 763 00:42:29,510 --> 00:42:31,755 an alternative way of doing it is like this. 764 00:42:31,755 --> 00:42:36,740 765 00:42:36,740 --> 00:42:38,450 But it's all the same thing, right? 766 00:42:38,450 --> 00:42:40,840 It's what you've already seen. 767 00:42:40,840 --> 00:42:45,330 So I just want you to get used to this way of writing the 768 00:42:45,330 --> 00:42:48,340 graph of a trellis of a rate 1/2 systematic 769 00:42:48,340 --> 00:42:49,860 convolutional code. 770 00:42:49,860 --> 00:42:53,090 Here are these systematic bits, which are both inputs 771 00:42:53,090 --> 00:42:55,715 and, ultimately, outputs on to the channel. 772 00:42:55,715 --> 00:42:59,610 And these are the parity bits which are only 773 00:42:59,610 --> 00:43:01,970 output onto the channel. 774 00:43:01,970 --> 00:43:03,540 All right, and these are the branch 775 00:43:03,540 --> 00:43:05,650 constraints for each time. 776 00:43:05,650 --> 00:43:09,260 And these are the state's basis for each time. 777 00:43:09,260 --> 00:43:12,570 So that I can always draw that, that way. 778 00:43:12,570 --> 00:43:17,000 All right, now up here, I really have two of these 779 00:43:17,000 --> 00:43:20,590 codes, possibly identical. 780 00:43:20,590 --> 00:43:23,570 And what's the connection between them? 781 00:43:23,570 --> 00:43:26,460 The connection between them is that they have the same 782 00:43:26,460 --> 00:43:30,520 information, but in some random order, some 783 00:43:30,520 --> 00:43:34,760 pseudo-random interleaved order. 784 00:43:34,760 --> 00:43:40,790 So I draw a graph of that, again, focus on the 785 00:43:40,790 --> 00:43:40,970 interleaver. 786 00:43:40,970 --> 00:43:44,470 Make it nice and big now. 787 00:43:44,470 --> 00:43:46,790 There's always going to be a big interleaver in the center 788 00:43:46,790 --> 00:43:48,450 of all our charts. 789 00:43:48,450 --> 00:43:51,750 This is always the random-like element. 790 00:43:51,750 --> 00:43:54,980 Now, let me draw my first convolutional code over here. 791 00:43:54,980 --> 00:44:00,250 792 00:44:00,250 --> 00:44:03,085 I'm just going to tilt this on its side. 793 00:44:03,085 --> 00:44:06,210 I'm going to put the parity bits on this side, the first 794 00:44:06,210 --> 00:44:07,460 parity sequence. 795 00:44:07,460 --> 00:44:09,850 796 00:44:09,850 --> 00:44:12,660 So now this is running in time either up to 797 00:44:12,660 --> 00:44:14,020 down or down to up. 798 00:44:14,020 --> 00:44:15,980 I don't care. 799 00:44:15,980 --> 00:44:21,460 So forth, down to here, et cetera, dot, dot, 800 00:44:21,460 --> 00:44:22,850 dot, dot, dot, dot-- 801 00:44:22,850 --> 00:44:25,390 And I'll put the information bit over here. 802 00:44:25,390 --> 00:44:27,830 And I'm going to do it in this way. 803 00:44:27,830 --> 00:44:30,060 The information bits are, first of all, 804 00:44:30,060 --> 00:44:31,830 used in this code. 805 00:44:31,830 --> 00:44:35,356 So I have a little equality. 806 00:44:35,356 --> 00:44:39,070 So these are going to be in my information bits. 807 00:44:39,070 --> 00:44:41,350 But then they're going to go through this permutation and 808 00:44:41,350 --> 00:44:44,550 also be used in another code over on the right side. 809 00:44:44,550 --> 00:44:50,140 810 00:44:50,140 --> 00:44:51,390 Is this clear? 811 00:44:51,390 --> 00:44:55,740 812 00:44:55,740 --> 00:44:58,900 So this is everything up to here. 813 00:44:58,900 --> 00:45:00,320 I'm about to go into the interleaver. 814 00:45:00,320 --> 00:45:03,760 815 00:45:03,760 --> 00:45:06,870 Stop me with questions if anything is 816 00:45:06,870 --> 00:45:08,030 mysterious about this. 817 00:45:08,030 --> 00:45:11,850 OK, after some huge permutation, they 818 00:45:11,850 --> 00:45:13,850 come out over here. 819 00:45:13,850 --> 00:45:17,180 And now these are information bits that go into another 820 00:45:17,180 --> 00:45:19,110 identical trellis-- 821 00:45:19,110 --> 00:45:22,010 or could be identical. 822 00:45:22,010 --> 00:45:28,430 So we have a trellis over on this side that's connected to 823 00:45:28,430 --> 00:45:33,090 one parity bit and one information bit. 824 00:45:33,090 --> 00:45:35,060 It's another rate 1/2 trellis. 825 00:45:35,060 --> 00:45:42,910 This is parity bits, these are, again, info bits. 826 00:45:42,910 --> 00:45:47,641 Same information bit sequence but drastically permuted. 827 00:45:47,641 --> 00:45:50,080 Is that clear? 828 00:45:50,080 --> 00:45:54,150 So again this is the same idea of a switchboard with sockets 829 00:45:54,150 --> 00:45:58,060 we have the same number sockets on the left side and 830 00:45:58,060 --> 00:46:00,110 on the right side. 831 00:46:00,110 --> 00:46:06,280 And we make a huge permutation that ties one to the other. 832 00:46:06,280 --> 00:46:07,530 It's only edges in here. 833 00:46:07,530 --> 00:46:10,050 834 00:46:10,050 --> 00:46:12,440 Notice there's no computation that ever takes place in the 835 00:46:12,440 --> 00:46:12,735 interleaver. 836 00:46:12,735 --> 00:46:16,250 This is , again, it's purely edges, purely sending messages 837 00:46:16,250 --> 00:46:17,340 through here. 838 00:46:17,340 --> 00:46:19,250 So the analogy of a switchboard 839 00:46:19,250 --> 00:46:21,790 is a very good one. 840 00:46:21,790 --> 00:46:23,780 Even though we don't have switchboards anymore. 841 00:46:23,780 --> 00:46:25,600 Maybe some of you don't even know what a telephone 842 00:46:25,600 --> 00:46:26,850 switchboard is? 843 00:46:26,850 --> 00:46:29,780 844 00:46:29,780 --> 00:46:33,170 It's a quaint but apt analogy. 845 00:46:33,170 --> 00:46:37,760 All right, so this is the normal graph of a turbo code. 846 00:46:37,760 --> 00:46:41,575 847 00:46:41,575 --> 00:46:45,020 I've drawn it to emphasize its commonality with low-density 848 00:46:45,020 --> 00:46:46,370 parity-check code. 849 00:46:46,370 --> 00:46:50,420 The biggest element is this big interleaver in here, and 850 00:46:50,420 --> 00:46:53,320 that's key to the thing working well. 851 00:46:53,320 --> 00:46:55,610 All right, so how would we apply the sum-product 852 00:46:55,610 --> 00:46:57,520 algorithm to this code? 853 00:46:57,520 --> 00:47:00,570 What would our decoding schedule be? 854 00:47:00,570 --> 00:47:05,120 In this case, when we observe the channel, we get messages 855 00:47:05,120 --> 00:47:07,960 in all these places. 856 00:47:07,960 --> 00:47:14,290 So we get intrinsic information coming in for all 857 00:47:14,290 --> 00:47:15,845 the external symbols. 858 00:47:15,845 --> 00:47:24,730 859 00:47:24,730 --> 00:47:32,832 First step might be to 860 00:47:32,832 --> 00:47:34,082 AUDIENCE: [INAUDIBLE] 861 00:47:34,082 --> 00:47:41,230 862 00:47:41,230 --> 00:47:46,330 PROFESSOR: That's first step, we can-- 863 00:47:46,330 --> 00:47:50,100 In the same way, this is just a distribution node when 864 00:47:50,100 --> 00:47:52,290 originally all else is ignorance. 865 00:47:52,290 --> 00:47:55,980 So these same messages just propagate out here, and if we 866 00:47:55,980 --> 00:48:00,780 like, we can get them out over here. 867 00:48:00,780 --> 00:48:04,430 All these are available too. 868 00:48:04,430 --> 00:48:05,410 OK, somebody else. 869 00:48:05,410 --> 00:48:09,040 What's the next step? 870 00:48:09,040 --> 00:48:11,620 Somebody was just about to say it. 871 00:48:11,620 --> 00:48:13,656 Be bold, somebody. 872 00:48:13,656 --> 00:48:15,440 AUDIENCE: [INAUDIBLE] 873 00:48:15,440 --> 00:48:16,780 PROFESSOR: Excuse me? 874 00:48:16,780 --> 00:48:18,044 AUDIENCE: The trellis decoding-- 875 00:48:18,044 --> 00:48:20,555 PROFESSOR: Trellis decoding, right. 876 00:48:20,555 --> 00:48:24,720 If we forget about that side and just look at what the 877 00:48:24,720 --> 00:48:29,435 sum-product algorithm does over here, we're doing the 878 00:48:29,435 --> 00:48:32,705 sum-product algorithm on a trellis, a BCJR algorithm. 879 00:48:32,705 --> 00:48:35,260 880 00:48:35,260 --> 00:48:43,430 So given all these messages, we do our backward forward 881 00:48:43,430 --> 00:48:48,650 algorithm, alphas and betas, eventually epsilons, extrinsic 882 00:48:48,650 --> 00:48:52,820 information coming out on all nodes there, there, 883 00:48:52,820 --> 00:48:54,630 there, and so forth. 884 00:48:54,630 --> 00:48:58,790 And that requires going up and down the whole trellis. 885 00:48:58,790 --> 00:49:03,230 If this is a 1,000 bit block, as it often is, or larger it 886 00:49:03,230 --> 00:49:05,890 means going from top to bottom through the whole block and 887 00:49:05,890 --> 00:49:10,470 doing one sweep of a BCJR algorithm through that block, 888 00:49:10,470 --> 00:49:12,670 which will generate a bunch of extrinsic 889 00:49:12,670 --> 00:49:14,470 information over here. 890 00:49:14,470 --> 00:49:18,020 891 00:49:18,020 --> 00:49:19,200 Now, we have more over here. 892 00:49:19,200 --> 00:49:21,460 We still got the same intrinsic information coming 893 00:49:21,460 --> 00:49:25,950 in here, but now we can take this new extrinsic information 894 00:49:25,950 --> 00:49:29,850 and combine it with this intrinsic information and, 895 00:49:29,850 --> 00:49:33,740 hopefully, get an improved, higher quality information. 896 00:49:33,740 --> 00:49:36,790 Because we've incorporated all the information from all these 897 00:49:36,790 --> 00:49:40,045 receive symbols on this side, and we send that over here. 898 00:49:40,045 --> 00:49:42,730 899 00:49:42,730 --> 00:49:46,170 And if you think of it in signal to noise ratio terms, 900 00:49:46,170 --> 00:49:49,260 as some people do, you hopefully have improved the 901 00:49:49,260 --> 00:49:52,040 signal to noise ratio in your information that's coming out. 902 00:49:52,040 --> 00:49:54,720 It's as though you received these bits over a higher 903 00:49:54,720 --> 00:49:56,690 quality channel. 904 00:49:56,690 --> 00:50:02,190 They tell you more about the information bits then you got 905 00:50:02,190 --> 00:50:06,830 just from looking at the raw data from the channel. 906 00:50:06,830 --> 00:50:10,590 That's basically where turbo comes from. 907 00:50:10,590 --> 00:50:17,330 You then do BCJR over here using this improved intrinsic 908 00:50:17,330 --> 00:50:19,760 information, of course, the parity 909 00:50:19,760 --> 00:50:22,370 information hasn't improved. 910 00:50:22,370 --> 00:50:26,690 You might think of ways to improve this too. 911 00:50:26,690 --> 00:50:28,150 But this was the basic scheme. 912 00:50:28,150 --> 00:50:30,140 It works just fine. 913 00:50:30,140 --> 00:50:31,170 You come over here. 914 00:50:31,170 --> 00:50:34,060 You then do a complete sweep through a 1,000 bits or 915 00:50:34,060 --> 00:50:38,930 whatever, and you develop outgoing messages here. 916 00:50:38,930 --> 00:50:41,530 Which again, let's hope we've improved the signal-noise 917 00:50:41,530 --> 00:50:43,450 ratio a little bit more, that these are even more 918 00:50:43,450 --> 00:50:47,070 informative about the input bits. 919 00:50:47,070 --> 00:50:52,140 And they come back, and now, with this further improved 920 00:50:52,140 --> 00:50:55,470 information, we can sweep through here again. 921 00:50:55,470 --> 00:50:57,010 That's where the turbo comes from. 922 00:50:57,010 --> 00:50:59,900 You keep recycling the information left to right and 923 00:50:59,900 --> 00:51:01,250 right to left. 924 00:51:01,250 --> 00:51:03,170 And, hopefully, you build up power. 925 00:51:03,170 --> 00:51:06,860 You lower the signal-noise ratio each time. 926 00:51:06,860 --> 00:51:07,240 Yes? 927 00:51:07,240 --> 00:51:10,520 AUDIENCE: [INAUDIBLE] 928 00:51:10,520 --> 00:51:13,063 and then you [UNINTELLIGIBLE] the other side is kind of 929 00:51:13,063 --> 00:51:13,830 [? encouraging. ?] 930 00:51:13,830 --> 00:51:16,330 Now, why can't you, because on this side, actually, the 931 00:51:16,330 --> 00:51:19,414 equilibrium is just the [UNINTELLIGIBLE] version of 932 00:51:19,414 --> 00:51:20,390 the other side. 933 00:51:20,390 --> 00:51:24,294 Why would you do it [UNINTELLIGIBLE] 934 00:51:24,294 --> 00:51:26,170 carry out, and do it again? 935 00:51:26,170 --> 00:51:27,590 PROFESSOR: So a good question. 936 00:51:27,590 --> 00:51:28,840 You certainly could. 937 00:51:28,840 --> 00:51:33,760 938 00:51:33,760 --> 00:51:37,740 So after you've done it twice, you basically processed all 939 00:51:37,740 --> 00:51:40,720 the same things as this thing does in one iteration, you 940 00:51:40,720 --> 00:51:42,950 spent twice as much effort. 941 00:51:42,950 --> 00:51:47,280 The question is, is now the quality of your information 942 00:51:47,280 --> 00:51:48,450 any better? 943 00:51:48,450 --> 00:51:52,080 And I haven't done this myself, but I suspect people 944 00:51:52,080 --> 00:51:54,440 in the business did this, and they found they didn't get 945 00:51:54,440 --> 00:51:57,550 enough improvement to make up for the additional 946 00:51:57,550 --> 00:51:59,540 computation. 947 00:51:59,540 --> 00:52:02,420 But that's an alternative that you could reasonably try. 948 00:52:02,420 --> 00:52:06,407 AUDIENCE: The reason I say that is because if you do it 949 00:52:06,407 --> 00:52:10,650 that way, that means for the second decoding process of the 950 00:52:10,650 --> 00:52:15,480 left side, the information is very fresh. 951 00:52:15,480 --> 00:52:18,444 Because it's sort of [? right ?] information. 952 00:52:18,444 --> 00:52:19,802 If you do this and this and this, it looks like there is 953 00:52:19,802 --> 00:52:23,384 enough propogation of the same provision to itself. 954 00:52:23,384 --> 00:52:24,510 PROFESSOR: There certainly is. 955 00:52:24,510 --> 00:52:28,624 There are certainly cycles in this graph. 956 00:52:28,624 --> 00:52:31,090 AUDIENCE: [INAUDIBLE] 957 00:52:31,090 --> 00:52:35,300 PROFESSOR: OK, well, these are great questions. 958 00:52:35,300 --> 00:52:40,295 What I hope that you will get from this class is that you 959 00:52:40,295 --> 00:52:42,740 will be able to go back and say, well why don't we try 960 00:52:42,740 --> 00:52:44,140 doing it this way? 961 00:52:44,140 --> 00:52:46,170 Whereas everybody else has just been following what they 962 00:52:46,170 --> 00:52:49,165 read in the literature, and it says, to do it first here, and 963 00:52:49,165 --> 00:52:50,980 then there, and then there. 964 00:52:50,980 --> 00:52:51,460 Try it. 965 00:52:51,460 --> 00:52:53,590 Maybe it's good. 966 00:52:53,590 --> 00:52:59,590 You're suggesting that suppose this guy it actually has poor 967 00:52:59,590 --> 00:53:01,190 information. 968 00:53:01,190 --> 00:53:04,030 He could actually make things worse over here. 969 00:53:04,030 --> 00:53:05,490 AUDIENCE: Yeah, and also [INAUDIBLE] 970 00:53:05,490 --> 00:53:08,110 PROFESSOR: So then if this guy just operated on the fresh 971 00:53:08,110 --> 00:53:10,030 information. 972 00:53:10,030 --> 00:53:14,890 It's a probabilistic thing whether this would work better 973 00:53:14,890 --> 00:53:17,080 on the average. 974 00:53:17,080 --> 00:53:18,600 I don't know. 975 00:53:18,600 --> 00:53:21,270 I suspect that, once upon a time, all these things have 976 00:53:21,270 --> 00:53:22,600 been tried. 977 00:53:22,600 --> 00:53:25,880 But certainly, if you're in any kind of new situation, new 978 00:53:25,880 --> 00:53:31,218 channel, new code, you might think to try it again. 979 00:53:31,218 --> 00:53:32,630 It's a very reasonable suggestion. 980 00:53:32,630 --> 00:53:39,470 981 00:53:39,470 --> 00:53:45,490 Because computation is not free, there is a marked 982 00:53:45,490 --> 00:53:50,220 difference in turbo decoding in that you're spending a lot 983 00:53:50,220 --> 00:53:52,090 more time decoding each side. 984 00:53:52,090 --> 00:53:55,890 This PCJR algorithm is a lot more complicated than just 985 00:53:55,890 --> 00:53:59,120 executing-- well, it's gone now-- but the sum-product 986 00:53:59,120 --> 00:54:03,500 update rule for equals or 0 sum node. 987 00:54:03,500 --> 00:54:04,730 That's a very simple operation. 988 00:54:04,730 --> 00:54:07,900 On the other hand, it doesn't get that much done. 989 00:54:07,900 --> 00:54:12,910 You can think of this as doing a lot of processing on this 990 00:54:12,910 --> 00:54:15,680 information over here before passing it back. 991 00:54:15,680 --> 00:54:18,490 Then this does a lot of processing before passing it 992 00:54:18,490 --> 00:54:19,740 back again. 993 00:54:19,740 --> 00:54:22,090 994 00:54:22,090 --> 00:54:28,170 And so for turbo codes, typically, they only do 10 or 995 00:54:28,170 --> 00:54:29,420 20 iterations. 996 00:54:29,420 --> 00:54:31,550 997 00:54:31,550 --> 00:54:34,760 Whereas for low-density parity-check codes, one does 998 00:54:34,760 --> 00:54:39,820 hundreds of iterations, of much simpler iterations. 999 00:54:39,820 --> 00:54:42,640 But, in either case, you've got to deal with the fact that 1000 00:54:42,640 --> 00:54:46,670 as you get up in the number of iterations, you are getting to 1001 00:54:46,670 --> 00:54:51,240 the region where cycles begin to have an effect, where you 1002 00:54:51,240 --> 00:54:54,830 are re-processing old information as though it was 1003 00:54:54,830 --> 00:54:57,150 new, independent information. 1004 00:54:57,150 --> 00:54:59,395 This tends to make you overconfident. 1005 00:54:59,395 --> 00:55:02,010 1006 00:55:02,010 --> 00:55:05,870 Once you get in the vicinity of a decision or of a fixed 1007 00:55:05,870 --> 00:55:09,880 point, whether it's a decision or not, it tends to lock you 1008 00:55:09,880 --> 00:55:12,675 into that fixed point. 1009 00:55:12,675 --> 00:55:16,470 Your processing, after a while, just reinforces itself. 1010 00:55:16,470 --> 00:55:20,050 1011 00:55:20,050 --> 00:55:22,940 Now, another thing, turbo codes in contrast to 1012 00:55:22,940 --> 00:55:25,810 low-density parity-check codes, generally have terrible 1013 00:55:25,810 --> 00:55:27,060 minimum distance. 1014 00:55:27,060 --> 00:55:29,535 1015 00:55:29,535 --> 00:55:34,060 If you can work through the algebra, and there's always 1016 00:55:34,060 --> 00:55:39,630 some weight 2 code word that produces maybe eight things 1017 00:55:39,630 --> 00:55:44,380 out here and 10 out here. 1018 00:55:44,380 --> 00:55:47,910 So the total minimum distance is only 20, no matter how long 1019 00:55:47,910 --> 00:55:50,200 the turbo code gets. 1020 00:55:50,200 --> 00:55:53,810 All right, so when I say terrible, I don't mean two, 1021 00:55:53,810 --> 00:55:57,450 but I mean 20 or 30 could be a number for minimum distance. 1022 00:55:57,450 --> 00:56:00,500 1023 00:56:00,500 --> 00:56:03,730 Certainly, this is called parallel concatenation, where 1024 00:56:03,730 --> 00:56:08,430 you have these two codes in parallel, and just pass 1025 00:56:08,430 --> 00:56:11,590 information bits back and forth between them. 1026 00:56:11,590 --> 00:56:14,810 It's typical that you get poor minimum distance which 1027 00:56:14,810 --> 00:56:20,490 eventually shows up as an error floor. 1028 00:56:20,490 --> 00:56:23,850 In all these codes, when you draw the performance curve, as 1029 00:56:23,850 --> 00:56:28,810 we always draw it, you tend to get what's called a waterfall 1030 00:56:28,810 --> 00:56:32,180 region, where things behave in a very steep 1031 00:56:32,180 --> 00:56:34,370 Gaussian like measure. 1032 00:56:34,370 --> 00:56:38,730 When you measure distance from the capacity, you might be-- 1033 00:56:38,730 --> 00:56:41,810 Oh, let's do this first, assess an r norm. 1034 00:56:41,810 --> 00:56:44,970 So capacity is always at 0dB. 1035 00:56:44,970 --> 00:56:47,440 And this is probability of error. 1036 00:56:47,440 --> 00:56:51,530 So this is your distance from capacity, and this might be 1037 00:56:51,530 --> 00:56:56,460 1dB, or 3/10 dB, or something very good. 1038 00:56:56,460 --> 00:57:01,800 But then, as you get down below, some cases it could be 1039 00:57:01,800 --> 00:57:05,710 10 to the minus three or four, some cases it could be 10 to 1040 00:57:05,710 --> 00:57:06,540 the minus seven. 1041 00:57:06,540 --> 00:57:09,710 So where it starts is important. 1042 00:57:09,710 --> 00:57:13,030 Then this tends to flatten out like that. 1043 00:57:13,030 --> 00:57:17,180 And this is simply what you get from the union-bound 1044 00:57:17,180 --> 00:57:23,320 estimate for poor distance. 1045 00:57:23,320 --> 00:57:27,210 So, in this region, other things hurt you worse than the 1046 00:57:27,210 --> 00:57:28,890 distance did. 1047 00:57:28,890 --> 00:57:31,720 If you are purely limited by distance, then you would have 1048 00:57:31,720 --> 00:57:32,840 a performance like this. 1049 00:57:32,840 --> 00:57:39,680 There a very, tiny number of minimum distance code words. 1050 00:57:39,680 --> 00:57:45,110 There may be only a few in 1,000 length block, so the 1051 00:57:45,110 --> 00:57:47,070 error coefficient is very small. 1052 00:57:47,070 --> 00:57:49,260 That's why this is way down here. 1053 00:57:49,260 --> 00:57:53,950 The interleaver tends to give you a 1/n effect on the error 1054 00:57:53,950 --> 00:57:55,510 coefficient. 1055 00:57:55,510 --> 00:57:58,130 So this is way down here, and it doesn't bother you in the 1056 00:57:58,130 --> 00:57:59,600 waterfall region, but then at some 1057 00:57:59,600 --> 00:58:00,600 point it becomes dominant. 1058 00:58:00,600 --> 00:58:03,740 You can think of these as being two types of curves. 1059 00:58:03,740 --> 00:58:05,610 This is the iterative decoding curve. 1060 00:58:05,610 --> 00:58:08,810 This is simple maximum likelihood of decoding when 1061 00:58:08,810 --> 00:58:10,920 you have minimum distance of d with a small error 1062 00:58:10,920 --> 00:58:12,770 coefficient. 1063 00:58:12,770 --> 00:58:17,600 And so where this error floor is an important issue for 1064 00:58:17,600 --> 00:58:20,130 turbo codes. 1065 00:58:20,130 --> 00:58:22,680 In some communications applications really all you're 1066 00:58:22,680 --> 00:58:24,460 interested in is 10 to the minus four, 10 1067 00:58:24,460 --> 00:58:25,850 to the minus five. 1068 00:58:25,850 --> 00:58:28,730 And then you really want to put all of your emphasis on 1069 00:58:28,730 --> 00:58:32,720 the waterfall region and just keep the error floor from 1070 00:58:32,720 --> 00:58:35,300 being not too bad. 1071 00:58:35,300 --> 00:58:39,160 So that would be a very good application for turbo code. 1072 00:58:39,160 --> 00:58:42,920 But if, as some people think they want, error probabilities 1073 00:58:42,920 --> 00:58:46,210 like 10 to the minus 12, or 10 to the minus 15, probably 1074 00:58:46,210 --> 00:58:48,565 turbo code is not going to be your best candidate. 1075 00:58:48,565 --> 00:58:52,600 1076 00:58:52,600 --> 00:58:55,470 And it's not that you couldn't create a code with better 1077 00:58:55,470 --> 00:59:01,000 minimum distance, but it's going to get harder. 1078 00:59:01,000 --> 00:59:03,960 I don't know that much effort has gone into this, because we 1079 00:59:03,960 --> 00:59:06,200 have low-density parity-check codes for this other 1080 00:59:06,200 --> 00:59:07,450 application. 1081 00:59:07,450 --> 00:59:12,300 1082 00:59:12,300 --> 00:59:13,680 Any questions on turbo code? 1083 00:59:13,680 --> 00:59:14,780 That's about all I'm going to say. 1084 00:59:14,780 --> 00:59:15,170 Yeah? 1085 00:59:15,170 --> 00:59:18,954 AUDIENCE: Why not expurgate the bad code words? 1086 00:59:18,954 --> 00:59:21,200 PROFESSOR: Expurgate the bad code words. 1087 00:59:21,200 --> 00:59:22,760 Well, how exactly are you going to do that? 1088 00:59:22,760 --> 00:59:27,350 AUDIENCE: Any malady report. 1089 00:59:27,350 --> 00:59:29,200 We disallow certain using [? passes. ?] 1090 00:59:29,200 --> 00:59:32,140 1091 00:59:32,140 --> 00:59:38,800 PROFESSOR: So you're not going to mess with the g of d, but 1092 00:59:38,800 --> 00:59:42,335 you're going to go through, you going to find all the u of 1093 00:59:42,335 --> 00:59:45,215 d's that lead to low weight sequences, and then you're 1094 00:59:45,215 --> 00:59:47,120 going to expurgate them. 1095 00:59:47,120 --> 00:59:55,150 Of course, it's a linear code, so if there's a low weight 1096 00:59:55,150 --> 00:59:57,720 sequence in the neighborhood of 0, then there is going to 1097 00:59:57,720 --> 01:00:00,710 be a corresponding sequence in the neighborhood of any of the 1098 01:00:00,710 --> 01:00:02,040 code words. 1099 01:00:02,040 --> 01:00:04,430 So you're going to have to expurgate, somehow, around all 1100 01:00:04,430 --> 01:00:05,140 the code words. 1101 01:00:05,140 --> 01:00:05,870 I don't know how to do it. 1102 01:00:05,870 --> 01:00:09,492 AUDIENCE: You would sacrifice rate. 1103 01:00:09,492 --> 01:00:13,485 PROFESSOR: You will sacrifice rate? 1104 01:00:13,485 --> 01:00:15,050 Oh, one other thing I should mention. 1105 01:00:15,050 --> 01:00:20,830 Very commonly in turbo codes, they don't send 1106 01:00:20,830 --> 01:00:22,720 all of these bits. 1107 01:00:22,720 --> 01:00:26,170 They send fewer bits, which. 1108 01:00:26,170 --> 01:00:29,580 in effect, raises the rate. 1109 01:00:29,580 --> 01:00:31,870 But then, of course, makes decoding harder, because you 1110 01:00:31,870 --> 01:00:34,870 don't get any received information from the bits that 1111 01:00:34,870 --> 01:00:36,270 you don't send. 1112 01:00:36,270 --> 01:00:39,670 But there are various philosophies of what's called 1113 01:00:39,670 --> 01:00:42,140 puncturing-- 1114 01:00:42,140 --> 01:00:45,000 that I'm certainly no expert on-- 1115 01:00:45,000 --> 01:00:47,670 and it's possible that by being very clever about 1116 01:00:47,670 --> 01:00:52,610 puncturing you could do something 1117 01:00:52,610 --> 01:00:53,860 about minimum distance. 1118 01:00:53,860 --> 01:00:56,410 1119 01:00:56,410 --> 01:00:59,610 Shortening is where you hold some of these bits to 0 and 1120 01:00:59,610 --> 01:01:01,630 don't send them. 1121 01:01:01,630 --> 01:01:06,650 Puncturing mean to let them go free and don't send them. 1122 01:01:06,650 --> 01:01:08,380 So I don't know. 1123 01:01:08,380 --> 01:01:12,530 But I don't think this is a very profitable way to go. 1124 01:01:12,530 --> 01:01:15,290 1125 01:01:15,290 --> 01:01:17,250 But it's certainly a reasonable question to ask. 1126 01:01:17,250 --> 01:01:21,900 Any time that you get into a minimum distance limited 1127 01:01:21,900 --> 01:01:25,600 situation, you should think about, is there some way I can 1128 01:01:25,600 --> 01:01:30,420 just expurgate that small fraction of code words in the 1129 01:01:30,420 --> 01:01:33,010 neighborhood of every code word that have 1130 01:01:33,010 --> 01:01:34,260 that minimum distance. 1131 01:01:34,260 --> 01:01:41,550 1132 01:01:41,550 --> 01:01:44,376 This, as I said, is called parallel concatenation. 1133 01:01:44,376 --> 01:01:49,680 1134 01:01:49,680 --> 01:01:50,920 Sorry, I didn't mean to cut off 1135 01:01:50,920 --> 01:01:52,450 questions about turbo codes. 1136 01:01:52,450 --> 01:01:54,910 I did say, I'm not going to talk about them again. 1137 01:01:54,910 --> 01:01:59,450 They, of course, gotten a lot of publicity, are 1138 01:01:59,450 --> 01:02:03,560 very popular initially. 1139 01:02:03,560 --> 01:02:05,940 This was a revolution in coding. 1140 01:02:05,940 --> 01:02:09,660 Turbo codes got into all the new standards and so forth. 1141 01:02:09,660 --> 01:02:12,930 Every communications company had a small group simulating 1142 01:02:12,930 --> 01:02:15,470 turbo codes. 1143 01:02:15,470 --> 01:02:18,560 And so they got a tremendous amount of momentum. 1144 01:02:18,560 --> 01:02:22,790 Low-density parity-check codes really didn't get looked at 1145 01:02:22,790 --> 01:02:27,190 till a couple years later. 1146 01:02:27,190 --> 01:02:29,600 As you'll see, there's a lot more analytical work you can 1147 01:02:29,600 --> 01:02:32,540 do a low-density parity-check codes, so they're popular in 1148 01:02:32,540 --> 01:02:35,040 the academic community for that reason. 1149 01:02:35,040 --> 01:02:38,780 But, in fact, it turned out that the analysis allowed you 1150 01:02:38,780 --> 01:02:42,330 to do fine tuning of the design of low-density 1151 01:02:42,330 --> 01:02:43,275 parity-check codes. 1152 01:02:43,275 --> 01:02:47,960 There are more knobs that you can do, such that you really 1153 01:02:47,960 --> 01:02:50,700 can get closer to capacity with low-density parity-check 1154 01:02:50,700 --> 01:02:53,350 codes than with turbo codes. 1155 01:02:53,350 --> 01:02:58,530 They have other differences in characteristics, but, for both 1156 01:02:58,530 --> 01:03:01,440 of these reasons, there is certainly a move now. 1157 01:03:01,440 --> 01:03:05,800 The low-density parity-check codes seem to be the favored 1158 01:03:05,800 --> 01:03:08,120 ones in any new standards. 1159 01:03:08,120 --> 01:03:11,740 But we still have a lot of existing standards, and people 1160 01:03:11,740 --> 01:03:14,900 who've already developed turbo code chips and so forth who 1161 01:03:14,900 --> 01:03:17,290 have a vested interest against moving. 1162 01:03:17,290 --> 01:03:19,520 Perhaps analog devices is one like that. 1163 01:03:19,520 --> 01:03:22,350 1164 01:03:22,350 --> 01:03:25,720 So, although you can see the trend is toward low-density 1165 01:03:25,720 --> 01:03:29,920 parity-check codes, there are many industrial and 1166 01:03:29,920 --> 01:03:34,500 competitive factors and inertia factors. 1167 01:03:34,500 --> 01:03:36,210 They'll both be around for a long time. 1168 01:03:36,210 --> 01:03:38,580 AUDIENCE: [INAUDIBLE] 1169 01:03:38,580 --> 01:03:41,660 turbo code they have a patent you have to pay a royalty to 1170 01:03:41,660 --> 01:03:41,898 the company. 1171 01:03:41,898 --> 01:03:44,270 And with LDPC you don't have to-- 1172 01:03:44,270 --> 01:03:48,220 PROFESSOR: Yes, since this is a theoretical class, but, of 1173 01:03:48,220 --> 01:03:52,370 course, issues like patents are very important. 1174 01:03:52,370 --> 01:03:56,700 Berrou, Glavieux, and all were working at ENST 1175 01:03:56,700 --> 01:03:59,120 Bretagne up in Brittany. 1176 01:03:59,120 --> 01:04:01,260 They were funded by France Telecom. 1177 01:04:01,260 --> 01:04:06,760 France Telecom went out and owns all the turbo code 1178 01:04:06,760 --> 01:04:10,460 patents and has decided to enforce them. 1179 01:04:10,460 --> 01:04:13,600 Whereas Bob Gallager's patents all-- 1180 01:04:13,600 --> 01:04:15,340 We owned the ball. 1181 01:04:15,340 --> 01:04:17,990 We never made a dime. 1182 01:04:17,990 --> 01:04:21,120 They all duly expired around 1980. 1183 01:04:21,120 --> 01:04:24,380 And no one needs to worry about at least basic patents 1184 01:04:24,380 --> 01:04:26,620 on low-density parity-check codes. 1185 01:04:26,620 --> 01:04:30,170 Of course, refinements can always be patented. 1186 01:04:30,170 --> 01:04:32,920 So I don't know what the situation is there. 1187 01:04:32,920 --> 01:04:35,560 And that often makes a big difference as to what people 1188 01:04:35,560 --> 01:04:39,405 want to see standardized and used in practice. 1189 01:04:39,405 --> 01:04:40,680 So, excellent point. 1190 01:04:40,680 --> 01:04:45,880 1191 01:04:45,880 --> 01:04:48,010 All right, well, we can come back to this at any point. 1192 01:04:48,010 --> 01:04:50,830 Serial concatenation-- 1193 01:04:50,830 --> 01:04:55,190 Here the idea is you, basically, go through one 1194 01:04:55,190 --> 01:05:00,590 code, then you interleave, and then you go 1195 01:05:00,590 --> 01:05:03,250 through another code. 1196 01:05:03,250 --> 01:05:11,470 This is the kind of setup that I talked about back when we 1197 01:05:11,470 --> 01:05:13,760 talked about-- 1198 01:05:13,760 --> 01:05:21,160 This could be a small block code or convolutional code 1199 01:05:21,160 --> 01:05:24,030 that you do maximum likelihood decoding on, need to do a 1200 01:05:24,030 --> 01:05:25,700 Viterbi algorithm. 1201 01:05:25,700 --> 01:05:28,340 And this could be a Reed-Solomon code, and the 1202 01:05:28,340 --> 01:05:30,820 interleaver might be in there for some kind of burst 1203 01:05:30,820 --> 01:05:35,980 protection or to decorrelate any memory in 1204 01:05:35,980 --> 01:05:37,230 the channel out here. 1205 01:05:37,230 --> 01:05:40,810 1206 01:05:40,810 --> 01:05:44,790 So that's the context in which concatenated codes were 1207 01:05:44,790 --> 01:05:46,040 originally invented. 1208 01:05:46,040 --> 01:05:48,290 1209 01:05:48,290 --> 01:05:53,420 That's the way they're used on space channel for instance, 1210 01:05:53,420 --> 01:05:55,415 additive white Gaussian noise channel. 1211 01:05:55,415 --> 01:05:59,250 But here we're talking about the same block diagram, but 1212 01:05:59,250 --> 01:06:02,190 we're talking about much simpler codes. 1213 01:06:02,190 --> 01:06:05,650 And again, the idea is to build a big code using very 1214 01:06:05,650 --> 01:06:09,680 simple component codes, which is what we did in low-density 1215 01:06:09,680 --> 01:06:10,650 parity-check codes. 1216 01:06:10,650 --> 01:06:14,320 That's a big code built up, basically, out of 0 sum and 1217 01:06:14,320 --> 01:06:16,030 repetition codes. 1218 01:06:16,030 --> 01:06:20,800 Turbo code is a code built up out of two simple 1219 01:06:20,800 --> 01:06:23,770 convolutional codes. 1220 01:06:23,770 --> 01:06:31,820 Here, I'm going to talk about repeat-accumulate codes just 1221 01:06:31,820 --> 01:06:33,530 because they are so simple. 1222 01:06:33,530 --> 01:06:38,670 These were proposed by Divsalar and McEliece really 1223 01:06:38,670 --> 01:06:41,560 for the purpose of trying to find a simple enough turbo 1224 01:06:41,560 --> 01:06:45,100 code so you could prove some theorems about it. 1225 01:06:45,100 --> 01:06:47,570 There are hardly any theorems about turbo code. 1226 01:06:47,570 --> 01:06:48,820 It's all empirical. 1227 01:06:48,820 --> 01:06:53,690 1228 01:06:53,690 --> 01:06:56,660 We've got now some nice analytical tools. 1229 01:06:56,660 --> 01:06:59,770 In particular, the exit chart, which was a very nice, 1230 01:06:59,770 --> 01:07:04,080 empirical engineering chart like Bode plots and Nyquist 1231 01:07:04,080 --> 01:07:05,600 plots, things like that. 1232 01:07:05,600 --> 01:07:07,265 It has a real engineering flavor, but 1233 01:07:07,265 --> 01:07:09,400 it works very well. 1234 01:07:09,400 --> 01:07:15,630 The repeat accumulate code is basically this. 1235 01:07:15,630 --> 01:07:17,040 We take input bits here. 1236 01:07:17,040 --> 01:07:20,630 1237 01:07:20,630 --> 01:07:25,110 We repeat n times. 1238 01:07:25,110 --> 01:07:29,600 So this, if you like, is an n one n repetition code. 1239 01:07:29,600 --> 01:07:30,850 That's pretty simple. 1240 01:07:30,850 --> 01:07:32,920 1241 01:07:32,920 --> 01:07:36,900 We have a stream and a long block, we would then permute 1242 01:07:36,900 --> 01:07:39,720 everything within the block. 1243 01:07:39,720 --> 01:07:48,210 And then this is a rate one or one over one convolutional 1244 01:07:48,210 --> 01:07:52,600 code called an accumulator. 1245 01:07:52,600 --> 01:07:57,310 This is the code with transfer function one over one plus d, 1246 01:07:57,310 --> 01:08:06,090 that means that y k plus one is equal to y k 1247 01:08:06,090 --> 01:08:09,770 plus x k plus one. 1248 01:08:09,770 --> 01:08:12,070 So we have x coming in. 1249 01:08:12,070 --> 01:08:13,950 Here is one delay element. 1250 01:08:13,950 --> 01:08:18,000 Here's y k coming out. 1251 01:08:18,000 --> 01:08:20,930 And there is what that looks like. 1252 01:08:20,930 --> 01:08:23,109 Xk plus one. 1253 01:08:23,109 --> 01:08:26,340 yk plus one. 1254 01:08:26,340 --> 01:08:30,580 So it's a very simple rate one convolutional encoder with 1255 01:08:30,580 --> 01:08:35,200 feedback where I guess we take this as the output. 1256 01:08:35,200 --> 01:08:38,899 That's called an accumulator because, if you look at it, 1257 01:08:38,899 --> 01:08:42,240 what is yk doing? 1258 01:08:42,240 --> 01:08:46,960 You can show that yk plus one is simply the sum up to k plus 1259 01:08:46,960 --> 01:08:51,070 one of all the xk prime. 1260 01:08:51,070 --> 01:08:54,715 k prime equals whatever it starts at through k plus one 1261 01:08:54,715 --> 01:08:55,965 of all the xk prime. 1262 01:08:55,965 --> 01:09:00,149 1263 01:09:00,149 --> 01:09:04,260 It's nothing more than saying than saying, g of d equals one 1264 01:09:04,260 --> 01:09:08,760 over one plus d, equals one plus d plus e squared plus d. 1265 01:09:08,760 --> 01:09:12,359 The impulse response to this is infinite. 1266 01:09:12,359 --> 01:09:18,229 And every past xk shows up in every y. 1267 01:09:18,229 --> 01:09:20,640 This is just the sum of all the xks. 1268 01:09:20,640 --> 01:09:23,270 But, of course, in the binary field it's the mod 2 sum, so 1269 01:09:23,270 --> 01:09:25,279 it's only going to be 0 and one. 1270 01:09:25,279 --> 01:09:31,319 Well, it's a little two-state, rate one convolutional code. 1271 01:09:31,319 --> 01:09:35,279 About as simple as you can get and obviously useless as a 1272 01:09:35,279 --> 01:09:36,340 standalone coded. 1273 01:09:36,340 --> 01:09:39,399 Rate one coders have no redundancy. 1274 01:09:39,399 --> 01:09:43,170 They can't protect against anything. 1275 01:09:43,170 --> 01:09:49,979 So that's the structure which prior to turbo codes or 1276 01:09:49,979 --> 01:09:53,270 capacity approaching codes, you would have said, what? 1277 01:09:53,270 --> 01:09:54,960 What are we trying to achieve with this? 1278 01:09:54,960 --> 01:09:57,950 1279 01:09:57,950 --> 01:10:02,030 And the reason I talk about them it that the codes 1280 01:10:02,030 --> 01:10:03,960 actually does pretty well. 1281 01:10:03,960 --> 01:10:06,640 All right, what's its graph look like? 1282 01:10:06,640 --> 01:10:09,380 Over here we have input bits. 1283 01:10:09,380 --> 01:10:12,520 The input bits aren't actually part of the output in this 1284 01:10:12,520 --> 01:10:14,920 case, so I won't draw the dongle. 1285 01:10:14,920 --> 01:10:21,310 We just have an equals sign with n call n equals three, 1286 01:10:21,310 --> 01:10:25,180 repetition from each. 1287 01:10:25,180 --> 01:10:28,270 Oh, what's the overall rate of this code? 1288 01:10:28,270 --> 01:10:30,100 Here we have a rate one over n code. 1289 01:10:30,100 --> 01:10:32,950 We don't do anything to the rate here, so the overall rate 1290 01:10:32,950 --> 01:10:36,230 is one over n. 1291 01:10:36,230 --> 01:10:39,170 So let's take a rate 1/3. 1292 01:10:39,170 --> 01:10:43,540 So the graph, dot, dot, dot, looks something like this. 1293 01:10:43,540 --> 01:10:48,790 1294 01:10:48,790 --> 01:10:54,020 And then, as always, this element. 1295 01:10:54,020 --> 01:10:56,040 We take these bits in. 1296 01:10:56,040 --> 01:11:02,630 We permute them in some sort of random permutation. 1297 01:11:02,630 --> 01:11:04,590 And then over here, what do we have? 1298 01:11:04,590 --> 01:11:05,950 Well, we have a trellis again. 1299 01:11:05,950 --> 01:11:08,460 1300 01:11:08,460 --> 01:11:11,323 In this case, I can draw the trellis very explicitly. 1301 01:11:11,323 --> 01:11:13,880 1302 01:11:13,880 --> 01:11:20,700 If we consider this to be the information bit, and this to 1303 01:11:20,700 --> 01:11:27,190 be the previous state bit, so this is yk. 1304 01:11:27,190 --> 01:11:28,440 And here's-- 1305 01:11:28,440 --> 01:11:32,370 1306 01:11:32,370 --> 01:11:35,950 We're considering the y's to be the output, so this is xk. 1307 01:11:35,950 --> 01:11:39,730 1308 01:11:39,730 --> 01:11:41,855 I think it works either way. 1309 01:11:41,855 --> 01:11:48,070 Let's call this x k plus one plus y k equals y k plus one. 1310 01:11:48,070 --> 01:11:50,560 So this enforces the constraint. 1311 01:11:50,560 --> 01:11:52,540 This is really the branch. 1312 01:11:52,540 --> 01:11:55,000 This is just to propagate the y k and 1313 01:11:55,000 --> 01:11:58,700 present them as outputs. 1314 01:11:58,700 --> 01:12:03,120 So this little two state code, here's the state. 1315 01:12:03,120 --> 01:12:05,650 The state is also the output. 1316 01:12:05,650 --> 01:12:07,880 The state is what's in here. 1317 01:12:07,880 --> 01:12:10,280 And this is what it's trellis looks like. 1318 01:12:10,280 --> 01:12:21,730 1319 01:12:21,730 --> 01:12:23,000 That's the way this looks. 1320 01:12:23,000 --> 01:12:25,420 Of course, again, we need an equal number of sockets on 1321 01:12:25,420 --> 01:12:27,610 this side and on this side. 1322 01:12:27,610 --> 01:12:33,720 1323 01:12:33,720 --> 01:12:36,620 So how would you decode this code now? 1324 01:12:36,620 --> 01:12:41,070 1325 01:12:41,070 --> 01:12:42,620 What do we see initially? 1326 01:12:42,620 --> 01:12:47,120 We initially get received data, measured intrinsic 1327 01:12:47,120 --> 01:12:51,490 information, for each of the bits that we actually send 1328 01:12:51,490 --> 01:12:54,330 over the channel. 1329 01:12:54,330 --> 01:12:56,255 And what's our next step? 1330 01:12:56,255 --> 01:13:00,060 1331 01:13:00,060 --> 01:13:00,620 Trellis? 1332 01:13:00,620 --> 01:13:01,700 Yeah. 1333 01:13:01,700 --> 01:13:06,400 We do the sum-product algorithm on this trellis. 1334 01:13:06,400 --> 01:13:11,330 So we just do BCJR ignoring the fact that it's rate one. 1335 01:13:11,330 --> 01:13:12,580 That doesn't matter. 1336 01:13:12,580 --> 01:13:14,860 1337 01:13:14,860 --> 01:13:19,570 And so we will get some information for each of these 1338 01:13:19,570 --> 01:13:24,520 guys that we compute from the forward backward algorithm. 1339 01:13:24,520 --> 01:13:28,790 We'll ultimately get messages going in this direction. 1340 01:13:28,790 --> 01:13:32,950 Which come over here when we get them all. 1341 01:13:32,950 --> 01:13:36,350 And again, from these two messages, we can compute an 1342 01:13:36,350 --> 01:13:39,670 output message here, from these two, compute one there, 1343 01:13:39,670 --> 01:13:41,990 from these two, compute one there. 1344 01:13:41,990 --> 01:13:48,942 So we combine and re-propagate all these messages. 1345 01:13:48,942 --> 01:13:51,745 And that gives us new information over here. 1346 01:13:51,745 --> 01:13:54,430 1347 01:13:54,430 --> 01:13:57,440 And now, based on that, we can do BCJR again. 1348 01:13:57,440 --> 01:14:01,010 So again, it's this left right sort of alternation, one side, 1349 01:14:01,010 --> 01:14:10,740 other side which, eventually, spreads out the data through 1350 01:14:10,740 --> 01:14:11,650 the whole block. 1351 01:14:11,650 --> 01:14:14,843 We can use all the received data in a block to decode all 1352 01:14:14,843 --> 01:14:16,770 the data in the block. 1353 01:14:16,770 --> 01:14:20,380 Now does this work as well as either of the two previous 1354 01:14:20,380 --> 01:14:24,440 ones I put up, low-density parity-check or turbo? 1355 01:14:24,440 --> 01:14:30,610 Not quite, but it works amazingly well. 1356 01:14:30,610 --> 01:14:31,840 This is the moral here. 1357 01:14:31,840 --> 01:14:35,310 That even this incredibly simple code, where 1358 01:14:35,310 --> 01:14:37,880 nothing is going on-- 1359 01:14:37,880 --> 01:14:40,760 Again, all we have is binary state variables. 1360 01:14:40,760 --> 01:14:45,900 We have equals and 0 sum nodes, that's it. 1361 01:14:45,900 --> 01:14:50,350 It's made out of the simplest possible elements. 1362 01:14:50,350 --> 01:14:52,920 Even this code can get within a dB or 1363 01:14:52,920 --> 01:14:55,410 two of channel capacity. 1364 01:14:55,410 --> 01:15:00,200 And I'm old enough to know that in 1993, we would have 1365 01:15:00,200 --> 01:15:02,600 thought that was a miracle. 1366 01:15:02,600 --> 01:15:05,760 So if this had been the first code proposed at the ICC in 1367 01:15:05,760 --> 01:15:09,510 Geneva in 1993, and people had said, we can get a dB and a 1368 01:15:09,510 --> 01:15:13,350 half from capacity, everyone would have said, totally 1369 01:15:13,350 --> 01:15:16,880 unbelievable until they went home and simulated it. 1370 01:15:16,880 --> 01:15:24,740 So I put this up just to illustrate the power of these 1371 01:15:24,740 --> 01:15:26,420 ideas, and where they come from. 1372 01:15:26,420 --> 01:15:29,900 1373 01:15:29,900 --> 01:15:33,860 Of course, this idea of using the permutation as your 1374 01:15:33,860 --> 01:15:37,610 pseudo-random element so that you, from very simple 1375 01:15:37,610 --> 01:15:42,330 components, you get the effect of a large pseudo-random code, 1376 01:15:42,330 --> 01:15:46,990 could be a block length, a 1,000, 10,000, what have you, 1377 01:15:46,990 --> 01:15:48,610 this is absolutely key. 1378 01:15:48,610 --> 01:15:51,910 And this, basically, is what Gallager had when he said, if 1379 01:15:51,910 --> 01:15:56,567 I just use my parity-check matrix at random, even if it 1380 01:15:56,567 --> 01:16:00,660 is sparse, it's going to give me a random-like, which means 1381 01:16:00,660 --> 01:16:04,510 a pretty good, code, because that's the intuition I get 1382 01:16:04,510 --> 01:16:05,760 from Shannon and Elias. 1383 01:16:05,760 --> 01:16:10,870 1384 01:16:10,870 --> 01:16:14,730 That's the important part of the code construction, but 1385 01:16:14,730 --> 01:16:21,610 then the decoding part of the power is the sum-product 1386 01:16:21,610 --> 01:16:25,060 algorithm used in an iterative way. 1387 01:16:25,060 --> 01:16:29,260 The idea that you can simply let this algorithm run, and, 1388 01:16:29,260 --> 01:16:35,180 if the code is properly designed, it will eventually 1389 01:16:35,180 --> 01:16:39,760 integrate all the information over the block and converge to 1390 01:16:39,760 --> 01:16:42,490 some fixed point. 1391 01:16:42,490 --> 01:16:45,290 Although, even for such a simple code as this, for this 1392 01:16:45,290 --> 01:16:50,820 code McEliece and his students have a few theorems and can 1393 01:16:50,820 --> 01:16:56,380 say something about the convergence behavior, and what 1394 01:16:56,380 --> 01:16:57,460 it's actually going to do. 1395 01:16:57,460 --> 01:17:02,170 Even for this code, they can't get anything very definitive, 1396 01:17:02,170 --> 01:17:04,180 I would say. 1397 01:17:04,180 --> 01:17:09,100 So to me, the more important thing about-- 1398 01:17:09,100 --> 01:17:11,160 these are called RA codes-- 1399 01:17:11,160 --> 01:17:16,940 is that incredibly simple codes can do better than 1400 01:17:16,940 --> 01:17:26,700 concatenation of a 1,000 byte Reed-Solomon code over g f of 1401 01:17:26,700 --> 01:17:32,330 two to the 10 with a two to the 14 state Viterbi decoder. 1402 01:17:32,330 --> 01:17:38,620 That doesn't do as well as this crummy little thing does. 1403 01:17:38,620 --> 01:17:42,320 So that's good to know. 1404 01:17:42,320 --> 01:17:43,630 Any questions? 1405 01:17:43,630 --> 01:17:47,400 1406 01:17:47,400 --> 01:17:49,310 Well, it's a good stopping place. 1407 01:17:49,310 --> 01:17:53,660 So next time, now, if you kind of have an impressionistic 1408 01:17:53,660 --> 01:17:57,730 idea of how we do these codes. 1409 01:17:57,730 --> 01:18:00,140 Next time, I'm going to analyze low-density 1410 01:18:00,140 --> 01:18:09,050 parity-check codes over the binary erasure channel, where 1411 01:18:09,050 --> 01:18:13,610 you can do exact analysis, at least in the asymptotic case. 1412 01:18:13,610 --> 01:18:17,310 And that will show very clearly how it is that these 1413 01:18:17,310 --> 01:18:18,430 codes actually work. 1414 01:18:18,430 --> 01:18:22,730 It's a good model for all the codes in general. 1415 01:18:22,730 --> 01:18:26,200 I guess that means that you can't do a lot of 1416 01:18:26,200 --> 01:18:28,190 the homework again. 1417 01:18:28,190 --> 01:18:33,950 So for Wednesday, what should we do? 1418 01:18:33,950 --> 01:18:35,310 AUDIENCE: [INAUDIBLE] 1419 01:18:35,310 --> 01:18:38,100 on Friday then? 1420 01:18:38,100 --> 01:18:41,192 PROFESSOR: Friday or Monday? 1421 01:18:41,192 --> 01:18:43,060 Monday seems to be popular. 1422 01:18:43,060 --> 01:18:46,140 1423 01:18:46,140 --> 01:18:49,490 So for Wednesday, just do-- 1424 01:18:49,490 --> 01:18:52,750 1425 01:18:52,750 --> 01:18:55,558 There's one problem left over from problem set eight. 1426 01:18:55,558 --> 01:18:58,910 1427 01:18:58,910 --> 01:19:06,020 And that's kind of a grungy problem but worthwhile doing. 1428 01:19:06,020 --> 01:19:10,000 Try to do the sum-product algorithm at least once. 1429 01:19:10,000 --> 01:19:15,290 So just do that for Wednesday, and then for next Monday, a 1430 01:19:15,290 --> 01:19:19,572 week from today, problem set nine other than that. 1431 01:19:19,572 --> 01:19:23,110 1432 01:19:23,110 --> 01:19:25,110 I'll see you Wednesday. 1433 01:19:25,110 --> 01:19:34,527