Prefix adders combine per-bit pairs (g[i], p[i]) with one operator: (G, P) = (Ghi + Phi Glo, Phi Plo). Each node covers twice the bit range of its inputs.
Depth counts combine levels, and node count counts combine cells, excluding the N per-bit g and p gates. All formulas below assume N is a power of two.
Kogge-Stone combines every bit at every level: fastest and largest. Brent-Kung builds a forward tree and distributes back: smallest and slowest.
Sklansky sits between them with minimum depth but growing fanout. The table pins 16-bit values; the program below checks all four widths.
Tree | Depth (levels) | Nodes (N = 16) | Wiring character |
|---|---|---|---|
Kogge-Stone | log2 N = 4 | N log2 N - N + 1 = 49 | Dense tracks, maximum fanout 2. |
Brent-Kung | 2 log2 N - 1 = 7 | 2N - 2 - log2 N = 26 | Sparse tree plus distribution wires. |
Sklansky | log2 N = 4 | (N / 2) log2 N = 32 | Some nodes fan out to many later nodes. |
N = 16, L = log2(16) = 4
Kogge-Stone nodes = N x L - N + 1 = 16 x 4 - 16 + 1 = 64 - 16 + 1 = 49
Brent-Kung nodes = 2 x N - 2 - L = 32 - 2 - 4 = 26
Sklansky nodes = (N / 2) x L = 8 x 4 = 32
depths: Kogge-Stone 4, Brent-Kung 2 x 4 - 1 = 7, Sklansky 4The program checks the depth and node formulas for 4, 8, 16, and 32 bits. It then proves the prefix recurrence correct against plain integer addition.
The functional check is exhaustive at 8 bits: all 256 x 256 = 65536 operand pairs. At 16 bits it covers 2000 strided pairs.
import sys
def ceil_log2(n):
level = 0
span = 1
while span < n:
span = span * 2
level = level + 1
return level
def ks_nodes(n):
return n * ceil_log2(n) - n + 1
def bk_nodes(n):
return 2 * n - 2 - ceil_log2(n)
def sk_nodes(n):
return (n // 2) * ceil_log2(n)
def ks_depth(n):
return ceil_log2(n)
def bk_depth(n):
return 2 * ceil_log2(n) - 1
def sk_depth(n):
return ceil_log2(n)
widths = [4, 8, 16, 32]
want_depth = {4: (2, 3, 2), 8: (3, 5, 3), 16: (4, 7, 4), 32: (5, 9, 5)}
want_nodes = {4: (5, 4, 4), 8: (17, 11, 12), 16: (49, 26, 32), 32: (129, 57, 80)}
bad = 0
for w in widths:
got_d = (ks_depth(w), bk_depth(w), sk_depth(w))
got_n = (ks_nodes(w), bk_nodes(w), sk_nodes(w))
if got_d != want_depth[w]:
print("FAIL: depth at width " + str(w) + " got " + str(got_d))
bad = bad + 1
if got_n != want_nodes[w]:
print("FAIL: nodes at width " + str(w) + " got " + str(got_n))
bad = bad + 1
def prefix_add(a, b, n):
gen = [0] * n
prop = [0] * n
for i in range(n):
ai = (a >> i) & 1
bi = (b >> i) & 1
gen[i] = ai & bi
prop[i] = ai ^ bi
pbit = prop[:]
span = 1
while span < n:
nxt_g = gen[:]
nxt_p = prop[:]
for i in range(span, n):
nxt_g[i] = gen[i] | (prop[i] & gen[i - span])
nxt_p[i] = prop[i] & prop[i - span]
gen = nxt_g
prop = nxt_p
span = span * 2
carry = 0
total = 0
for i in range(n):
total = total | ((pbit[i] ^ carry) << i)
carry = gen[i]
return total
for a in range(256):
for b in range(256):
if prefix_add(a, b, 8) != ((a + b) & 255):
print("FAIL: 8-bit sum case a=" + str(a) + " b=" + str(b))
sys.exit(1)
for k in range(2000):
a = (k * 12345) & 65535
b = (k * 6789 + 1) & 65535
if prefix_add(a, b, 16) != ((a + b) & 65535):
print("FAIL: 16-bit sum case k=" + str(k))
sys.exit(1)
if bad != 0:
sys.exit(1)
print("PASS: depths and node counts agree on 4 widths and sums agree on 65536 plus 2000 cases")Log2 of 32 is 5. Kogge-Stone: depth 5, nodes 160 - 32 + 1 = 129. Brent-Kung: depth 9, nodes 64 - 2 - 5 = 57. Sklansky: depth 5, nodes 16 x 5 = 80.
It proves the doubling combine computes the true carry at every bit for width 8. The formulas for depth and nodes are checked separately against hand values.