5.13 Filtering in the frequency domain  (Page 2/2)

For IIR systems, we cannot use the DFT to find the system's unit-sample response: aliasing of the unit-sampleresponse will always occur. Consequently, we can only implement an IIR filter accurately in the timedomain with the system's difference equation. Frequency-domain implementations are restricted to FIR filters.

Another issue arises in frequency-domain filtering that isrelated to time-domain aliasing, this time when we consider the output. Assume we have an input signal having duration $N_x$ that we pass through a FIR filter having a length- $q+1$ unit-sample response. What is the duration of the output signal? The difference equation for this filter is

The main theme of this result is that a filter's output extends longer than either its input or itsunit-sample response. Thus, to avoid aliasing when we use DFTs, the dominant factor is not the duration of input or of theunit-sample response, but of the output. Thus, the number of values at which we must evaluate the frequency response's DFTmust be at least $q+N_x$ and we must compute the same length DFT of the input. To accommodate a shorter signal than DFT length, we simply zero-pad the input: Ensure that for indices extending beyond the signal's duration that the signal iszero. Frequency-domain filtering, diagrammed in [link] , is accomplished by storing the filter's frequency response as the DFT $H(k)$ , computing the input's DFT $X(k)$ , multiplying them to create the output's DFT $Y(k)=H(k)X(k)$ , and computing the inverse DFT of the result to yield $y(n)$ .

Before detailing this procedure, let's clarify why so many new issues arose in trying to develop afrequency-domain implementation of linear filtering. The frequency-domain relationship between a filter's inputand output is always true: $Y(e^{i\times 2\pi f})=H(e^{i\times 2\pi f})X(e^{i\times 2\pi f})$ . The Fourier transforms in this result are discrete-time Fourier transforms; for example, $X(e^{i\times 2\pi f})=\sum x(n)e^{-(i\times 2\pi fn)}$ . Unfortunately, using this relationship to perform filtering is restricted to the situation when we have analyticformulas for the frequency response and the input signal. The reason why we had to "invent" the discrete Fourier transform(DFT) has the same origin: The spectrum resulting from the discrete-time Fourier transform depends on the continuous frequency variable $f$ . That's fine for analytic calculation, but computationally we would have to make anuncountably infinite number of computations.

Suppose we want to average daily stock prices taken over last year to yield a running weekly average(average over five trading sessions). The filter we want is a length-5 averager (as shown in the unit-sample response ), and the input's duration is 253 (365 calendar days minusweekend days and holidays). The output duration will be $253+5-1=257$ , and this determines the transform length we need to use. Because we want to use the FFT, we are restricted topower-of-two transform lengths. We need to choose any FFT length that exceeds the required DFT length. As it turns out,256 is a power of two ( $2^8=256$ ), and this length just undershoots our required length. To use frequency domain techniques, we must uselength-512 fast Fourier transforms.

[link] shows the input and the filtered output. The MATLAB programs that compute the filteredoutput in the time and frequency domains are

An interesting signal processing aspect of this example is demonstrated at the beginning and end of theoutput. The ramping up and down that occurs can be traced to assuming the input is zero before it begins and after itends. The filter "sees" these initial and final values as the difference equation passes over the input. These artifacts canbe handled in two ways: we can just ignore the edge effects or the data from previous and succeeding years' last and firstweek, respectively, can be placed at the ends.