# Fast 10-Point DFT Algorithm for Power System Harmonic Analysis
## 2 Preliminaries  
For a sequence of \(N\) complex numbers \(\{\mathbf{x_{n}}\}:=x_{0},x_{1},\ldots,x_{N-1}\), \(\{\mathbf{X_{k}}\}:=X_{0},X_{1},\ldots,\)\(X_{N-1}\) the Discrete Fourier Transform is defined by  
\[X_{k}=\sum_{n=0}^{N-1}x_{n}e^{-\frac{2\pi}{N}kn},\qquad k=0,1,\ldots,N-1 \tag{1}\]  
where \(e\) is Euler's number. If we assume \(w_{N}=e^{-\frac{2\pi}{N}}\), the DFT can be expressed as  
\[X_{k}=\sum_{n=0}^{N-1}x_{n}w_{N}^{kn},\qquad k=0,1,\ldots,N-1 \tag{2}\]  
For \(N=10\), the DFT has the following matrix notation:  
\[\mathbf{X}_{10\times 1}=\mathbf{W}_{10}\mathbf{x}_{10\times 1} \tag{3}\]  
where  
where  
\[\mathbf{V_{10}^{-1}}= \begin{bmatrix}1&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&1\\ 0&0&1&0&0&0&0&0&1&0\\ 0&0&0&1&0&0&0&1&0&0\\ 0&0&0&0&1&0&1&0&0&0\\ 0&0&0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&-1&0&0&0\\ 0&0&0&1&0&0&0&-1&0&0\\ 0&0&1&0&0&0&0&0&-1&0\\ 0&1&0&0&0&0&0&0&-1\end{bmatrix} ,\]  
\[\mathbf{W_{10}^{(1)}}= \begin{bmatrix}1&1&1&1&1&1&1&1&1\\ 1&C_{1}&C_{2}&C_{3}&C_{4}&-1&C_{4}&C_{3}&C_{2}&C_{1}\\ 1&C_{2}&C_{4}&C_{4}&C_{2}&1&C_{2}&C_{4}&C_{4}&C_{2}\\ 1&C_{3}&C_{4}&C_{1}&C_{2}&-1&C_{2}&C_{1}&C_{4}&C_{3}\\ 1&C_{4}&C_{2}&C_{2}&C_{4}&1&C_{4}&C_{2}&C_{2}&C_{4}\\ 1&-1&1&-1&1&-1&1&-1&1&-1\\ 0&-jS_{4}&jS_{2}&-jS_{2}&jS_{4}&0&-jS_{4}&jS_{2}&-jS_{2}&jS_{4}\\ 0&-jS_{3}&jS_{4}&jS_{1}&-jS_{2}&0&jS_{2}&-jS_{1}&-jS_{4}&jS_{3}\\ 0&-jS_{2}&-jS_{4}&jS_{4}&jS_{2}&-jS_{4}&jS_{4}&jS_{2}\\ 0&-jS_{1}&-jS_{2}&-jS_{3}&-jS_{4}&0&jS_{4}&jS_{3}&jS_{2}&jS_{1}\end{bmatrix} ,\]  
and coefficients \(C_{m}\), \(jS_{m}\), for \(m=1,2,3,4\), are equal:  
\[C_{m}=(w_{10}^{m}+w_{10}^{-m})/2,\]  
\[-jS_{m}=(w_{10}^{m}-w_{10}^{-m})/2.\]  
Using [PERSON]'s formula, \(C_{m}\) and \(jS_{m}\) are reduced to [38]  
\[C_{m}=\left(e^{-\frac{\beta\pi}{10}m}+e^{\frac{\beta\pi}{10}m}\right)/2=\cos(m \pi/5) \tag{9}\]  
\[jS_{m}=\left(e^{-\frac{\beta\pi}{10}m}-e^{\frac{\beta\pi}{10}m}\right)/2=j\sin (m\pi/5) \tag{10}\]  
We create auxiliary variables \(a_{0}=x_{0}\), \(a_{5}=x_{5}\), \(a_{i}=(x_{i}+x_{10-i})/2\), and \(a_{10-i}=(x_{i}-x_{10-i})/2\) for \(i=1,2,3,4\), as in [38]:  
\[\mathbf{a}_{10\times 1}=\mathbf{V}_{10}\mathbf{x}_{10\times 1},\]  
where matrix \(\mathbf{V}_{10}\) is defined in (7) and  
\[\mathbf{a}_{10\times 1}= \begin{bmatrix}a_{0}&a_{1}&a_{2}&a_{3}&a_{4}&a_{5}&a_{6}&a_{7 }&a_{8}&a_{9}\end{bmatrix} ^{T}.\]  
Then, the 10-point DFT algorithm (8) takes the following form:  
\[\mathbf{X}_{10\times 1}=\mathbf{V}_{10}^{-1}\mathbf{W}_{10}^{(2)}\mathbf{V}_{10}^ {-1}\mathbf{x}_{10\times 1} \tag{11}\]where  
\[\mathbf{W}_{10}^{(2)}= \begin{bmatrix}1&1&1&1&1&1&0&0&0&0\\ 1&C_{1}&C_{2}&C_{3}&C_{4}&-1&0&0&0&0\\ 1&C_{2}&C_{4}&C_{4}&C_{2}&1&0&0&0&0\\ 1&C_{3}&C_{4}&C_{1}&C_{2}&-1&0&0&0&0\\ 1&C_{4}&C_{2}&C_{2}&C_{4}&1&0&0&0&0\\ 1&-1&1&-1&1&-1&0&0&0&0\\ 0&0&0&0&0&0&jS_{4}&-jS_{2}&jS_{2}&-jS_{4}\\ 0&0&0&0&0&0&-jS_{2}&jS_{1}&jS_{4}&-jS_{3}\\ 0&0&0&0&0&0&jS_{2}&jS_{4}&-jS_{4}&-jS_{2}\\ 0&0&0&0&0&0&-jS_{4}&-jS_{3}&-jS_{2}&-jS_{1}\end{bmatrix} .\]  
Using \(C_{m}\) and \(S_{m}\), as defined in (9), and (10), the reduction formulas of trigonometric functions \(\sin(\pi-a)=\sin(a)\) and \(\cos(\pi-a)=-\cos(a)\), we obtain \(C_{3}=-C_{2}\), \(C_{4}=-C_{1}\), \(S_{3}=S_{2}\), and \(S_{4}=S_{1}\). This results in a new matrix form:  
\[\mathbf{W}_{10}^{(2)}= \begin{bmatrix}1&1&1&1&1&0&0&0\\ 1&C_{1}&C_{2}&-C_{2}&-C_{1}&-1&0&0&0\\ 1&C_{2}&-C_{1}&-C_{1}&C_{2}&1&0&0&0\\ 1&-C_{2}&-C_{1}&C_{1}&C_{2}&-1&0&0&0\\ 1&-C_{1}&C_{2}&C_{2}&-C_{1}&1&0&0&0\\ 1&-1&1&-1&1&-1&0&0&0&0\\ 0&0&0&0&0&jS_{1}&-jS_{2}&jS_{2}&-jS_{1}\\ 0&0&0&0&0&0&-jS_{2}&jS_{1}&jS_{1}&-jS_{2}\\ 0&0&0&0&0&0&jS_{2}&jS_{1}&-jS_{2}&-jS_{1}\end{bmatrix}  \tag{12}\]  
Now, according to [38], we introduce the new variables \(B_{i}=(A_{i}+A_{5-i})/2\), \(B_{5-i}=(A_{i}-A_{5-i})/2\) for \(i=0,1,2\), and \(B_{5+k}=(A_{5+k}+A_{10-k})/2\), \(B_{10-k}=(A_{5+k}-A_{10-k})/2\) for \(k=1,2\); then, we can write the following:  
\[\mathbf{B}_{10\times 1}=0.5\mathbf{\hat{V}}_{10}\mathbf{A}_{10\times 1},\]  
where  
\[\mathbf{B}_{10\times 1}= \begin{bmatrix}B_{0}&B_{1}&B_{2}&B_{3}&B_{4}&B_{5}&B_{6}&B _{7}&B_{8}&B_{9}\end{bmatrix}