0
\$\begingroup\$

I am a Computer Science undergraduate taking a module on Computer Organisation. There is this typical circuit design question that always appear in my assignment and I'm not sure what is the standard procedure to solve it and what skills do I need for it. This is one such problem where I'm required to get both a solution of 2 decoder and 1 logic gate and 1 decoder with 2 logic gate.

enter image description here

This is the Truth table I have drawnenter image description hereThe only deduction I have derived from it is that 'a' doesn't need to be wired as there is a total repetition in the pattern of b,c,d even as a switches over to 1, and I have to come up with some kind of boolean expression in the form of X.Y.Z where X,Y,Z are booleans formed from some b,c,d as it mimics the wiring in the Decoder with an enabler. The individual expressions inside must only contain 2 levels of boolean operators.

Update: We now have more information on the Truth Table which is similar to a program like

if (b nxor c) return 1, else return b xor d. There isn't a simple case of using the enabler to "zero-out" a case that is definitely 0, as 0 can only be achieved from the else case which required 2 levels of operations, and the role of the enabler doesn't allow us to "one-out" cases that are definitely 1, which is the result we got from the truth table and seemed hardly useful information to wire into the circuit. How exactly do we translate such a checking procedure into an expression X.Y.Z which mimics the decoder perfectly?

\$\endgroup\$
2
  • \$\begingroup\$ If b and c are the same, then f is always true. Otherwise, f is b xor d. Yes? \$\endgroup\$
    – jonk
    Commented Oct 18, 2018 at 7:52
  • \$\begingroup\$ Yes but I don't know how to wire it into the decoder. The b xor c doesn't quite fit into the enabler pin as the enabler immediate cause logic 0 when put to 0 in this case, but there is no obvious output that can be isolated by the enabler pin to be zero as the cases that don't fulfil the first case all will be tested for a 2nd round. \$\endgroup\$ Commented Oct 18, 2018 at 10:35

1 Answer 1

2
\$\begingroup\$

2-IN MUX

The following won't be exactly useful for solving your question. But it seems to me that I need to get you to focus on the logic of a 2-in MUX for a moment: $$\begin{smallmatrix} \begin{array}{l|l} \begin{array}{l} \begin{array}{l}M(A,B,S) \:=\: A\cdot \bar{S} + B\cdot S\end{array} \end{array} & \begin{array}{l} \begin{align*} M(x,y,0)\:&=\: x \\ M(x,y,1) \:&=\: y \\ M(0,x,y) \:&=\: x\:\cdot\: y \\ M(1,x,y) \:&=\: x\: +\: \overline{y} \\ M(x,0,y) \:&=\: x\:\cdot\:\overline{y} \\ M(x,1,y) \:&=\: x\: +\: y \\ M(x,y,x) \:&=\: x\:\cdot\: y \\ M(x,y,y) \:&=\: x\: +\: y \\ M(0,0,x) \:&=\: 0 \\ M(0,1,x) \:&=\: x \\ M(1,0,x) \:&=\: \bar{x} \\ M(1,1,x) \:&=\: 1 \end{align*} \end{array} \end{array} \end{smallmatrix}$$

Some are duplicates. I just wanted to illustrate some different, semi-interesting inputs and their results. I also wanted to force you to see the 2-in MUX equation on the left side of the above, so that it would be clearly fixed in your mind. I shouldn't have to do that. But for what follows, I think I need to remind you, anyway.


Suggestion

I had provided a suggestion as a comment, earlier. Your question included the following comment:

The only deduction I have derived from it is that 'a' doesn't need to be wired as there is a total repetition in the pattern of b,c,d even as a switches over to 1, and I have to come up with some kind of boolean expression in the form of X.Y.Z where X,Y,Z are booleans formed from some b,c,d as it mimics the wiring in the Decoder with an enabler.

