## 2 Materials and Methods
### Multiply-Accumulate Units  
Consider the implementation of a MAC unit in the FIR DF node corresponding to the coefficient \(b_{i}\). This unit performs calculations using the formula  
\[Y_{i}=b_{i}X(N-i)+Y_{i-1}, \tag{2}\]  
where \(Y_{i}\) is the result of the current MAC unit and \(Y_{i-1}\) is the result of the previous MAC unit. To obtain a result, according to Formula (2), there is no need to perform a complete multiplication \(b_{i}X(N-i)\). Instead, it is enough to use the generator of \(k\) partial products, where \(k=\left\lceil log_{2}b_{i}\right\rceil\) is the bit width of filter coefficient \(b_{i}\), and a carry-save adder (CSA) tree [25], without using the final addition of the Kogge-Stone adder (KSA) [26]. Instead, an additional term \(Y_{i-1}\) can be fed to the CSA tree, and the outputs \(A\) and \(B\) of this tree can be summed in the KSA. The MAC unit operating according to this principle is shown in Figure 2. Using the notation ((k + 1):2), it can be shown that (k + 1) terms are fed to the input of the CSA tree, and two terms are formed at the output. Figure 1: Finite impulse response (FIR) digital filter (DF) scheme of order \(K\). MAC is multiply-accumulate unit. Figure 2: Structure of the multiply-accumulate (MAC) unit. CSA is carry-save adder. KSA is Kogge-Stone adder. The basic device for performing arithmetic operations is a full adder (FA) [25]. Bits \(\alpha\), \(\beta\) and the carry \(C_{in}\) are the inputs of the device, which are converted to output bits \(S\) and \(C_{out}\) using the formulas  
\[ \begin{split} S=\alpha\oplus\beta\oplus C_{in},\\ C_{out}=(\alpha\ \&\beta)\vee(C_{in}\&( \alpha\oplus\beta))\end{split}  \tag{3}\]  
where bit \(S\) is a sum, the output bit \(C_{out}\) is a carry obtained in the FA, \(\oplus\) is an exclusive disjunction, & is a conjunction and \(\vee\) is a disjunction. The main idea of a CSA is to transform three input vectors of a device into two output vectors: sum and carry. At the same time, the amount of information for processing at the next step is reduced by 1.5 times. Another modification of the adders is the Kogge-Stone parallel-prefix adders. Consider the addition of two k-bit numbers \(A\) and \(B\). The idea of the parallel-prefix implementation is performed in three steps. At the first stage, the carry-generate bits \(G_{i}\), the carry-propagate bits \(P_{i}\) and the half-sums \(H_{i}\) are pre-calculated for \(i\), \(0\leq i\leq k-1\):  
\[G_{i}=A_{i}\& B_{i},\ P_{i}=A_{i}\lor B_{i},\ H_{i}=A_{i}\oplus B_{i} \tag{4}\]  
The second stage of addition, called the parallel-prefix network, computes the carry bits \(C_{i}\), for \(0\leq i\leq k-1\), using \(G_{i}\) and \(P_{i}\). For this, an operator \(\circ\) is used that connects pairs of carry-generate and carry-propagate bits, and is defined as  
\[(G,P)\circ(G^{\prime},P^{\prime})=(G\vee(P\& G^{\prime}),P\& P^{\prime}). \tag{5}\]  
The sequential calculation of carry-generate and carry-propagate bit pairs \((G,P)\) are denoted as \(\left(G_{i;j},P_{i;j}\right)\), \(i>j\), where the corresponding pair is calculated based on the bits \(i,i-1,\ldots,j\) in the following way:  
\[\left(G_{i;j},P_{i;j}\right)=(G_{i},P_{i})\circ(G_{i-1},P_{i-1})\circ\ldots \circ\left(G_{j},P_{j}\right). \tag{6}\]  
Since the carry is \(C_{i}=G_{i;0}\) for all \(i>0\), all carries can be calculated using only the operator \(\circ\)[26]. At the third stage, the sum is calculated as  
\[S_{0}=H_{0}\oplus C_{in},\ S_{i}=H_{i}\oplus C_{i-1}\,\ S_{k}=C_{k-1} \tag{7}\]  
for \(0\leq i\leq k-1\). Figure 3 shows the basic blocks for the parallel-prefix addition. Block 3a implements Formula (4). Block 3b implements Formula (5). No action takes place in block 3c. Block 3d implements Formula (7). Figure 4 shows the parallel-prefix adder scheme with the organization of a parallel-prefix network, according to the Kogge-Stone method.