QELM — Quine-McCluskey / Espresso Logic Minimizer

A C++ implementation of two classic boolean-function minimization algorithms: exact Quine-McCluskey and the heuristic Espresso algorithm, both reading standard PLA (Programmable Logic Array) format.

What it does

Given a truth table in PLA format (.i inputs, .o outputs, minterm/don't-care rows), QELM minimizes each output function to a compact sum-of-products (SOP) boolean expression.

Example (data/input.txt → data/output.txt):

.i 3
.o 2
000 00
001 01
010 10
...

produces minimized expressions like B and A'C + AC' per output column.

Structure

QELM/
├── include/
│   ├── term.hpp       # a boolean term (minterm + don't-care bits)
│   ├── quine.hpp       # exact Quine-McCluskey minimizer
│   ├── espresso.hpp    # heuristic Espresso-style minimizer (multi-pass)
│   └── combine.hpp
├── src/                # implementations
├── tests/
│   └── test_cases.cpp
├── data/
│   ├── input.txt        # sample PLA input
│   └── output.txt        # corresponding minimized output
└── Makefile

Running it

g++ -std=c++17 src/*.cpp -Iinclude -o qelm
./qelm data/input.txt data/output.txt

Espresso runs multiple minimization passes (minimizeEspresso(..., passes=5) by default) for better results than a single pass, at the cost of exactness — Quine-McCluskey is exact but exponential; Espresso trades optimality for speed on larger inputs.

Background

Boolean minimization is a classic digital-logic-design problem: given a truth table, find the smallest sum-of-products expression that implements it, which matters for real hardware where fewer gates/terms means less silicon and delay. Quine-McCluskey guarantees the exact minimum but scales poorly with input size; Espresso is the industry-standard heuristic that scales to much larger circuits.