Accelerating Discrete Fourier Transforms with Dot-product engine - Miao Hu: 2016 International Conference on Rebooting Computing
Discrete Fourier Transforms (DFT) are extremely useful in signal processing. Usually they are computed with the Fast Fourier Transform (FFT) method as it reduces the computing complexity from O(N^2) to O(Nlog(N)). However, FFT is still not powerful enough for many real-time tasks which have stringent requirements on throughput, energy efficiency and cost, such as Internet of Things (IoT). In this paper, we present a solution of computing DFT using the dot-product engine (DPE) a one transistor one memristor (1T1M) crossbar array with hybrid peripheral circuit support. With this solution, the computing complexity is further reduced to a constant O() independent of the input data size, where is the timing ratio of one DPE operation comparing to one real multiplication operation in digital systems.
Miao Hu delivers a talk on discrete fourier transforms, at ICRC 2016.