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{...
user avatar
21 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 ...
user avatar
20 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 (...
user avatar
  • 927
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 ...
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 using the notation $W_N^...
user avatar
  • 37.7k
14 votes

What Approximation Techniques Exist for Computing the Square Root?

if you want a cheap and dirty optimized power-series expansion (the coefficients for Taylor series converge slowly) for sqrt() and a bunch of other trancendentals, ...
user avatar
13 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 ...
user avatar
12 votes
Accepted

Algorithm to pan audio

The basic technique to place a mono source in stereo is called constant power panning. If you want to place a mono source at angle $\theta$ you can just use $A_\mathrm{amp}$ and $B_\mathrm{amp}$ as ...
user avatar
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 ...
user avatar
  • 80.4k
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 ...
user avatar
  • 6,903
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 ...
user avatar
  • 231
9 votes
Accepted

Books/resources for implementing various mathematical functions in fixed point arithmetic for DSP purposes

the general polynomial form is: $$\begin{align} f(u) &= \sum\limits_{n=0}^{N} \ a_n \ u^n \\ \\ &= a_{\small{0}} + \Bigg(a_{\small{1}} + \bigg(a_{\small{2}} + \Big(a_{\small{3}} + \,... \...
user avatar
9 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 ...
user avatar
  • 206
8 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 ...
user avatar
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\...
user avatar
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)>...
user avatar
  • 80.4k
7 votes

What Approximation Techniques Exist for Computing the Square Root?

If you haven't seen it, the "Quake square root" is simply mystifying. It uses some bit-level magic to give you a very good first approximation, and then uses a round or two of Newton's approximation ...
user avatar
7 votes
Accepted

What Is the Algorithm Behind Photoshop's "Black and White" Adjustment Layer?

I replicated the algorithm perfectly in MATLAB (Based on @Ivan Kuckir answer): ...
user avatar
  • 41.3k
7 votes

What Approximation Techniques Exist for Computing the Square Root?

Actually it is done by solving an quadratic equation using Newton Method - Wikipedia: Methods of Computing Square Roots. For numbers greater than one you can use the following Taylor Expansion - ...
user avatar
  • 41.3k
7 votes
Accepted

Simple and efficient algorithm to detect frequency and phase of a sine signal

Note: I originally posted this answer for the Stack Overflow copy of this question, before realizing that it had also been asked here. It somewhat duplicates pichenettes' answer, but I felt it still ...
user avatar
7 votes

Convex Optimization in Signal and Image Processing

Papers Interpolation by Solving an Optimization Problem. The Chebyshev Center Problem could be thought as Robust Localization Problem. Books Daniel P. Palomar, Yonina C. Eldar - Convex Optimization ...
user avatar
  • 41.3k
7 votes
Accepted

Looking for an arcsin algorithm

Here's just a polynomial version: $$ \arcsin(x) = x + \frac{1}{2} \frac{x^3}{3} + \frac{1 \cdot 3}{2 \cdot 4} \frac{x^5}{5} + \frac{1\cdot 3 \cdot 5}{2 \cdot 4 \cdot 6} \frac{x^7}{7} $$ ...
user avatar
  • 22.9k
6 votes

Measuring Audio Signal Similarities

You can use the Normalized Cross Correlation for that. Basically, representing each recorded sound as a vector, this gives the angle between them. Another approach is dealing with features of the ...
user avatar
  • 41.3k
6 votes

What Approximation Techniques Exist for Computing the Square Root?

You could also approximate the square root function by using Newton's Method. Newton's Method is a way of approximating where the roots of a function are. It is also an iterative method where the ...
user avatar
  • 513
6 votes

What Approximation Techniques Exist for Computing the Square Root?

because the code markup for SE seems to work like shit, i'll try to answer this more directly, specifically for the $\sqrt{x}$ function. yes, a power series can quickly and efficiently approximate ...
user avatar
6 votes
Accepted

Duration of unknown rectangular pulse with additive white Gaussian noise

You want a method that removes noise while preserving edges. This cannot be achieved well by linear filtering, as you noticed yourself. I know of two approaches that might work well for your problem. ...
user avatar
  • 80.4k
6 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 ...
user avatar
6 votes
Accepted

Convex Optimization in Signal and Image Processing

There's a whole area of signal processing dedicated to optimal filtering. In pretty much every case I've seen the filtering problem is formulated with a convex cost function. Here's a freely ...
user avatar
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 ...
user avatar
  • 32.6k
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 ...
user avatar
  • 22.9k

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