A New DIT Radix-4 FFT Structure and Implementation

Young-Beom Jang, Sang‐Woo LeeJournal of the Korea Academia-Industrial Cooperation Society 2015 · DOI

Abstract

Fast Fourier Transform (FFT) algorithms are generally categorized into Decimation-In-Time (DIT) and Decimation-In-Frequency (DIF). While DIF algorithms are widely implemented due to their structural variety, DIT algorithms offer a significant advantage in generating sequential outputs, which is critical for high-speed communication systems. This paper proposes and validates a new DIT Radix-4 FFT butterfly structure. A 64-point FFT was designed using the proposed architecture and implemented via Verilog HDL. Synthesis results show a gate count of 6.78 million using 48 multipliers at a 100MHz clock frequency. The proposed structure is highly suitable for Orthogonal Frequency Division Multiplexing (OFDM) System-on-a-Chip (SoC) applications requiring sequential data processing.

1. Introduction

The FFT is a cornerstone of digital signal processing, particularly in OFDM-based communication standards like Wi-Fi and LTE. The choice between DIT and DIF architectures often depends on the required data ordering. DIF algorithms typically produce bit-reversed outputs, necessitating additional memory and logic for reordering to a sequential format. Conversely, DIT algorithms can produce sequential outputs if the input is bit-reversed, which is often easier to manage in streaming hardware environments. Despite this advantage, high-radix DIT structures have seen less development compared to their DIF counterparts. This research addresses this gap by proposing an efficient Radix-4 DIT butterfly unit.

2. Proposed DIT Radix-4 FFT Architecture

The Radix-4 algorithm reduces the number of computational stages compared to Radix-2, thereby increasing throughput. For an $N$-point FFT, the number of stages is $\log_4 N$. In the case of a 64-point FFT, only three stages are required.

Signal Flow Graph of the 64-point DIT Radix-4 FFT

The signal flow graph (SFG) for the 64-point DIT Radix-4 FFT is shown above. By utilizing bit-reversed input indexing, the architecture ensures that the final output $X[k]$ is produced in a natural, sequential order. This eliminates the need for Parallel-to-Serial Conversion (PSC) circuits or complex reordering buffers at the output stage.

3. Hardware Implementation

The core of the proposed design is the modular butterfly unit. The mathematical operations involving complex twiddle factors ($W_N^k$) were decomposed into real and imaginary components to facilitate hardware mapping.

Hardware Architecture of the Proposed Butterfly Unit

As illustrated in the hardware block diagrams, the butterfly unit is divided into a Multiplier Block and an Adder Block. The Multiplier Block handles the complex rotations using sine and cosine values, while the Adder Block performs the final summation of the four paths required by the Radix-4 algorithm. The implementation uses 32-bit fixed-point arithmetic (1 sign bit, 15 integer bits, and 16 fractional bits) to balance precision and hardware area.

4. Synthesis and Verification

The design was coded in Verilog RTL and verified against a MATLAB reference model. Functional simulations confirmed bit-accurate results for a variety of test vectors. The design was synthesized using the Magnachip standard cell library with a target frequency of 100MHz.

Key Implementation Metrics: * Gate Count: 6.78 million gates. * Multipliers: 48 units (16 per stage). * Clock Frequency: 100 MHz. * Precision: 32-bit fixed-point.

The use of 48 multipliers allows for a fully pipelined architecture, maximizing throughput at the cost of area. For area-constrained applications, the number of multipliers could be reduced by reusing units across stages, albeit with a proportional decrease in speed.

5. Conclusion

This paper successfully demonstrated a new DIT Radix-4 FFT architecture optimized for sequential output. By implementing a 64-point FFT, the researchers proved the feasibility of the modular butterfly design for high-speed SoC applications. The sequential output characteristic makes this architecture particularly attractive for OFDM systems, where it can reduce overall system latency and complexity by removing reordering overhead.

Summary updated

Abstract

FFT(Fast Fourier Transform) 알고리즘에는 DIT(Decimation-In-Time)와 DIF(Decimation-In-Frequency)가 있다. DIF 알고리즘은 Radix-2/4/8 등의 다양한 종류와 그 구현 방법이 개발되어 사용되고 잇으나, DIT 알고리즘은 순차적인 출력을 낼 수 있는 장점이 있음에도 불구하고 다양한 알고리즘이 연구되지 못하였다. 이 논문에서는 새로운 DIT Radix-4 FFT의 나비연산기(butterfly) 구조를 제안하고 검증하였다. 제안 구조를 사용하여 64-point FFT 구조를 설계하고 Verilog로 코딩하여 구현함으로써 제안 구조의 효용성을 입증하였다. 48개의 곱셈기를 사용하여 합성하였으며 678만 게이트 수를 나타내었다. 따라서 제안된 DIT Radix-4 FFT 구조는 순차적인 FFT 출력을 필요로 하는 OFDM 통신용 SoC(System on a Chip)에 사용될 수 있을 것이다. Two basic FFT(Fast Fourier Transform) algorithms are the DIT(Decimation-In-Time) and the DIF (Decimation-In-Frequency). In spite of the advantage of the DIT algorithm is to generate a sequential output, various structures have not been made. In this paper, a new DIT Radix-4 FFT butterfly structure are proposed and implemented using Verilog coding. Through synthesis, it is shown that the 64-point FFT is implemented by 6.78 million gates. Since the proposed FFT structure has the advantage of a sequential output, it can be used in OFDM communication SoC(System on a Chip) which need a high speed FFT output.
BibTeX
@article{jang2015new,
  author = {Young-Beom Jang and Sang‐Woo Lee},
  title = {{A New DIT Radix-4 FFT Structure and Implementation}},
  journal = {Journal of the Korea Academia-Industrial Cooperation Society},
  year = {2015},
  doi = {10.5762/kais.2015.16.1.683},
}
Figure