Hardware implementation of the discrete fourier transform with non-power-of-two problem size

Peter A. Milder; Franz Franchetti; James C. Hoe; Markus Püschel

doi:10.1109/ICASSP.2010.5495517

Hardware implementation of the discrete fourier transform with non-power-of-two problem size

Peter A. Milder
, Franz Franchetti
, James C. Hoe
, Markus Püschel

Electrical Engineering

Carnegie Mellon University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

15 Scopus citations

Abstract

In this paper, we examine several algorithms suitable for the hardware implementation of the discrete Fourier transform (DFT) with non-power-of two problem size. We incorporate these algorithms into Spiral, a tool capable of automatically generating corresponding hardware implementations. We discuss how each algorithm can be used to generate different types of hardware structures, and we demonstrate that our tool is able to produce hardware implementations of non-powerof-two sized DFTs over a wide range of cost/performance tradeoff points.

Original language	English
Title of host publication	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1546-1549
Number of pages	4
ISBN (Print)	9781424442966
DOIs	https://doi.org/10.1109/ICASSP.2010.5495517
State	Published - 2010
Event	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Dallas, TX, United States Duration: Mar 14 2010 → Mar 19 2010

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)	1520-6149

Conference

Conference	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010
Country/Territory	United States
City	Dallas, TX
Period	03/14/10 → 03/19/10

Keywords

Algorithms
Discrete fourier transform
Field-programmable gate array
FPGA
High-level synthesis

Access to Document

10.1109/ICASSP.2010.5495517

Cite this

Milder, P. A., Franchetti, F., Hoe, J. C., & Püschel, M. (2010). Hardware implementation of the discrete fourier transform with non-power-of-two problem size. In 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings (pp. 1546-1549). Article 5495517 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2010.5495517

Milder, Peter A. ; Franchetti, Franz ; Hoe, James C. et al. / Hardware implementation of the discrete fourier transform with non-power-of-two problem size. 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2010. pp. 1546-1549 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{8326871f650d46b1892c78cd2c704148,

title = "Hardware implementation of the discrete fourier transform with non-power-of-two problem size",

abstract = "In this paper, we examine several algorithms suitable for the hardware implementation of the discrete Fourier transform (DFT) with non-power-of two problem size. We incorporate these algorithms into Spiral, a tool capable of automatically generating corresponding hardware implementations. We discuss how each algorithm can be used to generate different types of hardware structures, and we demonstrate that our tool is able to produce hardware implementations of non-powerof-two sized DFTs over a wide range of cost/performance tradeoff points.",

keywords = "Algorithms, Discrete fourier transform, Field-programmable gate array, FPGA, High-level synthesis",

author = "Milder, \{Peter A.\} and Franz Franchetti and Hoe, \{James C.\} and Markus P{\"u}schel",

year = "2010",

doi = "10.1109/ICASSP.2010.5495517",

language = "English",

isbn = "9781424442966",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1546--1549",

booktitle = "2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings",

note = "2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 ; Conference date: 14-03-2010 Through 19-03-2010",

}

Milder, PA, Franchetti, F, Hoe, JC & Püschel, M 2010, Hardware implementation of the discrete fourier transform with non-power-of-two problem size. in 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings., 5495517, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1546-1549, 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010, Dallas, TX, United States, 03/14/10. https://doi.org/10.1109/ICASSP.2010.5495517

Hardware implementation of the discrete fourier transform with non-power-of-two problem size. / Milder, Peter A.; Franchetti, Franz; Hoe, James C. et al.
2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2010. p. 1546-1549 5495517 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Hardware implementation of the discrete fourier transform with non-power-of-two problem size

AU - Milder, Peter A.

AU - Franchetti, Franz

AU - Hoe, James C.

AU - Püschel, Markus

PY - 2010

Y1 - 2010

N2 - In this paper, we examine several algorithms suitable for the hardware implementation of the discrete Fourier transform (DFT) with non-power-of two problem size. We incorporate these algorithms into Spiral, a tool capable of automatically generating corresponding hardware implementations. We discuss how each algorithm can be used to generate different types of hardware structures, and we demonstrate that our tool is able to produce hardware implementations of non-powerof-two sized DFTs over a wide range of cost/performance tradeoff points.

AB - In this paper, we examine several algorithms suitable for the hardware implementation of the discrete Fourier transform (DFT) with non-power-of two problem size. We incorporate these algorithms into Spiral, a tool capable of automatically generating corresponding hardware implementations. We discuss how each algorithm can be used to generate different types of hardware structures, and we demonstrate that our tool is able to produce hardware implementations of non-powerof-two sized DFTs over a wide range of cost/performance tradeoff points.

KW - Algorithms

KW - Discrete fourier transform

KW - Field-programmable gate array

KW - FPGA

KW - High-level synthesis

UR - https://www.scopus.com/pages/publications/78049411259

U2 - 10.1109/ICASSP.2010.5495517

DO - 10.1109/ICASSP.2010.5495517

M3 - Conference contribution

AN - SCOPUS:78049411259

SN - 9781424442966

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 1546

EP - 1549

BT - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010

Y2 - 14 March 2010 through 19 March 2010

ER -

Milder PA, Franchetti F, Hoe JC, Püschel M. Hardware implementation of the discrete fourier transform with non-power-of-two problem size. In 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2010. p. 1546-1549. 5495517. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2010.5495517

Hardware implementation of the discrete fourier transform with non-power-of-two problem size

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this