Does the NOT gate count towards the depth of a circuit?

Question

So I was going through some problems for a course that I am taking this semester and I came upon a problem that seemed to imply something. Let me first say that I am not looking for the solution to this problem, but rather it spawned a question that has me in the need for some clarification.

The problem was to write a two-level logic version of the following equation using AND, OR, and NOT gates only.

F = A + (B*\$\bar C\$)

As far as I can tell - that's not possible unless the NOT gate does not count towards the depth. So this raised the question - does a NOT gate not count towards the depth of a circuit?

The definition I typically see is that the depth of a Boolean circuit is the largest number of gates between a given input and output. The textbook for my course also uses this definition. So is this the impossible task? Or am I just not thinking cleverly enough?

Thanks for any insight!

Answer 1

A typical Programmable Array Logic (PAL) chip has only two levels of logic. When squeezing a bunch of logic into some PAL chips, NOT gates on the inputs don't count towards the depth of the circuit.

Answer 2

According to Fundamentals of Logic Design, Sixth Edition by Roth and Kinney, inverters (NOT gates) that are directly connected to the circuit inputs typically do not count towards the number of levels (depth) a circuit has:

As is usually the case in digital circuits where the gates are driven from flip-flop outputs (as discussed in Unit 11), we will assume that all variables and their complements are available as circuit inputs. For this reason, we will not normally count inverters which are connected directly to input variables when determining the number of levels in a circuit.

As for inverters within the circuit, those are typically combined with AND and OR gates to form NAND and NOR gates, which, according to Fundamentals of Logic Design, Sixth Edition, may be preferable for the following reason:

Logic designers frequently use NAND or NOR gates because they are generally faster and use fewer components than AND or OR gates.

Answer 3

There are a variety of technologies in which logic may be implemented. In some of them, such as balanced ECL, every input or output is a pair of complementary signals, such that any two-input gate may be used as AND, OR, NAND, NOR, ORNOT, or ANDNOT with equal propagation delay. In other technologies, such as CMOS, a "logic level" is a combination of AND and OR gates feeding an inverter, but with the caveat that propagation delay for an N-input AND or OR gate will be roughly proportional to aN^2+bN+c, for some constants a, b, and c (a three-input gate will probably not be much slower than a two-input gate, since the "c" term would dominate, but e.g. a 32-input NOR would be massively slower than eight 4-input NOR gates which feed four two-input NAND gates which in turn feed a 4-input NOR gate, since with a 32-input gate the "a" term would dominate).

Answer 4

Generally, inversions don't count.

As others have answered, some technologies give you inversions "for free".

Probably more important is question of exactly what you mean by an inversion. DeMorgan's Theorem allows you to "produce" inversions to a logical gate simply by considering it as its logical inverse. That is, an AND gate is "just" an OR gate with inversions on its inputs and outputs. So, where did they come from? In a complex logic function, you can sometimes simplify the physical number of gates just by applying this technique.

So it makes more sense to just ignore inversions when speaking in theoretical terms about logic functions. You'll get an adequate conceptual idea of what's going on, and that's what the analysis is all about.

Answer 5

DTL inputs (diodes) and TTL inputs (base-emitter junctions) are an example of "hidden inverting". It is made by inverting these diode elements with their cathodes facing out and biasing the anodes with Vcc.

Thus, these original OR gates are converted, according to De Morgan's theorem, into AND gates. It is done this way because diode switches cannot be connected in series (like transistor switches in CMOS for example) but only in parallel.

So TTL and DTL AND logic gates are actually OR gates with inverted inputs.

Answer 6

If you implemented this expression using discrete gates from packages like 74HC04 (inverters), then obviously an inverter will introduce a propagation delay which, from the perspective of "depth", cannot be discounted.

In that context, a NOT gate does contribute to depth.

From the perspective of a person designing an integrated circuit, though, they would go to great lengths to minimise propagation delay, by taking advantage of the inversion inherent in different FET arrangments. You may consider \$\overline{A\cdot B}\$ (NAND) as being two distinct operations, AND followed by NOT, with a depth of 2, but a NAND implementation with FETs has only one stage:

^{simulate this circuit – Schematic created using CircuitLab}

Conversely, a single AND operation may be considered to have depth = 1, but to implement it with FETs requires two stages:

^{simulate this circuit}

It seems to me that the answer to your question depends on who you ask, or what system you are employing to actually implement the expression. Are you using discrete logic gates, as found in ICs such as the 74' series, or are you using transistors?

A more useful answer for you might arise from consideration of whether NAND (or NOR) consists of two distinct operations, having a depth of 2. If so, then the inversion contributes to depth, and every \$\overline{BAR}\$ in a boolean expression is an extra stage to be counted. In my opinion, this is correct.

Another reason I favour the latter opinion (NOT gates do count), is that in any implementation of something like \$\overline{A}+B\$ (whether it be with FETs or discrete gates from ICs), necessarily there is an asymmetry in propagation delay along the paths.

I think this could be a divisive subject. I admit that this is an opinionated answer, and I fully expect to be lambasted for it, especially considering I have absolutely no other material or references to back me up.