# Tag Info

### Show how to do FFT by hand

Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p. In this case,...
• 101

### Expected Behavior of FFT

In polar coordinates, $(0,x) = (0,y)$ for any $x$ and $y$, so there's no issue. You've simply used a representation that has multiple representations of the complex number $0 + 0i$. Going beyond your ...
• 12.1k
Accepted

### Expected Behavior of FFT

Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones). ...
• 9,495
Accepted

• 278k

### Explaining why FFT is faster than DFT for the general public?

What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for ...
• 31.5k
1 vote

### 2D fourier transform

It has same meaning as the 1d Fourier transform: the magnitude and phase of waves that, when superimposed, reconstruct your original signal. In one dimension, the signal is (usually) a function of ...
• 173
1 vote

### How does each element in the output array of a DFT correspond to a specific frequency?

Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula: $$y(k) = \sum_{t=0}^{n-1} e^{-2\pi i tk/n} x(t).$$ ...
• 278k
1 vote

### Check for common element in two arrays using FFT

This one is a bit esoteric, but: $$\prod_{1\leq i,j \leq n} (x_i-y_j)$$ Could be decomposed to (as noted by @NotDijkstra) $$\prod_{i=1}^{n} p(x_i)$$ where $$p (x) = \prod_{j=1}^{n} (x - y_j)$$ ...
• 243
1 vote

### Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?

Fourier Transform changes basis from time (spatial data) to frequency. To encode frequency we need amplitude (magnitude) to know how strong is signal at given frequency and phase to know when sine ...
• 9,495
1 vote

### What are 'Butterfly Combinations' and why are they called this way?

So, a summary of the Wikipedia page on Butterfly Diagrams: In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger ...
• 123
1 vote

### What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?

The Fourier Transform is the change of basis, the discrete signal from image, which is finite, gets transformed into sines. The transformation itself is prone to rounding, because in frequency domain ...
• 9,495
1 vote

### How is this definition of the quantum Fourier transform to be understood?

The index $\mathbf{k}$ goes over all vectors in $\{0,1\}^n$ (which can be identified with $\mathbb{Z}_2^n$). The index $\mathbf{x}$ also has the same range, and \$\mathbf{k} \cdot \mathbf{x} = \sum_{i=...
• 278k
1 vote

### Explaining why FFT is faster than DFT for the general public?

Here is an attempt. The Fourier transform decomposes a signal into superimposed sine waves of various frequencies (this can be demonstrated visually). It turns out that we can find out the strength of ...
• 278k

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