# Radix-4 DIF FFT Algorithm

###### tags: `writeup` `dsp` `fft`

## Introduction
For fast and efficient calculation of Discrete Fourier Transform (DFT), there are Fast Fourier Transforms (FFT). FFT is generally based on divide-and-conquer principle. So, we break the signal into 2 parts, then take the FFT part by part (this is a very simplistic way of explaining).

So, in FFT, if we break the signal (of length $N$) into signals of length $2$, then those methods are called Radix-2. Similarly, we can have Radix-4 or any radix. But, for any Radix-$M$ method to be used throughout, the signal has to be of length $M^r$. Otherwise, padding can be added to make up the length.

Further, there can be 2 ways to compute FFT:
* Input stored row-wise and output read column-wise (DIF)
* Input stored column-wise and output read row-wise (DIT)

DIF algorithms are preferred because input order is unchanged, which is easier to implement in hardware.

## Purpose of this write-up
There are not many websites/papers explaining and proving Radix-4 DIF and its butterfly diagram in detail. Thus, this write-up aims to derive the equations of Radix-4 DIF and also explain the butterfly diagram.

## Pre-requisites
* Basic knowledge of DFT, DFT matrix and properties.
* Knowledge of FFT divide-and-conquer principle.
* Knowledge of derivations of Radix-2 DIT and DIF will help you understand this faster.

## Proof of Radix-4 DIF
Note: It may take some time for the math equations to load.

We start with the DFT equation:
$$X(k) = \sum_{n = 0}^N x(n)W_N^{kn} \hspace{0.3cm} \forall k \in [0, N - 1] $$

Now, in DIF, the input is stored row-wise, so no change in input order. We split the above equation in 4 parts as follows:
$$X(k) = \sum_{n = 0}^{\frac{N}{4} - 1} x(n)W_N^{kn} + \sum_{n = \frac{N}{4}}^{\frac{2N}{4} - 1} x(n)W_N^{kn} + \sum_{n = \frac{2N}{4}}^{\frac{3N}{4} - 1} x(n)W_N^{kn} + \sum_{n = \frac{3N}{4}}^{\frac{4N}{4} - 1} x(n)W_N^{kn}$$

Then, we substitute $m = n - \frac{cN}{4}$ in the $c^{th}$ summation (except the first). We do this to make all the summation limits $[0, \frac{N}{4} - 1]$. Thus, we get:
$$X(k) = \sum_{n = 0}^{\frac{N}{4} - 1} x(n)W_N^{kn} + \sum_{m = 0}^{\frac{N}{4} - 1} x(m + \frac{N}{4})W_N^{k(m + \frac{N}{4})} + \\ \sum_{m = 0}^{\frac{N}{4} - 1} x(m + \frac{2N}{4})W_N^{k(m + \frac{2N}{4})} + \sum_{m = 0}^{\frac{N}{4} - 1} x(m + \frac{3N}{4})W_N^{k(m + \frac{3N}{4})}$$

Now, consider each $W_N$ term and simplify it separately before moving forward, and using the properties of $W_N^k$,
$$W_N^{k(m + \frac{cN}{4})} = W_N^{km} W_N^{\frac{ckN}{4}} = W_N^{km}W_4^{ck} \hspace{0.3cm} \forall \hspace{0.3cm} c \in [1, 3]$$

We can see that the $W_N^{km}$ term will be common in all summations and also the limits. So, we replace $m$ by $n$ and we combine the summations:
$$X(k) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n)W_4^{0k} + x(n + \frac{N}{4})W_4^{1k} + x(n + \frac{2N}{4})W_4^{2k} + x(n + \frac{3N}{4})W_4^{3k} \} W_N^{kn}$$

We can further simplify the $W_4^{ck}$ terms as follows:
$$W_4^{0k} = W_4^0 = 1 \\
W_4^{1k} = (W_4^1)^k = (-j)^k \\
W_4^{2k} = (W_4^2)^k = (-1)^k \\
W_4^{3k} = (W_4^3)^k = (j)^k
$$

So, the equation becomes,
$$X(k) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j)^k + x(n + \frac{2N}{4})(-1)^k + x(n + \frac{3N}{4})j^k \} W_N^{kn}$$

The above equation is not a proper DFT relation since the limits of $n$ go from $0$ to $\frac{N}{4} - 1$ while the $W_N$ term has base $N$ instead of $\frac{N}{4}$.

