Brent–Kung adder

The Brent–Kung adder (BKA or BK), proposed in 1982,^[1] is an advanced binary adder design, having a gate level depth of $O(\log _{2}(n))$ .

Introduction edit

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 edit

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₁ and B = b_n b_n-1 … b₁ both be n-bit binary numbers.
With sum being S = s_n+1 s_n … s₁ and carry generated in each stage C = c_n … c₀ will be carry-in to next stages.

For RCA, c₀ = 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,
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₁, p₁) ○ (g₂, p₂) = (g₁ ∨ (p₁ ∧ g₂), p₁ ∧ p₂).

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₁, P₁) = (g₁, p₁) 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₁, p₁).

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 edit

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 edit

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.^[1] The graph shows a low-power Brent–Kung adder.^[2]

Comparison with Kogge–Stone adder edit

Diagram of an 8-bit Kogge–Stone adder. Each white diamond implements the ○ operation. Note that there are at most three diamonds between any input and any output.

Diagram of an 8-bit Brent–Kung adder. The Brent–Kung adder uses fewer modules and connections than the Kogge–Stone adder. Note that there are up to four white diamonds between e.g. input bits 0–3 and output bit 6.

Advantages edit

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.^[3]

Disadvantages edit

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

Equations edit

8-bit Kogge-Stone adder, valency-2:

P00 = A0 XOR B0              '1dt, S0
G00 = A0 AND B0              '1dt, C0
P10 = A1 XOR B1              '1dt  
G10 = A1 AND B1              '1dt 
P20 = A2 XOR B2              '1dt
G20 = A2 AND B2              '1dt 
P30 = A3 XOR B3              '1dt
G30 = A3 AND B3              '1dt
P40 = A4 XOR B4              '1dt
G40 = A4 AND B4              '1dt
P50 = A5 XOR B5              '1dt
G50 = A5 AND B5              '1dt  
P60 = A6 XOR B6              '1dt
G60 = A6 AND B6              '1dt
P70 = A7 XOR B7              '1dt
G70 = A7 AND B7              '1dt

G11 = G10 OR P10 AND G00     '3dt, C1
P21 = P20 AND P10            '2dt
G21 = G20 OR P20 AND G10     '3dt
P31 = P30 AND P20            '2dt
G31 = G30 OR P30 AND G20     '3dt
P41 = P40 AND P30            '2dt 
G41 = G40 OR P40 AND G30     '3dt
P51 = P50 AND P40            '2dt
G51 = G50 OR P50 AND G40     '3dt
P61 = P60 AND P50            '2dt
G61 = G60 OR P60 AND G50     '3dt
P71 = P70 AND P60            '2dt
G71 = G70 OR P70 AND G60     '3dt

G22 = G21 OR P21 AND G00     '4dt, C2
G32 = G31 OR P31 AND G11     '5dt, C3
P42 = P41 AND P21            '3dt
G42 = G41 OR P41 AND G21     '5dt
P52 = P51 AND P31            '3dt 
G52 = G51 OR P51 AND G31     '5dt
P62 = P61 AND P41            '3dt
G62 = G61 OR P61 AND G41     '5dt
P72 = P71 AND P51            '3dt
G72 = G71 OR P71 AND G51     '5dt

G43 = G42 OR P42 AND G00     '6dt, C4
G53 = G52 OR P52 AND G11     '6dt, C5
G63 = G62 OR P62 AND G22     '6dt, C6
G73 = G72 OR P72 AND G32     '7dt, C7, Cout

S0 = P00                     '1dt
S1 = P10 XOR G00             '2dt
S2 = P20 XOR G11             '4dt
S3 = P30 XOR G22             '5dt
S4 = P40 XOR G32             '6dt
S5 = P50 XOR G43             '7dt
S6 = P60 XOR G53             '7dt
S7 = P70 XOR G63             '7dt

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

P00 = A0 XOR B0                    '1dt, S0
G00 = A0 AND B0                    '1dt, C0
P10 = A1 XOR B1                    '1dt
G10 = A1 AND B1                    '1dt
P20 = A2 XOR B2                    '1dt
G20 = A2 AND B2                    '1dt
P30 = A3 XOR B3                    '1dt
G30 = A3 AND B3                    '1dt
P40 = A4 XOR B4                    '1dt
G40 = A4 AND B4                    '1dt
P50 = A5 XOR B5                    '1dt
G50 = A5 AND B5                    '1dt
P60 = A6 XOR B6                    '1dt
G60 = A6 AND B6                    '1dt
P70 = A7 XOR B7                    '1dt
G70 = A7 AND B7                    '1dt

G11 = G10 OR P10 AND G00           '3dt, distance=2^0=1, valency-2, C1
P21 = P20 AND P10                  '2dt
G21 = G20 OR P20 AND G10           '3dt, distance=2^0=1, valency-2
P31 = P30 AND P20                  '2dt
G31 = G30 OR P30 AND G20           '3dt, distance=2^0=1, valency-2
P41 = P40 AND P30                  '2dt
G41 = G40 OR P40 AND G30           '3dt, distance=2^0=1, valency-2
P51 = P50 AND P40                  '2dt
G51 = G50 OR P50 AND G40           '3dt, distance=2^0=1, valency-2
P61 = P60 AND P50                  '2dt
G61 = G60 OR P60 AND G50           '3dt, distance=2^0=1, valency-2
P71 = P70 AND P60                  '2dt
G71 = G70 OR P70 AND G60           '3dt, distance=2^0=1, valency-2

G22 = G20 OR_
      P20 AND G10 OR_
      P20 AND P10 AND G00          '3dt, distance=2^1=2, valency-3, C2
