The Development of Fast DST-I Algorithms for Short-Length Input Sequences

Abstract

The subject of this paper is the development of rationalized algorithms of discrete sinusoidal transform of type I for short sequences of length N = 2, 3, 4, 5, 6, 7, and 8. Here, by the word “rationalization”, we mean the reduction of the number of arithmetic operations required to implement the algorithms. The arithmetic complexity of the developed algorithms is presented in the final table. For each algorithm, we also provide data flow graphs demonstrating the space–time structure of the computational processes. The algorithms were tested to verify their validity using MATLAB software (version R2023).

1. Introduction

Discrete trigonometric (sine and cosine) transforms [1,2,3] are used today in many digital signal processing applications [4,5,6,7,8,9,10,11,12,13,14,15]. There are eight types of cosine and eight types of sine transforms. A list of all 16 types of discrete cosine and sine transforms can be found, for example, in [3,16]. Undoubtedly, the most popular are discrete cosine transforms. Discrete sine transforms are less popular. Nevertheless, many articles are devoted to the use of discrete sine transforms [2]. It is well known that any linear transform can be represented as a matrix–vector product. Computing this product directly takes a long time because the multiplicative complexity of this operation is proportional to the square of the order of the matrix. Multiplication is the most expensive of all arithmetic operations, apart from division, and therefore, developers of efficient algorithms are focused on reducing the number of multiplication operations. Traditionally, algorithms with reduced computational complexity are called fast algorithms. Over five decades, many fast algorithms for the efficient computation of one-/two-dimensional discrete trigonometric transform have been developed [17,18,19,20,21,22,23,24].

Among other things, the development of efficient algorithms for the implementation of small-sized discrete trigonometric transforms is of particular interest. Algorithms for some types of small-size discrete trigonometric transforms have already been developed [25,26,27,28]. Among other discrete trigonometric transforms, the discrete sine transform type I (DST-I) [29] is also an important tool in signal analysis and data processing, such as noise estimation and image denoising [5,6], discrete multi-tone systems [4,30,31], audio watermarking [11], EEG signal classification [12], and noisy speech enhancement [32], and others [33,34]. However, the purpose of our paper is not to justify the application of DST-I. We believe that since it has been defined, its feasibility has already been proven and is beyond doubt [2]. We focus on rationalizing the computation of this transform for the case of short input data sequence lengths. Thus, this paper is devoted to the design of DST-I algorithms with reduced multiplicative complexity for input data sequences of length N = 2, 3, 4, 5, 6, 7, 8.

2. Materials and Methods

First, we would like to present the sources we used while working on the solutions for the discrete sine transform type I (DST-I) algorithms presented here. We believe that they will help us better understand the essence of DST-I and the methodology for constructing our solutions.

DFT, DCT, MDCT, DST, and Fourier spectrum analysis of the signal were performed in [35]. An excellent description of the DCT and DST digital signal processing algorithms has been provided by Nirajan Pant [36]. An extensive description of the different types of DFT, DCT, and DST was given by Perera [37]. The paper in [38] presents a systematic methodology for deriving and classifying fast algorithms for linear transformations.

Our methodology, which we use to achieve the solutions presented in this paper, is based on specific matrix structures. These structures are included in “Table 3. The specific structures of N × N matrix patterns” in the paper [39]. Our research work is to analyze the matrix that we want to rationalize, and then set the values in that matrix so that the best possible matrix pattern can be applied to it.

Moreover, in the literature on the subject, we found many different ways of writing the expression for DST-I [3,18,40,41,42]. We found the DST-I notation method most similar to the one we use in the work of [43]. So, DST-I can be expressed as follows:

$$y_k=\sqrt{{\displaystyle \frac{2}{N+1}}}\sum _{n=0}^{N-1}{x}_{n}sin\left({\displaystyle \frac{\pi \left(k+1\right)\left(n+1\right)}{N+1}}\right)$$

(1)

where

$k=0,1,\dots ,N-1$,

${\mathit{y}}_k$—the output data after performing DST-I,

${\mathit{x}}_n$—input data, and

N—number of signal samples.

Using matrix notation, we can write DST-I as follows:

$${\mathsf{Y}}_{N\times 1}={\mathsf{C}}_N{\mathsf{X}}_{N\times 1}$$

(2)

where

$${\mathsf{Y}}_{N\times 1}={\left[y_0,y_1,\dots ,y_{N-1}\right]}^{\mathrm{T}},{\mathsf{X}}_{N\times 1}={\left[x_0,x_1,\dots ,x_{N-1}\right]}^{\mathrm{T}},$$

$${\mathsf{C}}_N=\left[\begin{array}{cccc}{c}_{0,0}& c_{0,1}& \dots & c_{0,N-1}\\ c_{1,0}& c_{1,1}& \cdots & c_{1,N-1}\\ ⋮& ⋮& \ddots & ⋮\\ c_{N-1,0}& c_{N-1,1}& \cdots & c_{N-1,N-1}\end{array}\right],$$

(3)

$$c_{k,n}=\sqrt{{\displaystyle \frac{2}{N+1}}}sin\left({\displaystyle \frac{\pi \left(k+1\right)\left(n+1\right)}{N+1}}\right),\mathrm{for}k,n=0,1,\dots ,N-1.$$

(4)

DST-I in matrix notation is as takes after

$$\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_{N-1}\end{array}\right]=\sqrt{{\displaystyle \frac{2}{N+1}}}\left[\begin{array}{cccc}sin\left({\displaystyle \frac{\pi }{N+1}}\right)& sin\left({\displaystyle \frac{2\pi }{N+1}}\right)& \cdots & sin\left({\displaystyle \frac{N\pi }{N+1}}\right)\\ sin\left({\displaystyle \frac{2\pi }{N+1}}\right)& sin\left({\displaystyle \frac{4\pi }{N+1}}\right)& \cdots & sin\left({\displaystyle \frac{2N\pi }{N+1}}\right)\\ ⋮& ⋮& \ddots & ⋮\\ sin\left({\displaystyle \frac{N\pi }{N+1}}\right)& sin\left({\displaystyle \frac{2N\pi }{N+1}}\right)& \cdots & sin\left({\displaystyle \frac{N^2\pi }{N+1}}\right)\end{array}\right]\left[\begin{array}{c}{x}_0\\ x_1\\ ⋮\\ x_{N-1}\end{array}\right].$$

(5)

We use the following notation in our work: [39,44]:

• ${\mathbf{I}}_N$—is an order N identity matrix;
• ${\mathbf{H}}_2$—a 2 × 2 Hadamard matrix;
• ⊗—the Kronecker product of two matrices; and
• ⊕—direct sum of two matrices.

An empty cell in matrix means that there is a zero there. Multipliers are denoted as $s_m^{\left(N\right)}$. In the graphs, we do not enter a superscript in order to maintain their clarity and elegance.

3. Two-Point DST-I Solution

The following is the matrix form expression for two-point DST-I:

$${\mathsf{Y}}_{2\times 1}={\mathsf{C}}_2{\mathsf{X}}_{2\times 1}$$

(6)

where

$${\mathsf{Y}}_{2\times 1}={\left[y_0,y_1\right]}^{\mathrm{T}},{\mathsf{X}}_{2\times 1}={\left[x_0,x_1\right]}^{\mathrm{T}},$$

$${\mathsf{C}}_2=\left[\begin{array}{cc}{a}_2& a_2\\ a_2& -a_2\end{array}\right],a_2=0.7071.$$

Presently, we are able determine the final expression for DST-I for N = 2:

$${\mathsf{Y}}_{2\times 1}={\mathsf{H}}_2{\mathsf{D}}_2^{\left(0\right)}{\mathsf{X}}_{2\times 1}$$

(7)

where

$${\mathsf{H}}_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right],{\mathsf{D}}_2^{\left(0\right)}=\mathrm{diag}\left(s_0^{\left(2\right)},s_1^{\left(2\right)}\right),s_0^{\left(2\right)}=s_1^{\left(2\right)}=a_2.$$

The data flow graph for our solution for two-point DST-I is shown in Figure 1. The naive, direct computation requires 2 additions and 4 multiplications. As can be observed, our solution uses 2 additions and 2 multiplications, reducing the number of multiplications from 4 to 2.

4. Three-Point DST-I Solution

The following is the matrix form expression for three-point DST-I:

$${\mathsf{Y}}_{3\times 1}={\mathsf{C}}_3{\mathsf{X}}_{3\times 1}$$

(8)

where

$${\mathsf{Y}}_{3\times 1}={\left[y_0,y_1,y_2\right]}^{\mathrm{T}},{\mathsf{X}}_{3\times 1}={\left[x_0,x_1,x_2\right]}^{\mathrm{T}},$$

$${\mathsf{C}}_3=\left[\begin{array}{ccc}{a}_3& b_3& a_3\\ b_3& 0& -b_3\\ a_3& -b_3& a_3\end{array}\right],a_3=0.5,b_3=0.7071.$$

Now, we will divide the matrix ${\mathsf{C}}_3$ into two parts:

