The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor take one step each day
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. Bada. Bada Boom. Sold. Huh? Just sold my car on Carvana. Dropping it off and getting paid today. Already? What? You still haven't sold yours? You told me about it months ago. I just... Is the offer good? Oh, it offers great. Don't have another car yet? I could trade it in for this car I love. Come on! What are we waiting for? Ah, you're right. Let's go! Whether you're looking to sell your car right now, or just whenever feels right, go to Carvana.com and sell your car the convenient way. Terms and conditions apply. You mean not the one two days from now, but yeah? Yeah, yeah. Well, what happened was, Rosita just sent me an email last week at the end of the lecture. He says, "You forgot to announce what time is due. I make it Friday." And I said, "That's good, but this is the first time I hear she made it the wrong Friday. So I will send her email to have her correct that. It's due like two days from now. Okay? I hope that it didn't cause much confusion for you guys. I'll write down on the board also which Friday I mean, so that people who are watching the class don't get confused. Okay, are there any comments or questions? Have you guys started doing the homework? Yeah. And how many people have finished? I don't even remember what the homework was. So I gave you a magnitude and I asked you to recover phase or the other way around. I gave you... I see. So first you started with magnitude recover phase, then you start with phase recover magnitude. Oh, I see. And you're saying... Right, right. And so you're saying... Oh, I see. So in some sense, you have a self-checking mechanism in a sense that you have to be computed. You can test it against the input to see if it's the same. Uh-huh. Uh-huh. I gave you the data for magnitude and phase but for one image, right? Oh, okay. Okay. So what's the question? And then what do I ask you to do? I see. And your question is... Minus the I/O I just talked a couple of people before class. One where you give us just the magnitude information. Right. I wasn't able to get it to come out like that. Oh, yeah. Yeah. Well, the reconstruction... that's exactly the point. The construction from magnitude is not... doesn't work very well. Good initial guess. Lots of additional constraints. Yeah, that's exactly the point. That's an if-condition problem. I wanted you to experience it kind of first time. Okay. Very good. Any other questions or comments about last time's lecture? Yeah, February 3rd, I said, which was last Friday. Has anybody bought it? Okay. So it wasn't in the bookstore. Okay. What? They only had three. Okay. Which one did you go to ASUC? Ned. How many people have purchased the book already? One, two, three. And where do you guys bought it from Amazon? You just bought it from... you didn't wait for the thing. Okay. I'll look into it too. When you say the Berkeley one, what do you mean? There's ASUC and there is Ned. Okay. ASUC. Okay. So, what I want to talk about today is a continuation of a little bit of Z-transform stuff. What we covered last time was the region of convergence of Z-transform for different quadrant sequences. If you have a first quadrant sequence, what would be the properties of the convergent region of convergence for the Z-transform, second, third, and fourth? What I want to talk about today is the notion of difference equations or differential equations. And I want to talk about the fact that a particular difference equation can have many different realizations. And I'll explain what I mean by that. And therefore, when you go to 2D, two dimensions, and you have difference equations, you could also have many different realizations. So the concepts that we'll emphasize are recursive computability, which is, can you, given a difference equation and given a set of input, can you in a recursive way compute one element of the output after the other? As opposed to an implicit way, which involves solving linear system of equations, it's much more complex. And then we also talk about choosing the boundary conditions properly, so that the resulting system from the difference equation ends up corresponding to an linear shift invariant system, and both in 1D and 2D. And rather than just jumping at 2D, I've always found it easier. I've taught this class many years and I've taught it different ways. I've always found it that if I just skip straight to 2D, I lose a lot of the students and the main concepts just don't get through. So I'm going to take a little bit of a detour and go over the basic concepts in 1D, and then the extension to 2D is immediately obvious, much more clear. And I guess I'm not banking on you to have just taken E123 to have seen this. So for those of you who did take it with me and who have seen this analysis, just bear with me. I think there's only really one student and that's Alan. Is that correct? The undergraduate from last semester is not here, David Lin. Well, this is not here today. He might be taking the course. Okay, so this goes back to the discussion we had, you know, way at the beginning of the semester, which was FIR filters, we know how to implement and how to realize finite impulse response filters. You have finitely many non-zero coefficients. You can convolve with an input, regardless of whether the input is infinitely long or finite long, convolution is not only a conceptual thing for FIR filter, for filtering a signal with an FIR filter, it's also a practical scheme. You know, you shift, add, multiply, etc., etc. Now, when you go to IIR filters, then you can't really convolve easily because you have an infinite impulse response. And if you have an infinitely long sequence multiplying and adding and shifting infinite number of points with the input signal, then it's very problematic. So instead, what we what we emphasize when we deal with IIR filters is a class of IIR filters that have rational transfer function, the ratio of two polynomials, and what we've already discussed that several times in this class. So and if the if the if the IR filter has a system function that's rational, then you can implement it through difference equations. And what I want to talk about is some today, mostly some subtleties about real different realizations of the same difference equation. What we'll end up talking about is that the same difference equations depending upon which way you realize it, it could correspond in one day to a causal system or an anti-causal system or just a non-causal system. And then in each case, we have to choose the boundary conditions properly for it to correspond to a linear shift invariant system. Okay, so let me let me begin instead of waving my hands. So just the universe of filters and by filters, I mean LSI systems. Sometimes people use the word non-linear filters to do not non-LSI system, but when I talk about filters in general, I'm talking about linear shift in a million systems that they all have an impulse response. As soon as you say the impulse then LSI, then there's an impulse response to be talking about. And I draw this diagram again. This is the universe of all the LSI systems. This is the FIR1 finite impulse response. This is the IR1. Within IR, you can again divide it into two parts. 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, a plenty 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. No, not quite. What's up? Sell my car and carve on it. It's just not quite the right time. Crazy coincidence. I just sold my car to carve on it. What? I told you about it two days ago. When you know, you know. You know? I've even dropping it off at one of those sweet car vending machines and getting paid today. That's a good deal. Oh, great deal. Come on. What's your heart saying? You're right. When you know? You know? Sold. Whether you're looking to sell your car right now or just whenever feels right, go to carve on it dot com and sell your car the convenient way. Terms and conditions apply. The ones with irrational transfer functions. An example of that is if you have a frequency response of your filter is box in the frequency domain and at the time domain you have a sync as your H event as your impulse response. That doesn't correspond to any rational transfer function. Okay. And then this is the part that we're most interested in is the IIR filter. So this is IIR with rational transfer function. But there's IIR with this is IIR irrational transfer function. This is IIR with rational transfer function. And that's the one we're most interested in. And what that is is for example an H of Z assistant function. That's P of Z over Q of Z. What these guys are all polynomials in Z. Okay. And it's this class that can be implemented using a difference equation. And for the rest of this class I'm going to refer to difference equations as DE. Not GE but DE. Okay. So just so that we can talk about the some of these things more concretely let me let me give you an example of this for at least for one dimension. I think I'll stick to this page. So here's an example. I have an H of Z which is 1 over 1 minus A Z inverse. And I can write this as output over input. H of Z is the system function. Y of Z over X of Z. Then I can cross multiply this thing. What I get is X of Z is equal to Y of Z times 1 minus A Z inverse. And I can take the inverse Z transform and do a couple of steps of manipulation. And what we get is Y of N is X of N plus A times Y of N minus 1. So this is the difference equation. This is called DE or the difference equation. And in different fields they actually we call this an IIR filter with a rational transfer function. But like in the networking literature what they call it they call it the weighted moving average filter. It's just a different terminology but it's the same thing. Okay. So essentially what it says is that output at time N is the input at time N plus some scalar of the previous output. So this is used in systems where you have some sort of a memory. You want to pay attention to the input but you also want to have the previous outputs have some influence of the future output. Okay. So maybe this is something that the stock market people are going to use to predict what tomorrow's stock value would be according to some model like this. But essentially it's an IIR filter with a rational transfer function. And of course if you have, can you roll up please? If you have basic circuit elements like a delay and a multiplier and an adder you can draw the the flow diagram for this as follows. X of N comes out here this is Y of N sticking out. So you start with Y of N you are delayed by 1 by passing it through this delay element and what comes out here is Y of N minus 1. Then you scale it by A. So what comes out here is A times Y of N minus 1. And then you add that to X of N and after you add the two things together according to this out comes Y of N. So this is the flow diagram or flow graph for our system. Okay. And just so that you can relate this to impulse responses the impulse response for this system H of N corresponding to this is A to the N U of N where U of N is just a step function. U of N is 1 for N larger than 0 and it's 0 otherwise. And pictorially H of N just looks like this. It's a it's a dying exponential but it goes on infinitely long. Yeah question, yeah sure. Why is the Z inverse necessarily make it go to like the previous value of time like Y N minus 1? Because this is a fundamental property of Z transform. If X of N has Z transform X of Z, X of N minus 1 has Z transform Z inverse times X of Z. So this this is just a mnemonic or a symbol for a delay element, delay by one unit. Okay. And and what what is the most typical element we use to do the delay is signaled by one point in real life? Yeah, a flip-flop, that's it. Flip-flop. How many people have not heard of flip-flops? Okay you must not be in your your bioengineering folks? Okay. Okay. Well it's it's a circuit element that it keeps the state. You you feed it and then you wait for the clock to change and then it's at one clock cycle later the input you gave comes out. It's a memory element. It delays everything by one unit. It's it's used all the time in electrical engineering system and perhaps mechanical engineering systems. Do we have any mechanical engineers? Okay. You have you had heard of it. So you can play a similar kind of game in 2D. So let's just quickly move on. You can roll up just a little bit. So two-dimensional difference equation. So now I have h of z1 and z2 which is a polynomial in z1 and z2 in the numerator over another polynomial in z1 and z2 in the denominator. Let's say p of z1 comma z2 over q of z1 comma z2. Okay. So now let me give you quickly an example. Suppose I said h of z1 and z2 is 1 over 1 minus a z1 inverse z2 inverse which and let's write this down as y of z1 comma z2 over x of z1 comma z2. By the way if I were to write the system function for an FIR filter what form would it have? Exactly. It would be just a polynomial in the numerator. Nothing in the denominator. The denominator is 1. Okay. So this is the output over input. This is the system and so I cross multiply and do a few steps of math and what comes out is x of n1 comma n2 is y of n1 comma n2 minus a y of, sorry, let me just write this down. It doesn't matter. I write one extra, I write one extra line but from here then you can rewrite it as y of n1 and n2 is x of n1 and n2 plus a times y of n1 minus 1 and 2 minus 1. Okay. Now in 2D I'm going to define what's called input mask and output mask. So let me write this down. Define input mask and output mask and the best way of doing it is just through this example. So what looking at, looking at this difference equation I can do the following. You can roll up a little bit. I can say okay so this is my, this is going to be my output mask as a function of n1 and n2 and this is going to be my input mask as a function of n1 and n2. So what this is telling us is that output at location n1 and 2 to compute this point. Okay. This is n1 and 2. This point would be n1 plus 1 and 2. This point would be n1 plus 1 and 2 plus 1. This point would be n1 comma n2 plus 1 etc. But looking at this thing, what this is telling us is that to compute this point, y of n1 and n2, I need to have y of n1 minus 1 and n2 minus 1. So if this is minus 1, this is minus 1. I need to have this point and that's the only thing I needed from the previous output and at the same time I need to have x of n1 and n2. So I need this point. So again this center point is n1 and n2. Okay. Sorry I'm going to, I'm going to put a circle here. 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 the circle, this is this, the cross denotes the point that's being computed and the circle denotes all the all the elements that go into that computation. So a circle here, a circle here and a cross here. And in real life, as I'm computing the successive values of the output, so this is real life computation that I end up doing, what I end up doing as a function of N1 and N2, to compute the particular point like N1 prime, N2 prime, looking at this difference equation up here to compute N1 prime and N2 prime. I need from the, I need N1 prime minus N2 prime, which is this point, N1 prime minus 1, N2 prime minus 1, and then the output domain. And in the input domain, I also need the point N1 prime and N2 prime. If this is really a repeat of that, maybe I shouldn't have even written down that confuses people. But it's just saying to compute a particular point at the output, I need to go down and left and look, look up the output, the previous output at that point. And I also need to do the same index as the output in the input to help me compute the answer. So this input, input mask, output mask is a convenient way of showing the dependencies of, for any given output, what are the previous outputs you need? And it's just a representation, it's nothing fancy or deep or anything like that. Anybody? Yeah, question. You normally just apply like a boundary condition, like causality or something for that, because it looks like you need y minus 1 minus 1, which is linear. Yeah, let me, let me get to that. That's coming. Just hold on. That's a good question, but hold on. Okay, so now, now let's, let's go on to what I call as to different realizations of the same difference equation. Okay, so let's roll up here. And we talk about different realizations of, yeah, just, just this paper here of the same difference equation. So suppose that I have this, this difference equation that we just wrote down here, which is x of z, which is y of n is equal to x of n plus a y of n minus 1. And as it, as it also happens, we, we also have this h of z, which is 1 over 1 minus a z inverse. And, and we all know from our regular, can you roll down please? From our regular signals and systems courses, maybe E 120 or something, that depending upon what region of convergence you choose for h of z, you're going to end up having two different kinds of systems, right? So if I pick the region of convergence as z larger than a, what kind of system do I end up having? A causal system, exactly. I end up with a causal system and its impulse response is a to the n u of n. But that same system function, if I choose region of convergence z smaller than a, then I end up having an anti-causal system with h of n, which is minus a to the n u of minus n minus 1. So here, the impulse response is right-handed, it goes down like this. Here, the impulse response is left-handed, and it goes to the left like this, okay? And in, in, in, when we're dealing with one-dimensional systems and one-dimensional signals, there weren't too many situations where we wanted to do anti-causal things because most of the time, the, the systems that we were dealing with are, are time-dependent and they're not too many anti-causal systems, most of them. But when you go to 2D and you're dealing with images, there is no causal, anti-causal. You can't say this pixel came before after the other one. So a lot of these things surface up and we have to kind of deal with them. So the bottom line was that with h of z together with region of convergence, can define uniquely an h of n. H of z with this ROC results in this h of n, h of z with this ROC results in this other h of n. And the same thing can be said about the difference equation. So the difference equation corresponding to this system is different from the difference equation corresponding to this other system. And that's exactly what I mean by the different realizations of the same difference equation. So I can realize this difference equation in two different ways. Okay, I can realize it as a causal way, in which case I say y of n takes on the value x of n. And notice that I've now replaced the equality sign because I'm no longer talking about the difference equation. This is the difference equation. This is a realization of that difference equation. So causal way. So this is a realization, let me write this down, of the difference equation. Realization number one. And then the second real, I'll write down the second one. So I can interpret, or I can write down one realization of this difference equation as y of n takes on the value x of n plus a y of n minus one. Alternatively, I can write down the second realization. So this is number one. Number two is the anti-causal way, anti-causal realization if you will. And that is, a y of n minus one takes on the value y of n minus x of n. Or I can now increase the index here by one and divide right-hand side and the left-hand side by a. And what I get is y of n takes on the value one over a y of n plus one minus one over a x of n plus one. So again, I've increased the n index for every term up here in order to come up with that. Or I could have just done the same thing, I could have done the same thing up here, just say write this down as y of n plus one equals x of n plus one plus a y of n and then bring y of n to the left-hand side and get to this. So if you can roll up just a little bit. So these are the two different realizations. This is realization one and this is realization two of the same difference equation. This was the difference equation up there. Okay, so this is the causal realization. And in this big picture that we have, what we can say is that I can draw the picture again. I can say h of z is here. If I have one or c of z larger than a, then I have a causal and the difference equation is y of n x of n plus a y of n minus one. And if my region of convergence is z smaller than a, then I have y of n taking on one over a y of n plus one plus minus one over a x of n plus one. And you can easily see why this is an anti-causal realization because the output at time n depends on future outputs and future inputs. And now I can kind of repeat the same thing for the two, let's now, now that we understand this two different realization for this, let's go back to the example we had in 2D and come up with the two different realizations of our, did everybody follow this discussion? Yeah. Okay, so we can, we can play that same game here. Okay, this was our difference equation, right? Why when is, is this and, and I can come up with two different realizations for that. Even though I kind of cheated the first time around, I automatically assume a given realization. You didn't know what a realization means, but now we do. So it's starting from there, for 2D, I can have also two different realization of my difference equation. Well, one of them is kind of a copy of this, which is y of n one and n two, takes on the value x of n one and n two plus a y of n one minus one, comma n two minus one. The second one is just increase all the indices here, bring, bring the a back and play a bit of a game. And what that, what that does is a y of n one comma n two takes on the value one over a y of n one plus one comma n two plus. 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. The 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. Minus one over a X of n one plus one comma n two plus one. So now for this is system one. This is system. These two correspond to two different systems all together. The same way as the same H of Z could correspond to two different systems depending upon ROC. The same way a different equation can correspond to multiple systems depending upon what realization you choose. In fact, the different realizations of a difference equation, there's a one-to-one correspondence between these, each one of these and the different ROCs, regional convergences, okay. So in this case, we already did the input output mass for one. So for one, the input output mass was shown here, okay. So this is for realization one and for realization two, what's the input output mask here? Well, the output mask is this. To compute the output at Y of n one and n two, I need to know the output at location n one plus one and two plus one, which is this point. And I also need to know the input at location n one plus one and two plus one. So this is the input output mask for realization two and this is the input output mask for realization one. So two different input output masks, two different everything. And you can repeat this same game for many different systems and play this game even more. And the question now becomes, can I recursively compute the output? How do I know whether a particular difference equation in 2D could be recursively computable? And what we mean by recursively computable, I write it down in just a second, is if there's a sequential way of computing one output after another, that's called recursive computable. And the first side you might say, what's you talking about? Of course, you can compute the output one after the other. That's what the thing is telling you. And the answer is no. I'll show you in this one second, an example where the difference equation, we come up with a realization of a difference equation that does not allow you to recursively compute its output. Okay? So now, and what we'll show, let me just give you a preview of what's coming in just one second, and what we're going to show is that, is the following, is that if the output mask of a realization of a difference equation has a wedge support, that means that the angle between its region of support can be contained in some, in a wedge that's less than 180 degrees, then it's recursively computable. And if it, if the wedge support for the output mask is 180 or more, then it cannot be computed in a recursive way. So let me get, get to that. So, so the notion that we want to talk about now is recursive computability. So, so far the, the main thing that we've, we've realized is that a difference equation can have multiple realizations. Now, I'm going to talk about recursive computability. And, and let me first define what I mean by it. And we say a system is recursively computable. If there is a sequential way of computing the output points one after another. Okay. So, again, let's, let's get moving to a slightly more sophisticated example. Suppose I say y of n1 and n2 takes on, I come up with the following realization. Well, let me first write down the difference equation and then write down the different realizations because I think that way you, you'll appreciate it a little bit better. So the difference equation we have, we were considering is y of n1 and 2 plus 2 y of n1 minus 1 comma n2 plus 3 y of n1 comma n2 minus 1 plus 4 y of n1 minus 1 comma n2 minus 1 is equal to x of n1 comma n2. Okay. And to begin with, how many different realizations of this can I possibly come out with? Well, I can have this guy to be on the left hand side. I can have this guy to be on the left hand side and then come up with a different realization. I could have this term to be on the left hand side or I could have this term to be on the left hand side, right? So there's four possible realizations of this difference equation. So four possible realizations of this difference equation. Okay. And we can, we can go over some of them. So let me write down the first realization. I simply just keep this one on the left hand side and I point, move everything to the right hand side. So I'd say y of n1 and n2 takes on the value minus 2 y of n1 minus 1 comma n2 minus 3 y of n1 comma n2 minus 1. That's this term, minus 4 y of n1 minus 1 comma n2 minus 1 plus x of n1 and n2. So this is realization number one. And let's let's write down the input and output mask for it. If we can't, here's the output mask for n1 as a function of n1 and n2. It tells me to compute the output at location n1 and 2. I need the output at location n1 minus 1 comma n2. So here's n1. This is n1 minus 1 n2. So I need this point. Then I need y of n and I need that to be scaled by minus 2. So I put a minus 2 there. I need to scale y of n1 comma n2 minus 1. So this is n1 and 2 minus 1. Just go down by 1. So this is this point and it has to be scaled by minus 3. And then y of n1 minus 1 and 2 minus 1, which is this point, I have to scale it by minus 4. So this is the output mask. And then the input mask is just simple. I need this point. So you can think of this as output mask as a two-dimensional sequence. And you ask yourself as to what is the region of support or ROS of the output mask? Well, now this is the region of support. If I start from this point, I can do a straight line going this way, a straight line going that way. So this is the region of support. So if the region of support of this output mask is wedge, and by wedge I mean is less than 180 degrees, then the system is recursively computable. And in this case, what's the angle here? 90 degrees. So indeed, ROS here for this output mask is wedge, because this angle is 90 degrees and which is less than 180 degrees. Therefore, I can conclude that this system is recursively computable. And what do I mean in real life by recursively computable? Well, I can you can imagine how I would compute the outputs given this kind of inputs. Think of it like this. Well, I'll stick to the same sheet. This is N1, this is N2, and I can compute the output in a let's say row by row or column by column fashion if I wanted to. So to compute this point, I would need to know at the output, I would need to know this output, this output, this output. And suppose I was given those and I can compute it, then I can move here to compute that point. I need to know this one, this one, this one, but I already computed that. So assuming that I have a row here, suppose this I have a row here and I have a column here as an initial condition, then I can compute this point. I need this, this, and that to compute this. 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, a plenty 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 Work Wear 20 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. Point. I need this, this and that to compute this point. I need this to add on that. After I'm done with a row, I can come up here, compute this point. I need this, this and that, this point. I need this, this and that, this point, this, this and that, this point, this, this and that, this, that, that, that, etc. So here's an order that I can row by row or given some sort of initial condition, I can row by row or column by column, go through and one after the other compute the outputs. Is that clear to everyone? And I'll just show you a different realization of that same system where we can't do that. For example, if to compute this, you need to have that and that, there's no way on earth, you can come up with a procedure, recursive procedure in order to compute the outputs in a sequential way. So let's do that. So this is another realization of the same thing, of the same difference equation and just so that we all remember what the difference equation looks like, here it is, okay. So now I'm going to bring this point, the y of n1 minus 1, n2, I'm going to keep that on the left hand side and move everything to the right hand side. So what I get is y of n1 and n2 takes on the value of minus 3 times over 2 of y of, and remember, I've increased, I'm doing two steps at the same time and I'm not sure if I should be doing that. I'm adding a plus 1 to all the n1 indices in this equation. So that makes this guy to become just y of n1 and n2. And then I'm bringing that to the left hand side and so by the time I do that, this term becomes y of n1 plus 1 comma n2 minus 1. This term becomes minus 1/2 of y of n1 plus 1 comma n2. This term is minus 4 over 2 of y of n1 minus 1 plus 1 is just n1 comma n2 minus 1. And then this term is just, this is equal, plus x of, and then this has to become n1 plus 1 comma n2. Did everybody follow what I just did? It's too many steps in one shot, but I'm lazy and I don't want to keep writing things. So what first thing I do is I kept this on the left hand side, brought everything to the right hand side to write it down, and then I added increase the indices of n1 by replaced all the n1s with n1 plus 1 on both sides to keep things balanced. So this is now my new, the realization for this different, new realization of the difference, same difference equation. And this is bound to have a different input output mask. So let's plot that. So here the output mask as a function of n1 and n2, to compute n1 and n2 point here, I need to have minus 3/2 of n1 plus 1 and 2 minus 1. So this is n1 plus 1 and this is n2 minus 1. So we need 3/2 of that, or minus 3/2 of that. And minus 1/2 of y of n1 plus 1 comma n2, this is n1 plus 1 comma n2, so minus 1/2 here, and this guy is n1 comma n2 minus 1, which is this point. Why is it not matching my, hold on, and one comma n2. So we did the half, and that matches what I have here, we did the 3/2 of that matches there. This one is the problematic one. Did I do this right? How could it be? The whole generation of... Hold on, hold on. Yeah, that's definitely here, and that doesn't match my notes from last time I thought it, which puts minus 2 here. So here we go. I was going to show you something that's not recursively computer, but sure as hell, it is recursively computer because the region of support is once again this and that's 90 degrees. So this is also recursively computer. So let me in my head, let's all of us collectively think what realization is that it's not recursively, there's one of them that's not, and let's just quickly see which one it is. So we already did this one, this one, how about if we do, pardon? No, no, no. One of the realizations is not recursively computer, and I meant a mistake, and in my last time I thought the course, and nobody then caught it, I didn't catch it either, and right now I'm realizing it's the same example. Everything is minus 2 of y of n1 and 2 minus 1, it's definitely here and not there. So let's quickly, let me just off-line do a quick calculation here, but let's all of us do it. So if I do, well yeah, but let's pick the right, let's intuitive, well I don't know if this is intuitive. This one? Oh you mean this one? Okay, thank you. So we'll try, what's your name? We'll try May's idea, let's see. That's okay, that's okay, we come with the third realization. So we add n1 and n2 plus 1, so you get, yeah we do, and 1 and n2 takes on y of n1 plus 1, n2 plus 1, and then that's a minus sign, and then minus 1/4, so we remove that, and then minus 2/4 of y of n1, n2 plus 1, and guys catch all my mistakes because this is real time, and then minus 3/4 of y of n1 plus 1, n2, and then plus x of n1 plus 1, n2 plus 1. So let's draw the output mask for this thing, thank you. Okay, so here's the output, here is minus 1/4 of n1 plus 1, n2 plus 1, that's this guy, minus 2/4, minus 1/2 of n1, n2 plus 1, that's this guy, minus 3/4 of n1 plus 1, n2, this one, and, is it right? Professor Gore? Yeah, I think you need 3 in a line, you can't just do it with 3 y terms in like a line. Yeah, that's what I'm looking for, one of the realizations of this thing is supposed to always come out like a box, one, and then I do something wrong, hold on, then you're right, you're right, it'll always come out, ah, you need, that's right, but you see, I have to not cook up an example where that would happen, so it would be, yeah, let's just cook it up, let's just cook it up real time, so it would be, you would have to have y of n1 and n2, which is this point, and then y of n1 plus 1, n2 plus, if you want to go this way, y of n1 minus 1, n2, right? This is, some alphabet, the combination of this should work, so let's say, this is a new difference equation, okay, change the example, so, so is equal, let's just say 1, 2, 4 for the, for the hell of it, and then this is x of n1 and n2, would that work? Yeah, that should do the job, so if you come up with the following realization of it, but what I was gonna do is try to come up with an example, one realization is of course of the computer, but the other one is not, and it's very easy to do that. It's not that, well, you see, I don't want to derive the wrong message to you, which is a given difference equation is always either recursive of the computer, but not, that's not the message. Depending on the realization, sometimes it is, and sometimes, actually, does anybody have Jay Lim's book? Yeah, let me borrow your copy, there's an example there that one could copy, it's too bad because when you, when you cook up an example in your lecture notes, you end up having a typo in them, then you're kind of in trouble, but let's draw the output mask for this, y of n1 and n2 is minus 2 y of n1. 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. Plus 1, n2. Thank you. Yeah, that's supposed to be the one. So. Yeah, let's just, if this doesn't work, then we'll cook up, we'll look it up from, from Lim's book. So, minus 2 and then minus 4 Y of n1 minus n1 comma n2 plus X of n1 comma n2. And if we do that, then the output mask is this point is this guy and then this guy. Perfect. And here's the input mask. Okay. Okay. Well, he finally hit it. But I'm just very curious to know why, I went wrong with my notes and with my examples. Yeah. We'll get, I'll get to that and, and just, I'll fix that example for the next time and show it to you. Yeah. Okay. So, so bottom line. Now, if I look at this, this output mask here, what kind of region of support does it have? Well, I start from here and I have to go all the way to the right and all the way to the left so that I can capture everything. So, it goes this way and it goes this way. So, the angle here is 180 degrees. And, and because it's 180 degrees, it does not have which support. And hence, it's not recursively computable. Okay. And, and, and let's just intuitively convince ourselves that this is indeed the case. Well, suppose I have some sort of initial condition that we'll cook it up as we go along. But basically what this is saying is that to compute a point here, I need to have the point to the right and it's point to the left. So, so, and then to compute, so, so you could say, well, we'll make both of them to be initial conditions. But then if you do that, then you have to have a whole column of initial conditions going up, known values here and whole known values there. And then, then you, then you end up just being able to process a, a one-dimensional signal or one column of your signal. So, then to compute this point, I need this one and, and, and to the right of it. So, you see that there's dependencies between the output and the input. So, you get caught in a chicken and egg kind of situation. So, no matter, you can sit down and play with this for a while, but you'll find out no matter how you pick the initial condition, there's no way that in a recursive way, you can compute the output points one after another. And the main reason is that this support of the output mask is 180 degrees. Or, even if it is larger than 180 degrees, you still have problems. So, for example, if your output mask were to look like this, which is what I had in my example, which is wrong, here, the angle is also 180 degrees. So, this is also not recursively computable. Okay. So, as long as the, this angle is, is larger than 180 degrees, it's, it's not possible to compute the outputs one after another. Okay. And so, one of the questions that, that might come up, so, so let me just write that down. So, if the region of support of output mask is wedge, that means it's less than 180 degrees, then it's recursively computable, the system is recursively computable. That means it's possible to find a set of initial conditions and set of initial conditions to compute the output points one after the other. That's kind of what the point we weren't going to walk away with. And just as a side comment, what happens, so, if you have this kind of a thing, if it is not recursively computable, are we completely a hundred percent out of lock, or is there another trick one can use to do something? Right. You can try a different realization, but for that realization, you can, you can, you may not, if you can put the camera down here, you might not be able to find the, find the output recursively, but here's the thing, suppose I gave you instead of input and I insisted on you computing the output, maybe you can solve a linear system of equations in order to find the output, right? It is true that, you know, the right hand side depends on the left, the left hand side, but if you write it as a matrix times column times a vector equals another vector, then you can do that. And that's called implicit way of solving TDEs, partial differential equation. So this, this recursive computability in the numerical analysis literature is called explicit way of computation. You compute one output after the other. It's kind of, it's very nice and be very good to, to always come up with boundary conditions and systems that allows you to do that, but if that doesn't happen, you're not a hundred percent out of lock, you might be able to solve a linear system of equations that, that given the input, compute the output at one point. And in fact, if you, if you look at, for example, some of the ways that people solve the heat equation, again, we have a mechanical engineer here, right? So what's the classic heat, heat propagation problem you guys solve? You have a plate and have some initial condition around it, right? And then you let time move forward and you want to know the heat distribution as the heat propagates. And I think many times for solving that, that, that's written as a difference equation, partial differential equation, which is the same as difference equation in 2D. And then for, for, for some of those problems, all you do is end up solving a series of linear system of equations at each time step in order to figure out how the heat propagated. If you're dealing with one dimension, you have a piece of wire, you have given, temperatures that the two ends and you want to know how that propagates along one beat, that's a simple difference equation, okay? So, so you're not entirely out of luck if the thing is, is not recursively computable. And just to wrap up this discussion before I start talking about boundary conditions and initial conditions, I would like to show a canned example from Lim's book, because, because then I don't, I don't make any mistakes. So, here is the, if you can zoom in, one more, more, more, more, okay. So, here is the, the system equation that he's, he's playing with, y of z over x of z, this is the numerator, this is the denominator, and that results in this difference equation written here, okay? It's more complicated, it has two x terms, etc. And this difference equation, you can implement four different ways, you can realize four different ways. Number one is to have this at the outputs of this 240 is, is the, this is the realization, this is the second one, 2.41, and this is the third one, and this is the fourth one. And for, for example, for this one, if I look at 240, the input-output mask relationship is shown here, to compute this point, I need this, that, and that, and, and is this wedge support? Yes, because if I start with the, with the, with the center point that I'm computing, draw a line, that's where I draw a line that way and then, then, that's a 90-degree thing. I go to this one, 240, and this is the output mask shown here, and is this a wedge support? It certainly is. If I put, start from the midpoint here, if I start with the midpoint here, draw a line this way, and a draw a line this way, the angle that I get is less than 90 degrees, so this is, this is also recursively computable. And the third realization, which is shown here, is, is shown here, and this is recursively computable as well, because I start from this center point, I draw a straight line up, and I draw a line this way, and the angle is small and less than 90 degrees, less than 180 degrees. And finally, the fourth realization is the one that's not recursively computable, which is what I was trying to show here. So, why has this term, this term, this term, and this term in it? So, and this is shown here, okay? So, the, the center point here, if I connect it to the up and to the down, to contain everything, that's exactly has a hundred. 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. You 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, I'm going to talk about is the process of choosing the boundary conditions. I won't get done with that topic in today's lecture. It will be left over on Friday, but it's a good idea to start it anyway. So, once you've proven to yourself that the thing is recursively computable, the question is how do you then end up choosing the boundary conditions in order to make the system recursively computable? So, choosing BC, BC doesn't stand for British Columbia, but boundary conditions. And the question that we want to ask is given a difference equation plus a realization how to choose boundary conditions. And again, I'm going to start with the one-dimensional, even continuous time example. Actually, let me not do a continuous time and rather stick to the discrete time example. And go over a few basic points. So, suppose that I start with my favorite example, y of n is a times y of n minus 1 plus b times x of n. So, does this, the first question that I ask is, does this define a system? And the answer is no, because the system is something with a unique input. I have to compute the unique output. And this thing with the unique input doesn't give me a unique output. And don't get worried. The main reason is because there's no initial condition. So, is this system? Does this define a system? The answer is no, because a unique input does not result in unique output. And so, suppose y of 1 of n is a solution, then y 2 of n, which is y 1 of n plus k times a to the n is also a solution. So, to the first order, then you can go plug it in and prove to yourself that's indeed the case. So, how do you fix it? Well, you fix it by adding initial condition. Or, by initial condition and boundary condition, I use them interchangeably, right? In 2D, you talk about boundary conditions and 1, either by initial condition. So, if I say, okay, well, that's my system, and I'm going to make the initial condition to be y of minus 1 equals y naught, then it is a system. And in fact, you can go through kind of all the steps, and either you do it by inspection, or you use induction, or you apply homogeneous solution and particular solutions in a variety of different ways. And what you find is that the answer is, I'm debating whether I should tell you how I got the answer or not. Let's just do it. So, for n larger than 0, you keep writing down the answer. You write down y of 0 is a times y of minus 1 plus b. And here, I'm assuming that x of n is just b times delta of n, okay? b times delta of 0, and we can find out that for n larger than 0, y of n is a to the n, a y naught plus b. Then I do y of 1, and I do y of 2, and then I can see that y of n is given by this form. And then for, if you can go back here, I'll roll up a little bit. And then you can also find out that for n equals minus 1, we already know what the output is for n smaller than minus 2. You can go backwards, okay? What you can say is that y of n, from here, from the difference equation, which is shown here, I can rewrite things in an anti-causal way, kind of say y of n minus 1 is equal to 1 over a y of n minus b over a delta of n, right? And then I can compute y of minus 2 when y of minus 3, and figure out that for n smaller than or equal to minus 1. So, in this case, y of minus 2 is nothing but 1 over a times y of minus 1 minus b over a delta of minus 1, and compute this in y of n is a to the n plus 1, why not? And then I marry these two answers. This is my answer for n smaller than 1, and I also computed the answer for n larger than 0, which is here. And I put these two things together, and what I get is y of n is a to the n, a y naught plus b times u of n, this is for n, u of n is, for this case, n larger than 0, plus the answer that I had here, a to the n plus 1, y naught times u of minus n minus 1. And again, I can do some simple manipulation, and I find that y of n is a to the n plus 1, y naught plus a to the n, v, u of n. So, that's the final answer, and this is true for all n. Okay? Or you can also solve, you can also do this thing by solving homogeneous solution, and then solving particular solutions, and then using the initial condition, you can say that the total solution is homogeneous, plus particular, and then to get rid of all the constants, you impose the initial conditions, and that gives you the final answer. Okay? So, still at this thing for a while, is this thing a linear, strictly speaking, a linear system? We have, this is the difference equation we're looking at. This is the difference equation we're looking at, and this is the solution we found. Is this a linear system? It really, strictly speaking, it's not. It's an affine system, but let's not get into the definition of an. It's not linear, because if I make the input, one of the properties of linear systems is that if the input is zero, output should be zero, right? It has this property. If x of n results in y of n, a times x of n should be equal a times y of n, should result in a times y of n, and that has to be true for all a, in particular for a equals zero, so one of the properties of a linear system is input to zero, output has to be zero. In this case, if I make b equals zero, the input just goes to zero, the output is not zero, it's something else. And you might say, okay, well, how do I fix that problem? It's just a mathematical oddity or something, how do I fix it? Can anybody figure out how to fix it? What should we change in our initial condition to fix that? And remember, our initial condition was that y of minus one is y naught, so that's showing up here. So if we make the initial condition to be zero, then we can have a linear system. Okay, so conclusion or observation, make I c to be zero. That means y naught has to be zero. Now if I do that, what I get is y of n is a to the n, b, u of n. Okay? So, so far, we've started with a linear constant coefficient difference equation, okay, which is this thing here. Why do I call it linear? Well, it's linear, it doesn't have any, it doesn't have any square terms, it doesn't have any cross terms, it doesn't have like y of n times y of n minus one, it doesn't have y of n squared or cube, it doesn't have square root of y of n, so it's linear. It's constant coefficients, that means a and b are constant, that means I could have had coefficients if they were not constant, like t of n minus one or, or. 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. Z of or W of n plus five, which means the coefficients of the system are also varying as a function of time, but they're not. So it turns out because we're dealing with ILR filters that have rational transfer function, that always results in linear constant coefficient difference equation. So we start with linear constant coefficient difference equation that we need IC to make it a system, to make it correspond to a system. And then we need the IC to be equal to zero to have linear system. And what I'm going to show you in just one second is that, will this system be shifting variant? And the answer is, the system is only shifting variant if the location at which the initial condition is zero is chosen in accordance with the input. So is it shifting variant? And the answer is yes, but only if initial condition is chosen in accordance with the input. Okay. So in other words, what, what do I mean by all of these things? What do we mean by shift invariance in general? Well, shift invariance in general means that if we shift the input, the output changes as well. Okay. So what I mean by all of these things is that if X of n, for X of n equals delta of n, B times delta of n, initial condition having Y of minus one equals to zero, that results in shift invariance. That's a good initial condition for this input. Okay, I mean, if you can roll up just a little bit. However, if X of n was B delta of n minus five, then if I'm initial condition was Y of minus one equals zero, that does not result in shift invariance. Instead, in this case, the initial condition that would result in shift invariance is Y of what? Here, the input X of n becomes non-zero at this time, and we're having a causal implementation. So we wanted Y at times minus one to be equal to zero. Here, what happened? Here, X of n starts at five, right? So we want for the initial condition to be right so that we can roll and can recursively compute the output that way, we want Y at four to be equal to zero. So that's what I mean by the input, the initial condition has to shift with input. It has to match, it has to drive with input. So instead, we don't, we talk about what's called initial rest conditions when we deal with one-dimensional systems. So in one-dimensional systems, again, you can watch one of the video tapes for 123, but the conclusion that you get is the linear constant coefficient difference equation plus initial rest condition results in an LTI system, which is causal, or alternatively, linear constant coefficient difference equation plus final rest condition results in an LTI system that's anti-causal. So if you want to have time invariance, you have to have initial rest condition and final rest conditions. That means what, in simple language, it means what I just said here is that depending upon what your input is doing, you have to match the initial condition to be just right for that input. So if I don't move the input, if I don't change the initial condition accordingly with the input, then I lose the time invariance kind of properly. And so coming back to a realization, then, in this, coming back to our example, which we had written here, so what do all of, let's just translate all of these facts that we wrote down here to the example, if I have y of n is a y of n minus 1 plus vx of n, where x of n is, oh, I have two b's here. Let's just remove that b, okay. Where x of n is b delta of n minus 5, then I have two b's again, okay. So to make this correspond to a linear shift invariant system, I need to have initial condition, which is y at times 4 is equal to 0. It has to be 0 here, in order to make it linear, where is my red 10? I lost it. 0 to make it linear, and I have to pick this to be index 4 to make it shift invariant, okay. So if it was anything else by 0, it wouldn't be linear, because 0 input wouldn't result in 0, but if it was at any different location. And this is for causal implementation, right? So y of n takes on a of y n minus 1 plus v of x of n, okay. Now for anti-causal realization, so this is, this whole discussion here is with causal. For anti-causal, it's all the opposite. So anti-causal, then y of n minus 1 takes on minus 1 over ay of n minus v over ay of x of n. That's the anti-causal implementation. Now, if I give you an input, for example, x of n, that's delta of n, it becomes non-zero at this location, then I want the initial condition to be 0 at, the initial, yeah, at 0 it has to be 0, as it turns out. Or if x of n is at this location at 5, then y of 5 has to be 0. That's the initial condition. Again, match to the input that allows us to recursively compute the output. Because then y of minus 1 is 1 over ay of 0 minus v over ay of x of 0. So I can successfully compute y of minus 1. y of minus 2 is the previous sample plus that. So then in this case, in this case, I can just compute the output y of n recursively, right? Given that y, let's say x of n is just a delta function, and x of n is equal to 0, I can say, okay, y of minus 1 is 1 over ay of 0 minus v over ay of x of 0. So I can compute this value of the output from the previous one. And this was my initial condition, right here. And then I can compute the output at time minus 2 using this thing. I think let's keep going back. So that's, or in this case, the same thing. If x of n is delta of n plus 5, then I can say y of 4 is minus ay of 5 minus v that. So because I have y of 5, that's, this makes, I can compute x, y of 4. Then I can compute y of 3, y of 2, y of 1 going all the way back. Is that clear? So the thing you want to walk away from is that to do, to do, to resolve in a shift invariant system, either causal or anti-causal, you have to match the boundary conditions or the initial conditions with the characteristics of the input. In fact, you have to pick the input. You have to make it pick the, for initial rest condition and one dimension, you have to pick the, the output to be 0 up until the time that the input has become non-zero. That's what I mean by matching, okay? Now what we do in next time's lecture is how to extend all of these concepts into the, and so we'll, we'll, we'll talk about it on Friday, and, and. 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, a plenty 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 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.