Skip to main content
26 votes
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 ...
robert bristow-johnson's user avatar
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
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
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
  • 52.3k
15 votes

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 ...
Laurent Duval's user avatar
14 votes

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 ...
jpa's user avatar
  • 763
12 votes
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 ...
Erik's user avatar
  • 236
10 votes

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 ...
Cedron Dawg's user avatar
  • 7,590
10 votes

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 ...
jpa's user avatar
  • 763
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

Efficient Magnitude Comparison for Complex Numbers

1. Logarithms and exponents to avoid multiplication To completely avoid multiplication, you could use $\log$ and $\exp$ tables and calculate: $$I^2 + Q^2 = \exp\!\big(2\log(I)\big) + \exp\!\big(2\...
Olli Niemitalo's user avatar
9 votes

Estimate Sine Frequency under White Noise — simple and effective method

I assume the model to be: $$ x \left[ n \right] = \sin \left[ 2 \pi \frac{f}{ {f}_{s} } n + \phi \right] + w \left[ n \right] $$ Where $ w \left[ n \right] $ is white noise uncorrelated with the ...
Royi's user avatar
  • 19.8k
8 votes

Efficient Magnitude Comparison for Complex Numbers

Given two complex numbers $z_1=a_1+jb_1$ and $z_2=a_2+jb_2$ you want to check the validity of $$a_1^2+b_1^2>a_2^2+b_2^2\tag{1}$$ This is equivalent to $$(a_1+a_2)(a_1-a_2)+(b_1+b_2)(b_1-b_2)>...
Matt L.'s user avatar
  • 90.5k
7 votes

Algorithm to pan audio

I just wanted to point out that if you're planning to use these formulas in your code, you can get the exact same results with fewer calculations by using an angle $\theta$ between 0 and 90 degrees ...
oddacorn's user avatar
7 votes

Efficient Magnitude Comparison for Complex Numbers

I'm putting this as a separate answer because my other answer is already too long, and this is an independent topic but still very pertinent to the OP question. Please start with the other answer. A ...
Cedron Dawg's user avatar
  • 7,590
7 votes

Estimate Sine Frequency under White Noise — simple and effective method

A common way to do this is to take the FFT of the input signal. Since the frequency might not be right at a FFT bin, usually a second step of interpolation is done after choosing the initial peak. A ...
Engineer's user avatar
  • 3,042
7 votes

Estimate Sine Frequency under White Noise — simple and effective method

If you have a low-noise and well-sampled signal, a quick way to estimate it is to find $\sqrt{-f''(t)/f(t)}$. For a signal $$f(t)=A \sin(\omega t+\phi)$$ the second derivative is $$-A \omega^2 \sin(\...
Nullius in Verba's user avatar
7 votes
Accepted

Identify abrupt changes in an audio waveform

Synchrosqueezed Wavelet Transform is an option. I have developed a complete algorithm for this task, which scores 100% train accuracy and 86% test accuracy with 0.05 sec tolerance, without machine ...
OverLordGoldDragon's user avatar
6 votes
Accepted

Algorithm for 1d spline interpolation suitable for 8 bit microcontroler

Take a look at the cubic Hermite spline. The interpolated function is continuous at the data points and the first derivative is also continuous. Away from the data points all of the derivatives are ...
robert bristow-johnson's user avatar
6 votes
Accepted

Fast & accurate convolution algorithm (like FFT) for high dynamic range?

Disclaimer: I know this topic is older, but if one is looking for "fast accurate convolution high dynamic range" or similar this is one of the first of only a few decent results. I wanna ...
oli's user avatar
  • 175
6 votes
Accepted

Doubts on LMS derivation

Here I expected $y(n)$ is to be computed by convolving $x(n)$ with $h(n)$, but in the equation given by Wikipedia it is shown as a matrix multiplication $y(n) = h^H(n).x(n)$. Are these two ...
Peter K.'s user avatar
  • 25.9k
6 votes
Accepted

Does this Signal Smoothing algorithm have a name?

Not sure if this has a name, but it is a nonlinear low pass filter that uses different smoothing constants depending on the input signal deviation from the filtered output. Small deviations are ...
Jazzmaniac's user avatar
  • 4,583
6 votes

Estimate Sine Frequency under White Noise — simple and effective method

This depends on the precision needed. If it's a pure sine wave that's noise free, you can get a very quick estimate by measuring the difference between two zero crossings. The tricky part is that most ...
Hilmar's user avatar
  • 45.6k
6 votes
Accepted

When if an FFT more efficient than Goertzel?

If you implement the Goertzel algorithm P times to detect P different spectral samples, Goertzel is more efficient (fewer multiplies) than the N-point FFT when P < log2(N).
Richard Lyons's user avatar
6 votes

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

I do not think that there's a specific name for this type of lowpass filter. There are indeed similarities between the cascade of two lowpass filters as suggested in the OP's answer, and a combination ...
Matt L.'s user avatar
  • 90.5k
5 votes

Beginner's book in signal processing with practical examples on fault detection in electrical motors

When I had a look at rotating machinery, the best reference I could find is Bob Randall's Frequency Analysis. This was generated in conjunction with Brüel & Kjær as they sold lots of nice (and ...
Peter K.'s user avatar
  • 25.9k
5 votes
Accepted

Computational Complexity of Polyphase Resampling

Rational Resampling 10 kHz -> 300 Hz is a rational resampling with relatively benign factors: $$ \frac{300\,\text{Hz}}{10\,\text{kHz}}=\frac{3\cdot10^2}{10^4}=\frac3{100}\text,$$ meaning that you'd ...
Marcus Müller's user avatar
5 votes

Extending Goertzel algorithm to 24 kHz, 32 kHz and 48 kHz

Choice of $N$ Dual-tone multi-frequency (DTMF) tones should be of certain minimum duration (40 ms) and quality to be detected (reviewed in ITU TABLE A-1/Q.24). The detection algorithm that you cite ...
Olli Niemitalo's user avatar
5 votes
Accepted

Maximum likelihood estimation complexity computation

Ordinary Least Squares problem Your $$\hat x = \arg\min_x \sum_{n=1}^{N_r} \left\lvert y_n - h_n x\right\rvert^2$$ is just a way of saying $$\hat x = \arg\min_x \left\| y - Hx \right \|$$ and that is ...
Marcus Müller's user avatar
5 votes
Accepted

One Too Many Non-Zero Eigenvalues in MUSIC DF Algorithm

You are really close! Change your signal and steering vectors to be complex. Specifically for the steering vectors, these coefficients are meant to act as phase shifts. Using a real sinusoid will ...
Envidia's user avatar
  • 2,601

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