$${\mathsf{C}}_3={\mathsf{C}}_3^{\left(\mathrm{a}\right)}+{\mathsf{C}}_3^{\left(\mathrm{b}\right)}$$

(9)

where

$${\mathsf{C}}_3^{\left(\mathrm{a}\right)}=\left[\begin{array}{ccc}{a}_3& & a_3\\ & & \\ a_3& & a_3\end{array}\right],{\mathsf{C}}_3^{\left(\mathrm{b}\right)}=\left[\begin{array}{ccc}& b_3& \\ b_3& & -b_3\\ & -b_3& \end{array}\right].$$

Matrix ${\mathsf{C}}_3^{\left(\mathrm{a}\right)}$ after omitting terms equal to zero is as takes after

$${\mathsf{C}}_2^{\prime }=\left[\begin{array}{cc}{a}_3& a_3\\ a_3& a_3\end{array}\right].$$

(10)

Presently, we are able determine the final expression for DST-I for N = 3:

$${\mathsf{Y}}_{3\times 1}={\mathsf{W}}_3^{\left(1\right)}{\mathsf{D}}_3{\mathsf{W}}_3^{\left(0\right)}{\mathsf{X}}_{3\times 1}$$

(11)

where

$${\mathsf{W}}_3^{\left(0\right)}=\left[\begin{array}{ccc}1& & 1\\ & 1& \\ 1& & -1\end{array}\right],{\mathsf{D}}_3=\mathrm{diag}\left(s_0^{\left(3\right)},s_1^{\left(3\right)},s_2^{\left(3\right)}\right),$$

$$s_0^{\left(3\right)}=a_3,s_1^{\left(3\right)}=s_2^{\left(3\right)}=b_3,{\mathsf{W}}_3^{\left(1\right)}=\left[\begin{array}{ccc}1& 1& \\ & & 1\\ 1& -1& \end{array}\right].$$

The data flow graph for our solution for three-point DST-I is shown in Figure 2. The naive, direct computation requires 5 additions and 4 multiplications. As can be observed, our solution uses 4 additions and 2 multiplications, reducing the number of additions from 5 to 4 and the number of multiplications from 4 to 2.

5. Four-Point DST-I Solution

The following is the matrix form expression for four-point DST-I:

$${\mathsf{Y}}_{4\times 1}={\mathsf{C}}_4{\mathsf{X}}_{4\times 1}$$

(12)

where

$$\begin{array}{ccc}\hfill \begin{array}{c}{\mathsf{Y}}_{4\times 1}={\left[y_0,y_1,y_2,y_3\right]}^{\mathrm{T}},\hfill \\ \\ {\mathsf{X}}_{4\times 1}={\left[x_0,x_1,x_2,x_3\right]}^{\mathrm{T}},\hfill \end{array}& {\mathsf{C}}_4=\left[\begin{array}{cccc}{a}_4& b_4& b_4& a_4\\ b_4& a_4& -a_4& -b_4\\ b_4& -a_4& -a_4& b_4\\ a_4& -b_4& b_4& -a_4\end{array}\right],\hfill & \hfill \begin{array}{c}{a}_4=0.3717,\hfill \\ \\ b_4=0.6015.\hfill \end{array}\end{array}$$

Now, we swap the columns and rows in matrix ${\mathsf{C}}_4$ to group the $a_4$ and $b_4$ terms so that the obtained matrix is consistent with the matrix pattern [39]:

$$\left[\begin{array}{cc}{\mathsf{A}}_2& {\mathsf{B}}_2\\ {\mathsf{B}}_2& -{\mathsf{A}}_2\end{array}\right]\mathrm{where}{\mathsf{A}}_2=\left[\begin{array}{cc}{a}_4& a_4\\ a_4& -a_4\end{array}\right],{\mathsf{B}}_2=\left[\begin{array}{cc}{b}_4& b_4\\ b_4& -b_4\end{array}\right].$$

This is accomplished by the permutation ${\pi }_4^{\left(0\right)}$:

$${\pi }_4^{\left(0\right)}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 4& 3& 2\end{array}\right).$$

(13)

Considering this, we may obtain the following expression for the first stage of decomposition:

$${\mathsf{Y}}_{4\times 1}={\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}{\mathsf{W}}_{4\times 6}{\mathsf{D}}_6^{\left(0\right)}{\mathsf{W}}_{6\times 4}{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}{\mathsf{X}}_{4\times 1}$$

(14)

where

$${\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}=\left[\begin{array}{cccc}1& & & \\ & & & 1\\ & & 1& \\ & 1& & \end{array}\right],{\mathsf{W}}_{6\times 4}=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & 1& \\ & & & 1\\ 1& & 1& \\ & 1& & 1\end{array}\right],$$

$${\mathsf{D}}_6^{\left(0\right)}=\left[\begin{array}{ccc}{\mathsf{F}}_2& & \\ & {\mathsf{G}}_2& \\ & & {\mathsf{B}}_2\end{array}\right],{\mathsf{F}}_2={\mathsf{A}}_2-{\mathsf{B}}_2,{\mathsf{G}}_2=-{\mathsf{A}}_2-{\mathsf{B}}_2,$$

$${\mathsf{W}}_{4\times 6}=\left[\begin{array}{cccccc}1& & & & 1& \\ & 1& & & & 1\\ & & 1& & 1& \\ & & & 1& & 1\end{array}\right].$$

The matrices ${\mathsf{F}}_2$ and ${\mathsf{G}}_2$ take after

$${\mathsf{F}}_2=\left[\begin{array}{cc}{a}_4-b_4& a_4-b_4\\ a_4-b_4& -a_4+b_4\end{array}\right],{\mathsf{G}}_2=\left[\begin{array}{cc}-a_4-b_4& -a_4-b_4\\ -a_4-b_4& a_4+b_4\end{array}\right].$$

As we can see above, these matrices do not require any operations to reduce complexity, because they both follow this pattern:

$$\left[\begin{array}{cc}a& a\\ a& -a\end{array}\right].$$

Presently, we are able determine the final expression for DST-I for N = 4:

$${\mathsf{Y}}_{4\times 1}={\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}{\mathsf{W}}_{4\times 6}{\mathsf{D}}_6^{\left(1\right)}{\mathsf{W}}_6^{\left(0\right)}{\mathsf{W}}_{6\times 4}{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}{\mathsf{X}}_{4\times 1}$$

(15)

where

$${\mathsf{W}}_6^{\left(0\right)}={\mathsf{H}}_2\oplus {\mathsf{H}}_2\oplus {\mathsf{H}}_2=\left[\begin{array}{ccc}{\mathsf{H}}_2& & \\ & {\mathsf{H}}_2& \\ & & {\mathsf{H}}_2\end{array}\right],{\mathsf{D}}_6^{\left(1\right)}=\mathrm{diag}\left(s_0^{\left(4\right)},s_1^{\left(4\right)},\dots ,s_5^{\left(4\right)}\right),$$

$$s_0^{\left(4\right)}=s_1^{\left(4\right)}=a_4-b_4,s_2^{\left(4\right)}=s_3^{\left(4\right)}=-a_4-b_4,s_4^{\left(4\right)}=s_5^{\left(4\right)}=b_4.$$

The data flow graph for our solution for four-point DST-I is shown in Figure 3. The naive, direct computation requires 12 additions and 16 multiplications. As can be observed, our solution uses 12 additions and 6 multiplications, reducing the number of multiplications from 16 to 6.

6. Five-Point DST-I Solution

The following is the matrix form expression for five-point DST-I:

$${\mathsf{Y}}_{5\times 1}={\mathsf{C}}_5{\mathsf{X}}_{5\times 1}$$

(16)

where

$${\mathsf{Y}}_{5\times 1}={\left[y_0,y_1,y_2,y_3,y_4\right]}^{\mathrm{T}},{\mathsf{X}}_{5\times 1}={\left[x_0,x_1,x_2,x_3,x_4\right]}^{\mathrm{T}},$$

$$\begin{array}{cc}\hfill {\mathsf{C}}_5=\left[\begin{array}{ccccc}{a}_5& b_5& c_5& b_5& a_5\\ b_5& b_5& 0& -b_5& -b_5\\ c_5& 0& -c_5& 0& c_5\\ b_5& -b_5& 0& b_5& -b_5\\ a_5& -b_5& c_5& -b_5& a_5\end{array}\right],& \begin{array}{c}{a}_5=0.2887,\hfill \\ \\ b_5=0.5,\hfill \\ \\ c_5=0.5774.\hfill \end{array}\hfill \end{array}$$

Now, we swap the columns and rows in matrix ${\mathsf{C}}_5$ to be able to perform operations that are beneficial to us. This is accomplished by the permutation ${\pi }_5^{\left(0\right)}$ for the columns and permutation ${\pi }_5^{\left(1\right)}$ for the rows:

$${\pi }_5^{\left(0\right)}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 5& 3& 4& 2\end{array}\right),{\pi }_5^{\left(1\right)}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 4& 3& 5& 2\end{array}\right).$$

(17)

After permutations, we divide the matrix ${\mathsf{C}}_5$ into two parts:

