# Fast 10-Point DFT Algorithm for Power System Harmonic Analysis
## 2 Preliminaries
.\]  
Consequently, the final algorithm for the 10-point DFT (14), which minimizes numerical complexity, can be written as  
\[\mathbf{X}_{10\times 1}=\mathbf{V}_{10}^{-1}\mathbf{\hat{V}}_{10}\mathbf{S}_{10 }^{(r)}\mathbf{T}_{10\times 14}\mathbf{W}_{14\times 12}\mathbf{T}_{12\times 10} \mathbf{S}_{10}^{(c)}\mathbf{V}_{10}^{-1}\mathbf{x}_{10\times 1} \tag{15}\]  
where  
\[\mathbf{T}_{12\times 10}= \begin{bmatrix}1&0&0&0&0&0&0&0&0&0\\ 0&0&1&0&1&0&0&0&0&0\\ 0&0&1&0&-1&0&0&0&0&0\\ 0&0&0&0&0&1&0&0&0&0\\ 0&1&0&1&0&0&0&0&0&0\\ 0&1&0&-1&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&-1&0&0\\ 0&0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1&0&1\\ 0&0&0&0&0&0&-1&0&0&0\\ 0&0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&1&0&1&0\end{bmatrix} ,\]  
\[\mathbf{T}_{10\times 14}= \begin{bmatrix}1&0&0&1&0&0&0&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0&0&0&0&0&0\\ -1&1&-1&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&1&1&1&0&0&0&0&0&0\\ 0&0&0&0&-1&1&-1&0&0&0&0&0&0\\ 0&0&0&0&1&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&1&0&1&0&0&0\\ 0&0&0&0&0&0&0&0&1&1&0&0&0\\ 0&0&0&0&0&0&0&0&0&1&0&1\\ 0&0&0&0&0&0&0&0&0&0&0&1&1\end{bmatrix} ,\]  
and  
\[\mathbf{W}_{14\times 12}= \begin{bmatrix}\mathbf{W}_{8\times 6}&\mathbf{0}_{8 \times 6}\\ \mathbf{0}_{6}&\mathbf{W}_{6}\end{bmatrix} ,\]where \(\mathbf{0}_{8\times 6}\) and \(\mathbf{0}_{6}\) are zero matrices,  
\[\mathbf{W}_{8\times 6}= \begin{bmatrix}1&0&0&0&0&0\\ 0&(C_{2}+C_{1})/2&0&0&0&0\\ 0&0&(C_{2}-C_{1})/2&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&(C_{2}+C_{1})/2&0\\ 0&0&0&0&(C_{2}-C_{1})/2\\ 0&0&0&0&0&1\end{bmatrix} ,\]  
\[\mathbf{W}_{6}= \begin{bmatrix}jS_{2}+jS_{1}&0&0&0&0&0\\ 0&jS_{2}-jS_{1}&0&0&0&0\\ 0&0&jS_{1}&0&0&0\\ 0&0&0&jS_{2}+jS_{1}&0&0\\ 0&0&0&0&jS_{2}-jS_{1}&0\\ 0&0&0&0&jS_{1}\end{bmatrix} .\]  
We can substitute real values into \(C_{1}\), \(C_{2}\), and \(S_{1}\), \(S_{2}\) using relations (9) and (10):  
\[ \begin{array}{ll}C_{1}=\cos(\pi/5)=0.8090,&jS_{1}=j\sin(\pi/5)=j0.5878,\\ C_{2}=\cos(2\pi/5)=0.3090,&jS_{2}=\sin(2\pi/5)=j0.9511.\end{array} \]  
The matrices \(\mathbf{W}_{8\times 6}\) and \(\mathbf{W}_{6}\) take the following form:  
\[\mathbf{W}_{8\times 6}= \begin{bmatrix}1&0&0&0&0&0\\ 0&0.5590&0&0&0&0\\ 0&0&-0.2500&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&0.5590&0\\ 0&0&0&0&-0.2500\\ 0&0&0&0&1\end{bmatrix} ,\]  
\[\mathbf{W}_{6}= \begin{bmatrix}1.5388&0&0&0&0&0\\ 0&0.3633&0&0&0&0\\ 0&0&0.5878&0&0&0\\ 0&0&0&1.5388&0&0\\ 0&0&0&0&0.3633&0\\ 0&0&0&0&0&0.5878\end{bmatrix} .\]  
The signal flow graph of the proposed algorithm is presented in Figure 1. The Matlab code of the 10-point DFT and the code verifying the each step of obtaining the 10-point DFT are included in the Supplementary Materials. The multiplication by 0.25 is performed with a 2 bit shift to the right. From an examination of Figure 1, it can be seen that the algorithm contains two multiplications by the number \(1/4\), which is a power of two. This operation is reduced to the usual shift of the multiplicand by two positions to the right. Due to the simplicity of implementation, such operations are usually not considered when evaluating computational complexity [41; 42]. Therefore, the proposed algorithm requires only 16 real multiplications and 92 real additions. Thus, in comparison with the base method [38; 39], which required 20 real multiplications and 84 additions, we decrease the number of real multiplications by 4 and increase the number of real additions by 8. Table 1 compares the number of real multiplication and addition operations for the proposed algorithm, the baseline algorithm [38], DFT, the mixed-radix fast Fourier transform (MFFT), prime factor algorithm (PFA), Winograd Fourier transform (WFTA), and SWIFT algorithms [43; 44]. Since multiplication is a more complicated operation from the point of view of its implementation [41; 42], the algorithm we propose has an advantage over the presented algorithms.