## 2 Mathematical Background
In matrix-vector notation the RDFT transform can be described as follows:  
\[\mathbf{y}_{N}=\mathbf{R}_{N}\mathbf{x}_{N} \tag{17}\]  
The entries \(r_{nk}\) of the matrix \(\mathbf{R}_{N}\) are obtained from (11)  
\[r_{nk}=\cos\left(\frac{2\pi nk}{N}+\theta_{n}\right) \tag{18}\]  
where the indexes \(n\) and \(k\) vary from 0 to \(N-1\) and \(\theta_{n}=\theta(n)\) is defined by (12). **3. RDFT Algorithm for \(N=3\)**  
For \(N=2\), the DFT is real-valued for real input signal and it is the same as RDFT, so we will start from \(N=3\). We introduce the denotation \(\phi_{N}=2\pi/N\). In this case the Equation (17) will take the form  
\[\mathbf{y}_{3}=\mathbf{R}_{3}\mathbf{x}_{3} \tag{19}\]  
where  
\[\mathbf{R}_{3}= \begin{bmatrix}\cos 0&\cos 0&\cos 0\\ \cos 0&\cos\phi_{3}&\cos 2\phi_{3}\\ \cos\frac{\pi}{2}&\cos(2\phi_{3}+\frac{\pi}{2})&\cos(4\phi_{3}+\frac{\pi}{2} )\end{bmatrix} = \begin{bmatrix}1&1&1\\ 1&\cos\phi_{3}&\cos 2\phi_{3}\\ 0&-\sin 2\phi_{3}&-\sin 4\phi_{3}\end{bmatrix}  \tag{20}\]  
Since \(\phi_{3}=2\pi/3\) then using the trigonometric reduction formulas we obtain \(\cos 2\phi_{3}=\cos\phi_{3}\), \(\sin 2\phi_{3}=-\sin\phi_{3}\), and \(\sin 4\phi_{3}=\sin\phi_{3}\), so the \(\mathbf{R}_{3}\) matrix will take the form  
\[\mathbf{R}_{3}= \begin{bmatrix}1&1&1\\ 1&\cos\phi_{3}&\cos\phi_{3}\\ 0&\sin\phi_{3}&-\sin\phi_{3}\end{bmatrix}  \tag{21}\]When we calculate the product of this matrix by the input vector \(\mathbf{x}_{3}\) we obtain  
\[ \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\end{bmatrix} = \begin{bmatrix}x_{0}+(x_{1}+x_{2})\\ x_{0}+\cos\phi_{3}(x_{1}+x_{2})\\ \sin\phi_{3}(x_{1}-x_{2})\end{bmatrix} = \begin{bmatrix}x_{0}+(x_{1}+x_{2})\\ (\cos\phi_{3}-1)(x_{1}+x_{2})+[x_{0}+(x1+x_{2})]\\ \sin\phi_{3}(x_{1}-x_{2})\end{bmatrix}  \tag{22}\]  
Figure 1 shows a data flow diagram corresponding to this calculation, where \(d_{1}=\cos\phi_{3}-1\) and \(d_{2}=\sin\phi_{3}\). In this paper, data flow diagrams are oriented from left to right. Straight lines in the figures denote the operations of data transfer. Points where lines converge denote summation. The dotted lines indicate a signed-changed data transfer operation. The circles in these figures show the operation of multiplication by a number inscribed inside a circle. When the vector \(\mathbf{z}_{3}=\mathbf{a}_{3}+i\mathbf{b}_{3}\) of complex coefficients of DFT for the real input vector \(\mathbf{x}_{3}\) is needed, it can be easily obtained from the output vector \(\mathbf{y}_{3}\) of RDFT, according to (16)  
\[\mathbf{a}_{3}= \begin{bmatrix}a_{0}\\ a_{1}\\ a_{2}\end{bmatrix} = \begin{bmatrix}y_{0}\\ y_{1}\\ y_{1}\end{bmatrix} \quad\mathbf{b}_{3}= \begin{bmatrix}b_{0}\\ b_{1}\\ b_{2}\end{bmatrix} = \begin{bmatrix}0\\ -y_{2}\\ y_{2}\end{bmatrix}  \tag{23}\]  
The algorithm of the RDFT for \(N=3\), presented in Figure 1, can be described by the following matrix-vector procedure, in which the matrix \(\mathbf{R}_{3}\) has been factorized:  
\[\mathbf{y}_{3}=\mathbf{C}_{3}\mathbf{D}_{3}\mathbf{\hat{A}}_{3}\mathbf{\hat{A }}_{3}\mathbf{y}_{3} \tag{24}\]  
where  
\[\mathbf{\hat{A}}_{3}= \begin{bmatrix}1&0&0\\ 0&1&1\\ 0&1&-1\end{bmatrix} \quad\mathbf{\hat{A}}_{3}= \begin{bmatrix}1&1&0\\ 0&1&0\\ 0&0&1\end{bmatrix} \quad\mathbf{D}_{3}= \begin{bmatrix}1&0&0\\ 0&d_{1}&0\\ 0&0&d_{2}\end{bmatrix} \quad\mathbf{C}_{3}= \begin{bmatrix}1&0&0\\ 1&1&0\\ 0&0&1\end{bmatrix}  \tag{25}\]  
According to this algorithm we need only 2 multiplications and 4 additions of real numbers to calculate the output vector \(\mathbf{y}_{3}\). It should be noted that only the matrix \(\mathbf{D}_{3}\) is responsible for multiplications and that matrix is diagonal  
\[\mathbf{D}_{3}=\text{diag}(1,d_{1},d_{2}) \tag{26}\]  
**4. RDFT Algorithm for \(N=4\)**  
For \(N=4\), the Equation (17) will take the form  
\[\mathbf{y}_{4}=\mathbf{R}_{4}\mathbf{x}_{4} \tag{27}\]  
where  
\[\mathbf{R}_{4}= \begin{bmatrix}1&1&1\\ 1&\cos\phi_{4}&\cos 2\phi_{4}&\cos 3\phi_{4}\\ 1&\cos 2\phi_{4}&\cos 4\phi_{4}&\cos 6\phi_{4}\\ 0&-\sin 3\phi_{4}&-\sin 6\phi_{4}&-\sin 9\phi_{4}\end{bmatrix}