## 3 Small Size 1D-QDFT Algorithms
### Algorithm 4, \(N=5\)  
Let \(\mathbf{x}_{5}=\big{[}x_{0},x_{1},x_{2},x_{3},x_{4}\big{]}^{T}\) and \(\mathbf{y}_{5}=\big{[}y_{0},y_{1},y_{2},y_{3},y_{4}\big{]}^{T}\) be five-entry input and output vectors, and \(x_{n}\in H,y_{m}\in H,m,n=0,1,2,3,4\). The 5-point QDFT can be represented as  
\[\mathbf{y}_{5}=\mathbf{E}_{5}\mathbf{x}_{5}, \tag{8}\]  
where  
\[\mathbf{E}_{5}= \begin{bmatrix}1&1&1&1&1\\ 1&a_{5}&b_{5}&b_{5}^{*}&a_{5}^{*}\\ 1&b_{5}&a_{5}^{*}&a_{5}&b_{5}^{*}\\ 1&b_{5}^{*}&a_{5}&a_{5}^{*}&b_{5}\\ 1&a_{5}^{*}&b_{5}^{*}&b_{5}&a_{5}\end{bmatrix} ,\]  
\[a_{5}=0.30902-0.54909i-0.54909j-0.54909k,\]  
\[a_{5}^{*}=0.30902+0.54909i+0.54909j+0.54909k,\]  
\[b_{5}=-0.80902-0.33936i-0.33936j-0.33936k,\]  
\[b_{5}^{*}=-0.80902+0.33936i+0.33936j+0.33936k.\]  
Let us now change the order of the rows and columns of matrix \(\mathbf{E}_{5}\) using the following permutation:  
\[\pi_{5}= \begin{pmatrix}0&1&2&3&4\\ 0&1&2&4&3\end{pmatrix} .\]  
Figure 3: Data-flow diagram for the 4-point QDFT. Then, we obtain the following matrix:  
\[\mathbf{E}_{5}= \begin{bmatrix}1&1&1&1&1\\ 1&a_{5}&b_{5}&a_{5}^{s}&b_{5}^{s}\\ 1&b_{5}&a_{5}^{s}&b_{5}^{s}&a_{5}\\ 1&a_{5}^{s}&b_{5}^{s}&a_{5}&b_{5}\\ 1&b_{5}^{s}&a_{5}&b_{5}&a_{5}^{s}\end{bmatrix} .\]  
Let us perform the following decomposition:  
\[\mathbf{\tilde{E}}_{5}= \begin{bmatrix}1&1&1&1&1\\ 1&a_{5}&b_{5}&a_{5}^{s}&b_{5}^{s}\\ 1&b_{5}&a_{5}^{s}&b_{5}^{s}&a_{5}\\ 1&a_{5}^{s}&b_{5}^{s}&a_{5}&b_{5}\\ 1&b_{5}^{s}&a_{5}&b_{5}&a_{5}^{s}\end{bmatrix} =\underbrace{ \begin{bmatrix}1&1&1& 1&1\\ 1&0&0&0&0\\ 1&0&0&0&0\\ 1&0&0&0&0\\ 1&0&0&0&0\end{bmatrix} }_{\mathbf{E}_{5}^{(1)}}+\underbrace{ \begin{bmatrix}0 &0&0&0&0\\ 0&a_{5}&b_{5}&a_{5}^{s}&b_{5}^{s}\\ 0&b_{5}&a_{5}^{s}&b_{5}^{s}&a_{5}\\ 0&b_{5}^{s}&a_{5}&b_{5}^{s}\end{bmatrix} }_{\mathbf{E}_{5}^{(2)}},\]  
\[\mathbf{\tilde{E}}_{5}^{(2)}= \begin{bmatrix}0&0&0&0&0\\ 0&&&&\mathbf{A}_{4}^{(5)}\\ 0&&&&\end{bmatrix} ,\;\mathbf{A}_{4}^{(5)}= \begin{bmatrix}\mathbf{A}_{2}^{(5)}& \mathbf{B}_{2}^{(5)}\\ \mathbf{B}_{2}^{(5)}&\mathbf{A}_{2}^{(5)}\end{bmatrix} ,\;\mathbf{A}_{2}^{(5)} = \begin{bmatrix}a_{5}&b_{5}\\ b_{5}&a_{5}^{s}\end{bmatrix} ,\;\mathbf{B}_{2}^{(5)}= \begin{bmatrix}a_{5}^{s}& b_{5}^{s}\\ b_{5}^{s}&a_{5}\end{bmatrix} .\]  
Due to the special structure of the \(\mathbf{A}_{4}^{(5)}\) matrix, it can be written as follows [31]:  
\[\mathbf{A}_{4}^{(5)}=(\mathbf{H}_{2}\otimes\mathbf{I}_{2})\left[\frac{1}{2} \left(\mathbf{A}_{2}^{(5)}+\mathbf{B}_{2}^{(5)}\right)\oplus\frac{1}{2}\left( \mathbf{A}_{2}^{(5)}-\mathbf{B}_{2}^{(5)}\right)\right](\mathbf{H}_{2}\otimes \mathbf{I}_{2}),\]  
where the matrices  
\[\frac{1}{2}\left(\mathbf{A}_{2}^{(5)}+\mathbf{B}_{2}^{(5)}\right)=\frac{1}{2} \begin{bmatrix}a_{5}+a_{5}^{s}&b_{5}+b_{5}^{s}\\ b_{5}+b_{5}^{s}&a_{5}+a_{5}^{s}\end{bmatrix} ,\;\text{and}\;\frac{1}{2}\left( \mathbf{A}_{2}^{(5)}-\mathbf{B}_{2}^{(5)}\right)=\frac{1}{2} \begin{bmatrix}a_ {5}-a_{5}^{s}&b_{5}-b_{5}^{s}\\ b_{5}-b_{5}^{s}&a_{5}^{s}-a_{5}\end{bmatrix} ,\]  
can be written in the form  
\[\frac{1}{2}\left(\mathbf{A}_{2}^{(5)}+\mathbf{B}_{2}^{(5)}\right)=\mathbf{H}_{ 2}\;diag\Big{(}s_{0}^{(5)},s_{1}^{(5)}\Big{)}\mathbf{H}_{2},\;\frac{1}{2} \left(\mathbf{A}_{2}^{(5)}-\mathbf{B}_{2}^{(5)}\right)=\mathbf{T}_{2\times 3}\; diag\Big{(}s_{2}^{(5)},\;s_{3}^{(5)},\;s_{4}^{(5)}\Big{)}\mathbf{T}_{3\times 2},\]  
\[\mathbf{T}_{2\times 3}= \begin{bmatrix}1&0&1\\ 0&1&1\end{bmatrix} ,\;\mathbf{T}_{3\times 2}= \begin{bmatrix}1&0\\ 0&1\\ 1&1\end{bmatrix}