Kogge-Stone Adder in Verilog: Parallel-Prefix Fast Adder with Code

// Kogge-Stone parallel-prefix adder (fast adder), parameterized for N a power of 2.
// Flow: g = a&b, p = a^b, then a log2(N)-stage parallel-prefix network
// computes group generates (carries), and sum = p ^ carry_in_chain.
module kogge_stone_adder #(parameter N = 8) (
  input  [N-1:0] a,
  input  [N-1:0] b,
  input          cin,
  output [N-1:0] sum,
  output         cout
);
  // number of prefix stages = ceil(log2(N)) for N in {1,2,4,8,16,32,64}
  localparam STAGES = (N<=1) ? 1 : (N<=2) ? 1 : (N<=4) ? 2 :
                      (N<=8) ? 3 : (N<=16) ? 4 : (N<=32) ? 5 : 6;

  // bit-level generate / propagate
  wire [N-1:0] g0, p0;
  assign p0 = a ^ b;          // propagate: a XOR b
  assign g0 = a & b;          // generate : a AND b

  // one (G,P) vector per prefix stage boundary (stage 0 = inputs)
  wire [N-1:0] G [0:STAGES];
  wire [N-1:0] P [0:STAGES];

  genvar i, s;

  // Stage 0 init. Fold carry-in into column 0's generate so the prefix
  // network produces carries that already include cin.
  generate
    for (i = 0; i < N; i = i + 1) begin : init
      if (i == 0) begin : c0
        assign G[0][0] = g0[0] | (p0[0] & cin);
        assign P[0][0] = p0[0];
      end else begin : cn
        assign G[0][i] = g0[i];
        assign P[0][i] = p0[i];
      end
    end
  endgenerate

  // Parallel-prefix network. At stage s the span is D = 2^s.
  // Dot operator: (G,P) o (G',P') = (G | P&G', P & P').
  generate
    for (s = 0; s < STAGES; s = s + 1) begin : stage
      localparam integer D = (1 << s);
      for (i = 0; i < N; i = i + 1) begin : col
        if (i >= D) begin : upd
          assign G[s+1][i] = G[s][i] | (P[s][i] & G[s][i-D]);
          assign P[s+1][i] = P[s][i] & P[s][i-D];
        end else begin : pass
          assign G[s+1][i] = G[s][i];   // no operand below: carry straight up
          assign P[s+1][i] = P[s][i];
        end
      end
    end
  endgenerate

  // Carry into bit i is the group-generate of bits [0..i-1] (cin already folded).
  wire [N-1:0] carry_in;
  assign carry_in[0] = cin;
  generate
    for (i = 1; i < N; i = i + 1) begin : carries
      assign carry_in[i] = G[STAGES][i-1];
    end
  endgenerate

  assign sum  = p0 ^ carry_in;
  assign cout = G[STAGES][N-1];
endmodule

