21 votes

What are some of the differences between DFT and FFT that make FFT so fast?

The naive implementation of an $N$-point DFT is basically a multiplication by a $N \times N$ matrix. This results in a complexity of $\mathcal{O}(N^2)$. One of the most common Fast Fourier Transform (...
anpar's user avatar
  • 957
20 votes
Accepted

Why do I have frequency leakage in DFT after zero padding if frequency resolution is fine?

This phenomenon has nothing to do with spectral leakage. What you are observing is the effect of zero padding. Given a number of samples $N$, there is a maximum possible frequency resolution $\Delta f$...
jojeck's user avatar
  • 11.1k
20 votes
Accepted

What is normalized frequency

Normalized frequency is frequency in units of cycles/sample or radians/sample commonly used as the frequency axis for the representation of digital signals. When the units are cycles/sample, the ...
Dan Boschen's user avatar
  • 51.4k
19 votes

What are some of the differences between DFT and FFT that make FFT so fast?

http://nbviewer.jupyter.org/gist/leftaroundabout/83df89a7d3bdc24373ea470fb50be629 DFT, size 16 FFT, size 16 The difference in complexity is pretty evident from that, isn't it? Here's how I ...
leftaroundabout's user avatar
17 votes
Accepted

Implementation of Wikipedia Equation for the DFT

You have a bug in ft2. You are incrementing i, and freq together. That's not how you want ...
Cedron Dawg's user avatar
  • 7,560
15 votes

Why calculate negative frequencies of DFT?

Mainly because its easier. The FFT is a specific algorithm to calculate the DFT. However, it only works if you calculate ALL frequencies (regardless if you want them or not). It takes in N complex ...
Hilmar's user avatar
  • 44.8k
15 votes

What are some of the differences between DFT and FFT that make FFT so fast?

Here is a picture to add to Robert's good answer demonstrating the "re-use" of operations, in this case for an 8 point DFT. The "Twiddle Factors" are represented in the diagram ...
Dan Boschen's user avatar
  • 51.4k
14 votes

Why is it a bad idea to filter by zeroing out FFT bins?

This question has also confused me for a long time. @hotpaw2's explanation is good. You may be interested in the simple experiment using matlab. https://poweidsplearningpath.blogspot.com/2019/04/...
Po-wei Huang's user avatar
14 votes
Accepted

What happens when N increases in N-point DFT

The length N of the DFT is the number of frequency points that will result in the DFT output. Zero padding will result in more frequency samples, however this does not increase frequency resolution, ...
Dan Boschen's user avatar
  • 51.4k
14 votes

Why does a longer observation time improve DFT resolution, but repeating a signal does not?

Why is this not equivalent to simply observing the signal for 1 period, and then paste it together N times? It's only equivalent if certain conditions are met. Let's look at a single sine wave with ...
Hilmar's user avatar
  • 44.8k
13 votes
Accepted

Bandwidth of an entire song

First of all, kudos to you: I appreciate the effort and thinking you've managed to articulate in your question. The DFT is a mathematical tool. As such, the parameters used to compute it can hide or ...
Jdip's user avatar
  • 6,055
11 votes

Applying DFT twice does not actually reverse an array. Instead, the first element stays in place while the rest of the array is reversed. Why?

The sequence is exactly what you should expect: $$x[-n]=x[N-n]\tag{1}$$ Clearly, for $n=0$ $x[n]$ and $x[-n]$ have the same value. It seems like you were expecting to see the sequence $x[N-1-n]$ ...
Matt L.'s user avatar
  • 90k
11 votes

Why does a longer observation time improve DFT resolution, but repeating a signal does not?

Why is this not equivalent to simply observing the signal for 1 period, and then paste it together N times? Because that statement presupposes that you already know how long one period is. If you do ...
TimWescott's user avatar
  • 12.7k
11 votes
Accepted

Fourier transform of modulus of sum of sines

$$\begin{align*}\mathscr{F}\left\{x(t)\right\} &= \mathscr{F}\left\{\left|\cos\left(\omega_0t\right)+\cos\left(\omega_1t\right)\right|\right\}\\ \\ &= 2 \mathscr{F}\left\{\left|\cos\left(\...
Andy Walls's user avatar
  • 2,710
11 votes

Is the negative spectrum (by DFT) of a real signal "needed" to reconstruct it?

is, in fact, the mirrored spectrum needed to reconstruct the signal? No, and yes. If I give you a spectrum with points from $n = 0$ to $n = \frac N 2$ and I tell you the original signal was real, ...
TimWescott's user avatar
  • 12.7k
11 votes
Accepted

Why do sinusoids have DFT magnitudes of N / 2 while we typically normalize by N?

The DFT is providing the coefficients of the basis functions given as samples of $e^{j\omega t}$ not cosines or sines. Review the formula for the inverse DFT which shows this relationship: $$x[n]= \...
Dan Boschen's user avatar
  • 51.4k
10 votes

How to get Fourier coefficients to draw any shape using DFT?

I'm not understanding the comments. Of course you can do this. It is simply a matter of understanding what a DFT means, how to calculate DFT bin values, and how to interpret those bin values as ...
Cedron Dawg's user avatar
  • 7,560
10 votes
Accepted

Why do we calculate the second half of frequencies in DFT?

First, there's some pedantics to get out of the way: it's not FFT or DFT -- the FFT is just a specific method of computing the DFT that's advantageous under many circumstances. Any DFT takes $N$ ...
TimWescott's user avatar
  • 12.7k
10 votes

Why do sinusoids have DFT magnitudes of N / 2 while we typically normalize by N?

To add to Dan’s answer, and focus on your “bonus” question: Keep in mind that DFT normalization/scaling is a matter of convention. Quoting the wikipedia article that you linked to in your question: ...
Jdip's user avatar
  • 6,055
9 votes
Accepted

Why calculate negative frequencies of DFT?

DFT does not decompose a signal into regular sinusoids, it decompose it up into complex exponentials. The Fourier transform of a real value signal must be conjugate symmetric (has both positive and ...
MimSaad's user avatar
  • 1,976
9 votes
Accepted

Considering the FFT of Real & Complex Signals

There's nothing wrong here - complex sinusoids like your signal really have only one peak in frequency domain! This is the fundamental idea of why we use the Fourier transform for periodic (even ...
Marcus Müller's user avatar
9 votes

What are some of the differences between DFT and FFT that make FFT so fast?

essentially, in computing the naive DFT directly from the summation: $$ X[k] = \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} $$ there are $N$ table lookups for the twiddle factor $ e^{-j 2 ...
robert bristow-johnson's user avatar
9 votes

A system that perfoms Fourier Transform operation - is it an LTI system?

The Fourier transform operator $\mathscr{F}$ is a linear one; i.e., $$\mathscr{F}\{x(t)\}=X(f) ~,~ \mathscr{F}\{y(t)\}=Y(f) \implies \mathscr{F}\{\alpha x(t) + \beta y(t) \} = \alpha X(f) + \beta Y(...
Fat32's user avatar
  • 28.2k
9 votes
Accepted

FFT vs DFT Run Time Comparison (Complexity Analysis) in MATLAB

Abhinav Jain, Welcome to DSP Community. I build for you a proper testing of the run time comparison. Few tips about timing in MATLAB: Never time in a script. Always call a function to do the heavy ...
Royi's user avatar
  • 19.6k
9 votes
Accepted

Why is the arithmetic mean the same as the DC component of its fourier transform?

The definition of the normalized discrete Fourier transform (DFT) for any signal $x[n]$ is $$F(k)=\frac{1}{N}\sum_{n=0}^{N-1}x[n]e^{-j2\pi k n /N}$$ The DC component of the DFT is evaluated at $k=0$. ...
Ash's user avatar
  • 915
9 votes

Downsample a signal by a non-integer factor

You need a resampler. There's different resamplers! I'm not sure you're correctly interpreting the answer you cite: you don't just decimate by 647; you'd first (at least mathematically) upsample by ...
Marcus Müller's user avatar
9 votes
Accepted

Why does interpolation with zeros introduce frequency artifacts?

First of all, you should (re-)read the corresponding chapter(s) in your textbook or lecture notes. Understanding these basic properties of discrete-time signals is essential. Second, what you see is ...
Matt L.'s user avatar
  • 90k
9 votes

Under what conditions does DFT(f(x)) = f(DFT(x)) hold?

The fft is an efficient computation of the DFT. So your question is about the DFT, not the fft. The DFT of a signal can be ...
Royi's user avatar
  • 19.6k
9 votes
Accepted

Why doesnt DFT Padding cause sinc like features

The OP is showing very good insight in all the comments stated. A product in the time domain with a rectangular pulse is convolution in the frequency domain with a Sinc. In fact zero padding in time ...
Dan Boschen's user avatar
  • 51.4k
8 votes
Accepted

How can I decompose a signal into square waves?

What is described in the question is very near the Discrete Wavelet Transform (DWT) with the use of the Haar Wavelet. The DWT decomposes a signal into a sum of dilated and translated orthogonal ...
A_A's user avatar
  • 10.7k

Only top scored, non community-wiki answers of a minimum length are eligible