How does this logic gate naming convention work?

Question

In their CMOS VLSI Design, Weste and Harris seem to use a naming convention for logic gates which I cannot quite seem to define in my head. Ill give the two examples they use and hopefully someone knows about it or can point me to standard source:

(1) \$Y = \overline{AB + CD}\$. They call this an AND-OR-Invert-22, or AOI22 gate because "it performs the NOR of a pair of 2-input ANDs"

(2) \$Y = \overline{(A+B + C)D}\$. They call this an OAI31 gate.

What is the crux of this naming convention with respect to the numbers used in particular? I had initially thought that the numbers were (A) the number of inputs to each "sub-gate". For example, in case (1) with the AOI22 gate we have two inputs to the AND gates at the first level, and 2 inputs to the OR at the second level. However, this fails for case (2). Next, I thought (B) that the first number was for the number of inputs to the gate at the first level (2 in AOI22 for the 2-input ANDs, 3 for the the three-input OR) and the second number is for the number of gates at the first level (2 ANDs and 1 OR). This seems to work for both cases. However, it seems to fail to uniquely name a gate (consider e.g. \$Y = \overline{(A+B + C)DE}\$ which would also seem to get the OAI31 moniker under this rubric) and so I wasn't sure what the deal was.

Answer 1

I believe the hang-up is on the "1" input case. Each number refers to the size of the first type of input gate. An AOI432 would be three AND gates, with 4, 3, and 2 inputs respectively, ORed together, then INVerted. Following the numbering scheme, the following logical equation shouldn't be too controversial:

$$Y=\overline{(ABCD)+(EFG)+(HK)}$$

When we get down to one input, it effectively passes the input unaltered. The operations "AND" and "OR" do not alter a single bit, and the reasoning for that can be traced back to Boolean logic rules: $$A+A=A\cdot A=A$$

If I reduce the number of inputs for each gate down to an AOI321, then maybe it would be more clear if we kept the signal names from the previous example.

$$Y=\overline{(ABC)+(EF)+(H)}$$

Revisiting your example equation of \$Y = \overline{(A+B + C)DE}\$, you would consider that gate to be an "OAI311"