$${\mathsf{C}}_5={\mathsf{C}}_5^{\left(\mathrm{a}\right)}+{\mathsf{C}}_5^{\left(\mathrm{b}\right)}$$

(18)

where

$${\mathsf{C}}_5^{\left(\mathrm{a}\right)}=\left[\begin{array}{ccccc}{a}_5& a_5& & b_5& b_5\\ b_5& -b_5& & b_5& -b_5\\ & & & & \\ a_5& a_5& & -b_5& -b_5\\ b_5& -b_5& & -b_5& b_5\end{array}\right],{\mathsf{C}}_5^{\left(\mathrm{b}\right)}=\left[\begin{array}{ccccc}& & c_5& & \\ & & & & \\ c_5& c_5& -c_5& & \\ & & c_5& & \\ & & & & \end{array}\right].$$

The matrix ${\mathsf{C}}_5^{\left(\mathrm{a}\right)}$ after omitting terms equal to zero is as follows:

$${\mathsf{C}}_4=\left[\begin{array}{cccc}{a}_5& a_5& b_5& b_5\\ b_5& -b_5& b_5& -b_5\\ a_5& a_5& -b_5& -b_5\\ b_5& -b_5& -b_5& b_5\end{array}\right].$$

The matrix ${\mathsf{C}}_4$ matches the matrix pattern:

$$\left[\begin{array}{cc}{\mathsf{A}}_2& {\mathsf{B}}_2\\ {\mathsf{A}}_2& -{\mathsf{B}}_2\end{array}\right]\mathrm{where}{\mathsf{A}}_2=\left[\begin{array}{cc}{a}_5& a_5\\ b_5& -b_5\end{array}\right],{\mathsf{B}}_2=\left[\begin{array}{cc}{b}_5& b_5\\ b_5& -b_5\end{array}\right].$$

Having stated this, we can write down the following expression for the first stage of rationalization:

$${\mathsf{Y}}_{5\times 1}={\mathsf{P}}_5^{\left({\pi }_5^{\left(1\right)}\right)}{\mathsf{W}}_{5\times 7}{\mathsf{W}}_{7\times 6}{\mathsf{D}}_6^{\left(2\right)}{\mathsf{W}}_{6\times 7}{\mathsf{W}}_{7\times 5}^{\left(0\right)}{\mathsf{P}}_5^{\left({\pi }_5^{\left(0\right)}\right)}{\mathsf{X}}_{5\times 1}$$

(19)

where

$${\mathsf{P}}_5^{\left({\pi }_5^{\left(0\right)}\right)}=\left[\begin{array}{ccccc}1& & & & \\ & & & & 1\\ & & 1& & \\ & & & 1& \\ & 1& & & \end{array}\right],{\mathsf{W}}_{7\times 5}^{\left(0\right)}=\left[\begin{array}{ccccc}1& & & & \\ & 1& & & \\ & & & 1& \\ & & & & 1\\ 1& & & & \\ & 1& & & \\ & & 1& & \end{array}\right],$$

$${\mathsf{W}}_{6\times 7}=\left[\begin{array}{cccc}{\mathsf{I}}_4& & & \\ & & & 1\\ & 1& 1& -1\end{array}\right],{\mathsf{D}}_6^{\left(2\right)}=\left[\begin{array}{cccc}{\mathsf{A}}_2& & & \\ & {\mathsf{B}}_2& & \\ & & c_5& \\ & & & c_5\end{array}\right],{\mathsf{W}}_{7\times 6}=\left[\begin{array}{ccc}{\mathsf{W}}_4& & \\ & 1& \\ & & 1\\ & 1& \end{array}\right],$$

$${\mathsf{W}}_4={\mathsf{H}}_2\otimes {\mathsf{I}}_2,{\mathsf{W}}_{5\times 7}=\left[\begin{array}{ccccccc}1& & & & 1& & \\ & 1& & & & & \\ & & & & & 1& \\ & & 1& & & & 1\\ & & & 1& & & \end{array}\right],{\mathsf{P}}_5^{\left({\pi }_5^{\left(1\right)}\right)}=\left[\begin{array}{ccccc}1& & & & \\ & & & & 1\\ & & 1& & \\ & 1& & & \\ & & & 1& \end{array}\right].$$

Next, matrices ${\mathsf{A}}_2$ and ${\mathsf{B}}_2$ have structures that correspond to matrix patterns that are beneficial to us. We will immediately derive the final expression for DST-I for N = 5:

$${\mathsf{Y}}_{5\times 1}={\mathsf{P}}_5^{\left({\pi }_5^{\left(1\right)}\right)}{\mathsf{W}}_{5\times 7}{\mathsf{W}}_{7\times 6}{\mathsf{D}}_6^{\left(3\right)}{\mathsf{W}}_6^{\left(1\right)}{\mathsf{W}}_{6\times 7}{\mathsf{W}}_{7\times 5}^{\left(0\right)}{\mathsf{P}}_5^{\left({\pi }_5^{\left(0\right)}\right)}{\mathsf{X}}_{5\times 1}$$

(20)

where

$${\mathsf{W}}_6^{\left(1\right)}=\left[\begin{array}{ccc}{\mathsf{H}}_2& & \\ & {\mathsf{H}}_2& \\ & & {\mathsf{I}}_2\end{array}\right],{\mathsf{D}}_6^{\left(3\right)}=\mathrm{diag}\left(s_0^{\left(5\right)},s_1^{\left(5\right)},\dots ,s_5^{\left(5\right)}\right),$$

$$s_0^{\left(5\right)}=a_5,s_1^{\left(5\right)}=s_2^{\left(5\right)}=s_3^{\left(5\right)}=b_5,s_4^{\left(5\right)}=s_5^{\left(5\right)}=c_5.$$

The data flow graph for our solution for five-point DST-I is shown in Figure 4. The naive, direct computation requires 16 additions and 9 multiplications. As can be observed, our solution uses 12 additions and 3 multiplications, reducing the number of additions from 16 to 12 and the number of multiplications from 9 to 3.

7. Six-Point DST-I Solution

The following is the matrix form expression for six-point DST-I:

$${\mathsf{Y}}_{6\times 1}={\mathsf{C}}_6{\mathsf{X}}_{6\times 1}$$

(21)

where

$${\mathsf{Y}}_{6\times 1}={\left[y_0,y_1,y_2,y_3,y_4,y_5\right]}^{\mathrm{T}},{\mathsf{X}}_{6\times 1}={\left[x_0,x_1,x_2,x_3,x_4,x_5\right]}^{\mathrm{T}},$$

$$\begin{array}{cc}\hfill {\mathsf{C}}_6=\left[\begin{array}{cccccc}{a}_6& b_6& c_6& c_6& b_6& a_6\\ b_6& c_6& a_6& -a_6& -c_6& -b_6\\ c_6& a_6& -b_6& -b_6& a_6& c_6\\ c_6& -a_6& -b_6& b_6& a_6& -c_6\\ b_6& -c_6& a_6& a_6& -c_6& b_6\\ a_6& -b_6& c_6& -c_6& b_6& -a_6\end{array}\right],& \begin{array}{c}{a}_6=0.2319,\hfill \\ \\ b_6=0.4179,\hfill \\ \\ c_6=0.5211.\hfill \end{array}\hfill \end{array}$$

Now, we swap the columns and rows in matrix ${\mathsf{C}}_6$ to match the matrix pattern:

$$\left[\begin{array}{cc}{\mathsf{A}}_3& {\mathsf{A}}_3\\ {\mathsf{B}}_3& -{\mathsf{B}}_3\end{array}\right]\mathrm{where}{\mathsf{A}}_3=\left[\begin{array}{ccc}{a}_6& b_6& c_6\\ b_6& -c_6& a_6\\ c_6& a_6& -b_6\end{array}\right],{\mathsf{B}}_3=\left[\begin{array}{ccc}{c}_6& -a_6& -b_6\\ b_6& c_6& a_6\\ a_6& -b_6& c_6\end{array}\right].$$

This is accomplished by the permutation ${\pi }_6^{\left(0\right)}$ for the columns and permutation ${\pi }_6^{\left(1\right)}$ for the rows:

$${\pi }_6^{\left(0\right)}=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 1& 2& 3& 6& 5& 4\end{array}\right),{\pi }_6^{\left(1\right)}=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 1& 5& 3& 4& 2& 6\end{array}\right).$$

(22)

Considering this, we may obtain the following expression for the first stage of decomposition:

$${\mathsf{Y}}_{6\times 1}={\mathsf{P}}_6^{\left({\pi }_6^{\left(1\right)}\right)}{\mathsf{D}}_6^{\left(4\right)}{\mathsf{W}}_6^{\left(2\right)}{\mathsf{P}}_6^{\left({\pi }_6^{\left(0\right)}\right)}{\mathsf{X}}_{6\times 1}$$

(23)

where

