Tweets by @dsprelated

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

Introduction of C Programming for DSP Applications

Richard Lyons is a Contracting Systems Engineer and Lecturer at Besser Associates, Mountain View, Calif. He has written over 30 articles and conference papers on DSP top...show full bio

**Would you like to be notified by email when Rick Lyons publishes a new blog?**

Follow @DSPRelated

This blog describes a technique to reduce the effects of spectral leakage when using the discrete Fourier transform (DFT).

In late April 2012 there was a thread on the comp.dsp newsgroup discussing ways to reduce the spectral leakage problem encountered when using the DFT. One post in that thread caught my eye [1]. That post referred to a website presenting a paper describing a DFT leakage method that I'd never heard of before [2]. (Of course, not that I've heard everything there is to hear about DFT leakage.)

The paper's author presents a method for reducing spectral leakage when an *r*(*n*) input sequence is applied to the DFT. In that method, a left-to-right time-flipped version of *r*(*n*) is appended to the original *r*(*n*) sequence creating a new *r*_{e}(*n*) sequence with twice as many samples as *r*(*n*). As I understand the idea, the below Figure 1(a) shows an example of a 32-sample *r*(*n*) time sequence and Figure 1(b) shows the 'leakage reduction' method's resulting 'data-flipped' 64-sample *r*_{e}(*n*) time sequence.

According to the paper's author, when *r*_{e}(*n*) is applied to the DFT, its DFT results will exhibit reduced spectral leakage compared to the DFT results of the original *r*(*n*). In addition, the author stated that the DFT of the *r*_{e}(*n*) sequence will have the same spectrum as the DFT of the original *r*(*n*) sequence. Reading those later words made me suspicious. As it turned out, many things in that paper bothered me—bothered me a lot—but I won't bore you with the details.

Wait a second, ... I will mention one thing that is truly important. The paper's author stated that the purpose of windowing is to ensure that the first and last samples of a windowed time sequence are zero-valued. That statement is not correct. The fact that the first and last samples of a windowed time sequence are zero-valued is an effect of windowing, not the goal of windowing. The goal of windowing is to reduce the amplitude discontinuities in a circular version of a DFT's input sequence. Stated in different words, if you created a repetitive version of the windowed time sequence, by repeating the windowed sequence over and over, the goal of windowing is to reduce the amplitude discontinuities in that repetitive sequence. Now in fairness, I'll admit that the author's mistaken conclusion about the purpose of windowing is an easy mistake to make.

What troubled me most was that in my Matlab simulations of that data-flipping spectral leakage reduction method is that I found a case where it does not work properly! For example, when a 183 Hz sinusoidal *r*(*n*) was used as the input to the data-flipping leakage reduction method the resulting frequency response is that shown by the solid curve in Figure 2. (The f_{s} sample rate of *r*(*n*) was 1000 Hz.) For reference purposes, the dashed curve in Figure 2 is the spectrum of *r*(*n*) windowed by a Hanning window. Notice two things: (1) the sidelobe levels of the data-flipping scheme are far higher than the sidelobes in the Hanning windowed spectrum; (2) the troubling dip in the mainlobe of the data-flipping method's frequency response.

I believe the problem with the paper's data-flipping leakage reduction method is as follows: Where the frequency transforms of the standard Hanning and Hanning windows are not dependent on the frequency of a time sequence to which they're applied, the paper's data-flipping leakage reduction method DOES depend on the frequency of an input *r*(*n*) sequence.

So, ...if I understand the paper's technique correctly, I'd never recommend that it be used in practice.

**Postscript:**

One of the subscribers here, nairen, posted a comment giving the frequency response of the 'data-flipping' process. A PDF file of nairen's very clever derivation can be downloaded by clicking here.

**References**

[1] From: "Lightbulb85", Subject: Re: Reducing Spectral Leakage of Rectangular Window?, Date: Thu, 26 Apr 2012.

[2] http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-6221.pdf

Richard Lyons is a Contracting Systems Engineer and Lecturer at Besser Associates, Mountain View, Calif. He has written over 30 articles and conference papers on DSP topics, and authored Amazon.com's top selling DSP book "Understanding Digital Signal Processing, 3rd Ed.". He served as an Associate Editor at IEEE Signal Processing Magazine, for nine years, where he created and edited the "DSP Tips & Tricks" column. Lyons is the editor of, and contributor to, the book "Streamlining Digital Signal Processing-A Tricks of the Trade Guidebook, 2nd Ed." (Wiley & Sons, 2012).

Previous post by Rick Lyons:

Next post by Rick Lyons:

Comments / Replies

Shep

Said:

Rick, I had heard this technique described but never read the original SLAC paper. Thank you for the clear debunking.

2 years ago

0

Sorry, you need javascript enabled to post any comments.

Rick Lyons

Replied:

Hi mboigner,
I hadn't thought to check if this technique was published in an IEEE publication. But darned if you're not correct. I just learned this 'leakage reduction' method was described in the paper:
"Gibbs phenomenon removal and digital
filtering directly through the fast Fourier
transform", IEEE Transactions on Signal Processing, Feb 2001, Vol. 49, Issue: 2, pp. 444-448.

grh

Said:

Thanks for this article!
I also wanted to analyze this method, but had no time so far ...
Cheh Pan also mentions in his paper
"Gibbs Phenomenon Removal and Digital Filtering Directly through the Fast Fourier Transform"
that there is a "second-order end effect", see chapter V. Discussion:

However, if the turning angle is too sharp (less than or near 90Â°), it may still cause a slope interruption, and the end effect may appear.The next sentences are:

On the other hand, the slope discontinuity at the first point can be treated by padding equal points to the end of the new waveform to ensure a zero slope there. In data flipping, this makes the even function no longer symmetrical but will not affect its periodicity, although the period is elongated, and the spectral resolution is further refined. Padding equal points to the end is useful because it allows the filter to accept any FFT algorithms for any truncation lengths.So maybe it would be worth trying to append values to the end of the waveform, as also described in his patent http://www.patentgenius.com/patent/5574674.html (picture 1). Furthermore it would be interesting to see, if these artifacts also remain when using the Baseline Tilting Method ...

Sorry, you need javascript enabled to post any comments.

niarn

Said:

Hi Rick,
Let x[n] be a real sequence of length N with Fourier transform X(w) = U + j*V, where U and V are the real and imaginary parts of the Fourier transform. The magnitude squared of the Fourier transform is then given by |X(w)|^2 = U^2 + V^2.
If we then form the sequence (as you describe it)
x[n] , for n=0..N-1
y[n] =
x[2N-n-1] , for n=N..2N-1
then after some steps you can find that the magnitude squared of the Fourier transform of y[n] is given by
[U cos(Aw) + V sin(Aw)]^2
|Y(w)|^2 = [U^2 + V^2]------------------------- , where A=(2N-1)/2
[U^2 + V^2]
Clearly, x[n] and y[n] does not have the same spectrum. Their 'envelopes' are the same. The data flipping operation has a comb-like filtering effect on the spectrum of x[n]. There will be N equally spaced nulls in the range [0; pi]. What you might have observed is that one of these nulls are located at or close to the frequency you expected to see.

Sorry, you need javascript enabled to post any comments.

Sorry, you need javascript enabled to post any comments.