README.md

---
license: mit
tags:
- pytorch
- safetensors
- threshold-logic
- neuromorphic
- arithmetic
- parallel-prefix
- adder
---

# threshold-han-carlson

4-bit Han-Carlson parallel prefix adder. Hybrid design combining Kogge-Stone's logarithmic depth with Brent-Kung's reduced wiring complexity.

## Function

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

Computes 4-bit addition with carry-in/carry-out using parallel prefix computation.

## Han-Carlson Structure (4-bit)

```
       G3,P3    G2,P2    G1,P1    G0,P0    Cin
         │        │        │        │       │
         │        │        │        │       │
Level 1  ●────────┘        ●────────┘       │   ← Odd-position prefix (like Brent-Kung)
         │                 │                │
         │                 │                │
Level 2  ●─────────────────┘                │   ← Kogge-Stone style merge
         │                                  │
         │                                  │
Level 3  └────────●                         │   ← Back-propagate to even positions
                  │                         │
                  │                         │
       G3:0     G2:0     G1:0     G0       │
         │        │        │        │       │
         ▼        ▼        ▼        ▼       │
    ┌────┴────┬───┴───┬────┴────┬───┴───────┘
    │         │       │         │
   XOR       XOR     XOR       XOR
    │         │       │         │
    ▼         ▼       ▼         ▼
  Cout       S3      S2        S1        S0
```

## Design Philosophy

Han-Carlson is a **hybrid parallel prefix adder** that interpolates between two extremes:

| Property | Kogge-Stone | Han-Carlson | Brent-Kung |
|----------|-------------|-------------|------------|
| Depth | log₂(n) | log₂(n) + 1 | 2·log₂(n) - 2 |
| Prefix cells | n·log₂(n) - n + 1 | (n/2)·log₂(n) | 2n - 2 - log₂(n) |
| Wiring tracks | High | Medium | Low |
| Fanout | Uniform | Mixed | Low |

For n=4: Depth=3, Cells=4, offering the best balance for small adders.

## Parallel Prefix Operation

The fundamental operation combines (Generate, Propagate) pairs:

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

Where:
- G_i = A_i AND B_i (generate carry)
- P_i = A_i XOR B_i (propagate carry)

## Truth Table (Examples)

| A (dec) | B (dec) | Cin | S (dec) | Cout | Equation |
|---------|---------|-----|---------|------|----------|
| 0 | 0 | 0 | 0 | 0 | 0+0+0=0 |
| 5 | 3 | 0 | 8 | 0 | 5+3+0=8 |
| 7 | 7 | 0 | 14 | 0 | 7+7+0=14 |
| 15 | 1 | 0 | 0 | 1 | 15+1+0=16 |
| 15 | 15 | 1 | 15 | 1 | 15+15+1=31 |

## Layer 0 Weights (Generate/Propagate)

Each bit position computes G and P from inputs:

```
G_i: weights[A_i]=1, weights[B_i]=1, bias=-2  (AND gate)
P_i: XOR decomposition using OR/NAND/AND
```

## Parameters

| | |
|---|---|
| Inputs | 9 (A[3:0], B[3:0], Cin) |
| Outputs | 5 (S[3:0], Cout) |
| Neurons | 32 |
| Layers | 5 |
| Parameters | 132 |
| Magnitude | 56 |

## Usage

```python
from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

def han_carlson_add(a3, a2, a1, a0, b3, b2, b1, b0, cin):
    # Generate and Propagate
    g = [a0 & b0, a1 & b1, a2 & b2, a3 & b3]
    p = [a0 ^ b0, a1 ^ b1, a2 ^ b2, a3 ^ b3]

    # Level 1: odd positions
    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: top merge
    g30 = g32 | (p32 & g10)

    # Level 3: back-propagate
    g20 = g[2] | (p[2] & g10)

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

    return p[3]^c2, p[2]^c1, p[1]^c0, p[0]^cin, c3

# Example: 5 + 3 = 8
s3, s2, s1, s0, cout = han_carlson_add(0,1,0,1, 0,0,1,1, 0)
print(f"Result: {cout*16 + s3*8 + s2*4 + s1*2 + s0}")  # 8
```

## Verification

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

## Files

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

## References

- Han, T., & Carlson, D. A. (1987). "Fast area-efficient VLSI adders"
- Parallel prefix adders are fundamental to high-performance ALU design

## License

MIT