|
Good Grief Charlie Brown! Ever since I presented the "Black Box Brain Boggler" in my
Logically Speaking column in the 8th May issue of EE Times, I've been running around in ever-decreasing circles shouting "Don't Panic, Don't Panic!"
Why? I will explain, but first let me say to those who have been playing with this puzzle: (a) You can not use XOR gates and (b) there really is a solution. In fact, as "The Black Adder" would say (for those au fait with British comedy): "This solution is so cunning that we could pin a tail on it and call it a weasel!"
Note: If you are a hardened logic designer, you might want to skip the next section and go directly to the Proposed solutions that didn't make the grade topic.
But suppose we could use XOR gates
OK, let's take this from the top. The idea is that we start with a black box (no, it doesn't matter whether it's a big box or a small one... look, if you're not going to take this seriously...). There are three inputs to our black box called A, B, and C. Similarly, there are three outputs called not-A, not-B, and not-C. Each of these outputs is the logical inversion of its corresponding input; that is, if A = 0, then not-A = 1, and vice versa. Obviously, if we had access to three NOT gates, then the solution would be simple (Fig 1).
1. Life would be simple if we had three NOT gates.
However, the rules of this "Brain Boggler" say that we have access to only two NOT gates. On the bright side, we also have access to as many AND and OR gates as we wish to use. The problem is that – when I first posed this conundrum in my Logically Speaking column – I mistakenly said that in addition to the AND and OR gates, you could also use as many XOR gates as you wish.
Arrggghhhh! This prompted an immediate flood of responses. Half of these were from logic design experts who immediately recognized what they perceive as being a blatantly obvious solution. In fact, some of these messages kicked-off along the lines of: "Is this the sad state of affairs to which EE Times has sunk..."
To these folks, I responded by saying: "Sorry, my bad, yes this does have an obvious solution, however I made a mistake, and you aren't allowed to use XOR gates." This was typically followed by a pause for a few hours before I received a follow-on message saying: "Oh, well, that makes things a little harder doesn't it ... let me think about this some more." In fact, at this stage many readers said: "I don't think this can be achieved; you can't create a negation from non-negating gates."
Having said this, I also received literally hundreds of emails from folks who aren't well-versed in logic theory, but who do like a good puzzle. Many of these guys and gals grimly fought their way to a solution the old-fashioned way by drawing a truth table of the inputs and outputs, pondering things, and eventually realizing how XOR gates could be used to provide a solution. So, before we leap into the more complex problem without XOR gates, let's first consider the XOR-based possibilities. And just to remind those who don't play with logic gates every day, the truth tables for the basic two-input functions at our disposal (if we assume that we do have access to XOR gates) are shown in Fig 2
2. Truth tables for the logic gates at our disposal
(assuming we have access to XOR gates).
Observe the use of the symbols '&', '+', and '^' to represent logical AND, OR, and XOR functions; we'll be using these symbols in our equations later (also, we will use the symbol '!' to indicate the NOT function). Note especially the XOR gate. As we see, if one of the inputs is held at a logic one value, then the output will be the inverse of the other input. This immediately allows us to come up with a solution to our black box problem using two NOT gates and one XOR gate as shown in Fig 3.
3. Solution using two NOT gates and one XOR.
Alternatively, if we wished to make our diagram look more aesthetically pleasing, we could opt to use three XOR gates as shown in Fig 4.
4. Solution using three XOR gates.
Ah, Ha! You say! But what if we aren't allowed to use a constant logic '1' value? Well, no problemo; if necessary, we can generate this value using one of our NOT gates with an OR gate as illustrated in Fig 5. (Observe that the convention in these schematics is that if two wires cross but there is no dot shown at their intersection, then there is no electrical connection between these wires. By comparison, a black dot at the intersection of two wires indicates that these wires are connected together.)
5. Generating a '1' using a NOT and an OR.
Note that we could have used any of our input signals to generate our logic 1 value; we just happened to pick input C because of the way this schematic was evolving. The trick here is that if input C is 0, then the output from the NOT gate will be 1, so the output of the OR gate will be 1 (remember that the output from an OR gate is 1 if either of its inputs are 1). Alternatively, if input C is 1, then the output from the NOT gate will be 0; but this doesn't matter, because input C is connected directly to the other input to the OR gate, so once again the output from the OR will be a 1.
I bet you're thinking this is all really easy, aren't you? Well, before we plunge into the non-XOR-based solutions, let me give you a taste of the things I've been going through this last week. A reader called Keith emailed me as follows:
"Mr. Maxfield, I just was reading my May 8th, EE Times and came across your puzzles. I left my brain working on the black box over lunch and here is what I came up with. The key is being able to invert one of the inputs gives us two points that we know are logical 1 and 0 (we just don't know which is which, but it doesn't matter). We can then compare the other two inputs to those states. Anyway, attached is a PDF of my solution to your inverting black box (using only one of the invertors)."
As you will see from Keith's PDF he's obviously put a lot of thought into this. The problem is that by the time this arrived, I'd waded through so many potential solutions that my eyes were watering and my brain was leaking out of my ears. In fact, I still haven't decided exactly what this circuit does, how it does it, and – most importantly – if it actually solves the black box problem. Perhaps you would like to ponder this circuit
But we digress... As I mentioned at the beginning of this article, we are not allowed to use XOR gates as part of our solution. When I let folks know this, they responded with gusto and abandon, and once again my "In Box" was flooded with emails. The problem now was working out which solutions worked and which fell at the first fence...
|
