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.

See also: online generator for sorting network IP cores

Generator

  1. Select problem specification parameters: transform size, transform direction, and data type
  2. 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
  3. 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.

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

  1. 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.
  2. 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.
  3. Markus Püschel, Peter A. Milder, and James C. Hoe
    Permuting Streaming Data Using RAMs
    Journal of the ACM, 26(2), 2009
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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

More information

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

Copyright (c) 2005-2014 Peter A. Milder for the Spiral Project, Carnegie Mellon University