phanerozoic / threshold-crc16-mag53

threshold-crc16-mag53

CRC-16 CCITT single-step function using magnitude-optimal XOR components .

Optimization

This circuit uses proven-optimal XOR decompositions instead of naive OR+NAND+AND:

Total magnitude: 74 → 53 (28% reduction)

XOR Component Choices

XOR (2-input) - Magnitude 7

From the 6 proven-optimal solutions, we use the symmetric opposites family:

h1: [-1, +1], bias=0   (fires when b > a)
h2: [+1, -1], bias=0   (fires when a > b)
out: [-1, -1], bias=1  (NOR of hidden)

Selected for:

• Zero biases in hidden layer (simpler accumulator)
• Symmetric structure (clearer mathematical reasoning)
• Proven optimal via exhaustive search (no mag-6 solutions exist)

XOR3 (3-input) - Magnitude 10

From the 18 proven-optimal solutions, we use the selector + full pattern:

h1: [0, 0, -1], bias=0   (selector: fires when c=0)
h2: [-1, +1, -1], bias=0 (full: fires when b > a+c)
h3: [-1, -1, +1], bias=0 (full: fires when c > a+b)
out: [+1, -1, -1], bias=0

Selected for:

• All biases are zero
• Selector neuron isolates the "unique" input in CRC context
• Proven optimal via exhaustive search (387M configs, no mag-9 solutions)

Polynomial

0x1021 = x^16 + x^12 + x^5 + 1 (CRC-16-CCITT)

Function

feedback = C[15] XOR D

C'[0]  = feedback           (tap at x^0)  ← XOR (mag 7)
C'[1]  = C[0]
C'[2]  = C[1]
C'[3]  = C[2]
C'[4]  = C[3]
C'[5]  = C[4] XOR feedback  (tap at x^5)  ← XOR3 (mag 10)
C'[6]  = C[5]
...
C'[11] = C[10]
C'[12] = C[11] XOR feedback (tap at x^12) ← XOR3 (mag 10)
C'[13] = C[12]
C'[14] = C[13]
C'[15] = C[14]

Architecture

Breakdown

Verification

• Exhaustively tested against all 2^17 = 131,072 input combinations
• XOR optimality proven via exhaustive search (magnitude 7, 6 solutions)
• XOR3 optimality proven via exhaustive search (magnitude 10, 18 solutions)

Comparison to Naive Implementation

Files

threshold-crc16-mag53/
├── model.safetensors
├── model.py
├── create_safetensors.py
├── config.json
└── README.md

Usage

from safetensors.torch import load_file
from model import forward

weights = load_file('model.safetensors')

# Single step: 16-bit CRC state + 1 data bit → new 16-bit state
inputs = [c0, c1, ..., c15, d]  # 17 binary values
outputs = forward(inputs, weights)  # 16 binary values

License

MIT