# FFT questions

Tags:
1. Nov 18, 2016

### btb4198

1) How many stages are in N numbers for a FFT? I know N=8 has 3 stages and N=4 has 2 stages ?
2) The DFT formula converts a signal from the time domain in to the frequency domain. Is this done by comparing x[n] against signals known as sinusoidal basis functions? are e-j2 pi kn/N sinusoidal basis functions ? I know it uses Correlation and that mean it compares the variables together but I am not 100% sure how this work ?

3) In a butterfly diagram the bottom line is alway -1, but why?

PS, I have been reading and watch videos on the DFT and the FFT and I have learned a lot, but I am just not sure about this questions.

2. Nov 19, 2016

### btb4198

anyone ?

3. Nov 21, 2016

### jasonRF

It depends ... perhaps that is why no one has replied. If you are doing a radix 2 FFT of $N=2^M$ points then sure, you have $M$ stages. But at the end of the day we all want software that is efficient, and radix 2 isn't always the answer. It doesn't even apply to something like a 100 point FFT. There are a number of different algorithms. Some use prime factors, some don't.

First, the built-in assumption is that the sequence $x[n]$ of $N$ numbers is one period of a periodic sequence. So it is reasonable to try and represent the sequence as a sum of complex exponentials that are consistent with the assumed periodicity of the given sequence. Now look at the formula for the DFT ,
$$X_k = \sum_{n=0}^{N-1} x_n e^{-j 2 \pi k n / N}$$
and the inverse,
$$x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{j 2 \pi k n / N}$$
I think of this as projecting the sequence $x_n$ onto a set of orthogonal basis functions $e^{j 2 \pi k n /N}$, and the $X_k$ are just the inner product (or dot product) of the sequence and the $k^{th}$ basis function. By orthogonal, I just mean,
$$\sum_{k=0}^{N-1} e^{j 2 \pi k_1 n / N} e^{-j 2 \pi k_2 n / N} = N \delta_{k_1,k_2} $where [itex]\delta_{k_1,k_2}$ is 1 if $k_1\neqk_2$ and 0 if $k_1\neq k_2$. The math is the same as representing a vector $v$ in terms of a set of orthogonal basis vectors $w_k$. The only thing different from what you probably did in basic vector algebra is that our sequence and the complex sinusoids can all be complex, so for the inner product one of the items is conjugated. Sorry, I can't help you here. I haven't looked at a butterfly diagram in 20+ years! I do work with folks that implement FFTs in FPGAs and other hardware, and if I had such a job then I would know the butterfly inside and out. Hopefully someone else can help. jason 4. Nov 22, 2016 ### btb4198 sorry but I am not really understanding your second answer. Why is it "represent the sequence as a sum of complex exponential "? 5. Nov 24, 2016 ### jasonRF The IFFT is [tex] x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{j 2 \pi k n / N}$$
The left hand side is the original sequence; the right side is a sum of complex exponentials.