Smaller Circuits for Bit Addition

Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. Three specific scenarios where it is used frequently are listed below.

• $\mathrm{■}$

  Adding two $n$-bit numbers.

• $\mathrm{■}$

  Computing a symmetric Boolean function (such as majority or sorting). A natural way of doing this is to first compute the binary representation of the sum of $n$ input bits (that is, to compress $n$ bits into about ${\log }_{2}n$ bits) and then to compute the function at hand out of the computed binary representation.

• $\mathrm{■}$

  To multiply two $n$-bit numbers, one may first compute all partial products (that is, products of the bits of the two input numbers) and then sum up the resulting bits.

In terms of the dot-notation introduced by Dadda [4], the three scenarios discussed above are visualized as shown in Figure 1. In this notation, one places bits of the same significance on the same vertical layer.

There are many other cases where one needs to add bits. Say, one may want to add a single bit to an $n$-bit number (the increment operation is a special case), or to add three $n$-bit numbers, or to add a few bits of varying significance, see Figure 2.

A function capturing all such scenarios is known as bit adder

It is parameterized by the significance vector $s=(s_1,\mathrm{\dots },s_n)\in {\mathbb{Z}}_{\ge 0}^n$, takes $n$ input bits $(x_1,\mathrm{\dots },x_n)\in {\{0,1\}}^n$, and outputs the binary representation of

This way, ${\mathrm{SUM}}_n={\mathrm{BA}}_n^{0,0,\mathrm{\dots },0}$ and ${\mathrm{ADD}}_n={\mathrm{BA}}_{2n}^{0,0,1,1,\mathrm{\dots },n-1,n-1}$.

Since bit addition is such a basic task in Boolean circuit synthesis, a lot of research has been done on constructing efficient circuits for various special cases of it, see, for example, [9, 8, 12, 2]. A vast majority of these results is devoted to optimizing the circuit depth (also known as delay). In this paper, we investigate the circuit size (also known as area) of bit addition. Specifically, we study circuits over the full binary basis.

Two basic building blocks for adding bits are known as Half Adder (HA) and Full Adder (FA). They compute the binary representation of the sum of two and three bits, respectively (that is, ${\mathrm{SUM}}_2$ and ${\mathrm{SUM}}_3$). In the full binary basis, they can be implemented in two and five gates, respectively, see Figure 3.

Using Half Adders and Full Adders, one can synthesize a bit adder using the following algorithm that goes back to Napier’s Rabdologiæ (1617), as modernized by Dadda [4].

Process the bits layer by layer, in the order of increasing significance. While the current significance layer $i$ contains at least three bits, take three of them and apply the Full Adder to replace them with a pair of bits of significance $i$ and $i+1$. If there are two bits left at the current layer $i$, apply the Half Adder to them to get a pair of bits of significance $i$ and $i+1$.

This algorithm ensures that, for any vector $s\in {\mathbb{Z}}_{\ge 0}^n$,

Indeed, each application of the Full Adder reduces the number of bits by one, hence the total cost of all Full Adders is at most $5(n-m)$. The Half Adder is applied at most once for each of the significance layers, hence the total cost of all Half Adders is at most $2m$. Hence, the total size is at most $5(n-m)+2m=5n-3m$. Note that most of the previous works consider specific special cases of bit addition (like summation or multiplication) where $m$ is a specific function on $n$. In such cases, the upper bounds are stated in terms of $n$ only. The parameter $m$ arises naturally when one considers the general bit addition function.

By applying this algorithm to partial products of bits of two input $n$-bit numbers, one gets the well-known Dadda multiplier circuit [4]. For many vectors $s$, the upper bound $5n-3m$ is loose: it does not match the size of the actual circuit produced by the algorithm. A straightforward example is $s=(0,1,\mathrm{\dots },n-1)$: in this case, no gates are needed whereas the upper bound is $2n$. It is also worth noting that, in some cases, the resulting circuit is provably optimal. For example, for the ${\mathrm{ADD}}_n$ function (that computes the sum of two $n$-bit integers), the method constructs a circuit out of a single Half Adder and $(n-1)$ Full Adders. The resulting circuit is known as ripple-carry adder and has size $5n-3$. Red’kin [10] proved that there is no smaller circuit for this function.

At the same time, in many scenarios, not only the bound $5n-3m$ is loose, but also the circuit produced by the algorithm is suboptimal. For example, for ${\mathrm{SUM}}_5$, it gives a circuit of size $12$ consisting of two Full Adders and one Half Adder, see Figure 4. However, ${\mathrm{SUM}}_5$ can be computed by a circuit of size $11$ as shown by [7] (see also Figure 7 later in the text). In general, whereas the algorithm produces a circuit of size about $5n$ for ${\mathrm{SUM}}_n$, this function can be computed by a circuit of size about $4.5n$ as shown by Demenkov et al. [5].

In this paper, we generalize the construction by Demenkov et al. Namely, we prove an upper bound $4.5n-2m$ for the circuit size of bit addition. In the regimes where $m$ is small compared to $n$, this gives a circuit that is about $10\%$ smaller. This applies to the Dadda multiplier. We complement our theoretical result by an open source implementation of generators producing circuits for bit addition and multiplication.

