Brent-Kung Adder in Verilog: Parallel-Prefix Carry Tree

// 8-bit Brent-Kung parallel-prefix adder with explicit black/gray cell logic
module bk_adder8(
  input  [7:0] a,
  input  [7:0] b,
  input        cin,
  output [7:0] sum,
  output       cout
);
  wire [7:0] g = a & b;   // bit generate
  wire [7:0] p = a ^ b;   // bit propagate

  // ---- Forward reduction tree (black cells) ----
  wire g1  = g[1] | (p[1]&g[0]);  wire p1  = p[1]&p[0];   // [1:0]
  wire g3a = g[3] | (p[3]&g[2]);  wire p3a = p[3]&p[2];   // [3:2]
  wire g5a = g[5] | (p[5]&g[4]);  wire p5a = p[5]&p[4];   // [5:4]
  wire g7a = g[7] | (p[7]&g[6]);  wire p7a = p[7]&p[6];   // [7:6]
  wire g3f = g3a | (p3a&g1);      wire p3f = p3a&p1;      // [3:0]
  wire g7b = g7a | (p7a&g5a);     wire p7b = p7a&p5a;     // [7:4]
  wire g7f = g7b | (p7b&g3f);     wire p7f = p7b&p3f;     // [7:0]

  // ---- Backward prefix tree (black cells) ----
  wire g5f = g5a   | (p5a&g3f);   wire p5f = p5a&p3f;     // [5:0]
  wire g2f = g[2]  | (p[2]&g1);   wire p2f = p[2]&p1;     // [2:0]
  wire g4f = g[4]  | (p[4]&g3f);  wire p4f = p[4]&p3f;    // [4:0]
  wire g6f = g[6]  | (p[6]&g5f);  wire p6f = p[6]&p5f;    // [6:0]

  wire [7:0] G = {g7f, g6f, g5f, g4f, g3f, g2f, g1, g[0]};
  wire [7:0] P = {p7f, p6f, p5f, p4f, p3f, p2f, p1, p[0]};

  wire [8:0] c;
  assign c[0] = cin;
  genvar i;
  generate
    for (i=0;i<8;i=i+1) begin : carry_gen
      assign c[i+1] = G[i] | (P[i] & cin);   // gray cell injects cin
    end
  endgenerate

  assign sum  = p ^ c[7:0];
  assign cout = c[8];
endmodule