$$\begin{array}{c}\hfill {\mathsf{P}}_6^{\left({\pi }_6^{\left(0\right)}\right)}=\left[\begin{array}{cccc}{\mathsf{I}}_3& & & \\ & & & 1\\ & & 1& \\ & 1& & \end{array}\right],\begin{array}{c}{\mathsf{W}}_6^{\left(2\right)}={\mathsf{H}}_2\otimes {\mathsf{I}}_3,\hfill \\ \\ \\ {\mathsf{D}}_6^{\left(4\right)}={\mathsf{A}}_3\oplus {\mathsf{B}}_3,\hfill \end{array}{\mathsf{P}}_6^{\left({\pi }_6^{\left(1\right)}\right)}=\left[\begin{array}{cccccc}1& & & & & \\ & & & & 1& \\ & & 1& & & \\ & & & 1& & \\ & 1& & & & \\ & & & & & 1\end{array}\right].\end{array}$$

Now, we focus on the matrices ${\mathsf{A}}_3$ and ${\mathsf{B}}_3$. We define the permutation ${\pi }_3^{\left(0\right)}$ as follows:

$${\pi }_3^{\left(0\right)}=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right).$$

(24)

Now, we swap the rows in matrix ${\mathsf{A}}_3$ using the ${\pi }_3^{\left(0\right)}$ permutation. Furthermore, we will change the signs in the first column and first row of this matrix. After these operations, the matrix has the following form:

$${\mathsf{A}}_3^{\prime }=\left[\begin{array}{ccc}{a}_6& -c_6& -b_6\\ -b_6& a_6& -c_6\\ -c_6& -b_6& a_6\end{array}\right].$$

Next, we apply a circular convolution [44] to the ${\mathsf{A}}_3^{\prime }$ matrix. Below are the expressions to calculate the circular convolution values for a matrix of size 3.

$$\begin{array}{cc}\hfill \left[\begin{array}{ccc}{h}_0& h_2& h_1\\ h_1& h_0& h_2\\ h_2& h_1& h_0\end{array}\right],& \begin{array}{cc}{s}_0={\displaystyle \frac{1}{3}}\left(h_0+h_1+h_2\right),\hfill & s_2=h_1-h_2,\hfill \\ \\ s_1=h_0-h_2,\hfill & s_3={\displaystyle \frac{1}{3}}\left(h_0+h_1-2h_2\right).\hfill \end{array}\hfill \end{array}$$

So, for ${\mathsf{A}}_3^{\prime }$, we have

$$s_0^{\left(6\right)}={\displaystyle \frac{a_6-c_6-b_6}{3}},s_1^{\left(6\right)}=a_6+c_6,s_2^{\left(6\right)}=-b_6+c_6,s_3^{\left(6\right)}={\displaystyle \frac{a_6-b_6+2c_6}{3}}.$$

(25)

The calculation procedure for matrix ${\mathsf{A}}_3$ is as follows:

$${\mathsf{A}}_3={\mathsf{P}}_3^{\left(1\right)}{\mathsf{T}}_3^{\left(1\right)}{\mathsf{A}}_{3\times 4}{\mathsf{D}}_4^{\left(0\right)}{\mathsf{A}}_{4\times 3}{\mathsf{T}}_3^{\left(0\right)}{\mathsf{P}}_3^{\left(0\right)}$$

(26)

where

$${\mathsf{P}}_3^{\left(0\right)}=\left[\begin{array}{ccc}-1& & \\ & & 1\\ & 1& \end{array}\right],{\mathsf{T}}_3^{\left(0\right)}=\left[\begin{array}{ccc}1& 1& 1\\ 1& & -1\\ & 1& -1\end{array}\right],{\mathsf{A}}_{4\times 3}=\left[\begin{array}{ccc}1& & \\ & 1& \\ & & 1\\ & 1& 1\end{array}\right],$$

$${\mathsf{D}}_4^{\left(0\right)}=\mathrm{diag}\left(s_0^{\left(6\right)},s_1^{\left(6\right)},s_2^{\left(6\right)},s_3^{\left(6\right)}\right),{\mathsf{A}}_{3\times 4}=\left[\begin{array}{cccc}1& & & \\ & 1& & -1\\ & & 1& -1\end{array}\right],$$

$${\mathsf{T}}_3^{\left(1\right)}=\left[\begin{array}{ccc}1& 1& \\ 1& -1& -1\\ 1& & 1\end{array}\right],{\mathsf{P}}_3^{\left(1\right)}=\left[\begin{array}{ccc}-1& & \\ & 1& \\ & & 1\end{array}\right].$$

In the matrix ${\mathsf{B}}_3$, we will change the signs in the third column and third row. After these operations, the matrix has the following form:

$${\mathsf{B}}_3^{\prime }=\left[\begin{array}{ccc}{c}_6& -a_6& b_6\\ b_6& c_6& -a_6\\ -a_6& b_6& c_6\end{array}\right].$$

And again, a circular convolution matrix will be used:

$$s_4^{\left(6\right)}={\displaystyle \frac{c_6+b_6-a_6}{3}},s_5^{\left(6\right)}=c_6+a_6,s_6^{\left(6\right)}=b_6+a_6,s_7^{\left(6\right)}={\displaystyle \frac{c_6+b_6+2a_6}{3}}.$$

(27)

The calculation procedure for matrix ${\mathsf{B}}_3$ is as follows:

$${\mathsf{B}}_3={\mathsf{P}}_3^{\left(2\right)}{\mathsf{T}}_3^{\left(1\right)}{\mathsf{A}}_{3\times 4}{\mathsf{D}}_4^{\left(1\right)}{\mathsf{A}}_{4\times 3}{\mathsf{T}}_3^{\left(0\right)}{\mathsf{P}}_3^{\left(2\right)}$$

(28)

where

$${\mathsf{P}}_3^{\left(2\right)}=\left[\begin{array}{ccc}1& & \\ & 1& \\ & & -1\end{array}\right],{\mathsf{D}}_4^{\left(1\right)}=\mathrm{diag}\left(s_4^{\left(6\right)},s_5^{\left(6\right)},s_6^{\left(6\right)},s_7^{\left(6\right)}\right).$$

In regard to this, we can determine the final expression for DST-I for N = 6:

$${\mathsf{Y}}_{6\times 1}={\mathsf{P}}_6^{\left({\pi }_6^{\left(1\right)}\right)}{\mathsf{P}}_6^{\left(2\right)}{\mathsf{A}}_6^{\left(2\right)}{\mathsf{A}}_{6\times 8}{\mathsf{D}}_8^{\left(0\right)}{\mathsf{A}}_{8\times 6}{\mathsf{A}}_6^{\left(1\right)}{\mathsf{P}}_6^{\left(1\right)}{\mathsf{W}}_6^{\left(2\right)}{\mathsf{P}}_6^{\left({\pi }_6^{\left(0\right)}\right)}{\mathsf{X}}_{6\times 1}$$

(29)

where

$${\mathsf{P}}_6^{\left(1\right)}=\left[\begin{array}{cc}{\mathsf{P}}_3^{\left(0\right)}& \\ & {\mathsf{P}}_3^{\left(2\right)}\end{array}\right],{\mathsf{A}}_6^{\left(1\right)}=\left[\begin{array}{cc}{\mathsf{T}}_3^{\left(0\right)}& \\ & {\mathsf{T}}_3^{\left(0\right)}\end{array}\right],{\mathsf{A}}_{8\times 6}=\left[\begin{array}{cc}{\mathsf{A}}_{4\times 3}& \\ & {\mathsf{A}}_{4\times 3}\end{array}\right],$$

$${\mathsf{D}}_8^{\left(0\right)}=\left[\begin{array}{cc}{\mathsf{D}}_4^{\left(0\right)}& \\ & {\mathsf{D}}_4^{\left(1\right)}\end{array}\right],{\mathsf{A}}_{6\times 8}=\left[\begin{array}{cc}{\mathsf{A}}_{3\times 4}& \\ & {\mathsf{A}}_{3\times 4}\end{array}\right],{\mathsf{A}}_6^{\left(2\right)}=\left[\begin{array}{cc}{\mathsf{T}}_3^{\left(1\right)}& \\ & {\mathsf{T}}_3^{\left(1\right)}\end{array}\right],$$

$${\mathsf{P}}_6^{\left(2\right)}=\left[\begin{array}{cc}{\mathsf{P}}_3^{\left(1\right)}& \\ & {\mathsf{P}}_3^{\left(2\right)}\end{array}\right].$$

The data flow graph for our solution for six-point DST-I is shown in Figure 5. The naive, direct computation requires 30 additions and 36 multiplications. As can be observed, our solution uses 28 additions and 8 multiplications, reducing the number of additions from 30 to 28 and the number of multiplications from 36 to 8.

8. Seven-Point DST-I Solution

The following is the matrix form expression for seven-point DST-I:

$${\mathsf{Y}}_{7\times 1}={\mathsf{C}}_7{\mathsf{X}}_{7\times 1}$$

(30)

where

$${\mathsf{Y}}_{7\times 1}={\left[y_0,y_1,y_2,y_3,y_4,y_5,y_6\right]}^{\mathrm{T}},{\mathsf{X}}_{7\times 1}={\left[x_0,x_1,x_2,x_3,x_4,x_5,x_6\right]}^{\mathrm{T}},$$