G32 = G30 OR_
      P30 AND G20 OR_
      P30 AND P20 AND G10 OR_
      P30 AND P20 AND P10 AND G00  '3dt, distance=2^1=2, valency-4, C3
P42 = P41 AND P21                  '3dt, distance=2^1=2
G42 = G40 OR_
      P40 AND G30 OR_
      P40 AND P30 AND G20 OR_
      P40 AND P30 AND P20 AND G10  '3dt, distance=2^1=2, valency-4
P52 = P51 AND P31                  '3dt, distance=2^1=2
G52 = G50 OR_
      P50 AND G40 OR_
      P50 AND P40 AND G30 OR_
      P50 AND P40 AND P30 AND G20  '3dt, distance=2^1=2, valency-4
P62 = P61 AND P41                  '3dt, distance=2^1=2
G62 = G60 OR_
      P60 AND G50 OR_
      P60 AND P50 AND G40 OR_
      P60 AND P50 AND P40 AND G30  '3dt, distance=2^1=2, valency-4
P72 = P71 AND P51
G72 = G70 OR_
      P70 AND G60 OR_
      P70 AND P60 AND G50 OR_
      P70 AND P60 AND P50 AND G40  '3dt, distance=2^1=2, valency-4

G43 = G42 OR P42 AND G00           '5dt, distance=2^2=4, valency-2, C4
G53 = G52 OR P52 AND G11           '5dt, distance=2^2=4, valency-2, C5
G63 = G62 OR P62 AND G22           '5dt, distance=2^2=4, valency-2, C6
G73 = G72 OR P72 AND G32           '5dt, distance=2^2=4, valency-2, C7

S0 = P00                           '1dt
S1 = P10 XOR G00                   '2dt
S2 = P20 XOR G11                   '4dt
S3 = P30 XOR G22                   '4dt
S4 = P40 XOR G32                   '6dt
S5 = P50 XOR G43                   '6dt
S6 = P60 XOR G53                   '6dt
S7 = P70 XOR G63                   '6dt

8-bit Brent-Kung adder, valency-2:

P00 = A0 XOR B0              '1dt, S0
G00 = A0 AND B0              '1dt, C0
P10 = A1 XOR B1              '1dt
G10 = A1 AND B1              '1dt
P20 = A2 XOR B2              '1dt
G20 = A2 AND B2              '1dt
P30 = A3 XOR B3              '1dt
G30 = A3 AND B3              '1dt
P40 = A4 XOR B4              '1dt
G40 = A4 AND B4              '1dt
P50 = A5 XOR B5              '1dt
G50 = A5 AND B5              '1dt
P60 = A6 XOR B6              '1dt
G60 = A6 AND B6              '1dt
P70 = A7 XOR B7              '1dt
G70 = A7 AND B7              '1dt

G11 = G10 OR P10 AND G00     '3dt, C1
G21 = G20 OR P20 AND G11     '3dt, C2
P31 = P30 AND P20            '2dt 
G31 = G30 OR P30 AND G20     '3dt
P51 = P50 AND P40            '2dt  
G51 = G50 OR P50 AND G40     '3dt
P71 = P70 AND P60            '2dt  
G71 = G70 OR P70 AND G60     '3dt

G32 = G31 OR P31 AND G11     '5dt, C3
P72 = P71 AND P51            '3dt 
G72 = G71 OR P71 AND G51     '5dt  

G53 = G51 OR P51 AND G32     '7dt, C5
G73 = G72 OR P72 AND G32     '7dt, C7, Cout

G44 = G40 OR P40 AND G32     '7dt, C4
G64 = G60 OR P60 AND G53     '9dt, C6

S0 = P00                     '1dt   
S1 = P10 XOR G00             '2dt
S2 = P20 XOR G11             '4dt
S3 = P30 XOR G21             '4dt
S4 = P40 XOR G32             '6dt
S5 = P50 XOR G44             '8dt
S6 = P60 XOR G53             '8dt 
S7 = P70 XOR G64            '10dt

References edit

^ ^a ^b Brent, Richard Peirce; Kung, Hsiang Te (March 1982) [June 1979]. "A Regular Layout for Parallel Adders". IEEE Transactions on Computers. C-31 (3). Department of Computer Sciences, Carnegie-Mellon University, USA: 260–264. doi:10.1109/TC.1982.1675982. ISSN 0018-9340. S2CID 17348212. CMS-CS-79-131. Archived from the original on September 24, 2017.
^ Alexander, Jonathan (2004). "VHDL Design Tips and Low Power Design Techniques". Retrieved 2018-04-21.
^ ^a ^b Pointer, Robey (2012-11-14). "How to add numbers (part 2)". robey.lag.net. Archived from the original on 2018-04-21. Retrieved 2018-04-21.

External links edit

Archived 4 February 2020 at the Wayback Machine

[Brent-Kung_1982-1] Brent, Richard Peirce; Kung, Hsiang Te (March 1982) [June 1979]. "A Regular Layout for Parallel Adders". IEEE Transactions on Computers. C-31 (3). Department of Computer Sciences, Carnegie-Mellon University, USA: 260–264. doi:10.1109/TC.1982.1675982. ISSN 0018-9340. S2CID 17348212. CMS-CS-79-131. Archived from the original on September 24, 2017.

[Alexander_2004-2] Alexander, Jonathan (2004). "VHDL Design Tips and Low Power Design Techniques". Retrieved 2018-04-21.

[Robey_2012-3] Pointer, Robey (2012-11-14). "How to add numbers (part 2)". robey.lag.net. Archived from the original on 2018-04-21. Retrieved 2018-04-21.

[1]

[2]

[3]