dunkirk.sh
bcd-optimization#
optimizing a gate level bcm to the end of the earth and back
The canonical repo for this is hosted on tangled over at dunkirk.sh/bcd-optimization
© 2026-present Kieran Klukas
optimizing a gate level bcm to the end of the earth and back
Python
98.8%
Verilog
0.6%
C
0.5%
12
1
0
Clone this repository
https://tangled.org/dunkirk.sh/bcd-optimization
https://tangled.org/did:plc:krxbvxvis5skq7jj6eot23ul/bcd-optimization
git@knot.dunkirk.sh:dunkirk.sh/bcd-optimization
git@knot.dunkirk.sh:did:plc:krxbvxvis5skq7jj6eot23ul/bcd-optimization
For self-hosted knots, clone URLs may differ based on your setup.
Download tar.gz
- Add XNOR to 2-input and 3-input allowed gates
- Add 4-input gate synthesis (AND4, OR4, XOR4, XNOR4, NAND4, NOR4)
- Add _try_general_synthesis() for mixed 2/3/4-input gates
- Add parallel search scripts for optimal circuit finding
Co-Authored-By: Claude Opus 4.5 <noreply@anthropic.com>
- Add exact_synthesis_mixed() for circuits with both 2-input and 3-input gates
- Add function restriction to limit to real gates (AND, OR, XOR, NAND, NOR)
- Add _decompose_gate_function() for cleaner DOT visualization
- Found 23-input solution: 7x2-input + 3x3-input gates
- Uses: XOR, OR, AND, NAND, OR3, XOR3
- Ties the 23-input record using only standard purchasable gates
Co-Authored-By: Claude Opus 4.5 <noreply@anthropic.com>
- Fix segment c truth table (was wrong for digits 2, 3)
- Fix segment f truth table (was wrong for digit 7)
- Fix gate function encoding (bit ordering was inverted)
- Add Verilog, C, and DOT export functions for exact synthesis
- Update CLI to use appropriate export based on result type
- Add exported 12-gate circuit files (verified correct for 0-9)
The corrected truth tables require 12 gates minimum (24 inputs)
compared to 11 gates with the buggy tables.
Co-Authored-By: Claude Opus 4.5 <noreply@anthropic.com>
Adds bcd_optimization/multi_level.py with:
- Gate and Circuit dataclasses for multi-level representation
- Support for arbitrary gate types (AND, OR, NAND, NOR, XOR, XNOR)
- Support for multi-input gates (3+)
- Circuit verification against truth tables
- Optimized synthesis using verified SOP expressions
Results comparison:
SOP (2-input gates): 52 total gate inputs
Multi-level (2-input): 22 total gate inputs (11 gates) <- BEST
Multi-input SOP: 52 total gate inputs (same structure)
The 2-input exact synthesis wins because it uses XOR/XNOR to exploit
segment relationships (a≈d, c≈f, d≈g differ by only 1-2 minterms).
Co-Authored-By: Claude Opus 4.5 <noreply@anthropic.com>
- Total cost = AND gate inputs + OR gate inputs
- MaxSAT now optimizes for total cost, not just AND inputs
- Updated default target to 61 (no-sharing baseline)
Results:
No sharing: 61 total (33 AND + 28 OR)
Optimized: 52 total (15 AND + 37 OR)
Savings: 9 gate inputs (15% reduction)
Sharing reduces AND inputs dramatically (33→15) but increases
OR inputs (28→37) since shared terms fan out to more outputs.
Co-Authored-By: Claude Opus 4.5 <noreply@anthropic.com>
README.md