$$\begin{array}{cc}\hfill {\mathsf{C}}_7=\left[\begin{array}{ccccccc}{a}_7& b_7& c_7& d_7& c_7& b_7& a_7\\ b_7& d_7& b_7& 0& -b_7& -d_7& -b_7\\ c_7& b_7& -a_7& -d_7& -a_7& b_7& c_7\\ d_7& 0& -d_7& 0& d_7& 0& -d_7\\ c_7& -b_7& -a_7& d_7& -a_7& -b_7& c_7\\ b_7& -d_7& b_7& 0& -b_7& d_7& -b_7\\ a_7& -b_7& c_7& -d_7& c_7& -b_7& a_7\end{array}\right],& \begin{array}{c}{a}_7=0.1913,\hfill \\ \\ b_7=0.3536,\hfill \\ \\ c_7=0.4619,\hfill \\ \\ d_7=0.5.\hfill \end{array}\hfill \end{array}$$

Now, we swap the columns and rows in matrix ${\mathsf{C}}_7$. For this purpose, we define the permutation ${\pi }_7^{\left(0\right)}$ and ${\pi }_7^{\left(1\right)}$ as follows:

$${\pi }_7^{\left(0\right)}=\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 1& 6& 3& 4& 7& 2& 5\end{array}\right),{\pi }_7^{\left(1\right)}=\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 1& 2& 3& 4& 7& 6& 5\end{array}\right).$$

(31)

Permute columns of matrix ${\mathsf{C}}_7$ according to ${\pi }_7^{\left(0\right)}$ and rows according to ${\pi }_7^{\left(1\right)}$. Moreover, we need to change the sign in row 6 and sign in column 2. These operations are described as follows:

$${\mathsf{C}}_7^{\prime }={\mathsf{P}}_7^{\left({\pi }_7^{\left(1\right)}\right)}{\mathsf{P}}_7^{\left(1\right)}{\mathsf{C}}_7{\left({\mathsf{P}}_7^{\left({\pi }_7^{\left(0\right)}\right)}{\mathsf{P}}_7^{\left(0\right)}\right)}^{\mathrm{T}}$$

(32)

where

