1 00:00:00,000 --> 00:00:01,120 2 00:00:01,120 --> 00:00:02,900 PROFESSOR: --we'll start off with a little review, so you 3 00:00:02,900 --> 00:00:06,090 might chance it. 4 00:00:06,090 --> 00:00:08,170 We're in the middle of the chapter nine on 5 00:00:08,170 --> 00:00:09,750 convolutional codes. 6 00:00:09,750 --> 00:00:12,840 Today, I intend to hand out problem set six. 7 00:00:12,840 --> 00:00:15,750 I believe Ashish will have it when he gets here. 8 00:00:15,750 --> 00:00:19,430 And we'll hand it out at the end. 9 00:00:19,430 --> 00:00:25,010 Last time, I introduced you to a lot of things about 10 00:00:25,010 --> 00:00:28,770 convolutional codes and their encoders. 11 00:00:28,770 --> 00:00:32,560 I stressed that a convolutional encoder had two 12 00:00:32,560 --> 00:00:33,910 distinct characters. 13 00:00:33,910 --> 00:00:37,140 One is it's a linear time-invariant system. 14 00:00:37,140 --> 00:00:41,170 So we can use the linearity and time-invariance and 15 00:00:41,170 --> 00:00:45,500 algebraic analysis of convolutional codes. 16 00:00:45,500 --> 00:00:49,270 Secondly, I stressed that's it's a finite state system, 17 00:00:49,270 --> 00:00:51,800 because it's a finite memory system where each memory 18 00:00:51,800 --> 00:00:55,630 element has a finite number of possible values, over F2 or 19 00:00:55,630 --> 00:00:57,800 indeed over any finite field. 20 00:00:57,800 --> 00:01:00,210 And therefore, we can use that for 21 00:01:00,210 --> 00:01:01,920 different kinds of analysis. 22 00:01:01,920 --> 00:01:05,200 We use that, for instance, in conjunction with linear 23 00:01:05,200 --> 00:01:08,990 property to find the minimum distance to a particular code. 24 00:01:08,990 --> 00:01:12,580 And we'll see that that's the key to getting an efficient 25 00:01:12,580 --> 00:01:16,300 optimal maximum likelihood decoder -- 26 00:01:16,300 --> 00:01:18,820 is the fact that we only have a finite number of states in 27 00:01:18,820 --> 00:01:20,400 this system. 28 00:01:20,400 --> 00:01:27,970 All right, so along the way I kind of went all over the map, 29 00:01:27,970 --> 00:01:33,050 as far as the introducing various algebraic quantities. 30 00:01:33,050 --> 00:01:36,970 I focused particularly on formal Laurent series. 31 00:01:36,970 --> 00:01:40,940 And I want to just give you a little table to make sure you 32 00:01:40,940 --> 00:01:43,820 have fixed in your mind what all these different kinds of 33 00:01:43,820 --> 00:01:46,380 sequences we're talking about are. 34 00:01:46,380 --> 00:01:49,870 On the left side, I have Laurent sequences. 35 00:01:49,870 --> 00:01:51,930 These are semi-infinite sequences that must 36 00:01:51,930 --> 00:01:53,140 start at some time. 37 00:01:53,140 --> 00:01:57,410 Their delay is not equal to minus infinity, which would be 38 00:01:57,410 --> 00:01:59,830 if it were all 1's forever. 39 00:01:59,830 --> 00:02:01,740 But their delay is some finite time. 40 00:02:01,740 --> 00:02:04,020 It could be negative, could be positive. 41 00:02:04,020 --> 00:02:05,750 That's their starting time. 42 00:02:05,750 --> 00:02:07,930 And then they could go on, possibly, 43 00:02:07,930 --> 00:02:09,299 infinitely into the future. 44 00:02:09,299 --> 00:02:12,160 45 00:02:12,160 --> 00:02:18,500 And then, among those, we can look particularly at the ones 46 00:02:18,500 --> 00:02:22,660 that start at time 0 or later, whose delay is 0, or whose 47 00:02:22,660 --> 00:02:24,720 delay is non-negative. 48 00:02:24,720 --> 00:02:26,980 These are called the formal power series, and you've 49 00:02:26,980 --> 00:02:29,250 probably encountered them earlier. 50 00:02:29,250 --> 00:02:31,550 They're a lot more frequently encountered 51 00:02:31,550 --> 00:02:36,170 in mathematics algebra. 52 00:02:36,170 --> 00:02:39,270 The rational sequences are simply those that can be 53 00:02:39,270 --> 00:02:43,140 written in a very finite way as a numerator polynomial over 54 00:02:43,140 --> 00:02:44,650 a denominator polynomial. 55 00:02:44,650 --> 00:02:50,240 Because the formal Laurent series form a field, every 56 00:02:50,240 --> 00:02:54,390 element is invertible, and, in particular, every polynomial 57 00:02:54,390 --> 00:02:59,520 has an inverse, which, unless the polynomial is a monomial, 58 00:02:59,520 --> 00:03:02,480 is going to run on for an infinite length of time. 59 00:03:02,480 --> 00:03:05,680 But nonetheless, there is a subset, a countable subset of 60 00:03:05,680 --> 00:03:08,650 these sequences that we can write in this way. 61 00:03:08,650 --> 00:03:11,800 And we call these the rational sequences, and they're 62 00:03:11,800 --> 00:03:16,580 analogous to the rational numbers in the real field. 63 00:03:16,580 --> 00:03:19,780 And their particular characteristic, as we showed, 64 00:03:19,780 --> 00:03:21,940 is that they're eventually periodic. 65 00:03:21,940 --> 00:03:26,460 And it's easy to see that these, too, form a field. 66 00:03:26,460 --> 00:03:29,375 Obviously, the inverse of N of d over D of d is D 67 00:03:29,375 --> 00:03:30,560 of d over N of d. 68 00:03:30,560 --> 00:03:35,220 Provided that n of d is not equal to 0, the denominator is 69 00:03:35,220 --> 00:03:40,580 always required to be non-zero for a rational sequence. 70 00:03:40,580 --> 00:03:44,450 So that's a very nice subset. 71 00:03:44,450 --> 00:03:49,220 It may or may not have operational meaning. 72 00:03:49,220 --> 00:03:51,090 Certainly, when we're talking about 73 00:03:51,090 --> 00:03:52,650 realizations, it has meaning. 74 00:03:52,650 --> 00:03:57,950 And then the finite sequences, by eventually periodic, I will 75 00:03:57,950 --> 00:04:00,350 from now on include the finite case. 76 00:04:00,350 --> 00:04:05,590 If we have a finite sequence, then its end is all 0's, and 77 00:04:05,590 --> 00:04:08,090 that's certainly a periodic sequence. 78 00:04:08,090 --> 00:04:09,830 So I would say a finite sequence is 79 00:04:09,830 --> 00:04:12,420 also eventually periodic. 80 00:04:12,420 --> 00:04:15,100 But among the rational sequences we have, 81 00:04:15,100 --> 00:04:18,540 particularly the finite sequence, these do not form a 82 00:04:18,540 --> 00:04:22,520 field, because the non-monomial polynomials 83 00:04:22,520 --> 00:04:23,570 cannot be inverted. 84 00:04:23,570 --> 00:04:26,420 So these are merely a ring. 85 00:04:26,420 --> 00:04:28,520 However, D has an inverse. 86 00:04:28,520 --> 00:04:32,280 Over here on this side, D minus 1 has an element of all 87 00:04:32,280 --> 00:04:33,090 these things. 88 00:04:33,090 --> 00:04:35,880 D has an inverse. 89 00:04:35,880 --> 00:04:39,820 Over here, on the causal side, these are the causal analogs 90 00:04:39,820 --> 00:04:42,540 to all of these. 91 00:04:42,540 --> 00:04:46,220 In the case of causal rational, we don't have 92 00:04:46,220 --> 00:04:47,940 particularly good notation. 93 00:04:47,940 --> 00:04:51,220 We just say these are the ones that are both causal, formal 94 00:04:51,220 --> 00:04:54,060 power series and rational. 95 00:04:54,060 --> 00:04:57,600 But they are important, because we've seen that it's 96 00:04:57,600 --> 00:05:01,700 this kind of sequence that you can get as the impulse 97 00:05:01,700 --> 00:05:08,620 response of a time-invariant linear system that is 98 00:05:08,620 --> 00:05:09,740 realizable. 99 00:05:09,740 --> 00:05:11,020 Realizable has two parts. 100 00:05:11,020 --> 00:05:15,070 One is the impulse response must start at time 0 or later, 101 00:05:15,070 --> 00:05:17,520 by physical causality. 102 00:05:17,520 --> 00:05:22,740 Two, the impulse response must be eventually periodic, 103 00:05:22,740 --> 00:05:26,370 therefore rational, if it's going to be realizable with a 104 00:05:26,370 --> 00:05:27,850 finite number of memory elements. 105 00:05:27,850 --> 00:05:31,200 So we include that in our definition of realizability. 106 00:05:31,200 --> 00:05:34,300 So these are sometimes called the realizable sequences, or 107 00:05:34,300 --> 00:05:37,030 the realizable D transforms. 108 00:05:37,030 --> 00:05:40,730 And these, of course, the causal finite sequences are 109 00:05:40,730 --> 00:05:41,700 the polynomials. 110 00:05:41,700 --> 00:05:46,260 These include the polynomials, which are trivially easy to 111 00:05:46,260 --> 00:05:53,460 realize with shift registers, as we saw in our example. 112 00:05:53,460 --> 00:05:57,450 So that's just a review of all these quantities. 113 00:05:57,450 --> 00:06:00,720 Does anyone feel the need for further elaboration or 114 00:06:00,720 --> 00:06:01,390 explanation? 115 00:06:01,390 --> 00:06:04,290 Or can we go forward with this? 116 00:06:04,290 --> 00:06:08,070 We tend to use all of them as we go along, so I want you to 117 00:06:08,070 --> 00:06:10,000 have them clearly in mind. 118 00:06:10,000 --> 00:06:10,230 Yeah. 119 00:06:10,230 --> 00:06:12,580 AUDIENCE: Why was the [INAUDIBLE] 120 00:06:12,580 --> 00:06:13,050 uncountable? 121 00:06:13,050 --> 00:06:14,930 What was the [INAUDIBLE]? 122 00:06:14,930 --> 00:06:18,020 PROFESSOR: Why is that uncountable? 123 00:06:18,020 --> 00:06:20,980 Try to count it. 124 00:06:20,980 --> 00:06:23,610 I could put it in one-to-one correspondence with a set of 125 00:06:23,610 --> 00:06:26,290 all binary expansions of the real numbers, and that's an 126 00:06:26,290 --> 00:06:27,540 uncountable set. 127 00:06:27,540 --> 00:06:35,610 128 00:06:35,610 --> 00:06:42,930 Some of these side comments are just to trigger analogies 129 00:06:42,930 --> 00:06:48,010 in your mind, maybe make it more reasonable, what we're 130 00:06:48,010 --> 00:06:50,400 talking about. 131 00:06:50,400 --> 00:06:53,130 OK, so next. 132 00:06:53,130 --> 00:07:02,150 Just again, to continue a quick review, we talked about 133 00:07:02,150 --> 00:07:07,895 realizable linear time-invariant systems. 134 00:07:07,895 --> 00:07:10,900 135 00:07:10,900 --> 00:07:16,805 First, we talked about single input, single output. 136 00:07:16,805 --> 00:07:20,470 I'm imposing an order that didn't necessarily exist. 137 00:07:20,470 --> 00:07:23,650 138 00:07:23,650 --> 00:07:28,150 In any case, these are characterized by impulse 139 00:07:28,150 --> 00:07:44,900 response, g of D, which, for realizability, that implies 140 00:07:44,900 --> 00:07:48,385 that g of D is causal rational. 141 00:07:48,385 --> 00:07:53,300 142 00:07:53,300 --> 00:07:57,840 The fact that it's rational means that we can write g of D 143 00:07:57,840 --> 00:08:04,730 as n of D over d of D. And the fact that it's causal, well, 144 00:08:04,730 --> 00:08:08,460 we would always reduce this to lowest terms in the first 145 00:08:08,460 --> 00:08:11,540 place, so there'd be no point carrying along common factors 146 00:08:11,540 --> 00:08:14,980 in the numerator and denominator. 147 00:08:14,980 --> 00:08:18,270 By inserting enough powers of D, we can make sure that both 148 00:08:18,270 --> 00:08:20,250 of these are polynomials. 149 00:08:20,250 --> 00:08:25,810 So if n of D, d of D are -- 150 00:08:25,810 --> 00:08:28,880 we can ensure that they're actually polynomials, not just 151 00:08:28,880 --> 00:08:31,230 finite sequences. 152 00:08:31,230 --> 00:08:35,720 And if it's going to be causal, that means that 153 00:08:35,720 --> 00:08:37,020 we can always -- 154 00:08:37,020 --> 00:08:42,909 if we remove common factors of D, that means that the 155 00:08:42,909 --> 00:08:45,590 numerator might still have factors of D in it, but the 156 00:08:45,590 --> 00:08:48,610 denominator can't have factors of D in it. 157 00:08:48,610 --> 00:08:50,390 You see that? 158 00:08:50,390 --> 00:08:54,360 Because, once we shift all these over as close to 0 as we 159 00:08:54,360 --> 00:08:58,110 can, the denominator has to be closer to 0. 160 00:08:58,110 --> 00:09:03,420 If D0 equals 1, that means 1 over d of D is something that 161 00:09:03,420 --> 00:09:05,890 starts at times 0. 162 00:09:05,890 --> 00:09:07,560 We multiply times the numerator. 163 00:09:07,560 --> 00:09:10,240 In order to have the whole thing be causal, the numerator 164 00:09:10,240 --> 00:09:13,890 has to be causal, because a point I didn't mention, when 165 00:09:13,890 --> 00:09:16,750 you multiply formal Laurent sequences, their delays add. 166 00:09:16,750 --> 00:09:19,290 167 00:09:19,290 --> 00:09:23,400 If a of D and b of D are Laurent, then the delay of a 168 00:09:23,400 --> 00:09:29,410 of D times b of D, defined as a convolution, is going to be 169 00:09:29,410 --> 00:09:31,740 the sum of the delays of each of the component sequence. 170 00:09:31,740 --> 00:09:34,250 You just take the lower order term on both and that's what 171 00:09:34,250 --> 00:09:37,020 determines the lower order term on the convolution, just 172 00:09:37,020 --> 00:09:40,780 like in polynomials and analogous to degrees. 173 00:09:40,780 --> 00:09:46,350 So from this, we find that we can always write a causal 174 00:09:46,350 --> 00:09:50,300 rational sequence in this form, if it isn't 0. 175 00:09:50,300 --> 00:09:54,630 If it is 0, we just take n of D to be 0, and d of D to be 1. 176 00:09:54,630 --> 00:09:56,930 And that satisfies this form, too. 177 00:09:56,930 --> 00:09:59,950 178 00:09:59,950 --> 00:10:03,670 I guess I didn't even have to make that comment. 179 00:10:03,670 --> 00:10:04,920 We're already in that form. 180 00:10:04,920 --> 00:10:07,650 181 00:10:07,650 --> 00:10:11,700 You can convince yourself this is a unique way to write a 182 00:10:11,700 --> 00:10:15,090 causal rational sequence. 183 00:10:15,090 --> 00:10:18,460 And every other way is just multiplying the numerator and 184 00:10:18,460 --> 00:10:28,030 the denominator by some common polynomial or finite sequence. 185 00:10:28,030 --> 00:10:36,100 So now we had a little theorem that says that, if g of D is 186 00:10:36,100 --> 00:10:45,190 causal rational, and therefore equal to n of D over d of D in 187 00:10:45,190 --> 00:10:57,242 this form, then realizable with how many memory elements? 188 00:10:57,242 --> 00:10:59,620 Does anyone remember? 189 00:10:59,620 --> 00:11:04,165 nu equals the maximum of the degrees. 190 00:11:04,165 --> 00:11:10,080 191 00:11:10,080 --> 00:11:14,130 And I debated whether to actually do this in class, and 192 00:11:14,130 --> 00:11:17,960 I think it's worth taking a few minutes to actually do 193 00:11:17,960 --> 00:11:18,740 this in class. 194 00:11:18,740 --> 00:11:23,050 It'll also appear as the first homework problem. 195 00:11:23,050 --> 00:11:26,090 So this'll be a little head start on the homework. 196 00:11:26,090 --> 00:11:31,290 So anybody have any ideas how we can do this realization? 197 00:11:31,290 --> 00:11:36,230 What we want is a circuit with an input, u of D. Eventually, 198 00:11:36,230 --> 00:11:43,220 an output, y of D equals u of D times n of D over d of D. 199 00:11:43,220 --> 00:11:46,410 For these are both polynomials and D0 equals 1. 200 00:11:46,410 --> 00:11:51,630 201 00:11:51,630 --> 00:11:55,210 A lot of you have probably seen this in discrete-time 202 00:11:55,210 --> 00:11:57,050 linear filters. 203 00:11:57,050 --> 00:11:58,720 It's going to be just the same technique. 204 00:11:58,720 --> 00:12:01,290 205 00:12:01,290 --> 00:12:03,380 But if we don't have volunteers, I don't want to 206 00:12:03,380 --> 00:12:05,570 waste time. 207 00:12:05,570 --> 00:12:06,770 The key is to use -- 208 00:12:06,770 --> 00:12:09,190 we're of course going to need feedback in general. 209 00:12:09,190 --> 00:12:13,350 To have a d of D, in general, will not be 1. 210 00:12:13,350 --> 00:12:17,600 If it's not 1, then we're going to get an infinite 211 00:12:17,600 --> 00:12:18,650 impulse response. 212 00:12:18,650 --> 00:12:22,100 To get an infinite impulse response, we need feedback. 213 00:12:22,100 --> 00:12:25,020 So we're going to need some feedback term in here. 214 00:12:25,020 --> 00:12:28,720 And here is the motivating idea of the construction. 215 00:12:28,720 --> 00:12:32,540 We want to create something here, v of D, which is 216 00:12:32,540 --> 00:12:38,030 basically equal to u of D over d of D. If we can do that, 217 00:12:38,030 --> 00:12:40,330 we'll be done. 218 00:12:40,330 --> 00:12:43,370 I'll show you why. 219 00:12:43,370 --> 00:12:45,740 So we created a different sequence, which is u of D 220 00:12:45,740 --> 00:12:49,965 divided by d of D. And then we pass that sequence through a 221 00:12:49,965 --> 00:12:51,215 shift register. 222 00:12:51,215 --> 00:12:58,660 223 00:12:58,660 --> 00:13:00,950 And what do we get at the various stages 224 00:13:00,950 --> 00:13:03,080 of the shift register? 225 00:13:03,080 --> 00:13:08,807 Here we would get v of D delayed by one time unit, v of 226 00:13:08,807 --> 00:13:13,540 D delayed by two time units, and so forth, up to -- 227 00:13:13,540 --> 00:13:17,210 let's make this nu. 228 00:13:17,210 --> 00:13:22,600 I want to realize it in nu memory elements, where nu is 229 00:13:22,600 --> 00:13:25,750 the maximum degree of either of these defining polynomials. 230 00:13:25,750 --> 00:13:35,700 So finally, out here, I get d nu of D, v of D. 231 00:13:35,700 --> 00:13:38,164 Now, what's the trick? 232 00:13:38,164 --> 00:13:40,060 AUDIENCE: [INAUDIBLE]. 233 00:13:40,060 --> 00:13:41,560 PROFESSOR: Excuse me? 234 00:13:41,560 --> 00:13:42,810 AUDIENCE: Because [UNINTELLIGIBLE PHRASE]. 235 00:13:42,810 --> 00:13:48,890 236 00:13:48,890 --> 00:13:49,850 PROFESSOR: That is the idea. 237 00:13:49,850 --> 00:13:54,420 What do we get if we take out these various lines, which are 238 00:13:54,420 --> 00:13:58,530 v of D, through d to the nu v of D, and we make a linear 239 00:13:58,530 --> 00:14:01,640 combination of them? 240 00:14:01,640 --> 00:14:04,280 We're going to do this twice, actually, once to form the 241 00:14:04,280 --> 00:14:13,420 feedback, and once to form the output. 242 00:14:13,420 --> 00:14:17,660 For the feedback, let me not take this into the linear 243 00:14:17,660 --> 00:14:18,910 combination. 244 00:14:18,910 --> 00:14:21,450 245 00:14:21,450 --> 00:14:25,960 Otherwise, I'd get a loop without a delay element in 246 00:14:25,960 --> 00:14:27,430 that, and that tends not to be well-defined. 247 00:14:27,430 --> 00:14:30,060 248 00:14:30,060 --> 00:14:32,560 So I want to take a linear combination. 249 00:14:32,560 --> 00:14:35,300 In general, by taking a linear combination of these things, I 250 00:14:35,300 --> 00:14:42,860 can get the multiple of v of D times any polynomial degree, 251 00:14:42,860 --> 00:14:49,260 nu or less, just by taking the coefficients of that 252 00:14:49,260 --> 00:14:52,816 polynomial as my linear combination. 253 00:14:52,816 --> 00:14:56,155 Do you see that? 254 00:14:56,155 --> 00:14:57,590 I'm not seeing people's -- 255 00:14:57,590 --> 00:14:58,840 AUDIENCE: [INAUDIBLE]. 256 00:14:58,840 --> 00:15:01,270 257 00:15:01,270 --> 00:15:04,035 PROFESSOR: Excuse me? 258 00:15:04,035 --> 00:15:05,410 AUDIENCE: In the linear combination 259 00:15:05,410 --> 00:15:06,730 [UNINTELLIGIBLE PHRASE] 260 00:15:06,730 --> 00:15:09,920 you also take the one with zero derivative. 261 00:15:09,920 --> 00:15:16,290 PROFESSOR: You're getting ahead of me, which is fine, 262 00:15:16,290 --> 00:15:20,180 but I'll ask for that comment in just a second. 263 00:15:20,180 --> 00:15:22,640 Let me first create the output. 264 00:15:22,640 --> 00:15:26,870 Suppose I had v of D equals u of D over d of D. Then to get 265 00:15:26,870 --> 00:15:30,440 the output, I simply want a linear combination, which will 266 00:15:30,440 --> 00:15:40,485 give me n of D times u of D over d of D. And that would be 267 00:15:40,485 --> 00:15:41,420 the correct output. 268 00:15:41,420 --> 00:15:44,170 And since n of D is a polynomial degree less than 269 00:15:44,170 --> 00:15:49,630 nu, I can do that by simply taking n nu times this, n nu 270 00:15:49,630 --> 00:15:54,270 minus 1 times that, n2 times that, n1 times that, and 0 271 00:15:54,270 --> 00:15:55,450 times that. 272 00:15:55,450 --> 00:15:59,940 And that will give me what I want as an output, if I'm 273 00:15:59,940 --> 00:16:02,510 successful in getting v of D of this form here. 274 00:16:02,510 --> 00:16:05,950 275 00:16:05,950 --> 00:16:10,580 So let me try a similar trick up here. 276 00:16:10,580 --> 00:16:16,760 The trick is, I force d of D to start off with a 1, to have 277 00:16:16,760 --> 00:16:18,830 D0 equal 1. 278 00:16:18,830 --> 00:16:21,320 So what I'm going to create up here is the linear 279 00:16:21,320 --> 00:16:29,680 combination, d of D minus 1 times v of D. 280 00:16:29,680 --> 00:16:34,050 First of all, let's verify that I can do that. 281 00:16:34,050 --> 00:16:35,560 d of D minus 1 is what? 282 00:16:35,560 --> 00:16:36,900 It's a polynomial. 283 00:16:36,900 --> 00:16:42,755 Its degree is the same as the degree of d of D. Now, if d of 284 00:16:42,755 --> 00:16:45,190 D is equal to 1, if the denominator is just 1, this 285 00:16:45,190 --> 00:16:46,610 whole thing falls out. 286 00:16:46,610 --> 00:16:48,620 I don't need anything coming in here. 287 00:16:48,620 --> 00:16:53,050 d of D is 1. v of D is equal to u of D, so that's the 288 00:16:53,050 --> 00:16:55,850 polynomial case where I don't need feedback. 289 00:16:55,850 --> 00:16:58,870 So let's assume d of D is not equal 1, therefore it's some 290 00:16:58,870 --> 00:17:05,000 polynomial of degree nu, degree of d of D, which is 291 00:17:05,000 --> 00:17:10,790 less than or equal to nu, and so is this. 292 00:17:10,790 --> 00:17:15,740 But by subtracting out the 1, I have no constant term. 293 00:17:15,740 --> 00:17:18,440 So it's going to be a multiple of D. That's another way of 294 00:17:18,440 --> 00:17:20,180 saying that. 295 00:17:20,180 --> 00:17:22,599 It's going to have no constant terms, so I only need to form 296 00:17:22,599 --> 00:17:25,230 a linear combination of these terms. 297 00:17:25,230 --> 00:17:26,480 So I can do it. 298 00:17:26,480 --> 00:17:29,486 299 00:17:29,486 --> 00:17:33,940 Now, if I do that, let's just solve this equation. 300 00:17:33,940 --> 00:17:37,580 I create x of D. This is supposed to be a plus. 301 00:17:37,580 --> 00:17:40,890 This is supposed to be a minus, to work over any field. 302 00:17:40,890 --> 00:17:44,820 This trick works over real or complex, or what you'd like. 303 00:17:44,820 --> 00:17:58,260 x of D is u of d minus d of D minus 1, times v of d, times x 304 00:17:58,260 --> 00:18:01,830 of D. Maybe I should just call this v of d. 305 00:18:01,830 --> 00:18:08,600 Now I'm going to solve for v of D. 306 00:18:08,600 --> 00:18:13,390 So I actually have a v of D on both sides of the equation. 307 00:18:13,390 --> 00:18:22,280 This results in u of D equal v of D times d of D. And 308 00:18:22,280 --> 00:18:25,230 dividing both sides by d of D, I see that I succeeded in 309 00:18:25,230 --> 00:18:26,810 getting what I wanted. 310 00:18:26,810 --> 00:18:32,240 So this is a typical trick of realizing a rational impulse 311 00:18:32,240 --> 00:18:37,570 response by including a feedback loop and negative 312 00:18:37,570 --> 00:18:39,360 feedback in your system. 313 00:18:39,360 --> 00:18:42,950 314 00:18:42,950 --> 00:18:45,490 This is done in the notes. 315 00:18:45,490 --> 00:18:47,510 I'm surprised if you haven't seen this before. 316 00:18:47,510 --> 00:18:49,610 Maybe it's that people in communications don't take 317 00:18:49,610 --> 00:18:52,300 circuits courses, or they don't take digital signal 318 00:18:52,300 --> 00:18:53,630 processing courses. 319 00:18:53,630 --> 00:18:55,906 Most people look puzzled. 320 00:18:55,906 --> 00:18:58,340 In any case, can you agree that, formally, I've shown 321 00:18:58,340 --> 00:19:00,500 that we get what we want here? 322 00:19:00,500 --> 00:19:09,270 So I've given a way of realizing, given a causal 323 00:19:09,270 --> 00:19:13,330 rational function, where nu is defined is the maximum degree 324 00:19:13,330 --> 00:19:15,510 of these two polynomials. 325 00:19:15,510 --> 00:19:18,960 There's a realization with nu memory elements. 326 00:19:18,960 --> 00:19:21,590 A little bit more work, we could prove that this is the 327 00:19:21,590 --> 00:19:23,370 minimum possible number of memory 328 00:19:23,370 --> 00:19:27,600 elements for this system. 329 00:19:27,600 --> 00:19:29,375 That gets into linear system theory. 330 00:19:29,375 --> 00:19:30,625 AUDIENCE: [INAUDIBLE]. 331 00:19:30,625 --> 00:19:36,020 332 00:19:36,020 --> 00:19:40,120 PROFESSOR: I mean, what I want is down here, I want the sum 333 00:19:40,120 --> 00:19:51,510 of n_i times d to the i, v of D. So the linear coefficients 334 00:19:51,510 --> 00:19:52,760 are going to be these n_i. 335 00:19:52,760 --> 00:19:58,150 336 00:19:58,150 --> 00:20:02,640 If I drew it out, I have n0 here, n1 here. 337 00:20:02,640 --> 00:20:06,240 So it's scalar linear combination, over F2. 338 00:20:06,240 --> 00:20:13,216 339 00:20:13,216 --> 00:20:15,000 And what is that? 340 00:20:15,000 --> 00:20:16,820 v of D is common. 341 00:20:16,820 --> 00:20:21,720 That's just n of D times v of D. Same trick up here. 342 00:20:21,720 --> 00:20:24,660 343 00:20:24,660 --> 00:20:27,970 Is that what was puzzling everybody? 344 00:20:27,970 --> 00:20:28,540 Think about it. 345 00:20:28,540 --> 00:20:31,920 What is a linear combination? 346 00:20:31,920 --> 00:20:33,170 Something that looks like that. 347 00:20:33,170 --> 00:20:38,880 348 00:20:38,880 --> 00:20:46,885 The second part, let's now talk about a 349 00:20:46,885 --> 00:20:48,135 convolutional encoder. 350 00:20:48,135 --> 00:20:55,350 351 00:20:55,350 --> 00:21:00,990 And we're just going to talk about rate 1/n in this course. 352 00:21:00,990 --> 00:21:02,945 So this is a single input. 353 00:21:02,945 --> 00:21:07,350 354 00:21:07,350 --> 00:21:13,485 n output linear time invariant system. 355 00:21:13,485 --> 00:21:16,560 356 00:21:16,560 --> 00:21:21,550 That's my definition, I guess, of what I mean by a 357 00:21:21,550 --> 00:21:22,890 convolutional encoder. 358 00:21:22,890 --> 00:21:27,445 And when I say linear time-invariant, I also want it 359 00:21:27,445 --> 00:21:31,760 to be a realizable, in the two senses that its impulse 360 00:21:31,760 --> 00:21:33,380 response is causal rational. 361 00:21:33,380 --> 00:21:35,960 362 00:21:35,960 --> 00:21:39,292 So [INAUDIBLE] 363 00:21:39,292 --> 00:21:40,610 down. 364 00:21:40,610 --> 00:21:55,550 Now it's characterized by n-tuple of impulse responses. 365 00:21:55,550 --> 00:22:01,790 366 00:22:01,790 --> 00:22:11,300 So it's going to be sum g of D equal to g1 of D, up to gn of 367 00:22:11,300 --> 00:22:19,350 D, where clearly all these have to be causal and rational 368 00:22:19,350 --> 00:22:21,010 in order for it to be realizable. 369 00:22:21,010 --> 00:22:23,740 If any one of them was not causal or not rational, then 370 00:22:23,740 --> 00:22:26,110 that individual impulse response wouldn't be 371 00:22:26,110 --> 00:22:30,080 realizable and the whole thing wouldn't be realizable. 372 00:22:30,080 --> 00:22:35,330 So where we have the gj of D are all causal rational. 373 00:22:35,330 --> 00:22:43,160 374 00:22:43,160 --> 00:22:48,760 And now, again, I'm going to put this into a standard form. 375 00:22:48,760 --> 00:22:56,480 In general, this is going to be n1 of D over d1 of D, so 376 00:22:56,480 --> 00:23:02,730 forth, up to n_n of D over d_n of D. So I'm going to have 377 00:23:02,730 --> 00:23:08,070 different denominators for each of the numerators. 378 00:23:08,070 --> 00:23:16,360 But I can always put it into the form, n1 prime of D over a 379 00:23:16,360 --> 00:23:25,495 common numerator, d to D, and up to n_n prime of D over d of 380 00:23:25,495 --> 00:23:29,730 D. Let d of D be the least common multiple 381 00:23:29,730 --> 00:23:31,890 of all these d_i's. 382 00:23:31,890 --> 00:23:33,450 These are all polynomials. 383 00:23:33,450 --> 00:23:35,650 Least common multiple is well-defined from our 384 00:23:35,650 --> 00:23:37,630 discussion of factorization. 385 00:23:37,630 --> 00:23:40,630 So I can always put in the least common multiple here, 386 00:23:40,630 --> 00:23:44,410 and then whatever d1 lacks out of the least common multiple, 387 00:23:44,410 --> 00:23:46,760 I multiply top and bottom by both of that. 388 00:23:46,760 --> 00:23:50,300 I have the same rational function, now with a common 389 00:23:50,300 --> 00:23:52,530 denominator. 390 00:23:52,530 --> 00:23:56,670 So I'm always going to put it in that standard form. 391 00:23:56,670 --> 00:24:13,520 And then I will say this is always realizable, with nu 392 00:24:13,520 --> 00:24:17,180 equal now the max of any of the degrees 393 00:24:17,180 --> 00:24:18,310 that appears in here. 394 00:24:18,310 --> 00:24:24,870 So let me just abbreviate that by degree of the numerators, 395 00:24:24,870 --> 00:24:28,370 which I'll just write as vector n prime of D, or the 396 00:24:28,370 --> 00:24:31,505 degree of the denominator d, of the common denominator d of 397 00:24:31,505 --> 00:24:36,540 D. Now, that's very easy to see. 398 00:24:36,540 --> 00:24:39,350 399 00:24:39,350 --> 00:24:40,600 Why is that? 400 00:24:40,600 --> 00:24:43,300 401 00:24:43,300 --> 00:24:45,970 Can certainly realize the first one here 402 00:24:45,970 --> 00:24:47,220 just by doing that. 403 00:24:47,220 --> 00:24:50,300 404 00:24:50,300 --> 00:24:52,045 Yes? 405 00:24:52,045 --> 00:24:56,540 If I want to just generate the first output, I build a 406 00:24:56,540 --> 00:24:58,985 circuit like this, and I don't need more of 407 00:24:58,985 --> 00:25:01,212 the new memory elements. 408 00:25:01,212 --> 00:25:02,990 There might even be some redundancy in that. 409 00:25:02,990 --> 00:25:05,980 410 00:25:05,980 --> 00:25:09,095 All right, so how would I then realize the second? 411 00:25:09,095 --> 00:25:15,550 412 00:25:15,550 --> 00:25:16,400 Is it just me? 413 00:25:16,400 --> 00:25:17,680 Nobody is volunteering anything. 414 00:25:17,680 --> 00:25:23,400 415 00:25:23,400 --> 00:25:24,460 I've realized this. 416 00:25:24,460 --> 00:25:29,260 Now I'd like to realize a second output. 417 00:25:29,260 --> 00:25:31,440 Now I want to realize this. 418 00:25:31,440 --> 00:25:36,760 Make this n1 of D. I want to realize n2 of D over d of D, 419 00:25:36,760 --> 00:25:39,151 times u of D. 420 00:25:39,151 --> 00:25:40,401 AUDIENCE: [INAUDIBLE]. 421 00:25:40,401 --> 00:25:43,960 422 00:25:43,960 --> 00:25:44,842 PROFESSOR: Thank you so much. 423 00:25:44,842 --> 00:25:46,165 AUDIENCE: Just take out [UNINTELLIGIBLE]. 424 00:25:46,165 --> 00:25:47,240 PROFESSOR: All right. 425 00:25:47,240 --> 00:25:51,870 So all I need is the second linear combination. 426 00:25:51,870 --> 00:25:57,090 So let me just make this n linear combinations. 427 00:25:57,090 --> 00:26:00,640 Then we're going to have n outputs, 428 00:26:00,640 --> 00:26:02,140 an n-tuple of outputs. 429 00:26:02,140 --> 00:26:04,440 Then I can form each one as a linear 430 00:26:04,440 --> 00:26:05,990 combination of those up there. 431 00:26:05,990 --> 00:26:11,150 432 00:26:11,150 --> 00:26:13,140 I really like more of you to be speaking up. 433 00:26:13,140 --> 00:26:13,920 Yes, thank you. 434 00:26:13,920 --> 00:26:15,342 AUDIENCE: [INAUDIBLE]. 435 00:26:15,342 --> 00:26:16,290 PROFESSOR: Excuse me? 436 00:26:16,290 --> 00:26:18,186 AUDIENCE: There's a second combination -- 437 00:26:18,186 --> 00:26:21,030 I mean the inquiry should come [UNINTELLIGIBLE]. 438 00:26:21,030 --> 00:26:24,680 PROFESSOR: Yeah, but again, what I want to realize, I have 439 00:26:24,680 --> 00:26:27,520 all the delays of v of D up here. 440 00:26:27,520 --> 00:26:32,750 What I want to realize is n2 of D times v of D, which is 441 00:26:32,750 --> 00:26:34,340 equal to that. 442 00:26:34,340 --> 00:26:37,200 n2 of D is the polynomial of degree less 443 00:26:37,200 --> 00:26:38,640 than or equal to nu. 444 00:26:38,640 --> 00:26:39,420 So I can do it. 445 00:26:39,420 --> 00:26:42,760 AUDIENCE: Yeah, but [UNINTELLIGIBLE PHRASE] 446 00:26:42,760 --> 00:26:44,630 parallel to that n1 D over d. 447 00:26:44,630 --> 00:26:45,110 The -- 448 00:26:45,110 --> 00:26:46,070 [INTERPOSING VOICES] 449 00:26:46,070 --> 00:26:48,490 PROFESSOR: Yeah, OK. 450 00:26:48,490 --> 00:26:50,800 I'm confusing you because I put all these here. 451 00:26:50,800 --> 00:26:54,530 I actually wrote out the linear combination. 452 00:26:54,530 --> 00:26:58,160 To say what I just said, I really need to go back to my 453 00:26:58,160 --> 00:27:01,570 original form, forget these multipliers, do the 454 00:27:01,570 --> 00:27:02,660 multiplications in here. 455 00:27:02,660 --> 00:27:06,110 That's what I mean by the linear combinations. 456 00:27:06,110 --> 00:27:07,990 Now I'm OK. 457 00:27:07,990 --> 00:27:10,080 The inputs are just the shifts. 458 00:27:10,080 --> 00:27:12,289 Make a linear combination of them, that's the output. 459 00:27:12,289 --> 00:27:17,450 460 00:27:17,450 --> 00:27:20,600 So easy proof. 461 00:27:20,600 --> 00:27:24,090 What's significantly harder to prove in this case is you 462 00:27:24,090 --> 00:27:25,410 can't do any better than. 463 00:27:25,410 --> 00:27:29,890 There aren't any realizations with fewer than nu, where nu 464 00:27:29,890 --> 00:27:33,970 is computed by first reducing to standard form and then 465 00:27:33,970 --> 00:27:35,600 evaluating this. 466 00:27:35,600 --> 00:27:38,550 That's the best you can do. 467 00:27:38,550 --> 00:27:42,390 But we aren't going to go into minimal system realizations, 468 00:27:42,390 --> 00:27:44,330 linear system realizations in this course. 469 00:27:44,330 --> 00:27:45,667 I'll just insert it. 470 00:27:45,667 --> 00:27:48,190 471 00:27:48,190 --> 00:27:53,200 So this is how we can always build a convolutional encoder, 472 00:27:53,200 --> 00:27:55,780 whether it has feedback or not. 473 00:27:55,780 --> 00:28:00,360 And so whatever we come up with as nu, this'll basically 474 00:28:00,360 --> 00:28:03,400 determine the state complexity of our decoder. 475 00:28:03,400 --> 00:28:08,670 The state space is dimension nu, is finite dimension. 476 00:28:08,670 --> 00:28:13,490 And because we're over a finite field, the actual 477 00:28:13,490 --> 00:28:16,920 number of states is only 2 to the nu. 478 00:28:16,920 --> 00:28:20,085 Still can't get more than 2 to the nu states for 479 00:28:20,085 --> 00:28:22,310 that system up there. 480 00:28:22,310 --> 00:28:25,120 So we're still in finite state world. 481 00:28:25,120 --> 00:28:30,940 So in particular, it's finite state realization. 482 00:28:30,940 --> 00:28:33,860 And again, this is if and only if. 483 00:28:33,860 --> 00:28:36,120 If we have if and only if, we have an n-tuple of causal 484 00:28:36,120 --> 00:28:40,790 rational, or even a matrix of causal rationals. 485 00:28:40,790 --> 00:28:43,030 We can make a realization like this. 486 00:28:43,030 --> 00:28:46,470 487 00:28:46,470 --> 00:28:48,575 So that's convolutional encoders. 488 00:28:48,575 --> 00:28:52,630 At least write 1/n over F2. 489 00:28:52,630 --> 00:28:57,010 And now the next step was what's a convolutional code. 490 00:28:57,010 --> 00:29:02,510 491 00:29:02,510 --> 00:29:08,330 And a convolutional code, we defined as, given a 492 00:29:08,330 --> 00:29:13,630 convolutional encoder, which is just the set of impulse 493 00:29:13,630 --> 00:29:19,330 response, given g of D, the corresponding convolutional 494 00:29:19,330 --> 00:29:25,180 code is just u of D, which is single sequence times this 495 00:29:25,180 --> 00:29:30,410 n-tuple of sequences, as u of D ranges through all the 496 00:29:30,410 --> 00:29:32,093 formal Laurent sequences. 497 00:29:32,093 --> 00:29:37,550 498 00:29:37,550 --> 00:29:41,090 Sequences that start at some time in the all-zero state and 499 00:29:41,090 --> 00:29:45,060 then continue perhaps forever. 500 00:29:45,060 --> 00:29:50,660 It's very quick to show that C, its 501 00:29:50,660 --> 00:29:53,200 properties is it's linear. 502 00:29:53,200 --> 00:29:57,440 Obviously, it's a vector space over F2. 503 00:29:57,440 --> 00:29:59,990 Multiplication by scalars is trivial. 504 00:29:59,990 --> 00:30:04,300 Addition is trivial, so it's linear. 505 00:30:04,300 --> 00:30:12,700 And its time-invariant, meaning the shift of any code 506 00:30:12,700 --> 00:30:14,250 sequence is another code sequence. 507 00:30:14,250 --> 00:30:22,040 If I have one particular code sequence, and I want to see if 508 00:30:22,040 --> 00:30:25,220 the shift of that is in the code, well, that code sequence 509 00:30:25,220 --> 00:30:28,610 must have been generated by some use, so if I just shift 510 00:30:28,610 --> 00:30:32,370 the u by the amount of time that I want to shift the 511 00:30:32,370 --> 00:30:36,800 output, y, then I'll get the shifted output. 512 00:30:36,800 --> 00:30:43,980 So it's easy to show that D to the k of C is simply equal to 513 00:30:43,980 --> 00:30:51,510 C for any integer k. 514 00:30:51,510 --> 00:30:55,080 Actually, it just suffices to show that the single time unit 515 00:30:55,080 --> 00:30:57,717 shift is in the code, and that implies all the rest of this. 516 00:30:57,717 --> 00:31:01,390 517 00:31:01,390 --> 00:31:01,890 Yes? 518 00:31:01,890 --> 00:31:03,140 AUDIENCE: [UNINTELLIGIBLE]. 519 00:31:03,140 --> 00:31:05,740 520 00:31:05,740 --> 00:31:10,276 We would want at least one of the g_i of D's to start at 0. 521 00:31:10,276 --> 00:31:13,380 Otherwise, they don't cancel out, do they? 522 00:31:13,380 --> 00:31:14,630 PROFESSOR: Right. 523 00:31:14,630 --> 00:31:17,530 524 00:31:17,530 --> 00:31:21,340 So what you're saying is we don't want d to be a common 525 00:31:21,340 --> 00:31:24,890 factor of all the n of D's. 526 00:31:24,890 --> 00:31:25,680 And that's true. 527 00:31:25,680 --> 00:31:28,780 In fact, we don't want to have any common factors of 528 00:31:28,780 --> 00:31:30,030 all the n of D's. 529 00:31:30,030 --> 00:31:33,270 530 00:31:33,270 --> 00:31:34,520 AUDIENCE: [INAUDIBLE]. 531 00:31:34,520 --> 00:31:37,540 532 00:31:37,540 --> 00:31:40,180 PROFESSOR: The u we've defined, so it can 533 00:31:40,180 --> 00:31:41,290 start at any time. 534 00:31:41,290 --> 00:31:43,790 AUDIENCE: [INAUDIBLE]. 535 00:31:43,790 --> 00:31:47,190 PROFESSOR: So notice that these have separate algebraic 536 00:31:47,190 --> 00:31:48,660 characters. 537 00:31:48,660 --> 00:31:51,800 This is a Laurent sequence. 538 00:31:51,800 --> 00:31:54,660 These are called causal rational sequences. 539 00:31:54,660 --> 00:31:58,040 So they have different restrictions on them, but they 540 00:31:58,040 --> 00:32:00,240 play together that way. 541 00:32:00,240 --> 00:32:04,940 542 00:32:04,940 --> 00:32:09,680 So where you're getting to is this idea of code equivalence. 543 00:32:09,680 --> 00:32:12,850 544 00:32:12,850 --> 00:32:14,210 I can just keep going. 545 00:32:14,210 --> 00:32:17,660 546 00:32:17,660 --> 00:32:33,600 So code equivalence, let's abbreviate it this way. 547 00:32:33,600 --> 00:32:40,520 g of D and some other n-tuple, g prime of D, 548 00:32:40,520 --> 00:32:42,040 generate the same code. 549 00:32:42,040 --> 00:32:45,865 We say that g of D generates C up here. 550 00:32:45,865 --> 00:32:49,480 551 00:32:49,480 --> 00:32:57,790 So two different n-tuples generate the same code, C, 552 00:32:57,790 --> 00:32:59,405 which is our notion of equivalence. 553 00:32:59,405 --> 00:33:03,690 554 00:33:03,690 --> 00:33:10,180 And we more or less proved last time it is true that g of 555 00:33:10,180 --> 00:33:14,120 D is some -- 556 00:33:14,120 --> 00:33:22,270 this is just a single sequence multiple of g prime of D. So 557 00:33:22,270 --> 00:33:24,780 we have to have a of D not equal to 0. 558 00:33:24,780 --> 00:33:29,810 Otherwise, I think there could be any sequence there. 559 00:33:29,810 --> 00:33:34,830 So what you were saying is that, if all of these n's had 560 00:33:34,830 --> 00:33:39,205 a common factor of d, then why not just shift them all over? 561 00:33:39,205 --> 00:33:41,800 And that would be the same as multiplying -- 562 00:33:41,800 --> 00:33:44,060 suppose we had a g prime of D where they all had d's. 563 00:33:44,060 --> 00:33:46,800 Suppose we just multiply them with d minus 1. 564 00:33:46,800 --> 00:33:49,370 We're still going to get the same code, but we're going to 565 00:33:49,370 --> 00:33:52,580 reduce the degrees of all the numerators. 566 00:33:52,580 --> 00:33:56,970 And therefore, we're likely to get a simpler realization. 567 00:33:56,970 --> 00:33:59,290 And that's the track we're going down right now. 568 00:33:59,290 --> 00:34:00,540 AUDIENCE: [INAUDIBLE]. 569 00:34:00,540 --> 00:34:05,090 570 00:34:05,090 --> 00:34:07,250 PROFESSOR: This would only shift the n's. 571 00:34:07,250 --> 00:34:10,650 572 00:34:10,650 --> 00:34:15,570 I'm assuming that all the n of D's are multiples of d. 573 00:34:15,570 --> 00:34:17,590 AUDIENCE: [INAUDIBLE] 574 00:34:17,590 --> 00:34:18,670 the root of d, right? 575 00:34:18,670 --> 00:34:23,900 So if you can reduce the d of D you can't save anything. 576 00:34:23,900 --> 00:34:26,370 PROFESSOR: You might not save anything if you've got a 577 00:34:26,370 --> 00:34:29,245 denominator, d of D, that has a larger degree. 578 00:34:29,245 --> 00:34:31,250 AUDIENCE: And that's always the case. 579 00:34:31,250 --> 00:34:33,739 PROFESSOR: No, it's not always the case. 580 00:34:33,739 --> 00:34:35,250 In the general case, either one of 581 00:34:35,250 --> 00:34:39,530 these things can dominate. 582 00:34:39,530 --> 00:34:44,469 In that picture we had, if we have a low degree, d of D, 583 00:34:44,469 --> 00:34:47,510 then it's only picking off of these first elements up here. 584 00:34:47,510 --> 00:34:50,532 AUDIENCE: But that definition states [UNINTELLIGIBLE] 585 00:34:50,532 --> 00:34:51,696 is the maximum d and also the [UNINTELLIGIBLE]. 586 00:34:51,696 --> 00:34:52,610 PROFESSOR: Right. 587 00:34:52,610 --> 00:34:56,870 So we could have a big one here making the outputs, and a 588 00:34:56,870 --> 00:34:58,850 small one there going back. 589 00:34:58,850 --> 00:35:01,780 In fact, we could have d of D equal to 1. 590 00:35:01,780 --> 00:35:04,650 Then we'd have no feedback whatsoever. 591 00:35:04,650 --> 00:35:08,400 So it could be either way. 592 00:35:08,400 --> 00:35:12,250 But then given this code equivalence concept, suppose 593 00:35:12,250 --> 00:35:13,950 we have a d of D that is very big. 594 00:35:13,950 --> 00:35:17,800 Suppose it's dominated by d of D. What would be a 595 00:35:17,800 --> 00:35:19,050 good thing to do? 596 00:35:19,050 --> 00:35:24,610 597 00:35:24,610 --> 00:35:28,660 We have a certain code we want to keep, but the nu, the 598 00:35:28,660 --> 00:35:31,540 numbers for the dimension of the state space is dominated 599 00:35:31,540 --> 00:35:40,860 by the degree of d of D. So suppose we have g of D equal 600 00:35:40,860 --> 00:35:50,660 to n of D over d of D. And we have degree of d of D is 601 00:35:50,660 --> 00:35:55,750 greater than degree of n of D. What would be a 602 00:35:55,750 --> 00:35:57,000 good thing to do? 603 00:35:57,000 --> 00:36:02,120 604 00:36:02,120 --> 00:36:09,720 Why don't we just let g prime of D be equal to d of D times 605 00:36:09,720 --> 00:36:19,950 g of D, and that would be just n of D. 606 00:36:19,950 --> 00:36:27,240 So I'm going to convert from the code generated by these 607 00:36:27,240 --> 00:36:31,060 rational generators, which are infinite. 608 00:36:31,060 --> 00:36:34,880 I can easily just multiply out the denominator, and now I 609 00:36:34,880 --> 00:36:39,900 have a code generated just by the numerator terms. 610 00:36:39,900 --> 00:36:41,150 So it's feedback-free. 611 00:36:41,150 --> 00:36:44,180 612 00:36:44,180 --> 00:36:46,950 That may or may not be important to me. 613 00:36:46,950 --> 00:36:52,410 Actually, it turns out it's very hard to make a case for 614 00:36:52,410 --> 00:36:56,420 not having feedback, but it's simpler, in any case. 615 00:36:56,420 --> 00:36:59,810 We don't have this feedback term in the encoders. 616 00:36:59,810 --> 00:37:02,430 So we get a feedback-free encoder. 617 00:37:02,430 --> 00:37:06,525 And if this is true, we may reduce -- 618 00:37:06,525 --> 00:37:09,430 619 00:37:09,430 --> 00:37:11,130 we can certainly never increase it. 620 00:37:11,130 --> 00:37:13,890 621 00:37:13,890 --> 00:37:17,950 But if this were true, then we would reduce it. 622 00:37:17,950 --> 00:37:20,280 If on the other hand, this were less than or equal, then 623 00:37:20,280 --> 00:37:22,510 nu would remain the same. 624 00:37:22,510 --> 00:37:24,370 So that seems like that would be a good thing to do. 625 00:37:24,370 --> 00:37:28,540 626 00:37:28,540 --> 00:37:34,910 So in fact, as I would advocate as a first step, that 627 00:37:34,910 --> 00:37:37,960 you clear the denominators, and just come up with a 628 00:37:37,960 --> 00:37:43,410 polynomial generator sequence which generates the same code. 629 00:37:43,410 --> 00:37:45,330 We're still going to have the same minimum distance, the 630 00:37:45,330 --> 00:37:48,300 same code sequence, the problem from the decoder's 631 00:37:48,300 --> 00:37:50,035 point of view is going to be absolutely unchanged. 632 00:37:50,035 --> 00:37:52,850 The decoder only cares what the consequences are. 633 00:37:52,850 --> 00:37:54,830 It wants to find the most likely one that was 634 00:37:54,830 --> 00:37:55,710 transmitted. 635 00:37:55,710 --> 00:37:58,970 So let's not make the encoder any more complicated 636 00:37:58,970 --> 00:38:01,596 than we have to. 637 00:38:01,596 --> 00:38:02,846 AUDIENCE: [UNINTELLIGIBLE PHRASE] 638 00:38:02,846 --> 00:38:13,060 639 00:38:13,060 --> 00:38:16,590 PROFESSOR: nu doesn't change in this condition. 640 00:38:16,590 --> 00:38:18,805 nu does change in this condition. 641 00:38:18,805 --> 00:38:22,392 AUDIENCE: So we are always better off multiplying by g of 642 00:38:22,392 --> 00:38:22,490 D. 643 00:38:22,490 --> 00:38:23,300 PROFESSOR: We can't be worse off. 644 00:38:23,300 --> 00:38:23,610 [INTERPOSING VOICES] 645 00:38:23,610 --> 00:38:25,040 AUDIENCE: --or the same. 646 00:38:25,040 --> 00:38:27,530 PROFESSOR: Exactly. 647 00:38:27,530 --> 00:38:29,810 Got it. 648 00:38:29,810 --> 00:38:34,630 All right, so let's now talk about whether there's anything 649 00:38:34,630 --> 00:38:39,300 we can do to n of D. We already suggested that if all 650 00:38:39,300 --> 00:38:42,610 the n of D had a factor of d in them, why don't 651 00:38:42,610 --> 00:38:43,860 just take it out? 652 00:38:43,860 --> 00:38:47,870 653 00:38:47,870 --> 00:38:49,150 Let's just write that down. 654 00:38:49,150 --> 00:39:03,510 If all n of D have a factor of d, then let's just transform n 655 00:39:03,510 --> 00:39:09,680 of D to d minus 1 n of D. 656 00:39:09,680 --> 00:39:12,455 So that reduces nu also. 657 00:39:12,455 --> 00:39:15,360 658 00:39:15,360 --> 00:39:19,130 And let's, of course, do that as many times as we can. 659 00:39:19,130 --> 00:39:23,060 So it's a good idea to take out common factors of d. 660 00:39:23,060 --> 00:39:24,490 We get a simpler encoder. 661 00:39:24,490 --> 00:39:26,125 We're have a simpler state diagram. 662 00:39:26,125 --> 00:39:30,010 663 00:39:30,010 --> 00:39:38,710 This leads us to a topic called catastrophicity, which 664 00:39:38,710 --> 00:39:41,990 is a misleading title because you have no idea where I'm 665 00:39:41,990 --> 00:39:43,540 going right now. 666 00:39:43,540 --> 00:39:45,340 So I'm actually going to try to fool you 667 00:39:45,340 --> 00:39:47,140 for a little while. 668 00:39:47,140 --> 00:39:47,500 Yes? 669 00:39:47,500 --> 00:39:48,726 AUDIENCE: Quick question. 670 00:39:48,726 --> 00:39:51,320 In the definition of code equivalence, is there a 671 00:39:51,320 --> 00:39:53,340 restriction [UNINTELLIGIBLE] 672 00:39:53,340 --> 00:39:57,460 that shouldn't be rational, shouldn't be causal? 673 00:39:57,460 --> 00:40:01,470 PROFESSOR: Should there be a restriction on this? 674 00:40:01,470 --> 00:40:02,480 Yes, of course. 675 00:40:02,480 --> 00:40:05,940 It has to be rational in order -- 676 00:40:05,940 --> 00:40:08,470 677 00:40:08,470 --> 00:40:10,570 But that's a consequence. 678 00:40:10,570 --> 00:40:13,930 If these are both causal rational, then what does a of 679 00:40:13,930 --> 00:40:14,620 D have to be? 680 00:40:14,620 --> 00:40:16,770 It has to be rational. 681 00:40:16,770 --> 00:40:19,320 It has to be non-zero. 682 00:40:19,320 --> 00:40:22,300 And does it have to be causal? 683 00:40:22,300 --> 00:40:25,620 No, in this case it's not causal. 684 00:40:25,620 --> 00:40:26,870 AUDIENCE: [INAUDIBLE]. 685 00:40:26,870 --> 00:40:31,310 686 00:40:31,310 --> 00:40:33,460 PROFESSOR: That's right. 687 00:40:33,460 --> 00:40:37,960 If there's a delay buried in g of D, if everything starts at 688 00:40:37,960 --> 00:40:41,870 time 1 or later, then a of D, in fact, can be non-causal. 689 00:40:41,870 --> 00:40:45,190 So the key restrictions are that these two guys have to be 690 00:40:45,190 --> 00:40:46,360 causal rational. 691 00:40:46,360 --> 00:40:52,450 And that will tell you restrictions on a. 692 00:40:52,450 --> 00:40:54,240 Let me introduce this by example. 693 00:40:54,240 --> 00:40:56,860 And I'll warn you that I'm going to try to 694 00:40:56,860 --> 00:40:58,940 fool you for a while. 695 00:40:58,940 --> 00:41:02,150 Let's just take a rate 1/1 encoder. 696 00:41:02,150 --> 00:41:09,060 This may seem a little peculiar to you, because it 697 00:41:09,060 --> 00:41:13,910 has no redundancy, one input, one output. 698 00:41:13,910 --> 00:41:18,300 And I'm going to let g of D just be 1 plus d. 699 00:41:18,300 --> 00:41:22,550 700 00:41:22,550 --> 00:41:23,380 So what do I mean? 701 00:41:23,380 --> 00:41:25,780 I'm going to try to get some mileage out of this encoder. 702 00:41:25,780 --> 00:41:29,146 703 00:41:29,146 --> 00:41:43,710 Here's u of D. Here's y of D, equals 1 plus d times u of D. 704 00:41:43,710 --> 00:41:48,295 Now let's draw the state diagram for this encoder. 705 00:41:48,295 --> 00:41:50,730 It's only got two states. 706 00:41:50,730 --> 00:41:51,580 One is 0. 707 00:41:51,580 --> 00:41:56,420 If we get a 0 in, we of course put a 0 out. 708 00:41:56,420 --> 00:41:57,740 We get 0, 0. 709 00:41:57,740 --> 00:42:00,105 Or we could get a 1 in. 710 00:42:00,105 --> 00:42:03,390 In which case, we would get a 1 out. 711 00:42:03,390 --> 00:42:06,230 Sorry, that was just a single output. 712 00:42:06,230 --> 00:42:08,346 And go to 1. 713 00:42:08,346 --> 00:42:17,000 If we're in the 1 state, and we get a 0 in, 714 00:42:17,000 --> 00:42:18,790 then we get a 1 out. 715 00:42:18,790 --> 00:42:22,990 Whereas if we get a 1 in, then they're both 0, and we get the 716 00:42:22,990 --> 00:42:24,350 complement. 717 00:42:24,350 --> 00:42:27,140 So with the 1, we get a 0 out. 718 00:42:27,140 --> 00:42:30,180 So that's the state transition diagram of this encoder. 719 00:42:30,180 --> 00:42:36,500 720 00:42:36,500 --> 00:42:39,040 Now, let's go through a similar kind of argument to 721 00:42:39,040 --> 00:42:41,470 what we went through to find the minimum distance was 5. 722 00:42:41,470 --> 00:42:45,170 This is a linear system, so we want to find the minimum 723 00:42:45,170 --> 00:42:48,350 non-zero weight of any code word. 724 00:42:48,350 --> 00:42:51,720 And here's my argument. 725 00:42:51,720 --> 00:42:54,050 There's a gold star to the first person who punches a 726 00:42:54,050 --> 00:42:56,380 hole in it. 727 00:42:56,380 --> 00:43:01,560 Any code word, you have to start in the 0 state, so 728 00:43:01,560 --> 00:43:03,700 you're always going to get at least one unit of distance 729 00:43:03,700 --> 00:43:07,120 when you go to the 1 state. 730 00:43:07,120 --> 00:43:10,550 You can stay out here as long as you like, but eventually 731 00:43:10,550 --> 00:43:14,550 you have to come back to the 0 state. 732 00:43:14,550 --> 00:43:16,430 And at that point, you're going to get 733 00:43:16,430 --> 00:43:18,600 another unit of distance. 734 00:43:18,600 --> 00:43:25,360 So I claim the minimum non-zero weight is 2. 735 00:43:25,360 --> 00:43:33,328 736 00:43:33,328 --> 00:43:34,578 Is that correct? 737 00:43:34,578 --> 00:43:39,870 738 00:43:39,870 --> 00:43:41,870 Let me try to create some doubt. 739 00:43:41,870 --> 00:43:44,420 What is the code here? 740 00:43:44,420 --> 00:43:51,620 The code is the set of all multiples of 1 plus d times u 741 00:43:51,620 --> 00:43:58,335 of D, where u of D is a formal Laurent sequence. 742 00:43:58,335 --> 00:44:01,240 743 00:44:01,240 --> 00:44:04,420 What is that? 744 00:44:04,420 --> 00:44:07,490 I can write this briefly as just the set of all formal 745 00:44:07,490 --> 00:44:10,330 Laurent sequences times 1 plus d. 746 00:44:10,330 --> 00:44:10,514 AUDIENCE: [INAUDIBLE] 747 00:44:10,514 --> 00:44:19,160 1 minus d minus d squared. 748 00:44:19,160 --> 00:44:20,410 PROFESSOR: Good. 749 00:44:20,410 --> 00:44:22,300 750 00:44:22,300 --> 00:44:24,260 That's correct. 751 00:44:24,260 --> 00:44:26,952 That's what's wrong with my claim. 752 00:44:26,952 --> 00:44:31,100 Let me detour around here. 753 00:44:31,100 --> 00:44:33,450 Let me get an answer to this question. 754 00:44:33,450 --> 00:44:35,170 What is the code in this case? 755 00:44:35,170 --> 00:44:39,180 It's the set of all possible sequences you can get by 756 00:44:39,180 --> 00:44:43,010 multiplying 1 plus d times the formal Laurent sequence. 757 00:44:43,010 --> 00:44:43,685 What is that? 758 00:44:43,685 --> 00:44:44,904 AUDIENCE: [INAUDIBLE]. 759 00:44:44,904 --> 00:44:45,351 PROFESSOR: What? 760 00:44:45,351 --> 00:44:46,480 AUDIENCE: Isn't it [UNINTELLIGIBLE]? 761 00:44:46,480 --> 00:44:47,840 PROFESSOR: It's just the set of all 762 00:44:47,840 --> 00:44:49,090 formal Laurent sequences. 763 00:44:49,090 --> 00:44:51,430 764 00:44:51,430 --> 00:44:57,190 Certainly for every formal Laurent sequence, I can get 765 00:44:57,190 --> 00:44:59,420 such a sequence this way. 766 00:44:59,420 --> 00:45:05,300 In particular, the code includes 1. 767 00:45:05,300 --> 00:45:10,730 What do I need as an input to get the output sequence 1? 768 00:45:10,730 --> 00:45:12,530 AUDIENCE: String of 1's. 769 00:45:12,530 --> 00:45:15,710 PROFESSOR: String of 1's, right. 770 00:45:15,710 --> 00:45:24,760 So an example, if u of D is equal to 1/1 plus d, which is 771 00:45:24,760 --> 00:45:37,910 a string of 1's, then y of D is equal to 1 plus d times u 772 00:45:37,910 --> 00:45:42,010 of D, which is 1. 773 00:45:42,010 --> 00:45:44,190 1 plus d has an inverse, and this is it. 774 00:45:44,190 --> 00:45:47,840 775 00:45:47,840 --> 00:45:54,170 So now we're coming back to Mr. Aggarwal's point. 776 00:45:54,170 --> 00:45:59,180 Suppose we put in u of D equals this sequence, all 0's 777 00:45:59,180 --> 00:46:03,510 before times 0, all 1's after time 0. 778 00:46:03,510 --> 00:46:05,530 Then where will we go? 779 00:46:05,530 --> 00:46:08,200 We'll go 1, and then we'll just stay 780 00:46:08,200 --> 00:46:11,950 in this 0 loop forever. 781 00:46:11,950 --> 00:46:15,090 Anything wrong with that? 782 00:46:15,090 --> 00:46:17,490 Is that a code word? 783 00:46:17,490 --> 00:46:21,190 That is a code word, the way we've defined the code. 784 00:46:21,190 --> 00:46:24,310 If we had defined the code so that the u of D were only 785 00:46:24,310 --> 00:46:30,220 finite input sequences, then this claim would be correct. 786 00:46:30,220 --> 00:46:32,640 For any finite input sequence, we eventually have to come 787 00:46:32,640 --> 00:46:33,930 back to the 0 state. 788 00:46:33,930 --> 00:46:36,620 789 00:46:36,620 --> 00:46:48,210 So this is true for finite inputs, not true 790 00:46:48,210 --> 00:46:49,460 for infinite inputs. 791 00:46:49,460 --> 00:46:57,315 792 00:46:57,315 --> 00:46:59,175 So this is wrong. 793 00:46:59,175 --> 00:47:06,540 The fact is d3 equals 1. 794 00:47:06,540 --> 00:47:08,790 The minimum weight of this code is 1. 795 00:47:08,790 --> 00:47:11,690 796 00:47:11,690 --> 00:47:18,220 But you see this is, first of all, it's a confusing 797 00:47:18,220 --> 00:47:22,460 situation for analytical purposes. 798 00:47:22,460 --> 00:47:26,620 Let me further indicate why it might be bad to have an 799 00:47:26,620 --> 00:47:30,060 encoder like this in general. 800 00:47:30,060 --> 00:47:44,270 The key catastrophicity, in general, will be defined as 801 00:47:44,270 --> 00:47:57,540 there are finite outputs generated by 802 00:47:57,540 --> 00:48:01,390 infinite inputs, as above. 803 00:48:01,390 --> 00:48:07,990 804 00:48:07,990 --> 00:48:18,190 Or equivalently, there are 0 loops in the 805 00:48:18,190 --> 00:48:19,440 state transition diagram. 806 00:48:19,440 --> 00:48:25,620 807 00:48:25,620 --> 00:48:28,250 So by choosing a proper input, you can just keep driving 808 00:48:28,250 --> 00:48:31,088 around a 0 loop forever. 809 00:48:31,088 --> 00:48:33,956 AUDIENCE: [INAUDIBLE]. 810 00:48:33,956 --> 00:48:35,040 PROFESSOR: Excuse me? 811 00:48:35,040 --> 00:48:36,290 AUDIENCE: [INAUDIBLE] 812 00:48:36,290 --> 00:48:38,315 813 00:48:38,315 --> 00:48:43,059 the output is becoming finite, so it's actually -- 814 00:48:43,059 --> 00:48:46,540 I'm just commenting on the whole catastrophicity. 815 00:48:46,540 --> 00:48:48,280 PROFESSOR: OK, well, I want to next tell you where 816 00:48:48,280 --> 00:48:49,720 catastrophicity comes from. 817 00:48:49,720 --> 00:48:54,450 The opposite of this property is non-catastrophicity. 818 00:48:54,450 --> 00:48:57,752 What we want is non-catastrophic encoders. 819 00:48:57,752 --> 00:49:03,880 We want encoders where, to get a finite output, you get a 820 00:49:03,880 --> 00:49:07,340 finite output only from finite inputs. 821 00:49:07,340 --> 00:49:13,330 822 00:49:13,330 --> 00:49:16,350 That's better analytically and it's better in practice. 823 00:49:16,350 --> 00:49:18,580 Here, let me draw you the practical argument. 824 00:49:18,580 --> 00:49:23,490 We have, for this particular case, u of D comes in, gets 825 00:49:23,490 --> 00:49:26,322 multiplied by 1 plus d. 826 00:49:26,322 --> 00:49:30,470 That gives us y of D, which -- 827 00:49:30,470 --> 00:49:31,940 let me just abbreviate it. 828 00:49:31,940 --> 00:49:34,780 We transmit that over a channel, 829 00:49:34,780 --> 00:49:38,470 and we get our decoder. 830 00:49:38,470 --> 00:49:42,730 Actually, decoder doesn't have much to do here, because all 831 00:49:42,730 --> 00:49:46,240 possible sequences are allowed at the output. 832 00:49:46,240 --> 00:49:49,980 So if this were a binary symmetric channel, the best 833 00:49:49,980 --> 00:49:52,590 the decoder could do would just be to put out whatever it 834 00:49:52,590 --> 00:49:56,930 sees as its guess, y-hat of D. So this 835 00:49:56,930 --> 00:49:58,180 is the decoder estimate. 836 00:49:58,180 --> 00:50:01,030 837 00:50:01,030 --> 00:50:07,140 So in any case, this can differ by 838 00:50:07,140 --> 00:50:08,740 code words from that. 839 00:50:08,740 --> 00:50:12,070 All possible code words are possible. 840 00:50:12,070 --> 00:50:19,330 And given y-hat of D, to get back to u of D, what do we 841 00:50:19,330 --> 00:50:19,830 have to do? 842 00:50:19,830 --> 00:50:23,690 We have to divide by 1/1 plus d, in effect, 843 00:50:23,690 --> 00:50:25,260 to invert this equation. 844 00:50:25,260 --> 00:50:29,710 For y of D is equal to 1 plus d times u of D, then the u of 845 00:50:29,710 --> 00:50:32,330 D that corresponds to a particular decoded code 846 00:50:32,330 --> 00:50:36,630 sequence, y-hat of D, we get by dividing by this. 847 00:50:36,630 --> 00:50:38,060 But this is infinite sequence. 848 00:50:38,060 --> 00:50:40,350 Suppose this makes just one error. 849 00:50:40,350 --> 00:50:44,420 It's possible for this to transmit all 0's, and for this 850 00:50:44,420 --> 00:50:45,670 to make just one error. 851 00:50:45,670 --> 00:50:48,270 852 00:50:48,270 --> 00:50:49,600 That's a code word. 853 00:50:49,600 --> 00:50:52,770 That's a legitimate code sequence. 854 00:50:52,770 --> 00:50:56,690 So it's something the decoder might come up with. 855 00:50:56,690 --> 00:51:01,500 If it does that, then what's this going to look like? 856 00:51:01,500 --> 00:51:06,440 This is going to look like an infinite number of 1's, 857 00:51:06,440 --> 00:51:10,110 because this is the infinite input that causes this code 858 00:51:10,110 --> 00:51:14,010 sequence with a finite number of outputs. 859 00:51:14,010 --> 00:51:17,750 So it's precisely this condition, whenever we make an 860 00:51:17,750 --> 00:51:22,250 error that corresponds to a finite output sequence, and we 861 00:51:22,250 --> 00:51:26,110 translate it back to the encoder input, that's an 862 00:51:26,110 --> 00:51:27,630 infinite encoder input. 863 00:51:27,630 --> 00:51:29,600 There's a one-to-one correspondence between inputs 864 00:51:29,600 --> 00:51:30,420 and outputs. 865 00:51:30,420 --> 00:51:33,350 So it's got to happen whenever we make that type of error. 866 00:51:33,350 --> 00:51:35,100 And this is called catastrophic error 867 00:51:35,100 --> 00:51:36,320 propagation. 868 00:51:36,320 --> 00:51:37,670 The decoder hasn't done anything bad. 869 00:51:37,670 --> 00:51:43,710 It made one error, as it's going to do once in a while. 870 00:51:43,710 --> 00:51:47,200 But the consequences are catastrophic. 871 00:51:47,200 --> 00:51:50,250 We make an infinite number of errors in the bits that we 872 00:51:50,250 --> 00:51:53,408 actually deliver to the user. 873 00:51:53,408 --> 00:51:55,540 Now, of course, what's really going to happen is that 874 00:51:55,540 --> 00:51:58,530 sometime later the decoder is going to make 875 00:51:58,530 --> 00:52:00,740 another little error. 876 00:52:00,740 --> 00:52:04,330 And at that point, this will switch state again. 877 00:52:04,330 --> 00:52:07,750 So that will terminate the error burst when the decoder 878 00:52:07,750 --> 00:52:08,740 makes another error. 879 00:52:08,740 --> 00:52:10,130 But this is completely random. 880 00:52:10,130 --> 00:52:12,330 It may take a long time for this to happen, 881 00:52:12,330 --> 00:52:14,450 and it's not good. 882 00:52:14,450 --> 00:52:16,835 So for practical reasons, we don't want catastrophicity. 883 00:52:16,835 --> 00:52:24,720 884 00:52:24,720 --> 00:52:27,990 I was going to give you another example, but in the 885 00:52:27,990 --> 00:52:32,190 interest of time, I'll just write it down. 886 00:52:32,190 --> 00:52:36,360 Here's another catastrophic example. 887 00:52:36,360 --> 00:52:42,260 Let me just do a rate 1/2 encoder so it looks more 888 00:52:42,260 --> 00:52:44,720 reasonable. 889 00:52:44,720 --> 00:52:47,250 And we'll make it look very much like the 890 00:52:47,250 --> 00:52:50,230 encoders we've had. 891 00:52:50,230 --> 00:52:55,170 Our first example looks something like this. 892 00:52:55,170 --> 00:52:56,570 1 plus d squared. 893 00:52:56,570 --> 00:52:58,340 I'll say 1 plus d. 894 00:52:58,340 --> 00:52:59,730 So it's a feet-forward encoder. 895 00:52:59,730 --> 00:53:01,755 It looks perfectly reasonable. 896 00:53:01,755 --> 00:53:07,340 897 00:53:07,340 --> 00:53:10,290 The top channel is impulse response, 1 plus d squared. 898 00:53:10,290 --> 00:53:14,030 The second output has impulse response, 1 plus d. 899 00:53:14,030 --> 00:53:16,400 If you look at the minimum weight for all finite 900 00:53:16,400 --> 00:53:18,890 sequences, it's 4, not quite as good as the other 901 00:53:18,890 --> 00:53:21,550 one which had 5. 902 00:53:21,550 --> 00:53:23,005 But is this catastrophic? 903 00:53:23,005 --> 00:53:26,430 904 00:53:26,430 --> 00:53:27,020 Yes? 905 00:53:27,020 --> 00:53:28,020 Who said yes? 906 00:53:28,020 --> 00:53:29,270 AUDIENCE: [INAUDIBLE]. 907 00:53:29,270 --> 00:53:38,390 908 00:53:38,390 --> 00:53:39,480 PROFESSOR: Great. 909 00:53:39,480 --> 00:53:46,480 So the same observation, if u of D is equal to 1/1 plus d, 910 00:53:46,480 --> 00:53:53,280 which is, again, this infinite sequence, then the output, y 911 00:53:53,280 --> 00:54:01,040 of D equals u of D, g of D, is equal to -- 912 00:54:01,040 --> 00:54:05,410 1 plus d divides both of these, so we get 1 plus d1. 913 00:54:05,410 --> 00:54:06,915 We get a finite output sequence. 914 00:54:06,915 --> 00:54:11,260 915 00:54:11,260 --> 00:54:14,880 You saw that immediately, because we know that 916 00:54:14,880 --> 00:54:18,180 polynomials are divisible by 1 plus d if and only if they 917 00:54:18,180 --> 00:54:21,105 have an even number of non-zero terms. 918 00:54:21,105 --> 00:54:24,960 919 00:54:24,960 --> 00:54:27,750 So that's a more elaborate example of where we can get 920 00:54:27,750 --> 00:54:28,970 catastrophic behavior. 921 00:54:28,970 --> 00:54:32,400 So what should we do here? 922 00:54:32,400 --> 00:54:35,080 Clearly, we should divide out the common factor from here. 923 00:54:35,080 --> 00:54:36,480 We can do that. 924 00:54:36,480 --> 00:54:41,790 If all of these polynomials have a common factor, we 925 00:54:41,790 --> 00:54:43,930 should divide it out. 926 00:54:43,930 --> 00:54:49,360 And we know that the code generated by -- if this is g 927 00:54:49,360 --> 00:54:54,940 of D, we're going to say g prime of D is equal to 1/1 928 00:54:54,940 --> 00:55:00,490 plus d times 1 plus d squared, 1 plus d. 929 00:55:00,490 --> 00:55:02,700 And that is -- we've already calculated -- 930 00:55:02,700 --> 00:55:06,350 1 plus d1. 931 00:55:06,350 --> 00:55:10,170 So by doing that, first of all, we got rid of the 932 00:55:10,170 --> 00:55:11,870 catastrophicity. 933 00:55:11,870 --> 00:55:13,880 Second of all, again, we reduced nu. 934 00:55:13,880 --> 00:55:16,690 935 00:55:16,690 --> 00:55:20,760 So this is clearly a very good thing to do. 936 00:55:20,760 --> 00:55:28,600 So more generally, going back here, if all n of D have any 937 00:55:28,600 --> 00:55:29,850 common factor -- 938 00:55:29,850 --> 00:55:35,880 939 00:55:35,880 --> 00:55:37,130 in other words, let's call -- 940 00:55:37,130 --> 00:55:40,094 941 00:55:40,094 --> 00:55:43,540 I've used d, so what'll I use? 942 00:55:43,540 --> 00:55:52,220 b of D equals the greatest common divisor of all of the n 943 00:55:52,220 --> 00:55:55,065 of D, 1 plus -- 944 00:55:55,065 --> 00:55:56,315 AUDIENCE: [INAUDIBLE]. 945 00:55:56,315 --> 00:56:00,200 946 00:56:00,200 --> 00:56:01,055 PROFESSOR: Who -- 947 00:56:01,055 --> 00:56:03,960 AUDIENCE: Do you think it could be 1? 948 00:56:03,960 --> 00:56:08,190 PROFESSOR: You're, once again, 30 seconds ahead of me. 949 00:56:08,190 --> 00:56:10,830 So yes, that's what I'm going to say. 950 00:56:10,830 --> 00:56:13,660 If they all have a common factor, then they have a GCD 951 00:56:13,660 --> 00:56:15,150 that is not equal to 1. 952 00:56:15,150 --> 00:56:18,260 That's if and only if. 953 00:56:18,260 --> 00:56:27,613 So we're going to transform n of D to 1 over b of D. We're 954 00:56:27,613 --> 00:56:31,700 going to divide out the common factor, n of D. That will be 955 00:56:31,700 --> 00:56:34,760 our n prime. 956 00:56:34,760 --> 00:56:36,870 And now what have we achieved? 957 00:56:36,870 --> 00:56:40,040 We've achieved that there is no common factor of these n 958 00:56:40,040 --> 00:56:50,630 prime of D. So no common factor, which does turn out. 959 00:56:50,630 --> 00:56:58,410 So that will mean it's non-catastrophic, and, 960 00:56:58,410 --> 00:57:08,750 furthermore, will reduce nu by whatever the degree of this 961 00:57:08,750 --> 00:57:13,735 common factor was, degree of b of D. Let me 962 00:57:13,735 --> 00:57:15,010 write degree of GCD. 963 00:57:15,010 --> 00:57:20,740 964 00:57:20,740 --> 00:57:22,320 We want them to have no common factor. 965 00:57:22,320 --> 00:57:28,810 We want the greatest common divisor to be 1. 966 00:57:28,810 --> 00:57:31,550 Another way of saying this is we want the ni of d to be 967 00:57:31,550 --> 00:57:36,950 relatively prime, the nj of d to be relatively prime. 968 00:57:36,950 --> 00:57:43,130 And if that's true, then can we prove that it's 969 00:57:43,130 --> 00:57:45,740 non-catastrophic, that if we have a finite output, that it 970 00:57:45,740 --> 00:57:49,290 must've been generated by a finite input? 971 00:57:49,290 --> 00:57:52,188 972 00:57:52,188 --> 00:57:56,102 AUDIENCE: No, because u of D times n_i of D would have to 973 00:57:56,102 --> 00:58:03,070 be a polynomial to be catastrophic, and to get a 974 00:58:03,070 --> 00:58:04,320 polynomial. 975 00:58:04,320 --> 00:58:05,916 976 00:58:05,916 --> 00:58:09,260 And u of D is rational. 977 00:58:09,260 --> 00:58:10,730 It has something in the denominator, 978 00:58:10,730 --> 00:58:12,230 because u of D is infinite. 979 00:58:12,230 --> 00:58:14,800 980 00:58:14,800 --> 00:58:17,970 That denominator should then get cancelled 981 00:58:17,970 --> 00:58:19,850 out to one of these. 982 00:58:19,850 --> 00:58:24,500 PROFESSOR: Yeah, you have the argument in your head. 983 00:58:24,500 --> 00:58:26,930 Let me leave that as an exercise for the student, 984 00:58:26,930 --> 00:58:28,910 since at least a couple of you see it. 985 00:58:28,910 --> 00:58:31,840 986 00:58:31,840 --> 00:58:34,950 The only way that you can get this behavior, if you have an 987 00:58:34,950 --> 00:58:39,620 infinite input which has in its denominator a common 988 00:58:39,620 --> 00:58:42,170 factor of all the n's. 989 00:58:42,170 --> 00:58:45,700 So if the n's have no common factor, 990 00:58:45,700 --> 00:58:46,820 then this can't happen. 991 00:58:46,820 --> 00:58:50,680 That's the outline of the argument. 992 00:58:50,680 --> 00:58:56,970 So what's our conclusion now? 993 00:58:56,970 --> 00:59:01,030 Since we have multiple encoders that generate the 994 00:59:01,030 --> 00:59:06,440 same code, we'd like to get the nicest one, in some sense, 995 00:59:06,440 --> 00:59:10,470 as our canonical encoder for a given code. 996 00:59:10,470 --> 00:59:11,540 So we have a given code. 997 00:59:11,540 --> 00:59:16,780 We can specify it by any causal 998 00:59:16,780 --> 00:59:19,630 rational transfer function. 999 00:59:19,630 --> 00:59:24,740 But then, having done that, we should clean this generator 1000 00:59:24,740 --> 00:59:26,130 n-tuple up. 1001 00:59:26,130 --> 00:59:31,540 We should multiply out by the least common multiple of all 1002 00:59:31,540 --> 00:59:36,680 the divisors to make it polynomial, feedback-free, 1003 00:59:36,680 --> 00:59:39,650 possibly reduce nu. 1004 00:59:39,650 --> 00:59:42,430 And then we should check the numerators and see if they 1005 00:59:42,430 --> 00:59:46,310 have any common factor, which could be d or it could be any 1006 00:59:46,310 --> 00:59:47,160 polynomial. 1007 00:59:47,160 --> 00:59:50,120 And whatever it is, we should divide that out. 1008 00:59:50,120 --> 00:59:54,060 And that will certainly reduce nu. 1009 00:59:54,060 --> 01:00:04,190 So at the end of the day, we have a canonical encoder, 1010 01:00:04,190 --> 01:00:07,940 which is equal to g of D times -- 1011 01:00:07,940 --> 01:00:10,930 we want to multiply by the least common multiple of the 1012 01:00:10,930 --> 01:00:13,800 denominators. 1013 01:00:13,800 --> 01:00:17,700 We want to divide by the greatest common divisor of the 1014 01:00:17,700 --> 01:00:18,950 numerators. 1015 01:00:18,950 --> 01:00:21,770 1016 01:00:21,770 --> 01:00:29,080 And this will be some n prime of D, which will be 1017 01:00:29,080 --> 01:00:31,990 polynomial. 1018 01:00:31,990 --> 01:00:34,040 It will be delay-free. 1019 01:00:34,040 --> 01:00:37,760 That means it doesn't have d as a common factor. 1020 01:00:37,760 --> 01:00:40,090 It will be non-catastrophic. 1021 01:00:40,090 --> 01:00:41,240 That means it doesn't have anything 1022 01:00:41,240 --> 01:00:44,350 else as a common factor. 1023 01:00:44,350 --> 01:00:49,890 And it will have minimal nu, for any encoder that can 1024 01:00:49,890 --> 01:00:52,250 generate that same code. 1025 01:00:52,250 --> 01:00:55,350 I haven't quite proved all those properties, but I think 1026 01:00:55,350 --> 01:00:57,310 we're well along the way. 1027 01:00:57,310 --> 01:00:58,365 So this is really -- 1028 01:00:58,365 --> 01:00:59,615 AUDIENCE: [INAUDIBLE]. 1029 01:00:59,615 --> 01:01:03,430 1030 01:01:03,430 --> 01:01:06,063 There should be at least n1 and n2. 1031 01:01:06,063 --> 01:01:07,165 [UNINTELLIGIBLE] 1032 01:01:07,165 --> 01:01:11,500 PROFESSOR: Well, if we have a rate 1/1 code, we just have 1033 01:01:11,500 --> 01:01:14,660 one of them, then what's the greatest common divisor? 1034 01:01:14,660 --> 01:01:18,620 Suppose it's n of D over d of D. The greatest common divisor 1035 01:01:18,620 --> 01:01:22,820 is n of D. The least common multiple is d of D. We get 1. 1036 01:01:22,820 --> 01:01:26,250 So going through this exercise for any rate 1/1 code, we'll 1037 01:01:26,250 --> 01:01:30,790 find that the canonical encoder is 1. 1038 01:01:30,790 --> 01:01:34,800 And that is clearly what we want for a rate 1/1 encoder, 1039 01:01:34,800 --> 01:01:38,570 because a rate 1/1 is always going to have an out. 1040 01:01:38,570 --> 01:01:41,250 The code is just going to be the universe code of all the 1041 01:01:41,250 --> 01:01:43,770 possible formal Laurent sequences. 1042 01:01:43,770 --> 01:01:47,470 So we get down to the right encoder for that code, not 1043 01:01:47,470 --> 01:01:48,720 some stupid encoder. 1044 01:01:48,720 --> 01:01:50,880 1045 01:01:50,880 --> 01:01:55,690 And in a similar way, going through this process, we come 1046 01:01:55,690 --> 01:01:56,590 up with the right encoder. 1047 01:01:56,590 --> 01:01:59,230 Is this process unique? 1048 01:01:59,230 --> 01:02:04,200 Is there only one encoder we could come up with? 1049 01:02:04,200 --> 01:02:07,570 1050 01:02:07,570 --> 01:02:11,360 Think about it a little, and you could convince yourself 1051 01:02:11,360 --> 01:02:15,960 there's only encoder that you can get from doing this. 1052 01:02:15,960 --> 01:02:19,220 1053 01:02:19,220 --> 01:02:20,620 This is over F2. 1054 01:02:20,620 --> 01:02:25,000 Over a larger field, it's unique up to units again, up 1055 01:02:25,000 --> 01:02:28,990 to a non-zero scalar multiple, which of course you can define 1056 01:02:28,990 --> 01:02:34,390 to be 1 and somehow make this unique. 1057 01:02:34,390 --> 01:02:41,495 So it's basically a unique canonical encoder that has all 1058 01:02:41,495 --> 01:02:42,550 of these properties. 1059 01:02:42,550 --> 01:02:44,880 You get it in this way. 1060 01:02:44,880 --> 01:02:48,400 So this is what we're always going to use. 1061 01:02:48,400 --> 01:02:55,135 For instance, for our original encoder, 1 plus -- 1062 01:02:55,135 --> 01:02:55,850 what was it? -- 1063 01:02:55,850 --> 01:02:59,800 1 plus d squared, 1 plus d plus d squared. 1064 01:02:59,800 --> 01:03:01,500 Is that already in canonical form? 1065 01:03:01,500 --> 01:03:07,470 1066 01:03:07,470 --> 01:03:09,280 This is irreducible. 1067 01:03:09,280 --> 01:03:13,990 This is divisible by 1 plus D, so these are relatively prime. 1068 01:03:13,990 --> 01:03:15,510 It's feed-forward. 1069 01:03:15,510 --> 01:03:19,330 It doesn't have any denominator terms, and it's 1070 01:03:19,330 --> 01:03:20,230 delay-free. 1071 01:03:20,230 --> 01:03:25,500 So it satisfies all of these, and clearly you can't 1072 01:03:25,500 --> 01:03:26,400 manipulate it. 1073 01:03:26,400 --> 01:03:28,580 The only ways you're allowed to manipulate it are by 1074 01:03:28,580 --> 01:03:35,530 multiplying by a of D over b of D. And it's clear that if 1075 01:03:35,530 --> 01:03:38,350 you have a non-trivial numerator or denominator, the 1076 01:03:38,350 --> 01:03:40,290 numerator will make it catastrophic, the denominator 1077 01:03:40,290 --> 01:03:44,800 will make it to have feedback. 1078 01:03:44,800 --> 01:03:46,340 Now, as I was saying, there's really 1079 01:03:46,340 --> 01:03:47,940 nothing wrong with feedback. 1080 01:03:47,940 --> 01:03:51,560 And so some people prefer -- 1081 01:03:51,560 --> 01:03:54,160 the one thing that this doesn't have, in general, is 1082 01:03:54,160 --> 01:03:57,030 it's not systematic. 1083 01:03:57,030 --> 01:03:59,990 That means the input stream is not one of the output streams. 1084 01:03:59,990 --> 01:04:06,060 1085 01:04:06,060 --> 01:04:10,910 So given a canonical encoder like this, can we always make 1086 01:04:10,910 --> 01:04:12,160 it systematic? 1087 01:04:12,160 --> 01:04:15,450 1088 01:04:15,450 --> 01:04:20,910 Yeah, we just divide by any of these polynomials. 1089 01:04:20,910 --> 01:04:25,450 So here's an equivalent systematic encoder. 1090 01:04:25,450 --> 01:04:31,420 1091 01:04:31,420 --> 01:04:35,380 For instance, if we divide both of these by 1 plus D 1092 01:04:35,380 --> 01:04:40,310 squared, we get 1 plus D plus D squared, 1093 01:04:40,310 --> 01:04:41,590 over 1 plus d squared. 1094 01:04:41,590 --> 01:04:45,580 1095 01:04:45,580 --> 01:04:48,390 This now is not polynomial. 1096 01:04:48,390 --> 01:04:49,810 It is delay-free. 1097 01:04:49,810 --> 01:04:54,190 1098 01:04:54,190 --> 01:04:55,440 It's non-catastrophic. 1099 01:04:55,440 --> 01:04:58,570 1100 01:04:58,570 --> 01:05:01,210 There's no 1 over something that we can put in to get a 1101 01:05:01,210 --> 01:05:03,140 finite thing out. 1102 01:05:03,140 --> 01:05:07,560 It turns out it's still minimal nu. 1103 01:05:07,560 --> 01:05:10,090 We know how to realize this with two memory elements now. 1104 01:05:10,090 --> 01:05:13,240 1105 01:05:13,240 --> 01:05:17,580 And in general, if you're not going to introduce a 1106 01:05:17,580 --> 01:05:20,870 denominator term that has a greater degree than the 1107 01:05:20,870 --> 01:05:23,260 maximum degree of the numerator terms, so it's still 1108 01:05:23,260 --> 01:05:25,460 realizable with minimal nu. 1109 01:05:25,460 --> 01:05:33,380 And so now it's systematic, but now it's not 1110 01:05:33,380 --> 01:05:34,630 feedback-free. 1111 01:05:34,630 --> 01:05:41,270 1112 01:05:41,270 --> 01:05:44,280 So I consider this one certainly the nicest. 1113 01:05:44,280 --> 01:05:50,060 The canonical feedback-free encoder is the nicest one for 1114 01:05:50,060 --> 01:05:53,370 analytical purposes, for instance, for trying to find 1115 01:05:53,370 --> 01:05:56,510 minumum-weight finite code words. 1116 01:05:56,510 --> 01:05:59,670 Because of the finite property, if we're looking for 1117 01:05:59,670 --> 01:06:01,790 the non-catastrophic property, if we're looking for 1118 01:06:01,790 --> 01:06:03,850 minimum-weight code words, we only have to 1119 01:06:03,850 --> 01:06:05,720 look at finite inputs. 1120 01:06:05,720 --> 01:06:08,990 We can now use the kind of analysis method that we use 1121 01:06:08,990 --> 01:06:12,930 that says you always have to come back to the 0 state, 1122 01:06:12,930 --> 01:06:19,830 because only finite inputs can produce finite outputs here. 1123 01:06:19,830 --> 01:06:22,970 This also has that property. 1124 01:06:22,970 --> 01:06:30,580 And people tended not to use these for a long time, but it 1125 01:06:30,580 --> 01:06:35,400 was founded that in turbo codes, you want to have this, 1126 01:06:35,400 --> 01:06:38,460 one of the generators be infinite. 1127 01:06:38,460 --> 01:06:41,300 And it was also nice to have one of them be systematic, so 1128 01:06:41,300 --> 01:06:44,030 that led to a revival of interest in systematic 1129 01:06:44,030 --> 01:06:45,090 convolutional encoders. 1130 01:06:45,090 --> 01:06:47,150 And this, again, it's a unique form. 1131 01:06:47,150 --> 01:06:50,770 If you say the first one has to be the systematic one, then 1132 01:06:50,770 --> 01:06:53,710 there's a unique equivalent systematic encoder that 1133 01:06:53,710 --> 01:06:55,330 generates any code. 1134 01:06:55,330 --> 01:06:58,190 So it's in alternative canonical form. 1135 01:06:58,190 --> 01:06:59,440 Take your pick. 1136 01:06:59,440 --> 01:07:03,480 1137 01:07:03,480 --> 01:07:04,390 Yeah? 1138 01:07:04,390 --> 01:07:07,120 AUDIENCE: What's systematic? 1139 01:07:07,120 --> 01:07:08,870 PROFESSOR: What's systematic? 1140 01:07:08,870 --> 01:07:12,630 Systematic means that the input that's appear unchanged 1141 01:07:12,630 --> 01:07:15,560 as a subset of the output bits. 1142 01:07:15,560 --> 01:07:19,720 For convolutional codes, it means that one of the output 1143 01:07:19,720 --> 01:07:23,400 sequences, if you have a rate 1/n encoder, one of the output 1144 01:07:23,400 --> 01:07:25,600 sequences is simply equal to the input sequence. 1145 01:07:25,600 --> 01:07:26,900 In other words, one of the transfer 1146 01:07:26,900 --> 01:07:29,908 functions is equal to 1. 1147 01:07:29,908 --> 01:07:31,158 AUDIENCE: [INAUDIBLE]. 1148 01:07:31,158 --> 01:07:34,450 1149 01:07:34,450 --> 01:07:36,570 PROFESSOR: Yes, very good. 1150 01:07:36,570 --> 01:07:38,998 Excellent comment. 1151 01:07:38,998 --> 01:07:44,890 Because now, if you have a finite output sequence, in 1152 01:07:44,890 --> 01:07:48,110 particular you can just read off the input sequence, the 1153 01:07:48,110 --> 01:07:51,640 information sequence, from this first term, and if the 1154 01:07:51,640 --> 01:07:53,880 whole thing was finite, it's finite. 1155 01:07:53,880 --> 01:07:59,360 So systematic directly ensures non-catastrophicity. 1156 01:07:59,360 --> 01:08:00,630 Excellent, excellent comment. 1157 01:08:00,630 --> 01:08:05,410 1158 01:08:05,410 --> 01:08:08,370 Which you might try to prove by the more elaborate 1159 01:08:08,370 --> 01:08:11,410 techniques that we had. 1160 01:08:11,410 --> 01:08:16,590 So that gets us pretty much through the algebra that I 1161 01:08:16,590 --> 01:08:19,920 wanted to do. 1162 01:08:19,920 --> 01:08:23,069 Now I want to -- 1163 01:08:23,069 --> 01:08:26,890 OK, good. 1164 01:08:26,890 --> 01:08:29,649 Now let's go more to the finite state picture. 1165 01:08:29,649 --> 01:08:33,689 1166 01:08:33,689 --> 01:08:51,160 And our objective here is mostly going to be to get to 1167 01:08:51,160 --> 01:08:54,220 Viterbi decoding algorithm. 1168 01:08:54,220 --> 01:08:57,550 But along the way, we'll see that we can use something like 1169 01:08:57,550 --> 01:09:00,090 the Viterbi algorithm to compute minimum distances, 1170 01:09:00,090 --> 01:09:04,349 too, once we have a finite state picture to the code. 1171 01:09:04,349 --> 01:09:07,620 1172 01:09:07,620 --> 01:09:17,770 Again, take our example one, where g of D is 1 plus D 1173 01:09:17,770 --> 01:09:21,270 squared, 1 plus D plus D squared. 1174 01:09:21,270 --> 01:09:27,569 We have a state transition diagram, 1175 01:09:27,569 --> 01:09:34,469 which looks like this. 1176 01:09:34,469 --> 01:09:43,890 1177 01:09:43,890 --> 01:09:48,074 And I won't bother to label it. 1178 01:09:48,074 --> 01:09:52,060 1179 01:09:52,060 --> 01:09:55,350 And that's a complete description of the encoder 1180 01:09:55,350 --> 01:10:00,260 operation, if I put labels of inputs and outputs on all 1181 01:10:00,260 --> 01:10:01,695 these states. 1182 01:10:01,695 --> 01:10:08,110 So 0 slash 0,0, so forth, 1 slash 1, 1. 1183 01:10:08,110 --> 01:10:12,400 Just to draw the impulse response, 0, 0, 1, 1184 01:10:12,400 --> 01:10:15,380 and 0 slash 1, 1. 1185 01:10:15,380 --> 01:10:18,110 There's the basic impulse response going 1186 01:10:18,110 --> 01:10:19,360 around, like that. 1187 01:10:19,360 --> 01:10:22,940 1188 01:10:22,940 --> 01:10:27,900 Trellis diagram is a very redundant 1189 01:10:27,900 --> 01:10:29,390 picture of the same thing. 1190 01:10:29,390 --> 01:10:35,070 1191 01:10:35,070 --> 01:10:38,600 We can start out in the 0 state that we like. 1192 01:10:38,600 --> 01:10:44,950 Let's say we start off in the 0 state at some time k, as we 1193 01:10:44,950 --> 01:10:45,530 always are. 1194 01:10:45,530 --> 01:10:47,010 We just don't know what k is. 1195 01:10:47,010 --> 01:10:50,260 1196 01:10:50,260 --> 01:10:52,600 Then let's spread the state transition 1197 01:10:52,600 --> 01:10:54,070 diagram out in time. 1198 01:10:54,070 --> 01:10:57,610 Let's draw all the states again at time k plus 1. 1199 01:10:57,610 --> 01:11:00,380 1200 01:11:00,380 --> 01:11:02,490 Actually, there are only two it can get to, 1201 01:11:02,490 --> 01:11:03,950 at time k plus 1. 1202 01:11:03,950 --> 01:11:09,870 So we can either stay in this state or we can go down here 1203 01:11:09,870 --> 01:11:15,450 to this state, at the next unit of time. 1204 01:11:15,450 --> 01:11:19,780 I'm just going to keep drawing all of the possible state 1205 01:11:19,780 --> 01:11:22,740 trajectories or paths. 1206 01:11:22,740 --> 01:11:27,080 At time 2, I can reach all possible states. 1207 01:11:27,080 --> 01:11:32,730 0, 0, 1, 0, 0, 1, 1, 1. 1208 01:11:32,730 --> 01:11:38,240 Here again, I already know what these are. 1209 01:11:38,240 --> 01:11:43,741 From here, I can get 1, 0, 2, 0. 1210 01:11:43,741 --> 01:11:46,660 It goes with a 0, 1 out. 1211 01:11:46,660 --> 01:11:51,170 So 1 goes with a 1, 0. 1212 01:11:51,170 --> 01:11:59,380 And k plus 3, I now have all possible transitions. 1213 01:11:59,380 --> 01:12:02,120 It's going to look like this. 1214 01:12:02,120 --> 01:12:04,110 Where can I go from 0, 1? 1215 01:12:04,110 --> 01:12:07,970 I can go back to here, or I could go to here. 1216 01:12:07,970 --> 01:12:09,950 And I could label these. 1217 01:12:09,950 --> 01:12:11,625 I should label these. 1218 01:12:11,625 --> 01:12:12,620 But I won't. 1219 01:12:12,620 --> 01:12:15,770 Here, I can go to these two. 1220 01:12:15,770 --> 01:12:18,210 There are eight possible state transitions. 1221 01:12:18,210 --> 01:12:20,440 k plus 4. 1222 01:12:20,440 --> 01:12:22,470 It's completely repetitive, since it's a 1223 01:12:22,470 --> 01:12:24,940 time-invariant system. 1224 01:12:24,940 --> 01:12:27,210 I just keep going like this. 1225 01:12:27,210 --> 01:12:34,610 1226 01:12:34,610 --> 01:12:36,720 And why have I gone to all this trouble? 1227 01:12:36,720 --> 01:12:40,555 This clearly contains the same information as this diagram, 1228 01:12:40,555 --> 01:12:42,340 but it's just spread out in time. 1229 01:12:42,340 --> 01:12:45,200 1230 01:12:45,200 --> 01:12:54,210 The basic reason for doing it is that now there is a unique 1231 01:12:54,210 --> 01:12:58,040 trellis path corresponding to every code word that can start 1232 01:12:58,040 --> 01:12:59,380 at time k or later. 1233 01:12:59,380 --> 01:13:02,010 1234 01:13:02,010 --> 01:13:06,840 So for instance, if I just have an impulse at time k and 1235 01:13:06,840 --> 01:13:12,450 nothing else, then the unique trellis path is this. 1236 01:13:12,450 --> 01:13:16,700 It starts at 0, goes through two non-zero states, comes 1237 01:13:16,700 --> 01:13:21,710 back to 0, 0, and then stays in 0, 0 forever more. 1238 01:13:21,710 --> 01:13:25,860 1239 01:13:25,860 --> 01:13:27,351 AUDIENCE: [INAUDIBLE]. 1240 01:13:27,351 --> 01:13:30,890 PROFESSOR: I've just taken an arbitrary starting time, k. 1241 01:13:30,890 --> 01:13:33,110 After a while, I'll just look at it -- 1242 01:13:33,110 --> 01:13:34,100 well, it's entrained. 1243 01:13:34,100 --> 01:13:36,710 This is kind of the steady state version of the trellis. 1244 01:13:36,710 --> 01:13:40,880 I've included a little starting part here. 1245 01:13:40,880 --> 01:13:45,670 And if I terminated the trellis, then I would also 1246 01:13:45,670 --> 01:13:46,360 have an ending time. 1247 01:13:46,360 --> 01:13:49,460 We'll talk about that. 1248 01:13:49,460 --> 01:13:52,250 So at this point, I just want you to see what the trellis 1249 01:13:52,250 --> 01:13:53,090 diagram is. 1250 01:13:53,090 --> 01:13:55,740 It's basically just an unrolling of the state 1251 01:13:55,740 --> 01:13:58,130 transition diagram out in time. 1252 01:13:58,130 --> 01:14:00,310 And it allows me to associate -- 1253 01:14:00,310 --> 01:14:02,580 there's a one-to-one correspondence now between 1254 01:14:02,580 --> 01:14:07,180 code words that start at time k or later, and trellis paths. 1255 01:14:07,180 --> 01:14:11,510 So every one corresponds to a unique, distinct 1256 01:14:11,510 --> 01:14:13,170 path through the code. 1257 01:14:13,170 --> 01:14:16,170 That's what we're going to use in decoding. 1258 01:14:16,170 --> 01:14:20,980 Each of these paths represents one possible decision that the 1259 01:14:20,980 --> 01:14:24,160 decoder could do about what was actually set. 1260 01:14:24,160 --> 01:14:29,230 The decoder is actually going to try to find the best of 1261 01:14:29,230 --> 01:14:32,290 these paths, in some sense, the one that's closest to the 1262 01:14:32,290 --> 01:14:34,810 received sequence, in the Hamming distance or Euclidean 1263 01:14:34,810 --> 01:14:39,360 distance, or likelihood sense. 1264 01:14:39,360 --> 01:14:42,810 Let's pause for a second, and see how this could be used to 1265 01:14:42,810 --> 01:14:48,890 compute the minimum distance of the code. 1266 01:14:48,890 --> 01:14:55,810 Let's assume that I have a non-catastrophic encoder. 1267 01:14:55,810 --> 01:14:58,900 Then I know the finite sequences are going to be 1268 01:14:58,900 --> 01:15:03,510 those that start in the 0 state, go through some 1269 01:15:03,510 --> 01:15:08,170 trajectory through the state transition diagram, and then 1270 01:15:08,170 --> 01:15:11,620 ultimately come back to the 0 state. 1271 01:15:11,620 --> 01:15:15,040 If I have canonical encoder, I agreed what I'm 1272 01:15:15,040 --> 01:15:17,270 going to use now. 1273 01:15:17,270 --> 01:15:21,380 So one way of computing the minimum distance would just be 1274 01:15:21,380 --> 01:15:28,780 to perform a search through here, and try to find the 1275 01:15:28,780 --> 01:15:34,496 minimum detour, the minimum weight detour that starts in 1276 01:15:34,496 --> 01:15:36,990 the 0 state, eventually gets back to the 0 state. 1277 01:15:36,990 --> 01:15:40,080 It accumulates Hamming distance along the way. 1278 01:15:40,080 --> 01:15:41,770 And that is the Hamming distance of 1279 01:15:41,770 --> 01:15:45,480 some valid code sequence. 1280 01:15:45,480 --> 01:15:49,490 So here, it's not very tough. 1281 01:15:49,490 --> 01:15:52,220 And I've already gone through an argument. 1282 01:15:52,220 --> 01:15:55,030 If you didn't know, you'd say, OK, here's the 1283 01:15:55,030 --> 01:15:56,090 first one to look at. 1284 01:15:56,090 --> 01:16:01,740 This is the only one that gets back in three time units. 1285 01:16:01,740 --> 01:16:06,230 Let's look for the finite path that gets back to the 0 state 1286 01:16:06,230 --> 01:16:07,630 in four time units. 1287 01:16:07,630 --> 01:16:09,560 Again, there's only one of them. 1288 01:16:09,560 --> 01:16:13,235 It looks like that, and it turns out it has weight 6. 1289 01:16:13,235 --> 01:16:15,900 1290 01:16:15,900 --> 01:16:20,190 So this is, again, it always ends up with a 1:1 when it 1291 01:16:20,190 --> 01:16:22,280 merges back in here. 1292 01:16:22,280 --> 01:16:26,210 And this, I think, is 0, 1 or something like that. 1293 01:16:26,210 --> 01:16:30,950 The only 0, 0 path in here is this one. 1294 01:16:30,950 --> 01:16:34,510 But you can easily see the 0, 0 path doesn't form a loop. 1295 01:16:34,510 --> 01:16:38,160 You can't proceed down 0, 0 forever. 1296 01:16:38,160 --> 01:16:41,280 So I go through here, and I've already got four units of 1297 01:16:41,280 --> 01:16:42,290 distance up to here. 1298 01:16:42,290 --> 01:16:44,440 In fact, I need to follow. 1299 01:16:44,440 --> 01:16:48,900 Next time I explore out here, 1, 1, 0, I've already got up 1300 01:16:48,900 --> 01:16:51,140 to four units of distance. 1301 01:16:51,140 --> 01:16:54,320 Now I know I'm always going to have two at the end. 1302 01:16:54,320 --> 01:16:59,120 So any time I get to four or more, I can stop. 1303 01:16:59,120 --> 01:17:01,830 And by that argument, I'm already done when 1304 01:17:01,830 --> 01:17:03,410 I get to this one. 1305 01:17:03,410 --> 01:17:06,350 Or if I didn't want to use that, I'd just explore -- 1306 01:17:06,350 --> 01:17:09,320 I already know that there's one of weight 5, the impulse 1307 01:17:09,320 --> 01:17:13,480 response, so I'd explore all the possibilities out until 1308 01:17:13,480 --> 01:17:16,450 they accumulated at least weight 5, and assure myself 1309 01:17:16,450 --> 01:17:19,130 that there was no way of getting back here with weight 1310 01:17:19,130 --> 01:17:20,600 less than 5. 1311 01:17:20,600 --> 01:17:24,030 And that would be a very systematic way of evaluating 1312 01:17:24,030 --> 01:17:26,020 the minimum distance to the code. 1313 01:17:26,020 --> 01:17:29,481 You can see you could do that for any generators. 1314 01:17:29,481 --> 01:17:31,020 You with me? 1315 01:17:31,020 --> 01:17:37,620 Just explore this little graph, picking up weight as 1316 01:17:37,620 --> 01:17:38,870 you go along. 1317 01:17:38,870 --> 01:17:42,480 1318 01:17:42,480 --> 01:17:45,210 That's basically the way the Viterbi algorithm goes as 1319 01:17:45,210 --> 01:17:54,940 well, except what we do is we have some received pair at 1320 01:17:54,940 --> 01:18:08,730 time k, r1 k, r2 k, r1 k plus 1, r2 k plus 1. 1321 01:18:08,730 --> 01:18:11,920 We get two received symbols at every time, whatever channel 1322 01:18:11,920 --> 01:18:14,300 we're going over. 1323 01:18:14,300 --> 01:18:19,020 Assuming that the channel is memory-less, I get a some kind 1324 01:18:19,020 --> 01:18:21,870 of distance or weight or likelihood weight at each 1325 01:18:21,870 --> 01:18:26,720 time, and maximum likelihood sequence decoding amounts to 1326 01:18:26,720 --> 01:18:30,830 finding the sequence that's closest, the code sequence 1327 01:18:30,830 --> 01:18:33,880 that's closest in Hamming distance or Euclidean distance 1328 01:18:33,880 --> 01:18:36,350 or likelihood distance to the transmitted sequence. 1329 01:18:36,350 --> 01:18:39,800 1330 01:18:39,800 --> 01:18:43,180 So I can simply put a metric on each of these branches 1331 01:18:43,180 --> 01:18:45,650 corresponding to what this was. 1332 01:18:45,650 --> 01:18:47,590 Now, if it was a binary symmetric channel and I 1333 01:18:47,590 --> 01:18:51,310 received 0, 0, then I'd have 0 weight here, but weight 2 1334 01:18:51,310 --> 01:18:53,660 here, in terms of Hamming distance from 1335 01:18:53,660 --> 01:18:56,090 the received sequence. 1336 01:18:56,090 --> 01:18:58,470 And similarly, as I go along, I'd have another set of 1337 01:18:58,470 --> 01:18:59,130 metrics here. 1338 01:18:59,130 --> 01:19:02,020 If I received 1, 1, then this one would have weight 2, this 1339 01:19:02,020 --> 01:19:05,160 one would be good, no distance from the received sequence. 1340 01:19:05,160 --> 01:19:06,640 Each of these would have distance 1 from 1341 01:19:06,640 --> 01:19:08,440 the received sequence. 1342 01:19:08,440 --> 01:19:14,680 So I get some kind of cost for every path in here. 1343 01:19:14,680 --> 01:19:16,830 And then the decoding algorithm is simply a matter 1344 01:19:16,830 --> 01:19:20,560 of finding the minimum cost path. 1345 01:19:20,560 --> 01:19:23,380 You could all do that. 1346 01:19:23,380 --> 01:19:29,165 We just had a celebration for Andy Viterbi out in USC, where 1347 01:19:29,165 --> 01:19:33,720 he's given them $50 million, so they were very happy, and 1348 01:19:33,720 --> 01:19:35,060 had a great celebration. 1349 01:19:35,060 --> 01:19:37,970 And the thing he's best known for is the Viterbi algorithm. 1350 01:19:37,970 --> 01:19:41,180 But what everybody knows is that, once you reduce the 1351 01:19:41,180 --> 01:19:43,410 problem to this point, anybody could have come up with the 1352 01:19:43,410 --> 01:19:45,260 Viterbi algorithm. 1353 01:19:45,260 --> 01:19:47,960 The Viterbi algorithm is just a systematic way for trying to 1354 01:19:47,960 --> 01:19:53,620 find the lowest-cost path as you go through a trellis. 1355 01:19:53,620 --> 01:19:56,570 And if you know dynamic programming and it's obvious 1356 01:19:56,570 --> 01:20:02,650 how to do it, or even if you don't, the next idea -- 1357 01:20:02,650 --> 01:20:03,900 do we have a minute? 1358 01:20:03,900 --> 01:20:06,500 1359 01:20:06,500 --> 01:20:09,220 There's only one idea in the Viterbi algorithm, which is, 1360 01:20:09,220 --> 01:20:12,280 when you get to this point, you can already make a 1361 01:20:12,280 --> 01:20:15,040 decision about what the best path is to get to each of 1362 01:20:15,040 --> 01:20:18,070 these states. 1363 01:20:18,070 --> 01:20:22,130 If the closest path over the first three intervals is this 1364 01:20:22,130 --> 01:20:28,040 one, not this one, say, then you can forget about this path 1365 01:20:28,040 --> 01:20:30,270 because it's never going to be the first part of the ultimate 1366 01:20:30,270 --> 01:20:33,370 closest path, because we're simply adding up independent 1367 01:20:33,370 --> 01:20:34,620 cost, independent increments. 1368 01:20:34,620 --> 01:20:37,230 1369 01:20:37,230 --> 01:20:41,870 So you can make a subdecision at each of these states, what 1370 01:20:41,870 --> 01:20:47,090 the best path is up to that state, the closest path. 1371 01:20:47,090 --> 01:20:49,290 And you only need to remember that. 1372 01:20:49,290 --> 01:20:52,000 That's called a survivor. 1373 01:20:52,000 --> 01:20:56,030 And this was basically, Viterbi was the first one to 1374 01:20:56,030 --> 01:20:59,010 put down this algorithm with the survivor. 1375 01:20:59,010 --> 01:21:01,340 You can make interim decisions. 1376 01:21:01,340 --> 01:21:03,250 You can only keep the survivor. 1377 01:21:03,250 --> 01:21:06,290 Then all you have to do is extend the survivor's one unit 1378 01:21:06,290 --> 01:21:07,280 of time out here. 1379 01:21:07,280 --> 01:21:10,130 Again, you have to add the new metric. 1380 01:21:10,130 --> 01:21:11,840 You have to compare the metrics to see 1381 01:21:11,840 --> 01:21:12,590 which one is better. 1382 01:21:12,590 --> 01:21:15,450 You select the survivor, and once again, you've only got 1383 01:21:15,450 --> 01:21:17,630 four survivors going forward. 1384 01:21:17,630 --> 01:21:20,500 So you get an iterative recursive algorithm that just 1385 01:21:20,500 --> 01:21:26,830 proceeds forward one unit of time at a time, and keeps 1386 01:21:26,830 --> 01:21:29,590 finding the four best survivors, or in general, the 1387 01:21:29,590 --> 01:21:34,630 2 to the nu best survivors at time k plus 3, k plus 4, k 1388 01:21:34,630 --> 01:21:37,450 plus 5, ad infinitum. 1389 01:21:37,450 --> 01:21:40,960 And that's the Viterbi algorithm. 1390 01:21:40,960 --> 01:21:43,480 So once you've drawn this trellis picture, it's very 1391 01:21:43,480 --> 01:21:47,030 clear how you should decode, and you get a very sufficient 1392 01:21:47,030 --> 01:21:49,400 decoding algorithm. 1393 01:21:49,400 --> 01:21:51,490 We'll come back next time. 1394 01:21:51,490 --> 01:21:53,320 I'll do that a little bit more carefully. 1395 01:21:53,320 --> 01:21:56,040 I'll talk about terminated codes. 1396 01:21:56,040 --> 01:21:58,590 I'll talk about how it works when the code isn't 1397 01:21:58,590 --> 01:22:01,880 terminated, and I'll talk about performance analysis. 1398 01:22:01,880 --> 01:22:04,780 But we're actually pretty close to the end of chapter 1399 01:22:04,780 --> 01:22:06,030 nine at this point. 1400 01:22:06,030 --> 01:22:14,996