The reason I added my comment (which I see you've incorporated into your question, after a fashion) was because you hadn't written out any specific expression after eliminating \$a\$; instead suggesting you were at a mental block from that point. I'd hoped to shake something loose.

While your problem's answer has several forms. I simply suggested to you a pattern that was pretty easy to see from your table. (I got this by simply observing the pattern in \$f\$, without looking at any of the other columns.) My suggestion was:

$$f=\overline{b \oplus c}\:+\:b \oplus d$$

You should know by now how to express \$\oplus\$ as a combination of \$\cdot\$ and \$+\$. (If you haven't already committed to memory that \$a\oplus b=a\cdot\overline{b}+\overline{a}\cdot b\$, then now is [or last week or last month was] definitely the time.) If you expand the above in that way and then simplify it, you should get something like:

$$f=\left(b\cdot \overline{d}+c\cdot d\right)+\overline{b}\cdot\overline{c}$$

It was my hope that you'd have been able to perform that relatively minimal boolean algebra transformation.


One Part of the Answer

Now, the above part within parentheses should be an obvious mux equation to you. It sticks out like a sore thumb. (Clearly, \$d\$ is the selector input for the MUX.)

You should also immediately realize that \$\overline{b}\cdot\overline{c}=\overline{b+c}\$, which is a NOR gate.

So how is it possible that you can not almost immediately arrive at:

schematic

simulate this circuit – Schematic created using CircuitLab

It just seems impossible to miss.


The Remaining Answer

I'll leave it to you to work out the easier answer (according to your teacher.) Be creative and write things down in several different ways. This is important practice; being able to specify the same logical equation in multiple, equivalent forms.

You can also, of course, go to a K-map:

$$\begin{array}{rl} \begin{smallmatrix}\begin{array}{r|cccc} f&\overline{c}\:\overline{d}&\overline{c}\: d&c \:d&c \:\overline{d}\\ \hline \overline{a}\:\overline{b}&1&1&1&0\\ \overline{a}\:b&1&0&1&1\\ a\: b&1&0&1&1\\ a\:\overline{b}&1&1&1&0 \end{array}\end{smallmatrix} &\rightarrow\quad \begin{smallmatrix}\begin{array}{r|cccc} f&\overline{c}\:\overline{d}&\overline{c}\: d&c \:d&c \:\overline{d}\\ \hline \overline{b}&1&1&1&0\\ b&1&0&1&1\\ \end{array}\end{smallmatrix} \end{array}$$

There are three different equivalent K-maps, where the one on the right side above is just one of the three. Write all three out and see if anything arrives in your mind about using two 2-in MUX units and one gate. Or just re-work the logic I gave you earlier, to see if you can re-arrange it into a form that makes the use of two 2-in MUX units more obvious to you.

But here we also get to the reason I wrote about the 2-in MUX at the outset, above. If you look over the list I provide there, and take into account the half-answer already provided, then at least one possible answer should be pretty obvious by now.

Part of the lesson here is that creativity still has a place. There isn't some algorithm that always takes you from any random starting point and inevitably walks you though the only-one-right-way-to-do-it path. Instead, you develop a flexible mind by practice. Lots of it. From that, you'll develop a better ability to not only recognize patterns, but also to recognize almost-patterns that help direct your attention towards something to explore further. Without the practice, you'll never develop the intuition, pattern-recognition, etc.


Note to Wise

The last thing I want to leave you with is this. In this day of cheap computers and myriad software programs to solve almost any question you can compose for them, it becomes far too easy to rely on those tools and to not develop and refine your own skills. Of course, it goes without saying that you also have sites like this and access to the time and skill of some very good folks who have paid all these prices I'm talking about, with their very life's time and blood.

To be honest, you can actually get by in life now without actually having to know much yourself; without investing that much in who you are. But that is a poor choice, I think.

What happens when you find yourself in a situation when you don't have access to these tools, or others don't have time to guide you?

You should be able to, using nothing more than a finger you are born with and some dirt in the ground to draw on, solve these problems. You will always have a finger or can find a stick. You will always have some dirt nearby to draw on. Those will always be at your side, no matter where you find yourself in a long life. (So long as you have a developed brain to work with, you can solve a great many problems.) It will be frustrating, indeed, if you are only capable when you must have Excel or Sage or Espresso and those aren't at hand at the moment. So develop your own imagination and your own skill and intuition. Put in the time without the tools that are so easy today to grab.

Turn yourself into a power-house even when all you have is your finger and some dirt.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.