Abstract
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 language | English (US) |
---|---|
Article number | 7070875 |
Pages (from-to) | 1146-1155 |
Number of pages | 10 |
Journal | IEEE Transactions on Circuits and Systems I: Regular Papers |
Volume | 62 |
Issue number | 4 |
DOIs | |
State | Published - Apr 1 2015 |
Keywords
- Conflict-free scheduling
- FFT
- digital signal processor
- fast Fourier transform
- single-ported memory
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Hardware and Architecture