The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Why do we need DFT when we already have DTFT/DTFS?

The answer is the same to the question: "Why do we need computers to process data when we have paper and pencil?" DTFT as well as the continuous-time Fourier Transform is a theoretical tool ...

### 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

### 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

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

### Why do we need DFT when we already have DTFT/DTFS?

TL, DR: world pervasive algorithms (FFT-related)! The continuous Fourier transform, the Discrete-time Fourier transform (DTFT) and the Discrete Fourier transform (DFT) share conceptually similar ...
• 32.1k

### What is the name of a low-pass filter that tracks rate of change?

I was able to remember how the filter works. The idea is very simple, a second low-pass filter tracks the steady-state error in the result of the first one, and it is then added to the output: Based ...
• 878
Accepted

### Understanding FFT: FFT size and bins

Question 1 If you apply it over the entire length of the array, the length of the FFT would be the length of the array. But, the FFT is more efficient if the length is a power of two, so it is common ...
• 236

### Efficient Magnitude Comparison for Complex Numbers

PROLOGUE My answer to this question is in two parts since it is so long and there is a natural cleavage. This answer can be seen as the main body and the other answer as appendices. Consider it a ...
• 7,590

### Efficient Magnitude Comparison for Complex Numbers

You mention in a comment that your target platform is a custom IC. That makes the optimization very different from trying to optimize for an already existing CPU. On a custom IC (and to a lesser ...
• 878

• 31.8k