$${\mathsf{P}}_7^{\left(0\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & -1& & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & 1& \\ & & & & & & 1\end{array}\right],{\mathsf{P}}_7^{\left({\pi }_7^{\left(0\right)}\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & & & & & 1& \\ & & 1& & & & \\ & & & 1& & & \\ & & & & & & 1\\ & 1& & & & & \\ & & & & 1& & \end{array}\right],$$

$${\mathsf{P}}_7^{\left(1\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & -1& \\ & & & & & & 1\end{array}\right],{\mathsf{P}}_7^{\left({\pi }_7^{\left(1\right)}\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & & & 1\\ & & & & & 1& \\ & & & & 1& & \end{array}\right],$$

The matrix ${\mathsf{C}}_7^{\prime }$ is as takes after:

$${\mathsf{C}}_7^{\prime }=\left[\begin{array}{ccccccc}{a}_7& b_7& c_7& d_7& a_7& -b_7& c_7\\ b_7& -d_7& b_7& & -b_7& -d_7& -b_7\\ c_7& b_7& -a_7& -d_7& c_7& -b_7& -a_7\\ d_7& & -d_7& & -d_7& & d_7\\ a_7& -b_7& c_7& -d_7& a_7& b_7& c_7\\ -b_7& -d_7& -b_7& & b_7& -d_7& b_7\\ c_7& -b_7& -a_7& d_7& c_7& b_7& -a_7\end{array}\right].$$

Now we will divide the matrix ${\mathsf{C}}_7^{\prime }$ into two parts:

$${\mathsf{C}}_7^{\prime }={\mathsf{C}}_7^{\left(\mathrm{a}\right)}+{\mathsf{C}}_7^{\left(\mathrm{b}\right)}$$

(33)

where

$${\mathsf{C}}_7^{\left(\mathrm{a}\right)}=\left[\begin{array}{ccccccc}{a}_7& b_7& c_7& & a_7& -b_7& c_7\\ b_7& -d_7& b_7& & -b_7& -d_7& -b_7\\ c_7& b_7& -a_7& & c_7& -b_7& -a_7\\ & & & & & & \\ a_7& -b_7& c_7& & a_7& b_7& c_7\\ -b_7& -d_7& -b_7& & b_7& -d_7& b_7\\ c_7& -b_7& -a_7& & c_7& b_7& -a_7\end{array}\right],$$

$${\mathsf{C}}_7^{\left(\mathrm{b}\right)}=\left[\begin{array}{ccccccc}& & & d_7& & & \\ & & & & & & \\ & & & -d_7& & & \\ d_7& & -d_7& & -d_7& & d_7\\ & & & -d_7& & & \\ & & & & & & \\ & & & d_7& & & \end{array}\right].$$

The matrix ${\mathsf{C}}_7^{\left(\mathrm{b}\right)}$ has one element in the first, third, fifth, and seventh rows and four elements with the same value in the fourth row, which allows us to reduce the number of operations without the need for further transformations. The matrix ${\mathsf{C}}_7^{\left(\mathrm{a}\right)}$ after removing terms equal to zero is as follows:

$${\mathsf{C}}_6=\left[\begin{array}{cccccc}{a}_7& b_7& c_7& a_7& -b_7& c_7\\ b_7& -d_7& b_7& -b_7& -d_7& -b_7\\ c_7& b_7& -a_7& c_7& -b_7& -a_7\\ a_7& -b_7& c_7& a_7& b_7& c_7\\ -b_7& -d_7& -b_7& b_7& -d_7& b_7\\ c_7& -b_7& -a_7& c_7& b_7& -a_7\end{array}\right].$$

Now, we can see that the matrix ${\mathsf{C}}_6$ matches the following matrix pattern:

$$\left[\begin{array}{cc}{\mathsf{A}}_3& {\mathsf{B}}_3\\ {\mathsf{B}}_3& {\mathsf{A}}_3\end{array}\right]$$

where

$${\mathsf{A}}_3=\left[\begin{array}{ccc}{a}_7& b_7& c_7\\ b_7& -d_7& b_7\\ c_7& b_7& -a_7\end{array}\right],{\mathsf{B}}_3=\left[\begin{array}{ccc}{a}_7& -b_7& c_7\\ -b_7& -d_7& -b_7\\ c_7& -b_7& -a_7\end{array}\right].$$

Considering this, we may obtain the following expression for the first stage of decomposition:

$${\mathsf{Y}}_{7\times 1}={\mathsf{P}}_7^{\left({\pi }_7^{\left(1\right)}\right)}{\mathsf{P}}_7^{\left(1\right)}{\mathsf{W}}_{7\times 11}{\mathsf{W}}_{11\times 8}{\mathsf{D}}_8^{\left(1\right)}{\mathsf{W}}_{8\times 11}{\mathsf{W}}_{11\times 7}{\mathsf{P}}_7^{\left({\pi }_7^{\left(0\right)}\right)}{\mathsf{P}}_7^{\left(0\right)}{\mathsf{X}}_{7\times 1}$$

(34)

where

$$\begin{array}{cc}\hfill {\mathsf{W}}_{11\times 7}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & & 1& & \\ & & & & & 1& \\ & & & & & & 1\\ 1& & & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & & 1\end{array}\right],& \begin{array}{c}{\mathsf{W}}_{8\times 11}=\left[\begin{array}{cccccc}{\mathsf{H}}_2\otimes {\mathsf{I}}_3& & & & & \\ & & & 1& & \\ & 1& -1& & -1& 1\end{array}\right],\hfill \\ \\ {\mathsf{D}}_8^{\left(1\right)}=\left[\begin{array}{cccc}{\mathsf{F}}_3& & & \\ & {\mathsf{G}}_3& & \\ & & d_7& \\ & & & d_7\end{array}\right],\hfill \\ \\ {\mathsf{F}}_3=\left({\mathsf{A}}_3+{\mathsf{B}}_3\right)/2,{\mathsf{G}}_3=\left({\mathsf{A}}_3-{\mathsf{B}}_3\right)/2,\hfill \end{array}\hfill \end{array}$$

$${\mathsf{W}}_{11\times 8}=\left[\begin{array}{ccc}{\mathsf{H}}_2\otimes {\mathsf{I}}_3& & \\ & 1& \\ & -1& \\ & & 1\\ & -1& \\ & 1\end{array}\right],{\mathsf{W}}_{7\times 11}=\left[\begin{array}{ccccccccccc}1& & & & & & 1& & & & \\ & 1& & & & & & & & & \\ & & 1& & & & & 1& & & \\ & & & & & & & & 1& & \\ & & & 1& & & & & & 1& \\ & & & & 1& & & & & & \\ & & & & & 1& & & & & 1\end{array}\right].$$

The matrices ${\mathsf{F}}_3$ and ${\mathsf{G}}_3$ are as takes after:

$${\mathsf{F}}_3={\displaystyle \frac{\left[\begin{array}{ccc}{a}_7& b_7& c_7\\ b_7& -d_7& b_7\\ c_7& b_7& -a_7\end{array}\right]+\left[\begin{array}{ccc}{a}_7& -b_7& c_7\\ -b_7& -d_7& -b_7\\ c_7& -b_7& -a_7\end{array}\right]}{2}}=\left[\begin{array}{ccc}{a}_7& & c_7\\ & -d_7& \\ c_7& & -a_7\end{array}\right],$$

(35)

$${\mathsf{G}}_3={\displaystyle \frac{\left[\begin{array}{ccc}{a}_7& b_7& c_7\\ b_7& -d_7& b_7\\ c_7& b_7& -a_7\end{array}\right]-\left[\begin{array}{ccc}{a}_7& -b_7& c_7\\ -b_7& -d_7& -b_7\\ c_7& -b_7& -a_7\end{array}\right]}{2}}=\left[\begin{array}{ccc}& b_7& \\ b_7& & b_7\\ & b_7\end{array}\right].$$

(36)

Now, we will divide the matrix ${\mathsf{F}}_3$ into two parts:

$${\mathsf{F}}_3={\mathsf{F}}_3^{\left(\mathrm{a}\right)}+{\mathsf{F}}_3^{\left(\mathrm{b}\right)}$$

(37)

where

$${\mathsf{F}}_3^{\left(\mathrm{a}\right)}=\left[\begin{array}{ccc}{a}_7& & c_7\\ & & \\ c_7& & -a_7\end{array}\right],{\mathsf{F}}_3^{\left(\mathrm{b}\right)}=\left[\begin{array}{ccc}& & \\ & -d_7& \\ & & \end{array}\right].$$

The matrix ${\mathsf{F}}_3^{\left(\mathrm{a}\right)}$ after removing terms equal to zero is as follows:

$${\mathsf{F}}_2=\left[\begin{array}{cc}{a}_7& c_7\\ c_7& -a_7\end{array}\right]\mathrm{and}\mathrm{matches}\mathrm{the}\mathrm{matrix}\mathrm{pattern}\left[\begin{array}{cc}a& b\\ b& -a\end{array}\right].$$

The calculation procedure for matrix ${\mathsf{F}}_3$ is as follows:

$${\mathsf{F}}_3={\mathsf{W}}_{3\times 4}{\mathsf{D}}_4^{\left(2\right)}{\mathsf{W}}_{4\times 3}$$

(38)

where

$${\mathsf{W}}_{4\times 3}=\left[\begin{array}{ccc}1& & \\ & & 1\\ 1& & 1\\ & 1& \end{array}\right],{\mathsf{D}}_4^{\left(2\right)}=\mathrm{diag}\left(s_0^{\left(7\right)},s_1^{\left(7\right)},s_2^{\left(7\right)},s_3^{\left(7\right)}\right),s_0^{\left(7\right)}=a_7-c_7,$$

$$s_1^{\left(7\right)}=-a_7-c_7,s_2^{\left(7\right)}=c_7,s_3^{\left(7\right)}=-d_7,{\mathsf{W}}_{3\times 4}=\left[\begin{array}{cccc}1& & 1& \\ & & & 1\\ & 1& 1& \end{array}\right].$$

The calculation procedure for matrix ${\mathsf{G}}_3$ is as follows:

$${\mathsf{G}}_3={\mathsf{W}}_{3\times 2}{\mathsf{D}}_2^{\left(1\right)}{\mathsf{W}}_{2\times 3}$$

(39)

where

$${\mathsf{W}}_{2\times 3}=\left[\begin{array}{ccc}1& & 1\\ & 1& \end{array}\right],{\mathsf{D}}_2^{\left(1\right)}=\mathrm{diag}\left(s_4^{\left(7\right)},s_5^{\left(7\right)}\right),s_4^{\left(7\right)}=s_5^{\left(7\right)}=b_7,{\mathsf{W}}_{3\times 2}=\left[\begin{array}{cc}& 1\\ 1& \\ & 1\end{array}\right].$$

In regard to this, we can determine the final expression for DST-I for N = 7:

$${\mathsf{Y}}_{7\times 1}={\mathsf{P}}_7^{\left({\pi }_7^{\left(1\right)}\right)}{\mathsf{P}}_7^{\left(1\right)}{\mathsf{W}}_{7\times 11}{\mathsf{W}}_{11\times 8}{\mathsf{W}}_8^{\left(1\right)}{\mathsf{D}}_8^{\left(2\right)}{\mathsf{W}}_8^{\left(0\right)}{\mathsf{W}}_{8\times 11}{\mathsf{W}}_{11\times 7}{\mathsf{P}}_7^{\left({\pi }_7^{\left(0\right)}\right)}{\mathsf{P}}_7^{\left(0\right)}{\mathsf{X}}_{7\times 1}$$

(40)

where

$${\mathsf{W}}_8^{\left(0\right)}=\left[\begin{array}{ccc}{\mathsf{W}}_{4\times 3}& & \\ & {\mathsf{W}}_{2\times 3}& \\ & & {\mathsf{I}}_2\end{array}\right],{\mathsf{D}}_8^{\left(2\right)}=\left[\begin{array}{ccc}{\mathsf{D}}_4^{\left(2\right)}& & \\ & {\mathsf{D}}_2^{\left(1\right)}& \\ & & {\mathsf{D}}_2^{\left(2\right)}\end{array}\right],$$

$${\mathsf{D}}_2^{\left(2\right)}=\mathrm{diag}\left(s_6^{\left(7\right)},s_7^{\left(7\right)}\right),s_6^{\left(7\right)}=s_7^{\left(7\right)}=d_7,{\mathsf{W}}_8^{\left(1\right)}=\left[\begin{array}{ccc}{\mathsf{W}}_{3\times 4}& & \\ & {\mathsf{W}}_{3\times 2}& \\ & & {\mathsf{I}}_2\end{array}\right].$$

The data flow graph for our solution for seven-point DST-I is shown in Figure 6. The naive, direct computation requires 37 additions and 32 multiplications. As can be observed, our solution uses 23 additions and 5 multiplications, reducing the number of additions from 37 to 23 and the number of multiplications from 32 to 5.

9. Eight-Point DST-I Solution

The following is the matrix form expression for eight-point DST-I:

$${\mathsf{Y}}_{8\times 1}={\mathsf{C}}_8{\mathsf{X}}_{8\times 1}$$

(41)

where

$${\mathsf{Y}}_{8\times 1}={\left[y_0,y_1,y_2,y_3,y_4,y_5,y_6,y_7\right]}^{\mathrm{T}},{\mathsf{X}}_{8\times 1}={\left[x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7\right]}^{\mathrm{T}},$$

$$\begin{array}{cc}\hfill {\mathsf{C}}_8=\left[\begin{array}{cccccccc}{a}_8& b_8& c_8& d_8& d_8& c_8& b_8& a_8\\ b_8& d_8& c_8& a_8& -a_8& -c_8& -d_8& -b_8\\ c_8& c_8& 0& -c_8& -c_8& 0& c_8& c_8\\ d_8& a_8& -c_8& -b_8& b_8& c_8& -a_8& -d_8\\ d_8& -a_8& -c_8& b_8& b_8& -c_8& -a_8& d_8\\ c_8& -c_8& 0& c_8& -c_8& 0& c_8& -c_8\\ b_8& -d_8& c_8& -a_8& -a_8& c_8& -d_8& b_8\\ a_8& -b_8& c_8& -d_8& d_8& -c_8& b_8& -a_8\end{array}\right],& \begin{array}{c}{a}_8=0.1612,\hfill \\ \\ b_8=0.3030,\hfill \\ \\ c_8=0.4082,\hfill \\ \\ d_8=0.4642.\hfill \end{array}\hfill \end{array}$$

Now, we swap the columns and rows in matrix ${\mathsf{C}}_8$ to match the following matrix pattern:

$$\left[\begin{array}{cc}{\mathsf{A}}_4& {\mathsf{A}}_4\\ {\mathsf{B}}_4& -{\mathsf{B}}_4\end{array}\right]$$

where

$${\mathsf{A}}_4=\left[\begin{array}{cccc}{a}_8& b_8& c_8& d_8\\ b_8& -d_8& c_8& -a_8\\ c_8& c_8& 0& -c_8\\ d_8& -a_8& -c_8& b_8\end{array}\right],{\mathsf{B}}_4=\left[\begin{array}{cccc}{d}_8& a_8& -c_8& -b_8\\ c_8& -c_8& 0& c_8\\ b_8& d_8& c_8& a_8\\ a_8& -b_8& c_8& -d_8\end{array}\right].$$

This is accomplished by the permutation ${\pi }_8^{\left(0\right)}$ for the columns and permutation ${\pi }_8^{\left(1\right)}$ for the rows:

$${\pi }_8^{\left(0\right)}=\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 1& 2& 3& 4& 8& 7& 6& 5\end{array}\right),{\pi }_8^{\left(1\right)}=\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 1& 7& 3& 5& 4& 6& 2& 8\end{array}\right).$$

(42)

Considering this, we may obtain the following expression for the first stage of decomposition:

$${\mathsf{Y}}_{8\times 1}={\mathsf{P}}_8^{\left({\pi }_8^{\left(1\right)}\right)}{\mathsf{D}}_8^{\left(3\right)}{\mathsf{W}}_8^{\left(2\right)}{\mathsf{P}}_8^{\left({\pi }_8^{\left(0\right)}\right)}{\mathsf{X}}_{8\times 1}$$

(43)

where

$$\begin{array}{cc}\hfill {\mathsf{P}}_8^{\left({\pi }_8^{\left(0\right)}\right)}=\left[\begin{array}{ccccc}{\mathsf{I}}_4& & & & \\ & & & & 1\\ & & & 1& \\ & & 1& & \\ & 1& & & \end{array}\right],& \begin{array}{c}{\mathsf{W}}_8^{\left(2\right)}={\mathsf{H}}_2\otimes {\mathsf{I}}_4,\hfill \\ \\ {\mathsf{D}}_8^{\left(3\right)}={\mathsf{A}}_4\oplus {\mathsf{B}}_4,\hfill \end{array}\hfill \end{array}$$

$${\mathsf{P}}_8^{\left({\pi }_8^{\left(1\right)}\right)}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & & & & & & 1& \\ & & 1& & & & & \\ & & & & 1& & & \\ & & & 1& & & & \\ & & & & & 1& & \\ & 1& & & & & & \\ & & & & & & & 1\end{array}\right].$$

