Lably
Skip to content

Kogge–Stone adder

Arithmetic logic circuit

  • 50 min read
  • 3 chapters

Related on Lably

Through Computing, Optimization problem and AND gate

Lab · Class 11NodeMCU & IoTLab · Class 11Smart Home IoT ProjectLab · Class 12Linear ProgrammingLab · Class 11Binary and Logic Gates

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

Sign in to keep reading

2 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard