Q5VLSI Design

CMOS Circuits for y=A+BC+D and y=A'+B'C', and Euler-Path Layout for y=AB+CDE

For y = A + BC + D: the complement is y' = (A+BC+D)' = A'.(BC)'.D' = A'.(B'+C').D'. The pull-down network (NMOS) therefore implements y'=1 as a series connection of A', D', and a parallel combination of B' and C' (all three series-connected blocks in series: A', then the parallel(B',C') block, then D'). The pull-up network (PMOS) is the series-parallel dual: a parallel connection of A', D', and a series combination of B' and C'. As with the earlier AOI structures, since the switch-level literals used are the complements A', B', C', D', either dedicated small inverters generate these complements from the true inputs, or (more commonly in practice) the gate is designed so the NMOS and PMOS device gates are directly driven by the true signals A, B, C, D with the network topology itself (not literal inversion) implementing the required logic - the standard convention is that for an AOI (AND-OR-INVERT) gate of this form, NMOS gates are driven directly by A, B, C, D (not their complements), with the series/parallel arrangement of the PDN mirroring the AND/OR structure of the terms being summed, and the output naturally emerges inverted (giving y' at the output, requiring a following inverter stage to recover true y if needed).

For y' = A' + B'C' (i.e., y = A'+B'C' is itself the function required, which is already in a convenient AOI-inverted form): treating y=A'+B'C' as the direct output of an AOI gate, its complement is y' = (A'+B'C')' = A.(B'C')' = A.(B+C). The pull-down network implementing y'=1 is series A with a parallel combination of B and C. The pull-up network (dual) is parallel A with a series combination of B and C. This is a standard 3-input AOI21-type gate structure (one literal ORed with the AND of two others, then inverted), realized with 3 NMOS and 3 PMOS transistors total.

Euler Path Layout for y = AB + CDE

The Euler-path layout technique aims to find a single ordering of the input gate signals (a permutation of A, B, C, D, E in this case) such that a single, uninterrupted diffusion strip can be drawn through all the transistors of both the NMOS pull-down network and the PMOS pull-up network, without needing to lift the diffusion (i.e., without requiring any break/gap in the diffusion strip that would otherwise force separate diffusion islands connected by metal, wasting layout area). For y = AB+CDE, the complement is y' = (AB+CDE)' = (AB)'.(CDE)' = (A'+B').(C'+D'+E'). The PDN structure corresponding to this expression is a series-parallel network: A and B in series (implementing the AB product) in parallel with C, D, E all in series (implementing the CDE product), the two parallel branches joined at both the top (to output) and bottom (to ground).

Representing this network as a graph (nodes = circuit junction points, edges = transistors labeled by their gate signal) and searching for an Euler path (a path traversing every edge exactly once) reveals that the gate ordering A-B-C-D-E (or an equivalent ordering that keeps the two series-connected groups AB and CDE contiguous and adjacent, such as A-B then continuing to C-D-E) permits a single continuous diffusion path threading through all five transistors of the PDN in sequence, since the AB branch and CDE branch share common top and bottom junction nodes that allow the path to continue from the end of one branch's transistors directly into the start of the other's without a diffusion break. The dual PUN (PMOS network: A,B in parallel joined in series with the parallel combination... more precisely the dual of the PDN structure, which for series-parallel dual networks is parallel(A,B) in series with parallel(C,D,E)) uses the identical gate ordering A-B-C-D-E stacked directly above the NMOS row in the standard two-row (NMOS row, PMOS row) stick-diagram layout convention, since a valid Euler-path ordering for the PDN is simultaneously valid for its dual PUN. This shared single gate ordering across both rows is precisely what allows the polysilicon gate strips to run as simple continuous vertical lines crossing both the NMOS and PMOS diffusion rows without any jogs, producing the most compact possible layout for this 5-transistor-per-network AOI gate.

It is worth noting that the choice between implementing a complex Boolean expression as a single compound AOI/OAI gate (as done for both y=A+BC+D and y=A'+B'C' above) versus decomposing it into multiple cascaded elementary gates (inverters, NAND2, NOR2, etc.) represents a fundamental trade-off in static CMOS design: the compound single-gate realization uses fewer total transistors and incurs only a single gate-delay's worth of propagation delay (rather than accumulating delay across multiple cascaded stages), but produces a PDN/PUN network with more series-stacked transistors than a simple 2-input gate, and each additional series-stacked transistor adds resistance that slows the gate's own switching speed - so beyond a certain fan-in and stack-depth (commonly 3 to 4 series transistors in practice), the compound-gate approach's single-stage-delay advantage can be outweighed by its own increased internal series resistance, motivating designers to decompose very complex expressions into multiple simpler cascaded stages instead.

Regarding the Euler-path layout technique more broadly, it is important to recognize that not every arbitrary series-parallel switch network necessarily admits a valid Euler path using a single common gate ordering for both its NMOS and PMOS networks; when no such common ordering exists, the layout must either accept one or more diffusion breaks (requiring additional metal-to-diffusion contacts and hence extra layout area to bridge the discontinuous diffusion regions), or the designer may restructure the underlying Boolean expression itself (exploiting associativity, commutativity, or alternative factorizations of the same logic function) specifically to arrive at a switch-network topology that does admit a compact, single-path Euler ordering - this consideration is why compact standard-cell layout design for complex AOI/OAI gates in real commercial cell libraries often involves iterating over multiple algebraically-equivalent factorizations of the same target Boolean function purely to find the one yielding the most compact, Euler-path-compatible transistor layout.

For the specific 5-transistor y=AB+CDE example, the practical layout benefit of achieving a valid Euler path is significant: without it, the two branches (the AB series pair and the CDE series triple) would need to be laid out as two physically separate diffusion strips joined only by metal interconnect at the shared top (output) and bottom (ground/VDD) nodes, consuming additional metal routing area and at least one extra diffusion-to-metal contact per branch junction; with the valid Euler-path ordering found above, however, the entire 5-transistor network is realized as one single, unbroken diffusion strip with polysilicon gates crossing it at the five ordered positions, minimizing both the diffusion-region area and the number of contacts required, which is precisely the layout-density benefit that makes Euler-path-based transistor ordering a standard, systematically applied technique in real full-custom and standard-cell CMOS layout methodology.