# 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 ![Radix-4 DIF Butterfly](https://i.imgur.com/GtksKwu.png=1578x824) 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)
Last changed by  
 
Akshay Kulkarni
MS CS at UCSD (2022-2024) Research Intern at Sony R&D Center (Summer 2023) Project Assistant at VAL, IISc (2020-2022) B. Tech - EEE, VNIT (2016-2020)
11396

Read more

Notes on "[DACS: Domain Adaptation via Cross-domain Mixed Sampling](https://arxiv.org/abs/2007.08702)"

Author: Akshay Kulkarni Note: WACV '21 paper; Official Code Release Brief Outline They propose Domain Adaptation via Cross-domain Mixed Sampling which mixes images from two domains along with their corresponding labels. These mixed samples are trained on, along with the labelled data itself. Introduction Unsupervised Domain Adaptation (UDA) deals with the problem where labelled data is available for a source domain, but only unlabelled data is available for the target domain.

4/19/2021
Notes on "[Prototypical Pseudo Label Denoising and Target Structure Learning for DA sem. seg.](https://arxiv.org/abs/2101.10979)"

Notes Author: Akshay Kulkarni CVPR '21 paper; Code Release SOTA on sem. seg. UDA benchmarks (as of 10/04/21). However, their code shows use of DeepLabv3+ type of decoder instead of DeepLabv2 (as claimed in the paper). Thus, it is unclear whether performance improvements are architecture-dependent or not. Brief Outline They use representative prototypes (class feature centroids) to address 2 issues in self-training for UDA in semantic segmentation. Exploit the feature distances from prototypes to estimate likelihood of pseudo-labels to facilitate online correction during training.

4/10/2021
Notes on "[Consistency Regularization with High-dimensional Non-adversarial Source-guided Perturbation for UDA in Segmentation](https://arxiv.org/abs/2009.08610)"

Notes author: Akshay Kulkarni AAAI '21 paper; Code Release Brief Outline They propose a bidirectional style-induced DA method (BiSIDA) that employs consistency regularization to efficiently exploit information from the unlabeled target dataset using a simple neural style transfer model. Introduction To perform domain alignment on a pixel-level or feature-level, existing works (Tsai et al. CVPR '18, Hoffman et al. ICML '18) typically use adversarial training and training with the aligned data is supervised using the labeled source data. However, this introduces extra complexity and instability in training.

3/28/2021
Notes on "[Discover, Hallucinate, and Adapt: Open Compound Domain Adaptation for Semantic Segmentation](https://papers.nips.cc/paper/2020/hash/7a9a322cbe0d06a98667fdc5160dc6f8-Abstract.html)"

NeurIPS '20 paper; Code not released as of 30/11/20. Author: Akshay Kulkarni Brief Outline This work investigates open compound domain adaptation (OCDA) for semantic segmentation which deals with mixed and novel situations at the same time. They first cluster the compound target data based on style (discover), then hallucinate multiple latent target domains in source using image translation, and perform target-to-source alignment separately between domains (adapt). Introduction Most existing UDA techniques focus on a single-source single-target setting instead of a more practical scenario where target consists of multiple data distributions without clear distinctions.

12/3/2020
Read more from Akshay Kulkarni
Published on HackMD