A Remarkable Bit of DFT Trivia

Rick Lyons (contact)
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal ...show full bio

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

  

https://twitter.com/DSPRelated

Share on facebookShare on twitterShare on redditShare on google_plusone_shareShare on linkedin

Pageviews: 666

A Remarkable Bit of DFT Trivia

Posted by Rick Lyons on Dec 26 2013 under Tips and Tricks   

I recently noticed a rather peculiar example of discrete Fourier transform (DFT) trivia; an unexpected coincidence regarding the scalloping loss of the DFT. Here's the story.

DFT SCALLOPING LOSS
As you know, if we perform an N-point DFT on N real-valued time-domain samples of a discrete sine wave, whose frequency is an integer multiple of f_s/N (f_s is the sample rate in Hz), the peak magnitude of the sine wave's positive-frequency spectral component will be

where A is the peak amplitude of the time-domain sine wave. That phrase "whose frequency is an integer multiple of f_s/N" means that the sine wave's frequency is located exactly at one of the DFT's bin centers.

Now, if a DFT's input sine wave's frequency is between two DFT bin centers (a frequency equal to a non-integer multiple of f_s/N) the DFT magnitude of that spectral component will be less that the value in Eq. (1). Figure 1 illustrates this behavior where the variable m is the integer index of the DFT's bins. Figure 1(a) shows the frequency responses of individual DFT bins where, for simplicity, we only show the mainlobes (no sidelobes) of the DFT bins' responses.

What this means is that if we were to apply a sine wave to a DFT, and scan the frequency of that sine wave over multiple bins, the magnitude of the DFT's largest normalized magnitude sample value will follow the curve in Figure 1(b). That curve describes what is called the scalloping loss of a DFT [1]. We represent the maximum scalloping loss by the variable P. (By the way, the word scallop is not related to the seafood we sauté with butter and garlic. As it turns out, some window drapery, and table cloths, do not have linear borders. Rather they have a series of circular segments, or loops, of fabric defining their decorative borders. Those loops of fabric are called scallops.)

The Trivia
The peculiar trivia mentioned at the beginning of this blog is that the value P in Figure 1(b) is equal to the probability that a toothpick thrown on a wooden floor will land such that it crosses a line separating the floorboards as shown in Figure 2.

That is, the worst-case normalized DFT scalloping loss in Figure 1(b) is:

The only restriction on the toothpick throwing scenario is that the length of the toothpick be equal to the width of the parallel floorboards.

You might think this blog is a bit irrational. Maybe so, but it's not as irrational as the value P, which is:

If you are intrigued by this silly DFT trivia, you can investigate Eq. (2) further by searching the web for Buffon's needle.

(Disclosure: No taxpayer money was used, and no animals were injured, in the preparation of this blog.)

References
[1] fred harris, "On the use of windows for harmonic analysis with the discrete Fourier transform," Proceedings of the IEEE, Vol. 66, No. 1, pp. 51-83, January 1978.

This article is also available in pdf format

Rate this article:

Rating: 4.5 | Votes: 2

 

Tweet

   

 

posted by Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He was also an Associate Editor for the IEEE Signal Processing Magazine.

Previous post by Rick Lyons: Computing Translated Frequencies in Digitizing and Downsampling Analog Bandpass Signals
all articles by Rick Lyons