# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 1 Introduction  
The DFT is a function that decomposes a discrete signal into its constituent frequencies. Computing the DFT is often an integral part of DSP systems, and so its efficient computation is very important. As is well known, the founding of DSP was significantly impacted by the development of the Cooley-Tukey FFT (Fast DFT) algorithm [1]. If \(x\) is a discrete signal of length \(N\), the DFT of \(x\) is given by  
\[X(k)=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}nk}, \tag{1}\]  
where \(k=0,1,\ldots,N-1\). If \(F\) is the Fourier transform matrix whose elements are the complex exponentials given in (1) taken in the proper order, the DFT \(X\) of \(x\) can be written  
\[X=Fx \tag{2}\]  
The matrix \(F\) is unitary, i.e., the scaling factor \(\frac{1}{\sqrt{N}}\) from (1) is included in \(F\). This is in contrast to the conventional DSP definition of \(F\), where the \(\frac{1}{\sqrt{N}}\) scaling factor is pushed into the inverse transform as the scale \(\frac{1}{N}\). Here, we assume that this scaling factor is included in \(F\). As is well known, multiplication of two complex numbers in \(\mathbb{C}^{1}\) requires either four real multiplications and two real additions or three real multiplications and five real additions. Using traditional approaches of calculating the DFT using the various FFT algorithms does not completely eliminate the need for complex multiplications. Although complex multiplications can be easily implemented in sophisticated software like MATLAB or high level programming languages like Python, it is a harder task in hardware or low cost/low performance digital signal processors. For example, complex multiplication in VHDL or C programming language needs additional libraries, and the code or hardwareproduced is irregular (not vectorizable). Thus, we were motivated to look into a DFT computation method that eliminates the need for complex multiplications and additions. The aforementioned Cooley-Tukey FFT algorithm is the most common method used for computing the DFT [1], though in a modified form to exploit the advantages of the \(N=2^{2}=4\) butterfly using the split-radix method [2]. This algorithm uses the divide and conquer approach that decomposes the DFT of a composite length \(N\) into smaller DFTs to reduce the resulting computational complexity. As mentioned before, using the Cooley-Tukey FFT algorithm requires the multiplication by complex twiddle factors (these are constants of magnitude 1 in \(\mathbb{C}\)) which stitch the smaller length DFTs together when recombining to produce the larger \(N\) length DFT. Even considering the prime factor FFT algorithm [3], the smallest un-factorizable DFT will require complex arithmetic. Our proposed method uses the real-valued eigenvectors of the DFT for computation and a combiner matrix that essentially replaces the twiddle factor multiplications. Our method uses only vector dot products and vector-scalar products. Therefore, our method has the potential to perform well on hardware with dedicated multiply-and-accumulate (MAC) units or on hardware designed to operate on one-dimensional arrays like vector processors. The eigenvectors obtained from the ortho-normalization of DFT projection matrices are slightly sparse, which further improves computational efficiency. However, there are a few disadvantages with our method. If the size of the DFT is a power of 2, the Cooley-Tukey FFT outperforms our method. Furthermore, the CORDIC algorithm [4] will perform better on hardware that can efficiently do bit shifts. Another limitation, though relatively unimportant in today's environment of inexpensive memory, is the need for extra memory to store the pre-computed eigenvectors. Our work done in [5] showed the relationship between the eigenstructure of the discrete Hirschman transform and the eigenstructure of the DFT. That work inspired us to develop the method presented here. By extension, our method can also be used to calculate the discrete Hirschman transform first introduced in [6].