DSP Tricks: Frequency Domain Windowing
There's an interesting technique for minimizing the calculations necessary to implement windowing of fast fourier transform (FFT) input data to reduce spectral leakage.
There are times when we need the FFT of unwindowed time domain data, while at the same time we also want the FFT of that same time-domain data with a window function applied.
In this situation, we don't have to perform two separate FFTs. We can perform the FFT of the unwindowed data and then we can perform frequency-domain windowing on that FFT results to reduce leakage. Let's see how.
The commonly used Hanning and the Hamming windows can be expressed as ωHan(n) = 0.5 - 0.5 cos(2pi n/N) and ωHam(n) = 0.54 - 0.46 cos(2 pi n/N), respectively. They both have the general cosine function form of
for n = 0, 1, 2, ..., N-1. Looking at the frequency response of the general cosine window function, using the definition of the discrete fourier transform (DFT), the transform of Eq. (13-8) is
Equation 13-9 can be written as
Equation (13-10) looks pretty complicated, but it merely results in the superposition of three sin(x)/x functions in the frequency domain. Their amplitudes are shown in Figure 13-10 below.
|Figure 13-10 General cosine window frequency response amplitude.|
Notice that the two translated sin(x)/x functions have side lobes with opposite phase from that of the center sin(x)/x function. This means that α/2 times the mth bin output, minus β/2 times the (m-1)th bin output, minus β/2 times the (m+1)th bin output will minimize the sidelobes of the mth bin. This frequency domain convolution process is equivalent to multiplying the input time data sequence by the N-valued window function ω(n) in Eq. (13-8).
For example, let's say the output of the mth FFT bin is
and the outputs of its two neighboring bins are
Then frequency-domain windowing for the mth bin of the unwindowed X(m) is as follows:
To compute a windowed N-point FFT, X three-term(m), we can apply Eq. (13-11), requiring 4N additions and 3N multiplications, to the unwindowed N-point FFT result X(m) and avoid having to perform the N multiplications of time domain windowing and a second FFT with its Nlog2(N) additions and 2Nlog2(N) multiplications.
(In this case, we called our windowed results Xthree-term(m) because we're performing a convolution of a three-term W(m) sequence with the X(m) sequence.)
The neat situation here are the frequency-domain coefficients values, α and β, for the Hanning window. They're both 0.5, and the multiplications in Eq. (13-11) can be performed in hardware with two binary right shifts by a single bit for α = 0.5 and two shifts for each of the two β/2 = 0.25 factors, for a total of six binary shifts.
If a gain of four is acceptable, we can get away with only two left shifts (one for the real and one for the imaginary parts of X(m)) using
In application specific integrated circuit (ASIC) and field-programmable gate array (FPGA) hardware implementations, where multiplies are to be avoided, the binary shifts can be eliminated through hard-wired data routing. Thus only additions are necessary to implement frequency-domain Hanning windowing.
The issues we need to consider are which window function is best for the application, and the efficiency of available hardware in performing the frequency domain multiplications. Frequency-domain Hamming windowing can be implemented but, unfortunately, not with simple binary shifts.
Along with the Hanning and Hamming windows, there is a family of windows known as Blackman windows that provide further FFT spectral leakage reduction when performing frequency-domain windowing.
Blackman windows have five non-zero frequency-domain coefficients, and their use requires the following five-term convolution:
Table 13-3 below provides the frequency-domain coefficients for several common window functions.
|Table 13-3 Frequency-Domain windowing coefficients|
Let's end our discussion of the frequency-domain windowing trick by saying this scheme can be efficient because we don't have to window the entire set of FFT data; windowing need only be performed on those FFT bin outputs of interest to us.
Used with the permission of the publisher, Prentice Hall, this on-going series of articles is based on copyrighted material from "Understanding Digital Signal Processing, Second Edition" by Richard G. Lyons. The book can be purchased on line.
Richard Lyons is a consulting systems engineer and lecturer with Besser Associates. As a lecturer with Besser and an instructor for the University of California Santa Cruz Extension, Lyons has delivered digitasl signal processing seminars and training course at technical conferences as well at companies such as Motorola, Freescale, Lockheed Martin, Texas Instruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm, Honeywell, National Semiconductor, General Dynamics and Infinion.