The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor The journey of a thousand miles begins with a single step.
Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. Decisions, decisions. Wait a minute, are you still looking for cars on Carvana? Yeah, decisions, decisions. When I use Carvana, I found the exact car I was looking for in minutes. Bought it on the spot. Electric or full diesel. Decisions. Come on, you've been at it for weeks. Just buy it already. You're right, crossover it is. Decisions, decide it. Whether you know exactly what you want or like to take your time, buy your car the convenient way with Carvana. And so this is the solution. There's 20 copies. So take up solution to homework number two on your way out. Homework number three is on the web and it has to do with a tomography lab experiment. And Cindy, did you, did you put the files in or residue it? There's an additional file, Tom's dot DB, that I couldn't figure out where she got that from. You might want to go talk to her at the end of class to figure out what it's all about. Okay. When is the homework due? Oh right, it's next week. Yeah, do next Friday, the 17th. I hear a lot of sighs. What's the problem? Well, there's no midterm, there's no finals. Well, then that's going to be very mild. So just so that I have an idea of the show of hands, how many people took five hours or less to do this homework? Oh wow, excellent. How many written five and 10? Wow, how many more than 10? How many just never raised our hands? Like, let's do zero to five, just about everybody. Okay, okay, very good. So that was an easy homework. Actually, I have to warn you this next homework is harder, so I'll just tell you that ahead of time. That's right, I think if you, from a game theory point of view, if you collaborated with each other, you would know what the optimal strategy would be, is that you just collude and, and, okay, we're all ready to go. So what I talked about last time was, yeah, this is a copy of last time's lecture was the notion of difference equations in particular linear constant coefficient difference equations, and, and how they relate to linear shifting variance systems. So I think the best picture we have from last time is, is this diagram right here, if you can just, thank you. So you start with a, with a linear constant coefficient difference equation, which corresponds to an IOR filter with rational transfer functions, and we show that we need to have initial condition or boundary condition in order to make it correspond to a system, period. Otherwise, it wouldn't be even a system because unique input doesn't result in a unique output. You need to have that initial condition to be zero for that system to be linear, and then furthermore for, for the system to be shifting variance, you have to make sure the initial condition is chosen in accordance with the input. So as I shift the input and, and, and put different kinds of input into the system, in order to make the overall system to be shifting variance, I have to pick the boundary condition or the initial condition of the difference equation to match that input. So in particular, if I have, for example, this kind of a system with, with an input, which is a delta at times n equals five, then in order to make this a causal linear time invariant system, then I have to make the initial, to begin with, this difference equation corresponds to a causal implementation, which is y of n takes on the value of a times y of n minus 1 plus b of x of n. Or it could have an anti-causal interpretation, which is y of n minus 1 takes on y, it's something times y of n plus something else times x of n. So the causal implementation, let me just write that for completeness. So for this causal implementation to correspond to an LTI system, if the input is non-zero up until the time time is n equals five, I have to pick the initial condition to be output at time four equals zero. If this was delta of n minus 100, then the initial condition would be y of 99 equals zero. It has to be zero here to make it linear. It has to be at picked at the right time to make this shift invariance. Otherwise, you can go through, if you make the initial condition, let's say for this system, make y of minus 1 equals zero, you can come up with a solution, but you will find that if you shift the input, the output doesn't shift. And the way to do that is go through solving the entire rigamel n of this difference equation. I don't want to do it because it wastes a lot of time because this is not a course and a difference equation, but you can see if I pick the wrong initial condition, and if I shifted the input, the output wouldn't be the shifted version of the input, which is a condition for shifting invariance. And furthermore, for the anti-causal implementation of that, which is written by here, again, I have to match the initial condition to match the input. In particular, if the input is, again, delta of n minus 5, which is x of n looks like this, it has a kink at n equals 5, then the initial condition has to be chosen at y at times 5 equals zero. And the reason for that is shown here, because you want to be able to compute the, you want to be, let me just draw it here, because once y of 5 is equal to zero, then I can plug in and compute y of 4 using y of 5, y of 3 using y of 4, y of 2 using y of 1, y of 2 using y of 3, etc. I can go backward in time. Does everybody see this point? Okay, and you can also generalize that even further. You can say that if the system was, let's say we're talking about causal system, but what if it was the second order difference equation? In other words, y of n was taking on the value of something times y of n minus 1, plus something else times y of n minus 2. What would be the, and we want it to be causal, what would be the boundary conditions? First of all, because it's a second order difference equation, we have to have two boundary conditions, right? And what would the two boundary conditions be? Well, it would be, depending, let's say the input what n equals 5 would be y of 4 equals 0 and y of 3 equals 0, because you need to go two time steps back in order to compute a particular output point, right? But what I want you to walk away from, I mean, this is really not a course in different equations, but what, what, the reason I did all of these things is, in order to generalize this to 2d, there's a simpler method, and that applies to 1d and 2d. So, let me, let me explain what I mean by that. So, in the, so generalizing, so boundary condition for, two-dimensional, different linear, constant, coefficient, difference equations. This is kind of the goal for today's lecture, or at least part of today's lecture. So, what we talked about last time was that if you have a two-dimensional linear constant coefficient difference equation, then we talked about the notion of recursive computability. The, the output mask has to have a wedge support for the, for the thing to be, for, for the system to be recursively computable. Now, what we wanted to talk about is, in addition to that, we have to pick the right boundary condition in order to do that. And what, how do we pick that boundary condition? And the answer, so another, how to choose the boundary conditions for the, for 2d LCCDEs. And the strategy we're going to take is generalize the way we compute the boundary condition in a one-dimensional system into 2d. So, approach is really generalize the approach in 1d. Well, you might say, well, what do you mean by that? Well, let me, again, do an example. Suppose that I have a . . . Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus, save 10% on Amazon brands, like our new brand Amazon Saver. 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work, day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So, whether you're gearing up for a new project, or looking to add some tried and true work wear to your collection. Remember, the Dickies has been standing the test of time for a reason. Their work wear isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code WorkWear20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. A realization of a one-dimensional difference in equation Y of n is just Y of n minus 1 plus X of n. And in general, how do we pick the boundary condition for this? Well, so this is a causal system. So, if I have an X of n, an input to this system that becomes non-zero at time and not, then we all know that the boundary condition would be the output at time and not minus 1 has got to be zero, okay? So, to obtain LTI system, because of the discussions we had in the last time's lecture, the boundary condition should be Y of n not minus 1 has got to be equal to zero. And again, we're adjusting where the output is zero to the time that input becomes non-zero. And one way of another way of arriving at this conclusion is to take the following steps is compute the region of support of output of the output given the difference equation. And then, number two, set the boundary condition and call the region of support of the output to be R sub Y. R stands for region of support. Y is the output because output is denoted by Y. And then set the boundary condition to be equal to zero outside of R sub Y, okay? And how do I do one and what do I mean by step one, step two? Well, here's the way I compute the R sub Y, the region of support of the output is to start with the region of support of the input and the region of support of the impulse response. And then from that, deduce what the region of support of the output is. So making this a little bit more detailed, if you can roll up just a little bit. So more detailed version of that two-step procedure is to, so this is detailed. You start with region of support of the input, which we call R sub X. A given the fact that we've nailed down what the computational procedure is or what the realization is, we're no longer dealing with just the difference equation. We know which implementation or which realization of that we're working in. So given the computational procedure for our difference equation, we know we can now compute the impulse response, H of N, and then from that, we can compute R sub H, which is the region of support for the impulse response, okay? And then using step one and two, use R sub X and R sub H to compute R sub Y, which is the region of support of the output. And then the boundary condition has to be equal to zero for all N that are not in R sub Y, okay? So this might sound like a hell of a lot of steps to go through for just one-dimensional difference equation. But indeed, if you think about it, that's exactly what we do in 1D. And that's exactly what we have to do when we go to 2D. The simple arguments of causal anti-causal therefore just said Y of N not minus one equal to zero, that all of that, that intuition doesn't carry straight forward. The best way to think about it is to say, what is a bigger, more generalized methodology for 1D? This is it. And now translate this methodology straight on to 2D. But before I translate it to 2D, I want to convince you that indeed it works in 1D. So let's just do that through this famous example that we have, which is Y of N takes on the value Y of N minus one plus X of N. So let's go through that. Can you zoom up a little bit please? So actually, let's go through that example. Y of N takes on the value Y of N minus one plus X of N. So this is a causal system. And you're given X of N is delta of N. So what I need to compute is R of Y. In other words, what is the region of support for the output? Well, it's not that hard to figure that out. If X of N is delta of N, then Y of zero takes on the value Y of minus one plus delta of zero. And then Y of one takes on the value Y of zero plus zero. Because input that time one is equals to zero. Y of two takes on the value Y of one. Y of three takes on the value Y of two. On and on. And so based on this, it seems like the only time isn't. And also, if you look at Y of minus one, it takes on the value Y of minus two plus zero, etc. So if I look at these things, the only time anything is non-zero and has a shot at being non-zero is right here at Y of zero. Because that's the only point where we got delta of zero, that's non-zero. So definitely, if I were to write down the region of support for the output, Y of N, it's definitely going to be non-zero at index zero right here. It's going to be something else. And once this is non-zero, once Y of zero is non-zero, it makes automatically Y of one, non-zero, Y of two. These are all some non-zero values. And these guys, on the other hand, have no chance of getting any input contribution. So Y of N is going to have a region of support that looks like this. So this is R sub Y. This is the region of support of Y of N. And therefore, the boundary condition has got to be equal to zero for all these negative indices, minus one, minus two, etc. So this is the boundary condition that makes this computation procedure to correspond to an LTI system. Alternatively, we can even go one step beyond that and do the thing in a more detailed way. You can compute H of N, what's the impulse response for a system like this? Well, you can do that by writing down the Z transform. So, it's an alliter and another way of looking at the same thing. What's H of N? Well, you can just take the Z transform, you get Y of Z, is equal to Z inverse Y of Z plus X of Z. And you can write down H of Z, then, is Y of Z over X of Z as one over one minus Z inverse. That means H of N is just U of N. So you can say that this is R sub H, the region of support of impulse response. And if this is the region of supportive impulse response and the input is X of N, is delta of N. It's just not zero here. Then, involving these two things in your head, you can easily see that the region of support of R sub Y would be here. So this is R sub Y. And therefore, the boundary condition is going to be zero right in this region. Is this clear? So, it's quite easy and it's quite clear what happens in 1D. And now, we're just going to extend this procedure right on exactly that same steps in 2D, to 2D. So, let's just do that. So what happens in 2D? Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus, save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Uplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So, whether you're gearing up for a new project or looking to add some tried and true workware to your collection, remember that Dickies has been standing the test of time for a reason. Their workware isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code Workware20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. Well, it's exact same steps. In other words, given the computational procedure, determine R of H, given input, determine R of X, and then using R of X and R of H, determine R of Y, and then boundary conditions equal to zero for all N1 and N2s, not in R sub Y. Those are the same kind of steps that we take. So, let's kind of define that for, let's just go through an example and see if we can take these steps one after another if you can roll up. So, half of the other pages shown. Thank you. So, let's just do an example here. Suppose I have a different equation, suppose I have sort of a computational procedure, which is as follows. Y of N1 and N2 takes on the value minus two Y of N1 minus one comma N2 minus three Y of N1 comma N2 minus one, minus four Y of N1 minus one comma N2 minus one plus X of N1 and N2. So, right off the bat, let's draw. It turns out to do these steps in 2D, one of the things that helps you a lot to do this intuitively is to write down the output mask or plot the output mask and the input mask. So, in this case, the output mask is given by, to compute Y at times N1 and 2, I need N1 minus one comma N2, which is this guy, N1 comma N2 minus one, which is this guy, and then N1 minus one and 2 minus one, which is this guy and the input mask, obviously, is this. And you can go through kind of multiple steps and multiple arguments, but you can show if the output mask is like this and the input mask like this, then the region of support for R sub H for the impulse response, you can plug this into the difference equation and convince yourself that R sub H would look something like this as a function of N1 and N2, it will be non-zero for this whole region and the first quadrant. In general, the way you do it is you start with this and you kind of flip it over and I'll show you a few other examples. So, by the time we're done with the lecture, by the time you do the next homework, which is do the 24th, you develop this intuition, but the trick is very simple. I'll give you a few other examples to see how you can quickly go from an output mask to R sub H, but here's the kind of intuition and you can develop, you can prove yourself that this is the R sub H for this by kicking the system with the delta and computing the outputs and convincing yourself these are the only non-zero values that you get. So, if the output mask is like this, then the way you do it is you flip it over this way and this becomes the R sub H for the region of support for the impulse. Okay, so here's R sub H and now suppose that I kick this system with an input which looks like this. This is x of n1 and n2, so it has this kind of a region of support for simplicity. I've just made it be just a 3 by 3 input and again without doing the actual convolution the same way as in one dimension you can do the convolution in your head just to know what the region of support for the output is. You can convolve this in your head with this R sub H and in order to figure out that R sub Y, the region of support for the output is going to be is one index to the left because this is one index to the left is going to be all these points and I'm running out of patience as you can see, so it's this thing. So this is R sub Y, okay, and therefore the boundary condition is going to be out, so this is the boundary condition, it's going to be zero for all these values of n1 and n2 and given that now we can, we can now apply, given this fact this is the boundary condition and given the fact that this output mask is recursively computable, we can now compute using these boundary conditions, we can compute the output points in a recursively computable way. I want you to see this output mask, so given that this output mask has a wedge support, this angle is less than 180 degrees and given that now we have this beautiful boundary condition, you can compute the output points one after the other, you can do it row by row or you can do it column by column and you can even do it in a zig-zag manner, there's many different ways of doing the output computations, one after the other. Is this at these steps clear? Let me do one more example and in order to avoid writing down so many things, I'm just going to use Jay Lin's pictures and Jay Lin's books, just so that we can move a little bit faster so I can move on to discrete Fourier transform, so what I'm going to cover is the example on page 98, 99 and 100, so page 98 to 100 of Lin's book. So here's what we've got there, we've got this difference equation, if you can zoom in please, thank you. Okay and maybe you can focus just a little bit, oh much better. Okay I think it's focused enough, so here's our system function, so h of z1 and z2 is the ratio between y of z1 and z2 output and the input z transform and you cross multiply y's by x's, you take it, manage the shift property in order to come up with the difference equation and now this difference equation can have one, two, three, four, four different implementations and those are shown here in equation, you don't all adjust, you just stay where you are, the camera person. Well if you both move then we both miss each other, so so this is this is one realization, we would just take this point into the left hand side as shown here and this is a second computational procedure, this is the third one and this is the fourth one and I think we already went over that just a little bit last time and we already know for example how from this computational procedure to come up with any one of them to come up with input output mask here you have n1 minus one and two and one and two minus one and one and two minus two and x value, so here we go, this is the output mask for the first realization and the input mask for it, this is for the second, this is for the third and this is for the fourth and of these four, let's go over and collectively decide which ones correspond to a recursively computable systems and which ones don't, so does this one do correspond to recursively, yeah it certainly does. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh, shop prime exclusive deals and save up to 50% on weekly grocery favorites, plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Uplenty and more, come back for new deals rotating every week, don't miss out on savings, shop prime exclusive deals at Amazon Fresh, select varieties. We wear our work day by day, stitch by stitch, at Dickies we believe work is what we're made of, so whether you're gearing up for a new project or looking to add some tried and true work wear to your collection, remember that Dickies has been standing the test of time for a reason. Their work wear isn't just about looking good, it's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code Workwear20 at checkout to save 20% on your purchase, it's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. If I draw a point here and a drop a point here, the angle here is 90 degrees, so this is recursively computable. And while we're added, what do you think the R sub H is, the region of support of the impulse response of a system corresponding to this realization? Well, this also has a 90 degree thing, so it's going to have an R sub H that's, if I extend this this way and this this way, it's going to be an R sub H that's in this region, which is shown right here. Flip it over. Once for the first time you have to go through the actual difference, it's pretty painful, but you have to plug in delta of N into the difference equation, yeah, it's do it by hand. And Jay Lim goes through the pain of explaining all of that, but you only have to convince yourself once and then from then on you'll see, oh, that's the rule you have to kind of apply, okay. Then you move on to here. This is the second, this is the computational procedure for the, I mean, sorry, this is the input optimist, but the second computational procedure. And now what you do is I have to draw a line connecting this to that and extend it here and extend this line here and the region of support would be there. Let me draw, it makes sense for me to draw that and explain it a little bit better. So if the input output mask has a region, if the output mask has this region of support, because I don't want to write on the book, I'll write it here. So what we do is you connect this guy to this guy and then extend it here and connect this guy to this guy and extend it here. I usually, actually, this is the first time that I discuss this trick, if you will, in the lecture. Usually I let the students discover it in the homework or by just reading the book, but I think it's better to be upfront and not hide anything from you. So then this would be the region of, this is with the R sub H, where does it, there's a second point there, there's a point yeah, there's a point here, there's a point here. And then, so this is an, this angle essentially is the same as this angle. And again, this is shown, the region of support for this R sub H corresponding to this system is shown here. And finally, for the third realization, we have a, again, a wage support, this angle is definitely less than 180 degrees. And now R sub H would be straight line this way, straight line this way, so it'll be a wedge region here. And sure enough, if you, if you go through it, you'll see that it's a wedge here, except that it doesn't include zero, zero. And finally, when we come to the, to the fourth system, which is here, and what can we say about the, the support of this output mask or recursive compatibility of this? This is not recursively computable, because if I start from the center point here and draw a line here and another line down here to encompass all the points, I end up getting 180 degrees. So because this is not a recursive retrieval system, we, there's, there's no boundary, essentially there's no boundary condition that will ever make this thing work. That's, that's what the implications are. Make it work, I mean, to compute the outputs in a recursive way one after the other, for a system like this, you might have to solve implicitly a big linear system of equations in order to figure out how, how, what the answer, what the output is going to be. But certainly you can't compute it one, one after the other. Okay, any questions or comments? I want to talk about one more thing on this material or chapter in, in, and then move on to the next topic, which is discrete Fourier transforms and, and ways of computing it. So, suppose that I've, I've, I've, I've, I've been given, as an example, I've been given a, a given difference equation using the same ideas that, that was talked about, and, and I wanted to come up with a particular realization such that the impulse response is third quadrant. Okay, so I'm given this difference equation, y of n1 and n2 is y of n1 minus 1 comma n2 minus 1 plus x of n1 and n2. This is a difference equation, and I'm, I'm, I'm being asked to find the computational procedure so that the h of n here is third quadrant. Okay, and based on what we've learned or what we've discussed, how would, how would you go about doing solving a problem like that? Well, there's two different, there's no more than two different possibilities here, right? No more than two computational procedure, either this takes on the value of that or you bring this to the left hand side and this takes on the values of those other ones. So, and then what you can do is you can write down the input output mask for both of those and then based on that, figure out what the reason of support for R sub h is and that only one of them is third quadrant. So, so, so there's only two computational procedure. Number one is just y of n1 and n2 takes on y of n1 minus 1 comma n2 minus 1 plus x. In this case, the output mask as a function of n1 and n2 looks like this and if you go through a bit of a calculation, what you find is R sub h as a function of n1 and n2 would have this kind of region of support. Non-zero along this at this point. So, this is a first quadrant support. That's definitely not the procedure we want. Now, on the other hand, if you pick the other computational procedure where this one takes on the value of these other two guys. So, we get y of n1 comma n2 taking on the value of y of n1 plus 1 comma n2 plus 1 minus x of n1 plus 1 comma n2 plus 1, okay. Then what happens is the output mask as a function of n1 and n2 would look like something like this and if you compute the R sub h, the region of support of h, you find that it's the flip version of that. It'll be non-zero for these points. So, this is indeed a third quadrant impulse response. So, essentially, by picking the wide computational procedure, you can make very similar to the 1D case. You can have different regions of support and different impulse responses. So, to wrap all of these things up, the picture, the mental picture I want to leave you with, is this clear? Is this discussion clear? Yeah, was there a question? I see some puzzled faces. Like Sam, it seems that you're a little bit puzzled. Oh my god, okay. Next time I should come into class, I pop up a pill of riddle in. I don't know if you guys heard about the news about the stimulants. Did you hear about that? Yeah, apparently in college campuses, people use stimulants. Like when in my generation, when I was at Caltech, the thing to do is to have caffeine pills. You pop one in. It's like 100 pounds more effective than the mountain. It keeps you up all night. But the stimulant things, apparently, is even better from what I hear on the radio. But some kids pretend like they have learning disability or ADHD or whatever, ADHD. I can't remember the name of it. They go to the doctors. They've looked up the symptoms on the web or somewhere. They pretend they have it. They get the prescription. They use some of it themselves and then they start selling it to the rest of the students, especially at the time of midterms and finals. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands. Like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So, whether you're gearing up for a new project or looking to add some tried and true work wear to your collection, remember that Dickies has been standing the test of time for a reason. Their work wear isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code Workwear20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. So, anyway, just thought I would pass that on. I just come to the class and as I hand in the homework, you know, here's a pill. What? This is not a business class. This is a signal processing class. Okay, so you're tied. But does everybody follow what I'm doing here? Is it pretty clear? Okay. So, the final picture I want to leave you with is that in general, the H of Z plus region of convergence uniquely specifies H of N, an impulse response, and the two do these two things uniquely specify a computational procedure. So, if you know this, you can go here. If you know this, you can go there. So, there's a two-way arrow from all of these things, all right? So, a difference equation by itself is not enough to specify H or H of Z. The same way as H of Z by itself is not enough to determine uniquely what H of N is and what the computational procedure is. So, there's an ambiguity. Without regional convergence, H of Z has a certain amount of ambiguity. The same thing, a difference equation without knowing what computational procedure you have has a certain amount of ambiguity. Neither difference equation, nor H of Z by itself, is enough to uniquely specify what the system is. Okay? So, and you can clearly show yourself in 1D and 2D in any dimension that a given H of Z with different regions of convergences would correspond to different computational procedures and therefore different H of N's. So, for example, H of Z plus ROC1 could correspond to H1 of N and furthermore, could correspond to computational procedure 1. And then H of Z plus a different region of convergence could result in a different impulse response and a different computational procedure. So, unless you nail what the region of convergence is, you haven't really, or unless you've nailed what particular realization of a difference equation you want to use, you can't really tell what's going on. You can't really tell what the system is. You don't know what the impulse response is. Okay, that's the end of discussion on whatever chapter it is in Lim's book, I think it's chapter 3 or so. We're not covering stability or any of that kind of stuff. So, next, I'm going to move on to DFT because DFT is the one transform that's used in practice and that's kind of the next chapter. We won't go over all the pieces of chapter 4 in Jay Lim's book either, but just kind of a cursory look at the important parts of it. So, we're going to talk about two-dimensional DFT. But before we do that, I want to just write down the expressions of all the transforms so that you can place DFT in the right context in your brain so you know where it stands with relates to all the other transforms that are happening. So, to begin with, you start with a discrete time. And I'm only worried about discrete time signals. And I do them one D just and then we'll move on to the two-dimensional version of it. So, there's a transform called DFT. That's the thing that we talked about at the beginning of the class. How do I reconstruct from the phase of the DFT? How do I reconstruct from magnitude of DFT, et cetera? And this is a function of, this is written DFT is written by X of omega, which is a continuous variable. And this is discrete. Summation over n of X of n e to the minus j omega n. Then there is a Z transform. And this omega guy is a continuous variable and it's real. X of Z, here Z, is a continuous variable but it's complex. And it's written as summation of X of n z to the minus n. And now, so what's just off the off the bat? What is the problem with DFT and Z transform? They're what? What's bad? Yeah, that's exactly right. I mean, you can't compute in a computer, you can't compute things. You can compute samples of X of omega and you can compute samples of X of Z. So first of all, we all know X of omega is X of Z computed on a unit circle, right? So, those two are related. But the problem, both of them is that these are continuous variables. So instead, we come up with DFT, discrete Fourier transform, which is X of k, summation over X of n e to the minus j 2 pi nk over n. And now, this is an integer and it takes on discrete values. So for the first time, we have a transform that takes on an array of numbers and spits out another array of numbers. And from this, you can get back X of n as you wish. And for those of you who have forgotten some of your DSP, there's a thing called FFT. It stands for fast Fourier transform, we talk about that. And FFT is just a method. It's just an algorithm to compute DFT. You can compute DFT five different ways. You can do it in a direct way, or z transform way, or FFT way, or what's it called? There was a famous technique that was popular in the mid 80s. It had not the prime number one. It never took off, even though mathematically, you could show it had lower number. Anyway, it's just a method to compute DFT. Just as a little joke, once I ran into my advisor, Oppenheimer at the dining hall at MIT with his son, Jason, who at the time was maybe five years old. And somewhere in the middle of the lunch, I asked Jason, I said, Jason, what's your dad do? He said, he does FFTs. That's a five-year-old picture of what, you know, what his dad, well, apparently, I mean, that must be the one thing you talked about at home. It's FFTs. Actually, I never asked that question from my son when he was five. If you ask my son now, I said, what is your mom and dad? Oh, they're just nerds, categorically. Okay, so just pictorially, this is the z transform. X of omega, so X of z is defined in this z plane, real part of z, and imaginary part of z, and an X of omega. So it's a two-dimensional function, complex value that you can think of, it's sticking out of this plane. It has a value everywhere in this plane. And if you took it, I always called it like a birthday knife and cut like a cake. You cut a circle around it, the values of the cream that you get on top of the knife as a position of the knife moving around or the heights variation as you move around. That's X of omega. And finally, X of k is just x of omega evaluated at uniformly spaced values of along the unit circle. So it would be, so for an 8-point transformer, it would be here, here, here, here, here, here, and here. So x of omega is equally spaced samples on the unit circle. Okay, so the key question that comes up in 2D is, well in 1D, we have this fantastic algorithm FFT that computes the Fourier transform signals very fast, and in 2D, you can, there's two ways of computing two-dimensional FFTs, either as a series of one-dimensional FFTs, which is called row column decomposition. And it's not that different from when we talked about convolving a separable signal with a, sorry, a signal with an impulse response that's separable, or you can, you can apply it genuinely two-dimensional FFTs for your transform algorithm, which does the decomposition fundamentally in 2D. And I'll talk about both of those really briefly, and you'll see that the computational cost for those are comparable, although the genuine two-dimensional FFT has a slightly lower computation cost, but more complex to implement. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work, day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So, whether you're gearing up for a new project, or looking to add some tried and true work wear to your collection, remember that Dickies has been standing the test of time for a reason. Their work wear isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code WorkWear20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. Basically, this part of our course has to do with computational complexity of computing to the DFT. So, what is 2D DFT? You compute DFT of X of n1 and n2, or you define it as double summation of n1 and 2 X of n1 and 2 e to the minus j 2 pi n1 k1 over capital n1, and then e to the minus j 2 pi n2 k2 over capital n2. Where we're assuming this signal is n1 by n2 points. And this is for k1 and k2 between, sorry, k1 in between this range and k2 is smaller than n2 and 0, but it's 0 otherwise. So, DFT is not defined for outside of these values of K's. And then the inverse DFT is X of n1 and n2 can be obtained back from X of k1 and k2 by the following summation 1 over n1 and 2 of X of k1 and k2 e to the j 2 pi n2. So, e to the j 2 pi k1 n1 over n1 e to the j 2 pi k2 n2 over n2. And this is for, again, n1 between capital n1 and 0, 0 and n2 between capital n2 and 0, and it's 0 otherwise. It's a lot of summation for nothing. I mean, it's not for nothing. It's just the same thing as 1D, but just extended to 2D. So, when we were dealing with one-dimensional signal processing, if you wanted to convolve two signals, let's say you have an input signal X of n that has M non-zero points. And you have an impulse response H of n that has n non-zero points. And why was DFT useful? Because you can use DFT to do convolution, right? So, DFT relates to linear time aberrant system, at least, not the IIR ones, but the FIR ones, because you can compute the DFT of impulse response. You can compute the DFT of the input, multiply them together, you get the DFT of the output, then you can take inverse DFT of the output to get a Y of k, the product of those two things to get the output. Everybody familiar with that? Right? Seen it all in signals and systems, right? So, let me kind of quickly flash this by, so use of DFT in convolutions. Okay, so if I have X of n going into LTI systems, Y of n coming out, and this guy is n point, and this guy is n point, then output is going to have n plus n minus one point. Then, as long as we choose P larger than n plus n minus one, then we can apply the following steps to compute the output from the input. Number one, compute the P point DFT of input, call that X of k. And what do we mean by a P point DFT of input? If the input has only n non-zero values, how do I compute its P point DFT, pat it with a bunch of zeros until it's P points, right? Number two, compute the P point DFT of H, you get H of k, number three, compute H of k, X of k times H of k to get Y of k, and this is DFT of the output Y of n. And then it's therefore number four, this is using the convolution property of DFT, take the inverse DFT of Y of k to get Y of n. So again, this is just a reminder. And so of what's going on, so if I pick P to be incredibly larger than n plus n minus one, that's n plus n minus one is a hundred, and I pick P to be two hundred. Is this method going to get messed up? Yes, how many people think yes? How many people think no? Correct, it won't get messed up because the hundred of the points will be zero. Okay, in real life, when you want to do FFTs and stuff, there's certain advantages to be gained by using powers of two, and therefore, many times, even though n plus n minus one might be just a random number like, you know, hundred, and you pick P to be two, let's say, 128, just so that you can have a fast method of computing the output. Why do you want P greater than n plus n minus one, can it be equal? Oh, greater than or equal, thank you. Very good, very good. And the spare of the moment, yeah, it can be exactly equal. So in two-dimension, you know, the same thing holds true. So if I have an m by n, so let's just write this down. If I have an m by m important, n by n impulse response, it's the output is n plus n minus one times n plus n minus one, and so I can apply the same kind of things to compute the output. So all of this applies in 2D. So the only caveat is how do we compute the 2D DFT in two dimensions? Can roll up just a tiny bit. Okay, so the question is how to compute 2D DFT. And there's basically three ways of doing it. And again, remember, this is the expression of our 2D DFT, right? How do we compute that? Well, there's the direct method, just like in 1D. And the direct method works by, for every value of the output, x of k1 and k2, this is x of k1 and k2. You multiply this by these exponentials and add them up, that's called the direct method. And then the second method is row column decomposition. And the third method is vector radix, which is really, this is the true equivalent of FFT, but in two dimensions. Why do I care about computing two-dimensional DFTs? Why do I care about computational complexity of it? And what are some factors that determine computational complexity of anything? Yeah, let me ask that question. When you design an algorithm, what are some factors that determine computational complexity of things? How do you measure? You have approach A and approach B, and you want to say this one costs more in terms of, and you're implementing it. Yeah, go ahead. Good, so one most immediately, so here's the factors that affect speed. The find that immediately comes to mind is number of arithmetic operations. That could be multiplies, adds, or whatever. And for the most part, and traditionally when we teach signal processing, we've kind of been emphasizing that. What other thing in practice comes into play? Exactly. So there's two memory requirements, right Alan? There's the usage of memory as the program goes along, but also the size of the code itself and the complexity of the code. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work, day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So, whether you're gearing up for a new project, or looking to add some tried and true work wear to your collection, remember that Dickies has been standing the test of time for a reason. Their work wear isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code WorkWear20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century. Code. Is it 5,000 lines of C program to do this matrix inversion, or is it 10 lines, or 100 lines? So, complexity of the program itself. So, memory or the space for the executable. And a lot of times that's referred to as footprint, right? And the other one is the memory, and it has a name. The computer architecture people use a different name from that. It's called the delete memory. Anybody we have from computer architecture in this class? No. Okay, so memory usage has a word for it, as the program moves on. So, let me give you an example. So, why is it the size of the footprint is important? That's the size of the executable. You've written your C code, you've compiled it, you do Ls minus L on your Unix machine to see how many bytes does that executable take. And why is that an important measure? Because, let's say, for people who have cell phones, for example, if you're downloading an application over the air from Verizon, you don't want to wait half an hour just for the executable to get to your phone. You want it to get there in five seconds. It's, you know, we're living in a society of instantaneous gratification. You can't wait. Can't wait ten minutes. You know, you want to play that video game now on your cell phone and can't wait too long. So, and almost all these complexity arguments had gone away for a long time until the cell phone and wireless industry came now. It's important again. How about usage of memory? Again, the cell phone has a limited memory. And what would be some applications where usage of memory is prohibitive? Video. If I'm doing motion estimation, I have to store two entire frames in order to search for the best motion. And then, even at the decoder, I have to, when I'm doing predictive coding, I need to know what frame n minus 1 is because I'd receive the difference between n and n minus 1. I decode that difference after it's been half an encoded, et cetera. So, I have to add it to frame n minus 1 to reconstruct frame n. That means I have to have two whole, I have to have storage for two entire frames. That's a lot. If your, if your pixel size is, you know, 200 by 200 and add it up, it's 24 bits of color and that n minus 1 frame, also you have to store it in the, not in the compressed format, but in the uncompressed format, which is hell, almost. So, that's the amount of usage the memory that the program uses as it goes on. And those are important as well. Most recently, one of my grad students, Pierre Garig, is working on sparse basing and learnings for, for over-complete or sparse representation of signals. And so, essentially, the problem is you have a dictionary of functions and you want to come up with the, the dictionary is over-complete and you want to find a linear combination of the dictionary that approximates the signal best, but you want that linear combination to have as few coefficients as possible. So, there's, there's norm, norm one minimization, norm two minimization. This is L0, norm zero minimization. You want to have as few coefficients in your representation of your signal given a dictionary. It turns out to solve that problem accurate or properly, you need to do matrix inversions. But if you have an image that's, let's say, a thousand by thousand, the matrix you have to invert is a million by a million. Kind of like the reconstruction from magnitude thing, right? If your image was n by n, the matrix you have to invert was n squared by n squared. So, in that, so when you look up the matrix inversion literature, what happens is that up to a certain size of matrices, it turns out, if you got a 10,000 by 10,000 matrix, on today's past machines, like a single processing, you can do it in 10 minutes. But the complex, the operation count goes up as n cubed. So, if I, if the size of the matrix becomes double, the, the computational code becomes 8 times bigger. But the size of the matrix, but, but if I double the size of my image, if, if I have a 100 by 100 image, make it 200 by 200. That size of my image went up by 4, and therefore my computation goes up by 64, okay? So, so instead of 10 minutes, it takes 640 minutes, which is 10 hours, that's the whole day. So, you can parallelize things. But anyway, the reason I got into this discussion is that this, this is a computational complexity that goes up. But, as it turns out, when the size of the matrix goes up, the IO becomes a killer as well. Just, just getting the, when you, when the computer is doing calculations, the, the numbers get stored at three different levels. There's the cache, then there's the memory, then there's the, the disk, and then there's the, that's right. So, there's, there's memory and disk. And so, you don't want your, your machine to get into a paging mode, where it doesn't have enough space and cache, therefore it puts it on the disk. And so, you, you spend a lot of time reading back and forth from the disk, that already slows you down. That might become the dominant factor in how long the whole thing takes. Not how many comp, how much competition. On how much competition, we have a good handle on a lot of algorithms. Or of n, or of n squared, or of n cubed, we can calculate that easily. But, for a given architecture, for a given machine, if you exceed cache limitations or memory limitations of it, you can get into factors like paging. And those, we don't really have a good handle on. Those become much more computer architecture fine tuning kind of issues, and you have to make sure that they don't, that they don't kill you. Right? Okay, how about the third factor that we, as signal processes, we always ignore, in terms of what affects complexity? It's, it's just the language, you write the code. So, how many of you have program in Java? Good, how many people have program video algorithms in Java? None. Because it's so damn slow, it just tests your patience. If you implement anything in Java, it's ten times slower than if you implement it on C, in C, for example. Right? And what are some techniques, if you, if you're just using computers, what are some techniques to speed up beyond C, C implementation? Assembly, that's it. And a lot of software engineers and industry spend a lifetime, I optimize this and I optimize that. What does that mean, is you, you figure out, like for example, Intel, when they release their chips, they have an MMX instruction sets. That is pseudo-assembly in order to help developers who are doing video applications implement their stuff faster. So it does, I don't know, vector for vector populations, inner products fast, it does matrix for vector multiplication fast. It does block matching for motion estimation fast. And how do you get that speed up, you're not writing it in C, they have already optimized it at the assembly level. And then they've provided API for you to call those, so that the time consuming operations get done very fast. And by the way, for chip companies like Intel who, who keep doubling the speed of their chips, but they're kind of running out of applications as to how do we now sell the new product we got. Okay, now we got four gigahertz chips, but how do we convince the corporations that bought the two gigahertz machines last year, now they have to upgrade. And so how do you think they convince them? What application is ideally suited for that? Video. Because it's a lot of data, it's a lot of computation. In particular video encoding, because that's video encoding and decoding and most times are very asymmetric. You're encoding takes hundreds of times more than decoding. And so like I would visit Intel, I don't know, four years ago and, you know, say, "Oh, well, professor, what should be something we've done?" And they take you to everyone and say, "No, we can real time encode a, I don't know, 500 by 100 video, pixel video, real time on our latest, you know, can't remember. The latest, Xeon, da, da, da, da, da, 2.4 gigahertz." And I bet you, if I visit them today, they're not going to show that same demo. What would they say? But first of all, we're not going to encode real time on a single Intel chip, an HDTV signal, right? So the, I don't know how we got sidetracked into that, but anyway, the speed of the thing also depends on the language and the platform, and the thing is run on. And for years and years, the single processing people would go to conferences and, you know, they would come up with tweaks on FFTs instead of n log n. Now I have n log n minus three, and then the next guy would go, "Oh, now I have n log n minus three and a half." And, you know, everybody would clap for them. And once my, you know, my office made, what's his name, Webster Dove, who's, by the way, his wife Monica Dove was the assistant to Oppenheim. He stood up and said, "Look, I can speed up the whole thing by factor of ten if I just coded in assembly." And everybody looked at him like he was crazy, but it was right. If you don't code in C or if you don't call it in Java and use a different programming language, you can, of course, get huge amounts of speedups. Okay, so given this picture of the different methods of computing, if you can roll up just a little bit of DFT, let's just now stare at this and try to come up with direct method arithmetic count. So this is it. This is the direct method equation. So for each k1, so for each value of k1 and k2, how many multiplications do I have to do and how many additions do I have to do? This goes from 0 to n1 minus 1 and this goes from 0 to n2 minus 1. But for the sake of argument, we're assuming n1 is equal to n2 is equal to n. Well, there's n squared values of this that we have to go through. So roughly speaking, we need n squared moths and n squared ads. And how many k1s and k2s are there? How many values of k1 and k2 is it? Well, it's n by n, so there's n squared of those. So putting these two things together, roughly speaking, we need n to the 4 moths and n to the 4 ads. So in many practical situations, it's very important to know how your complexity goes up as n, where n could be the size of your image or the size of your matrix, et cetera. So the next method we're going to talk about is row column, does everybody follow that? The next column is row column decomposition. I'll start on a new page. And what row column decomposition does is the best trade-off between computational complexity and ease of implementation. The code for row column decomposition is very small compared to the true FFT. What you'll see in maybe at the end of today's lecture or next time's lecture is that if you do true FFT with the true decomposition, you have a slightly lower number of operations, number of mathematical operations. But implementing that takes longer and more complex. That's exactly why I can't remember the name of the algorithm that was invented in the '80s. It was a guy at IBM and it was provably a lot fewer operations on FFT, but it was so complex to implement that nobody ever used it. I have to remember that. Oh, Winograd. That's it. Winograd transformed. He came up with that approach. Okay. So how does the row column decomposition work? Well, you rewrite this equation that you have up here as follows. You can write x of k1 and k2 as summation of n2 from 0 to n minus 1 and n1 from 0 to n minus 1 of x of n1 and n2 e to the minus j 2 pi n1 k1 over n over n times the other exponentials, e to the minus j 2 pi n2 k2 over n. So we call this whole entity here F of k1, n2. Why? Because we're summing over n1, so the n1 gets out. All that's left is k1 and this n2, because we have to do the summation with respect to that. So basically pictorially what you can think of is you start with an n1, n2 array of numbers. That's a 5x5 array of numbers just for the sake of this example. And this is our x signal. And this is our f signal. It's going to be a function of k1 and n2. And what does it say? It says for a fixed value of n2, that means for a fixed row, I'm going to do a one-dimensional DFT of the row. This is nothing but a one-dimensional DFT. So I'll take the DFT of this guy and I plug it into here. And I take the DFT of this guy and I plug it into here. And I take the one-dimensional DFT of this guy and I put it into here. So how many one-dimensional DFTs do I have to do? That's right. So I have to do n1-dimensional DFTs of rows. And each one-dimensional DFT is n points, right? And then after I'm done with that, I have now f of k1 and k2 stare at this equation. Now k1 is fixed and I'm taking a one-dimensional DFT of, now k1 is fixed, and I'm taking the one-dimensional DFT for the fixed k1 with respect to n2. So now I'm going to redraw this picture just for the sake of completeness. Can you roll up, please? So this is now my f of k1 and 2. So it's 5 by 5. Now I take one-dimensional DFT along the column. And now my k1 is fixed and after I take the one-dimensional DFT with respect to n2, I get k2. So this gets transformed into five points here and this column gets transformed into these five points. This column gets into this, this five points, et cetera. So in this process, how much work do I have to do? Again, I have to do n1-dimensional DFTs and each one DFT was n point long. And how do I do this so I have to add up this amount of work to this amount of work? And how do I do my one-dimensional DFTs? FFT is just one line of code. And we're assuming that for our FFT, so 1D DFTs, we apply FFT and we assume that for our FFT, can you roll up, please? We can do n log n type ideas. So we can do n log base to n maults and n over 2 log to n adds. And then combining adding up everything, this guy, this guy, and this other guy that we had up here, adding everything up, you can figure out that you end up with all of, so roll column decomposition ends up having all of n squared log to n operations, which is a lot lower than n to the fourth. Operation is meaning either malt or add. It's actually n squared for malts and then n squared over 2 for adds. I'm going to stop here, so conclusion, this is a lot lower than the direct method. The direct method, by the way, has the shortest amount of code. It's just a do loop, two do loops, but this thing is a little bit more work, but not too bad. We managed to decrease the complexity quite a bit. So I'll see you all on Wednesday. Hey Amazon Prime members. Why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver. 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. We wear our work, day by day, stitch by stitch. At Dickies, we believe work is what we're made of. So whether you're gearing up for a new project, or looking to add some tried and true workware to your collection, remember that Dickies has been standing the test of time for a reason. Their workware isn't just about looking good. It's about performing under pressure and lasting through the toughest jobs. Head over to Dickies.com and use the promo code Workware20 at checkout to save 20% on your purchase. It's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century.