On synthesizing CMOS implementation given logic function with uncomplemented literals

Question

I understand that the basic idea is to construct a PUN such that \$V_f\$ (the output node) is raised up to \$V_{DD}\$ if and only if we have input valuations such that \$f = 1\$, and similarly to construct a PDN such that \$V_f\$ is pulled down to \$V_{SS}\$ if and only if we have input valuations such that \$f = 0\$. As far as I can tell, there are two cases, with my question regarding the second case:

1. The given function \$f\$ has literals only in complemented form. In this case, things are easy and the PUN can be read off the function, with the PDN following from finding \$\overline{f}\$ which will be entirely in terms of uncomplemented variables. Thus we can again read off the PDN (and as expected it will be dual to the PUN).

2. The given function \$f\$ has some literals in uncomplemented form. In this case, I am unsure how to proceed as the procedure of Case (1) does not work, at least a priori. For example, if I have a function like \$f = x_1 +x_2\overline{x_3}\$, how should I proceed? It's not clear to me how to "see" the PUN in the same way as in Case (1). What is the general strategy in such cases?

Answer 1

In case 2, you could substitute \$y_3=\overline{x_3}\$. Drive the PUN/PDN with a complement as needed.

You could also complement the type of devices that would be taking the y signal, but that requires level shifting for the signal, and that adds quite a bit of delay vs an inverter.

But - PUNs and PDNs are not always the fastest implementations of a given logic function. Sometimes a ROM block is faster, especially as the number of inputs grows. So it all depends on the usual speed vs. energy use vs. area tradeoffs.

And anyway, the partitioning of branches of a PUN or PDN is by no means unique for a given logic equation, and there's no simple rule of thumb for speed vs size. Usually an optimizer gets to try all combinations, or explores a subset of design space using genetic programming, heuristics, simulated annealing, etc. This makes sense for PUNs and PDNs that are on the timing critical path.

Answer 2

I think it would be helpful to consider simpler cases than a 3-input gate, and the rules for gate formation definitely hold up for 1-2 input static CMOS gates. It's just those gates often have names already. Consider the logic function to implement \$Y=\overline{A\cdot B}\$ which I have implemented as a "custom" logic gate below. The pull-up network consists of M3 and M4 in parallel, and is active when \$\overline{A+B}\$. The pull-down network consists of M1 and M2 in series, and is active when \$\overline{A \cdot B}\$.

^{simulate this circuit – Schematic created using CircuitLab}

Some observations:

1. The NFET pull-down network logical function matches the original function
2. The PFET pull-up network does not require any logical inversions in the inputs (e.g. \$\overline{A}\$ or \$\overline{B}\$), only topological changes.
3. The output function is always inverting.
4. We don't really have a way of inverting an input in a single-stage gate like this. No inputs are inverted.

Observation 1 and 2 are pretty easy to follow, but we run up against 3 and 4 pretty regularly. So how do you implement logic functions like \$Y=A \cdot B\$ or even \$Y=A\cdot \overline{B}\$ in a single stage using static CMOS when you only have access to A and B? You can't.

When you have additional inversions that you can't work around, you must add an additional stage of logic to invert the signal.

^{simulate this circuit}