## 3 Small Size 1D-QDFT Algorithms
### Algorithm 6, \(N=7\)  
Let \(\mathbf{x}_{7}=\big{[}x_{0},x_{1},x_{3},x_{4},x_{5},x_{6}\big{]}^{T}\) and \(\mathbf{y}_{7}=\big{[}y_{0},y_{1},y_{3},y_{4},y_{5},y_{6}\big{]}^{T}\) be seven-entry input and output vectors, and \(x_{n}\in H,y_{m}\in H,\,m,n=0,1,2,3,4,5,6\). The 7-point QDFT can be represented as  
\[\mathbf{y}_{7}=\mathbf{E}_{7}\mathbf{x}_{7}, \tag{13}\]  
Figure 5: Data-flow diagram for the 6-point QDFT. where  
\[\mathbf{E}_{7}= \begin{bmatrix}1&1&1&1&1&1&1\\ 1&a_{7}&b_{7}&c_{7}&c_{7}^{*}&b_{7}^{*}&a_{7}^{*}\\ 1&b_{7}&c_{7}^{*}&a_{7}^{*}&a_{7}&c_{7}&b_{7}^{*}\\ 1&c_{7}&a_{7}^{*}&b_{7}^{*}&b_{7}^{*}&a_{7}&c_{7}^{*}\\ 1&c_{7}^{*}&a_{7}&b_{7}^{*}&b_{7}&a_{7}^{*}&c_{7}\\ 1&b_{7}^{*}&c_{7}&a_{7}&a_{7}^{*}&c_{7}^{*}&b_{7}\\ 1&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&c_{7}&b_{7}&a_{7}\end{bmatrix} ,\]  
\[a_{7}=0.62349-0.45139i-0.45139j-0.45139k,\]  
\[b_{7}=-0.22252-0.56287i-0.56287j-0.56287k,\]  
\[c_{7}=-0.90097-0.2505i-0.2505j-0.2505k.\]  
Let us now change the order of the columns and rows of matrix \(\mathbf{E}_{7}\) using the following permutation:  
\[\pi_{7}= \begin{pmatrix}0&1&2&3&4&5&6\\ 0&1&2&3&6&5&4\end{pmatrix} .\]  
We obtain the following matrix:  
\[\mathbf{E}_{7}= \begin{bmatrix}1&1&1&1&1&1&1\\ 1&a_{7}&b_{7}&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}\\ 1&b_{7}&c_{7}^{*}&a_{7}^{*}&b_{7}^{*}&c_{7}&a_{7}\\ 1&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}^{*}\\ 1&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}&c_{7}^{*}\\ 1&b_{7}^{*}&c_{7}&a_{7}&b_{7}^{*}&c_{7}&a_{7}^{*}&b_{7}\end{bmatrix} .\]  
Let us perform the following decomposition:  
\[\mathbf{E}_{7}= \begin{bmatrix}1&1&1&1&1&1\\ 1&a_{7}&b_{7}&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}\\ 1&b_{7}&c_{7}^{*}&a_{7}^{*}&b_{7}^{*}&c_{7}&a_{7}\\ 1&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}^{*}\\ 1&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}&c_{7}^{*}\\ 1&b_{7}^{*}&c_{7}&a_{7}&b_{7}&c_{7}^{*}&a_{7}^{*}\\ 1&c_{7}^{*}&a_{7}&b_{7}^{*}&c_{7}&a_{7}^{*}&b_{7}\end{bmatrix} =\underbrace{ \begin{bmatrix}1&1&1&1&1&1\\ 1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0\end{bmatrix} }_{\mathbf{E}_{7}^{(1)}}+\underbrace{ \begin{bmatrix}0&0&0&0&0&0 &0\\ 0&a_{7}&b_{7}&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}\\ 0&b_{7}&c_{7}^{*}&a_{7}^{*}&b_{7}^{*}&c_{7}&a_{7}\\ 0&c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}^{*}\\ 0&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}\end{bmatrix} }_{\mathbf{E}_{7}^{(2)}},\]  
\[\mathbf{E}_{7}^{(2)}= \begin{bmatrix}0&0&0&0&0&0&0\\ 0&&&&\\ 0&&&&\\ 0&&&&\\ 0&&&&\\ 0&&&&\\ 0&&&&\\ \end{bmatrix} ,\ \mathbf{A}_{6}^{(7)}= \begin{bmatrix}a_{7}&b_{7}&c_{7}&a_{7}^{*}&b_{7}^{*}& c_{7}^{*}\\ b_{7}&c_{7}^{*}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}\\ c_{7}&a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}^{*}\\ a_{7}^{*}&b_{7}^{*}&c_{7}^{*}&a_{7}&b_{7}&c_{7}^{*}\\ c_{7}^{*}&a_{7}&b_{7}^{*}&c_{7}&a_{7}^{*}&b_{7}\end{bmatrix} ,\]  
\[\mathbf{A}_{6}^{(7)}= \begin{bmatrix}\mathbf{A}_{3}^{(7)}&\mathbf{B}_{3}^{(7)}\\ \mathbf{B}_{3}^{(7)}&\mathbf{A}_{3}^{(7)}\end{bmatrix} ,\ \mathbf{A}_{3}^{(7)}= \begin{bmatrix}a_{7}&b_{7}&c_{7}\\ b_{7}&c_{7}^{*}&a_{7}^{*}\\ c_{7}&a_{7}^{*}&b_{7}^{*}\end{bmatrix} ,\ \mathbf{B}_{3}^{(7)}= \begin{bmatrix}a_{7}^{*}&b_{7}^{*}&c_{7}^{*}\\ b_{7}^{*}&c_{7}&a_{7}^{*}\\ c_{7}^{*}&a_{7}&b_{7}^{*}\end{bmatrix} .\]We see that matrix \(\mathbf{A}_{6}^{(7)}\) has a specific structure that allows us to factorize this matrix as follows [31]:  
\[\mathbf{A}_{6}^{(7)}=(\mathbf{H}_{2}\otimes\mathbf{I}_{3})\,\left[\frac{1}{2} \Big{(}\mathbf{A}_{3}^{(7)}+\mathbf{B}_{3}^{(7)}\Big{)}\oplus\frac{1}{2}\Big{(} \mathbf{A}_{3}^{(7)}-\mathbf{B}_{3}^{(7)}\Big{)}\right](\mathbf{H}_{2}\otimes \mathbf{I}_{3}), \tag{14}\]  
\[\frac{1}{2}\Big{(}\mathbf{A}_{3}^{(7)}+\mathbf{B}_{3}^{(7)}\Big{)}=\frac{1}{2 } \begin{bmatrix}a_{7}+a_{7}^{*}&b_{7}+b_{7}^{*}&c_{7}+c_{7}^{*}\\ b_{7}+b_{7}^{*}&c_{7}^{*}+c_{7}&a_{7}^{*}+a_{7}\\ c_{7}+c_{7}^{*}&a_{7}^{*}+a_{7}&b_{7}+b_{7}^{*}\end{bmatrix} =\mathbf{C}_{3},\]  
\[\frac{1}{2}\Big{(}\mathbf{A}_{3}^{(7)}-\mathbf{B}_{3}^{(7)}\Big{)}=\frac{1}{2 }