Now, we will deal with matrices ${\mathsf{A}}_4$ and ${\mathsf{B}}_4$. Permute rows of ${\mathsf{A}}_4$ according to ${\pi }_4^{\left(0\right)}$, change the sign in row 1 and 4 and change the sign in column 4. These operations are described in the expression below:

$${\mathsf{A}}_4^{\prime }={\mathsf{P}}_4^{\left(1\right)}{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}{\mathsf{A}}_4{\mathsf{P}}_4^{\left(0\right)}$$

(44)

where

$${\mathsf{P}}_4^{\left(0\right)}=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & 1& \\ & & & -1\end{array}\right],{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}=\left[\begin{array}{cccc}1& & & \\ & & & 1\\ & & 1& \\ & 1& & \end{array}\right],{\mathsf{P}}_4^{\left(1\right)}=\left[\begin{array}{cccc}-1& & & \\ & 1& & \\ & & 1& \\ & & & -1\end{array}\right].$$

As a result of the above Equation (44), matrix ${\mathsf{A}}_4^{\prime }$ looks like the following:

$${\mathsf{A}}_4^{\prime }=\left[\begin{array}{cccc}-a_8& -b_8& -c_8& d_8\\ d_8& -a_8& -c_8& -b_8\\ c_8& c_8& 0& c_8\\ -b_8& d_8& -c_8& -a_8\end{array}\right].$$

Now, we will divide the matrix ${\mathsf{A}}_4^{\prime }$ into two parts:

$${\mathsf{A}}_4^{\prime }={\mathsf{A}}_4^{\left(\mathrm{a}\right)}+{\mathsf{A}}_4^{\left(\mathrm{b}\right)}$$

(45)

where

$${\mathsf{A}}_4^{\left(\mathrm{a}\right)}=\left[\begin{array}{cccc}-a_8& -b_8& & d_8\\ d_8& -a_8& & -b_8\\ & & & \\ -b_8& d_8& & -a_8\end{array}\right],{\mathsf{A}}_4^{\left(\mathrm{b}\right)}=\left[\begin{array}{cccc}& & -c_8& \\ & & -c_8& \\ c_8& c_8& & c_8\\ & & -c_8& \end{array}\right].$$

The matrix ${\mathsf{A}}_4^{\left(\mathrm{a}\right)}$ after removing terms equal to zero is as follows:

$${\mathsf{A}}_3=\left[\begin{array}{ccc}-a_8& -b_8& d_8\\ d_8& -a_8& -b_8\\ -b_8& d_8& -a_8\end{array}\right]\mathrm{and}\mathrm{takes}\mathrm{the}\mathrm{form}\mathrm{of}\mathrm{a}\mathrm{circular}\mathrm{convolution}\mathrm{matrix}.$$

So, we can again use the properties of a circular convolution matrix:

$$s_0^{\left(8\right)}={\displaystyle \frac{-a_8+d_8-b_8}{3}},s_1^{\left(8\right)}=-a_8+b_8,s_2^{\left(8\right)}=d_8+b_8,s_3^{\left(8\right)}={\displaystyle \frac{-a_8+d_8+2b_8}{3}}.$$

(46)

The calculation procedure for matrix ${\mathsf{A}}_4$ is as follows:

$${\mathsf{A}}_4={\left({\mathsf{P}}_4^{\left(1\right)}{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}\right)}^{\mathrm{T}}{\mathsf{W}}_{4\times 7}^{\left(0\right)}{\mathsf{W}}_{7\times 5}^{\left(1\right)}{\mathsf{W}}_{5\times 6}{\mathsf{D}}_6^{\left(5\right)}{\mathsf{W}}_{6\times 5}{\mathsf{W}}_{5\times 7}^{\left(1\right)}{\mathsf{W}}_7{\mathsf{P}}_4^{\left(0\right)}$$

(47)

where

$$\begin{array}{cc}\hfill {\mathsf{W}}_7=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & & 1\\ 1& & & \\ & 1& & \\ & & 1& \\ & & & 1\end{array}\right],& \begin{array}{c}{\mathsf{W}}_{5\times 7}^{\left(1\right)}=\left[\begin{array}{ccccc}{\mathsf{T}}_3^{\left(0\right)}& & & & \\ & & & 1& \\ & 1& 1& & 1\end{array}\right],\hfill \\ \\ {\mathsf{W}}_{6\times 5}=\left[\begin{array}{cc}{\mathsf{A}}_{4\times 3}& \\ & {\mathsf{I}}_2\end{array}\right],\hfill \end{array}\hfill \end{array}$$

$$\begin{array}{c}\hfill \begin{array}{c}{\mathsf{D}}_6^{\left(5\right)}=\mathrm{diag}\left(s_0^{\left(8\right)},s_1^{\left(8\right)},...,s_5^{\left(8\right)}\right),\hfill \\ \\ s_4^{\left(8\right)}=s_5^{\left(8\right)}=c_8,\hfill \end{array}{\mathsf{W}}_{5\times 6}=\left[\begin{array}{cc}{\mathsf{A}}_{3\times 4}& \\ & {\mathsf{I}}_2\end{array}\right],{\mathsf{W}}_{7\times 5}^{\left(1\right)}=\left[\begin{array}{ccc}{\mathsf{T}}_3^{\left(1\right)}& & \\ & -1& \\ & -1& \\ & & 1\\ & -1& \end{array}\right],\end{array}$$

$${\mathsf{W}}_{4\times 7}^{\left(0\right)}=\left[\begin{array}{ccccccc}1& & & 1& & & \\ & 1& & & 1& & \\ & & & & & 1& \\ & & 1& & & & 1\end{array}\right].$$

In matrix ${\mathsf{B}}_4$, change the sign in row 1 and change the sign in column 2. These operations are described in the expression below:

$${\mathsf{B}}_4^{\prime }={\mathsf{P}}_4^{\left(3\right)}{\mathsf{B}}_4{\mathsf{P}}_4^{\left(2\right)}$$

(48)

where

$${\mathsf{P}}_4^{\left(2\right)}=\left[\begin{array}{cccc}1& & & \\ & -1& & \\ & & 1& \\ & & & 1\end{array}\right],{\mathsf{P}}_4^{\left(3\right)}=\left[\begin{array}{cccc}-1& & & \\ & 1& & \\ & & 1& \\ & & & 1\end{array}\right].$$

As a result of the above Equation (48), matrix ${\mathsf{B}}_4^{\prime }$ looks like this:

$${\mathsf{B}}_4^{\prime }=\left[\begin{array}{cccc}-d_8& a_8& c_8& b_8\\ c_8& c_8& 0& c_8\\ b_8& -d_8& c_8& a_8\\ a_8& b_8& c_8& -d_8\end{array}\right].$$

Now, we will divide the matrix ${\mathsf{B}}_4^{\prime }$ into two parts:

$${\mathsf{B}}_4^{\prime }={\mathsf{B}}_4^{\left(\mathrm{a}\right)}+{\mathsf{B}}_4^{\left(\mathrm{b}\right)}$$

(49)

where

$${\mathsf{B}}_4^{\left(\mathrm{a}\right)}=\left[\begin{array}{cccc}-d_8& a_8& & b_8\\ & & & \\ b_8& -d_8& & a_8\\ a_8& b_8& & -d_8\end{array}\right],{\mathsf{B}}_4^{\left(\mathrm{b}\right)}=\left[\begin{array}{cccc}& & c_8& \\ c_8& c_8& & c_8\\ & & c_8& \\ & & c_8& \end{array}\right].$$

