# Tag Info

### 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 (...
• 957
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$...
• 11.1k
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 ...
• 51.4k

### 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 ...
• 1,269
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 ...
• 7,560

### 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 ...
• 44.8k

### 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 ...
• 51.4k

### 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/...
• 457
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, ...
• 51.4k

### 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 ...
• 44.8k
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 ...
• 6,055

### 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]$ ...
• 90k

### 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 ...
• 12.7k
Accepted

• 51.4k

### 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 ...
• 7,560
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$ ...
• 12.7k

### 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: ...
• 6,055
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 ...
• 1,976
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 ...
• 30.7k

• 915

### 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 ...
• 30.7k
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 ...
• 90k

### 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 ...
• 19.6k
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 ...
• 51.4k