## 3 Small Size 1D-QDFT Algorithms
### Algorithm 7, \(N=8\)  
Let \(\mathbf{x}_{8}=[x_{0},x_{1},x_{3},x_{4},x_{5},x_{6},x_{7}]^{T}\) and \(\mathbf{y}_{8}=[y_{0},y_{1},y_{3},y_{4},y_{5},y_{6},y_{7}]^{T}\) be the eight-entry input and output vectors, and \(x_{n}\in H,y_{m}\in H,m,n=0,1,2,3,4,5,6,7\). The 8-point QDFT can be represented as  
\[\mathbf{y}_{8}=\mathbf{E}_{8}\mathbf{x}_{8}, \tag{20}\]  
where  
\[\mathbf{E}_{8}= \begin{bmatrix}1&1&1&1&1&1&1&1\\ 1&a_{8}&b_{8}&-a_{8}^{*}&-1&-a_{8}&-b_{8}&a_{8}^{*}\\ 1&b_{8}&-1&-b_{8}&1&b_{8}&-1&-b_{8}\\ 1&-a_{8}^{*}&-b_{8}&a_{8}&-1&a_{8}^{*}&b_{8}&-a_{8}\\ 1&-1&1&-1&1&-1&1&-1\\ 1&-a_{8}&b_{8}&a_{8}^{*}&-1&a_{8}&-b_{8}&-a_{8}^{*}\\ 1&-b_{8}&-1&b_{8}&1&-b_{8}&-1&b_{8}\\ 1&a_{8}^{*}&-b_{8}&-a_{8}&-1&-a_{8}^{*}&b_{8}&a_{8}\end{bmatrix} ,\]  
and  
\[a_{8}=0.70711-0.40825i-0.40825j-0.40825k,\]  
\[b_{8}=-0.57735i-0.57735j-0.57735k.\]  
Let us now change the order of the rows of matrix \(\mathbf{E}_{8}\) using the following permutation:  
\[\pi_{8}= \begin{pmatrix}0&1&2&3&4&5&6&7\\ 0&4&2&5&1&6&3&7\end{pmatrix} .\]  
We obtain the following matrix:  
\[\tilde{\mathbf{E}}_{8}= \begin{bmatrix}1&1&1&1&1&1&1&1\\ 1&-1&1&-1&1&-1&1&-1\\ 1&b_{8}&-1&-b_{8}&1&b_{8}&-1&-b_{8}\\ 1&-b_{8}&-1&b_{8}&1&-b_{8}&-1&b_{8}\\ 1&a_{8}&b_{8}&-a_{8}^{*}&-1&-a_{8}&-b_{8}&a_{8}^{*}\\ 1&-a_{8}^{*}&-b_{8}&a_{8}&-1&a_{8}^{*}&b_{8}&-a_{8}\\ 1&-a_{8}&b_{8}&a_{8}^{*}&-1&a_{8}&-b_{8}&-a_{8}^{*}\\ 1&a_{8}^{*}&-b_{8}&-a_{8}&-1&-a_{8}^{*}&b_{8}&a_{8}\end{bmatrix} = \begin{bmatrix} \mathbf{A}_{4}^{(8)}&\mathbf{A}_{4}^{(8)}\\ \mathbf{B}_{4}^{(8)}&-\mathbf{B}_{4}^{(8)}\end{bmatrix} ,\]  
Figure 6: Data-flow diagram for the 7-point QDFT. where  
\[\mathbf{A}_{4}^{(8)}= \begin{bmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&b_{8}&-1&-b_{8}\\ 1&-b_{8}&-1&b_{8}\end{bmatrix} ,\ \mathbf{B}_{4}^{(8)}= \begin{bmatrix}1&a_{8}&b_{8}&-a_{8} ^{*}\\ 1&-a_{8}^{*}&-b_{8}&a_{8}\\ 1&-a_{8}&b_{8}&a_{8}^{*}\\ 1&a_{8}^{*}&-b_{8}&-a_{8}\end{bmatrix} .\]  
The matrix \(\tilde{\mathbf{E}}_{8}\) of such a structure can be written as  
\[\tilde{\mathbf{E}}_{8}=\left(\mathbf{A}_{4}^{(8)}\oplus\mathbf{B}_{4}^{(8)} \right)(\mathbf{H}_{2}\otimes\mathbf{I}_{4}). \tag{21}\]  
The matrix \(\mathbf{A}_{4}^{(8)}\) has analogous structure so  
\[\mathbf{A}_{4}^{(8)}= \begin{bmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&b_{8}&-1&-b_{8}\\ 1&-b_{8}&-1&b_{8}\end{bmatrix} = \begin{bmatrix}\mathbf{A}_{2}^{(8)}&\mathbf{A }_{2}^{(8)}\\ \mathbf{B}_{2}^{(8)}&-\mathbf{B}_{2}^{(8)}\end{bmatrix} =\left(\mathbf{A}_{2}^ {(8)}\oplus\mathbf{B}_{2}^{(8)}\right)(\mathbf{H}_{2}\otimes\mathbf{I}_{2}), \tag{22}\]  
where  
\[\mathbf{A}_{2}^{(8)}= \begin{bmatrix}1&1\\ 1&-1\end{bmatrix} =\mathbf{H}_{2},\ \mathbf{B}_{2}^{(8)}= \begin{bmatrix}1&b_{8}\\ 1&-b_{8}\end{bmatrix} =\mathbf{H}_{2} \begin{bmatrix}1&0\\ 0&b_{8}\end{bmatrix} .\]  
Let us reorder the columns of the matrix \(\mathbf{B}_{4}^{(8)}\) using the \(\pi_{4}\) permutation. We obtain  
\[\tilde{\mathbf{B}}_{4}^{(8)}= \begin{bmatrix}1&b_{8}&a_{8}&-a_{8}^{*}\\ 1&-b_{8}&-a_{8}^{*}&a_{8}\\ 1&b_{8}&-a_{8}&a_{8}^{*}\\ 1&-b_{8}&a_{8}^{*}&-a_{8}\end{bmatrix} = \begin{bmatrix}\mathbf{B}_{2}^{(8)}& \mathbf{C}_{2}^{(8)}\\ \mathbf{B}_{2}^{(8)}&-\mathbf{C}_{2}^{(8)}\end{bmatrix} =(\mathbf{H}_{2} \otimes\mathbf{I}_{2})(\mathbf{B}_{2}^{(8)}\oplus\mathbf{C}_{2}^{(8)}), \tag{23}\]  
where  
\[\mathbf{C}_{2}^{(8)}= \begin{bmatrix}a_{8}&-a_{8}^{*}\\ -a_{8}^{*}&a_{8}\end{bmatrix} =\mathbf{H}_{2} \begin{bmatrix}\frac{1}{2}(a_{8}- a_{8}^{*})&0\\ 0&\frac{1}{2}(a_{8}+a_{8}^{*})\end{bmatrix} \mathbf{H}_{2}.\]  
Taking into account the obtained factorization schemes, the final computational procedure can be written as follows:  
\[\mathbf{y}_{8}=\mathbf{P}_{8}^{(2)}\mathbf{W}_{8}^{(4)}\mathbf{W}_{8}^{(3)} \mathbf{D}_{8}\mathbf{W}_{8}^{(2)}\mathbf{P}_{8}^{(1)}\mathbf{W}_{8}^{(1)} \mathbf{x}_{8}, \tag{24}\]  
where  
\[\mathbf{W}_{8}^{(1)}=\mathbf{H}_{2}\otimes\mathbf{I}_{4}= \begin{bmatrix}1&0&0& 0&1&0&0\\ 0&1&0&0&0&1&0&0\\ 0&0&1&0&0&0&1&0\\ 0&0&0&1&0&0&0&1\\ 1&0&0&0&-1&0&0&0\\ 0&1&0&0&0&-1&0&0\\ 0&0&1&0&0&0&-1&0\\ 0&0&0&1&0&0&0&-1\end{bmatrix}