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$

System Diagram of the Running-Sum Filter Bank

Figure 9.15: DFT Filter Bank.

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

Specific Windows

  • Recall that the rectangular window transform is $ \hbox{\sc Nyquist}(2\pi/M)$ , implying the rectangular window itself is $ \hbox{\sc Cola}(M)$ , which is obvious.

  • The window transform for the Hamming family is $ \hbox{\sc Nyquist}(4\pi/M)$ , implying that Hamming windows are $ \hbox{\sc Cola}(M/2)$ , which we also knew.

  • The rectangular window transform is also $ \hbox{\sc Nyquist}(K2\pi/M)$ for any integer $ 1\leq K\leq M/2$ , implying that all hop sizes given by $ R=M/K$ for $ K=1,2,\ldots,M/2$ are COLA.

  • Because its side lobes are the same width as the sinc side lobes, the Hamming window transform is also $ \hbox{\sc Nyquist}(K2\pi/M)$ ,for any integer $ 2\leq K\leq M/2$ , implying hop sizes $ R=M/K$ are good, for $ K=2,\ldots,M/2$ . Thus, the available hop sizes for the Hamming window family include all of those for the rectangular window except one ($ R=M$ ).

The Nyquist Property on the Unit Circle

As a degenerate case, note that $ R=1$ is COLA for any window, while no window transform is $ \hbox{\sc Nyquist}(2\pi)$ except the zero window. (since it would have to be zero at dc, and we do not consider such windows). Did the theory break down for $ R=1$ ?

Intuitively, the $ \hbox{\sc Nyquist}(2\pi/R)$ condition on the window transform $ W(\omega)$ ensures that all nonzero multiples of the time-domain-frame-rate $ 2\pi/R$ will be zeroed out over the interval $ [-\pi,\pi)$ along the frequency axis. When the frame-rate equals the sampling rate ($ R=1$ ), there are no frame-rate multiples in the range $ [-\pi,\pi)$ . (The range $ [0,2\pi)$ gives the same result.) When $ R=2$ , there is exactly one frame-rate multiple at $ -\pi$ . When $ R=3$ , there are two at $ \pm 2\pi/3$ . When $ R=4$ , they are at $ -\pi$ and $ \pm\pi/2$ , and so on.

We can cleanly handle the special case of $ R=1$ by defining all functions over the unit circle as being $ \hbox{\sc Nyquist}(2\pi)$ when there are no frame-rate multiples in the range $ [-\pi,\pi)$ . Thus, a discrete-time spectrum $ W(\omega), \omega\in[-\pi,\pi)$ is said to be $ \hbox{\sc Nyquist}(2\pi/K)$ if $ W(r 2\pi/K)=0$ , for all $ \vert r\vert=1,2,\ldots,\left\lfloor K/2\right\rfloor $ , where $ \left\lfloor x\right\rfloor $ (the ``floor function'') denotes the greatest integer less than or equal to $ x$ .

Next Section:
Downsampled STFT Filter Bank
Previous Section:
Making a Bandpass Filter from a Lowpass Filter