Smaller Circuits for Bit Addition
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916966579568640 |
|---|---|
| author | Goncharov, Mikhail Kulikov, Alexander S. Levtsov, Georgie |
| author_facet | Goncharov, Mikhail Kulikov, Alexander S. Levtsov, Georgie |
| contents | Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. 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. A vast majority of these results are devoted to optimizing the circuit depth (also known as delay).
In this paper, we investigate the circuit size (also known as area) over the full binary basis of bit addition. Though most of the known circuits are built from Half Adders and Full Adders, we show that, in many interesting scenarios, these circuits have suboptimal size. Namely, we improve an upper bound $5n-3m$ to $4.5n-2m$, where $n$ is the number of input bits and $m$ is the number of output bits. In the regimes where $m$ is small compared to $n$ (for example, for computing the sum of $n$ bits or multiplying two $n$-bit integers), this leads to $10\%$ improvement.
We complement our theoretical result by an open-source implementation of generators producing circuits for bit addition and multiplication. The generators allow one to produce the corresponding circuits in two lines of code and to compare them to existing designs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13966 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Smaller Circuits for Bit Addition Goncharov, Mikhail Kulikov, Alexander S. Levtsov, Georgie Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. 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. A vast majority of these results are devoted to optimizing the circuit depth (also known as delay). In this paper, we investigate the circuit size (also known as area) over the full binary basis of bit addition. Though most of the known circuits are built from Half Adders and Full Adders, we show that, in many interesting scenarios, these circuits have suboptimal size. Namely, we improve an upper bound $5n-3m$ to $4.5n-2m$, where $n$ is the number of input bits and $m$ is the number of output bits. In the regimes where $m$ is small compared to $n$ (for example, for computing the sum of $n$ bits or multiplying two $n$-bit integers), this leads to $10\%$ improvement. We complement our theoretical result by an open-source implementation of generators producing circuits for bit addition and multiplication. The generators allow one to produce the corresponding circuits in two lines of code and to compare them to existing designs. |
| title | Smaller Circuits for Bit Addition |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science |
| url | https://arxiv.org/abs/2509.13966 |