DFT/FFT IP Core Generator

Explanation

The Spiral DFT/FFT IP Generator automatically generates customized Discrete Fourier Transform (DFT) soft IP cores in synthesizable RTL Verilog. All of our designs use fast Fourier transform algorithms (FFTs). The user has control over a variety of parameters that control the functionality and cost/performance tradeoffs such as area and throughput. The generator is powered by our formula-driven hardware compilation tool targeting linear signal processing transforms. For more information, please see our overview paper and other references below.

An overview paper describing our tool won the 2014 ACM TODAES best paper award.

Our full tool flow has considerably more flexibility than the web version presented here, including non-power-of-two problem sizes and transforms other than the DFT. If you have an application that could benefit from our work, please feel free to contact us at the address given at the bottom of this page.

Generator

Select problem specification parameters: transform size, transform direction, and data type
Select parameters controlling implementation in order to balance the performance and cost of the desired implementation: architecture, radix, streaming width, data ordering, and BRAM budget
Click "Generate Verilog." A window will appear that includes: performance information (throughput and latency, in cycles); resource consumption (number of adders, multipliers, memories); and a link to your synthesizable register-transfer Verilog description. Additionally, the Verilog file will include a small example test bench to demonstrate the timing and control signals.

Please select parameters in order (from top to bottom), as the parameters chosen may restrict the choices below. For more information about any parameter, please click on (?) in the explanation column.

If you use the generator in your work we ask you to cite some of the associated publications below including the overview paper.

You may also want to consider this DFT generator that offers some improvements but is also more restricted in scope.

Benchmarks

Here are a few example benchmarks of the latest iteration of our generator, which is an improvement and considerable extension of the one above (see [1] and other references below). All designs are synthesized using Xilinx ISE, and all cost and performance data are collected after place and route.

DFT 1024, fixed point, throughput and latency:

DFT 256, floating point, throughput:

2-D DFT 256 x 256, fixed point, throughput:

FPGA accelerated software on the FPGA's embedded PowerPC processor. Both software and hardware are generated (see [6]):

References

Overview paper (ACM TODAES best paper award):
Peter A. Milder, Franz Franchetti, James C. Hoe, and Markus Püschel
Computer Generation of Hardware for Linear Digital Signal Processing Transforms
ACM Transactions on Design Automation of Electronic Systems, Vol. 17, No. 2, 2012.
Francois Serre and Markus Püschel
Optimal Circuits for Streamed Linear Permutations using RAM
Proc. FPGA, pp. 215-223, 2016
Peter A. Milder, Franz Franchetti, James C. Hoe, and Markus Püschel
Hardware Implementation of the Discrete Fourier Transform with Non-Power-of-Two Problem Size
Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2010.
Markus Püschel, Peter A. Milder, and James C. Hoe
Permuting Streaming Data Using RAMs
Journal of the ACM, 26(2), 2009
Peter A. Milder, James C. Hoe, and Markus Püschel
Automatic Generation of Streaming Datapaths for Arbitrary Fixed Permutations
Proc. Design, Automation and Test in Europe (DATE), 2009
Peter A. Milder, Franz Franchetti, James C. Hoe and Markus Püschel
Formal Datapath Representation and Manipulation for Implementing DSP Transforms
Proc. Design Automation Conference (DAC), 2008
Paolo D'Alberto, Franz Franchetti, Peter A. Milder, Aliaksei Sandryhaila, James C. Hoe, Jeremy Johnson, José M. F. Moura, Markus Püschel
Generating FPGA-Accelerated DFT Libraries
Proc. IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM) 2007
Peter A. Milder, Franz Franchetti, James C. Hoe and Markus Püschel
Discrete Fourier Transform Compiler: From Mathematical Representation to Efficient Hardware
CSSI Technical Report #CSSI-07-01, Carnegie Mellon University, 2007
Peter A. Milder, Mohammad Ahmad, James C. Hoe and Markus Püschel
Fast and Accurate Resource Estimation of Automatically Generated Custom DFT IP Cores
Proc. FPGA, pp. 211-220, 2006
Grace Nordin, Peter A. Milder, James C. Hoe and Markus Püschel
Automatic Generation of Customized Discrete Fourier Transform IPs
Proc. Design Automation Conference (DAC), pp. 471-474, 2005

More publications on IP cores for FPGAs/ASICs

More publications on the discrete/fast Fourier transform

Online generator for sorting IP cores

Copyrights to many of the above papers are held by the publishers. The attached PDF files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. Some links to papers above connect to IEEE Xplore with permission from IEEE, and viewers must follow all of IEEE's copyright policies.

More information

Contact: Peter Milder: peter.milder@stonybrook.edue (remove last letter)