Verilog: FFT With 32K-Point Transform Length

This example describes a 32K-point fast Fourier transform (FFT) using the Altera® FFT IP MegaCore® . The FFT is a discrete Fourier transform (DFT) algorithm which reduces the number of computation needed from O(N2) to O(NlogN) by decomposition. The DFT of a sequence x(n) is given by the following equation:

Equation for the DFT of a sequence x(n) 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 which feeds into the two individual 16K-point FFT blocks implemented in parallel using the FFT IP MegaCore. The results from the FFT IP MegaCore are recombined and reordered to obtain the final FFT output. This is shown in Figure 1. Similar to the FFT IP MegaCore, 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 Altera 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 IP MegaCore. 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 ModelSim
  • 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

Figure 1. Top-Level Diagram of 32K Point FFT Design
View Full Size

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

Table 1. 32K-Point FFT Port Listing

Port Name Type Description
data_real_in[15:0], data_imag_in[15:0]Input16-bit complex data inputs
clkInputFFT system clock
resetInputActive high reset
master_sink_davInputMaster sink data available signal: Asserted by the FFT slave data source to indicate the availability of data sample for input to the FFT function
master_sink_enaOutputMaster sink write enable signal: Asserted by the FFT function to indicate that data can be written into the function
master_sink_sopInputInput start of packet: Indicates to the FFT function the start of an input data block. Should be asserted for one clock cycle synchronous with the first input data sample
fft_real_out[15:0], fft_imag_out[15:0]Output16-bit complex data outputs
exponent_out[5:0]OutputSigned block exponent: Accounts for scaling of internal signal values during FFT computation
master_source_davInputAsserted by the slave sink on the output of the FFT function to indicate that it can accept one block of output samples
master_source_enaOutputMaster source enable: Asserted by the FFT function when data is available to be output by the FFT
master_source_sopOutputOutput start of packet: Asserted on first output sample of each block
master_source_eopOutputOutput end of packet: Asserted on last output sample of each block

Related Links

For more information on related features used in this design example in your project, go to:

Design Examples Disclaimer

These design examples may only be used within Altera Corporation devices and remain the property of Altera. They are being provided on an “as-is” basis and as an accommodation; therefore, all warranties, representations, or guarantees of any kind (whether express, implied, or statutory) including, without limitation, warranties of merchantability, non-infringement, or fitness for a particular purpose, are specifically disclaimed. Altera expressly does not recommend, suggest, or require that these examples be used in combination with any other product not provided by Altera.