ESOP and Reed–Muller Synthesis

In ordinary logic design you learned to write any Boolean function as a sum of products — ANDs joined by ORs, minimised on a Karnaugh map. The reversible world speaks a different dialect: ANDs joined by XOR. The reason is hiding in plain sight in the gates themselves — a Toffoli computes t \oplus ab: an AND, XORed onto a target. XOR is what Toffoli-family gates do natively. So if you can write your function as an exclusive sum of products (an ESOP), the circuit practically draws itself: one Toffoli per product term. This page is about that translation — and the classical theory behind it, the Reed–Muller expansion.

Every function is an XOR of ANDs

Every Boolean function f(x_1, \ldots, x_n) can be written as an XOR of AND terms in which every variable appears un-negated: f = c_0 \oplus c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_{12} x_1 x_2 \oplus \cdots \oplus c_{12\cdots n}\, x_1 x_2 \cdots x_n, one coefficient c_S \in \{0,1\} for each of the 2^n subsets of the variables;
this expansion is unique — unlike SOP, where many equivalent covers exist, a function has exactly one positive-polarity Reed–Muller (PPRM) form;
allowing some variables to appear negated instead (via \bar x = x \oplus 1) gives the mixed-polarity forms, and any XOR-of-ANDs whatsoever is called an ESOP — the freest and often shortest of the family.

The translation toolkit between the OR world of Boolean algebra and the XOR world is tiny:

Identity	Use it to…
x \lor y = x \oplus y \oplus xy	turn each OR into XORs (the xy term cancels the double-count)
\bar x = x \oplus 1	trade a negation for a constant term
x \oplus x = 0	cancel duplicated terms — pairs annihilate
x \lor y = x \oplus y when xy = 0	replace OR by XOR outright for disjoint terms

Worked example: the majority function

Take the 3-input majority \mathrm{maj}(a,b,c) — output 1 when at least two inputs are 1 (the carry bit of a full adder). Its familiar SOP is ab \lor bc \lor ca. Convert: the three products overlap only in the all-ones case abc. Apply x \lor y = x \oplus y \oplus xy twice and collect — every correction term is a copy of abc, and they cancel in pairs (abc \oplus abc = 0). The result:

\mathrm{maj}(a,b,c) \;=\; ab \,\oplus\, bc \,\oplus\, ca.

Check it the fast way, case by case: no 1s or one 1 — every product is 0. Two 1s (say a=b=1, c=0) — exactly one product fires: 1 \oplus 0 \oplus 0 = 1. Three 1s — all three fire: 1 \oplus 1 \oplus 1 = 1. Correct on all eight rows, and already in positive-polarity Reed–Muller form: three AND terms, no negations, no constant.

Term by term, gate by gate

Now the payoff. Add one fresh target ancilla wire t, prepared as 0. For each product term of the ESOP, place one (multi-controlled) Toffoli: controls on the term's variables, target on t. Each gate XORs its term onto t, so after k gates the target holds 0 \oplus (\text{term}_1) \oplus \cdots \oplus (\text{term}_k) = f — while the inputs pass through completely untouched. An ESOP with k terms becomes a k-Toffoli cascade. For the majority:

Housekeeping for the other term shapes: a single-variable term (x_i) becomes a CNOT; the constant term 1 becomes a NOT on t; and a mixed-polarity term like \bar a b is a Toffoli whose a-control is conjugated by NOTs (or, expanding \bar a b = b \oplus ab, a CNOT plus a Toffoli — your choice, and a genuine cost trade-off). Since every gate targets t and the controls never change, the gates commute freely — order the cascade however suits the optimiser.

ESOP versus MMD

Notice what changed since transformation-based synthesis: MMD synthesises a whole reversible permutation in place; ESOP synthesis computes an ordinary, quite possibly irreversible, Boolean function onto a fresh output wire — reversibility is restored by the ancilla, exactly the embedding move you know from Bennett-style computing. That makes ESOP the tool of choice when your spec is "compute f(x)" rather than "permute the states": arithmetic predicates, comparators, round functions of ciphers. Real toolchains factor the work: an ESOP minimiser (the classic tool is EXORCISM) squeezes the term count k, then the term-per-Toffoli translation runs mechanically.

The expansion is older than reversible computing by decades. David Muller described the algebraic form in 1954; Irving Reed, the same year, gave a majority-logic decoder for it — and their names stuck to the resulting family of error-correcting codes. The connection is direct: the codewords of a Reed–Muller code are exactly the truth tables of low-degree XOR-of-ANDs polynomials. The very same expansion that here turns functions into Toffoli cascades also protected the imagery beamed back by the Mariner probes from Mars in the 1970s. One algebraic identity, two entirely different superpowers — and in both cases the magic ingredient is that XOR makes Boolean functions into honest algebra (a vector space over GF(2)) where cancellation and uniqueness hold.

The single most dangerous reflex from SOP-land: reading \oplus as "or". They agree on three of four input pairs and differ exactly where it hurts: 1 \oplus 1 = 0 while 1 \lor 1 = 1. So you may not take a Karnaugh-map cover and staple its product terms together with XORs — wherever two terms overlap, the overlap counts twice and cancels. (Try it on the majority: stapling gives ab \oplus bc \oplus ca, which happens to be right only because the double-counted abc region is covered three times — an odd number. Cover it twice and it would vanish!) The safe road is always through the identities: x \lor y = x \oplus y \oplus xy, or use disjoint products. XOR keeps honest books: every term is counted mod 2.