phanerozoic / threshold-ladner-fischer

threshold-ladner-fischer

4-bit Ladner-Fischer parallel prefix adder. A parameterized adder family that provides tunable trade-offs between circuit depth and fanout.

Function

S[3:0], Cout = A[3:0] + B[3:0] + Cin

Ladner-Fischer Structure (4-bit)

       G3,P3    G2,P2    G1,P1    G0,P0    Cin
         │        │        │        │       │
         │        │        │        │       │
Level 1  ●────────┤        ●────────┤       │   ← Pairwise combination
         │        │        │        │       │
         │        │        │        │       │
Level 2  ●────────●────────┴────────┘       │   ← Variable fanout level
         │        │                         │
         │        │                         │
       G3:0     G2:0     G1:0     G0       │
         │        │        │        │       │
         ▼        ▼        ▼        ▼       │
        XOR      XOR      XOR      XOR ─────┘
         │        │        │        │
         ▼        ▼        ▼        ▼
       Cout      S3       S2       S1       S0

Design Philosophy

Ladner-Fischer defines a parameterized family of parallel prefix networks. The parameter controls the trade-off:

Fanout ◄────────────────────────────────► Depth
   │                                        │
   │    Brent-Kung ─── Ladner-Fischer ─── Sklansky
   │         │               │               │
   │      Low fanout    Configurable    Min depth
   │      Max depth      Trade-off      Max fanout
   ▼                                        ▼

The key insight: at each level, you can choose how many prefix cells to include. More cells = lower depth but higher fanout.

Parallel Prefix Operation

(G_high, P_high) ○ (G_low, P_low) = (G_high + P_high·G_low, P_high·P_low)

• G (Generate) : Position i generates a carry if A_i AND B_i
• P (Propagate) : Position i propagates a carry if A_i XOR B_i
• G_i:j : Combined generate for positions i down to j

Truth Table (Examples)

Threshold Implementation

Layer 0: Generate/Propagate Computation

G_i = A_i AND B_i
    weights: [A_i: 1.0, B_i: 1.0], bias: -2.0

P_i = A_i XOR B_i
    OR:   [A_i: 1.0, B_i: 1.0], bias: -1.0
    NAND: [A_i: -1.0, B_i: -1.0], bias: 1.0
    AND:  [OR: 1.0, NAND: 1.0], bias: -2.0

Layers 1-2: Prefix Network

Combines G,P pairs according to the Ladner-Fischer pattern with chosen fanout parameter.

Parameters

Usage

from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

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

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

    # Level 1: span 1
    g10 = g[1] | (p[1] & g[0])
    p10 = p[1] & p[0]
    g32 = g[3] | (p[3] & g[2])
    p32 = p[3] & p[2]

    # Level 2: span 2
    g30 = g32 | (p32 & g10)
    p30 = p32 & p10
    g20 = g[2] | (p[2] & g10)

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

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

    return s3, s2, s1, s0, c3

# Verify: 7 + 5 = 12
result = ladner_fischer_add(0,1,1,1, 0,1,0,1, 0)
print(f"7 + 5 = {result[4]*16 + result[0]*8 + result[1]*4 + result[2]*2 + result[3]}")

Verification

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

Files

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

References

• Ladner, R. E., & Fischer, M. J. (1980). "Parallel Prefix Computation"
• Journal of the ACM, Vol. 27, No. 4, pp. 831-838

License

MIT