## 3 Small Size 1D-QDFT Algorithms
### Algorithm 6, \(N=7\)
\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{D}_{3},\]  
It is easy to see that matrix \(\mathrm{C}_{3}\) is left-circulant. For it, there is a factorization leading to a reduction in the number of multiplications when calculating the matrix-vector product. We can write  
\[\mathrm{C}_{3}=\mathbf{\Lambda}_{3}^{(2)}\mathbf{\Lambda}_{3\times 4}\mathbf{D }_{4}^{(1)}\mathbf{\Lambda}_{4\times 3}\mathbf{\Lambda}_{3}^{(1)}, \tag{15}\]  
where  
\[\mathbf{\Lambda}_{3}^{(1)}= \begin{bmatrix}1&1&1\\ 1&0&-1\\ 0&1&-1\end{bmatrix} ,\,\mathbf{\Lambda}_{4\times 3}= \begin{bmatrix}0&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1\end{bmatrix} ,\,\mathbf{\Lambda}_{3\times 4}= \begin{bmatrix}0&1&0&0\\ -1&0&1&0\\ -1&0&0&1\end{bmatrix} ,\,\mathbf{\Lambda}_{3}^{(2)}= \begin{bmatrix}1&1&0\\ 1&0&1\\ 1&-1&-1\end{bmatrix} ,\]  
\[\mathbf{D}_{4}^{(1)}=diag\Big{(}s_{0}^{(7)},s_{1}^{(7)},s_{2}^{(7)},s_{3}^{(7 )}\Big{)},\]  
\[s_{0}^{(7)}=\frac{1}{6}[(a_{7}+a_{7}^{*})+(c_{7}+c_{7}^{*})-2(b_{7}+b_{7}^{*}) ]=0.055854,\]  
\[s_{1}^{(7)}=\frac{1}{6}[(a_{7}+a_{7}^{*})+(c_{7}+c_{7}^{*})+(b_{7}+b_{7}^{*}) ]=-0.16667,\]  
\[s_{2}^{(7)}=\frac{1}{2}[(a_{7}+a_{7}^{*})-(b_{7}+b_{7}^{*})=0.84601,\]  
\[s_{3}^{(7)}=\frac{1}{2}[(c_{7}+c_{7}^{*})-(b_{7}+b_{7}^{*})]=-0.67845.\]  
Let us now multiply by \((-1)\) the last row and last column of the matrix \(\mathbf{D}_{3}\). Then, we obtain a left-circulant matrix \(\mathbf{D}_{3}\) of the form  
\[\mathbf{\dot{D}}_{3}=\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} .\]  
This matrix can also be successfully factorized (due to the symmetry of the data-flow diagram, a slightly different factorization method was chosen in this case than for the \(\mathrm{C}_{3}\) matrix):  
\[\mathbf{\dot{D}}_{3}=\mathbf{\Lambda}_{3}^{(2)}\mathbf{V}_{3\times 4}\mathbf{D }_{4}^{(2)}\mathbf{V}_{4\times 3}\mathbf{\Lambda}_{3}^{(1)}, \tag{16}\]  
where  
\[\mathbf{V}_{4\times 3}= \begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1\\ 0&1&1\end{bmatrix} ,\,\mathbf{V}_{3\times 4}= \begin{bmatrix}1&0&0&0\\ 0&1&0&-1\\ 0&0&1&-1\end{bmatrix} ,\]  
\[\mathbf{D}_{4}^{(2)}=diag\Big{(}s_{4}^{(7)},s_{5}^{(7)},s_{6}^{(7)},s_{7}^{(7) }\Big{)},\]\[s_{4}^{(7)}=\frac{1}{6}[(a_{7}-a_{7}^{*})+(c_{7}^{*}-c_{7})+(b_{7}-b_{7}^{*})]=- \ 0.25459i-\ 0.25459j-\ 0.25459k,\]  
\[s_{5}^{(7)}=\frac{1}{2}[(a_{7}-a_{7}^{*})-(b_{7}-b_{7}^{*})]=0.11148i+0.11148j+0.1 1148k,\]  
\[s_{6}^{(7)}=\frac{1}{2}[(c_{7}^{*}-c_{7})-(b_{7}-b_{7}^{*})]=0.81338i+\ 0.81338j+0.81338k,\]  
\[s_{7}^{(7)}=\frac{1}{6}[(a_{7}-a_{7}^{*})+(c_{7}^{*}-c_{7})-2(b_{7}-b_{7}^{*})]= 0.30829i+0.30829j+0.30829k,\]  
and the remaining matrices are the same as in (15). Since  
\[\mathbf{D}_{3}=\mathbf{B}_{3}^{(1)}\mathbf{\hat{D}}_{3}\mathbf{B}_{3}^{(1)}, \tag{17}\]  
where  
\[\mathbf{B}_{3}^{(1)}= \begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&-1\end{bmatrix} ,\]  
we can write  
\[\mathbf{D}_{3}=\mathbf{V}_{3}^{(2)}\mathbf{V}_{3\times 4}\mathbf{D}_{4}^{(2)} \mathbf{V}_{4\times 3}\mathbf{V}_{3}^{(1)} \tag{18}\]  
where  
\[\mathbf{V}_{3}^{(1)}=\mathbf{\Lambda}_{3}^{(1)}\mathbf{B}_{3}^{(1)}= \begin{bmatrix} 1&1&-1\\ 1&0&1\\ 0&1&1\end{bmatrix} ,\ \mathbf{V}_{3}^{(2)}=\mathbf{B}_{3}^{(1)}\mathbf{\Lambda}_{3}^{(2)}= \begin{bmatrix}1&1&0\\ 1&0&1\\ -1&1&1\end{bmatrix} ,\]  
and the remaining matrices are the same as in (16). Taking into account expressions (15), (18) and substituting them into (14), we can write the final seven-point QDFT algorithm with reduced computational complexity:  
\[\mathbf{y}_{7}=\mathbf{P}_{7}\mathbf{A}_{7\times 8}\mathbf{W}_{8}^{(1)}\mathbf{W }_{8}^{(5)}\mathbf{W}_{8\times 10}^{(4)}\mathbf{D}_{10}\mathbf{W}_{10\times 8}^{(3)}\mathbf{W}_{8}^{(2)} \mathbf{W}_{8}^{(1)}\mathbf{A}_{8\times 7}\mathbf{P}_{7}\mathbf{\chi}_{7}, \tag{19}\]  
where  
\[\mathbf{P}_{7}=\mathbf{I}_{4}\oplus\mathbf{J}_{3}=