Further, since output is read column-wise, we need $X(4k), X(4k + 1), X(4k + 2), X(4k + 3)$ instead of $X(k)$.
$$X(4k) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j)^{4k} + x(n + \frac{2N}{4})(-1)^{4k} + x(n + \frac{3N}{4})j^{4k} \} W_N^{4kn} \\
X(4k + 1) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j)^{4k + 1} + x(n + \frac{2N}{4})(-1)^{4k + 1} + x(n + \frac{3N}{4})j^{4k + 1} \} W_N^{(4k + 1)n} \\
X(4k + 2) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j)^{4k + 2} + x(n + \frac{2N}{4})(-1)^{4k + 2} + x(n + \frac{3N}{4})j^{4k + 2} \} W_N^{(4k + 2)n} \\
X(4k + 3) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j)^{4k + 3} + x(n + \frac{2N}{4})(-1)^{4k + 3} + x(n + \frac{3N}{4})j^{4k + 3} \} W_N^{(4k + 3)n} \\
$$

Now, consider the constant terms first:
$$(-j)^{4k} = ((-j)^4)^k = 1^k = 1 \\
(-j)^{4k + 1} = (-j)^{4k} (-j)^1 = -j \\
(-j)^{4k + 2} = (-j)^{4k} (-j)^2 = -1 \\
(-j)^{4k + 3} = (-j)^{4k} (-j)^3 = j
$$
Similarly, we can find the other constant terms, and the equations become:
$$X(4k) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4}) + x(n + \frac{2N}{4}) + x(n + \frac{3N}{4}) \} W_N^{4kn} \\
X(4k + 1) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j) + x(n + \frac{2N}{4})(-1) + x(n + \frac{3N}{4})(j) \} W_N^{(4k + 1)n} \\
X(4k + 2) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-1) + x(n + \frac{2N}{4}) + x(n + \frac{3N}{4})(-1) \} W_N^{(4k + 2)n} \\
X(4k + 3) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(j) + x(n + \frac{2N}{4})(-1) + x(n + \frac{3N}{4})(-j) \} W_N^{(4k + 3)n}
$$

We can see that the inner terms are actually the $W_4$ matrix. More on that later. Now, we simplify the outer terms:
$$W_N^{4kn} = W_{\frac{N}{4}}^{kn} \\
W_N^{(4k + 1)n} = W_N^{4kn} W_N^{1n} = W_N^nW_{\frac{N}{4}}^{kn} \\
W_N^{(4k + 2)n} = W_N^{4kn} W_N^{2n} = W_N^{2n}W_{\frac{N}{4}}^{kn} \\
W_N^{(4k + 3)n} = W_N^{4kn} W_N^{3n} = W_N^{3n}W_{\frac{N}{4}}^{kn} \\
$$

So, the equations become:
$$X(4k) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4}) + x(n + \frac{2N}{4}) + x(n + \frac{3N}{4}) \} W_{\frac{N}{4}}^{kn} \\
X(4k + 1) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-j) + x(n + \frac{2N}{4})(-1) + x(n + \frac{3N}{4})(j) \} W_N^nW_{\frac{N}{4}}^{kn} \\
X(4k + 2) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(-1) + x(n + \frac{2N}{4}) + x(n + \frac{3N}{4})(-1) \} W_N^{2n}W_{\frac{N}{4}}^{kn} \\
X(4k + 3) = \sum_{n = 0}^{\frac{N}{4} - 1} \{ x(n) + x(n + \frac{N}{4})(j) + x(n + \frac{2N}{4})(-1) + x(n + \frac{3N}{4})(-j) \} W_N^{3n}W_{\frac{N}{4}}^{kn}
$$

These 4 equations are $\frac{N}{4}$ point DFT relations since limits of $n$ are from $0$ to $\frac{N}{4} - 1$ and $W$ term has base $\frac{N}{4}$. These are the generating equations for Radix-4 DIF and can be used to construct the butterfly diagram.

Note: There is no direct matrix form (as in Radix-4 DIT), but the inner part has the $W_4$ matrix terms.

## Butterfly Diagram
Source of image - [3]
Figure (a) shows the butterfly diagram. It can be understood from the generating equations. It just maps from input to output.
Figure (b) shows the simplified butterfly diagram. The circle at the centre represents the $W_4$ matrix which is
$$W_4 =
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -j & -1 & j \\
1 & -1 & 1 & -1 \\
1 & j & -1 & -j \\
\end{bmatrix}
$$
So, the 4 inputs are multiplied by the $W_4$ matrix and then each of the outputs is multiplied by $W_N^{cn}$ where $c$ is the index of the output.

## Conclusion
In this write-up, I have attempted to give an in-depth derivation of Radix-4 DIF FFT generating equations and the corresponding butterfly and simplified butterfly diagrams. If there are any issues in this, you can [contact me](https://akshayk07.weebly.com/about-me.html).

## References
1. [TI Technical Report on Hardware Implementation of Radix-4 DIF](http://www.ti.com/lit/an/spra152/spra152.pdf)
2. [Notes on FFT](http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html)
3. [Paper on Radix-4 DIF FFT implementation](http://ijarcsse.com/Before_August_2017/docs/papers/Volume_4/5_May2014/V4I5-0346.pdf)