threshold-prefix-and

4-bit parallel prefix AND operation. Computes running AND from MSB to each position. Used in leading-zero detection and all-ones prefixes.

Circuit

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

Function

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

y3 = x3
y2 = x3 AND x2
y1 = x3 AND x2 AND x1
y0 = x3 AND x2 AND x1 AND x0

Each output yi is the AND of all inputs from x3 down to xi.

Truth Table (selected)

x3 x2 x1 x0	y3 y2 y1 y0	Meaning
1 1 1 1	1 1 1 1	All ones
1 1 1 0	1 1 1 0	All ones except LSB
1 1 0 1	1 1 0 0	First zero at pos 1
1 0 1 1	1 0 0 0	First zero at pos 2
0 1 1 1	0 0 0 0	First zero at pos 3
1 1 0 0	1 1 0 0	Zeros in lower half
0 0 0 0	0 0 0 0	All zeros

Mechanism

Parallel implementation using threshold gates:

Each output requires detecting that ALL bits from x3 down to that position are 1:

Output	Condition	Weights	Bias
y3	x3 >= 1	[1,0,0,0]	-1
y2	x3 + x2 >= 2	[1,1,0,0]	-2
y1	x3 + x2 + x1 >= 3	[1,1,1,0]	-3
y0	x3 + x2 + x1 + x0 >= 4	[1,1,1,1]	-4

All computations are parallel (single layer)!

Architecture

Neuron	Weights [x3,x2,x1,x0]	Bias	Function
y3	[1, 0, 0, 0]	-1	x3
y2	[1, 1, 0, 0]	-2	x3 AND x2
y1	[1, 1, 1, 0]	-3	x3 AND x2 AND x1
y0	[1, 1, 1, 1]	-4	x3 AND x2 AND x1 AND x0

Total: 4 neurons, 1 layer (fully parallel)

Parameters

Inputs	4
Outputs	4
Neurons	4
Layers	1
Parameters	20
Magnitude	14

Applications

Leading-zero detection: The transition from 1 to 0 in the prefix-AND output marks where the first zero appears from MSB.

All-ones prefix: y_i = 1 means all bits from MSB down to position i are 1.

Carry propagation: In adders, prefix-AND of propagate signals indicates carry will propagate through entire prefix.

Prefix Operation Family

Operation	y_i computes
prefix-and	x_n AND ... AND x_i
prefix-or	x_n OR ... OR x_i
prefix-xor	x_n XOR ... XOR x_i
prefix-sum	x_n + ... + x_i

Usage

from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

def prefix_and(x3, x2, x1, x0):
    inp = torch.tensor([float(x3), float(x2), float(x1), float(x0)])

    y3 = int((inp @ w['y3.weight'].T + w['y3.bias'] >= 0).item())
    y2 = int((inp @ w['y2.weight'].T + w['y2.bias'] >= 0).item())
    y1 = int((inp @ w['y1.weight'].T + w['y1.bias'] >= 0).item())
    y0 = int((inp @ w['y0.weight'].T + w['y0.bias'] >= 0).item())

    return y3, y2, y1, y0

# Examples
print(prefix_and(1, 1, 1, 1))  # (1, 1, 1, 1) - all ones
print(prefix_and(1, 1, 0, 1))  # (1, 1, 0, 0) - first zero at pos 1
print(prefix_and(0, 1, 1, 1))  # (0, 0, 0, 0) - first zero at MSB

Related Circuits

• threshold-prefix-or: OR version of prefix operation
• threshold-prefix-xor: XOR version (parity prefix)
• threshold-prefix-sum: Existing circuit for addition prefix
• threshold-clz4: Uses prefix-AND internally

Files

threshold-prefix-and/
├── model.safetensors
├── model.py
├── create_safetensors.py
├── config.json
└── README.md

License

MIT