Low-power Butterfly Structure for DIT Radix-4 FFT Implementation

Young-Beom Jang, Sang‐Woo LeeThe Journal of Korean Institute of Communications and Information Sciences 2013 · DOI

Abstract

Fast Fourier Transform (FFT) algorithms are essential in digital signal processing, primarily implemented using either Decimation-In-Frequency (DIF) or Decimation-In-Time (DIT) techniques. While DIF is more common due to its well-documented Radix-2/4/8 implementations, DIT algorithms offer the inherent advantage of producing sequential outputs, which is highly desirable for real-time systems. This paper derives the DIT Radix-4 algorithm and proposes an efficient butterfly structure optimized for System-on-a-Chip (SoC) implementation.

Introduction

The Fast Fourier Transform (FFT) is a cornerstone of modern digital signal processing. Currently, the Decimation-In-Frequency (DIF) algorithm dominates hardware design because its various radix implementations are extensively researched. However, DIF architectures typically result in "bit-reversed" output orders, necessitating additional memory and logic to reorder data for practical use.

In contrast, Decimation-In-Time (DIT) algorithms naturally produce sequential outputs, significantly simplifying data flow in real-time applications. Despite this clear advantage, efficient hardware architectures for DIT Radix-4 have remained under-explored. This paper bridges this gap by providing a formal mathematical derivation and a corresponding low-power hardware "butterfly" structure.

Mathematical Derivation and Signal Flow

The authors take a rigorous approach to decomposing the standard $N$-point Discrete Fourier Transform (DFT) equation into four sub-sequences, forming the Radix-4 structure. By defining indices for $4r, 4r+1, 4r+2,$ and $4r+3$, they derive the four fundamental equations that govern a DIT Radix-4 butterfly unit. This mathematical framework is visualized through a Signal Flow Graph (SFG), which maps the data movement for a complete FFT operation.

Signal Flow Graph (SFG) for a 64-point DIT Radix-4 FFT.

Proposed Hardware Architecture

To move from abstract mathematics to a physical System-on-a-Chip (SoC) design, the authors translate complex-number equations into real and imaginary hardware components. The proposed architecture is centered around an optimized butterfly unit consisting of:

  1. Complex Multipliers: These units are specifically designed to handle twiddle factor multiplications ($\cos\theta - j\sin\theta$), as shown in the detailed logic diagrams.
  2. Adder Logic: A structured network of adders and subtractors implements the final butterfly outputs ($X_a$ through $X_d$) by processing the real and imaginary parts derived in the mathematical section.

The design emphasizes symmetry in the arrangement of multipliers and adders. This symmetry is crucial for maintaining balanced timing paths and reducing overall power consumption in VLSI (Very Large Scale Integration) designs.

Proposed hardware architecture: (a) Top-level block diagram, (b) Detailed multiplier logic, and (c) Optimized adder network.

Key Insights and Results

  • The Sequential Advantage: The core benefit of this DIT implementation is the elimination of complex reordering buffers, allowing for a more natural data flow in high-throughput systems.
  • Resource Parity: The proposed DIT structure utilizes a comparable number of multipliers and adders to existing DIF structures. This ensures that engineers can leverage the sequential output benefits of DIT without incurring a significant penalty in hardware area.
  • Complex-to-Real Bridge: The paper provides the explicit logic required to implement complex butterfly operations using only real-valued hardware components, serving as a practical guide for silicon implementation.

Conclusion and Future Work

This work successfully derives a DIT Radix-4 FFT algorithm and a corresponding hardware-ready butterfly structure. While the architecture is designed for low-power SoC applications, the paper acknowledges limitations in empirical validation. Future research should focus on synthesizing this design on FPGA or ASIC platforms to provide concrete benchmarks for power consumption (mW), throughput (Gbps), and latency compared to traditional DIF implementations.

Summary updated

Abstract

FFT(Fast Fourier Transform) 알고리즘에는 DIT(Decimation-In-Time)와 DIF(Decimation-In-Frequency)가 있다. DIF 알고리즘은 Radix-2/4/8 등의 다양한 종류와 그 구현 방법이 개발되어 사용되는데 반하여 DIT 알고리즘은 순차적인 출력을 낼 수 있는 장점에도 불구하고 다양한 구현방법이 연구되지 못하였다. 이 논문에서는 DIT Radix-4 알고리즘을 유도하며 반도체 구현을 위한 효율적인 butterfly 구조를 제안한다. There are two FFT(Fast Fourier Transform) algorithms, which are DIT(Decimation-In-Time) and DIF(Decimation-In- Frequency). Even the DIF algorithm is more widely used because of its various implementation architectures, the DIT structures have not been investigated. In this paper, the DIT Radix-4 algorithm is derived and its efficient butterfly structure is proposed for SoC(System on a Chip) implementation.
BibTeX
@article{jang2013low,
  author = {Young-Beom Jang and Sang‐Woo Lee},
  title = {{Low-power Butterfly Structure for DIT Radix-4 FFT Implementation}},
  journal = {The Journal of Korean Institute of Communications and Information Sciences},
  year = {2013},
  doi = {10.7840/kics.2013.38a.12.1145},
}
Figure