// ---------------------------------------------------------------------------
module tb;
  localparam N = 8;
  reg  [N-1:0] a, b;
  reg          cin;
  wire [N-1:0] sum;
  wire         cout;
  integer ai, bi, ci, errors;
  reg  [N:0] expected;

  kogge_stone_adder #(.N(N)) dut (.a(a), .b(b), .cin(cin), .sum(sum), .cout(cout));

  task check;
    input [N-1:0] ta;
    input [N-1:0] tbv;
    input         tci;
    reg   [N:0]   exp;
    begin
      a = ta; b = tbv; cin = tci; #1;
      exp = ta + tbv + tci;
      if ({cout, sum} === exp)
        $display("PASS  a=%3d b=%3d cin=%0d -> {cout,sum}=%3d", ta, tbv, tci, {cout, sum});
      else begin
        errors = errors + 1;
        $display("FAIL  a=%3d b=%3d cin=%0d got=%0d exp=%0d", ta, tbv, tci, {cout, sum}, exp);
      end
    end
  endtask

  initial begin
    errors = 0;
    // Directed corner cases
    check(8'h00, 8'h00, 1'b0);   // zero
    check(8'hFF, 8'hFF, 1'b1);   // max + max + 1 (worst-case carry)
    check(8'hFF, 8'h01, 1'b0);   // carry ripple across all bits
    check(8'hAA, 8'h55, 1'b0);   // alternating patterns
    check(8'h80, 8'h80, 1'b0);   // MSB + MSB

    // Deterministic sweep (step chosen coprime-ish to cover many values)
    for (ai = 0; ai < 256; ai = ai + 17)
      for (bi = 0; bi < 256; bi = bi + 13)
        for (ci = 0; ci < 2; ci = ci + 1) begin
          a = ai[7:0]; b = bi[7:0]; cin = ci[0]; #1;
          expected = a + b + cin;
          if ({cout, sum} !== expected) begin
            errors = errors + 1;
            $display("MISMATCH a=%0d b=%0d cin=%0d got=%0d exp=%0d",
                     a, b, cin, {cout, sum}, expected);
          end
        end

    if (errors == 0) $display("ALL PASS");
    else             $display("FAIL: %0d errors", errors);
    $finish;
  end
endmodule

PASS  a=  0 b=  0 cin=0 -> {cout,sum}=  0
PASS  a=255 b=255 cin=1 -> {cout,sum}=511
PASS  a=255 b=  1 cin=0 -> {cout,sum}=256
PASS  a=170 b= 85 cin=0 -> {cout,sum}=255
PASS  a=128 b=128 cin=0 -> {cout,sum}=256
ALL PASS
Simulate with iverilog -g2005 -o sim kogge_stone_adder8.v && vvp sim. Expected final line: ALL PASS.

Example 2: 16-bit instance + the (G,P) dot operator
The same module instanced at N = 16. The testbench also models the prefix dot operator as a Verilog function and exhaustively proves it is associative over all 64 input triples — the mathematical guarantee behind computing carries in parallel — before running the 16-bit adder vectors.
kogge_stone_adder16.vSimulation log
// Kogge-Stone adder: 16-bit instance, and an explicit look at the (G,P) prefix
// "dot" operator used to build the carry network. The dot operator is:
//     (G,P) o (Gp,Pp) = (G | (P & Gp),  P & Pp)
// It is associative, which is what lets the carries be computed in parallel.
module kogge_stone_adder #(parameter N = 16) (
  input  [N-1:0] a,
  input  [N-1:0] b,
  input          cin,
  output [N-1:0] sum,
  output         cout
);
  localparam STAGES = (N<=1) ? 1 : (N<=2) ? 1 : (N<=4) ? 2 :
                      (N<=8) ? 3 : (N<=16) ? 4 : (N<=32) ? 5 : 6;

  wire [N-1:0] g0, p0;
  assign p0 = a ^ b;
  assign g0 = a & b;

  wire [N-1:0] G [0:STAGES];
  wire [N-1:0] P [0:STAGES];

  genvar i, s;
  generate
    for (i = 0; i < N; i = i + 1) begin : init
      if (i == 0) begin : c0
        assign G[0][0] = g0[0] | (p0[0] & cin);
        assign P[0][0] = p0[0];
      end else begin : cn
        assign G[0][i] = g0[i];
        assign P[0][i] = p0[i];
      end
    end
    for (s = 0; s < STAGES; s = s + 1) begin : stage
      localparam integer D = (1 << s);
      for (i = 0; i < N; i = i + 1) begin : col
        if (i >= D) begin : upd
          assign G[s+1][i] = G[s][i] | (P[s][i] & G[s][i-D]);
          assign P[s+1][i] = P[s][i] & P[s][i-D];
        end else begin : pass
          assign G[s+1][i] = G[s][i];
          assign P[s+1][i] = P[s][i];
        end
      end
    end
  endgenerate

  wire [N-1:0] carry_in;
  assign carry_in[0] = cin;
  generate
    for (i = 1; i < N; i = i + 1) begin : carries
      assign carry_in[i] = G[STAGES][i-1];
    end
  endgenerate

  assign sum  = p0 ^ carry_in;
  assign cout = G[STAGES][N-1];
endmodule

// ---------------------------------------------------------------------------
module tb;
  localparam N = 16;
  reg  [N-1:0] a, b;
  reg          cin;
  wire [N-1:0] sum;
  wire         cout;
  integer k, errors;
  reg  [N:0] expected;

  kogge_stone_adder #(.N(N)) dut (.a(a), .b(b), .cin(cin), .sum(sum), .cout(cout));

  // Behavioural model of the dot operator, used to self-check associativity.
  // Pack {G,P} into a 2-bit value: bit1 = G, bit0 = P.
  function [1:0] dot;
    input [1:0] hi;   // more-significant group (G,P)
    input [1:0] lo;   // less-significant group (Gp,Pp)
    reg g, p, gp, pp;
    begin
      g = hi[1]; p = hi[0]; gp = lo[1]; pp = lo[0];
      dot = { (g | (p & gp)), (p & pp) };
    end
  endfunction

  integer x, y, z, assoc_err;

  initial begin
    errors = 0;

    // ---- Part A: prove the dot operator is associative over all 2-bit inputs.
    assoc_err = 0;
    for (x = 0; x < 4; x = x + 1)
      for (y = 0; y < 4; y = y + 1)
        for (z = 0; z < 4; z = z + 1)
          if (dot(dot(x[1:0], y[1:0]), z[1:0]) !== dot(x[1:0], dot(y[1:0], z[1:0])))
            assoc_err = assoc_err + 1;
    if (assoc_err == 0)
      $display("PASS  dot operator associative over all 64 input triples");
    else begin
      errors = errors + 1;
      $display("FAIL  dot operator NOT associative (%0d cases)", assoc_err);
    end

    // ---- Part B: 16-bit adder, directed corners + deterministic sweep.
    check(16'h0000, 16'h0000, 1'b0);
    check(16'hFFFF, 16'hFFFF, 1'b1);   // max + max + 1
    check(16'hFFFF, 16'h0001, 1'b0);   // full-width carry ripple
    check(16'hAAAA, 16'h5555, 1'b0);
    check(16'h1234, 16'hEDCB, 1'b1);   // 0x1234 + 0xEDCB + 1 = 0x10000

    for (k = 0; k < 65536; k = k + 2531) begin
      a = k[15:0]; b = (16'hFFFF - k[15:0]); cin = k[0]; #1;
      expected = a + b + cin;
      if ({cout, sum} !== expected) begin
        errors = errors + 1;
        $display("MISMATCH a=%0d b=%0d cin=%0d got=%0d exp=%0d",
                 a, b, cin, {cout, sum}, expected);
      end
    end

    if (errors == 0) $display("ALL PASS");
    else             $display("FAIL: %0d errors", errors);
    $finish;
  end

  task check;
    input [N-1:0] ta;
    input [N-1:0] tbv;
    input         tci;
    reg   [N:0]   exp;
    begin
      a = ta; b = tbv; cin = tci; #1;
      exp = ta + tbv + tci;
      if ({cout, sum} === exp)
        $display("PASS  a=%5d b=%5d cin=%0d -> {cout,sum}=%6d", ta, tbv, tci, {cout, sum});
      else begin
        errors = errors + 1;
        $display("FAIL  a=%5d b=%5d cin=%0d got=%0d exp=%0d", ta, tbv, tci, {cout, sum}, exp);
      end
    end
  endtask
endmodule
PASS  dot operator associative over all 64 input triples

PASS  a=    0 b=    0 cin=0 -> {cout,sum}=     0

PASS  a=65535 b=65535 cin=1 -> {cout,sum}=131071

PASS  a=65535 b=    1 cin=0 -> {cout,sum}= 65536

PASS  a=43690 b=21845 cin=0 -> {cout,sum}= 65535

PASS  a= 4660 b=60875 cin=1 -> {cout,sum}= 65536

ALL PASS
Run iverilog -g2005 -o sim kogge_stone_adder16.v && vvp sim; it prints the associativity check, the directed cases, then ALL PASS.
How the parallel-prefix carry works
Every adder reduces to one problem: find the carry into each bit. Define per-bit generate g=a&b (this bit makes a carry regardless of its input carry) and propagate p=a^b (this bit passes an incoming carry through). A group spanning bits can itself be described by a group (G,P) pair. Two adjacent groups merge with the associative dot operator (G,P) o (G',P') = (G | P&G', P&P'): the merged group generates a carry if the upper group generates one, or it propagates a carry that the lower group generated.
Kogge-Stone arranges these merges so that after stage s each column summarizes a span of 2s bits. After log2(N) stages, column i's G is the carry out of bit i. The sum is then simply the bit propagate XORed with the carry coming in: sum[i] = p[i] ^ carry_in[i].
Why the generate loops, and handling carry-in
The design uses arrays of wire vectors, wire [N-1:0] G [0:STAGES], one snapshot per stage, and nested generate/genvar loops to wire the network. This is pure structural elaboration: nothing is hardcoded to 8 bits, so changing the parameter N (to any power of two) rebuilds the whole prefix tree, with STAGES derived as ceil(log2N). A neat trick keeps carry-in clean: instead of threading cin through a separate path, we fold it into column 0's generate term, G[0][0] = g[0] | (p[0] & cin). The prefix network then produces carries that already include cin, and cout falls out as G[STAGES][N-1].
Synthesis, timing and area trade-offs
Kogge-Stone's appeal is low logic depth: only log2(N) prefix stages on the critical path (4 for 16-bit, 5 for 32-bit), each a simple AND-OR cell, versus N stages for a ripple-carry adder. It also keeps fan-out at every node low (ideally 2), which is good for high clock frequencies. The cost is wiring and area: it has the most prefix cells and the busiest interconnect of the common prefix adders, so it consumes more power and routing resources. Brent-Kung trades some speed back for far fewer cells; Sklansky cuts stages but suffers high fan-out. In real flows you usually let the synthesizer pick an architecture from a + operator, but knowing Kogge-Stone explains the structure it may choose for a timing-critical wide adder.
Common pitfalls and the interview angle
Watch the span condition: for column i at stage s, only merge when i >= 2^s; otherwise the column passes straight up unchanged. Off-by-one here silently corrupts upper carries, which is exactly why the testbench sweeps 0xFF + 0x01 and max+max+1 — the full-ripple and overflow corners. In interviews, be ready to: derive g/p; write the dot operator and state that it is associative (the reason parallel prefix is correct); contrast Kogge-Stone, Brent-Kung and Sklansky on depth, fan-out and area; and give the stage count as log2(N). A strong answer notes that the adder is purely combinational — registering operands and result is what sets the achievable clock period.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI Courses