To: file

From: Jon Hagen

Date: April 17, 2003

Subject: Polyphase and weighted overlap-add filter bank architectures

Reference: Crochiere & Rabiner, "Multirate Digital Signal Processing"

Summary: The polyphase filter bank and overlap-add algorithms are two efficient implementations of a DFT filterbank..

1. Introduction

Let the circuit below represent the operations carried out by one frequency channel of a prototype filter bank that Crochiere & Rabiner refer to as a DFT filter bank, though these particular DFT filters might better be called 'generalized DFT filters.' The first step is a conversion to baseband; the input sequence, x(n) is multiplied by a complex "LO" sequence, exp(-j2 nk/K), which translates the input band, shifting the frequency k/N (times the sampling rate) down to DC. The resulting baseband signal is then low-pass filtered to define the desired bandpass shape. (Note that the input signal can be complex, e.g., the I and Q components of a bandpass signal that has been converted to base band).

Figure 1. kth frequency channel of a generalized DFT filter bank.

Here the low pass filtering is being done by an FIR filter, i.e. a sum of weighted taps from a digital delay line of length H.. The greater the number of taps, the better the filter can approximate a desired filter shape, e.g. rectangular, Gaussian, or whatever. Since the filtered sequence has less bandwidth than the input signal, it is over-sampled and can be decimated without losing information. Here M denotes the decimation factor; every Mth output is picked off to form the low pass output sequence, x(k,m), where k denotes the frequency channel.and m is the output sample number. In this case, this filter produces an output sample for every K input samples. A bank of these filters produces a block of output samples for every K input samples. We will consider only the common case of 'critical sampling' where M=K..

A particular case of this DFT filter channel is when the filter tap weights are all unity. This is just the 'standard' DFT, ie, one channel of a standard FFT. While the FFT is a particularly efficient algorithm for implementing a bank of standard DFT filters, these filters have a sin(x)/x response causing 'leakage' between nearby channels. The shape can be improved by windowing the input data, i.e. moving the multiplier block downstream to a position just ahead of the decimator. This allows for arbitrary coefficients. But the window length is then no longer than the transform length, which broadens the filter bandwidth unless the transform length is increased. Moreover, in a random signal situation, windowing also forces one to do transforms of overlapping sequences of data in order not to increase the integration time needed to reach a desired variance.

In general, we would like to carry out the operation as shown in Figure 1, with an arbitrary filter length, H. Successive data blocks are shown schematically below in Figure 2.

Figure 2. Data moving to the right through the FIR filter of Figure 1.

Note that, because the filter window,H, is longer than the transform length, M, the blocks processed by the filter do indeed overlap.

2. Polyphase Architecture

The processing needed to produce the output value of the kth frequency channel for the mth data block can be see by inspection to be

where WM (n)=exp(2 i n/M). Now, since WM(-k[mM+n]) = WM(-kmM)WM(-kn), and since

WK(-kmM) =1, we have

There is nothing new to this point, but now let us express n as = rM + where the index r goes from 0 to R-1, where R= H/M, and the index goes from 0 to M-1. Using this notation we have

Note that this is just a standard DFT of the bracketed expression, so the transform can be carried out efficienctly using the FFT algorithm. For each value of , the bracketed expression is a FIR filter operating successively delayed 'phases' of the input data. Obviously one chooses H so that R = H/M is an integer in order that the FIR have an integral number of taps. A schematic diagram of this algorithm is shown below in Figure 3. Note the way in which the tap weights of the prototype filter are distributed among the shorter FIR filters at each input to the FFT block.

Figure 3. Polyphase implementation of DFT Filter

3. Weighted Overlap-Add (WOLA) Architecture

Another way to look at the bracketed term in Equation 3 is that, for each value of , it is the sum of R=H/M products, each product being a filter weight times an input data point. Figure 4 shows another arrangement that produces this sum of R products. The input data moves through a cascade of R-1 shift registers, each of length M. The input data and the output of each of these M-length registers feeds a multiplier. There are R multipliers. The other input of each multiplier is fed a cyclic version of the the appropriate 1/Rth section of the tap weight sequence. This front-
end circuitry supplies an FFT with serial data having the same rate as the input signal. The output of the FFT, however corresponds to data processed through a set of steep sided filters, rather than through a set of filters whose bandpass is given by sin(x)/x.

Figure 4. Weighted Overlap-Add Structure