Logic · Digital circuits
Three inverters from two
Build a combinational circuit which negates 3 binary inputs using only 2 NOT gates. You may use any number of AND or OR gates, but obviously no NANDs or NORs are allowed.
Show my solutionHide my solution
First, it's useful to think about the possible structure of the solution before writing any logical expression. Thinking like a physicist, it may be useful to assume some symmetrical structure in the solution. Then you can play with the algebra.
So our first guess would be to look for symmetrical logic expressions to make good use of the limited number of NOT gates. The idea of looking for symmetrical expressions is to be able to reuse them for each negated output. What I mean is that, in a first stage, we probably won't want signals in our circuit such as \(\overline{X}\) or \(\overline{XY}\), but we would like to have and make good use of signals such as \(\overline{X+Y+Z}\) or \(\overline{XYZ}\). But what do these signals mean? For example, \(\overline{X+Y+Z}\) means that (is only true when) all our inputs are down (or false, or logic 0), and \(\overline{XYZ}\) means that at least one input is down (but it doesn't say which one, so in that sense the expression is symmetrical).
Let's think about how to build up a circuit for \(\overline{X}\). How do we express \(\overline{X}\) in terms of minterms? Easy:
\[ \overline{X} = \overline{X}\,\overline{Y}\,\overline{Z} + \overline{X}\,\overline{Y}Z + \overline{X}Y\overline{Z} + \overline{X}YZ \]In terms of boolean algebra, sums and products correspond to OR and AND gates, so they are infinitely available. But negations aren't, so we want to get rid of them and substitute them with symmetrical expressions. For example the first term in our minterm expansion, \(\overline{X}\,\overline{Y}\,\overline{Z}\), means that 0 inputs are up (which is nicely symmetrical). With that idea in mind, we can rewrite \(\overline{X}\) as:
\[ \begin{aligned} \overline{X} &= \text{(0 inputs up)} && \leftarrow\ \overline{X}\,\overline{Y}\,\overline{Z} \\ &+ (Y+Z)\,\text{(1 input up)} && \leftarrow\ \overline{X}\,\overline{Y}Z + \overline{X}Y\overline{Z} \\ &+ YZ\,\text{(2 inputs up)} && \leftarrow\ \overline{X}YZ \end{aligned} \]OK. Probably we are on the right track. But we would like to have in our expressions just two symmetric expressions and use one NOT gate for each one. It's time to apply some boolean algebra to simplify our expressions. First, it's easy to notice that:
\[ \begin{aligned} (Y+Z)\,\text{(1 input up)} &= (Y+Z)\,\text{(1 input or 0 inputs up)} \\ YZ\,\text{(2 inputs up)} &= YZ\,\text{(2 inputs or 0 inputs up)} \end{aligned} \]because adding false expressions doesn't change the truth of our statements. Do these new expressions have any use? Yes, because we can now rewrite
\[ \begin{aligned} \text{(0 up)} + (Y+Z)\,\text{(1 or 0 up)} &= (Y+Z+\text{0 up})\,\text{(1 or 0 up)} \\ &= (Y+Z+\text{0 up}+\text{2 up})\,\text{(1 or 0 up)} \end{aligned} \]Great! We have expressed \(\overline{X}\) using just two symmetric logical expressions,
\[ \text{(0 or 1 inputs up)}, \qquad \text{(0 or 2 inputs up)} \] \[ \overline{X} = \big(Y+Z+\text{(0 or 2 up)}\big)\,\text{(0 or 1 up)} + YZ\,\text{(0 or 2 up)} \]plus the unrestricted signals \(X\), \(Y\) and \(Z\). The nice thing about all this is that these symmetrical expressions can naturally be reused for the synthesis of the other outputs, \(\overline{Y}\) and \(\overline{Z}\).
The last question to answer is how we synthesize the symmetrical expressions we found using NOT gates and, in general terms, what kind of symmetrical expressions we can find using NOTs. It's easy to find out that expressions such as at least N inputs up \((1 \le N \le 3)\) can be synthesized without using any NOT gates, so expressions such as at most N inputs up \((0 \le N \le 2)\) can be synthesized using one NOT gate:
\[ \begin{aligned} \text{(0 inputs up)} &= \overline{X+Y+Z} \\ \text{(at most 1 input up)} &= \overline{XY+XZ+YZ} \\ \text{(at most 2 inputs up)} &= \overline{XYZ} \end{aligned} \]OK, let's use one NOT gate to synthesize:
\[ \text{(0 or 1 inputs up)} = \text{(at most 1 input up)} = \overline{XY+XZ+YZ} \]What about synthesizing (0 or 2 inputs up)? Let's negate this expression (wasting the other NOT), and see if we can build it up:
\[ \overline{\text{(0 or 2 inputs up)}} = \text{(1 or 3 inputs up)} = \text{(1 input up)} + XYZ \]But (1 input up) = (at least 1 input up)(at most 1 input up). So, if you realize, we are done(!) because:
\[ \begin{aligned} \text{(0 or 2 inputs up)} &= \overline{\text{(at least 1 up)}\,\text{(at most 1 up)} + XYZ} \\ &= \overline{(X+Y+Z)\,\text{(at most 1 up)} + XYZ} \end{aligned} \]and we have made use of our second NOT gate. Now, it's easy to synthesize \(\overline{Y}\) and \(\overline{Z}\) using the same NOT gates. Here is the entire circuit; flip the inputs and watch both NOT gates feed all three outputs.
| X | Y | Z | A | B | X̄ | Ȳ | Z̄ |
|---|
Some friends from MIT told me about this problem while I was working at Synopsys, CA. Kind regards to Samitha and Nodari!