threshold-kogge-stone

4-bit Kogge-Stone parallel prefix adder. Computes all carries in O(log n) depth using generate/propagate signals.

Circuit

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

Level 0 - Generate/Propagate:
  G_i = A_i AND B_i
  P_i = A_i XOR B_i

Level 1-3 - Parallel Prefix:
  (G_high, P_high) o (G_low, P_low) = (G_high + P_high·G_low, P_high·P_low)

Final:
  C_i = G_i:0 + P_i:0·Cin
  S_i = P_i XOR C_{i-1}

Kogge-Stone Structure (4-bit)

       G3,P3    G2,P2    G1,P1    G0,P0    Cin
         │        │        │        │       │
Level 1  ●────────●        ●────────●       │
         │        │        │        │       │
Level 2  ●────────┼────────●        │       │
         │        │        │        │       │
Level 3  ●────────┼────────┼────────●       │
         │        │        │        │       │
         ▼        ▼        ▼        ▼       │
       G3:0     G2:0     G1:0     G0      ──┘
         │        │        │        │
         ▼        ▼        ▼        ▼
       Cout      C2       C1       C0
                  │        │        │
                  ▼        ▼        ▼
                 S3       S2       S1       S0

Advantage Over Ripple Carry

Adder Type	Carry Depth	4-bit	64-bit
Ripple Carry	O(n)	4	64
Kogge-Stone	O(log n)	3	6

Kogge-Stone trades area for speed with maximum parallelism.

Truth Table (Examples)

A	B	Cin	S	Cout
0000	0000	0	0000	0
0101	0011	0	1000	0
1111	0001	0	0000	1
1111	1111	1	1111	1

Parameters

Inputs	9
Outputs	5
Neurons	36
Layers	5
Parameters	132
Magnitude	56

Usage

from safetensors.torch import load_file

w = load_file('model.safetensors')

# All 512 input combinations verified correct

Files

threshold-kogge-stone/
├── model.safetensors
├── create_safetensors.py
├── config.json
└── README.md

License

MIT