Free Books

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).

Next Section:
Inverse DFT and the DFT Filter Bank Sum
Previous Section:
System Diagram of the Running-Sum Filter Bank