How a Kogge-Stone adder works: a 4-bit parallel prefix adder

A Kogge-Stone adder computes every carry in parallel with a prefix tree: each bit makes a generate signal g = A AND B and a propagate signal p = A XOR B, and log2(n) levels of small cells combine them so that carry i is ready after only log2(n) cell delays. This live 4-bit one needs two prefix levels.

The cells all do one job. A gray cell takes a high group (Gh, Ph) and the group just below it (Gl) and outputs G = Gh OR (Ph AND Gl): the combined group generates a carry if its upper part does, or if the upper part propagates one that the lower part generates. A black cell also outputs P = Ph AND Pl, for use one level later. Level 1 joins neighbours (span 1), level 2 joins groups two apart (span 2), so with n bits the carries are done after log2(n) levels; Cin enters at bit 0 as G0 = g0 OR (p0 AND Cin). Peter Kogge and Harold Stone described the scheme in 1973. It is the fastest of the classic prefix adders because every cell drives at most two others, at the price of many cells and long wires; the carry-lookahead adder computes the same carries with wide flattened gates instead, and the ripple-carry adder waits for them one bit at a time. All 512 combinations of A, B and Cin are checked against real addition before the page is built.

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

4× XOR: propagate p_i = A_i XOR B_i
4× AND: generate g_i = A_i AND B_i
4× gray cell (AND + OR): G0 with Cin, G1:0 (level 1), G2:0 and G3:0 (level 2)
2× black cell (AND + OR, plus an AND): G2:1 with P2:1 = p2 p1, and G3:2 with P3:2 = p3 p2 (level 1)
4× XOR: sums S_i = p_i XOR c_i

Step by step

Place inputs A3 to A0, B3 to B0 and Cin, and probes S3 to S0 and Cout.
For each bit make p = A XOR B and g = A AND B.
Fold Cin into bit 0: G0 = g0 + p0 Cin. This is carry c1.
Level 1 (span 1): G1:0 = g1 + p1 G0 (carry c2), G2:1 = g2 + p2 g1, G3:2 = g3 + p3 g2, with P2:1 = p2 p1 and P3:2 = p3 p2.
Level 2 (span 2): G2:0 = G2:1 + P2:1 G0 (carry c3) and G3:0 = G3:2 + P3:2 G1:0 (Cout). Then S_i = p_i XOR c_i, with c0 = Cin.

Worked examples

A	B	Cin	g	p	Carries c4 c3 c2 c1	S	Cout
0011	0001	0	0001	0010	0011	0100	0
0101	0010	0	0000	0111	0000	0111	0
0111	0001	0	0001	0110	0111	1000	0
1000	1000	1	1000	0000	1000	0001	1
1111	0000	1	0000	1111	1111	0000	1

In the last row nothing generates but every bit propagates, so the carry-in runs all the way out: the prefix tree finds that in two levels, where a ripple-carry adder needs four full-adder delays. The circuit has 26 gates, against 20 for a 4-bit ripple-carry adder; at 64 bits the difference in delay is 6 levels against 64 stages.

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 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

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 4-bit Kogge-Stone adder in the lab →

Frequently asked

What is a Kogge-Stone adder?

A parallel prefix adder: every bit computes generate (A AND B) and propagate (A XOR B), and a tree of log2(n) levels of prefix cells combines them so that all carries are available at the same time. Each sum bit is then propagate XOR carry.

Why is the Kogge-Stone adder fast?

Its depth is log2(n) cell levels and every cell drives at most two others, so no carry waits for the bits below it one at a time. A 64-bit Kogge-Stone adder has 6 prefix levels where a ripple-carry adder has 64 full-adder stages.

What are black and gray cells?

A black cell combines two groups into both a group generate G = Gh + Ph Gl and a group propagate P = Ph Pl. A gray cell outputs only G, because nothing later needs that group's P. In this 4-bit adder there are 4 gray cells and 2 black cells.

What is the difference between Kogge-Stone and carry lookahead?

Both compute carries from generate and propagate signals. Classic carry lookahead expands each carry into one wide AND-OR expression per bit, which grows quickly with width; Kogge-Stone builds the same carries from small two-input cells in a tree of log2(n) levels, which scales to 32 or 64 bits.

What is the drawback of the Kogge-Stone adder?

Area and wiring: it uses about n log2(n) prefix cells and long wires that cross the whole width, so it costs more chip area and power than sparser prefix adders such as Brent-Kung, which trade a few more levels for far fewer cells.