DSPRelated.com
Free Books
   Free Books    Spectral Audio Signal Processing  

The DFT Filter Bank

To obtain insight into the operation of filter banks implemented using an FFT, this section will derive the details of the DFT Filter Bank. More general STFT filter banks are obtained by using different windows and hop sizes, but otherwise are no different from the basic DFT filter bank.

The Discrete Fourier Transform (DFT) is defined by [264]

$\displaystyle X(\omega_k) = \sum_{n=0}^{N-1} x(n) e^{-j\omega_k n}$ (10.4)

where $ x(n)$ is the input signal at time $ n$ , and $ \omega_k\isdef 2\pi k/N$ . In this section, we will show how the DFT can be computed exactly from a bank of $ N$ FIR bandpass filters, where each bandpass filter is implemented as a demodulator followed by a lowpass filter. We will then find that the inverse DFT is computed by remodulating and summing the output of this filter bank. In this way, the DFT filter bank is shown to be a perfect-reconstruction filter bank. The STFT is then an extension of the DFT filter bank to include non-rectangular analysis windows $ w$ and a downsampling factor $ R$ .

The Running-Sum Lowpass Filter

Perhaps the simplest FIR lowpass filter is the so-called running-sum lowpass filter [175]. The impulse response of the length $ N$ running-sum lowpass filter is given by

$\displaystyle h(n) \isdef \left\{\begin{array}{ll} 1, & n=0,1,2,...,N-1 \\ [5pt] 0, & \hbox{otherwise.} \\ \end{array} \right. \protect$ (10.5)

Figure 9.10: Black-box view of application of the running-sum lowpass filter.
\includegraphics{eps/blackbox}

Figure 9.10 depicts the generic operation of filtering $ x(n)$ by $ h(n)$ to produce $ y(n)$ , where $ h(n)$ is the impulse response of the filter. The output signal is given by the convolution of $ x$ and $ h$ :

\begin{eqnarray*} y(n) &=& (h\ast x)(n) \isdef \sum_{m=-\infty}^{\infty} h(m) x(n-m) = \sum_{m=0}^{N-1} x(n-m)\\ &=& x(n) + x(n-1) + \cdots + x(n-N+1). \end{eqnarray*}

In this form, it is clear why the filter (9.5) is called ``running sum'' filter. Dividing it by $ N$ , it becomes a ``moving average'' filter, averaging the most recent $ N$ input samples.

The transfer function of the running-sum filter is given by [263]

$\displaystyle H(z) = 1 + z^{-1}+ \cdots + z^{-N+1} = \frac{1-z^{-N}}{1-z^{-1}},$ (10.6)

so that its frequency response is

\begin{eqnarray*} H(e^{j\omega}) &=& \frac{1-e^{-j\omega N}}{1-e^{-j\omega }} = \frac{e^{-j\omega N/2}}{e^{-j\omega /2}} \frac{\sin(\omega N/2)}{\sin(\omega /2)}\\ [10pt] &\isdef & Ne^{-j\omega(N-1)/2} \hbox{asinc}_N(\omega ). \end{eqnarray*}

Recall that the term $ e^{-j\omega(N-1)/2}$ is a linear phase term corresponding to a delay of $ (N-1)/2$ samples (half of the FIR filter order). This arises because we defined the running-sum lowpass filter as a causal, linear phase filter.

We encountered the ``aliased sinc function''

$\displaystyle \hbox{asinc}_N(\omega ) \isdef \frac{\sin(\omega N/2)}{N\cdot\sin(\omega /2)}$ (10.7)

previously in Chapter 5 (§3.1.2) and elsewhere as the Fourier transform (DTFT) of a sampled rectangular pulse (or rectangular window).

Note that the dc gain of the length $ N$ running sum filter is $ N$ . We could use a moving average instead of a running sum ( $ h \leftarrow h/N$ ) to obtain unity dc gain.

Figure: Running-sum amplitude response for $ N=5$
\includegraphics[width=4in]{eps/sincabs}

Figure 9.11 shows the amplitude response of the running-sum lowpass filter for length $ N=5$ . The gain at dc is $ N=5$ , and nulls occur at $ \omega = \pm2\pi/5$ and $ \pm4\pi/5$ . These nulls occur at the sinusoidal frequencies having respectively one and two periods under the 5-sample ``rectangular window''. (Three periods would need at least $ 2\cdot 3 = 6$ samples, so $ 6\pi/5$ doesn't ``fit''.) Since the pass-band about dc is not flat, it is better to call this a ``dc-pass filter'' rather than a ``lowpass filter.'' We could also call it a dc sampling filter.10.1

Modulation by a Complex Sinusoid

Figure: System diagram for complex demodulation (frequency-shifting) by $ -\omega _c$ .
\includegraphics{eps/modulation}

Figure 9.12 shows the system diagram for complex demodulation.10.2The input signal $ x(n)$ is multiplied by a complex sinusoid to produce the frequency-shifted result

$\displaystyle x_c(n) = e^{-j\omega_c n} x(n).$ (10.8)

Given a signal expressed as a sum of sinusoids,

$\displaystyle x(n) = \sum_{k=1}^{N_x} a_k e^{j\omega_k n}, \quad a_k\in{\bf C},$ (10.9)

then the demodulation produces

$\displaystyle x_c(n) \isdef x(n) e^{-j\omega_c n} = \sum_{k=1}^{N_x} a_k e^{j(\omega_k -\omega_c) n}.$ (10.10)

We see that frequency $ \omega_k$ is down-shifted to $ \omega_k-\omega_c$ . In particular, frequency $ \omega_c$ (the ``center frequency'') is down-shifted to dc.

Making a Bandpass Filter from a Lowpass Filter

Figure 9.13: Construction of a bandpass filter using demodulation, lowpass filtering, and remodulation.
\includegraphics{eps/BPF}

Figure 9.13 shows how a bandpass filter can be made using a lowpass filter together with modulation. The input spectrum is frequency-shifted by $ -\omega _c$ , lowpass filtered, then frequency-shifted by $ +\omega_c$ , thereby creating a bandpass filter centered at frequency $ \omega_c$ . From our experience with rectangular-window transforms (Fig.9.11 being one example), we can say that the bandpass-filter bandwidth is equal to the main-lobe width of the aliased sinc function, or $ 4\pi/N$ radians per sample (measured from zero-crossing to zero-crossing).

Uniform Running-Sum Filter Banks

Using a length $ N$ running-sum filter, let's make $ N$ bandpass filters tuned to center frequencies

$\displaystyle \omega_k\isdef k\frac{2\pi}{N}, \quad k=0,1,2,\ldots,N-1.$ (10.11)

Since the bandwidths, as defined, are $ 4\pi/N$ , the filter pass-bands overlap by 50%. A superposition of the bandpass frequency responses for $ N=5$ is shown in Fig.9.14. Also shown is the frequency-response sum, which we will show to be exactly constant and equal to $ N$ . This gives our filter bank the perfect reconstruction property. We can simply add the outputs of the filters in the filter bank to recreate our input signal exactly. This is the source of the name Filter-Bank Summation (FBS).

Figure: Example filter-bank channel frequency responses for $ N=5$
\includegraphics[width=3in]{eps/sincbank}

System Diagram of the Running-Sum Filter Bank

Figure 9.15: DFT Filter Bank.
\includegraphics{eps/BPFB}

Figure 9.15 shows the system diagram of the complete $ N$ -channel filter bank constructed using length $ N$ FIR running-sum lowpass filters. The $ k$ th channel computes:

$\displaystyle y_k(n)$ $\displaystyle =$ $\displaystyle (h\ast x_k)(n) = \sum_{m=0}^{N-1}h(m)x_k(n-m)$  
  $\displaystyle =$ $\displaystyle (x_k\ast h)(n) = \sum_{m=n-(N-1)}^{n}x_k(m)h(n-m)$  
  $\displaystyle =$ $\displaystyle \sum_{m=n-(N-1)}^{n}x(m)e^{-j\omega_k m }\hbox{\sc Shift}_{n,m}(\hbox{\sc Flip}(h))$  
  $\displaystyle =$ $\displaystyle \sum_{m=n-(N-1)}^{n}x(m)e^{-j\omega_k m } \protect$ (10.12)

DFT Filter Bank

Recall that the Length $ N$ Discrete Fourier Transform (DFT) is defined as

$\displaystyle X(k) \isdef \sum_{n=0}^{N-1} x(n) e^{-j2\pi nk/N}$ (10.13)

Comparing this to (9.12), we see that the filter-bank output $ y_k(n)$ , $ k=0,1,\ldots,N-1$ , is precisely the DFT of the input signal when $ n=N-1$ , i.e.,

$\displaystyle \zbox {X(k) = y_k(N-1)}.$ (10.14)

In other words, the filter-bank output at time $ n=N-1$ (the set of $ N$ samples $ y_k(N-1)$ for $ k=0,1,2,\ldots,N-1$ ), equals the DFT of the first $ N$ samples of $ x$ ($ x(n)$ , $ n=0,\ldots,N-1$ ). That is, taking a snapshot of all filter-bank channels at time $ N-1$ yields the DFT of the input data from time 0 through $ N-1$ .

More generally, for all $ n$ , we will call Fig.9.15 the DFT filter bank. The DFT filter bank is the special case of the STFT for which a rectangular window and hop size $ R=1$ are used.

The sliding DFT is obtained by advancing successive DFTs by one sample:

$\displaystyle X_n(k) \isdef \sum_{m=0}^{N-1} x(n+m) e^{-j2\pi mk/N}$ (10.15)

When $ n=LN-1$ for any integer $ L$ , the Sliding DFT coincides with the DFT filter bank. At other times, they differ by a linear phase term. (Exercise: find the linear phase term.) The Sliding DFT redefines the time origin every sampling period (each modulation term within the DFT starts at time 0 for each transform), while the DFT Filter Bank does not redefine the time origin (modulation terms are ``free running'' as they would be in an analog filter bank). Since ``DFT time'' repeats every $ N$ samples, the two treatments coincide every $ N$ samples (i.e., $ e^{j\omega_k(n+LN)}=e^{j\omega_kn}$ for every integer $ L$ ).

When $ N$ is a power of 2, the DFT can be implemented using a Cooley-Tukey Fast Fourier Transform (FFT) using only $ {\cal O}(N\log_2(N))$ operations per transform. By keeping track of the linear phase term (an $ {\cal O}(N)$ modification), a DFT Filter Bank can be implemented efficiently using an FFT. Uniform FIR filter banks are very often implemented in practice using FFT software such as fftw.

Note that the channel bandwidths are narrow compared with half the sampling rate (especially for large $ N$ ), so that the filter bank output signals $ y_k(n)$ are oversampled, in general. We will later look at downsampling the channel signals $ y_k(n)$ to obtain a ``hopping FFT'' filter bank. ``Sliding'' and ``hopping'' FFTs are special cases of the discrete-time Short Time Fourier Transform (STFT). The STFT normally also uses a window function other than the rectangular window used in this development (the running-sum lowpass filter).

Inverse DFT and the DFT Filter Bank Sum

The Length $ N$ inverse DFT is given by [264]

$\displaystyle x(n) = \frac{1}{N}\sum_{k=0}^{N-1} X(k) e^{j2\pi nk/N}, \quad n=0,1,2,\ldots,N-1.$ (10.16)

This suggests that the DFT Filter Bank can be inverted by simply remodulating the baseband filter-bank signals $ y_k(n)$ , summing over $ k$ , and dividing by $ N$ for proper normalization. That is, we are led to conjecture that

$\displaystyle x(n-N+1) = \frac{1}{N}\sum_{k=0}^{N-1} y_k(n) e^{j2\pi nk/N}, \quad n=0,1,2,\ldots\,.$ (10.17)

This is in fact true, as we will later see. (It is straightforward to show as an exercise.)

Next Section:
FBS Window Constraints for R=1
Previous Section:
STFT Filter Bank