# Kogge–Stone 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 :
In computing, the Kogge–Stone adder (KSA or KS) is a parallel prefix form of carry-lookahead adder. Other parallel prefix adders (PPA) include the Sklansky adder (SA), Brent–Kung adder (BKA), the Han–Carlson adder (HCA), the fastest known variation, the Lynch–Swartzlander spanning tree adder (STA), Knowles adder (KNA) and Beaumont-Smith adder (BSA) (like Sklansky adder (SA), radix-4).
The Kogge–Stone adder takes more area to implement than the Brent–Kung adder, but has a lower fan-out at each stage, which increases performance for typical CMOS process nodes. However, wiring congestion is often a problem for Kogge–Stone adders. The Lynch–Swartzlander design is smaller, has lower fan-out, and does not suffer from wiring congestion; however to be used the process node must support Manchester carry chain implementations. The general problem of optimizing parallel prefix adders is identical to the variable block size, multi level, carry-skip adder optimization problem, a solution of which is found in Thomas Lynch's thesis of 1996.

## Design

Like all carry-lookahead adders, the Kogge-Stone adder internally tracks "generate" and "propagate" bits for spans of bits. We start with 1-bit spans, where a single column in the addition generates a carry bit if both inputs are 1 (logical AND), and propagates a carry bit if exactly one input is 1 (logical XOR). Then adjacent spans are merged together to produce generate and propagate bits for wider spans.
Merging continues until generate bits are known for all spans ending at the least significant bit, at which point these may be used as the carry inputs to compute all the sum bits in parallel.
The difference between different carry-lookahead adder designs lies in how the span merging takes place. Most designs use log$_2$ n stages, doubling the width of the merged spans at each stage, but they differ in how spans which are not a power of two in size are divided into subspans. The Kogge–Stone design truncates the less-significant spans, and always uses full-width more-significant spans.
Starting with the 1-bit spans, all adjacent spans are merged to produce 2-bit spans. The least-significant span is treated specially: it is merged with the carry in to the addition, and it only produces a generate bit, as no propagation is possible. The next stage, each 2-bit wide span is merged with the preceding 2-bit span to produce a 4-bit span. This is with the exception of the least significant three spans. The least significant span has already been computed, while the next two are merged with the carry in and the previously computed least significant span respectively, producing generate bits for 3- and 4-bit spans including the carry in.
This process repeats, doubling the span widths at each stage, and with simplified computation of least-significant spans, until all of the desired generate bits are known.
Since each span is merged with at most two other spans in the next stage (one more significant and one less significant), fan-out is minimal. However, there is significant wiring congestion; in the second-last stage of a 64-bit adder, the most significant half of the spans to be merged each require separate generate and propagate signals from spans 16 bits away, necessitating 32 horizontal wires across the adder. The final stage is similar; although only generate bits are needed, 32 of them are required to cross the adder.

## Examples

An example of a 4-bit Kogge–Stone adder is shown in the diagram. Each vertical stage produces a "propagate" and a "generate" bit, as shown. The culminating generate bits (the carries) are produced in the last stage (vertically), and these bits are XOR'd with the initial propagate after the input (the red boxes) to produce the sum bits. E.g., the first (least-significant) sum bit is calculated by XORing the propagate in the farthest-right red box (a "1") with the carry-in (a "0"), producing a "1". The second bit is calculated by XORing the propagate in second box from the right (a "0") with C0 (a "0"), producing a "0".

### Binary, radix-2, 4-bit

4-bit Kogge-Stone adder, Radix-2, without Cin on Borland Turbo Basic 1.1:

### Binary, radix-2, 4-bit, with Cin

4-bit Kogge-Stone adder, Radix-2, with Cin:

### Binary, radix-2, 8-bit

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

### Binary, radix-4, 4-bit

4-bit PPA radix-4 (valency-2,3,4) adder (is 4-bit CLA radix-4 (valency-2,3,4) adder and 4-bit Sklansky radix-4 (valency-2,3,4) adder and 4-bit Kogge-Stone radix-4 (valency-2,3,4) adder and 4-bit Beaumont-Smith radix-4 (valency-2,3,4) adder):

### Binary, radix-4, 8-bit

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

### Binary, radix-8, 8-bit

8-bit radix-8 PPA valency-2,3,4,5,6,7,8 adder (is 8-bit CLA valency-2,3,4,5,6,7,8 adder and 8-bit Sklansky valency-2,3,4,5,6,7,8 adder and 8-bit Kogge-Stone valency-2,3,4,5,6,7,8 adder):

### Velocity of Kogge-Stone adders on noninverting Key gates

The Kogge-Stone adder concept was developed by Peter M. Kogge and Harold S. Stone, who published it in a seminal 1973 paper titled A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations.

## Enhancements

Enhancements to the original implementation include increasing the radix and sparsity of the adder. The radix of the adder refers to how many results from the previous level of computation are used to generate the next one. The original implementation uses radix-2, although it's possible to create radix-4 and higher. Doing so increases the power and delay of each stage, but reduces the number of required stages. In the so-called sparse Kogge–Stone adder (SKA) the sparsity of the adder refers to how many carry bits are generated by the carry-tree. Generating every carry bit is called sparsity-1, whereas generating every other is sparsity-2 and every fourth is sparsity-4. The resulting carries are then used as the carry-in inputs for much shorter ripple carry adders or some other adder design, which generates the final sum bits. Increasing sparsity reduces the total needed computation and can reduce the amount of routing congestion.
Above is an example of a Kogge–Stone adder with sparsity-4. Elements eliminated by sparsity shown marked with transparency. As shown, power and area of the carry generation is improved significantly, and routing congestion is substantially reduced. Each generated carry feeds a multiplexer for a carry select adder or the carry-in of a ripple carry adder.
16-bit Kogge-Stone adder valency-2 without Cin: