How a Brent-Kung adder works: an 8-bit parallel prefix adder

A Brent-Kung adder finds every carry with a parallel prefix tree that uses as few cells as possible: an up-sweep combines generate and propagate signals into spans of 2, 4 and 8 bits, and a down-sweep fills in the carries in between. This live 8-bit one uses 12 prefix cells where a Kogge-Stone adder would need 18, at the cost of more levels.

Each bit makes g = A AND B (generate) and p = A XOR B (propagate), and Cin joins bit 0 as G0 = g0 OR (p0 AND Cin). A gray cell combines a high group with the one below it, G = Gh OR (Ph AND Gl); a black cell also passes on P = Ph AND Pl. The up-sweep pairs neighbours into spans 1:0, 3:2, 5:4 and 7:6, then 3:0 and 7:4, then 7:0, which is the carry out. That leaves the carries at bits 2, 4, 5 and 6, and the down-sweep supplies them: G5:0 from G5:4 and G3:0, then G2:0, G4:0 and G6:0, each from its own bit and the span just below it. Richard Brent and H. T. Kung published the scheme in 1982. Compared with the Kogge-Stone adder, which computes every span at every level and finishes in log2(n) levels, Brent-Kung uses about 2n cells instead of n log2(n), with shorter wires, but its longest carry path is about twice as deep (in this 8-bit version it passes through 5 cells, against 4 for a Kogge-Stone adder with the same Cin cell), which is why it suits designs where area and power matter more than the last bit of speed. A ripple-carry adder sits at the other extreme, with no tree at all. 2^17 input rows are too many to sweep on every build, so before the page is built 3,160 additions are checked on every sum bit and Cout: each value of A with B = 0, 1, A, 255 - A and 255 and both carries in, plus 600 seeded random pairs.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

8× XOR: propagate p_i = A_i XOR B_i
8× AND: generate g_i = A_i AND B_i
4× black cell (AND + OR, plus an AND): up-sweep spans 3:2, 5:4, 7:6 and 7:4
8× gray cell (AND + OR): G0 with Cin, G1:0, G3:0 and G7:0 (up-sweep), G5:0, G2:0, G4:0 and G6:0 (down-sweep)
8× XOR: sums S_i = p_i XOR c_i

Step by step

Place inputs A7 to A0, B7 to B0 and Cin, and probes S7 to S0 and Cout.
For each bit make p = A XOR B and g = A AND B, and fold Cin into bit 0: G0 = g0 + p0 Cin.
Up-sweep: G1:0, then the pairs 3:2, 5:4, 7:6; then G3:0 = G3:2 + P3:2 G1:0 and the span 7:4; then G7:0, the carry out.
Down-sweep: G5:0 = G5:4 + P5:4 G3:0, G2:0 = g2 + p2 G1:0, G4:0 = g4 + p4 G3:0, G6:0 = g6 + p6 G5:0.
Sums: S_i = p_i XOR c_i, where c0 = Cin and c(i+1) = G(i:0). Try 01111111 + 00000001: every carry is set.

Cells and depth, 8 bits

Adder	Prefix cells	Longest carry path	Depth grows like
Ripple-carry	none (a carry chain)	8 full-adder carries	n
Brent-Kung (this one)	12 (11 plus the Cin cell)	5 cells	about 2 log2(n)
Kogge-Stone	18 (17 plus the Cin cell)	4 cells	log2(n)

Cell counts include the extra gray cell that folds Cin into bit 0. For n bits, Brent-Kung needs 2n - 2 - log2(n) prefix cells and Kogge-Stone n log2(n) - n + 1, so the gap widens quickly: at 64 bits it is 120 cells against 321.

You can also read the full theory in the lesson on faster adders and carry lookahead. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter Hamming (7,4) code encoder and corrector traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder full adder using 4:1 multiplexers edge detector serial adder 4-bit carry-select adder 4-bit Kogge-Stone adder 4-bit carry-skip adder 4x4 Wallace tree multiplier 8-bit adder frequency divider (by 2, 4 and 3)switch debouncer (SR latch)3-bit Gray code counter Mealy machine (1011 detector)master-slave JK flip-flop (NAND)half subtractor from NOR gates 1-to-8 demultiplexer excess-3 to BCD code converter vending machine FSM 4-bit carry-save adder 3-bit synchronous counter (JK)CMOS transmission gate tri-state buffer (CMOS)2-to-1 mux from transmission gates mod-5 counter flip-flop conversion (JK to D)8-bit ALU decimal to BCD encoder BCD to decimal decoder 4-to-1 mux from 2-to-1 muxes XOR gate from NOR gates 4-bit LFSR 74LS138 decoder BCD subtractor 74181 ALU CMOS AOI gate (AOI21)D latch vs D flip-flop 74LS47 BCD to 7-segment decoder 74HC595 shift register 7400 quad NAND gate chip 7402 quad NOR gate chip 7404 hex inverter chip 7408 quad AND gate chip 7432 quad OR gate chip 7486 quad XOR gate chip 7474 dual D flip-flop 74HC165 shift register CD4017 decade counter 74LS283 4-bit adder 74LS90 decade counter 74HC161 4-bit counter 74HC151 8-to-1 multiplexer 74HC157 quad 2-to-1 multiplexer 74HC139 dual 2-to-4 decoder CD4511 BCD to 7-segment decoder 7492 divide-by-12 counter 7493 4-bit binary counter 74HC244 octal buffer Race-around condition (JK latch)74HC373 octal latch 74HC374 octal D flip-flop Turnstile state machine 1-to-2 demultiplexer half adder using 2:1 multiplexers register file (4 x 4-bit)digital PWM generator CD4013 dual D flip-flop 74LS76 dual JK flip-flop 7410 triple 3-input NAND chip 7411 triple 3-input AND chip 7420 dual 4-input NAND chip CD4011 quad 2-input NAND chip CD4001 quad 2-input NOR chip CD4081 quad 2-input AND chip CD4069 hex inverter chip 74HC164 8-bit shift register 7485 4-bit magnitude comparator 74HC125 quad tri-state buffer CD4040 12-stage binary counter CD4060 14-stage counter and oscillator 74LS193 4-bit up/down counter electronic dice circuit memory address register (MAR) and MDR hardware stack with a stack pointer direct-mapped cache 4x4 Dadda multiplier binary clock circuit

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the 8-bit Brent-Kung adder in the lab →

Frequently asked

How does a Brent-Kung adder work?

It computes generate and propagate for each bit, combines them in an up-sweep tree into spans of 2, 4, 8 and so on bits, and then fills in the missing carries with a down-sweep. Each sum bit is p XOR the carry into that bit.

What is the difference between Brent-Kung and Kogge-Stone adders?

Kogge-Stone computes every span at every level, so it is the fastest (log2(n) levels) but uses many cells and long wires. Brent-Kung uses about 2n cells and short wires but needs about twice as many levels. Other prefix adders, such as Sklansky, Ladner-Fischer and Han-Carlson, make other trade-offs.

Is a Brent-Kung adder faster than a ripple-carry adder?

For wide words, yes: its delay grows with log2(n) rather than with n. In this 8-bit version the longest carry path passes through 5 prefix cells, against 8 full-adder carries in a ripple adder.

Who invented the Brent-Kung adder?

Richard P. Brent and H. T. Kung, in a 1982 paper on a regular layout for parallel adders.