This example describes a 32K-point fast Fourier transform (FFT) using the FFT Intel® FPGA intellectual property (IP) core. The FFT is a discrete Fourier transform (DFT) algorithm that reduces the number of computation needed from O(N^{2}) to O(NlogN) by decomposition. The DFT of a sequence x(n) is given by the following equation:

where k = 0, 1, … N-1 and N is the transform length.

In this design example, the transform length, N, is 32768. Using the decimation in time (DIT) method, the design breaks down the input sequence into odd and even samples that feeds into the two individual 16K-point FFT blocks implemented in parallel using the FFT Intel FPGA IP core. The results from the FFT Intel FPGA IP core are recombined and reordered to obtain the final FFT output. This is shown in Figure 1. Similar to the FFT Intel FPGA IP core, the design example uses Atlantic compliant input and output interfaces.

Download the files used in this example:

The use of this design is governed by, and subject to, the terms and conditions of the Intel Hardware Reference Design License Agreement.

Files in the zip download include:

- fft_32K.v—Top level design file implementing the 32K-point FFT
- parse_fft_input.v—Reorders the input sample into even and odd samples to feed into the two smaller 16K-point FFT blocks
- fft_small.v—Wrapper file generated by the FFT Intel FPGA IP. The core is configured to implement transform length of 16K, and it uses the streaming I/O data flow structure.
- combine_fft.v—Recombines the output of the individual 16K-point FFT blocks using the appropriate twiddle factors
- fft_32K_streaming_tb.v—Testbench for RTL simulation
- fft_32K_streaming_vo_msim.tcl—TCL script to automate the RTL simulation process in the ModelSim- Intel FPGA software
- fft_32K_tb.m—MATLAB model to verify the RTL simulation results

Figure 1 shows the top-level diagram of the 32K-point FFT design example.

*Figure 1. Top-Level Diagram of 32K-Point FFT Design*

Table 1 lists the ports and gives a description for each.