3
$\begingroup$

What are the differences between decimation in time and decimation in frequency algorithms of FFT, especially as their names suggest?

How can I see/understand that decimation in time domain is taking place in DIT and decimation in frequency domain is taking place in DIF?

$\endgroup$
1
  • $\begingroup$ Try reading this: quora.com/… $\endgroup$
    – Hilmar
    Commented Dec 3, 2018 at 6:50

1 Answer 1

3
$\begingroup$

The DFT is (let's say that $N$ is even):

$$ X[k] \ \triangleq \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} $$

The radix-2 FFT works by splitting a size-$N$ DFT into two size-$\frac{N}{2}$ DFTs. (Because the cost of a naive DFT is proportional to $N^2$, cutting the problem in half will cut this cost, maybe, in half. Two size-$\frac{N}{2}$ DFTs appear to cost less than one size-$N$ DFT.


The Decimation-in-Time FFT splits the two DFTs into even and odd-indexed input samples:

$$\begin{align} X[k] \ &\triangleq \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n\text{ even}} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + \sum\limits_{n\text{ odd}} x[n] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m] \, e^{-j 2 \pi \frac{(2m)k}{N}} + \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m+1] \, e^{-j 2 \pi \frac{(2m+1)k}{N}} \\ \\ &= \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m] \, e^{-j 2 \pi \frac{mk}{N/2}} + e^{-j 2 \pi \frac{k}{N}} \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m+1] \, e^{-j 2 \pi \frac{mk}{N/2}} \\ \\ \end{align}$$

This shows that if the evens are stuffed into one DFT and the odds are stuffed into another DFT, that the results of the two DFTs can be combined by multiplying the result of the right-hand (odd) DFT with a single factor $ e^{-j 2 \pi \frac{k}{N}} $ and added to the left-hand (even) DFT. The result for the two frequencies $X[k]$ and $X[k+\tfrac{N}{2}]$ are the same except the right hand term is subtracted than added.

$$\begin{align} X[k] &= \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m] \, e^{-j 2 \pi \frac{mk}{N/2}} + e^{-j 2 \pi \frac{k}{N}} \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m+1] \, e^{-j 2 \pi \frac{mk}{N/2}} \\ \\ X[k+\tfrac{N}{2}] &= \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m] \, e^{-j 2 \pi \frac{mk}{N/2}} - e^{-j 2 \pi \frac{k}{N}} \sum\limits_{m=0}^{\frac{N}{2}-1} x[2m+1] \, e^{-j 2 \pi \frac{mk}{N/2}} \\ \end{align}$$

This shows how the butterflies are defined on the last pass of the FFT.


The Decimation-in-Frequency FFT splits the two DFTs into the first half and last half of the input samples:

$$\begin{align} X[k] \ &\triangleq \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + \sum\limits_{n=\frac{N}{2}}^{N-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + \sum\limits_{n=0}^{\frac{N}{2}-1} x[n+\tfrac{N}{2}] \, e^{-j 2 \pi \frac{(n+N/2)k}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + e^{-j 2 \pi \frac{(N/2)k}{N}} \sum\limits_{n=0}^{\frac{N}{2}-1} x[n+\tfrac{N}{2}] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + e^{-j \pi k} \sum\limits_{n=0}^{\frac{N}{2}-1} x[n+\tfrac{N}{2}] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} x[n] \, e^{-j 2 \pi \frac{nk}{N}} + (-1)^k \sum\limits_{n=0}^{\frac{N}{2}-1} x[n+\tfrac{N}{2}] \, e^{-j 2 \pi \frac{nk}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} \Big( x[n] + (-1)^k x[n+\tfrac{N}{2}] \Big) \, e^{-j 2 \pi \frac{nk}{N}} \\ \end{align}$$

For even $k$ we add the $x[n+\tfrac{N}{2}]$ to $x[n]$. For odd $k$, we subtract.

$$\begin{align} X[2m] &= \sum\limits_{n=0}^{\frac{N}{2}-1} \Big( x[n] + x[n+\tfrac{N}{2}] \Big) \, e^{-j 2 \pi \frac{n(2m)}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} \Big( x[n] + x[n+\tfrac{N}{2}] \Big) \, e^{-j 2 \pi \frac{nm}{N/2}} \\ \\ X[2m+1] &= \sum\limits_{n=0}^{\frac{N}{2}-1} \Big( x[n] - x[n+\tfrac{N}{2}] \Big) \, e^{-j 2 \pi \frac{n(2m+1)}{N}} \\ \\ &= \sum\limits_{n=0}^{\frac{N}{2}-1} \Big( x[n] - x[n+\tfrac{N}{2}] \Big) \, e^{-j 2 \pi \frac{n}{N}} e^{-j 2 \pi \frac{nm}{N/2}} \\ \end{align}$$

This shows how the butterflies are defined on the first pass of the FFT.


$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.