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 ...
23
votes
Accepted
methods of computing fixed point atan2 on FPGA
You can use logarithms to get rid of the division. For $(x, y)$ in the first quadrant:
$$z = \log_2(y)-\log_2(x)\\
\text{atan2}(y, x) = \text{atan}(y/x) = \text{atan}(2^z)$$
Figure 1. Plot of $\text{...
- 13.5k
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 (...
- 947
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 ...
- 1,269
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 ...
- 48.8k
14
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 ...
- 31.7k
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 ...
- 683
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 ...
- 236
11
votes
Digital Distortion effect algorithm
Thanks to the plot in Olli Niemitalo's answer I got convinced that the formula given in the book has a sign error. The non-linearity used for fuzz or distortion is always some type of smoothed ...
- 88.9k
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 ...
- 7,520
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 ...
- 683
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 ...
8
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\...
- 13.5k
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)>...
- 88.9k
8
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 ...
- 19.3k
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 ...
- 71
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 ...
- 7,520
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(\...
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 ...
- 8,815
6
votes
Audio frequency modulation algorithm
You need to build a time varying delay, where you can modulate the delay amount over time.
The peak delay modulation is a function of your maximum desired frequency shift and the modulation ...
- 42.5k
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 ...
- 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 ...
- 25.2k
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 ...
- 4,556
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 ...
- 42.5k
6
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 ...
- 3,012
6
votes
Estimate Sine Frequency under White Noise — simple and effective method
I wasn't going to answer this, since the question is stale. But I'm a little bit dissatisfied with Royi's answer and with the Kay algorithm as presented.
The Kay method is, at first glance, simply ...
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 ...
- 88.9k
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 ...
- 25.2k
5
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 ...
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 ...
- 29.6k
Only top scored, non community-wiki answers of a minimum length are eligible