Using the DFT as a Filter: Correcting a Misconception

• Tips and Tricks

I have read, in some of the literature of DSP, that when the discrete Fourier transform (DFT) is used as a filter the process of performing a DFT causes an input signal's spectrum to be frequency translated down to zero Hz (DC). I can understand why someone might say that, but I challenge that statement as being incorrect. Here are my thoughts.

Using the DFT as a Filter
It may seem strange to think of the DFT as being used as a filter but there are a number of applications where this is done. For example, we can use the DFT to implement a bank of bandpass filters used in some sort of subband coding application, or use the DFT to implement a bank of bandpass filters for a straightforward spectrum analysis application such as a weighted overlap and add (WOLA) spectrum analyzer [1-5].

The general process of using the DFT as a filter is illustrated in Figure 1. An N-sample x(n) input sequence enters a tapped-delay line, is multiplied by a w(k) window sequence, and the u(n) product sequence is applied to an N-point DFT. Windowing with a w(k) sequence is optional, based on the our DFT filterbank application. For “rectangular windowing” the w(k) window sequence would be all ones and the multiplication by the w(k) sequence in Figure 1 becomes unnecessary.

If the w(k) window sequence is all ones, as each new x(n) sample enters the tapped-delay line we compute a new output sample for each of the DFT's X_m(n) output sequences. The subscripted m index in X_m(n) represents the mth DFT bin where m is in the range 0 ≤ m ≤ N-1. Looking at the m = 2 DFT bin, inside the oval of Figure 1 shows a hypothetical, complex-valued, X₂(n) time-domain output sequence.

In viewing the computation of a single DFT bin output as the output of a tapped-delay line finite impulse response (FIR) filter, we can show the Figure 1 u(n) sequence as the input to an N-point DFT, as shown in Figure 2. The dashed rectangle in Figure 2 shows the computations needed to compute a single mth bin output sequence X_m(n).

An Easy Mistake to Make
Again, the misconception I referred to at the beginning of this blog, regarding the use of the DFT as a filterbank of bandpass filters as shown in Figure 1 or as a single bandpass filter as shown in Figure 2, is that when used as a filter the DFT translates spectral energy down in frequency such that all of the DFT's mth bin output signals are centered at zero Hz (DC). I believe this is not true, and here's why:

You see, when implementing the standard N-point DFT equation,

we're correlating the e^-j2πnm/N twiddle factors with an x(n) input sequence. In an FIR implementation we're convolving the e^-j2πnm/N twiddle factors with an x(n) input sequence, and that means from an FIR filter viewpoint the order of the e^-j2πnm/N twiddle factor coefficients must be flipped relative to their order in a standard DFT. Figure 2 illustrates what I'm saying here. Notice in Figure 2 how the largest DFT twiddle factor coefficient e^{-j2π⋅(N-1)⋅m/N} is on the left side, and the smallest twiddle factor coefficient e^{-j2π⋅0⋅m/N} is on the right side, of Figure 2's tapped-delay line.

I've seen two Internet DSP tutorial websites, as well as a recently-published DSP textbook, that had the twiddle factors incorrectly reversed in order when the authors were discussing using the DFT as a filter. That is, they mistakenly had the e^{-j2π⋅0⋅m/N} twiddle factor coefficient on the left side of the tapped-delay line, ...and that's a VERY easy mistake to make. (I don't know if the Professor on Gilligan's Island or Sheldon Cooper on THE BIG BANG THEORY would make that mistake, but some people do.)

The critical point here is that the DFT twiddle factors in Eq. (1) comprise a negative-frequency complex exponential, while the twiddle factor coefficients in Figure 2 comprise a positive-frequency complex exponential.

Improper ordering of the DFT twiddle factors, when trying to perform a mathematical analysis of the Figure 2 FIR filter, leads to an incorrect equation for the frequency response of the DFT's mth bin FIR filter.

The Frequency Response of the DFT's mth Bin
As derived in the Appendix A, the frequency response of the mth bin of Figure 2's N-point DFT is:

where frequency variable ω is –π ≤ ω ≤ π measured in radians/sample. The |H_DFT(ω)| magnitude response of H_DFT(ω) is a sin(x)/x-like bandpass filter response centered at a frequency of:

That ω_cntr center frequency is the value of ω where the angle argument of the ratio's denominator equals zero in Eq. (2). The spectral magnitude |H_DFT(ω)| for N = 16 and m = 4 is shown in Figure 3(a). There we see that the main lobe of |H_DFT(ω)| is located at a frequency of ω_cntr = 2π4/16 = 0.5π radians/sample (one fourth of the input signal's sample rate measured in Hz). The linear phase response of this example H_DFT(ω)'s passband is given in Figure 3(b).

Figure 3(a) illustrates why we can treat consecutive time-domain output samples of a DFT's mth bin as the output of a complex bandpass filter.

