Efficient 2D DFT implementation in micro-threaded environments
Hi all from Madrid!
These last days I’ve been working on an application for testing the PThreading – Paradise Threading – library, the core of Paradise Engine and all our tools, in different systems by just downloading/executing a little application – which will be soon available for download -. But… what to test? At really… it could seem to be something easy to decide, but I can swore that it isn’t! It must to be something parallelizable and useful for us in a future, so… what better than a complete, efficient and smart 2D FFT/DFT – and inverses – implementation?
Good, so… let’s go. In this post I’ll talk about the DFT implementation, not the FFT this time, but almost all – at really, all – results can be extrapolated to the FFT case, just taking account that the FFT is orders of magnitude faster than the DFT calculation.
In a practical implementation of the two dimensional DFT , we explote the fact that the 2D DFT of a MxN matrix could be calculated by performing the one dimensional DFT of the M rows, and then the 1D DFT of the N columns. For more information visit this and this links.
Well, now that I’ve written a – very - little 2D DFT introduction, it’s time to talk about the practical implementation. In this post I’ll talk about two methods, from now labeled as A and B.
In this post I’ll assume that the MxN matrix data type is stored in a simple array of size M*N where each A(m,n) element one-dimensional index is given by the formula: Index = m*N+n, so rows elements are stored in contiguous memory addresses and the last elements of the K row is contiguous to the first elements of the K+1 row. Read more →