threshold-prefix-xor

4-bit parallel prefix XOR (running parity). Computes cumulative XOR from MSB to each position. Essential for parity-based error detection.

Circuit

    x3      x2      x1      x0
     │       │       │       │
     ▼       │       │       │
   ┌───┐     │       │       │
   │y3 │     │       │       │
   │=x3│     │       │       │
   └───┘     ▼       │       │
     │     ┌─────┐   │       │
     └────►│ XOR │   │       │
           │ y2  │   │       │
           └─────┘   ▼       │
             │     ┌─────┐   │
             └────►│ XOR │   │
                   │ y1  │   │
                   └─────┘   ▼
                     │     ┌─────┐
                     └────►│ XOR │
                           │ y0  │
                           └─────┘

Function

prefix_xor(x3, x2, x1, x0) -> (y3, y2, y1, y0)

y3 = x3
y2 = x3 XOR x2
y1 = x3 XOR x2 XOR x1
y0 = x3 XOR x2 XOR x1 XOR x0  (full parity)

Each output yi is the XOR (parity) of all inputs from x3 down to xi.

Truth Table (selected)

x3 x2 x1 x0	y3 y2 y1 y0	y0 = parity
0 0 0 0	0 0 0 0	even (0)
0 0 0 1	0 0 0 1	odd (1)
0 0 1 1	0 0 1 0	even (0)
0 1 1 1	0 1 0 1	odd (1)
1 1 1 1	1 0 1 0	even (0)
1 0 1 0	1 1 0 0	even (0)
1 1 0 0	1 0 0 0	even (0)

Mechanism

Unlike prefix-AND and prefix-OR, prefix-XOR requires sequential XOR gates because XOR is not a simple threshold function.

Architecture: Chain of 3 XOR gates (each XOR = 3 neurons)

Stage	Computes	Neurons
1	y3 = x3 (passthrough)	0
2	y2 = y3 XOR x2	3
3	y1 = y2 XOR x1	3
4	y0 = y1 XOR x0	3

Parameters

Inputs	4
Outputs	4
Neurons	9
Layers	6
Parameters	27
Magnitude	30

Applications

• Running parity: y_i gives parity of bits from MSB to position i
• Error detection: Final y0 is overall parity bit
• Gray code generation: Related to Gray code conversions
• Checksum computation: Partial checksums at each position

Usage

from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

def xor2(a, b, prefix):
    inp = torch.tensor([float(a), float(b)])
    or_out = int((inp @ w[f'{prefix}.or.weight'].T + w[f'{prefix}.or.bias'] >= 0).item())
    nand_out = int((inp @ w[f'{prefix}.nand.weight'].T + w[f'{prefix}.nand.bias'] >= 0).item())
    l1 = torch.tensor([float(or_out), float(nand_out)])
    return int((l1 @ w[f'{prefix}.and.weight'].T + w[f'{prefix}.and.bias'] >= 0).item())

def prefix_xor(x3, x2, x1, x0):
    y3 = x3
    y2 = xor2(y3, x2, 'xor2')
    y1 = xor2(y2, x1, 'xor1')
    y0 = xor2(y1, x0, 'xor0')
    return y3, y2, y1, y0

print(prefix_xor(1, 1, 1, 1))  # (1, 0, 1, 0) - even parity
print(prefix_xor(1, 0, 0, 0))  # (1, 1, 1, 1) - odd parity

License

MIT