Introduction to ffast in digital multitone communication

Digital communication is a pervasive technology that many individuals, corporations, and governments rely upon to share information. Numerous researchers and engineers have focused their efforts on decreasing the time required for digital communication. One of the greatest such advancements is the Fast Fourier Transform (FFT), an algorithm [link] developed by James Cooley and John Tukey in 1965 that reduces the computational complexity of the DFT from $O$ $\left(N^2\right)$ to $O$ $(NlogN)$ for appropriately chosen $N$ , where $N$ is the signal length.

For many years, $O$ $(NlogN)$ was believed to be the best achievable run-time complexity for computing a discrete time Fourier transform (DFT). However, in recent years, researchers have developed a class of algorithms known as Sparse FFT algorithms [link] which run in sublinear time with respect to $N$ . These algorithms are able to have such a low run time complexity because they assume that the signal is sparse in its Fourier representation; that is, there are $k$ nonzero DFT coefficients where $k<<N$ .

In this report, we present one such Sparse FFT algorithm, the Fast Fourier Aliasing-based Sparse Transform (FFAST) [link] , as a method to significantly decrease computation time in a digital multitone (DMT) communication scheme because it can operate in $O$ $(klogk)$ . In Module 2, we present the DMT scheme and demonstrate signal sparsity. In Module 3, we outline the architecture of FFAST. In Module 4, we highlight several FFT methods used in our project. We describe our computational experiment and provide numerical results in Module 5 and discuss practical considerations and other future work in Module 6.