phanerozoic / threshold-brent-kung

threshold-brent-kung

4-bit Brent-Kung parallel prefix adder. Area-efficient variant that computes odd-position prefixes first, then back-propagates.

Circuit

Inputs: A[3:0], B[3:0], Cin (9 inputs)
Outputs: S[3:0], Cout (5 outputs)

Brent-Kung uses fewer prefix operators than Kogge-Stone
by only computing odd positions in the upward sweep.

Brent-Kung Structure (4-bit)

       G3,P3    G2,P2    G1,P1    G0,P0
         │        │        │        │
Level 1  ●────────┘        ●────────┘     (odd positions)
         │                 │
Level 2  ●─────────────────┘              (top)
         │
Level 3  └────────●                       (back-propagate)
                  │
       G3:0     G2:0     G1:0     G0

Comparison with Kogge-Stone

Brent-Kung trades some speed for reduced area and wiring complexity.

Truth Table (Examples)

Parameters

Threshold Implementation

Layer 0: Generate/Propagate

G_i = A_i AND B_i
    weights: [A_i: 1.0, B_i: 1.0]
    bias: -2.0
    fires when: 1·A_i + 1·B_i - 2 >= 0 → A_i + B_i >= 2

P_i = A_i XOR B_i (via OR-NAND-AND decomposition)
    OR:   [1.0, 1.0], bias=-1.0   → A_i + B_i >= 1
    NAND: [-1.0, -1.0], bias=1.0  → -(A_i + B_i) + 1 >= 0 → A_i + B_i <= 1
    AND:  [1.0, 1.0], bias=-2.0   → OR + NAND >= 2

Layers 1-3: Prefix Computation

Brent-Kung's upward sweep computes only odd-position prefixes, then back-propagates to even positions. This minimizes wiring at the cost of depth.

Usage

from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

def brent_kung_add(a3, a2, a1, a0, b3, b2, b1, b0, cin):
    a = [a0, a1, a2, a3]
    b = [b0, b1, b2, b3]

    # Generate and Propagate
    g = [a[i] & b[i] for i in range(4)]
    p = [a[i] ^ b[i] for i in range(4)]

    # Upward sweep (odd positions only)
    g10 = g[1] | (p[1] & g[0])
    p10 = p[1] & p[0]
    g32 = g[3] | (p[3] & g[2])
    p32 = p[3] & p[2]

    # Top level
    g30 = g32 | (p32 & g10)

    # Downward sweep (fill even positions)
    g20 = g[2] | (p[2] & g10)

    # Carries
    c0 = g[0] | (p[0] & cin)
    c1 = g10 | (p10 & cin)
    c2 = g20 | (p[2] & p10 & cin)
    c3 = g30 | (p32 & p10 & cin)

    # Sums
    s0 = p[0] ^ cin
    s1 = p[1] ^ c0
    s2 = p[2] ^ c1
    s3 = p[3] ^ c2

    return s3, s2, s1, s0, c3

# Example: 13 + 5 = 18 (overflow)
s3, s2, s1, s0, cout = brent_kung_add(1,1,0,1, 0,1,0,1, 0)
print(f"13 + 5 = {cout*16 + s3*8 + s2*4 + s1*2 + s0}")  # 18

Verification

All 512 input combinations (16 × 16 × 2) exhaustively verified correct.

Files

threshold-brent-kung/
├── model.safetensors    # Threshold network weights
├── create_safetensors.py # Weight generation + exhaustive verification
├── config.json          # Circuit metadata
└── README.md

References

• Brent, R. P., & Kung, H. T. (1982). "A Regular Layout for Parallel Adders"
• IEEE Transactions on Computers, C-31(3), pp. 260-264

License

MIT