Understanding N-Stages of FFT & DFT Formula for Frequency Domain

[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 into 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.

 

[btb4198]

anyone ?

 

[jasonRF]

1) How many stages are in N numbers for a FFT? I know N=8 has 3 stages and N=4 has 2 stages ?

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.

2) The DFT formula converts a signal from the time domain into 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 ?

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,
[tex]
\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}
[itex]
where $\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.

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

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

 

[btb4198]

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,
[tex]
\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}
[itex]
where $\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

sorry but I am not really understanding your second answer. Why is it "represent the sequence as a sum of complex exponential "?

 

[jasonRF]

The IFFT is
$$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.