## 3 Small Size 1D-QDFT Algorithms
### Algorithm 5, \(N=6\)  
Let \(\mathbf{x}_{6}=\big{[}x_{0},x_{1},x_{2},x_{3},x_{4},x_{5}\big{]}^{T}\) and \(\mathbf{y}_{6}=\big{[}y_{0},y_{1},y_{2},y_{3},y_{4},y_{5}\big{]}^{T}\) be six-entry input and output vectors, and \(x_{n}\in H,y_{m}\in H,m,n=0,1,2,3,4,5\).  
The 6-point QDFT can be represented as  
\[\mathbf{y}_{6}=\mathbf{E}_{6}\mathbf{x}_{6}, \tag{10}\]  
where  
\[\mathbf{E}_{6}=\begin{bmatrix}1&1&1&1&1&1\\ 1&a_{6}&-a_{6}^{*}&-1&-a_{6}&a_{6}^{*}\\ 1&-a_{6}^{*}&-a_{6}&1&-a_{6}^{*}&-a_{6}\\ 1&-1&1&-1&1&-1\\ 1&-a_{6}&-a_{6}^{*}&1&-a_{6}&-a_{6}^{*}\\ 1&a_{6}^{*}&-a_{6}&-1&-a_{6}^{*}&a_{6}\end{bmatrix},\]  
\[a_{6}=0.5-0.5i-0.5j-0.5k,\ a_{6}^{*}=0.5+0.5i+0.5j+0.5k.\]  
Let us now reorder both rows and columns of the matrix \(\mathbf{E}_{6}\) using the following permutation:  
\[\pi_{6}=\begin{pmatrix}0&1&2&3&4&5\\ 0&4&2&3&1&5\end{pmatrix}.\]  
Then, we obtain the following matrix:  
\[\mathbf{E}_{6}=\begin{bmatrix}1&1&1&1&1&1\\ 1&-a_{6}&-a_{6}^{*}&1&-a_{6}&a_{6}^{*}\\ 1&-a_{6}^{*}&-a_{6}&1&-a_{6}^{*}&-a_{6}\\ 1&1&1&-1&-1&-1\\ 1&-a_{6}&-a_{6}^{*}&-1&a_{6}&a_{6}^{*}\\ 1&-a_{6}^{*}&-a_{6}&-1&a_{6}^{*}&a_{6}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_ {3}^{(6)}&\mathbf{A}_{3}^{(6)}\\ \mathbf{A}_{3}^{(6)}&-\mathbf{A}_{3}^{(6)}\end{bmatrix},\ \mathbf{A}_{3}^{(6)}=\begin{bmatrix}1&1&1\\ 1&-a_{6}&-a_{6}^{*}\\ 1&-a_{6}^{*}&-a_{6}\end{bmatrix}.\]  
We see that matrix \(\tilde{\mathbf{E}}_{6}\) has a specific structure that allows us to factorize this matrix as follows [31]:  
\[\tilde{\mathbf{E}}_{6}=\Big{(}\mathbf{A}_{3}^{(6)}\oplus\mathbf{A}_{3}^{(6)} \Big{)}(\mathbf{H}_{2}\otimes\mathbf{I}_{3}). \tag{11}\]  
Matrix \(\mathbf{A}_{3}^{(6)}\) has a structure similar to that which has already been analyzed above. Therefore, it can be decomposed in the same way:  
\[\mathbf{A}_{3}^{(6)}=\begin{bmatrix}1&1&1\\ 1&0&0\\ 1&0&0\end{bmatrix}+\begin{bmatrix}0&0&0\\ 0&-a_{6}&-a_{6}^{*}\\ 0&-a_{6}^{*}&-a_{6}\end{bmatrix}.\]  
By applying to matrix \(\mathbf{A}_{3}^{(6)}\) techniques similar to those we used in the case of matrix \(\mathbf{E}_{3}\) and taking into account factorization (11), we can synthesize an algorithm for calculating a six-point QDFT with reduced computational complexity:  
\[\boldsymbol{y}_{6}=\mathbf{P}_{6}^{(3)}\mathbf{A}_{6\times 8}\mathbf{W}_{8}^{(2)} \mathbf{D}_{8}\mathbf{W}_{8}^{(2)}\mathbf{A}_{8\times 6}\mathbf{P}_{6}^{(2)} \mathbf{W}_{6}^{(1)}\mathbf{P}_{6}^{(1)}\mathbf{x}_{6}, \tag{12}\]  
where  
\[\mathbf{P}_{6}^{(1)}=\begin{bmatrix}1&0&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&1\end{bmatrix},\mathbf{W}_{6}^{(1)}=\mathbf{H}_{2}\otimes\mathbf{I}_ {3}=\begin{bmatrix}1&0&0&1&0&0\\ 0&1&0&0&1&0\\ 0&0&1&0&0&1\\ 1&0&0&-1&0&0\\ 0&1&0&0&-1&0\\ 0&0&1&0&0&-1\end{bmatrix},\]\[\mathbf{P}_{6}^{(2)}=\begin{bmatrix}1&0&0&&\\ 0&1&0&&\mathbf{0}_{3}\\ 0&0&1&&\\ &\mathbf{0}&1&0&\\ &\mathbf{0}_{3}&&0&0&1\\ &&1&0&0\end{bmatrix},\mathbf{A}_{8\times 6}=\begin{bmatrix}1&0&0&&\\ 1&1&1&&\\ 0&1&0&&\mathbf{0}_{4\times 3}\\ 0&0&1&&\\ &1&0&0\\ &\mathbf{0}_{4\times 3}&&1&1&1\\ &0&0&1\end{bmatrix},\]  
\[\mathbf{W}_{8}^{(2)}=(\mathbf{I}_{2}\oplus\mathbf{H}_{2})\oplus(\mathbf{H}_{2} \oplus\mathbf{I}_{2})=\begin{bmatrix}1&0&\mathbf{0}_{2}&&\\ \mathbf{0}_{2}&1&1&&\\ &1&-1&&\\ &&1&1&\\ &\mathbf{0}_{4}&&1&-1&\mathbf{0}_{2}\\ &&\mathbf{0}_{2}&&1&0\\ &&\mathbf{0}_{2}&&0&1\end{bmatrix},\]  
\[\mathbf{D}_{8}=diag\Big{(}1,1,s_{0}^{(6)},s_{1}^{(6)},s_{2}^{(6)},s_{3}^{(6) },1,1\Big{)},\]  
\[s_{0}^{(6)}=-\frac{1}{2}(a_{6}^{*}+a_{6})=-\frac{1}{2},\,s_{1}^{(6)}=-\frac{1} {2}(a_{6}^{*}-a_{6})=\frac{1}{2}(i+j+k),\,s_{2}^{(6)}=s_{0}^{(6)},\,s_{3}^{(6) }=s_{1}^{(6)},\]  
\[\mathbf{A}_{6\times 8}=\begin{bmatrix}0&1&0&0&&\\ 1&0&1&0&&\\ 1&0&0&1&&\\ &\mathbf{0}_{3\times 4}&&1&0&0&1\\ &&\mathbf{0}&1&0&1&\\ &&\mathbf{0}&0&1&0\end{bmatrix},\,\mathbf{P}_{6}^{(3)}=\begin{bmatrix}1&0&0&0& 0&0\\ 0&0&0&1&0&0\\ 0&0&1&0&0&0\\ 0&0&0&0&0&1\\ 0&1&0&0&0&0\\ 0&0&0&0&1&0\end{bmatrix}.\]  
Figure 5 shows a data-flow diagram of the proposed algorithm for the six-point QDFT with reduced computation complexity.