The matrix ${\mathsf{B}}_4^{\left(\mathrm{a}\right)}$ after removing terms equal to zero is as follows:

$${\mathsf{B}}_3=\left[\begin{array}{ccc}-d_8& a_8& b_8\\ b_8& -d_8& a_8\\ a_8& b_8& -d_8\end{array}\right]\mathrm{and}\mathrm{takes}\mathrm{the}\mathrm{form}\mathrm{of}\mathrm{a}\mathrm{circular}\mathrm{convolution}\mathrm{matrix}.$$

So, we can again use the properties of a circular convolution matrix:

$$s_6^{\left(8\right)}={\displaystyle \frac{-d_8+b_8+a_8}{3}},s_7^{\left(8\right)}=-d_8-a_8,s_8^{\left(8\right)}=b_8-a_8,s_9^{\left(8\right)}={\displaystyle \frac{-d_8+b_8-2a_8}{3}}.$$

(50)

The calculation procedure for matrix ${\mathsf{B}}_4$ is as follows:

$${\mathsf{B}}_4={\mathsf{P}}_4^{\left(3\right)}{\mathsf{W}}_{4\times 7}^{\left(1\right)}{\mathsf{W}}_{7\times 5}^{\left(2\right)}{\mathsf{W}}_{5\times 6}{\mathsf{D}}_6^{\left(6\right)}{\mathsf{W}}_{6\times 5}{\mathsf{W}}_{5\times 7}^{\left(1\right)}{\mathsf{W}}_7{\mathsf{P}}_4^{\left(2\right)}$$

(51)

where

$$\begin{array}{cc}\hfill \begin{array}{c}{\mathsf{D}}_6^{\left(6\right)}=\mathrm{diag}\left(s_6^{\left(8\right)},s_7^{\left(8\right)},...,s_{11}^{\left(8\right)}\right),\hfill \\ \\ s_{10}^{\left(8\right)}=s_{11}^{\left(8\right)}=c_8,\hfill \end{array}& {\mathsf{W}}_{7\times 5}^{\left(2\right)}=\left[\begin{array}{ccc}{\mathsf{T}}_3^{\left(1\right)}& & \\ & 1& \\ & & 1\\ & 1& \\ & 1& \end{array}\right],\hfill \end{array}$$

$${\mathsf{W}}_{4\times 7}^{\left(1\right)}=\left[\begin{array}{ccccccc}1& & & 1& & & \\ & & & & 1& & \\ & 1& & & & 1& \\ & & 1& & & & 1\end{array}\right].$$

Taking all the transformations together, we obtain the following expression for the fast DST-I algorithm for N = 8:

$${\mathsf{Y}}_{8\times 1}={\mathsf{P}}_8^{\left({\pi }_8^{\left(1\right)}\right)}{\mathsf{P}}_8^{\left(1\right)}{\mathsf{W}}_{8\times 14}{\mathsf{W}}_{14\times 10}{\mathsf{W}}_{10\times 12}{\mathsf{D}}_{12}{\mathsf{W}}_{12\times 10}{\mathsf{W}}_{10\times 14}{\mathsf{W}}_{14\times 8}{\mathsf{P}}_8^{\left(0\right)}{\mathsf{W}}_8^{\left(2\right)}{\mathsf{P}}_8^{\left({\pi }_8^{\left(0\right)}\right)}{\mathsf{X}}_{8\times 1}$$

(52)

where

$$\begin{array}{c}\hfill {\mathsf{P}}_8^{\left(0\right)}=\left[\begin{array}{cc}{\mathsf{P}}_4^{\left(0\right)}& \\ & {\mathsf{P}}_4^{\left(2\right)}\end{array}\right],{\mathsf{W}}_{14\times 8}=\left[\begin{array}{cc}{\mathsf{W}}_{7\times 4}& \\ & {\mathsf{W}}_{7\times 4}\end{array}\right],{\mathsf{W}}_{10\times 14}=\left[\begin{array}{cc}{\mathsf{W}}_{5\times 7}^{\left(1\right)}& \\ & {\mathsf{W}}_{5\times 7}^{\left(1\right)}\end{array}\right],\end{array}$$

$$\begin{array}{c}\hfill {\mathsf{W}}_{12\times 10}=\left[\begin{array}{cc}{\mathsf{W}}_{6\times 5}& \\ & {\mathsf{W}}_{6\times 5}\end{array}\right],{\mathsf{D}}_{12}=\left[\begin{array}{cc}{\mathsf{D}}_6^{\left(5\right)}& \\ & {\mathsf{D}}_6^{\left(6\right)}\end{array}\right],{\mathsf{W}}_{10\times 12}=\left[\begin{array}{cc}{\mathsf{W}}_{5\times 6}& \\ & {\mathsf{W}}_{5\times 6}\end{array}\right],\end{array}$$

$$\begin{array}{c}\hfill {\mathsf{W}}_{14\times 10}=\left[\begin{array}{cc}{\mathsf{W}}_{7\times 5}^{\left(1\right)}& \\ & {\mathsf{W}}_{7\times 5}^{\left(2\right)}\end{array}\right],{\mathsf{W}}_{8\times 14}=\left[\begin{array}{cc}{\mathsf{W}}_{4\times 7}^{\left(0\right)}& \\ & {\mathsf{W}}_{4\times 7}^{\left(1\right)}\end{array}\right],\end{array}$$

$$\begin{array}{c}\hfill {\mathsf{P}}_8^{\left(1\right)}=\left[\begin{array}{cc}{\left({\mathsf{P}}_4^{\left(1\right)}{\mathsf{P}}_4^{\left({\pi }_4^{\left(0\right)}\right)}\right)}^{\mathsf{T}}& \\ & {\mathsf{P}}_4^{\left(3\right)}\end{array}\right].\end{array}$$

The data flow graph for our solution for eight-point DST-I is shown in Figure 7. The naive, direct computation requires 52 additions and 60 multiplications. As can be observed, our solution uses 40 additions and 12 multiplications, reducing the number of additions from 52 to 40 and the number of multiplications from 60 to 12.

10. Results

The work shows how it is possible to reduce the number of multiplication operations in DST-I algorithms of sizes two to eight. At the same time, the number of addition operations was slightly reduced. The number of addition operations was reduced by an average of 21% and the number of multiplication operations was reduced by an average of 74%. The achieved results are presented in the

Table 1. Comparison of the direct method with the proposed solutions.

	Direct Method		Proposed Solutions
N	Additions	Multiplications	Additions	Multiplications
2	2	4	2	2
3	5	4	4	2
4	12	16	12	6
5	16	9	12	3
6	30	36	28	8
7	37	32	23	5
8	52	60	40	12

.

This allows for a significant reduction in the amount of resources used on a signal processor, while speeding up work and allowing for easier operation in real time. A significant reduction in multiplication operations contributes to this, because, due to their characteristics, they are more expensive to use than addition operations.

Each proposed algorithm has been implemented in the MATLAB environment and we are sure that they all work correctly. We have published the program code in an open dataset repository, which we reference in the Data Availability Statement section.

11. Discussion of Computational Complexity

For the direct DST-I calculation approach and suggested solutions, we first describe how to determine the number of multiplication and addition operations. A bit shift can be used in place of a multiplication operation for any number that is a power of two. We do not count addition and multiplication operations for a value of zero.

The above appear in the following matrices: ${\mathsf{C}}_3$—one 0 and four values of 0.5; ${\mathsf{C}}_5$—four 0s and twelve values of 0.5; ${\mathsf{C}}_7$—five 0s and twelve values of 0.5; ${\mathsf{C}}_8$—four 0s. And in the proposed solutions in diagonal matrices, we have the following: ${\mathsf{D}}_3$—one value of 0.5; ${\mathsf{D}}_6^{\left(3\right)}$—three values of 0.5; ${\mathsf{D}}_8^{\left(2\right)}$—three values of 0.5; ${\mathsf{D}}_8$—one value 0.5.

Additionally,

Table 2. Comparison of the proposed solutions with other algorithms.

	N = 4		N = 8
	Additions	Multiplications	Additions	Multiplications
Yip and Rao [40]	4	2 + 4	22	8 + 8
Sun and Yip [45]	-	-	18	6 + 8
Our solutions	12	6	40	12

provides a comparison with the results obtained by other researchers of the topic we addressed. Yip and Rao used the sparse-matrix factorization technique and Sun and Yip used the idea of split radix algorithm. However, these works do not present the exact step-by-step achievement of the results, as we show for each solution. Our solutions are transparent.

In this regard, we note that both works in the table below do not include normalizing coefficients in the number of multiplication operations. To the Yip and Rao solution for N = 4, we have added four multiplication operations, which correspond to multiplications by normalizing coefficients. Similarly, for the DST algorithms for N = 8, we have added eight multiplication operations in both cases.

The rigorous mathematical derivation of the final computational procedures for each case is presented in full. To ensure the correctness of these procedures, we have written validation computer programs, which we have included in our paper. We do not claim that the presented solutions are optimal. We show what we have obtained so far and would be glad if someone publishes better solutions.