Special purpose hardware for discrete Fourier transform implementation

DOI10.1016/0167-8191(94)90082-5MaRDI QIDQ1319523zbMATH OpenOpenAlexFDO

Authors Michael Conner, R. Tolimieri

Publication date 30 October 1994

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(94)90082-5

zbMATH Keywords

discrete Fourier transformFourier matrixparallel hardware implementationpipeline timing resultspre-addition stages

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10)

Review text

Let \(n\) be the product of either 2 or 3 distinct primes. Up to permutations, some discrete Fourier transform (DFT) algorithms can be expressed as a factorization \(F = CA\) of the \(n\)-th Fourier matrix \(F\), where the pre-addition matrix \(A\) is sparse, well-structured and consists of elements from \(\{-1,0,1\}\). The matrix \(C\) is block diagonal, each block being skew circulant or the tensor product of skew circulants. The authors propose a highly parallel hardware implementation of the permutation and the pre-addition stages of this algorithm. This hardware has enough parallel structure to achieve the pre-addition phase at the full bus bandwidth of any machine. Pipeline timings are given showing a nearly perfect hardware utilization. Examples for the DFT's of lengths 35 and 105 are described in detail.

Recommendations

• Hardware efficient fast computation of the discrete Fourier transform
• scientific article; zbMATH DE number 4129958
• A prime factor FTT algorithm using distributed arithmetic
• scientific article; zbMATH DE number 3915602
• On the structure of efficient DFT algorithms

This page was built for publication: Special purpose hardware for discrete Fourier transform implementation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1319523)