1 00:00:00,000 --> 00:00:04,180 PROFESSOR: OK, well I'm going to start now. 2 00:00:04,180 --> 00:00:07,735 As I say, I know that the wireless course has its final 3 00:00:07,735 --> 00:00:11,720 at 11:00, so we might not see the people who are taking it. 4 00:00:11,720 --> 00:00:14,770 Is anyone here in the wireless course? 5 00:00:14,770 --> 00:00:16,510 OK. 6 00:00:16,510 --> 00:00:21,860 Q.E.D. Ipso facto ergo sum. 7 00:00:21,860 --> 00:00:25,590 OK, just to remind you, I think we have Problem Set 10 8 00:00:25,590 --> 00:00:26,270 solutions today. 9 00:00:26,270 --> 00:00:29,510 In any case, they'll be available on the web. 10 00:00:29,510 --> 00:00:33,300 The final is next Tuesday. 11 00:00:33,300 --> 00:00:36,540 Do bring calculators if you have them. 12 00:00:36,540 --> 00:00:39,170 They won't be absolutely essential, but 13 00:00:39,170 --> 00:00:40,420 they might be useful. 14 00:00:40,420 --> 00:00:43,220 15 00:00:43,220 --> 00:00:47,340 You may bring five sheets of notes. 16 00:00:47,340 --> 00:00:51,680 It's a good exercise to make these up. 17 00:00:51,680 --> 00:00:54,480 And otherwise, it's closed-book. 18 00:00:54,480 --> 00:00:57,860 Ashish will hold a review session tomorrow, 4:00 to 19 00:00:57,860 --> 00:01:04,084 6:00, 26-328, which I'm sure will be excellent as usual. 20 00:01:04,084 --> 00:01:07,450 21 00:01:07,450 --> 00:01:11,120 All right, just to remind you, we're in Chapter 14. 22 00:01:11,120 --> 00:01:15,590 Most of the course we talked about coding for power-limited 23 00:01:15,590 --> 00:01:18,070 channels, where basically you could get away with binary 24 00:01:18,070 --> 00:01:21,010 codes with very little loss of optimality. 25 00:01:21,010 --> 00:01:24,070 For bandwidth-limited, additive white Gaussian noise 26 00:01:24,070 --> 00:01:26,890 channels, we've got to consider non-binary, 27 00:01:26,890 --> 00:01:29,680 multi-level codes, we've really got to go out into 28 00:01:29,680 --> 00:01:32,820 Euclidian space and use Euclidian distance as our 29 00:01:32,820 --> 00:01:36,390 metric rather than Hamming distance. 30 00:01:36,390 --> 00:01:42,750 So we started out with a simple idea, build a lattice 31 00:01:42,750 --> 00:01:44,610 constellation. 32 00:01:44,610 --> 00:01:49,440 A lattice is an infinite set of points in end space that 33 00:01:49,440 --> 00:01:51,030 has a group property. 34 00:01:51,030 --> 00:01:53,640 That's it, a discrete set of points. 35 00:01:53,640 --> 00:01:58,450 We take a finite set of them by chopping out a region R, a 36 00:01:58,450 --> 00:02:03,620 compact region, which chops out a finite number of points 37 00:02:03,620 --> 00:02:07,220 in this lattice or in a translate of the lattice. 38 00:02:07,220 --> 00:02:12,060 And we went through this exercise of computing the 39 00:02:12,060 --> 00:02:17,470 union-bound estimate, which I remind you is a reasonable 40 00:02:17,470 --> 00:02:20,280 estimate for codes that are not too complex. 41 00:02:20,280 --> 00:02:21,430 We're not going to use this for 42 00:02:21,430 --> 00:02:23,450 capacity-approaching codes. 43 00:02:23,450 --> 00:02:28,840 But for codes, where..., basically dominated by minimum 44 00:02:28,840 --> 00:02:33,080 distance properties, how many nearest neighbors are there, 45 00:02:33,080 --> 00:02:36,580 the likeliest error events are all to the nearest neighbors, 46 00:02:36,580 --> 00:02:39,980 we can use the union-bound estimate, which basically just 47 00:02:39,980 --> 00:02:43,940 tallies the probability of error to the nearest neighbor 48 00:02:43,940 --> 00:02:47,320 events by the union-bound, which itself is inaccurate if 49 00:02:47,320 --> 00:02:50,830 you get too many near neighbor events. 50 00:02:50,830 --> 00:02:55,320 And we've got this nice approximate expression that 51 00:02:55,320 --> 00:02:59,520 the probability of error per n dimensions, if we're signaling 52 00:02:59,520 --> 00:03:02,640 in n dimensions, is the number of nearest neighbors in the 53 00:03:02,640 --> 00:03:09,310 lattice times the Q to the square root of a function 54 00:03:09,310 --> 00:03:13,760 times an expression, which involves a coding gain of the 55 00:03:13,760 --> 00:03:19,110 lattice, and separably a shaping gain of the region 56 00:03:19,110 --> 00:03:22,490 times 3 times SNR norm. 57 00:03:22,490 --> 00:03:25,910 So this embodies all kinds of simplifications. 58 00:03:25,910 --> 00:03:29,540 It separates the effects of the lattice and the region. 59 00:03:29,540 --> 00:03:32,710 Basically, we can optimize each of these separately to 60 00:03:32,710 --> 00:03:34,720 optimize this expression. 61 00:03:34,720 --> 00:03:39,200 And also, by the way, by talking about SNR norm, which 62 00:03:39,200 --> 00:03:45,520 is SNR normalized by 2 to the spectral efficiency, it makes 63 00:03:45,520 --> 00:03:48,520 this whole expression independent of rate or 64 00:03:48,520 --> 00:03:51,420 equivalently independent of spectral efficiency. 65 00:03:51,420 --> 00:03:55,690 We saw this back when we talked about m by m QAM, we 66 00:03:55,690 --> 00:03:58,285 got a universal expression. 67 00:03:58,285 --> 00:04:02,210 The probability of error was simply this expression with a 68 00:04:02,210 --> 00:04:06,550 3SNR norm in here - regardless of what m was (regardless of 69 00:04:06,550 --> 00:04:09,730 how big the QAM constellation was), we got the same 70 00:04:09,730 --> 00:04:10,920 approximate expression. 71 00:04:10,920 --> 00:04:14,550 So this is also independent of the size of the constellations 72 00:04:14,550 --> 00:04:19,200 in this large constellation, high SNR approximation. 73 00:04:19,200 --> 00:04:23,450 Once you get to enough points, everything sort of washes out. 74 00:04:23,450 --> 00:04:26,760 So it's very useful. 75 00:04:26,760 --> 00:04:31,170 And I remind you that the coding gain basically depends 76 00:04:31,170 --> 00:04:36,650 on the minimum square distance normalized by the density of 77 00:04:36,650 --> 00:04:39,270 the lattice, if you like, normalized to two dimensions. 78 00:04:39,270 --> 00:04:45,700 The shaping gain is basically the shaping gain of an n-cube 79 00:04:45,700 --> 00:04:46,780 divided by-- 80 00:04:46,780 --> 00:04:49,310 this is the normalized second moment of an n-cube, this is 81 00:04:49,310 --> 00:04:52,140 the normalized second moment of your region, which better 82 00:04:52,140 --> 00:04:55,730 be better than that of an n-cube, meaning smaller. 83 00:04:55,730 --> 00:04:59,920 And writing it out, it's equal to this, where this is the 84 00:04:59,920 --> 00:05:02,970 second moment of your region. 85 00:05:02,970 --> 00:05:06,840 And this is the volume, again, normalized to two dimensions. 86 00:05:06,840 --> 00:05:09,520 So the baseline constellations, we showed 87 00:05:09,520 --> 00:05:12,840 these were invariant to Cartesian products. 88 00:05:12,840 --> 00:05:15,520 In any number of dimensions, n, we can take the integer 89 00:05:15,520 --> 00:05:21,520 lattice or any translate of the integer lattice and we can 90 00:05:21,520 --> 00:05:24,300 take a region, which is the n-cube -- 91 00:05:24,300 --> 00:05:28,250 which will chop out basically a square or cubic 92 00:05:28,250 --> 00:05:30,590 constellation, a regular constellation in n 93 00:05:30,590 --> 00:05:31,660 dimensions-- 94 00:05:31,660 --> 00:05:34,980 and we'll get that the coding gain is the shaping gain is 1. 95 00:05:34,980 --> 00:05:42,860 So we'll get just our baseline expression for any integer 96 00:05:42,860 --> 00:05:47,880 lattice shaped by an n-cube centered on the origin. 97 00:05:47,880 --> 00:05:49,100 And this is what it looks like. 98 00:05:49,100 --> 00:05:53,170 This is back from Chapter Four or whatever. 99 00:05:53,170 --> 00:05:56,720 We get this universal curve, the baseline curve, which 100 00:05:56,720 --> 00:06:01,930 holds for m-PAM, m by m QAM, or you can Cartesian product 101 00:06:01,930 --> 00:06:04,870 these up into as high a dimension as you like. 102 00:06:04,870 --> 00:06:08,610 The constellation we're talking about is really m-PAM 103 00:06:08,610 --> 00:06:11,190 Cartesian product to the nth. 104 00:06:11,190 --> 00:06:13,080 For any of those constellations, if we 105 00:06:13,080 --> 00:06:16,330 normalize the probability of error to two dimensions-- 106 00:06:16,330 --> 00:06:19,340 which is what I'm recommending to you, normalize everything 107 00:06:19,340 --> 00:06:23,480 per two dimensions in the high SNR regime-- 108 00:06:23,480 --> 00:06:26,240 then we basically get the number of near neighbors in 109 00:06:26,240 --> 00:06:31,775 Z-squared, the QAM lattice, which is 4 times Q to the 110 00:06:31,775 --> 00:06:33,480 square root of 3SNR norm. 111 00:06:33,480 --> 00:06:35,980 And it looks like this. 112 00:06:35,980 --> 00:06:38,260 We plot probability of error per two 113 00:06:38,260 --> 00:06:40,940 dimensions over SNR norm. 114 00:06:40,940 --> 00:06:44,160 I think at 10 to the minus 5, it's 8.4 dB. 115 00:06:44,160 --> 00:06:46,770 Does anybody remember? 116 00:06:46,770 --> 00:06:49,000 But it's somewhere around 9 dB. 117 00:06:49,000 --> 00:06:51,540 And the Shannon limit, as we recall, is for SNR 118 00:06:51,540 --> 00:06:53,700 norm, it's at 0 dB. 119 00:06:53,700 --> 00:06:56,420 So this is where we can play. 120 00:06:56,420 --> 00:07:00,090 Any code will fall somewhere between these two curves, and 121 00:07:00,090 --> 00:07:04,370 the name of the game is to get a code the gets as close to 122 00:07:04,370 --> 00:07:06,560 the Shannon limit as possible. 123 00:07:06,560 --> 00:07:10,300 And at least in this moderate complexity regime, the way we 124 00:07:10,300 --> 00:07:14,020 play the game is we try to optimize the shaping region, 125 00:07:14,020 --> 00:07:18,190 we try to optimize the lattice, we're going to get a 126 00:07:18,190 --> 00:07:21,680 certain gain from shaping, and a certain gain from coding, 127 00:07:21,680 --> 00:07:27,230 de-rated by the number of nearest neighbors, which is 128 00:07:27,230 --> 00:07:29,840 going to turn out to be an important effect for some 129 00:07:29,840 --> 00:07:31,630 well-known lattices because they have huge 130 00:07:31,630 --> 00:07:33,210 numbers of near neighbors. 131 00:07:33,210 --> 00:07:36,870 And that will give us some curve somewhere in here, and 132 00:07:36,870 --> 00:07:38,570 we plot that and we're done. 133 00:07:38,570 --> 00:07:41,290 We've written a paper for that particular lattice 134 00:07:41,290 --> 00:07:43,245 constellation, for its performance. 135 00:07:43,245 --> 00:07:49,358 136 00:07:49,358 --> 00:07:53,840 Today I'm going to talk quickly about shaping, because 137 00:07:53,840 --> 00:08:00,390 that's a very easy story, and obvious, and 138 00:08:00,390 --> 00:08:01,900 it won't take long. 139 00:08:01,900 --> 00:08:05,540 Then I'm going to talk about lattices, which is really a 140 00:08:05,540 --> 00:08:10,430 subject in mathematics, what's known about lattices. 141 00:08:10,430 --> 00:08:13,630 I guess the decoding part of that story is not mathematics. 142 00:08:13,630 --> 00:08:16,550 That's engineering. 143 00:08:16,550 --> 00:08:21,410 And then I'm going to talk about trellis codes, which are 144 00:08:21,410 --> 00:08:25,600 the analog of convolutional codes, and which, similarly to 145 00:08:25,600 --> 00:08:28,090 the way convolutional codes beat block codes for the 146 00:08:28,090 --> 00:08:30,780 bandwidth for the power-limited regime, trellis 147 00:08:30,780 --> 00:08:35,140 codes tend to beat lattice codes in terms of performance 148 00:08:35,140 --> 00:08:40,950 versus complexity for the bandwidth-limited regime. 149 00:08:40,950 --> 00:08:42,010 So, shaping. 150 00:08:42,010 --> 00:08:45,410 Shaping is really an almost trivial story. 151 00:08:45,410 --> 00:08:52,200 This really wasn't recognized as a separable issue until 152 00:08:52,200 --> 00:08:57,650 perhaps sometime in the '80s, when trellis-coded modulation 153 00:08:57,650 --> 00:08:58,280 was invented. 154 00:08:58,280 --> 00:09:03,020 In '82 was Ungerboeck's paper. 155 00:09:03,020 --> 00:09:04,900 That was really the breakthrough in 156 00:09:04,900 --> 00:09:10,240 bandwidth-limited coding, that trellis codes were the first 157 00:09:10,240 --> 00:09:13,000 bandwidth-limited codes that were widely implemented. 158 00:09:13,000 --> 00:09:15,950 And after people analyzed them for a while, they realized 159 00:09:15,950 --> 00:09:19,590 that you could separate out the shaping effect from the 160 00:09:19,590 --> 00:09:23,370 coding effect, which is what I've shown by this expression. 161 00:09:23,370 --> 00:09:28,580 So anyone care to guess what the optimum region is in n 162 00:09:28,580 --> 00:09:29,980 dimensions? 163 00:09:29,980 --> 00:09:33,480 I guess I've already mentioned it last time. 164 00:09:33,480 --> 00:09:35,540 The optimum region, what do we want to do? 165 00:09:35,540 --> 00:09:39,440 We want to minimize the normalized second moment-- 166 00:09:39,440 --> 00:09:42,150 167 00:09:42,150 --> 00:09:44,540 well, a second moment with appropriate normalization, 168 00:09:44,540 --> 00:09:45,810 what would you do? 169 00:09:45,810 --> 00:09:47,870 Well, the optimum region for just about anything is an 170 00:09:47,870 --> 00:09:51,660 n-sphere, and it certainly is here. 171 00:09:51,660 --> 00:09:54,650 So we take Rn equals an n-sphere. 172 00:09:54,650 --> 00:09:57,800 173 00:09:57,800 --> 00:10:04,400 If we have a two-dimensional sphere, what are its 174 00:10:04,400 --> 00:10:05,650 parameters? 175 00:10:05,650 --> 00:10:08,510 176 00:10:08,510 --> 00:10:13,810 We certainly know that the volume of this region, if this 177 00:10:13,810 --> 00:10:15,405 is R, it's pi times R squared. 178 00:10:15,405 --> 00:10:19,430 179 00:10:19,430 --> 00:10:28,500 And the second moment of this region, how do we do that? 180 00:10:28,500 --> 00:10:31,670 We integrate ... go to polar coordinates, 0 to 2pi, 181 00:10:31,670 --> 00:10:38,190 d pi, 0 to R, rdr. 182 00:10:38,190 --> 00:10:41,590 And then what are we measuring? 183 00:10:41,590 --> 00:10:45,400 The second moment is r squared, but we normalize it 184 00:10:45,400 --> 00:10:47,020 per dimension, which is 2. 185 00:10:47,020 --> 00:10:49,740 186 00:10:49,740 --> 00:10:55,820 Oh, and we've got to take the uniform distribution over v of 187 00:10:55,820 --> 00:10:59,220 R, and that's one over pi R squared. 188 00:10:59,220 --> 00:11:02,130 So have I got it now? 189 00:11:02,130 --> 00:11:04,970 This is the second moment of a uniform distribution, a 190 00:11:04,970 --> 00:11:09,100 probability distribution over the 2-sphere. 191 00:11:09,100 --> 00:11:14,230 And so this will be 1 over 2pi R squared times 192 00:11:14,230 --> 00:11:19,690 R 4th over 4, right? 193 00:11:19,690 --> 00:11:23,520 194 00:11:23,520 --> 00:11:24,500 Is that all correct? 195 00:11:24,500 --> 00:11:32,510 And so p of R over v of R is already not normalized to two 196 00:11:32,510 --> 00:11:35,870 dimensions, so we don't have to re-normalize it. 197 00:11:35,870 --> 00:11:44,620 198 00:11:44,620 --> 00:11:46,290 I didn't get the 2pi in here. 199 00:11:46,290 --> 00:11:50,950 200 00:11:50,950 --> 00:11:51,970 I need some help, class. 201 00:11:51,970 --> 00:11:53,790 When it comes down to integration, I'm not 202 00:11:53,790 --> 00:11:56,680 necessarily the world's best. 203 00:11:56,680 --> 00:12:00,350 So R squared over 4... 204 00:12:00,350 --> 00:12:09,510 R squared over 4pi R squared, so we get 1 over 4pi. 205 00:12:09,510 --> 00:12:10,050 Is that right? 206 00:12:10,050 --> 00:12:11,670 That looks about right because it's fairly 207 00:12:11,670 --> 00:12:12,920 close to 1 over 12. 208 00:12:12,920 --> 00:12:15,370 209 00:12:15,370 --> 00:12:18,390 So what is the shaping gain of a 2-sphere? 210 00:12:18,390 --> 00:12:22,790 211 00:12:22,790 --> 00:12:25,680 And I can just say 2-sphere, because I know it's invariant 212 00:12:25,680 --> 00:12:28,250 to scaling. 213 00:12:28,250 --> 00:12:31,780 Rotation isn't going to do much to it. 214 00:12:31,780 --> 00:12:39,220 It's 1/12 over this, the normalized second moment, 1 215 00:12:39,220 --> 00:12:47,220 over 4pi, which is pi over 3, which is about 2/10 of a dB. 216 00:12:47,220 --> 00:12:51,530 OK, so I've improved the second moment by 2/10 of a dB, 217 00:12:51,530 --> 00:12:53,920 reduced it to 2/10 of a dB. 218 00:12:53,920 --> 00:12:57,730 This is not very impressive. 219 00:12:57,730 --> 00:13:00,680 So of course, a lot of the early work was on shaping 220 00:13:00,680 --> 00:13:02,930 two-dimensional constellations. 221 00:13:02,930 --> 00:13:06,270 And this basically says if you get a large constellation, you 222 00:13:06,270 --> 00:13:10,250 don't even see this effect to, say, 64-QAM. 223 00:13:10,250 --> 00:13:13,955 If you have a 64-QAM constellation, 8 by 8-- 224 00:13:13,955 --> 00:13:23,870 225 00:13:23,870 --> 00:13:26,370 Somebody at Paradyne noticed that you could improve it 226 00:13:26,370 --> 00:13:30,390 slightly by taking the four corner points out and putting 227 00:13:30,390 --> 00:13:34,686 them up here, without reducing the minimum distance. 228 00:13:34,686 --> 00:13:40,860 OK, so there is an improved, more spherical 64-point 229 00:13:40,860 --> 00:13:41,690 constellation. 230 00:13:41,690 --> 00:13:44,840 It's improved by about 0.1 dB, as I remember. 231 00:13:44,840 --> 00:13:49,710 And what this calculation says is if you go up to 256, 1024, 232 00:13:49,710 --> 00:13:55,350 and you simply take all the points in the QAM grid that 233 00:13:55,350 --> 00:13:58,830 are surrounded by a sphere of appropriate size to pick out 2 234 00:13:58,830 --> 00:14:02,860 to the n points, for high, large constellations you get a 235 00:14:02,860 --> 00:14:04,790 gain of about 0.2 dB. 236 00:14:04,790 --> 00:14:09,030 So this is nothing to write home about. 237 00:14:09,030 --> 00:14:11,850 What happens as n goes to infinity? 238 00:14:11,850 --> 00:14:15,370 239 00:14:15,370 --> 00:14:19,570 We look up in a math book what the expressions are for the 240 00:14:19,570 --> 00:14:23,070 normalized second moment-- actually, you can do it just 241 00:14:23,070 --> 00:14:26,360 by this kind of calculation. 242 00:14:26,360 --> 00:14:28,010 It's easy enough. 243 00:14:28,010 --> 00:14:39,475 And just by scaling, you'll find that the shaping gain of 244 00:14:39,475 --> 00:14:49,460 the n-sphere goes to pi times e over 6, which is 1.53 dB. 245 00:14:49,460 --> 00:14:52,630 A famous number not only now in shaping, but also in 246 00:14:52,630 --> 00:14:55,850 quantization, where you're also interested in minimizing 247 00:14:55,850 --> 00:14:59,560 the second moment of a quantization cell. 248 00:14:59,560 --> 00:15:02,210 249 00:15:02,210 --> 00:15:06,450 Or it's something like 0.229 bits per two dimensions, is 250 00:15:06,450 --> 00:15:08,600 another way of expressing it. 251 00:15:08,600 --> 00:15:12,100 All right, so what is this? 252 00:15:12,100 --> 00:15:15,090 This is the maximum shaping gain you could get by the 253 00:15:15,090 --> 00:15:19,470 optimum region in the optimum number of dimensions, which is 254 00:15:19,470 --> 00:15:21,040 as large as you can go. 255 00:15:21,040 --> 00:15:24,090 So this says this is the ultimate shaping gain. 256 00:15:24,090 --> 00:15:26,120 You can never get a shaping gain of more 257 00:15:26,120 --> 00:15:29,650 than 1 and 1/2 dB. 258 00:15:29,650 --> 00:15:34,490 So it says when we play this game, we've got about 9 dB 259 00:15:34,490 --> 00:15:37,255 down here that we want to make up at 10 to the minus 5, 10 to 260 00:15:37,255 --> 00:15:42,820 the minus 6, we can get only 1 and a 1/2 dB of it by doing 261 00:15:42,820 --> 00:15:45,260 good shaping in large dimensions. 262 00:15:45,260 --> 00:15:47,620 That's the best we can ever do. 263 00:15:47,620 --> 00:15:49,390 So that's a little bit discouraging. 264 00:15:49,390 --> 00:15:53,230 It says shaping is never going to give you that much. 265 00:15:53,230 --> 00:15:57,400 On the other hand, you can't get this 1 and a 1/2 dB 266 00:15:57,400 --> 00:15:59,040 in any other way. 267 00:15:59,040 --> 00:16:01,380 If you have n-cubed constellations, you will 268 00:16:01,380 --> 00:16:04,870 always be limited to be 1 and a 1/2 dB away 269 00:16:04,870 --> 00:16:07,570 from the Shannon limit. 270 00:16:07,570 --> 00:16:09,990 So if you want to approach the Shannon limit, you do have to 271 00:16:09,990 --> 00:16:12,230 address the shaping problem. 272 00:16:12,230 --> 00:16:13,840 You can't ignore it. 273 00:16:13,840 --> 00:16:21,020 1 and a 1/2 dB is enough to be noticed in most applications, 274 00:16:21,020 --> 00:16:24,750 so you should do some moderate shaping. 275 00:16:24,750 --> 00:16:27,240 Now, of course we can plot the curve. 276 00:16:27,240 --> 00:16:31,280 It's done in the notes for any n whatsoever, and you'll see 277 00:16:31,280 --> 00:16:34,380 that it goes up fairly steeply at first. 278 00:16:34,380 --> 00:16:41,450 It gets to about 1 dB at 16 dimensions, so if you shape in 279 00:16:41,450 --> 00:16:45,820 a 16 dimensional sphere, you can get 1 dB out of this 280 00:16:45,820 --> 00:16:48,950 maximum of 1 and a 1/2 dBs you can ever get. 281 00:16:48,950 --> 00:16:53,170 If you go to 32, it's 1.2 dB or something like that, it 282 00:16:53,170 --> 00:16:55,840 begins to slope out. 283 00:16:55,840 --> 00:17:02,260 So that gives you a good idea of what you 284 00:17:02,260 --> 00:17:04,109 can actually attain. 285 00:17:04,109 --> 00:17:09,200 In the V.34 modem, for instance, a rather simple 286 00:17:09,200 --> 00:17:13,740 shaping scheme is used that gets up to about 0.8 dB of 287 00:17:13,740 --> 00:17:14,609 shaping gain. 288 00:17:14,609 --> 00:17:16,840 It's called shaping on regions. 289 00:17:16,840 --> 00:17:20,630 290 00:17:20,630 --> 00:17:25,700 I just mentioned some techniques for shaping. 291 00:17:25,700 --> 00:17:29,480 As with a lot of things, once shaping was realized to be a 292 00:17:29,480 --> 00:17:33,220 separate subject from coding, there was a flurry 293 00:17:33,220 --> 00:17:34,270 of activity on it. 294 00:17:34,270 --> 00:17:37,670 People basically proposed a number of different schemes, 295 00:17:37,670 --> 00:17:41,480 particularly in the context of the V.34 modem standards 296 00:17:41,480 --> 00:17:42,952 development. 297 00:17:42,952 --> 00:17:50,010 Of which trellis shaping, I would 298 00:17:50,010 --> 00:17:53,000 say, is the most elegant. 299 00:17:53,000 --> 00:17:58,210 This is kind of a dual to trellis-coded modulation where 300 00:17:58,210 --> 00:18:01,310 we use trellis codes for shaping rather than coding. 301 00:18:01,310 --> 00:18:03,290 So that's elegant. 302 00:18:03,290 --> 00:18:08,440 But a cruder and quite effective, just fine 303 00:18:08,440 --> 00:18:16,960 technique, shell mapping, was used in the V.34 modem. 304 00:18:16,960 --> 00:18:21,700 The basic idea here is that you take a two-dimensional 305 00:18:21,700 --> 00:18:27,000 constellation, you just divide it into shells like this. 306 00:18:27,000 --> 00:18:30,610 It turns out in two dimensions, if you take a 307 00:18:30,610 --> 00:18:36,540 constant delta here, that the average energy goes up, I 308 00:18:36,540 --> 00:18:42,960 think, linearly with delta or some way nicely with delta. 309 00:18:42,960 --> 00:18:48,980 You take a constellation bigger than you really need, 310 00:18:48,980 --> 00:18:50,970 so you have the possibility of some redundancy. 311 00:18:50,970 --> 00:18:56,090 312 00:18:56,090 --> 00:18:59,750 So you identify each point in the constellation by which 313 00:18:59,750 --> 00:19:03,900 region it lands in. 314 00:19:03,900 --> 00:19:06,220 You then go up to 16 dimensions or something-- 315 00:19:06,220 --> 00:19:09,770 I think it is 16 dimensions in the V.34 modem-- 316 00:19:09,770 --> 00:19:17,640 and you assign each series of points a score depending on 317 00:19:17,640 --> 00:19:20,690 which shells its points land in. 318 00:19:20,690 --> 00:19:27,150 And you basically have a big table that chooses the lowest 319 00:19:27,150 --> 00:19:34,100 energy combinations from all the possible series of eight 320 00:19:34,100 --> 00:19:37,860 shells, which can be done fairly elegantly using 321 00:19:37,860 --> 00:19:39,290 generating function techniques. 322 00:19:39,290 --> 00:19:43,010 I realize this is just hand-waving and you can't get 323 00:19:43,010 --> 00:19:50,100 it, but the effect is that you use this shell with very high 324 00:19:50,100 --> 00:19:50,730 probability. 325 00:19:50,730 --> 00:19:53,560 You sort of get a Gaussian-like probability on 326 00:19:53,560 --> 00:19:55,650 the shells. 327 00:19:55,650 --> 00:19:57,860 Let me just draw that like this. 328 00:19:57,860 --> 00:19:59,750 You don't use the points out in this 329 00:19:59,750 --> 00:20:01,410 outermost shell very much. 330 00:20:01,410 --> 00:20:04,880 You use this a lot, and they sort of have an overall 331 00:20:04,880 --> 00:20:07,290 Gaussian distribution. 332 00:20:07,290 --> 00:20:09,720 And I should mention that this is an equivalent way of 333 00:20:09,720 --> 00:20:10,970 getting shaping gain. 334 00:20:10,970 --> 00:20:17,010 335 00:20:17,010 --> 00:20:21,270 If we're shaping uniformly over an n-sphere in a high 336 00:20:21,270 --> 00:20:26,870 number n of dimensions and we basically have constellations 337 00:20:26,870 --> 00:20:32,880 which consist of two-dimensional QAM points, 338 00:20:32,880 --> 00:20:36,805 what is the projection of a uniform distribution over an 339 00:20:36,805 --> 00:20:39,990 n-sphere down onto two dimensions? 340 00:20:39,990 --> 00:20:43,560 If we look at each two-dimensional component of 341 00:20:43,560 --> 00:20:47,266 these n-dimensional vectors, what distribution will it have 342 00:20:47,266 --> 00:20:52,180 if we impose a uniform spherical distribution on the 343 00:20:52,180 --> 00:20:53,830 high dimensional constellation? 344 00:20:53,830 --> 00:20:59,040 It will turn out that it becomes Gaussian in two 345 00:20:59,040 --> 00:21:00,560 dimensions. 346 00:21:00,560 --> 00:21:01,750 Think of the projection of the 347 00:21:01,750 --> 00:21:04,110 2-sphere down on one dimension. 348 00:21:04,110 --> 00:21:07,580 The projection of a 2-sphere on one dimension is 349 00:21:07,580 --> 00:21:09,730 something like this. 350 00:21:09,730 --> 00:21:14,570 It's not Gaussian, but there's more probability that one of 351 00:21:14,570 --> 00:21:18,040 the coordinates will be near 0 than it will be out at one of 352 00:21:18,040 --> 00:21:19,990 these maxima here. 353 00:21:19,990 --> 00:21:24,230 So this is just the same thing raised up to n dimensions. 354 00:21:24,230 --> 00:21:27,020 So an equivalent way of looking at this problem is we 355 00:21:27,020 --> 00:21:30,620 want somehow to get a Gaussian-like distribution on 356 00:21:30,620 --> 00:21:33,880 a one- or two-dimensional constellation, and this is one 357 00:21:33,880 --> 00:21:36,390 way of doing it. 358 00:21:36,390 --> 00:21:40,700 And you can get the same pi times e over 6 factor by just 359 00:21:40,700 --> 00:21:44,680 looking at it from an entropy point of view, the entropy of 360 00:21:44,680 --> 00:21:47,420 a two-dimensional Gaussian distribution relative to the 361 00:21:47,420 --> 00:21:51,750 entropy of a uniform distribution over a square. 362 00:21:51,750 --> 00:21:54,992 That will give you the same factor if you 363 00:21:54,992 --> 00:21:57,300 do everything right. 364 00:21:57,300 --> 00:22:01,120 OK so basically, shaping is easy. 365 00:22:01,120 --> 00:22:04,970 These techniques are not difficult to implement. 366 00:22:04,970 --> 00:22:09,320 You can get one dB of shaping gain quite easily through a 367 00:22:09,320 --> 00:22:12,230 variety of techniques. 368 00:22:12,230 --> 00:22:14,550 It's worth getting that one dB, you're not going to get it 369 00:22:14,550 --> 00:22:17,050 by any other means. 370 00:22:17,050 --> 00:22:19,660 But having done that, that's all you're ever going to get, 371 00:22:19,660 --> 00:22:22,460 and so end of story on shaping. 372 00:22:22,460 --> 00:22:29,260 So as I said, it was a flurry of activity in the '90s, and 373 00:22:29,260 --> 00:22:30,510 no one has looked at shaping since then. 374 00:22:30,510 --> 00:22:38,270 375 00:22:38,270 --> 00:22:39,870 So that's part of the story. 376 00:22:39,870 --> 00:22:42,730 377 00:22:42,730 --> 00:22:47,180 Let's continue now with lattices, an old 378 00:22:47,180 --> 00:22:48,430 mathematical subject. 379 00:22:48,430 --> 00:22:51,580 380 00:22:51,580 --> 00:22:55,170 So what we're interested in is, what's the densest lattice 381 00:22:55,170 --> 00:22:57,096 packing in n dimensions? 382 00:22:57,096 --> 00:22:59,970 383 00:22:59,970 --> 00:23:03,380 This appeared in mathematics, long before it appeared in 384 00:23:03,380 --> 00:23:05,330 engineering, as Hermite's parameter. 385 00:23:05,330 --> 00:23:07,440 And Hermite said this was the right way to measure the 386 00:23:07,440 --> 00:23:10,540 density of a lattice, normalized in all the 387 00:23:10,540 --> 00:23:11,380 appropriate ways. 388 00:23:11,380 --> 00:23:15,290 So any version of a lattice is equivalent. 389 00:23:15,290 --> 00:23:18,960 A version is something that you get by scaling or rotating 390 00:23:18,960 --> 00:23:24,020 or even by Cartesian products, which I'm not sure how 391 00:23:24,020 --> 00:23:26,860 widespread that idea is. 392 00:23:26,860 --> 00:23:30,642 So what's the densest lattice in two dimensions again? 393 00:23:30,642 --> 00:23:35,760 We want to find the densest lattice, in terms of coding 394 00:23:35,760 --> 00:23:38,700 gain or Hermite's parameter in n dimensions. 395 00:23:38,700 --> 00:23:43,392 396 00:23:43,392 --> 00:23:46,230 Anyone care to guess what the densest lattice in two 397 00:23:46,230 --> 00:23:49,500 dimensions is? 398 00:23:49,500 --> 00:23:52,000 It's the hexagonal lattice. 399 00:23:52,000 --> 00:24:00,660 So in two dimensions, hexagonal, which reasons of 400 00:24:00,660 --> 00:24:04,690 mathematical history is denoted A_2. 401 00:24:04,690 --> 00:24:12,190 And its coding gain, I believe we computed it last time, and 402 00:24:12,190 --> 00:24:13,620 it was 0.6 dB. 403 00:24:13,620 --> 00:24:18,870 404 00:24:18,870 --> 00:24:25,280 So what's the most we could ever do by fooling around with 405 00:24:25,280 --> 00:24:26,810 two-dimensional constellations? 406 00:24:26,810 --> 00:24:33,040 Suppose I want the best possible 256 point QAM 407 00:24:33,040 --> 00:24:35,350 constellation? 408 00:24:35,350 --> 00:24:39,990 Well, according to these large constellation approximations, 409 00:24:39,990 --> 00:24:47,540 the best I could do would be to take the 256 lowest energy 410 00:24:47,540 --> 00:24:50,260 points in some translate of the hexagonal lattice. 411 00:24:50,260 --> 00:24:53,210 So I might fool around with the translation vector a 412 00:24:53,210 --> 00:24:57,960 little bit to try to find the absolute lowest energy point, 413 00:24:57,960 --> 00:24:59,580 but it really wouldn't matter very much 414 00:24:59,580 --> 00:25:02,020 regardless of what I did. 415 00:25:02,020 --> 00:25:06,240 I could expect 0.6 dB of coding gain and 0.2 dB of 416 00:25:06,240 --> 00:25:14,360 shaping gain, or 0.8 dB better than the 8 by 8 - sorry the 16 417 00:25:14,360 --> 00:25:19,100 by 16 QAM constellation with the same number of points and 418 00:25:19,100 --> 00:25:20,350 the same minimum distance. 419 00:25:20,350 --> 00:25:24,140 420 00:25:24,140 --> 00:25:28,340 This basically tells you what your options are. 421 00:25:28,340 --> 00:25:30,670 2D, there's not much to do. 422 00:25:30,670 --> 00:25:33,300 You remember way back in Chapter One, I gave you this 423 00:25:33,300 --> 00:25:36,060 problem about the 16 point, 2D constellation. 424 00:25:36,060 --> 00:25:41,690 That is precisely 16 points from a certain translate of 425 00:25:41,690 --> 00:25:45,600 the hexagonal lattice that fall within a circle that's 426 00:25:45,600 --> 00:25:48,370 just big enough to enclose 16 points. 427 00:25:48,370 --> 00:25:54,810 And it has, I forget, something like a 0.7 dB gain 428 00:25:54,810 --> 00:25:59,210 over the 4 by 4 square constellation. 429 00:25:59,210 --> 00:26:02,810 We computed that in the very first homework. 430 00:26:02,810 --> 00:26:05,840 So again, staying to two dimensions, 431 00:26:05,840 --> 00:26:07,120 things aren't very exciting. 432 00:26:07,120 --> 00:26:10,340 433 00:26:10,340 --> 00:26:13,270 Turns out, it's most interesting to go 434 00:26:13,270 --> 00:26:14,710 in powers of two. 435 00:26:14,710 --> 00:26:21,320 In four dimensions, the densest lattice is something 436 00:26:21,320 --> 00:26:26,700 called D4, Schlafly's lattice, 1850-something. 437 00:26:26,700 --> 00:26:34,260 And its coding gain is precisely the square root of 438 00:26:34,260 --> 00:26:36,530 2, which is 1.5 dB. 439 00:26:36,530 --> 00:26:42,965 440 00:26:42,965 --> 00:26:53,610 8 dimensions, it's E8, Gosset's lattice, about 1900. 441 00:26:53,610 --> 00:26:57,660 The D4 and E8 come, again, from the mathematical 442 00:26:57,660 --> 00:26:59,800 literature and have something to do with their relationship 443 00:26:59,800 --> 00:27:02,380 to certain groups. 444 00:27:02,380 --> 00:27:07,230 Lattices and finite groups are very closely connected. 445 00:27:07,230 --> 00:27:12,420 And this has a coding gain of 2 or 3 dB. 446 00:27:12,420 --> 00:27:18,100 16 dimensions, it's something just called lambda 16. 447 00:27:18,100 --> 00:27:23,010 It's a Barnes-Wall lattice, as all of these are, actually. 448 00:27:23,010 --> 00:27:26,630 And it's 2 to the 3/2, or 4.5 dB. 449 00:27:26,630 --> 00:27:28,380 You see a certain pattern here? 450 00:27:28,380 --> 00:27:31,080 451 00:27:31,080 --> 00:27:36,910 In 32 dimensions, we have two lattices that I'll mention. 452 00:27:36,910 --> 00:27:43,850 There's the 32-dimensional Barnes-Wall lattice, which has 453 00:27:43,850 --> 00:27:45,100 a coding gain of 4.6 dB. 454 00:27:45,100 --> 00:27:48,500 455 00:27:48,500 --> 00:27:54,330 Or there's actually Quebbeman in the '60s, I think, came up 456 00:27:54,330 --> 00:27:55,470 with a denser lattice. 457 00:27:55,470 --> 00:28:00,000 So this is still a subject of active investigation, 458 00:28:00,000 --> 00:28:02,760 particularly in dimensions like 19, where it's not so 459 00:28:02,760 --> 00:28:05,290 easy to find the densest lattice. 460 00:28:05,290 --> 00:28:08,555 And this, I forget, is maybe 6.2 dB. 461 00:28:08,555 --> 00:28:11,510 It's definitely denser. 462 00:28:11,510 --> 00:28:12,810 But it's something like that. 463 00:28:12,810 --> 00:28:19,930 464 00:28:19,930 --> 00:28:22,660 This basically goes to infinity. 465 00:28:22,660 --> 00:28:25,340 You can get denser and denser lattices just by following 466 00:28:25,340 --> 00:28:28,460 this chain here which is a chain of Barnes-Wall lattices. 467 00:28:28,460 --> 00:28:31,630 468 00:28:31,630 --> 00:28:35,920 The nominal coding gain can be taken to infinity, just as we 469 00:28:35,920 --> 00:28:41,100 saw with kd over n. 470 00:28:41,100 --> 00:28:44,570 That goes to infinity for rate 1/2 Reed-Muller codes. 471 00:28:44,570 --> 00:28:47,390 472 00:28:47,390 --> 00:28:51,870 But of course, Shannon says we can't ever get more than 9 dB 473 00:28:51,870 --> 00:28:53,900 of effective coding gain here. 474 00:28:53,900 --> 00:28:56,810 Or actually, we can't get more than 7 and a 1/2 dB if we take 475 00:28:56,810 --> 00:28:59,150 into account that 1 and a 1/2 is going to be given by 476 00:28:59,150 --> 00:29:01,020 shaping gain. 477 00:29:01,020 --> 00:29:04,230 So what must be happening here? 478 00:29:04,230 --> 00:29:08,200 We must be having a huge number of near neighbors. 479 00:29:08,200 --> 00:29:12,250 The number of nearest neighbors in the hexagonal 480 00:29:12,250 --> 00:29:14,960 lattice is six. 481 00:29:14,960 --> 00:29:25,830 In D4 it's 24, in E8 it's 240, in lambda 16 482 00:29:25,830 --> 00:29:27,980 I think it's 4320-- 483 00:29:27,980 --> 00:29:30,840 the correct numbers are in the notes. 484 00:29:30,840 --> 00:29:37,100 By the time we get up here, we get something like a 146,680 485 00:29:37,100 --> 00:29:39,360 or something like that. 486 00:29:39,360 --> 00:29:44,640 So these lattices are designed to have a very 487 00:29:44,640 --> 00:29:46,580 high degree of symmetry. 488 00:29:46,580 --> 00:29:51,100 That means if you stand on any point, you look around you, 489 00:29:51,100 --> 00:29:53,790 they've pushed the neighboring points as far away 490 00:29:53,790 --> 00:29:55,710 from you as they can. 491 00:29:55,710 --> 00:29:58,140 But now there are a great many of them, so you get a uniform 492 00:29:58,140 --> 00:30:02,190 sky just filled with points around you, a number of 493 00:30:02,190 --> 00:30:05,100 dimensions. 494 00:30:05,100 --> 00:30:10,880 So that's what the problem is and that means that the 495 00:30:10,880 --> 00:30:12,250 effective coding gain-- 496 00:30:12,250 --> 00:30:14,790 497 00:30:14,790 --> 00:30:16,630 I again do the calculation. 498 00:30:16,630 --> 00:30:20,340 I know here we lose at least two dB. 499 00:30:20,340 --> 00:30:21,590 This is something like 3.8 dB. 500 00:30:21,590 --> 00:30:24,440 501 00:30:24,440 --> 00:30:30,030 OK, so the effective coding gain actually sags and begins 502 00:30:30,030 --> 00:30:31,760 to top out as you get out here. 503 00:30:31,760 --> 00:30:35,690 504 00:30:35,690 --> 00:30:38,060 Maybe nowadays you could think of implementing a larger 505 00:30:38,060 --> 00:30:41,930 lattice, but I think this is the largest anyone has ever 506 00:30:41,930 --> 00:30:43,850 thought about implementing. 507 00:30:43,850 --> 00:30:47,900 And what do we get? 508 00:30:47,900 --> 00:30:49,560 A coding gain of less than 4 dB -- 509 00:30:49,560 --> 00:30:51,500 an effective coding gain. 510 00:30:51,500 --> 00:30:57,140 So if you use that, you'd be, say, 511 00:30:57,140 --> 00:30:58,870 somewhere around 5 db here. 512 00:30:58,870 --> 00:31:01,845 513 00:31:01,845 --> 00:31:09,660 We go over 6 dB, but then we go up by this normalized per 514 00:31:09,660 --> 00:31:12,470 two dimensions, so we divide by 16. 515 00:31:12,470 --> 00:31:20,980 That's still 10,000, which is still 13 factors of 2, 516 00:31:20,980 --> 00:31:23,120 which is 2.6 dB. 517 00:31:23,120 --> 00:31:25,780 You can see where the problem is. 518 00:31:25,780 --> 00:31:29,980 So anyway, we get something that's really this moved way 519 00:31:29,980 --> 00:31:35,575 up a lot more, and as a result we get a much steeper curve. 520 00:31:35,575 --> 00:31:38,300 521 00:31:38,300 --> 00:31:43,480 This method doesn't work up here, but this might be lambda 522 00:31:43,480 --> 00:31:47,500 16 or lambda 32. 523 00:31:47,500 --> 00:31:50,040 And then we can get another 1 and a 1/2 dB of shaping gain. 524 00:31:50,040 --> 00:31:52,500 So maybe 4 dB, optimistically. 525 00:31:52,500 --> 00:31:59,740 526 00:31:59,740 --> 00:32:00,990 OK, not really. 527 00:32:00,990 --> 00:32:04,500 528 00:32:04,500 --> 00:32:06,770 So that's a little disappointing. 529 00:32:06,770 --> 00:32:14,130 Just by looking up in the math textbooks, we don't do very 530 00:32:14,130 --> 00:32:17,310 striking things. 531 00:32:17,310 --> 00:32:22,470 I mention in particular the Barnes-Wall lattices, and if I 532 00:32:22,470 --> 00:32:27,080 had more time I would develop them because they're very much 533 00:32:27,080 --> 00:32:30,100 analogous to the Reed-Muller codes. 534 00:32:30,100 --> 00:32:35,060 They are constructed by a u, u plus v construction in the 535 00:32:35,060 --> 00:32:36,740 same way as Reed-Muller codes. 536 00:32:36,740 --> 00:32:41,830 They are length-doubling constructions that also double 537 00:32:41,830 --> 00:32:46,480 the distance, just as the Reed-Muller codes do now 538 00:32:46,480 --> 00:32:48,580 Euclidian distance. 539 00:32:48,580 --> 00:32:52,140 But let me just give you the first couple of sentences in a 540 00:32:52,140 --> 00:32:57,010 discussion of the Barnes-Wall lattices, which were only 541 00:32:57,010 --> 00:32:59,357 discovered in '59, about the same time as 542 00:32:59,357 --> 00:33:00,607 the Reed-Muller codes. 543 00:33:00,607 --> 00:33:03,300 544 00:33:03,300 --> 00:33:06,225 Suppose we take the QAM grid like this. 545 00:33:06,225 --> 00:33:09,770 546 00:33:09,770 --> 00:33:13,570 An important observation is that if we take every other 547 00:33:13,570 --> 00:33:18,570 point in sort-of checkerboard fashion, what do we get? 548 00:33:18,570 --> 00:33:24,520 549 00:33:24,520 --> 00:33:26,990 Imagine it's going to infinity in both directions. 550 00:33:26,990 --> 00:33:31,270 551 00:33:31,270 --> 00:33:36,940 So this is a subset of half the points, basically. 552 00:33:36,940 --> 00:33:46,490 Half the density, twice the volume of points that, itself 553 00:33:46,490 --> 00:33:48,890 is a rotated and scaled version 554 00:33:48,890 --> 00:33:50,140 of the integer lattice. 555 00:33:50,140 --> 00:33:53,150 556 00:33:53,150 --> 00:33:55,470 Take the centers on a checkerboard and they form a 557 00:33:55,470 --> 00:33:59,660 45 degree rotated and square root of 2 scaled version of 558 00:33:59,660 --> 00:34:01,830 the integer lattice. 559 00:34:01,830 --> 00:34:05,320 If this had minimum squared distance 1 between points, 560 00:34:05,320 --> 00:34:07,859 then this has minimum squared distance 2 between points. 561 00:34:07,859 --> 00:34:10,710 562 00:34:10,710 --> 00:34:13,639 So we could label the points red, black, 563 00:34:13,639 --> 00:34:16,770 red, black, red, black. 564 00:34:16,770 --> 00:34:21,340 If we did that, the red points would be a co-set of this 565 00:34:21,340 --> 00:34:25,020 sub-lattice and the black points would be a co-set-- 566 00:34:25,020 --> 00:34:26,429 meaning a translate-- 567 00:34:26,429 --> 00:34:29,110 of this sub-lattice. 568 00:34:29,110 --> 00:34:31,420 So let me write that as follows. 569 00:34:31,420 --> 00:34:36,620 If we take Z-squared, it has a sub-lattice which we call RZ 570 00:34:36,620 --> 00:34:39,560 squared, r for rotation. 571 00:34:39,560 --> 00:34:43,690 Rotation by the Hadamard matrix, 1, 1, 1 minus 1. 572 00:34:43,690 --> 00:34:48,820 573 00:34:48,820 --> 00:34:54,230 If I write d min squared, this has d min squared at 1, this 574 00:34:54,230 --> 00:34:58,030 has twice the d min squared. 575 00:34:58,030 --> 00:35:02,230 So I partition my lattice, or any translate of this lattice, 576 00:35:02,230 --> 00:35:06,450 into two co-sets of the sub-lattice with twice the 577 00:35:06,450 --> 00:35:08,270 minimum squared distance. 578 00:35:08,270 --> 00:35:11,880 This is the first steps in what Ungerboeck called set 579 00:35:11,880 --> 00:35:14,370 partitioning. 580 00:35:14,370 --> 00:35:18,840 So it's an obvious way to partition any QAM-type signal 581 00:35:18,840 --> 00:35:21,270 set, red and black points. 582 00:35:21,270 --> 00:35:24,170 Having done that, I can do it again. 583 00:35:24,170 --> 00:35:26,190 Alright, do it again, what do I get? 584 00:35:26,190 --> 00:35:31,330 So now I'm going to take every other one of these points, 585 00:35:31,330 --> 00:35:33,760 which will leave me, say, these 4 points. 586 00:35:33,760 --> 00:35:39,410 Let me call these A, A, A, A. These points might be B, B, B, 587 00:35:39,410 --> 00:35:41,975 B, the other ones that I cut out. 588 00:35:41,975 --> 00:35:52,320 I could call these C, C, C, C and D, D, D, D. Now I've 589 00:35:52,320 --> 00:35:59,150 partitioned each of these subsets into two subsets. 590 00:35:59,150 --> 00:36:04,140 I've partitioned one into A, B and the other into C, D, such 591 00:36:04,140 --> 00:36:06,130 that - what does A look like? 592 00:36:06,130 --> 00:36:10,200 593 00:36:10,200 --> 00:36:14,800 A is another translate of a lattice. 594 00:36:14,800 --> 00:36:18,110 This happens to be Z-squared scaled by 2. 595 00:36:18,110 --> 00:36:21,850 It's not rotated, it's just Z-squared scaled by 2. 596 00:36:21,850 --> 00:36:24,350 So we get down to 2 times Z-squared. 597 00:36:24,350 --> 00:36:26,020 And what's its minimum squared distance? 598 00:36:26,020 --> 00:36:26,835 AUDIENCE: 4. 599 00:36:26,835 --> 00:36:28,300 PROFESSOR: 4. 600 00:36:28,300 --> 00:36:29,705 So I've doubled the distance again. 601 00:36:29,705 --> 00:36:39,010 602 00:36:39,010 --> 00:36:41,790 This is an elementary but important observation. 603 00:36:41,790 --> 00:36:44,120 I can continually go through these, 604 00:36:44,120 --> 00:36:45,840 partitioning into two subsets. 605 00:36:45,840 --> 00:36:48,910 Every time I do, I double the distance. 606 00:36:48,910 --> 00:36:54,270 I get another version of the integer lattice at a higher 607 00:36:54,270 --> 00:36:56,550 scale and, perhaps, rotated. 608 00:36:56,550 --> 00:37:02,410 So if I did it again, I would get eight subsets with minimum 609 00:37:02,410 --> 00:37:08,220 squared distance 8 between points in each subset. 610 00:37:08,220 --> 00:37:13,510 So it's just a repeated divide-by-2 scheme. 611 00:37:13,510 --> 00:37:15,650 All right, now to get the Barnes-Wall lattices, you 612 00:37:15,650 --> 00:37:18,290 remember how we got the Reed-Muller codes. 613 00:37:18,290 --> 00:37:24,210 We took, say, two codes of length 2 and we put them 614 00:37:24,210 --> 00:37:27,570 together with the u, u plus v construction and we got codes 615 00:37:27,570 --> 00:37:32,190 of length 4 that had the minimum square distance of the 616 00:37:32,190 --> 00:37:36,380 higher distance code, if we chose them properly. 617 00:37:36,380 --> 00:37:38,640 That's the same thing we do here. 618 00:37:38,640 --> 00:37:45,330 If we put together these two lattices, if we choose them-- 619 00:37:45,330 --> 00:37:50,390 well, just use the u, u plus v construction where u is from 620 00:37:50,390 --> 00:37:55,350 Z-squared and v is from RZ-squared. 621 00:37:55,350 --> 00:37:57,290 So in words, that's what you do. 622 00:37:57,290 --> 00:37:59,475 If you're interested in looking it up, look 623 00:37:59,475 --> 00:38:00,710 it up in the notes. 624 00:38:00,710 --> 00:38:07,030 What you get is a lattice, D4, that has normalized density 625 00:38:07,030 --> 00:38:10,080 halfway between that of Z-squared and RZ-squared, it 626 00:38:10,080 --> 00:38:11,340 turns out-- 627 00:38:11,340 --> 00:38:14,340 sort of analogous to the code-- and its minimum square 628 00:38:14,340 --> 00:38:16,990 distance is 2. 629 00:38:16,990 --> 00:38:20,190 Or if you put these two together, you get something 630 00:38:20,190 --> 00:38:24,635 called RD4, whose minimum square distance is 4. 631 00:38:24,635 --> 00:38:27,690 632 00:38:27,690 --> 00:38:32,510 So you get something whose normalized volume is halfway 633 00:38:32,510 --> 00:38:35,650 between that of these two normalized volumes, but it has 634 00:38:35,650 --> 00:38:39,180 the same minimum distance as this guy, and that's where you 635 00:38:39,180 --> 00:38:41,460 get the coding gain from. 636 00:38:41,460 --> 00:38:44,650 This is denser but still has the same minimum distance. 637 00:38:44,650 --> 00:38:47,730 638 00:38:47,730 --> 00:38:51,140 If we do this again, go out to eight dimensions, we get, it 639 00:38:51,140 --> 00:38:53,670 turns out, E8. 640 00:38:53,670 --> 00:38:58,190 And this has minimum square distance 4. 641 00:38:58,190 --> 00:39:01,860 But it has the same normalized volume normalized back to two 642 00:39:01,860 --> 00:39:05,610 dimensions as this guy, which only had minimum squared 643 00:39:05,610 --> 00:39:07,300 distance 2. 644 00:39:07,300 --> 00:39:10,360 So that's precisely why this has a nominal 645 00:39:10,360 --> 00:39:12,150 coding gain of 2. 646 00:39:12,150 --> 00:39:15,520 We've doubled the minimum square distance without 647 00:39:15,520 --> 00:39:18,700 changing its density, normalized back to two 648 00:39:18,700 --> 00:39:19,950 dimensions. 649 00:39:19,950 --> 00:39:22,140 650 00:39:22,140 --> 00:39:25,530 All right, so you get all the Barnes-Wall lattices just by 651 00:39:25,530 --> 00:39:26,030 doing this. 652 00:39:26,030 --> 00:39:28,730 This turns out to be a sub-lattice of this guy. 653 00:39:28,730 --> 00:39:32,480 Not surprisingly, just as these lattices are nested, 654 00:39:32,480 --> 00:39:35,160 just as the Reed-Muller codes are nested, so you get a 655 00:39:35,160 --> 00:39:36,270 similar tableau. 656 00:39:36,270 --> 00:39:40,800 You get a similar construction that you can take out to 16 657 00:39:40,800 --> 00:39:43,190 dimensions, 32 dimensions, however many 658 00:39:43,190 --> 00:39:44,660 dimensions you want. 659 00:39:44,660 --> 00:39:48,410 And every time you do, you increase the coding gain by a 660 00:39:48,410 --> 00:39:51,810 factor of square root of 2, so the coding gain eventually 661 00:39:51,810 --> 00:39:54,500 gets driven to infinity, and that's the story on 662 00:39:54,500 --> 00:39:55,550 Barnes-Wall lattices. 663 00:39:55,550 --> 00:40:00,410 So similarly to Reed-Muller codes, these are lattices that 664 00:40:00,410 --> 00:40:04,440 are the densest known in certain small dimensions like 665 00:40:04,440 --> 00:40:06,220 4, 8, and 16. 666 00:40:06,220 --> 00:40:08,560 We don't know any denser lattices. 667 00:40:08,560 --> 00:40:12,270 You start to get up to 32, 64 dimensions, then we do know of 668 00:40:12,270 --> 00:40:14,000 denser lattices. 669 00:40:14,000 --> 00:40:16,750 But they are not nearly as nicely structured, and maybe 670 00:40:16,750 --> 00:40:22,020 these are still the best from a complexity point of view. 671 00:40:22,020 --> 00:40:27,090 You can play similar games on building trellis 672 00:40:27,090 --> 00:40:29,462 representations of these lattices, as we did for 673 00:40:29,462 --> 00:40:29,860 Reed-Muller codes. 674 00:40:29,860 --> 00:40:33,010 They have similar kinds of trellises because they're 675 00:40:33,010 --> 00:40:34,260 based on the same construction. 676 00:40:34,260 --> 00:40:36,920 677 00:40:36,920 --> 00:40:39,580 So that's the story of Barnes-Wall lattices. 678 00:40:39,580 --> 00:40:44,480 The most famous lattice is the Leech lattice, which is a 679 00:40:44,480 --> 00:40:51,000 super-dense lattice in 24 dimensions. 680 00:40:51,000 --> 00:40:53,790 It has a coding gain of 6 dB. 681 00:40:53,790 --> 00:40:58,630 682 00:40:58,630 --> 00:41:04,620 And unfortunately, it has 195,560 near neighbors or 683 00:41:04,620 --> 00:41:05,870 something like that. 684 00:41:05,870 --> 00:41:09,870 685 00:41:09,870 --> 00:41:13,990 So you can see, it turns out it's a very close cousin of 686 00:41:13,990 --> 00:41:18,160 this 32-dimensional Barnes-Wall lattice. 687 00:41:18,160 --> 00:41:29,960 It's related to the 24-12-8 Golay code in the same way as 688 00:41:29,960 --> 00:41:34,710 the Barnes-Wall lattices are to the Reed-Muller codes. 689 00:41:34,710 --> 00:41:37,980 So the fact that the Golay code is so exceptional can be 690 00:41:37,980 --> 00:41:41,850 seen just as a projection of the fact that the Leech 691 00:41:41,850 --> 00:41:43,470 lattice is so exceptional. 692 00:41:43,470 --> 00:41:47,440 This somehow has the Golay code buried in it, if you can 693 00:41:47,440 --> 00:41:49,660 find it in here. 694 00:41:49,660 --> 00:41:54,310 And the Leech lattice is particularly notable not just 695 00:41:54,310 --> 00:41:57,890 because it has remarkably high coding gain for its 696 00:41:57,890 --> 00:42:00,810 dimension-- it's remarkably dense for its dimension, 697 00:42:00,810 --> 00:42:03,110 exceptional-- 698 00:42:03,110 --> 00:42:07,400 but also because it has remarkable symmetries, so it's 699 00:42:07,400 --> 00:42:11,060 connected to some of the largest exceptional groups, 700 00:42:11,060 --> 00:42:13,760 the monster exceptional groups. 701 00:42:13,760 --> 00:42:16,950 And it was a key step in the classification of all finite 702 00:42:16,950 --> 00:42:23,040 groups to find the symmetry group of this lattice. 703 00:42:23,040 --> 00:42:27,480 Just a little liberal arts for you. 704 00:42:27,480 --> 00:42:29,250 So that's what we can get with lattices. 705 00:42:29,250 --> 00:42:32,080 By going out to the Leech lattice or the Barnes-Wall 706 00:42:32,080 --> 00:42:35,690 lattice-- this could equally well be the Leech lattice-- 707 00:42:35,690 --> 00:42:39,540 again, effective coding gain is only about 4 dB or maybe 708 00:42:39,540 --> 00:42:42,210 even less because of the exceptional number of near 709 00:42:42,210 --> 00:42:43,460 neighbors here. 710 00:42:43,460 --> 00:42:48,390 711 00:42:48,390 --> 00:42:52,440 To one digit of significance, that's approximately its 712 00:42:52,440 --> 00:42:53,690 coding gain. 713 00:42:53,690 --> 00:42:56,720 714 00:42:56,720 --> 00:43:01,958 So how can we go beyond this? 715 00:43:01,958 --> 00:43:09,280 As I said already, the next great breakthrough was trellis 716 00:43:09,280 --> 00:43:12,495 codes for which Gottfried Ungerboeck became famous. 717 00:43:12,495 --> 00:43:19,490 718 00:43:19,490 --> 00:43:24,480 Trellis codes, as I say in the notes, are basically-- 719 00:43:24,480 --> 00:43:27,200 first of all, Ungerboeck thought about the problem from 720 00:43:27,200 --> 00:43:29,450 a Euclidian distance point of view. 721 00:43:29,450 --> 00:43:32,860 So what you had to do to break out of 722 00:43:32,860 --> 00:43:34,822 Hamming distance thinking. 723 00:43:34,822 --> 00:43:37,490 He had the idea that in the bandwidth-limited regime, what 724 00:43:37,490 --> 00:43:40,000 you want to do is expand the constellation rather than 725 00:43:40,000 --> 00:43:41,730 expand the bandwidth. 726 00:43:41,730 --> 00:43:48,690 So to send four bits per second per Hertz. 727 00:43:48,690 --> 00:43:54,740 You could do that using uncoded 16-QAM constellation. 728 00:43:54,740 --> 00:43:59,350 Or Ungerboeck saw, well, let's make it into a 32-point 729 00:43:59,350 --> 00:44:00,430 constellation. 730 00:44:00,430 --> 00:44:03,970 Now we have some redundancy, now we can do some coding on 731 00:44:03,970 --> 00:44:05,220 this constellation. 732 00:44:05,220 --> 00:44:07,440 733 00:44:07,440 --> 00:44:11,760 He used the set partitioning idea, which I've just 734 00:44:11,760 --> 00:44:14,360 explained to you. 735 00:44:14,360 --> 00:44:18,200 Initially, he just looked at a QAM constellation and he said, 736 00:44:18,200 --> 00:44:27,960 let's divide it up into A, B, A, B, C, D, C, D, A, B, A, B, 737 00:44:27,960 --> 00:44:37,350 C, D, C, D. So let's partition it from A, B, C, D into A and 738 00:44:37,350 --> 00:44:41,870 D as I've done it here, and B and C are these two subsets. 739 00:44:41,870 --> 00:44:48,320 And we'll break this up into A and D and B and C. And then 740 00:44:48,320 --> 00:44:51,340 some theoretical people came along and said, well, this is 741 00:44:51,340 --> 00:44:54,810 just Z-squared, this is RZ-squared, and this is 742 00:44:54,810 --> 00:44:56,060 2Z-squared. 743 00:44:56,060 --> 00:45:01,330 744 00:45:01,330 --> 00:45:04,386 Let's, first of all, partition our enlarged constellation. 745 00:45:04,386 --> 00:45:07,100 746 00:45:07,100 --> 00:45:08,905 Now here's the setup we're going to use for coding. 747 00:45:08,905 --> 00:45:13,040 748 00:45:13,040 --> 00:45:15,240 We are going to bring in our ...If we're trying to send-- 749 00:45:15,240 --> 00:45:20,120 I forget what notation I used in the notes-- b bits per two 750 00:45:20,120 --> 00:45:21,370 dimensions. 751 00:45:21,370 --> 00:45:28,570 752 00:45:28,570 --> 00:45:31,250 Let's take one bit per two dimensions and put it into a 753 00:45:31,250 --> 00:45:32,740 rate 1/2 convolutional code. 754 00:45:32,740 --> 00:45:36,760 755 00:45:36,760 --> 00:45:38,010 So we're going to get out two bits. 756 00:45:38,010 --> 00:45:41,450 757 00:45:41,450 --> 00:45:44,130 Everything here is going to be per two dimensions because 758 00:45:44,130 --> 00:45:46,610 we're going to use a two-dimensional signal set. 759 00:45:46,610 --> 00:45:50,420 And we'll bring in our other b minus 1 bits down here. 760 00:45:50,420 --> 00:45:51,890 These are called uncoded bits. 761 00:45:51,890 --> 00:45:55,770 762 00:45:55,770 --> 00:45:58,370 For these two bits, we're going to go 763 00:45:58,370 --> 00:46:00,295 into a subset selector. 764 00:46:00,295 --> 00:46:04,480 765 00:46:04,480 --> 00:46:07,040 Two bits are going to select among-- 766 00:46:07,040 --> 00:46:12,855 this going to be something from A, B, C, or D. It's going 767 00:46:12,855 --> 00:46:14,725 to tell us which subset to use. 768 00:46:14,725 --> 00:46:18,780 769 00:46:18,780 --> 00:46:23,710 All right, then we'll use that in combination with these b 770 00:46:23,710 --> 00:46:37,990 minus 1 bits to select a point from a 2 to the b plus 1 bit 771 00:46:37,990 --> 00:46:39,240 QAM constellation. 772 00:46:39,240 --> 00:46:41,530 773 00:46:41,530 --> 00:46:42,750 Two dimensions. 774 00:46:42,750 --> 00:46:47,650 So this is actually our signal point y, our two-dimensional 775 00:46:47,650 --> 00:46:50,220 signal point. 776 00:46:50,220 --> 00:46:54,590 Do you see how the numbers work out? 777 00:46:54,590 --> 00:47:00,280 We want to send b bits per QAM point, per two dimensions. 778 00:47:00,280 --> 00:47:06,410 We're going to use a 2 to the b plus 1 point constellation, 779 00:47:06,410 --> 00:47:08,050 so 32 instead of 16, say. 780 00:47:08,050 --> 00:47:10,890 781 00:47:10,890 --> 00:47:20,280 Take one bit in here, generate two streams, one redundant. 782 00:47:20,280 --> 00:47:24,120 This will tell us A, B, C, D, so that's two of the bits you 783 00:47:24,120 --> 00:47:25,930 need to select one of these points. 784 00:47:25,930 --> 00:47:29,720 785 00:47:29,720 --> 00:47:34,640 Say, in a 16-point constellation, we'll provide a 786 00:47:34,640 --> 00:47:36,080 bit label that looks like this. 787 00:47:36,080 --> 00:47:41,220 For A, it will be 0, 0. b is 0, 1, c is 1, 0, D is 1, 1. 788 00:47:41,220 --> 00:47:44,530 That's always the low-order bits in any selection for A, 789 00:47:44,530 --> 00:47:48,220 B, C, D. And then we'll take two high-order bits, which 790 00:47:48,220 --> 00:47:51,950 then tell us which of these four groups it's in. 791 00:47:51,950 --> 00:47:56,470 So we'll have another 0, 0, 0, 1, 1, 0, 1, 1. 792 00:47:56,470 --> 00:47:59,140 793 00:47:59,140 --> 00:48:02,000 Now I'm talking about b equals 3. 794 00:48:02,000 --> 00:48:05,360 We have two bits that come in here and select one of these 795 00:48:05,360 --> 00:48:09,690 blocks, and then two bits that come out of here and select A, 796 00:48:09,690 --> 00:48:13,380 B, C, D within the block. 797 00:48:13,380 --> 00:48:15,330 There's two parts to the label. 798 00:48:15,330 --> 00:48:17,900 One of them determines A, B, C, D, the other one just 799 00:48:17,900 --> 00:48:20,880 determines some larger group. 800 00:48:20,880 --> 00:48:26,080 801 00:48:26,080 --> 00:48:29,910 These bits are called uncoded because there's no protection. 802 00:48:29,910 --> 00:48:37,370 If you sent point A over here and received point A over 803 00:48:37,370 --> 00:48:39,980 here, that would look like a perfectly 804 00:48:39,980 --> 00:48:42,250 legitimate code word. 805 00:48:42,250 --> 00:48:48,490 If we make an error of that far, which is d min squared 806 00:48:48,490 --> 00:48:50,740 equals 4, say. 807 00:48:50,740 --> 00:48:56,300 We make an error of size d min equal 2 all the way over here, 808 00:48:56,300 --> 00:49:00,230 then there's no further protection from this code 809 00:49:00,230 --> 00:49:02,670 because this code only determines the sequence of As, 810 00:49:02,670 --> 00:49:03,920 Bs, Cs, and Ds. 811 00:49:03,920 --> 00:49:09,720 812 00:49:09,720 --> 00:49:11,880 This is called a within-subset error. 813 00:49:11,880 --> 00:49:16,380 There's no protection on within subset errors. 814 00:49:16,380 --> 00:49:19,490 What the code does is it protects against smaller 815 00:49:19,490 --> 00:49:26,840 errors that are between subset errors like A to B, which has 816 00:49:26,840 --> 00:49:30,890 squared distance of 1 or A to D has a squared distance of 817 00:49:30,890 --> 00:49:32,380 two, and so forth. 818 00:49:32,380 --> 00:49:39,250 819 00:49:39,250 --> 00:49:40,640 Are you with me? 820 00:49:40,640 --> 00:49:41,920 Nobody's asking questions. 821 00:49:41,920 --> 00:49:43,170 Maybe I haven't permitted it. 822 00:49:43,170 --> 00:49:48,550 823 00:49:48,550 --> 00:49:53,140 Do you follow what the overall setup is? 824 00:49:53,140 --> 00:49:57,880 I've done everything now, except choose an exact 825 00:49:57,880 --> 00:49:58,790 constellation. 826 00:49:58,790 --> 00:50:03,500 For the exact constellation, I'll just choose one of the 827 00:50:03,500 --> 00:50:05,110 best QAM signal sets. 828 00:50:05,110 --> 00:50:08,590 If it's large enough, I'll shape it like a circle. 829 00:50:08,590 --> 00:50:13,860 Or I might even try to put Gaussian shaping on it by some 830 00:50:13,860 --> 00:50:15,900 completely extraneous thing that works 831 00:50:15,900 --> 00:50:17,175 only on these clumps. 832 00:50:17,175 --> 00:50:19,750 833 00:50:19,750 --> 00:50:24,450 So shaping takes place on the higher order bits. 834 00:50:24,450 --> 00:50:27,630 You can see that, given a large enough constellation 835 00:50:27,630 --> 00:50:31,340 just by choosing these clumps, I can make the constellation 836 00:50:31,340 --> 00:50:33,085 sort of have the shape of a circle. 837 00:50:33,085 --> 00:50:42,535 838 00:50:42,535 --> 00:50:45,950 The subsets of A, B, C, and D points have to all be the same 839 00:50:45,950 --> 00:50:48,460 size in order for this scheme to work. 840 00:50:48,460 --> 00:50:50,630 But I can do that within a sort of circular constellation 841 00:50:50,630 --> 00:50:53,250 if the constellation is large enough. 842 00:50:53,250 --> 00:50:58,650 Or I can put some Gaussian distribution on these clumps. 843 00:50:58,650 --> 00:51:00,340 So I do shaping down here. 844 00:51:00,340 --> 00:51:03,490 845 00:51:03,490 --> 00:51:05,140 Initially, of course, Ungerboeck 846 00:51:05,140 --> 00:51:06,190 didn't worry about shaping. 847 00:51:06,190 --> 00:51:10,940 But if I try to do shaping, it's down on this index, which 848 00:51:10,940 --> 00:51:14,440 is considered to be the higher order bits that determine the 849 00:51:14,440 --> 00:51:16,950 growth structure of the constellation. 850 00:51:16,950 --> 00:51:20,030 These are the lower order bits, these two bits, and they 851 00:51:20,030 --> 00:51:22,250 determine the fine structure which is 852 00:51:22,250 --> 00:51:23,680 determined by this code. 853 00:51:23,680 --> 00:51:28,580 So the last thing I have to select is the code, and it 854 00:51:28,580 --> 00:51:33,260 turns out that the same code we used in the example is a 855 00:51:33,260 --> 00:51:34,530 good code to use here. 856 00:51:34,530 --> 00:51:42,290 Suppose we use the four-state rate 1/2 example code that 857 00:51:42,290 --> 00:51:51,290 I've used before that is everybody's favorite example 858 00:51:51,290 --> 00:51:56,010 because it has such excellent distance properties. 859 00:51:56,010 --> 00:51:57,680 So it looks like this. 860 00:51:57,680 --> 00:52:00,290 861 00:52:00,290 --> 00:52:02,740 So that's my rate 1/2 encoder. 862 00:52:02,740 --> 00:52:06,090 863 00:52:06,090 --> 00:52:12,660 You remember as a binary code, it had minimum Hamming 864 00:52:12,660 --> 00:52:14,020 distance 5. 865 00:52:14,020 --> 00:52:17,800 And the only minimum distance code word 866 00:52:17,800 --> 00:52:21,430 was the impulse response. 867 00:52:21,430 --> 00:52:23,290 Let me write the impulse response as this 868 00:52:23,290 --> 00:52:24,540 way: 11, 01, 11. 869 00:52:24,540 --> 00:52:26,380 870 00:52:26,380 --> 00:52:30,200 This is what we get out at time 0, time 1, and time 2. 871 00:52:30,200 --> 00:52:38,510 872 00:52:38,510 --> 00:52:42,340 Let me assign the following labels to these subsets. 873 00:52:42,340 --> 00:52:46,370 We'll make that 00, this one 11, this one 01, 874 00:52:46,370 --> 00:52:47,620 and that one 10. 875 00:52:47,620 --> 00:52:49,640 876 00:52:49,640 --> 00:52:53,185 In other words, this is the complement of that. 877 00:52:53,185 --> 00:52:54,545 This is the complement of that. 878 00:52:54,545 --> 00:53:05,690 879 00:53:05,690 --> 00:53:10,680 What is the nearest neighbor point in Euclidian space for 880 00:53:10,680 --> 00:53:13,300 this sequence? 881 00:53:13,300 --> 00:53:16,080 If I complement the first two bits coming out, then I'm 882 00:53:16,080 --> 00:53:24,020 going to go from one of these subsets to another, but within 883 00:53:24,020 --> 00:53:27,590 one of these RZ-squared subsets, which has minimum 884 00:53:27,590 --> 00:53:30,650 squared distance 2. 885 00:53:30,650 --> 00:53:33,460 So let's remind ourselves that the minimum squared distance 886 00:53:33,460 --> 00:53:38,480 within A, B, C, D is 1, within A, D or B, C is 2, within 887 00:53:38,480 --> 00:53:42,470 2Z-squared is 4. 888 00:53:42,470 --> 00:53:43,920 So I'm claiming-- 889 00:53:43,920 --> 00:53:47,200 there's actually a problem on this on Problem Set 10 if you 890 00:53:47,200 --> 00:53:49,900 tried to do it-- 891 00:53:49,900 --> 00:54:00,780 that any error of this type, 11, is going to cause me a 892 00:54:00,780 --> 00:54:05,620 Euclidian error of minimum squared distance 2, at least. 893 00:54:05,620 --> 00:54:09,830 It can only cause me to go from A to D, which is always 894 00:54:09,830 --> 00:54:15,850 at least squared distance 2, or from B to C, or vice versa. 895 00:54:15,850 --> 00:54:20,720 So in terms of Euclidian distance, d min squared, I'm 896 00:54:20,720 --> 00:54:25,200 always going to get a squared distance of 2 at this point. 897 00:54:25,200 --> 00:54:28,200 And actually, any place you diverged in the trellis, 898 00:54:28,200 --> 00:54:29,810 because of the structure of the code, this 899 00:54:29,810 --> 00:54:32,210 is going to be true. 900 00:54:32,210 --> 00:54:37,800 I'm always going to get a squared distance of 2 when two 901 00:54:37,800 --> 00:54:42,110 trellis paths come together in the trellis. 902 00:54:42,110 --> 00:54:45,770 I always have a binary difference of 11, so by the 903 00:54:45,770 --> 00:54:48,140 same argument I'm always going to get a Euclidian squared 904 00:54:48,140 --> 00:54:52,250 distance of 2 when two trellis paths come together. 905 00:54:52,250 --> 00:54:55,070 And furthermore, I'm going to have at least one difference 906 00:54:55,070 --> 00:54:58,790 somewhere in between, which is going to, again, in terms of 907 00:54:58,790 --> 00:55:00,730 Euclidian distance, lead to a Euclidian 908 00:55:00,730 --> 00:55:05,250 distance of at least 1. 909 00:55:05,250 --> 00:55:12,080 So the conclusion is that between any two sequences of 910 00:55:12,080 --> 00:55:16,920 constellation points that are labeled by two distinct code 911 00:55:16,920 --> 00:55:21,720 words here, I'm going to have a cumulative Euclidian squared 912 00:55:21,720 --> 00:55:25,520 distance of at least 5, by the same argument as I had for the 913 00:55:25,520 --> 00:55:26,440 binary code. 914 00:55:26,440 --> 00:55:32,740 But now it turns out that I'm still in a regime where binary 915 00:55:32,740 --> 00:55:37,140 distance, Hamming distance translates directly to 916 00:55:37,140 --> 00:55:38,450 Euclidian distance. 917 00:55:38,450 --> 00:55:41,370 This is what you saw. 918 00:55:41,370 --> 00:55:44,760 Basically, what we're using here is this is Z-squared, you 919 00:55:44,760 --> 00:55:49,420 can think of as the image of the (2, 2) binary code. 920 00:55:49,420 --> 00:55:54,360 RZ-squared is the image of the (2, 1) binary code, and this 921 00:55:54,360 --> 00:55:58,330 2Z-squared is the image of the (2, 0) binary code. 922 00:55:58,330 --> 00:56:02,370 You get the same partition structure for these codes and 923 00:56:02,370 --> 00:56:04,390 their co-sets. 924 00:56:04,390 --> 00:56:07,830 This is the set of all four two-tuples. 925 00:56:07,830 --> 00:56:10,050 We divided it into two subsets, each of minimum 926 00:56:10,050 --> 00:56:13,530 distance 2 here, and here we divide it into four subsets, 927 00:56:13,530 --> 00:56:14,785 each of minimum distance infinity. 928 00:56:14,785 --> 00:56:17,330 929 00:56:17,330 --> 00:56:21,240 I'm not going to take the time to make this precise, but 930 00:56:21,240 --> 00:56:24,540 think of how that relation goes. 931 00:56:24,540 --> 00:56:28,200 So I've assured myself of a Euclidian squared distance at 932 00:56:28,200 --> 00:56:32,300 least 5 between signal point sequences that correspond to 933 00:56:32,300 --> 00:56:33,550 two different code words. 934 00:56:33,550 --> 00:56:35,900 935 00:56:35,900 --> 00:56:37,890 That's excellent. 936 00:56:37,890 --> 00:56:39,910 Is the minimum squared distance of the code then 937 00:56:39,910 --> 00:56:43,190 equal to 5, as it was in the binary case of 938 00:56:43,190 --> 00:56:44,400 this trellis code? 939 00:56:44,400 --> 00:56:46,200 No, it's not. 940 00:56:46,200 --> 00:56:49,910 And the problem is I could make this kind of error, which 941 00:56:49,910 --> 00:56:52,660 is completely invisible to the code. 942 00:56:52,660 --> 00:56:55,470 I can make a within subset error, and this only has 943 00:56:55,470 --> 00:56:59,220 minimum square distance of 4. 944 00:56:59,220 --> 00:57:04,500 So the conclusion of this analysis is that this is 945 00:57:04,500 --> 00:57:08,930 what's called a four-state two-dimensional trellis code. 946 00:57:08,930 --> 00:57:11,620 This four-state two-dimensional trellis code 947 00:57:11,620 --> 00:57:15,430 has a minimum squared distance of 4, and it has a number of 948 00:57:15,430 --> 00:57:18,430 nearest neighbors per two dimension of 4. 949 00:57:18,430 --> 00:57:21,600 That's the number of nearest neighbors within 2Z-squared, 950 00:57:21,600 --> 00:57:25,320 which is one of these subsets. 951 00:57:25,320 --> 00:57:30,580 So the conclusion is that already, this has a legitimate 952 00:57:30,580 --> 00:57:32,300 3 dB coding gain. 953 00:57:32,300 --> 00:57:37,020 Its coefficient is still just the QAM coefficient, and this 954 00:57:37,020 --> 00:57:42,170 very simple code has this performance curve moved over. 955 00:57:42,170 --> 00:57:46,490 956 00:57:46,490 --> 00:57:48,695 So it's 3 dB all the way up the line. 957 00:57:48,695 --> 00:57:52,440 958 00:57:52,440 --> 00:57:54,600 So that's pretty good. 959 00:57:54,600 --> 00:57:57,800 This is a trivial code that could be decoding-- 960 00:57:57,800 --> 00:58:00,120 by the way, it was, again, done by the Viterbi algorithm 961 00:58:00,120 --> 00:58:02,960 of a four-state trellis. 962 00:58:02,960 --> 00:58:09,380 You just take the sequences and it's exactly the same. 963 00:58:09,380 --> 00:58:14,960 You measure distance in terms of minimum squared distance. 964 00:58:14,960 --> 00:58:25,640 The only difference is when you decode, you first find 965 00:58:25,640 --> 00:58:27,520 what the closest point is within the 966 00:58:27,520 --> 00:58:30,500 A, B, C and D subsets. 967 00:58:30,500 --> 00:58:32,910 That is what you're going to take as your representative 968 00:58:32,910 --> 00:58:33,920 for that subset. 969 00:58:33,920 --> 00:58:38,250 So you first make basically an uncoded decision, which is the 970 00:58:38,250 --> 00:58:39,190 closest point in A? 971 00:58:39,190 --> 00:58:41,750 Which is the closest point in B, which is the closest point 972 00:58:41,750 --> 00:58:45,090 in C, which is the closest point in D? 973 00:58:45,090 --> 00:58:46,750 You're going to get a metric for each of those. 974 00:58:46,750 --> 00:58:49,470 How far is each of those from the receive point? 975 00:58:49,470 --> 00:58:52,810 So then in trellis decoding, what the trellis is going to 976 00:58:52,810 --> 00:58:55,880 look like is something like this. 977 00:58:55,880 --> 00:59:03,380 A, D, A, D, B, C, and so forth. 978 00:59:03,380 --> 00:59:09,490 979 00:59:09,490 --> 00:59:13,860 The trellis is going to look exactly the same, but here you 980 00:59:13,860 --> 00:59:18,840 get A, D, D, A, B, C, C, B. 981 00:59:18,840 --> 00:59:21,290 So what metric are we going to use for 982 00:59:21,290 --> 00:59:25,090 each of these branches? 983 00:59:25,090 --> 00:59:28,210 First, we find the closest point within each subset, and 984 00:59:28,210 --> 00:59:30,670 then we use the metric for that point. 985 00:59:30,670 --> 00:59:34,540 Clearly, if we're going to choose A for this time 986 00:59:34,540 --> 00:59:40,020 interval, then we should use the closest point in A as our 987 00:59:40,020 --> 00:59:41,980 receive decision. 988 00:59:41,980 --> 00:59:46,380 We can get that survivor without any memory whatsoever 989 00:59:46,380 --> 00:59:51,630 when we make that decision, and then we take the sequences 990 00:59:51,630 --> 00:59:55,180 of representatives and find the best of those 991 00:59:55,180 --> 00:59:57,570 representatives as our best trellis-coded sequence. 992 00:59:57,570 --> 01:00:00,880 993 01:00:00,880 --> 01:00:03,830 Any sequence of points that has labels that correspond to 994 01:00:03,830 --> 01:00:06,210 some path through this trellis is a valid 995 01:00:06,210 --> 01:00:07,560 point and vice versa. 996 01:00:07,560 --> 01:00:10,660 If and only if the sequence of labels is according to this 997 01:00:10,660 --> 01:00:15,920 trellis is it a legitimate trellis-coded point. 998 01:00:15,920 --> 01:00:17,170 So it's a nice amalgamation. 999 01:00:17,170 --> 01:00:22,640 1000 01:00:22,640 --> 01:00:23,220 Great. 1001 01:00:23,220 --> 01:00:27,580 With a simple four-state code, basically we've doubled the 1002 01:00:27,580 --> 01:00:28,920 size the constellation. 1003 01:00:28,920 --> 01:00:32,850 The constellation expansion is 2, the constellation expansion 1004 01:00:32,850 --> 01:00:36,230 factor with twice as large a constellation, we've been able 1005 01:00:36,230 --> 01:00:40,420 to achieve a coding gain of 3 dB. 1006 01:00:40,420 --> 01:00:43,110 Not bad. 1007 01:00:43,110 --> 01:00:46,730 So how do we extend this idea? 1008 01:00:46,730 --> 01:00:50,710 First, extension would be to-- 1009 01:00:50,710 --> 01:00:53,060 all right, let's go up to an 8 state, 16 1010 01:00:53,060 --> 01:00:54,340 state, whatever code. 1011 01:00:54,340 --> 01:00:56,960 But is that going to improve our minimum distance using 1012 01:00:56,960 --> 01:01:00,310 this block diagram? 1013 01:01:00,310 --> 01:01:02,710 It's not, because we're still stuck with this 1014 01:01:02,710 --> 01:01:03,950 within subset distance. 1015 01:01:03,950 --> 01:01:08,550 So we can never get past d min squared equals 4 with a 1016 01:01:08,550 --> 01:01:10,920 four-way partition. 1017 01:01:10,920 --> 01:01:13,490 What we have to do is make one more level of partition and we 1018 01:01:13,490 --> 01:01:16,830 need to make an eight way partition, at which point 1019 01:01:16,830 --> 01:01:19,280 we're going to get a within subset distance of 8. 1020 01:01:19,280 --> 01:01:29,960 1021 01:01:29,960 --> 01:01:31,810 I left out one step, I'm sorry. 1022 01:01:31,810 --> 01:01:33,060 I'll come back to it. 1023 01:01:33,060 --> 01:01:36,130 1024 01:01:36,130 --> 01:01:40,520 We can get a code minimum squared distance up to 8, if 1025 01:01:40,520 --> 01:01:43,260 we extend the minimum squared distance up to 8. 1026 01:01:43,260 --> 01:01:47,830 The thing I didn't use, I didn't tell you before, was in 1027 01:01:47,830 --> 01:01:51,570 computing the coding gain of this code-- 1028 01:01:51,570 --> 01:01:54,190 let's just call it c-- 1029 01:01:54,190 --> 01:01:55,100 what should it be? 1030 01:01:55,100 --> 01:01:57,950 It should be the minimum squared distance of the code 1031 01:01:57,950 --> 01:02:01,970 over the volume of the code per two dimensions. 1032 01:02:01,970 --> 01:02:04,990 In this case, n is 2 so I'm just going to do it over the 1033 01:02:04,990 --> 01:02:06,310 volume of the code. 1034 01:02:06,310 --> 01:02:10,420 Now what is the volume of a convolutional code? 1035 01:02:10,420 --> 01:02:17,030 This is actually an interesting problem, because 1036 01:02:17,030 --> 01:02:20,480 the Voronoi region of a trellis code is actually an 1037 01:02:20,480 --> 01:02:23,030 infinite dimensional object. 1038 01:02:23,030 --> 01:02:25,400 A trellis code is really an infinite dimensional lattice. 1039 01:02:25,400 --> 01:02:28,490 It's a lattice in infinite dimensional space. 1040 01:02:28,490 --> 01:02:33,040 And if you look at the Voronoi region, it extends out into 1041 01:02:33,040 --> 01:02:34,820 all these dimensions. 1042 01:02:34,820 --> 01:02:36,890 It might not for such a simple code, but in 1043 01:02:36,890 --> 01:02:39,930 principle it does. 1044 01:02:39,930 --> 01:02:42,590 However, you can find other fundamental regions. 1045 01:02:42,590 --> 01:02:47,040 The way to think about this is instead of 1046 01:02:47,040 --> 01:02:50,040 putting the volume here-- 1047 01:02:50,040 --> 01:02:52,840 well, what have we cost ourselves in volume? 1048 01:02:52,840 --> 01:02:55,650 We've doubled the size of the constellation. 1049 01:02:55,650 --> 01:02:57,580 And in two dimensions, that means 1050 01:02:57,580 --> 01:02:58,830 we've doubled the volume. 1051 01:02:58,830 --> 01:03:02,510 1052 01:03:02,510 --> 01:03:05,910 So we've quadrupled the minimum distance at the cost 1053 01:03:05,910 --> 01:03:10,230 of doubling the volume. 1054 01:03:10,230 --> 01:03:13,160 We've covered twice as much space now because we have 1055 01:03:13,160 --> 01:03:15,610 twice as many points. 1056 01:03:15,610 --> 01:03:18,050 And so, that's where we get the-- 1057 01:03:18,050 --> 01:03:21,710 this is equal to, for this code, that's 4. 1058 01:03:21,710 --> 01:03:25,750 We have a factor of 2 loss in volume, and so that's where we 1059 01:03:25,750 --> 01:03:29,795 get what I said was a coding gain of 2 or 3 dB. 1060 01:03:29,795 --> 01:03:34,270 1061 01:03:34,270 --> 01:03:37,280 Just to get you to the bottom line, we should replace the 1062 01:03:37,280 --> 01:03:40,230 volume by two times-- 1063 01:03:40,230 --> 01:03:44,720 I call it eta of the code-- where eta of the code is its 1064 01:03:44,720 --> 01:03:51,620 redundancy per two dimensions. 1065 01:03:51,620 --> 01:03:54,390 In this case, we introduce one redundant bit per two 1066 01:03:54,390 --> 01:03:57,400 dimensions, and that's why the constellation has to expand by 1067 01:03:57,400 --> 01:03:59,970 a factor of 2. 1068 01:03:59,970 --> 01:04:03,840 You see, we get the right answer. 1069 01:04:03,840 --> 01:04:08,050 The redundancy has increased by one bit, so this has to be 1070 01:04:08,050 --> 01:04:10,790 2 to the b plus 1, so the constellation has to be twice 1071 01:04:10,790 --> 01:04:14,220 as large, so the volume is twice as large. 1072 01:04:14,220 --> 01:04:17,360 I'll just hand-wave and tell you that's the factor you want 1073 01:04:17,360 --> 01:04:19,670 down here representing volume -- 1074 01:04:19,670 --> 01:04:21,680 2 to the redundancy. 1075 01:04:21,680 --> 01:04:27,992 And you can prove this by finding a region which you can 1076 01:04:27,992 --> 01:04:30,870 show is a fundamental region of the trellis code and has 1077 01:04:30,870 --> 01:04:32,030 this volume. 1078 01:04:32,030 --> 01:04:35,730 But I won't go into that. 1079 01:04:35,730 --> 01:04:39,000 OK, so that's the calculation which I should've mentioned 1080 01:04:39,000 --> 01:04:41,090 before, I skipped right over it. 1081 01:04:41,090 --> 01:04:42,220 Back to what I was saying. 1082 01:04:42,220 --> 01:04:46,450 To improve trellis codes, the first thing you can do is to, 1083 01:04:46,450 --> 01:04:49,760 say, go to an eight-way partition. 1084 01:04:49,760 --> 01:04:53,270 So now we're going to have eight subsets. 1085 01:04:53,270 --> 01:04:56,140 So we're going to need three bits here. 1086 01:04:56,140 --> 01:05:01,180 So let's use two bits here and use a rate 2/3 trellis code. 1087 01:05:01,180 --> 01:05:04,450 We're going to have three bits coming out here to select 1088 01:05:04,450 --> 01:05:08,610 subsets, and we're going to have b minus 2 bits down here 1089 01:05:08,610 --> 01:05:14,620 to select a point still a 2b plus 1 point QAM 1090 01:05:14,620 --> 01:05:16,060 constellation. 1091 01:05:16,060 --> 01:05:19,220 So our redundancy per two dimensions is still one bit 1092 01:05:19,220 --> 01:05:20,120 per two dimensions. 1093 01:05:20,120 --> 01:05:23,540 We're still going to lose a factor of 2, but now we can go 1094 01:05:23,540 --> 01:05:27,570 up to d min squared equals 8 and we can go up to a coding 1095 01:05:27,570 --> 01:05:29,690 gain of 6 dB. 1096 01:05:29,690 --> 01:05:33,910 So in his original paper, Ungerboeck did this. 1097 01:05:33,910 --> 01:05:39,860 He showed codes going up to 256 states in two dimensions 1098 01:05:39,860 --> 01:05:44,320 that gets you up to a nominal 6 dB coding gain. 1099 01:05:44,320 --> 01:05:48,390 And because they have low coefficients here, they get 1100 01:05:48,390 --> 01:05:51,350 very close to 6 dB of effective coding gain. 1101 01:05:51,350 --> 01:05:54,610 1102 01:05:54,610 --> 01:05:59,050 Already in Ungerboeck, we have codes-- 1103 01:05:59,050 --> 01:06:03,510 I mean, eventually you can get back to just the within-subset 1104 01:06:03,510 --> 01:06:07,930 coefficient again, which is always 4. 1105 01:06:07,930 --> 01:06:14,860 You can get up to, say, 6 dB with maybe 512 states of 1106 01:06:14,860 --> 01:06:21,160 effective coding gain, which is considerably better than 1107 01:06:21,160 --> 01:06:27,250 the densest lattice we would think of using, and also quite 1108 01:06:27,250 --> 01:06:28,220 reasonable to implement. 1109 01:06:28,220 --> 01:06:31,500 Now we're going to need a 256, 512-state 1110 01:06:31,500 --> 01:06:33,250 Viterbi algorithm decoder. 1111 01:06:33,250 --> 01:06:38,510 1112 01:06:38,510 --> 01:06:43,040 This was a stunning breakthrough. 1113 01:06:43,040 --> 01:06:48,360 Immediately in 1993, everybody started building turbo codes. 1114 01:06:48,360 --> 01:06:50,360 Back in 1982, everybody started 1115 01:06:50,360 --> 01:06:51,970 building trellis codes. 1116 01:06:51,970 --> 01:06:56,820 It happened to be the time of the V.32 modem, and everybody 1117 01:06:56,820 --> 01:07:00,680 said boy, this is just what we need to get an additional 3 or 1118 01:07:00,680 --> 01:07:04,115 4 dB coding gain in the V.32 modem. 1119 01:07:04,115 --> 01:07:07,680 What was actually done there is this was simply an 1120 01:07:07,680 --> 01:07:13,690 eight-state convolutional code, so it was rate 2/3. 1121 01:07:13,690 --> 01:07:15,230 And there was tweaking of this. 1122 01:07:15,230 --> 01:07:19,810 It was made rotationally invariant, made nonlinear. 1123 01:07:19,810 --> 01:07:23,840 And a lot of activity, which was very nice, stimulated by 1124 01:07:23,840 --> 01:07:25,130 the standards effort. 1125 01:07:25,130 --> 01:07:27,640 But that was basically the state of the art in the '80s. 1126 01:07:27,640 --> 01:07:30,270 1127 01:07:30,270 --> 01:07:36,070 The one other improvement that was made was 1128 01:07:36,070 --> 01:07:38,650 the following idea. 1129 01:07:38,650 --> 01:07:41,610 We really don't like doubling the size of the constellation, 1130 01:07:41,610 --> 01:07:45,060 particularly for a large one, mostly for 1131 01:07:45,060 --> 01:07:48,160 implementation reasons. 1132 01:07:48,160 --> 01:07:51,460 There were some feelings against nonlinearities a 1133 01:07:51,460 --> 01:07:53,920 larger constellation would cost you. 1134 01:07:53,920 --> 01:07:58,190 You wanted to minimize the constellation expansion ratio. 1135 01:07:58,190 --> 01:08:02,730 So how were we ever going to do that? 1136 01:08:02,730 --> 01:08:06,610 You can't do it this way in two dimensions. 1137 01:08:06,610 --> 01:08:09,255 The way to do that is to go up to four dimensions. 1138 01:08:09,255 --> 01:08:12,270 1139 01:08:12,270 --> 01:08:15,140 So let's do subset partitioning in four 1140 01:08:15,140 --> 01:08:16,390 dimensions. 1141 01:08:16,390 --> 01:08:18,270 1142 01:08:18,270 --> 01:08:20,760 So now think of four dimensional constellations. 1143 01:08:20,760 --> 01:08:24,270 In practice, these are just built from the Cartesian 1144 01:08:24,270 --> 01:08:27,790 product of two two-dimensional constellations. 1145 01:08:27,790 --> 01:08:29,830 We start with Z4. 1146 01:08:29,830 --> 01:08:32,939 The next one down is D4, which has a minimum 1147 01:08:32,939 --> 01:08:34,079 square distance of 2. 1148 01:08:34,079 --> 01:08:37,390 It's sometimes called a checkerboard constellation in 1149 01:08:37,390 --> 01:08:38,180 four dimensions. 1150 01:08:38,180 --> 01:08:41,729 It's just the red-black idea again. 1151 01:08:41,729 --> 01:08:46,010 Then below that, we have a four-way partition into RZ4, 1152 01:08:46,010 --> 01:08:51,300 which still has minimum distance 2. 1153 01:08:51,300 --> 01:08:56,279 And one more level of partitioning here into 1154 01:08:56,279 --> 01:09:02,559 something into RD4, which has minimum squared distance of 4. 1155 01:09:02,559 --> 01:09:06,950 1156 01:09:06,950 --> 01:09:10,160 So this is an eight-way partition of a 1157 01:09:10,160 --> 01:09:11,930 four-dimensional constellation. 1158 01:09:11,930 --> 01:09:14,189 This idea was introduced by Lee-Fang Wei. 1159 01:09:14,189 --> 01:09:17,290 1160 01:09:17,290 --> 01:09:22,140 Again, this is an interesting column over here. 1161 01:09:22,140 --> 01:09:25,200 You can think of this as being the (4, 4, 1) code. 1162 01:09:25,200 --> 01:09:30,376 This is the Euclidian image of the (4, 3, 2) code. 1163 01:09:30,376 --> 01:09:32,930 It kind of expanded in the lattice. 1164 01:09:32,930 --> 01:09:35,870 We know we can't do any better than (4, 2, 2). 1165 01:09:35,870 --> 01:09:39,120 Down here, this is the (4, 1, 4) code. 1166 01:09:39,120 --> 01:09:42,870 So again, this is the same partition as we get for binary 1167 01:09:42,870 --> 01:09:44,993 codes with the distances-- 1168 01:09:44,993 --> 01:09:47,810 1169 01:09:47,810 --> 01:09:52,609 again, for binary codes and this level of partitioning, 1170 01:09:52,609 --> 01:09:56,440 Hamming distance translates to Euclidian distance. 1171 01:09:56,440 --> 01:10:01,480 It's really just the image of these codes as you go up to 1172 01:10:01,480 --> 01:10:02,730 the lattices. 1173 01:10:02,730 --> 01:10:05,600 1174 01:10:05,600 --> 01:10:10,220 Now in this case, what's the best we can ever do? 1175 01:10:10,220 --> 01:10:10,910 Coding gain. 1176 01:10:10,910 --> 01:10:16,800 We still can't go up to a squared distance of greater 1177 01:10:16,800 --> 01:10:22,830 than 4 because our within-subset distance is 1178 01:10:22,830 --> 01:10:25,410 going to be within RD4. 1179 01:10:25,410 --> 01:10:28,240 So this is still limited to 4. 1180 01:10:28,240 --> 01:10:31,850 But now, what's our redundancy per two dimensions? 1181 01:10:31,850 --> 01:10:37,210 Here, say, we're going to use still a rate 2/3 1182 01:10:37,210 --> 01:10:38,490 convolutional code. 1183 01:10:38,490 --> 01:10:42,570 We'll now have an eight-subset selector in 4D, so everything 1184 01:10:42,570 --> 01:10:45,800 is per 4D here. 1185 01:10:45,800 --> 01:10:55,380 So this is going to be 2b minus two bits and this is 1186 01:10:55,380 --> 01:11:00,450 going to be, it turns out, a constellation that is twice as 1187 01:11:00,450 --> 01:11:02,010 large in four dimensions. 1188 01:11:02,010 --> 01:11:05,260 We still have one redundant bit per four dimensions, so we 1189 01:11:05,260 --> 01:11:08,050 need twice the size of the constellation in four 1190 01:11:08,050 --> 01:11:09,660 dimensions. 1191 01:11:09,660 --> 01:11:14,670 But that's only 1/2 a bit of redundancy per two dimensions. 1192 01:11:14,670 --> 01:11:18,620 So this denominator becomes 2 to the 1/2. 1193 01:11:18,620 --> 01:11:21,940 Waving hands furiously here. 1194 01:11:21,940 --> 01:11:26,990 And so this could go up to 2 to the 3/2, which is 4.5 dB. 1195 01:11:26,990 --> 01:11:31,360 1196 01:11:31,360 --> 01:11:35,800 So there's actually a particularly nice eight-state 1197 01:11:35,800 --> 01:11:41,620 code here that Wei came up with which, really, in terms 1198 01:11:41,620 --> 01:11:45,530 of performance versus complexity is the only code 1199 01:11:45,530 --> 01:11:48,510 that anyone has ever come up with that is distinctly better 1200 01:11:48,510 --> 01:11:50,855 than any of Ungerboeck's original codes. 1201 01:11:50,855 --> 01:11:54,040 All of Ungerboeck's original codes were in one dimension, 1202 01:11:54,040 --> 01:11:56,280 two dimensions, or PSK codes. 1203 01:11:56,280 --> 01:11:58,870 You could also do this on phase shift key 1204 01:11:58,870 --> 01:12:00,120 constellations. 1205 01:12:00,120 --> 01:12:02,140 1206 01:12:02,140 --> 01:12:09,260 So with the Wei code, it gives you a very simple way 1207 01:12:09,260 --> 01:12:10,840 to get 4 1/2 dB. 1208 01:12:10,840 --> 01:12:13,750 1209 01:12:13,750 --> 01:12:18,770 Actually, you have to go up to 16 states to get 4 1/2 dB. 1210 01:12:18,770 --> 01:12:21,290 The Wei code is only 4.2 dB. 1211 01:12:21,290 --> 01:12:24,900 And this is basically what was adopted for standards in the 1212 01:12:24,900 --> 01:12:25,810 early '90s. 1213 01:12:25,810 --> 01:12:33,470 The V.34 modem standard, also the ADSL standard has the same 1214 01:12:33,470 --> 01:12:34,020 code in it. 1215 01:12:34,020 --> 01:12:38,230 If you have DSL at home, that's what it's using in it. 1216 01:12:38,230 --> 01:12:43,460 Again, with a very simple code, the eight-state Viterbi 1217 01:12:43,460 --> 01:12:47,680 algorithm, you can get 4.2 dB of coding gain. 1218 01:12:47,680 --> 01:12:53,530 The error coefficient in this case, this has 24 nearest 1219 01:12:53,530 --> 01:12:57,110 neighbors in D4, or 12 per two dimensions. 1220 01:12:57,110 --> 01:13:05,460 So you lose 0.15 dB or something. 1221 01:13:05,460 --> 01:13:06,735 I'm sorry, 0.3 dB. 1222 01:13:06,735 --> 01:13:11,800 1223 01:13:11,800 --> 01:13:14,860 Anyway, this is a very nice code. 1224 01:13:14,860 --> 01:13:21,460 1225 01:13:21,460 --> 01:13:24,640 There are 32 and 64-state codes in V.34. 1226 01:13:24,640 --> 01:13:26,610 They don't gain you very much. 1227 01:13:26,610 --> 01:13:29,820 They each double the complexity and only gain you 1228 01:13:29,820 --> 01:13:33,710 about 0.2 dB for each one. 1229 01:13:33,710 --> 01:13:35,430 All these things tend to saturate. 1230 01:13:35,430 --> 01:13:39,760 You can't get more than about 5 to 6 dB of coding gain with 1231 01:13:39,760 --> 01:13:41,700 a reasonable size trellis code. 1232 01:13:41,700 --> 01:13:45,790 1233 01:13:45,790 --> 01:13:48,500 So where are we now? 1234 01:13:48,500 --> 01:13:55,610 We can get 5 or 6 dB of coding gain with, say, a 256-state 1235 01:13:55,610 --> 01:13:57,420 trellis code. 1236 01:13:57,420 --> 01:14:03,360 We can get another 1 to 1 and a 1/2 dB of shaping gain. 1237 01:14:03,360 --> 01:14:09,590 So all together, we're up to 6 to 7.5 dB. 1238 01:14:09,590 --> 01:14:15,580 From here, we're up somewhere into the 2 to 3 dB range. 1239 01:14:15,580 --> 01:14:23,980 In other words, combining trellis code with, say, 256 1240 01:14:23,980 --> 01:14:33,300 states with some shaping scheme with maybe 1 dB of 1241 01:14:33,300 --> 01:14:41,520 shaping gain, this gets you maybe 5 dB or 5.5 dB. 1242 01:14:41,520 --> 01:14:51,870 We get 6 dB total effective gain, and we're still 3 dB or 1243 01:14:51,870 --> 01:14:55,140 maybe 2 or 3 dB from Shannon limit. 1244 01:14:55,140 --> 01:15:05,440 1245 01:15:05,440 --> 01:15:09,840 So, close but not quite there yet. 1246 01:15:09,840 --> 01:15:13,250 Five minutes to go. 1247 01:15:13,250 --> 01:15:16,210 So in the notes, there's one page on 1248 01:15:16,210 --> 01:15:17,590 higher performance schemes. 1249 01:15:17,590 --> 01:15:20,340 There are higher performance schemes. 1250 01:15:20,340 --> 01:15:23,680 There are turbo codes for the bandwidth-limited regime that 1251 01:15:23,680 --> 01:15:27,130 get you to within 1 dB of the Shannon limit. 1252 01:15:27,130 --> 01:15:30,700 Sequential decoding gets you to within about 1 and a 1/2 dB 1253 01:15:30,700 --> 01:15:33,260 of the Shannon limit. 1254 01:15:33,260 --> 01:15:34,510 The idea of multi-level codes -- 1255 01:15:34,510 --> 01:15:37,450 1256 01:15:37,450 --> 01:15:42,260 you can regard each of these two-way partitions as being 1257 01:15:42,260 --> 01:15:45,340 specified by one bit. 1258 01:15:45,340 --> 01:15:48,570 So with three bits of labels, you can specify 1259 01:15:48,570 --> 01:15:51,150 an eight-way partition. 1260 01:15:51,150 --> 01:15:54,100 Another idea is to code on each of these levels 1261 01:15:54,100 --> 01:15:55,500 separately. 1262 01:15:55,500 --> 01:15:58,300 Use a binary code on each of these levels separately. 1263 01:15:58,300 --> 01:16:04,080 Each of these corresponds to an effective channel that has 1264 01:16:04,080 --> 01:16:05,410 different characteristics. 1265 01:16:05,410 --> 01:16:09,350 You've basically got to take the Gaussian distribution and 1266 01:16:09,350 --> 01:16:13,450 alias it around in accord with whatever this partition 1267 01:16:13,450 --> 01:16:14,300 actually is. 1268 01:16:14,300 --> 01:16:19,030 But you can come up with an effective binary channel at 1269 01:16:19,030 --> 01:16:20,090 each of these levels. 1270 01:16:20,090 --> 01:16:24,240 It turns out to be a binary symmetric input channel, 1271 01:16:24,240 --> 01:16:27,490 always in these cases. 1272 01:16:27,490 --> 01:16:30,960 So you could think of taking a binary-- 1273 01:16:30,960 --> 01:16:33,690 now, each one of these channels is going to have its 1274 01:16:33,690 --> 01:16:36,130 own capacity. 1275 01:16:36,130 --> 01:16:41,660 It turns out that information theoretically, the capacity of 1276 01:16:41,660 --> 01:16:46,600 multi-level coding on each of these levels independently is 1277 01:16:46,600 --> 01:16:49,460 the same as the aggregate capacity of coding it on the 1278 01:16:49,460 --> 01:16:50,645 whole channel. 1279 01:16:50,645 --> 01:16:55,450 It's a lovely separability result. 1280 01:16:55,450 --> 01:17:00,220 So in principle, if you could code at capacity on each of 1281 01:17:00,220 --> 01:17:04,150 these binary channels, then you could get to the capacity 1282 01:17:04,150 --> 01:17:08,330 of the aggregate channel, with a large enough constellation. 1283 01:17:08,330 --> 01:17:09,400 So that's a good idea. 1284 01:17:09,400 --> 01:17:14,470 We now know a lot of binary capacity-approaching code, so 1285 01:17:14,470 --> 01:17:17,860 let's use a turbo code or a low-density parity-check code 1286 01:17:17,860 --> 01:17:22,330 at each level, an appropriate code. 1287 01:17:22,330 --> 01:17:24,950 It turns out, as you might expect, that the first level 1288 01:17:24,950 --> 01:17:26,910 is the really hard level. 1289 01:17:26,910 --> 01:17:31,470 In this case, you might have a rate 1/3 or 1/2 code and 1290 01:17:31,470 --> 01:17:33,750 really work hard with your code. 1291 01:17:33,750 --> 01:17:38,030 At the next level, the effective error probability is 1292 01:17:38,030 --> 01:17:40,680 much better. 1293 01:17:40,680 --> 01:17:43,530 Making hard decisions, you might have a probability of 1294 01:17:43,530 --> 01:17:47,480 1/10 or lower of making an error. 1295 01:17:47,480 --> 01:17:49,265 So these are really much easier problems. 1296 01:17:49,265 --> 01:17:52,230 It might be a better idea at these levels just to use 1297 01:17:52,230 --> 01:17:55,940 algebraic coding or something that works very well. 1298 01:17:55,940 --> 01:17:59,450 The capacity is nearly one per bit at each level, so you want 1299 01:17:59,450 --> 01:18:02,780 to code with very little redundancy at these next 1300 01:18:02,780 --> 01:18:06,410 levels, but it's still capable of approaching capacity. 1301 01:18:06,410 --> 01:18:09,690 Well, it turns out this is a good scenario for Reed-Solomon 1302 01:18:09,690 --> 01:18:12,980 codes or some kind of algebraic code. 1303 01:18:12,980 --> 01:18:16,880 So the moral is you only really need your 1304 01:18:16,880 --> 01:18:19,390 capacity-approaching code at maybe the first or first and 1305 01:18:19,390 --> 01:18:20,930 second levels. 1306 01:18:20,930 --> 01:18:24,820 Down here, just use a very high rate-- 1307 01:18:24,820 --> 01:18:34,170 1,023, 1,003 Reed-Solomon code over gf of 2 to the 10th-- 1308 01:18:34,170 --> 01:18:36,836 very little redundancy, and drive the error rate down as 1309 01:18:36,836 --> 01:18:40,840 low as you like at each of these levels. 1310 01:18:40,840 --> 01:18:44,380 So multi-level coding is a good way in principle. 1311 01:18:44,380 --> 01:18:46,830 I'm not sure if it's been done in practice. 1312 01:18:46,830 --> 01:18:50,940 In fact, I don't know of any capacity-approaching code that 1313 01:18:50,940 --> 01:18:54,380 has been done in practice, except there's a very crude 1314 01:18:54,380 --> 01:19:02,450 technique, I would say, called Bit-Interleaved Coded 1315 01:19:02,450 --> 01:19:08,070 Modulation, BICM, which is the following simple idea. 1316 01:19:08,070 --> 01:19:12,910 1317 01:19:12,910 --> 01:19:16,470 Let's just take a single low-density parity-check code 1318 01:19:16,470 --> 01:19:20,290 or some capacity-approaching code. 1319 01:19:20,290 --> 01:19:23,620 It's going to have to be designed for a BICM channel. 1320 01:19:23,620 --> 01:19:26,650 Let's totally interleave the bits and then let's use them 1321 01:19:26,650 --> 01:19:29,640 as the bits that control each of these levels here. 1322 01:19:29,640 --> 01:19:32,070 At the output of the channel, we know which level the bits 1323 01:19:32,070 --> 01:19:33,410 came out of. 1324 01:19:33,410 --> 01:19:36,120 So at the output of the channel, we know what the 1325 01:19:36,120 --> 01:19:38,820 appropriate a posteriori probabilities 1326 01:19:38,820 --> 01:19:40,500 are for each bit. 1327 01:19:40,500 --> 01:19:41,850 They're going to be wildly different. 1328 01:19:41,850 --> 01:19:43,690 A bit sent through here is going to be sent through a 1329 01:19:43,690 --> 01:19:46,130 very highly reliable channel, a bit sent through here is 1330 01:19:46,130 --> 01:19:48,780 going to be sent through a very low reliability channel. 1331 01:19:48,780 --> 01:19:53,500 But with all this interleaving and the independence 1332 01:19:53,500 --> 01:19:56,380 approximation in the analysis, we're going to be able to 1333 01:19:56,380 --> 01:20:00,380 design a code for this mixture channel, a mixture of high 1334 01:20:00,380 --> 01:20:03,560 reliability and low reliability binary channels, 1335 01:20:03,560 --> 01:20:06,290 that's going to get to the capacity of this mixture 1336 01:20:06,290 --> 01:20:10,590 channel, which as I've already told you is equal to the 1337 01:20:10,590 --> 01:20:12,440 capacity of the aggregate channel. 1338 01:20:12,440 --> 01:20:16,260 1339 01:20:16,260 --> 01:20:19,480 I guess there's some elegant features of it. 1340 01:20:19,480 --> 01:20:21,740 But that's, in practice, what people use. 1341 01:20:21,740 --> 01:20:23,790 They use it more because they've already developed a 1342 01:20:23,790 --> 01:20:28,220 chip for binary channels, and they want to reuse that chip 1343 01:20:28,220 --> 01:20:32,310 for some large constellation channel, some 1344 01:20:32,310 --> 01:20:34,520 bandwidth-limited channel. 1345 01:20:34,520 --> 01:20:38,120 So this was originally advocated by Qualcomm as a, 1346 01:20:38,120 --> 01:20:40,740 quote, pragmatic approach. 1347 01:20:40,740 --> 01:20:46,030 OK, we've got a chip that works for binary channels, so 1348 01:20:46,030 --> 01:20:51,640 let's just interleave outputs and use it over this 1349 01:20:51,640 --> 01:20:54,750 multi-level channel and it'll probably work well enough. 1350 01:20:54,750 --> 01:20:56,930 And, in fact, that's true. 1351 01:20:56,930 --> 01:20:59,390 And the information support for it, again, is the fact 1352 01:20:59,390 --> 01:21:06,180 that you don't lose anything by coding bit by bit from a 1353 01:21:06,180 --> 01:21:07,636 capacity point of view. 1354 01:21:07,636 --> 01:21:12,820 1355 01:21:12,820 --> 01:21:17,030 I think that's the only one that's been used in practice. 1356 01:21:17,030 --> 01:21:22,800 And on wireless cellular channels for instance, that 1357 01:21:22,800 --> 01:21:24,300 tends to be what's used. 1358 01:21:24,300 --> 01:21:27,340 1359 01:21:27,340 --> 01:21:32,770 And of course, I know that perhaps a couple of you have 1360 01:21:32,770 --> 01:21:35,550 an exam at 11:00, so I'll make a point of 1361 01:21:35,550 --> 01:21:37,790 letting you out of here. 1362 01:21:37,790 --> 01:21:40,150 I've really enjoyed teaching the course this term. 1363 01:21:40,150 --> 01:21:43,110 It was the first time I was able to get to the analysis of 1364 01:21:43,110 --> 01:21:48,240 capacity-approaching codes, so I enjoyed doing that. 1365 01:21:48,240 --> 01:21:55,000 At this point, I think the subject of coding for the 1366 01:21:55,000 --> 01:21:58,080 additive white Gaussian noise channel, the traditional 1367 01:21:58,080 --> 01:21:59,780 channel, is pretty well wrapped up. 1368 01:21:59,780 --> 01:22:02,360 I don't think we're going to see any great improvements. 1369 01:22:02,360 --> 01:22:05,340 There's still some very interesting theoretical 1370 01:22:05,340 --> 01:22:08,160 questions about the convergence of these iterative 1371 01:22:08,160 --> 01:22:09,280 decoding algorithms. 1372 01:22:09,280 --> 01:22:10,980 What do they converge to? 1373 01:22:10,980 --> 01:22:12,650 How fast do they converge? 1374 01:22:12,650 --> 01:22:15,510 There are interesting connections to statistical 1375 01:22:15,510 --> 01:22:17,960 physics and inference and so forth that 1376 01:22:17,960 --> 01:22:19,365 people are still exploring. 1377 01:22:19,365 --> 01:22:22,190 They're interested in graph theoretical properties. 1378 01:22:22,190 --> 01:22:25,220 There's attempts to algebraically construct these 1379 01:22:25,220 --> 01:22:28,120 capacity-approaching codes, so we can say a lot more about 1380 01:22:28,120 --> 01:22:31,460 their parameters and their performance, particularly for 1381 01:22:31,460 --> 01:22:34,360 lower probabilities like 10 to the minus 15. 1382 01:22:34,360 --> 01:22:37,360 So you go to the information theory symposium, you'll still 1383 01:22:37,360 --> 01:22:40,750 hear a lot of papers about coding effectively for 1384 01:22:40,750 --> 01:22:44,830 additive white Gaussian noise or memoryless binary symmetric 1385 01:22:44,830 --> 01:22:47,110 input channels. 1386 01:22:47,110 --> 01:22:53,800 But people ask me, is coding dead now? 1387 01:22:53,800 --> 01:22:56,020 Are Fourier transforms dead? 1388 01:22:56,020 --> 01:22:57,150 No, they're not dead. 1389 01:22:57,150 --> 01:23:01,220 But they've become sort of part of the standard core of 1390 01:23:01,220 --> 01:23:03,570 what you should know. 1391 01:23:03,570 --> 01:23:07,240 I think this is a subject that anyone in communication should 1392 01:23:07,240 --> 01:23:10,130 certainly learn, but is it an area where people are going to 1393 01:23:10,130 --> 01:23:14,210 make further advances that are important from a practical 1394 01:23:14,210 --> 01:23:14,750 point of view? 1395 01:23:14,750 --> 01:23:17,990 Obviously not very much, in view of the Shannon limit. 1396 01:23:17,990 --> 01:23:21,030 We are very close to the Shannon limit for these 1397 01:23:21,030 --> 01:23:24,290 channels, and have been now for a few years. 1398 01:23:24,290 --> 01:23:27,350 So it's important to know about these things. 1399 01:23:27,350 --> 01:23:29,850 It's important to know when you're in the wireless course, 1400 01:23:29,850 --> 01:23:31,150 for instance. 1401 01:23:31,150 --> 01:23:33,980 You basically calculate mutual information and assume that 1402 01:23:33,980 --> 01:23:36,810 you can go at the mutual information. 1403 01:23:36,810 --> 01:23:38,690 This is how you do it. 1404 01:23:38,690 --> 01:23:43,770 So you should know how it's done, and that's why I think 1405 01:23:43,770 --> 01:23:46,820 this course continues to be worth teaching. 1406 01:23:46,820 --> 01:23:50,740 But from a point of view of research, it's become a rather 1407 01:23:50,740 --> 01:23:53,790 mature area, and the action has gone off to 1408 01:23:53,790 --> 01:23:55,290 other kinds of channels. 1409 01:23:55,290 --> 01:23:57,120 Multi this, multi that, so forth. 1410 01:23:57,120 --> 01:24:00,830 Anything to do with networks or multi-user is where the 1411 01:24:00,830 --> 01:24:03,410 action in coding is. 1412 01:24:03,410 --> 01:24:05,740 Data compression, of course, is a subject that we haven't 1413 01:24:05,740 --> 01:24:09,180 talked about at all, which is also coding. 1414 01:24:09,180 --> 01:24:12,630 So anyway, I think it's good for you to have all this under 1415 01:24:12,630 --> 01:24:14,460 your belts. 1416 01:24:14,460 --> 01:24:18,570 I hope that you find it useful in your future lives, and I 1417 01:24:18,570 --> 01:24:19,970 wish you all well on the final exam. 1418 01:24:19,970 --> 01:24:21,220 Thank you. 1419 01:24:21,220 --> 01:24:35,626