An example application: fourier transform

This chapter represents an example of accelerating the Cooley-Tukey algorithm with the Maxeler MAX3 machine and gives the results of the achieved acceleration. First, it explains the importance and usages of the Cooley-Tukey algorithm. Second, it gives mathematical explanation of the algorithm and algorithm’s pseudo code and explains different ways to implement the algorithm. The implementation with best time and memory complexity is explained in detail. Third, it explains how the algorithm has been accelerated using DataFlow engines. Fourth, it explains the experiments done to measure acceleration and present the results. The final results are presented as various graphs with explanations.