# Brent–Kung adder

Part of a series on :
Arithmetic logic circuits :
Quick navigation :
Theory
Binary number
Boolean algebra
Logic gate
Ones' complement number
Two's complement number
Signed number representations :
Components
Adder (+)
Adder
Half adder
Full adder
Ripple-carry adder
Carry-lookahead adder
Brent–Kung adder
Kogge–Stone adder
Ling adder
Carry-save adder
Carry-select adder
Carry-skip adder
Adder–subtractor (±)
Adder–subtractor
Subtractor (−)
Subtractor
Full subtractor
Half subtractor
Multiplier (×)
Binary multiplier
Multiplication algorithm
Booth's multiplication algorithm
Wallace tree
Dadda multiplier
Divider (÷)
Binary Divider
Division algorithm
Bitwise ops
Bitwise operation
NOT
AND
OR
XOR
Bit shifts
Bit manipulation
See also
Kochanski multiplication (exponentiation)
Multiply–accumulate operation :
Categories
Category:Binary arithmetic
Category:Computer arithmetic :
See also
FPU
GPU
AGU
Mechanical calculator :
vte :
The Brent–Kung adder (BKA or BK), proposed in 1982, is an advanced binary adder design, having a gate level depth of $O(\log _{2}(n))$.

## Introduction

The Brent–Kung adder is a parallel prefix adder (PPA) form of carry-lookahead adder (CLA). Proposed by Richard Peirce Brent and Hsiang Te Kung in 1982 it introduced higher regularity to the adder structure and has less wiring congestion leading to better performance and less necessary chip area to implement compared to the Kogge–Stone adder (KSA). It is also much quicker than ripple-carry adders (RCA).
Ripple-carry adders were the initial multi-bit adders which were developed in the early days and got their name from the ripple effect which the carry made while being propagated from right to left. The time taken for addition was directly proportional to the length of the bit being added. This is reverse in Brent–Kung adders where the carry is calculated in parallel thus reducing the addition time drastically. Further work has been done on Brent–Kung adders and other parallel adders to reduce the power consumption and chip area as well as to increase the speed thus making them suitable for low-power designs.
A Brent–Kung adder is a parallel adder made in a regular layout with an aim of minimizing the chip area and ease of manufacturing. The addition of n-bit number can be performed in time $O(\log _{2}n)$ with a chip size of area $O(n\log _{2}n),$ thus making it a good-choice adder with constraints on area and maximizing the performance. Its symmetry and regular build structure reduces costs of production effectively and enable it to be used in pipeline architectures. In parallel adders the critical path is decided by computation of the carry from least significant bit (LSB) adder to the most significant bit (MSB) adder, therefore efforts are in reducing the critical path for the carry to reach the MSB.

## Basic model outline

In general, most of the adders use carry-in and the corresponding bits of two numbers (A and B) to get the corresponding sum bit and carry-out - with ripple carry adders taking $O(n)$ time for carry to reach MSB.
* Considering that A = a$_n$ a$_{n-1}$ … a$_1$ and B = b$_n$ b$_{n-1}$ … b$_1$ both be n-bit binary numbers.
* With sum being S = s$_{n+1}$ s$_n$ … s$_1$ and carry generated in each stage C = c$_n$ … c$_0$ will be carry-in to next stages.
* For RCA, c$_0$ = 0, and i the sum bit and carry bit generated are c$_i$ = g$_i$ ∨ (a$_i$ ∧ c$_{i-1}$) ∨ (b$_i$ ∧ c$_{i-1}$), s$_i$ = a$_i$ ⊕ b$_i$ ⊕ c$_{i-1}$ for i = 1, 2, … n s$_{n+1}$ = c$_n$ respectively.
* It is possible to transform the above ripple carry into carry-lookahead (CLA) by defining the carry bit i as c$_0$ = 0, c$_i$ = g$_i$ ∨ (p$_i$ ∧ c$_{i-1}$) where g$_i$ = a$_i$ ∧ b$_i$, p$_i$ = a$_i$ ⊕ b$_i$, and s$_i$ = p$_i$ ⊕ c$_{i-1}$ for i = 1, 2, … n. p and g are known as carry propagate and carry generate. This corresponds to the fact that the carry c$_i$ is either generated by a$_i$ and b$_i$ or propagated from the previous carry c$_{i-1}$.
Brent and Kung further transformed the carry generation and propagation by defining an associative operator ○ which defines the carry generation and propagation across a range of bits as (g$_1$, p$_1$) ○ (g$_2$, p$_2$) = (g$_2$ ∨ (p$_2$ ∧ g$_1$), p$_1$ ∧ p$_2$).
* They also defined the values G$_i$ and P$_i$ as the generate and propagate bits for the bits from i through 1, i.e. (G$_1$, P$_1$) = (g$_1$, p$_1$) for i = 1; otherwise (G$_i$, P$_i$) = (g$_i$, p$_i$) ○ (G$_{i-1}$, P$_{i-1}$) for i = 2, 3, … n. It can be derived that G$_i$ in the function is equivalent to c$_i$. Also (G$_n$, P$_n$) can be non-recursively written as = (g$_n$, p$_n$) ○ (g$_{n-1}$, p$_{n-1}$) ○ … ○ (g$_1$, p$_1$).
Taking advantage of the associativity of operator ○, (G$_n$, P$_n$) can be computed in a tree-like manner.
The design of the white nodes is obvious as they are just buffering the g$_i$'s and p$_i$'s, and the black nodes are performing operation defined by operator ○, which is similar to a one bit adder.
* This tree-like propagation of carry reduces its critical path to that of tree height. As the carry tree height can be maximum of $O(log_{2}(n))$, the critical path of the Brent–Kung parallel adder is also $O(log_{2}(n))$, which is better than the normal adder performance of $O(n)$. The tree-based layout also reduces the chip area and redundant wiring required in general CLA-based adders.

## Final processing stage

Using the carry propagation and generation transformation for working out addition and carry used by Brent and Kung, the performance of the adder increases considerably and also leads to an increase in regularity. The final sum can be calculated as follows: s$_i$ = p$_i$ ⊕ G$_{i-1}$, since p$_i$ = a$_i$ ⊕ b$_i$ and G$_{i-1}$ = c$_{i-1}$.

## Low-power adder

The increase in performance in Brent–Kung adders is attributed to its tree structure of carry propagation which also leads to lower power consumption as the carry signal now has to travel through fewer stages, leading to less switching of transistors. Also, the decrease in amount of wiring and fan-out also contributes largely to its lower power consumption than CLA adders. A Brent–Kung adder can also be used in a pipeline manner which can further reduce the power consumption by reducing the depth of combinatorial logic and glitches stabilization. The graph shows a low-power Brent–Kung adder.

## Comparison with Kogge–Stone adder
### Advantages

Due to this type of adder requiring fewer modules to implement than the Kogge–Stone adder, the Brent–Kung adder is much simpler to build. It also contains far fewer connections to other modules, which also contributes to its simplicity.

### Disadvantages

This type of adder has greater delay, requiring 2 log$_2$ n − 2 levels of logic to compute all the carry bits. (Kogge–Stone requires log$_2$ n.)

### Equations

8-bit Kogge-Stone adder, valency-2:
8-bit Kogge-Stone adder, valency-2,3,4:
8-bit Brent-Kung adder, valency-2: