enter image description here

Could anybody provide help in answering this question? I'm pretty sure I should use a Kmap to analyze it but not sure how to do so.

  • 1
    \$\begingroup\$ You could make a slightly better attempt to motivate than posting an image of an extra bonus question without any specific thoughts of your own. Perhaps at least show us you know how to implement a mux with simple gates. Then an attempt using boolean algebra to minimize may further help. I'm probably the most likely person here to provide an answer with no effort by you. I'm a rare bird that way, in this place. But even I'm not motivated yet.. \$\endgroup\$ – jonk Jun 20 '19 at 5:08
  • \$\begingroup\$ I honestly have no idea where to start. I'm not sure how to convert the muxes into logical expressions which can be put into a Kmap. Can you give me a hint on what to do at least? \$\endgroup\$ – rofldude188 Jun 20 '19 at 5:36
  • \$\begingroup\$ Can you demonstrate the value of F for any two input permutations of your choice? \$\endgroup\$ – jonk Jun 20 '19 at 6:03
  • \$\begingroup\$ A hint might be that you look at the mux in the lower right and note that a is selected when \$c=0\$ and \$d=1\$. This means its output contains \$a\cdot\overline{c}\cdot d\$ as one of its terms. Another of its terms is \$b\cdot\overline{c}\cdot \overline{d}\$ because b is selected when \$c=0\$ and \$d=0\$. The remaining two cases, those where \$c\cdot\overline{d}\$ and \$c\cdot d\$ are true, are no more complex to compose, though not as simply expressed. \$\endgroup\$ – jonk Jun 20 '19 at 6:24
  • \$\begingroup\$ I'd start with just making a truth table, count to 15 in binary (0000 to 1111), place ABCD over their columns. Then look at what F should be for each row in your truth table. If you can make this, show your attempt in your question. - Once you have a truth table you can go straight to Karnaugh map and be done with it. - Is this tedious? Sure. \$\endgroup\$ – Harry Svensson Jun 20 '19 at 8:10

Let's first list out the cases for the box marked with an (\$*\$). Per the text with your problem:

$$\begin{align*} f_0&= a \oplus b\\\\ f_1&= \overline{a \oplus b}\\\\ f_2&= a \cdot b\\\\ f_3&= \overline{a \cdot b} \end{align*}$$

Let's call the mux using \$c\$ and \$d\$ as select inputs \$m_0\$. The other mux with \$f\$ as its output will be called \$m_f\$. Then the two k-maps for the two muxes are:

$$\begin{array}{rl} \begin{smallmatrix}\begin{array}{r|cc} m_0&\overline{c}&c\\ \hline \overline{d}&b&f_3\\ d&a&f_2\end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cc} m_f&\overline{m_0}&m_0\\ \hline \overline{f_0}&f_0&d\\ f_0&f_1&c\end{array}\end{smallmatrix} \end{array}$$

Substituting the expressions for \$f_0\$ through \$f_3\$ into the above k-maps:

$$\begin{array}{rl} \begin{smallmatrix}\begin{array}{r|cc} m_0&\overline{c}&c\\ \hline \overline{d}&b&\overline{a\, \cdot\, b}\\ d&a&a\, \cdot\, b\end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cc} m_f&\overline{m_0}&m_0\\ \hline \overline{a\,\oplus\, b}&a\,\oplus\, b&d\\ a\,\oplus\, b&\overline{a\,\oplus\, b}&c\end{array}\end{smallmatrix} \end{array}$$

If you want, you could proceed through the necessary algebra, starting with:

$$m_0=b\,\overline{c}\,\overline{d}+a\,\overline{c}\,d+\overline{a\, b}\,c\,\overline{d}+a\, b\,c\,d$$

But that's more painful than it needs to be.

You only have 16 permutations. So just list them out in a table:

$$\begin{smallmatrix} \begin{array}{cccc|cc} a&b&c&d&m_0&m_f\\ \hline 0&0&0&0& 0&0\\ 0&0&0&1& 0&0\\ 0&0&1&0& 1&0\\ 0&0&1&1& 0&0\\ 0&1&0&0& 1&0\\ 0&1&0&1& 0&0\\ 0&1&1&0& 1&1\\ 0&1&1&1& 0&0\\ 1&0&0&0& 0&0\\ 1&0&0&1& 1&0\\ 1&0&1&0& 1&1\\ 1&0&1&1& 0&0\\ 1&1&0&0& 1&0\\ 1&1&0&1& 1&1\\ 1&1&1&0& 0&0\\ 1&1&1&1& 1&1 \end{array} \end{smallmatrix}$$

That's a lot easier. From the above table it is trivial to develop the k-map for \$m_f\$ (remember that \$f=m_f\$):

$$\begin{smallmatrix}\begin{array}{r|cccc} m_f&\overline{a}\,\overline{b}&\overline{a}\,b&a\,b&a\,\overline{b}\\ \hline \overline{c}\,\overline{d}&0&0&0&0\\ \overline{c}\, d&0&0&1&0\\ c\, d&0&0&1&0\\ c\, \overline{d}&0&1&0&1 \end{array}\end{smallmatrix}$$

Obviously, the above results in:

$$\begin{align*} m_f&=a\,b\,d + \overline{a}\,b\,c\,\overline{d}+a\,\overline{b}\,c\,\overline{d}\\ &=a\,b\,d +\left(\overline{a}\,b+a\,\overline{b}\right)c\,\overline{d}\\ &=a\,b\,d +\left(a\oplus b\right)c\,\overline{d} \end{align*}$$

You should be able to easily construct the necessary gates -- especially since the question allows you to assume ready access to both the inverted and non-inverted values of inputs \$a\$ through \$d\$.

  • \$\begingroup\$ Thank you for taking the time to write out an answer sir. Much appreciated! \$\endgroup\$ – rofldude188 Jun 21 '19 at 15:11
  • \$\begingroup\$ @rofl If that helps and you aren't waiting for further answers, you are allowed to select it as an answer. But if you want to see others' responses or are not satisfied, then just hold off. The main reason to select an answer is to save the time of others, if you don't need additional help. \$\endgroup\$ – jonk Jun 21 '19 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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