1 00:00:00,012 --> 00:00:04,970 >> In this video we're going to discuss the implementation of digital filters, and 2 00:00:04,970 --> 00:00:09,168 I don't mean what kind of software environment or issues like that. 3 00:00:09,168 --> 00:00:13,846 What I'm more concerned about are efficiency and using filters that have the 4 00:00:13,846 --> 00:00:17,308 characteristics that I really want in my application. 5 00:00:17,308 --> 00:00:20,201 So we're going to talk a little bit about IIR. 6 00:00:20,201 --> 00:00:24,295 Iir versus FIR filters. Turns out that FIR filters are used 7 00:00:24,295 --> 00:00:28,795 frequently as are IIR. The choice really depends on some details. 8 00:00:28,795 --> 00:00:33,174 We're then going to talk about the con, computational complexity. 9 00:00:33,174 --> 00:00:38,688 Whether you want to implement a filter in a time-domain, what I mean by that is just 10 00:00:38,688 --> 00:00:44,340 program the difference equation. Or whether you want to implement frequency 11 00:00:44,340 --> 00:00:49,836 domain which means using 4a transforms. We're going to find that in many cases 12 00:00:49,836 --> 00:00:55,716 frequency-domain filtering despite the idea you might say well geez taking all 13 00:00:55,716 --> 00:01:01,241 those transforms can't be that good. Ah,turns out it winds up being efficient 14 00:01:01,241 --> 00:01:05,349 in many cases because of. Properties of the FFT. 15 00:01:05,349 --> 00:01:13,265 Now, let's consider the IIR filter first and what we can start is worrying about a 16 00:01:13,265 --> 00:01:19,563 time domain of limitation ie, we use the difference equation. 17 00:01:19,563 --> 00:01:28,209 And it's pretty easy to see That, for each output p multiplies and p minus 1 18 00:01:28,209 --> 00:01:36,284 additions for what I call the IIR part, and q plus 1 and q for the FIR part. 19 00:01:36,284 --> 00:01:45,662 And putting all these together in terms of complexity For each output the complexity 20 00:01:45,662 --> 00:01:51,705 is order p plus q. Now even if the input is a finite duration 21 00:01:51,705 --> 00:01:56,610 the output for an IIR filter is infinitely long. 22 00:01:56,610 --> 00:02:02,353 This has an infinite duration units impulse response. 23 00:02:02,353 --> 00:02:04,837 So. The number of computations is 24 00:02:04,837 --> 00:02:09,565 theoretically infinite. What happens in practice is that once the 25 00:02:09,565 --> 00:02:15,430 last input has been passed into the filter the succeeding calculations the filter 26 00:02:15,430 --> 00:02:20,896 does produce an output but usually it settles down after a while being used. 27 00:02:20,896 --> 00:02:27,982 Seems to stop the computations, but that depends on a host of values not the least 28 00:02:27,982 --> 00:02:34,582 of which are the values of the, of the a coefficients, so it turns out, for all 29 00:02:34,582 --> 00:02:41,168 practical purposes IIR filters are. An infinite computational complexity but 30 00:02:41,168 --> 00:02:46,138 in practice we actually have fewer but that's hard to judge here. 31 00:02:46,138 --> 00:02:51,064 I'm going to point out by the way that we are not going to talk much about filter 32 00:02:51,064 --> 00:02:54,440 design. There are, as you might expect, software 33 00:02:54,440 --> 00:02:57,501 programs that design these filters for you. 34 00:02:57,501 --> 00:03:03,416 In other words, you give it. Specifications of let's say you have a low 35 00:03:03,416 --> 00:03:06,496 pass. You want to know what the cut off 36 00:03:06,496 --> 00:03:12,077 frequency is and you give that. It will come back with a set of 37 00:03:12,077 --> 00:03:18,608 coefficients, values for p and q and a set of coefficients that will do the job. 38 00:03:18,609 --> 00:03:21,221 Job. And that, turns out. 39 00:03:21,221 --> 00:03:27,376 So, the filter design problem is really nothing more than running some software. 40 00:03:27,376 --> 00:03:31,111 There's software out there for FIR filters, too. 41 00:03:31,111 --> 00:03:35,201 It's very different, But it works very well, too. 42 00:03:35,201 --> 00:03:41,749 What you discover is that the number of. Coefficients for an FIR filter to do a 43 00:03:41,749 --> 00:03:48,704 specific filter job is going to be more than the total number of coefficients for 44 00:03:48,704 --> 00:03:52,409 an IRR filter. In general, this is true. 45 00:03:52,409 --> 00:03:56,507 Not always. But in most cases, it takes more 46 00:03:56,508 --> 00:04:02,190 coefficients to. Compute the Fir filter all the B's, then 47 00:04:02,190 --> 00:04:06,863 it does some of the A's and B's for the FIR filter. 48 00:04:06,863 --> 00:04:13,937 But anyway, we now can compute complication complexity because this is an 49 00:04:13,937 --> 00:04:19,173 FIR filter. The complexity for each outfit is order Q. 50 00:04:19,174 --> 00:04:25,832 And therefore if the input has a duration n, the output is going to have a duration 51 00:04:25,832 --> 00:04:29,812 of n plus q. Notice that the duration of the unit 52 00:04:29,812 --> 00:04:35,521 sample response here runs from zero to q, so the duration's q plus 1. 53 00:04:35,521 --> 00:04:40,473 So using my old formula for the duration of the output is n. 54 00:04:40,474 --> 00:04:48,227 Notice that the duration of the input was the duration of the mid sample response 55 00:04:48,227 --> 00:04:51,971 minus 1. And that gives us the n plus q. 56 00:04:51,971 --> 00:04:56,121 So the complexity is q times n plus q. Okay. 57 00:04:56,121 --> 00:05:02,134 So that's the complexity. And, We can use this to consider whether 58 00:05:02,134 --> 00:05:07,380 we want to actually implement that f-r filter in the frequency domain. 59 00:05:07,380 --> 00:05:12,353 So, this brings up the issue of a frequency domain implementation. 60 00:05:12,353 --> 00:05:18,144 Now, we know it's true, because this is the way the mathematics works, that the 61 00:05:18,144 --> 00:05:21,662 DTFT. The output is equal to the DTFT of the 62 00:05:21,662 --> 00:05:27,377 sample response times the DTFT of the, note that this is always true. 63 00:05:27,377 --> 00:05:33,203 However as we've talked about, you actually can't compute these things 64 00:05:33,203 --> 00:05:38,538 because the frequency interval f, that's the stumbling block. 65 00:05:38,539 --> 00:05:45,552 F has a uncountably, infinite number of values you'd have to compute it for, and 66 00:05:45,552 --> 00:05:50,083 you could never get there. So we have to use the DFT. 67 00:05:50,083 --> 00:05:53,823 Now, the DFT is a sampled version of these. 68 00:05:53,823 --> 00:05:58,457 So y k is a sampled version of the y e to the j 2 pi f. 69 00:05:58,458 --> 00:06:03,516 We kept, these are sample versions. This is a sample version. 70 00:06:03,516 --> 00:06:09,137 And this is a sample version.So there's some issues we need to talk about. 71 00:06:09,137 --> 00:06:14,450 So but let me go through what the frequency domain implementation is. 72 00:06:14,450 --> 00:06:19,212 You have some input. The idea is, we're going to take its DFT, 73 00:06:19,212 --> 00:06:25,219 obviously using the FFT algorithm, to get the sampled spectrum of x. 74 00:06:25,219 --> 00:06:31,893 We're then going to multiply that by the sampled spectrum of the transfer function. 75 00:06:31,893 --> 00:06:36,563 Now, I didn't show taking the Fourier transform of the. 76 00:06:36,564 --> 00:06:41,093 The example response because usually that's a fixed quantity. 77 00:06:41,093 --> 00:06:46,539 We know what the filter is, we're just trying to run data through it so there's 78 00:06:46,539 --> 00:06:52,616 usually, you don't consider the complexity of the one time com, computation of this 79 00:06:52,617 --> 00:06:57,991 trans, sample transfer function. We multiply the two together. 80 00:06:57,991 --> 00:07:03,885 That produces, hopefully, the sampled spectrum of the output. 81 00:07:03,885 --> 00:07:08,838 Take the inverse DFT and finally wind up with our output. 82 00:07:08,838 --> 00:07:15,578 So the idea is, this is our linear system. Linear shift and variance system. 83 00:07:15,578 --> 00:07:19,655 I put a box around it. And what we're going to worry about is how 84 00:07:19,655 --> 00:07:23,090 to implement it. We're going to do it in the time domain 85 00:07:23,090 --> 00:07:27,593 with a difference equation or are we going to use this frequency domain 86 00:07:27,593 --> 00:07:31,588 implementation? Now, can we use this implementation in the 87 00:07:31,588 --> 00:07:38,290 frequency domain for an IIR filter? Well, by definition, we, our unit sample 88 00:07:38,290 --> 00:07:44,709 response has infinite duration. To compute the DFT, I need a finite 89 00:07:44,709 --> 00:07:49,653 duration sample. So I can't even compute, this, as a 90 00:07:49,653 --> 00:07:54,127 Fourier transform. I can sample the formula. 91 00:07:54,127 --> 00:08:01,237 For the transfer function, which can be derived from the difference equation to 92 00:08:01,237 --> 00:08:05,518 get an h of k. However, the sampling theorem still 93 00:08:05,518 --> 00:08:10,341 applies. Those sample values correspond to, those 94 00:08:10,341 --> 00:08:16,714 correspond to an alias version. Of the unit sample response if the actual 95 00:08:16,714 --> 00:08:20,675 IIR filter. So you can't really get there, you, you 96 00:08:20,675 --> 00:08:25,120 can't really find anything useful using this approach. 97 00:08:25,120 --> 00:08:31,636 So it turns out IIR filters really can't be implemented in frequency domain it's 98 00:08:31,636 --> 00:08:33,061 just. It goes. 99 00:08:33,061 --> 00:08:37,920 F-r builders though, I think all systems are go here. 100 00:08:37,920 --> 00:08:45,611 It has a finite-duration, output, because little h is a finite-duration, so I can 101 00:08:45,611 --> 00:08:50,323 find this by taking the DTF, and everything's fine. 102 00:08:50,324 --> 00:08:55,017 So we're going to be off and running with this approach. 103 00:08:55,017 --> 00:09:01,430 We're going to talk about frequency domain implementations of FIR filters. 104 00:09:01,430 --> 00:09:05,972 All right. Now, here's where the subtleties come in 105 00:09:05,972 --> 00:09:11,368 of the FIR filters. All transform lengths have to be the same. 106 00:09:11,369 --> 00:09:19,382 It makes no sense to multiply an x times a capital h where these were taken with 107 00:09:19,382 --> 00:09:26,382 different length transforms. Furthermore, the output is derived from a 108 00:09:26,382 --> 00:09:33,417 inverse d of t, so, the duration this transform here has to be of the same limit 109 00:09:33,417 --> 00:09:37,495 as this one, and the one that is implicit here. 110 00:09:37,495 --> 00:09:42,568 So, the transform length that determines it is how long the signal is. 111 00:09:42,568 --> 00:09:47,296 The length of the signal. You have, have to take a transform that's 112 00:09:47,296 --> 00:09:52,307 at least as long as the signal. Well, that means the longest signal. 113 00:09:52,307 --> 00:09:57,659 Is going to be the one. Well, by far and away, the one that's the 114 00:09:57,659 --> 00:10:02,082 longest is the output. And as we know the duration of the output 115 00:10:02,082 --> 00:10:07,626 is the duration of the input plus the duration of the unit sample response minus 116 00:10:07,626 --> 00:10:11,034 1. And that means our transforming has to be 117 00:10:11,034 --> 00:10:13,730 bigger Were equal to n plus q. So. 118 00:10:13,730 --> 00:10:21,206 That means this, this has duration n. This has duration q with a little h and n. 119 00:10:21,206 --> 00:10:28,124 That means we're going to have to pad those and take a transform at least n plus 120 00:10:28,124 --> 00:10:35,144 q long which is going to be The sign, the duration of y then, of course N plus q 121 00:10:35,144 --> 00:10:41,948 might not wind up being counter 2 for using the FFT, so we're going to pad that 122 00:10:41,948 --> 00:10:46,536 even with 0, with 0 so we could get to the power of 2. 123 00:10:46,536 --> 00:10:50,640 So you could be taking fairly long transform. 124 00:10:50,641 --> 00:10:58,822 Especially of h of n, in order to, to meet this requirement because n could be much 125 00:10:58,822 --> 00:11:04,183 bigger than q. Alright, so, but is it more efficient to 126 00:11:04,183 --> 00:11:10,312 go through all that work? Is it better to implement in a time-domain 127 00:11:10,312 --> 00:11:16,170 versus the frequency domain? Now, better does not mean you get better 128 00:11:16,170 --> 00:11:20,964 quality results. Presumably, in today's computers, the 129 00:11:20,964 --> 00:11:25,096 computational accuracy would be about the same. 130 00:11:25,096 --> 00:11:28,591 That's not the issue. The issue is speed. 131 00:11:28,591 --> 00:11:33,627 Which one is faster. Now, the number of computations for a 132 00:11:33,627 --> 00:11:38,174 linked in input in the time domain, is given by this. 133 00:11:38,174 --> 00:11:42,517 We have n plus q output values, we have to compute. 134 00:11:42,517 --> 00:11:47,898 And the complexity for each was 2q plus 1. The formula for the. 135 00:11:47,898 --> 00:11:51,828 Frequency domain approach is rather interesting. 136 00:11:51,828 --> 00:11:56,520 So you see the term over here that relates to the transforms. 137 00:11:56,520 --> 00:12:02,727 I have two transforms I have to compute. They each have the same complexity because 138 00:12:02,727 --> 00:12:08,050 they have to be the same length. And so that's where 5 times N plus q log 2 139 00:12:08,050 --> 00:12:14,760 of N plus q comes from. The six here, which is just proportional 140 00:12:14,760 --> 00:12:23,937 to n plus q has to do with this multiply. This is a complex multiple inspector or 141 00:12:23,937 --> 00:12:30,127 complex value. So you have an a plus jb, times a c plus 142 00:12:30,127 --> 00:12:33,856 jd. And you'd have to multiply that out. 143 00:12:33,856 --> 00:12:38,687 That requires four real multiplies and two addiotions. 144 00:12:38,687 --> 00:12:45,115 And that's where this 6 comes from. So, the question is, which is smaller? 145 00:12:45,115 --> 00:12:48,944 Whichever is smaller is going to be the one. 146 00:12:48,945 --> 00:12:53,688 That we want to choose. We do not want to choose the one that's 147 00:12:53,688 --> 00:12:57,140 bigger. That would mean more computations. 148 00:12:57,140 --> 00:13:02,131 So, let's see how that works. So here I have a plot of the number of 149 00:13:02,131 --> 00:13:08,202 computations it takes versus in the time domain and in the frequency domain. 150 00:13:08,203 --> 00:13:12,802 N is along this axis. Q is along this axis. 151 00:13:12,802 --> 00:13:21,192 And you can that the time domain, while it may be prettier plot, turns out to be 152 00:13:21,192 --> 00:13:27,639 bigger than in the frequency domain for all values of N. 153 00:13:27,639 --> 00:13:35,565 And it's only when the filter length is less than about 20 is the time-domain 154 00:13:35,565 --> 00:13:39,620 small. So N is not the consideration, what 155 00:13:39,620 --> 00:13:44,642 matters is the number of coefficients in the filter. 156 00:13:44,642 --> 00:13:51,381 And it turns out that the filter length gets bigger than about 20 or so. 157 00:13:51,381 --> 00:13:57,745 It is much more effeciant to do things in frequency domain much, much fewer 158 00:13:57,745 --> 00:14:02,068 complitations. So it is worth all that work in most 159 00:14:02,068 --> 00:14:09,106 applications to take transformers and inverse transformers really does make the 160 00:14:09,106 --> 00:14:13,676 filtering occur much more effecintly and quickly. 161 00:14:13,676 --> 00:14:19,446 Frequency domains are ready to go. So, I want to digress a little bit and 162 00:14:19,446 --> 00:14:25,299 talk a little bit about long inputs. So, suppose the input X is a million 163 00:14:25,299 --> 00:14:31,833 points smaller, does this means I have to take a million plus, let's say a 100 164 00:14:31,833 --> 00:14:37,200 length transform of that? Do all those computations at once. 165 00:14:37,200 --> 00:14:43,206 The answer is no because we can use the principle of super position. 166 00:14:43,206 --> 00:14:48,585 And here's the idea. Just like we did for spectrograms, I can 167 00:14:48,585 --> 00:14:52,716 divide up the long input into sections. Okay? 168 00:14:52,716 --> 00:14:55,856 I can filter each separately. Okay? 169 00:14:55,856 --> 00:15:01,792 And because the signal consists of the blue part plus the green part. 170 00:15:01,792 --> 00:15:07,188 They really don't overlap in time. They're at separate times. 171 00:15:07,188 --> 00:15:11,358 But conceptually, since it consists of the sum. 172 00:15:11,358 --> 00:15:18,058 I just need to add up the results. And so, what you get for an FIR filter is 173 00:15:18,058 --> 00:15:25,403 you will, might have a output which looks like this, but's it's going to be longer 174 00:15:25,403 --> 00:15:29,721 than the input, or however long the filter is. 175 00:15:29,721 --> 00:15:35,403 And so, it will extend into the boundary of the next section. 176 00:15:35,404 --> 00:15:42,267 The green signal gets filtered and it produces this which again is longer, but 177 00:15:42,267 --> 00:15:49,092 we now have to use superposition and in the region of what's called overlap, we 178 00:15:49,092 --> 00:15:54,389 have to add them up. Well of course there's some overlap from 179 00:15:54,389 --> 00:15:58,988 the previous. Section here if this wasn't really the 180 00:15:58,988 --> 00:16:04,255 beginning of the sigma. And when all is said and done you get this 181 00:16:04,255 --> 00:16:11,304 beautiful output here which looks like we filtered that entire, long signal at once. 182 00:16:11,304 --> 00:16:18,010 We don't actually have to do that, we actually can do it using sections and 183 00:16:18,010 --> 00:16:22,453 filtering each overlapping and adding the results. 184 00:16:22,453 --> 00:16:27,629 This is sometimes called the overlap add method of doing these. 185 00:16:27,629 --> 00:16:33,054 So you don't, you can actually process these in short pieces. 186 00:16:33,054 --> 00:16:37,992 This makes things run a whole lot quicker. You just add them up and just be 187 00:16:37,992 --> 00:16:43,261 continually producing output as long as you worry about this overlap region. 188 00:16:43,261 --> 00:16:46,886 This is very important to get this overlap correctly. 189 00:16:46,886 --> 00:16:52,238 I want to talk about something else that's in this picture, and those are the dash 190 00:16:52,238 --> 00:16:57,915 red curve. This input that I started with consists of 191 00:16:57,915 --> 00:17:02,111 a sine wave, which I show as a dashed red line. 192 00:17:02,111 --> 00:17:07,727 With noise added. Noise is random signals, usually of a high 193 00:17:07,727 --> 00:17:12,569 frequency content, that just sort of gets in the way. 194 00:17:12,569 --> 00:17:18,151 And, Makes the signal look ugly. And once I added the noise, I got the 195 00:17:18,151 --> 00:17:22,335 signal shown by the stem plot. Which is very erratic. 196 00:17:22,335 --> 00:17:26,096 And you can barely tell there's a sine wave inside. 197 00:17:26,096 --> 00:17:31,692 1 of the great uses of low pass filters is to get rid of high frequency noise. 198 00:17:31,692 --> 00:17:37,573 To try to remove it as much as possible. Some of the noise usually has some power 199 00:17:37,573 --> 00:17:43,077 in the same frequency band as the signal. You can't get rid of that but you can 200 00:17:43,077 --> 00:17:49,080 certainly get rid of the, the noise, the high frequency content that has nothing to 201 00:17:49,080 --> 00:17:52,514 do with the signal. And that's what I did here. 202 00:17:52,514 --> 00:17:57,298 I've used a low pass filter In both these cases. 203 00:17:57,298 --> 00:18:05,827 And I produced a result with is given by the blue output down here. 204 00:18:05,827 --> 00:18:13,148 You can see that it kind of resembles the, sine wave. 205 00:18:13,148 --> 00:18:18,819 But it doesn't quite. And like I said, that's due to the fact 206 00:18:18,819 --> 00:18:24,561 that some of the noise has frequency components that are close to the frequency 207 00:18:24,561 --> 00:18:27,764 of the sine wave, it's hard to remove those. 208 00:18:27,764 --> 00:18:31,927 What's more interesting though is why is it shifted over? 209 00:18:31,927 --> 00:18:35,418 Why is there, why is the peak of the input here. 210 00:18:35,418 --> 00:18:39,746 But the peak of the amplitude is over here. 211 00:18:39,746 --> 00:18:46,758 If you look carefully, it's about the same shift, all the way accross. 212 00:18:46,758 --> 00:18:53,101 What's causing that? The answer is, it's a linear phase shift. 213 00:18:53,101 --> 00:18:57,022 Due to the filter. The filter had to be implemented somehow, 214 00:18:57,022 --> 00:19:00,035 and that always produces a linear phase shift. 215 00:19:00,035 --> 00:19:04,263 Which is very predictable. In other words, I know what that linear 216 00:19:04,263 --> 00:19:09,114 phase shift is, it's a property of the filter, and I understand that it's going 217 00:19:09,114 --> 00:19:12,234 to, the output is going to look like a phase shift. 218 00:19:12,234 --> 00:19:18,920 With respect to inputs of, some sense I could shift back the blue ones to, if I 219 00:19:18,920 --> 00:19:25,561 wanted to, in order to make it look like the input if that were ever an issue. 220 00:19:25,561 --> 00:19:32,084 Okay, so, implementing filters. When you go through the filter design 221 00:19:32,084 --> 00:19:34,106 process. Ok, steady. 222 00:19:34,106 --> 00:19:40,972 Usually true that the FIR, the IIR filter rather is fewer coefficient values than in 223 00:19:40,972 --> 00:19:45,261 FIR filter. It's hard to figure out the computation 224 00:19:45,261 --> 00:19:51,729 complexity of the IIR filter but in most applications is probably going to be true 225 00:19:51,729 --> 00:19:58,627 than an IIR filter is also faster. However people tend to use FIR filters in 226 00:19:58,627 --> 00:20:05,024 very interesting applications. In particular, ones where linear phase 227 00:20:05,024 --> 00:20:11,086 characteristics are involved. Linear phase means a pure delay. 228 00:20:11,086 --> 00:20:16,523 It turns out II filters, IIR filters. Cannot have a linear phase. 229 00:20:16,523 --> 00:20:21,900 You'll get what's called phase distortion, which may be an issue or may not. 230 00:20:21,900 --> 00:20:27,870 One of the more attractive reasons though, for using FIR filters is even though, they 231 00:20:27,870 --> 00:20:33,330 may be, have more coefficient values is that they can be implemented using the 232 00:20:33,330 --> 00:20:37,236 FFT. That really makes it quite Interesting and 233 00:20:37,236 --> 00:20:43,696 attractive that means you can get a chance to look at the signal spectrum while 234 00:20:43,696 --> 00:20:49,449 you're filtering in advanced applications that might be important. 235 00:20:49,450 --> 00:20:54,775 And so in a lot of cases people use the FIR filter and go that way.