# VLSI-Friendly Filtering Algorithms for Deep Neural Networks
## 3 Preliminary Remarks  
The primary step in computing a 2D convolution involves taking the dot product between the vectors created by the sliding time window from the present data stream and the impulse response of an \(M\)-order finite impulse response (FIR) filter. The procedure for computing convolution elements can be represented as follows in the most general case:  
\[y_{j}=\sum_{i=0}^{M-1}x_{i+j}w_{i} \tag{1}\]  
\[j=0,1,\ldots,N-M+1,\]  
where \(N\) represents the length of the current data stream, with \(\{x_{i+j}\}\) denoting the elements of the data stream, and \(\{w_{i}\}\) represents the constant coefficients of the FIR filter's impulse response. In a more detailed form, expression (1) can be represented as follows:  
\[ \begin{array}{c}y_{0}=w_{0}x_{0}+w_{1}x_{1}+\cdots+w_{M-1}x_{M-1}\\ y_{1}=w_{0}x_{1}+w_{1}x_{2}+\cdots+w_{M-1}x_{M}\\ \vdots\\ y_{N-M}=w_{0}x_{N-M}+w_{1}x_{N-M+1}+\cdots+w_{M-1}x_{N-1}\end{array}  \tag{2}\]  
Figure 1 illustrates the sequence of steps in calculating the moving dot product. The equations above comprehensively describe all the mathematical operations required for the calculations. However, strictly speaking, they do not constitute an algorithm since they do not reveal the specific sequence of calculations. In some instances, expressing the sliding dot product operation as a matrix-vector product is more convenient:  
\[\textbf{Y}_{(N-M+1)\times 1}=\textbf{W}_{(N-M+1)\times N}\textbf{X}_{N\times 1} \tag{3}\]  
where:  
\[\textbf{Y}_{(N-M+1)\times 1}=[y_{0},y_{1},\ldots,y_{N-M}]^{\text{T}},\]  
\[\textbf{X}_{N\times 1}=[x_{0},x_{1},\ldots,x_{N-1}]^{\text{T}},\]  
\[\textbf{W}_{(N-M+1)\times N}=\left[ \begin{array}{cccccc}w_{0}&w_{1}&\cdots& w_{M-1}&&\\ &w_{0}&w_{1}&\cdots&w_{M-1}&\\ &&\ddots&\ddots&\ddots&\ddots&\\ &&&w_{0}&w_{1}&\cdots&w_{M-1}\end{array} \right].\]  
However, regarding the research task at hand, such a representation is unhelpful as it does not facilitate identifying opportunities for reducing the computational complexity of the procedure for determining the sliding inner product when the sequence is comprised of input signal samples. Figure 1: The illustration of the step sequences during calculating the moving dot product. Let us rewrite expressions (2) in the following form:  
\[\textbf{Y}_{(N-M+1)\times 1}=\textbf{X}_{(N-M+1)\times M}\textbf{W}_{M\times 1} \tag{4}\]  
where:  
\[\textbf{W}_{M\times 1}=[w_{0},w_{1},\dots,w_{M-1}]^{\text{T}},\]  
\[\textbf{X}_{(N-M+1)\times M}=\left[ \begin{array}{cccc}x_{0}&x_{1}&\cdots&x_{ M-1}\\ x_{1}&x_{2}&\cdots&x_{M}\\ \vdots&\vdots&\ddots&\vdots\\ x_{N-M}&x_{N-M+1}&\cdots&x_{N-1}\end{array} \right].\]  
This form of writing is much more useful and legible, which will be visible in the next steps. It turns out that considering the structural properties of the matrix \(\textbf{X}_{(N-M+1)\times M}\) in the expression (4) allows for a fairly significant reduction in the number of arithmetic operations. Let us consider this problem in more detail. Let us impose certain conditions on the sizes of the input sequences. Suppose \(N=M(K+1)-1\), where \(K=1,2,3,\dots\) is a positive integer number. It is obvious that if the supposed requirement for \(N\) is not satisfied, sequences \(\{x_{n}\},n=0,1,\dots,N-1\) can be padded with zeros without losing computation precision. Then the expression (4) takes the following form:  
\[\textbf{Y}_{KM\times 1}=\textbf{X}_{KM\times M}\textbf{W}_{M\times 1} \tag{5}\]  
where:  
\[\textbf{Y}_{KM\times 1}=[y_{0},y_{1},\dots,y_{KM-1}]^{\text{T}},\]  
\[\textbf{X}_{KM\times M}=\left[\textbf{X}_{1\times M^{\prime}}^{(0)}\textbf{X} _{1\times M^{\prime}}^{(1)},\dots,\textbf{X}_{1\times M}^{(KM-1)}\right]^{ \text{T}},\]  
and  
\[\textbf{X}_{1\times M}^{(i)}=[x_{i},x_{i+1},\dots,x_{M-1+i}],\quad i=0,1,\dots, KM-1.\]  
To see the structure of the matrix \(\textbf{X}_{KM\times M}\), we present expression (5) in a more detailed form:  
\[\left[ \begin{array}{c}y_{0}\\ y_{1}\\ \vdots\\ y_{KM-1}\end{array} \right]=\left[