## 3 Boolean Masking for Addition Circuits
### Brent-Kung Adder (BKA)  
A BKA [16] allows a further reduction in the number of PG blocks in comparison to an SA, albeit with the cost of increased latency. The general structure of BKA is composed of two trees, where the first tree computes the group generate and propagate terms of increasingly larger groups of bits until the carry bit for the most significant output can be determined. The resulting structure can be viewed as a binary tree where the output carry for the most significant bit represents the root and the PG terms generated by the preprocessing represent the leafs. An 8-bit version of this tree is shown in Figure 3.  
As PG terms, which are not required to compute the most significant carry bit, are not considered in this process, a second reversed tree is needed in order to generate them. A full 8-bit BKA that can compute all bits of the final sum is depicted in Figure 4. Note that in this 8-bit case, the carry for the most significant bit is already available after \(\log 8=3\) stages. However, an additional stage is required for the reverse tree, which computes the remaining carry bits. As a result, the 8-bit BKA requires a total of 4 stages and 11 PG blocks, excluding the preprocessing stage. Figure 3: 8-bit Brent–Kung Adder, generation of the MSB carry bit. The first stage in a BKA is the same as for the SA, combining every other PG term with its neighbor and therefore generating \(\frac{n}{2}\) 2-bit PG terms. Following the tree structure of BKAs, the second stage combines adjacent 2-bit PG terms to 4-bit terms as:  
\[PG(\left\{4\cdot i+3,4\cdot i+2\right\}\,,\,\left\{4\cdot i+1,4\cdot i\right\}) \,\,\forall 0\leq i<n/4.\]  
This pattern is repeated until the final carry can be computed, requiring \(\log n\) stages. The \(k\)-th stage therefore computes PG terms for increasingly larger groups of bits using \(\frac{n}{2^{k+1}}\) PG blocks according to:  
\[PG\left(\left\{i\cdot 2^{k+1}-1,(2\cdot i-1)\cdot 2^{k}\right\}\,,\right.\] \[\left.\left\{(2\cdot i-1)\cdot 2^{k}-1,(i-1)\cdot 2^{k+1}\right\} \right)\,\,\forall 1\leq i<\frac{n}{2^{k+1}}.\]  
The resulting structure consists of \(n-1\) PG blocks, of which \(\log n\) are only needed for the output carry generation. As explained above, this binary tree does only generate the group PG terms that are necessary to calculate carry for the MSB. The reversed tree is therefore inserted to the circuit below the initial binary tree, generating the remaining terms. In order to improve the readability of the equations describing the PG term generation, we count the stages of this subtree beginning with the output stage of the adder, i.e., the stage number \(l\) of the inverse tree is related to the stage of the complete adder \(k\) through \(l=2\cdot\log n-2-k\). On the lowest level (\(l=0\)), the inverse tree generates all even PG terms, i.e., \(pg(\left\{2\cdot i,0\right\})\,\,\forall 1\leq i<n/2\) as:  
\[PG(\left\{2\cdot i,2\cdot i\right\}\,,\,\left\{2\cdot i-1,0\right\})\,\, \forall 1\leq i<n/2.\]  
In general, the inverse tree in a BKA computes \(\frac{n}{2^{k+1}}-1\) PG terms in \(\log n-1\) stages as:  
\[PG\left(\left\{i\cdot 2^{l+1}+2^{l}-1,i\cdot 2^{l+1}\right\}\,,\,\left\{i\cdot 2 ^{l+1}-1,0\right\}\right)\,\,\forall 1\leq i<\frac{n}{2^{l+1}}-1.\]  
The total number of PG terms in this lower tree is equal to \(n-\log n-1\). When joining both tree structures, the last stage of the upper tree and the first stage of the lower tree can be combined in one stage, as there is no direct dependency between them. If no carry output is required, this step is trivial as the last stage of the upper tree can be omitted. As a result, a BKA can be realized in with a total of \(2\cdot(n-\log n-1)\) PG blocks in \(2\cdot\log n-2\) stages, when no carry output is computed. Figure 4: Complete 8-bit Brent–Kung Adder. The asymptotic complexity of the number of PG blocks in a BKA is \(\mathcal{O}(n)\) in comparison to \(\mathcal{O}(n\cdot\log n)\) in the KSA and SA cases. This leads directly to smaller implementations if masking countermeasures are employed.