A Simple Example
Figure 4 shows a simple example of how the DFT, used as a filter, does not induce frequency translation as some people claim. Figure 4(a) shows a sinusoidal u(n) input sequence whose frequency is f_s/16, where f_s is the u(n) sample rate is Hz. (There are 16 samples/cycle in u(n)). A block of N = 128 samples of sequence u(n) contains exactly eight sinusoidal cycles. The complex X₈(n) output of a 128-point DFT's m = 8 bin is shown in Figure 4(b). Each complex

X₈(n) = Real[X₈(n)] + jImag[X₈(n)]

sample in Figure 4(b) represents the output of the m = 8th bin of consecutive 128-point DFTs.

Notice how the real and imaginary parts of X₈(n) also contain 16 samples/cycle, as did the u(n) input sequence. NO frequency translation occurs in the DFT's X₈(n) bin time-domain output sequence!

Here's Where Frequency Translation Can Occur
In some applications of the DFT used as a filterbank, a frequency down-conversion does occur. Because Figure 2's X_m(n) output sequence is narrow in bandwidth relative to the bandwidth of the input u(n) sequence, some DFT filterbank practitioners decimate the X_m(n) sequence by N as shown in Figure 5. That decimation process frequency translates a DFT bin's X_m(n) spectral energy, originally centered at 2πm/N radians/sample, to be centered at zero Hz (DC).

The decimated-by-N X_m,dec(r) sequence in Figure 5 is:

and the output index r is r = 0,1,2,3,…. For example, the u(n) input sequence in Figure 4(a) is a sinusoid whose frequency is centered exactly at the m = 8 bin. If that u(n) sequence had been thousands of samples in length, decimating the real and imaginary parts of X₈(n) by N = 128 produces an all-ones sequence and an all-zeros sequence, respectively. If a lengthy u(n) sequence's frequency had been ±Δ radians/sample above or below the m = 8 bin's center frequency, the decimated complex X8,dec(r) sequence would have a frequency of ±Δ radians/sample.

The interesting thing about the ʹfrequency translation through decimation by Nʹ process, shown in Figure 6, is that the spectral energy in any X_m(n) sequence is frequency translated to be centered at zero Hz regardless of the value of m. The top panel of Figure 6 shows the frequency translation if m is a positive integer. The bottom panel of Figure 6 shows the frequency translation if m is a negative integer.

Conclusion
To recap the main points of this blog we can say:

• Computing consecutive mth bin output samples of an N-point DFT can be viewed as a tapped-delay line complex-valued FIR filter as shown in Figure 2.
• The linear phase frequency response of the DFT's mth bin filter is a sin(x)/x-like passband centered at 2πm/N radians/sample (mf_s/N Hz).
• When a new mth bin output sample is computed, upon the arrival of each new delay line input sample, the DFT's mth bin output sequence exhibits no frequency translation.

I end this blog by pointing out that what I haven't yet figured out is “How can the Figure 2 FIR bandpass filter have linear phase when its coefficients are not symmetrical?”

Postscript (August 2015)

I have an answer to the above linear phase bandpass filter question at:

https://www.dsprelated.com/showarticle/808.php

References
[1] Lyons, R. Understanding Digital Signal Processing, 2nd Ed. & 3rd Ed., Prentice Hall Publishing, Hoboken, NJ, 2010, Chap. 13, Section 13.20.

[2] Crochiere, R., and Rabiner, L. Multirate Digital Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1983 pp. 315-319.

[3] http://www.rfel.com/download/W05012_Architectures_for_SDR_Channelisation.pdf

[4] http://www.onsemi.com/pub_link/Collateral/AND8382-D.PDF

[5] http://www.onsemi.cn/site/pdf/ICECS2003_ASR.pdf

Appendix A [Derivation of Eq. (2)]
We can determine the frequency response of the mth bin of an N-point DFT by treating the Figure 2 block diagram as a simple tapped-delay line finite impulse response (FIR) filter. Doing so we see that the coefficients of the Figure 2 FIR filter are:

where time index p is 0 ≤ p ≤ N-1. Because e^-j2πmN/N = 1, we can simplify Eq. (A-1) as:

Next we use the discrete-time Fourier transform (DTFT) definition to find the H_DFT(ω) frequency response of the h_DFT(p) coefficients as:

where frequency variable ω is –π ≤ ω ≤ π measured in radians/sample. The summation in Eq. (A-3) is a geometric series, so we can set Eq. (A-3) equal to:

Because e^j2πm =1, we have:

Factoring out the half-angled exponentials e^-jNω/2 and e^{j(πm/N-ω/2)}, we have:

Using Euler's identity, e^jα - e^-jα = 2jsin(α), we arrive at

Canceling common factors and rearranging terms, the frequency response of our N-point DFT's mth bin bandpass filter is:

Sign in