module tb;
  reg  [7:0] a, b;
  reg        cin;
  wire [7:0] sum;
  wire       cout;
  integer    ia, ib, ic;
  reg  [8:0] ref;
  integer    fails;

  bk_adder8 dut(.a(a), .b(b), .cin(cin), .sum(sum), .cout(cout));

  initial begin
    fails = 0;
    for (ia=0; ia<256; ia=ia+1)
      for (ib=0; ib<256; ib=ib+1)
        for (ic=0; ic<2; ic=ic+1) begin
          a = ia[7:0]; b = ib[7:0]; cin = ic[0];
          #1;
          ref = a + b + cin;
          if ({cout,sum} !== ref) begin
            fails = fails + 1;
            $display("FAIL a=%0d b=%0d cin=%0d got=%0d exp=%0d",
                     a, b, cin, {cout,sum}, ref);
          end
        end
    a=8'hFF; b=8'h01; cin=1'b0; #1;
    if ({cout,sum}===9'd256) $display("PASS 255+1   -> cout=%0d sum=%0d", cout, sum);
    else begin fails=fails+1; $display("FAIL 255+1"); end
    a=8'hFF; b=8'hFF; cin=1'b1; #1;
    if ({cout,sum}===9'd511) $display("PASS 255+255+1 -> %0d", {cout,sum});
    else begin fails=fails+1; $display("FAIL 255+255+1"); end

    if (fails==0) $display("PASS exhaustive 131072 vectors, 0 mismatches");
    else          $display("FAIL total mismatches=%0d", fails);
    if (fails==0) $display("ALL TESTS PASSED");
    $finish;
  end
endmodule

PASS 255+1   -> cout=1 sum=0
PASS 255+255+1 -> 511
PASS exhaustive 131072 vectors, 0 mismatches
ALL TESTS PASSED
The log shows an exhaustive sweep over every 8-bit a, b, and both cin values with zero mismatches, plus named corner cases (255+1 and 255+255+1 exercising the full carry chain). Because the reference is an independent a + b + cin, any wrong prefix cell would print a FAIL line.

This version builds the Brent-Kung prefix network algorithmically from the WIDTH parameter (a power of two), so the same RTL scales to 8, 16, or 32 bits. The forward and backward passes use the standard Brent-Kung index schedule. The testbench sweeps the 16-bit instance with coprime strides for wide, deterministic coverage.
bk_adder.vSimulation log
// Parameterized Brent-Kung adder (WIDTH must be a power of two).
module bk_adder #(parameter WIDTH = 16) (
  input  [WIDTH-1:0] a,
  input  [WIDTH-1:0] b,
  input              cin,
  output [WIDTH-1:0] sum,
  output             cout
);
  integer d, i;
  reg [WIDTH-1:0] G, P;
  reg [WIDTH:0]   carry;
  reg [WIDTH-1:0] s;
  reg [WIDTH-1:0] pini;

  always @(*) begin
    for (i=0; i<WIDTH; i=i+1) begin
      G[i] = a[i] & b[i];
      P[i] = a[i] ^ b[i];
    end
    pini = a ^ b;

    d = 1;
    while (d < WIDTH) begin
      i = 2*d - 1;
      while (i < WIDTH) begin
        G[i] = G[i] | (P[i] & G[i-d]);
        P[i] = P[i] & P[i-d];
        i = i + 2*d;
      end
      d = d * 2;
    end

    d = WIDTH/4;
    while (d >= 1) begin
      i = 3*d - 1;
      while (i < WIDTH) begin
        G[i] = G[i] | (P[i] & G[i-d]);
        P[i] = P[i] & P[i-d];
        i = i + 2*d;
      end
      d = d / 2;
    end

    carry[0] = cin;
    for (i=0; i<WIDTH; i=i+1)
      carry[i+1] = G[i] | (P[i] & cin);
    for (i=0; i<WIDTH; i=i+1)
      s[i] = pini[i] ^ carry[i];
  end

  assign sum  = s;
  assign cout = carry[WIDTH];
endmodule

module tb;
  localparam W = 16;
  reg  [W-1:0] a, b;
  reg          cin;
  wire [W-1:0] sum;
  wire         cout;
  integer      ia, ib, ic;
  reg  [W:0]   ref;
  integer      fails, checks;

  bk_adder #(.WIDTH(W)) dut(.a(a), .b(b), .cin(cin), .sum(sum), .cout(cout));

  initial begin
    fails = 0; checks = 0;
    for (ia=0; ia<65536; ia=ia+257)
      for (ib=0; ib<65536; ib=ib+251)
        for (ic=0; ic<2; ic=ic+1) begin
          a = ia[W-1:0]; b = ib[W-1:0]; cin = ic[0];
          #1;
          ref = a + b + cin;
          checks = checks + 1;
          if ({cout,sum} !== ref) begin
            fails = fails + 1;
            $display("FAIL a=%0d b=%0d cin=%0d got=%0d exp=%0d",
                     a, b, cin, {cout,sum}, ref);
          end
        end
    a=16'hFFFF; b=16'h0001; cin=1'b0; #1;
    if ({cout,sum}===17'd65536) $display("PASS 65535+1 ripple -> cout=%0d", cout);
    else begin fails=fails+1; $display("FAIL 65535+1"); end
    a=16'hFFFF; b=16'hFFFF; cin=1'b1; #1;
    if ({cout,sum}===17'd131071) $display("PASS 65535+65535+1 -> %0d", {cout,sum});
    else begin fails=fails+1; $display("FAIL 65535+65535+1"); end
    a=16'hAAAA; b=16'h5555; cin=1'b0; #1;
    if ({cout,sum}===17'd65535) $display("PASS 0xAAAA+0x5555 -> %0d", sum);
    else begin fails=fails+1; $display("FAIL alt-bits"); end

    $display("PASS swept %0d vectors with 0 mismatches", checks);
    if (fails==0) $display("ALL TESTS PASSED");
    else          $display("FAIL total mismatches=%0d", fails);
    $finish;
  end
endmodule
PASS 65535+1 ripple -> cout=1
PASS 65535+65535+1 -> 131071
PASS 0xAAAA+0x5555 -> 65535
PASS swept 134144 vectors with 0 mismatches
ALL TESTS PASSED
The log reports more than 134,000 verified 16-bit vectors with zero mismatches, plus corner cases including the all-ones ripple (65535+1) and alternating bit patterns. The deterministic coprime strides guarantee the same vectors on every run, so the PASS lines are reproducible evidence that the parameterized prefix schedule is correct.

How the Brent-Kung prefix tree works
Define the group pair (G, P) for a span of bits. The associative dot operator combines a higher span with a lower span:
(G, P) ° (G', P') = ( G | (P & G'),  P & P' )
A cell that produces both a new G and a new P is a black cell; a cell that only needs the generate output (typically where a span already reaches bit 0) is a gray cell. Brent-Kung computes the prefix in two phases:
Forward reduction (like the up-sweep of a scan): at distance d = 1, 2, 4, …, node i absorbs node i-d. After this phase only positions 0, 1, 3, 7, 15, … hold a full prefix down to bit 0.
Backward prefix (the down-sweep): at decreasing distances it fills in the remaining positions by combining each un-finished node with the nearest completed prefix below it.
Once every position i holds the group generate/propagate for the span [i:0], the carry into bit i+1 is carry[i+1] = G[i] | (P[i] & cin), and the sum is simply sum[i] = p[i] ^ carry[i] with carry[0] = cin.
Timing, area, and the log-depth win
A ripple-carry adder has a critical path of O(N) gate delays because each full adder waits for the carry below it. Brent-Kung breaks that chain: the prefix tree has depth 2·log2(N) - 2 cell stages, so a 16-bit adder settles in about 6 prefix stages instead of 16 carry hops. The trade-off versus Kogge-Stone is fan-out and wiring: Brent-Kung reuses prefix nodes aggressively, so it has far fewer cells and shorter wires (better area and power), at the cost of two extra logic levels and higher fan-out on the shared nodes.
Brent-Kung vs Kogge-Stone
Both are parallel-prefix adders built from the same dot operator; they differ only in the shape of the prefix tree.
Kogge-Stone: minimum logic depth (log2(N) stages) and fan-out of 2, but it computes a prefix at every position in every stage, so it needs the most cells and the most wiring — the fastest but largest/most power-hungry choice.
Brent-Kung: roughly double the depth (2·log2(N) - 2) but far fewer cells and wires because of the forward/backward reuse — the most area- and power-efficient choice.
In practice designers often use hybrids (Han-Carlson, Sklansky, Ladner-Fischer) that sit between these two extremes to balance depth against fan-out and wiring.
Common mistakes
Forgetting the carry-in path. The prefix tree computes group generate/propagate; cin must be injected at the output with a gray cell (G[i] | (P[i] & cin)) or folded into column 0. Dropping it makes the adder correct only for cin = 0.
Using g = a | b. Bit generate is AND (a & b); the propagate used for the sum is XOR (a ^ b). Using OR for propagate also works for the carry but then sum = p ^ carry is wrong — keep propagate as XOR.
Wrong prefix index schedule. The backward pass is the part most people get wrong. Verify it by self-checking against a + b + cin over many vectors, exactly as the testbenches here do.
Non-power-of-two width in the parameterized version: the d = 1,2,4,… schedule assumes WIDTH is a power of two. For arbitrary widths, pad to the next power of two or use a width-generic prefix formulation.
Synthesis notes
Both modules are purely combinational and synthesizable. The parameterized version uses an always @(*) block with while/for loops over constant bounds; synthesis unrolls these at elaboration time into the same fixed prefix network as the hand-written version — there is no loop or state in hardware. In-place updates of the G/P arrays are safe because each stage only reads nodes finalized in an earlier stage. For a real datapath, most teams let the synthesizer infer the adder from a + b and pick the prefix structure via timing constraints; writing the tree explicitly is mainly for study, custom cells, or when you must lock the micro-architecture.
FAQ
How many stages does a Brent-Kung adder have? About 2·log2(N) - 2 prefix stages — for N=16 that is 6 stages, versus log2(16)=4 for Kogge-Stone.
Is Brent-Kung faster than ripple-carry? Yes — logarithmic depth instead of linear, so it scales much better as width grows, at the cost of extra prefix cells.
Why pick Brent-Kung over Kogge-Stone? When area, wiring, and power matter more than the last bit of speed; Brent-Kung uses far fewer cells and shorter interconnect.
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