Building Conflict-Free FFT Schedules

Stephen Richardson, Dejan Marković, Andrew Danowitz, John Brunhaver, Mark Horowitz

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


A conflict-free schedule lets an FFT run to completion without ever having to pause for memory-conflict resolution. We show how to build such schedules for FFTs having any number of butterfly units B operating at any radix R, transforming any number of datapoints D. Our algorithm works for FFT datapaths with or without pipeline overlap, and for memory banks having any number of access ports. Specifically, it enables construction of conflict-free schedules using single-ported memory banks, which require less area than more traditional multi-ported designs.

Original languageEnglish (US)
Article number7070875
Pages (from-to)1146-1155
Number of pages10
JournalIEEE Transactions on Circuits and Systems I: Regular Papers
Issue number4
StatePublished - Apr 1 2015


  • Conflict-free scheduling
  • FFT
  • digital signal processor
  • fast Fourier transform
  • single-ported memory

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Building Conflict-Free FFT Schedules'. Together they form a unique fingerprint.

Cite this