## 4 Computational Cost Analysis  
Compared to the direct method, the proposed algorithms achieve a notable reduction in the number of multiplications at the expense of an increase in elementary additions. Table 1 summarizes this reduction. As multiplication operations typically require more resources than additions, the proposed method offers resource savings in application-specific integrated circuits (ASICs) and enables the use of more straightforward and cheaper field-programmable gate arrays (FPGAs). The number of additions is reduced when constant coefficient values are present in the Toeplitz matrix. In such a situation, it becomes possible to precalculate the multipliers appearing in matrices \(\mathbf{D}_{6}^{(3)}\) (4), \(\mathbf{D}_{9}^{(4)}\) (7), \(\mathbf{D}_{14}^{(5)}\) (10), \(\mathbf{D}_{18}^{(6)}\) (13), \(\mathbf{D}_{25}^{(7)}\) (16), \(\mathbf{D}_{27}^{(8)}\) (19), or \(\mathbf{D}_{36}^{(9)}\) (22). As a result, there is a notable reduction in the number of additions, as included in Table 2.  
Figure 7: Data flow diagram of the algorithm (23) for \(N=9\). The proposed algorithm was exemplified in FPGAs on Xilinx's Spartan 3, the most straightforward possible device of the Spartan series, containing the number of inputs and outputs required by the algorithm. The 8-bit \(x_{i}\) inputs, 16-bit \(y_{i}\) outputs, and fixed 8-bit coefficients in the Toeplitz matrix were assumed. Table 3 shows the number of slices and Table 4 the four-input LUTs used in the Spartan 3 FPGA implementation. Both algorithms took full advantage of the available multipliers MULT 18 \(\times\) 18 on each FPGA chip, as shown in Table 3. A significant reduction in the logic blocks used was achieved in the example applications shown. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Order of**} & \multicolumn{3}{c}{**Multiplications**} & \multicolumn{3}{c}{**Additions**} & \multicolumn{3}{c}{**Arithmetic Operations**} \\ \cline{2-10}  & **Direct** & **Prop.** & **Reduct.** & **Direct** & **Prop.** & **Incr.** & **Direct** & **Prop.** & **Incr.** \\ \hline
3 & 9 & 6 & 3 & 6 & 15 & 9 & 15 & 21 & 6 \\
4 & 16 & 9 & 7 & 12 & 26 & 14 & 28 & 35 & 7 \\
5 & 25 & 14 & 11 & 20 & 45 & 25 & 45 & 59 & 14 \\
6 & 36 & 18 & 18 & 30 & 60 & 30 & 66 & 78 & 12 \\
7 & 49 & 25 & 24 & 42 & 87 & 45 & 91 & 112 & 21 \\
8 & 64 & 27 & 37 & 56 & 114 & 58 & 120 & 141 & 21 \\
9 & 81 & 36 & 45 & 72 & 144 & 72 & 153 & 180 & 27 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The comparison of the number of multiplications and additions in the direct method and the proposed algorithm in the general case. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Order of**} & \multicolumn{3}{c}{**Multiplications**} & \multicolumn{3}{c}{**Additions**} & \multicolumn{3}{c}{**Arithmetic Operations**} \\ \cline{2-10}  & **Direct** & **Prop.** & **Reduct.** & **Direct** & **Prop.** & **Incr.** & **Direct** & **Prop.** & **Reduct.** \\ \hline
3 & 9 & 6 & 3 & 6 & 9 & 3 & 15 & 15 & 0 \\
4 & 16 & 9 & 7 & 12 & 15 & 3 & 28 & 24 & 4 \\
5 & 25 & 14 & 11 & 20 & 27 & 7 & 45 & 41 & 4 \\
6 & 36 & 18 & 18 & 30 & 33 & 3 & 66 & 51 & 15 \\
7 & 49 & 25 & 24 & 42 & 51 & 9 & 91 & 76 & 15 \\
8 & 64 & 27 & 37 & 56 & 57 & 1 & 120 & 84 & 36 \\
9 & 81 & 36 & 45 & 72 & 81 & 9 & 153 & 117 & 36 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The comparison of the number of multiplications and additions in the direct method and the proposed algorithm, assuming a constant value of the elements of the Toeplitz matrix.