Sign in

Not a member? | Forgot your Password?

Search blogs

Search tips

Find us on Facebook!





Free PDF Downloads

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

C++ Tutorial

Introduction of C Programming for DSP Applications

Fixed-Point Arithmetic: An Introduction

Cascaded Integrator-Comb (CIC) Filter Introduction

Articles by category

IIR Filter Design Software

See Also

Embedded SystemsFPGA

Blogs > Rick Lyons > How Not to Reduce DFT Leakage


Rick Lyons (contact)
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?

  




Pageviews: 1367

How Not to Reduce DFT Leakage

Posted by Rick Lyons on May 23 2012 under Tips and Tricks   

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 re(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 re(n) time sequence.

According to the paper's author, when re(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 re(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 fs 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



Rate this article:
5
Rating: 5 | Votes: 4
 
   
 
posted by Rick Lyons
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: The History of CIC Filters: The Untold Story
Next post by Rick Lyons: How Discrete Signal Interpolation Improves D/A Conversion
all articles 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
Reply
Sorry, you need javascript enabled to post any comments.
mboigner
Said:
Hi Rick, Thx for your anti-recommentation :) Does anyone know if this fairy tale paper made it into a IEEE magazine? If yes, I really would be disappointed.
2 years ago
0
Reply
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.
2 years ago
0
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 ...
2 years ago
0
Reply
Sorry, you need javascript enabled to post any comments.
grh
Replied:
Hey! Are you also willing to share your thoughts here in this discussion? Or is there any other online resource where you share your steps? I would be interested too... Thanks and have a nice day!
2 years ago
0
niarn
Replied:
Hi grh, Maybe you can ask Rick if he can update his blog with the 'steps'. Otherwise, if you write you email I can send you a short pdf document.
2 years ago
0
grh
Replied:
Hey niarn! My mail is grh _ät_ gmx _dot at. Many thanks!
2 years ago
0
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.
2 years ago
0
Reply
Sorry, you need javascript enabled to post any comments.
Rick Lyons
Replied:
Hi niarn, I'd like to learn more about the 'steps' you used in finding the magnitude squared of the Fourier transform of y[n]. Would you please send me an E-mail at:? [-Rick-]
2 years ago
0
niarn
Replied:
Thought it would be easy but I haven't been successful in finding your email address. If you want I can upload a short document and send you a link...
2 years ago
0
Rick Lyons
Replied:
Hi niarn, I entered my E-mail address in my last comment, but it showed up as a question mark. I'll try again. My E-mail address is: R.Lyons@ieee.org [-Rick-]
2 years ago
0
Sorry, you need javascript enabled to post any comments.