We also show that it is provably impossible to improve the two upper bounds above to $5n-3.01m$ or $4.5n-2.51m$. We achieve this by establishing that the circuit size of the increment function (a special case of the bit addition function with $m=n+1$) is equal to $2n$.

In this section, we formally introduce the Boolean functions studied in this paper as well as the main building blocks for computing them.

In this section, we prove a new upper bound $4.5n-2m$ for the circuit size of bit addition. For regimes where $m$ is small compared to $n$, this is better than $5n-3m$ by about $10\%$. This applies to ${\mathrm{MULT}}_n$ and ${\mathrm{SUM}}_n$.

In the proof, we use the following straightforward observation. Assume that . In this case, the first output is equal to $x_1$, the cost of computing this particular bit of the output is zero, allowing one to forget about it. Thus,

where $s^{\prime }=(s_2,\mathrm{\dots },s_n)$. We call the operation of replacing $s$ by $s^{\prime }$ as shifting. Note that shifting reduces both the number of inputs and the number of outputs by one. Figure 9 gives an example.

The upper bound $\mathrm{size}({\mathrm{BA}}_n^s)\le 5n-3m$ holds for any vector $s$, but in many scenarios it is loose. For example, for the function

this upper bounds turns into $5\cdot 2n-3(n+1)=7n-3$, whereas $\mathrm{size}({\mathrm{ADD}}_n)=5n-3$. Interestingly, the term $3m$ in the upper bound $5n-3m$ cannot be increased: for any constant $\alpha >3$, there exists a vector $s$ such that $\mathrm{size}({\mathrm{BA}}_n^s)\ge 5n-\alpha m-O(1)$. One example of such a vector is $s=(0,0,1,\mathrm{\dots },n-1)$. The corresponding function ${\mathrm{BA}}_n^s$ adds a bit to an $n$-bit number. It is not difficult to see that it can be computed using $n$ Half Adders (see Figure 10), hence its circuit size is at most $2n$. Below, we show that this straightforward circuit is optimal (up to an additive constant). It also shows that it is impossible to improve our upper bound $4.5n-2m$ to $4.5n-\beta m$ for $\beta >2.5$.

We implemented efficient generators of our new circuits in the Cirbo open-source framework [1]. To generate a circuit computing ${\mathrm{BA}}_n^s$, one passes the vector $s$. Listing 1 shows how to use the generator to produce an efficient circuit computing ${\mathrm{SUM}}_{31}$ in a single line of code. When the circuit is generated, one can use a wide range of Cirbo methods to analyze and manipulate the circuit.

In this paper, we presented smaller circuits for bit addition. In many practically relevant scenarios, the described circuits are about 10% smaller than the known circuits composed out of Half Adders and Full Adders. Also, we implemented generators that allow one to produce the corresponding circuits using a single line of code via the Cirbo open-source package [1].

There are three natural open problems related to the circuit size of bit addition.

1. 1.

   What is the largest $\alpha$ such that

   $$\mathrm{size}({\mathrm{BA}}_n^s)\le 4.5n-\alpha m$$

   holds for every vector $s$? In this paper, we proved that $\alpha \ge 2$. Theorem 1 shows that $\alpha \le 2.5$. An example of a vector where our upper bound $4.5n-2m$ matches the size of the circuit produced by our algorithm is

   $$s^{\ast }=(0,0,0,0,1,1,2,2,\mathrm{\dots },\frac{n}{2}-2,\frac{n}{2}-2).$$

   In this case, our method first spends $n/2$ gates to pair the bits and then applies $n/2$ MDFA’ blocks. The size of the resulting circuit is, up to an additive constant, $n/2+6\cdot n/2=3.5n$. This matches the upper bound $4.5n-2m$. Thus, to improve the bound $4.5n-2m$ to $4.5n-\beta m$, for $\beta >2$, one needs to find a smaller circuit for this particular vector $s^{\ast }$. And vice versa, by proving a lower bound $\mathrm{size}({\mathrm{BA}}_n^{s^{\ast }})\ge 3.5n-O(1)$, one would prove that $\alpha =2$.

2. 2.

   What is the smallest $\gamma$ such that

   $$\mathrm{size}({\mathrm{BA}}_n^s)\le \gamma n-O(m)$$

   holds for every vector $s$? In this paper, we proved that $\gamma \le 4.5$. Improving this seems to be more challenging than just improving $2m$ to $2.5m$ as this would most probably require using new building blocks.

3. 3.

   Finally, note also that the upper bounds $5n-3m$ and $4.5n-2m$ hold for all vectors $s$. It would be interesting to improve known upper and lower bounds for specific vectors. Perhaps, one of the most interesting such functions is ${\mathrm{SUM}}_n$ (here, $s=(0,0,\mathrm{\dots },0)$). For it, we know an upper bound $4.5n$ (originally proved by Demenkov et al. [5]; also follows from our Theorem 1) and a lower bound $2.5n-O(1)$ due to Stockmeyer [13].