Special purpose hardware for discrete Fourier transform implementation (Q1319523)

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.