Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and\n Fan-Out Two Article Swipe

MAKE IMPACT

Stephan Held , Sophie Spirkl · YOU? · · 2015 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1503.08659

We consider the problem of constructing fast and small binary adder circuits.\nAmong widely-used adders, the Kogge-Stone adder is often considered the\nfastest, because it computes the carry bits for two $n$-bit numbers (where $n$\nis a power of two) with a depth of $2\\log_2 n$ logic gates, size $4 n\\log_2 n$,\nand all fan-outs bounded by two. Fan-outs of more than two are avoided, because\nthey lead to the insertion of repeaters for repowering the signal and\nadditional depth in the physical implementation. However, the depth bound of\nthe Kogge-Stone adder is off by a factor of two from the lower bound of $\\log_2\nn$. This bound is achieved asymptotically in two separate constructions by\nBrent and Krapchenko. Brent's construction gives neither a bound on the fan-out\nnor the size, while Krapchenko's adder has linear size, but can have up to\nlinear fan-out. With a fan-out bound of two, neither construction achieves a\ndepth of less than $2 \\log_2 n$. In a further approach, Brent and Kung proposed\nan adder with linear size and fan-out two, but twice the depth of the\nKogge-Stone adder. These results are 33-43 years old and no substantial\ntheoretical improvement for has been made since then.\n In this paper we integrate the individual advantages of all previous adder\ncircuits into a new family of full adders, the first to improve on the depth\nbound of $2\\log_2 n$ while maintaining a fan-out bound of two. Our adders\nachieve an asymptotically optimum logic gate depth of $\\log_2 n + o(\\log_2 n)$\nand linear size $\\mathcal {O}(n)$.\n

Type

preprint

Landing Page

http://arxiv.org/abs/1503.08659

PDF

https://arxiv.org/pdf/1503.08659

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4300600261

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4300600261

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1503.08659

Digital Object Identifier

Title

Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and\n Fan-Out Two

Work title

Type

preprint

OpenAlex work type

Publication year

2015

Year of publication

Publication date

2015-03-30

Full publication date if available

Authors

Stephan Held, Sophie Spirkl

List of authors in order

Landing page

https://arxiv.org/abs/1503.08659

Publisher landing page

PDF URL

https://arxiv.org/pdf/1503.08659

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1503.08659

Direct OA link when available

Concepts

Adder, Fan-out, Upper and lower bounds, Mathematics, Arithmetic, Carry-save adder, Binary number, Bounded function, Electronic circuit, Serial binary adder, Discrete mathematics, Combinatorics, Computer science, Telecommunications, Mathematical analysis, Electrical engineering, Chip, Engineering, Latency (audio)

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload