# VLSI-Friendly Filtering Algorithms for Deep Neural Networks
## 5 Implementation Complexity  
Due to the relatively small lengths of the input sequences and the straightforward nature of the data flow diagrams depicting the computation process, it is easy to assess the implementation complexity of the proposed solutions. Table 1 estimates the number of arithmetic blocks required for the fully parallel implementation of the filtering algorithms designed for short lengths. The values presented in the table can be regarded as an approximate measure of the implementation cost on an ASIC.  
Figure 5: Data flow graph of the algorithm for implementing the basic filtering operation for the case \(M=9\).  
As we can see, using the proposed algorithmic solutions to construct digital filtering cores results in fewer multipliers being needed than using naive approaches to their design. In the context of designing specialised fully parallel VLSI processors, minimising the number of multipliers is of paramount importance. This approach significantly reduces the cost of implementing the entire system and mitigates power dissipation. This is due to the hardware multiplier's higher level of complexity and larger chip area occupation than the adder. It has been demonstrated that the hardware cost of a binary adder rises linearly with the operand size. In contrast, the implementation cost of a hardwired multiplier escalates quadratically with the operand size [46]. Hence, reducing the number of multipliers, even if it results in a slight increase in the number of adders, significantly influences the hardware implementation of digital filtering cores.  
The proposed algorithms have been exemplarily implemented in FPGAs on the simplest possible devices of Xilinx's Spartan 3 series. The criterion for selecting a model from the Spartan 3 family was to provide a sufficient number of inputs and outputs. The 8-bit inputs \(\mathbf{X}_{(2M-1)\times 1}\), 16-bit outputs \(\mathbf{Y}_{9\times 1}\), and fixed 8-bit coefficients of the impulse response of the FIR filter \(\mathbf{W}_{M\times 1}\), were assumed. Table 2 shows the number of slices used in the Spartan 3 FPGA implementation. The number of uses multipliers MULT 18\(\times\)18 is also shown in this table, but both algorithms mostly used all hardware-accessible multipliers. Only for size \(M=5\) was the number of available multipliers is for the proposed algorithm greater than required, and only in this case did the algorithm not use all of them. Table 3 shows the number of four input LUTs used in the Spartan 3 FPGA implementation. For each size \(M\), the proposed algorithms achieved a reduction of the logic blocks used. The smallest was for the size \(M=3\), where the reduction was only about 1% for the slices and 2,4% for four inputs LUTs. The biggest was for size \(M=5\), which achieves nearly a 40% decrease in logical blocks.  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & & & \multicolumn{4}{c}{**Numbers of Arithmetic Blocks**} \\
**Size \(M\)** & **Naive Method** & & & & & **Proposed Algorithm** & \\ \hline  & **Multipliers** & **M-Input** & **Multipliers** & **2-Input** & **3-Input** & **4-Input** & **M-Input** \\
3 & 9 & 3 & 6 & - & 6 & - & - \\
5 & 25 & 5 & 14 & 4 & - & - & 10 \\
7 & 49 & 7 & 25 & 7 & 24 & 1 & 1 \\
9 & 81 & 9 & 36 & - & 60 & - & - \\ \hline \hline \end{tabular}
\end{table}
Table 1: The complexities of implementing of the naive and proposed solutions.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & \multicolumn{3}{c}{**MULT 18 \(\times\) 18**} & \multicolumn{3}{c}{**Slices**} \\
**Size \(M\)** & **Devices** & **School** & **Proposed** & **School** & **Proposed** & **Reduction** \\ \hline
3 & xc3s50- & 4p4p208 & 4 & 4 & 111 & 110 & 0.9\% \\
5 & xc3s400- & 16 & 14 & 563 & 342 & 39.3\% \\
7 & xc3s400- & 16 & 16 & 776 & 684 & 11.9\% \\
9 & xc3s1000- & 24 & 24 & 1303 & 1066 & 18.2\% \\ \hline \hline \end{tabular}
\end{table}
Table 2: The number of the multipliers MULT 18 \(\times\) 18, and the slices used in the Spartan 3 FPGA implementations.