0
\$\begingroup\$

Below is a problem I made up and did. Is my solution wrong?


Problem:
Attached is following map for the function \$f\$. We want a minimal cost expression using only and, or and not gates. The cost of a gate is the number of inputs it has plus 1.

K-map

In the above diagram 'd' represents 'don't case' so '0' or '1' would be acceptable.

(original)

Answer:
We can cover the entire area with three selections.
1.) The four squares in the upper left hand corner.
2.) The two squares in the upper right hand corner.
3.) The squares in the upper right hand corner and lower left hand corner.
$$ f = \overline X_1 \overline X_3 + \overline X_0 X_1 \overline X_3 + \overline X_0 X_ 1 \overline X_2 $$

Based upon the comments I got, here is an updated solution.
Another approach is to cover it with the following four selections:
1.) The four squares in the upper left hand corner.
2.) The top row.
3.) The top half of the left most column and the top half of the right most column.
4.) The squares in the upper right hand corner and lower right hand corner.
$$ f = \overline X_1 \overline X_3 + \overline X_2 \overline X_3 + \overline X_0 \overline X_2 + \overline X_0 X_1 \overline X_2 $$

Another approach is to cover it with the following three selections:
1.) The four squares in the upper left hand corner.
2.) The upper two squares in the left most column plus the upper two squares in the right most column.
3.) The bottom square of the right most column and the top square of the right most column.
$$ f = \overline X_1 \overline X_3 + \overline X_0 \overline X_3 + \overline X_2 x_1 \overline X_0 $$ Is this right?

\$\endgroup\$
  • 1
    \$\begingroup\$ How do you define "cost"? If you use a 4-input LUT as is done in an FPGA then all logically equivalent functions will have the same cost. Could you crop your image, by the way? \$\endgroup\$ – Elliot Alderson Oct 16 '19 at 23:16
  • 1
    \$\begingroup\$ Term 3 shows you understand that the top of kmap is linked to bottom. That's a clue. \$\endgroup\$ – StainlessSteelRat Oct 17 '19 at 1:09
  • 1
    \$\begingroup\$ On your edit, you have 4 terms. Three are correct, 1 is wrong! The wrong term was not in your initial answer. \$\endgroup\$ – StainlessSteelRat Oct 18 '19 at 18:14
  • 1
    \$\begingroup\$ Looks good… ... \$\endgroup\$ – StainlessSteelRat Oct 19 '19 at 20:38
  • 1
    \$\begingroup\$ What does 'd' represent in the map? Is it 'don't care'? This needs to be in your question in order to answer it. \$\endgroup\$ – Warren Hill Oct 20 '19 at 15:08
1
\$\begingroup\$

Assuming that a 3-input gate "costs" more than a 2-input gate, your solution is not the lowest cost solution. Since this looks a lot like a homework problem I'll let you make another attempt. Don't forget to look for all of the groupings formed by curling or rolling the map so that the edges touch.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I am not sure what you mean by a homework problem but I am not currently taking any classes and I am not planning on doing so. \$\endgroup\$ – Bob Oct 16 '19 at 23:29
  • \$\begingroup\$ It would help then if you would explain your motivation for asking the question, particularly the issue of "cost". Karnaugh maps aren't used much for optimization anymore in the real world, because "cost" is more complex than a K-map can optimize. \$\endgroup\$ – Elliot Alderson Oct 16 '19 at 23:40
  • \$\begingroup\$ I do not see a better solution. It is my belief that the upper left hand corner and the lower right hand corner do not border. If you have a better solution, I would like to see it. \$\endgroup\$ – Bob Oct 16 '19 at 23:40
  • \$\begingroup\$ I am trying to understand Karnaugh maps. \$\endgroup\$ – Bob Oct 16 '19 at 23:41
0
\$\begingroup\$

You can try simplifying the solution further. Karnaught maps "folds" so the edges connect. Look for large groupings

| improve this answer | |
\$\endgroup\$

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.