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.
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.
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