Functional Decomposition (Digital Logic)

See figure attached for problem statement, and other figure for my attempt.

In my attempt I was able to successfully draw, and use Karnaugh maps to simplify my two functions f and g significantly.

However, the part I get stuck on is, how do I know what can be shared between f and g in a combined circuit?

I attached the solution given for this problem in another figure. As I said above, I can get the first part of the solution without a problem, it's just the jump to the combined circuit that I'm confused about. I can't see how he gets there.

I mean, sure I could start using boolean algebra and try see what's being shared between f and g after simplifying it, but then if I miss something I'm screwed.

Is there a systematic process for finding terms that can be shared between f and g? I feel like I'm left in the dark on this one.

Hopefully the source of my confusion is clear. (If not, just say so and I will try to further clarify)

Any ideas/suggestions/tips/hint/advice/strategies you have for me would be greatly appreciated!

Thanks again,

Well, I can tell you what your textbook did, or at least tried to do. It picked the terms with the most common variables, and expanded them, so that they would become larger but identical.
For example, from the function f, the term \(\bar{x_1} \bar{x_4}\) became
\(\bar{x_1}\bar{x_4} (\bar{x_3} {x_3})=\\
=\bar{x_1}\bar{x_4}\bar{x_3} + \bar{x_1}\bar{x_4}{x_3}\)
All good here. Do this for the rest of the terms where needed. The problem is that at some point, the textbook tried to create the term \(\bar{x_2}{x_3}\bar{x_4}\) from the terms \(\bar{x_1}\bar{x_4}{x_3} \text{ and } {x_1}\bar{x_2}{x_3}{x_4} \) which just doesn't fit, no matter how I look at it. That leads me to the conclusion that the book's answer is wrong. The theory behind the effort is correct, but the execution is wrong.

I would like to comment the method a bit though. Expressing the funtions as a sum of very big products, seems unpractical to me. We should keep in mind that it's the actual operations that cost, and in reality, even the type of IC's that we are going to use matter. For example, if we have 2 products of 4 terms to calculate, we would use a dual 4-input IC (I thing it exists). If however, there were 3 products of 3 terms, only one IC would be enough. Also, after 3 years at university, I have seen that not Sum Of Products nor Product Of Sums is the most cheap implementation of a function. Often factorizations that make the expression shorter (but more deep) cost less operations (and hence IC's). But, sadly, it all comes down to intuition, as far I have seen. No one ever taught me of a standart way to do this and always I had to try several factorizations to decide on the most profitable.

Georacer said:

But, sadly, it all comes down to intuition, as far I have seen. No one ever taught me of a standart way to do this and always I had to try several factorizations to decide on the most profitable.

Click to expand...

Not only is that disapointing, but frightening as well.

So if I'm faced with a question like this in a test scenario, it's going to be either I see it or I don't.

There's got to be more to it than that.

Does anyone else have any input on whether or not you can systematically combine circuits in an efficient manner?

In attempt to try to figure out a systematic way of solving the simpliest combined circuits, I expanded both f and g in terms of minterms.

I put a square box around the minterms that were shared with f and g and labeled them accordingly.(1,2,3,4)

Is there anyway I can use this to get to my end result?

If there is, I don't see it. Just thought I'd throw it out there!

The way you book uses is systematic. Just not practical too. So I think it will be ok if you use it in an exam.

I 'll recap its basic points:

• Express each function as a sum of products
• Search for products in both functions that share a significant number (if not all) of similar terms. For example, x1x2' from the first and x1x2'x3' from the second
• Expand the above terms so that they match. From the above, x1x2' becomes x1x2'x3+x1x2'x3'
• Make all the possible matches between the products of the two functions. Try to simplify any remaining single products. Another Carnot map could be a good idea, if you can't see factorisations with a glance.

Is that clear?

Georacer said:

The way you book uses is systematic. Just not practical too. So I think it will be ok if you use it in an exam.

I 'll recap its basic points:

• Express each function as a sum of products
• Search for products in both functions that share a significant number (if not all) of similar terms. For example, x1x2' from the first and x1x2'x3' from the second
• Expand the above terms so that they match. From the above, x1x2' becomes x1x2'x3+x1x2'x3'
• Make all the possible matches between the products of the two functions. Try to simplify any remaining single products. Another Carnot map could be a good idea, if you can't see factorisations with a glance.

Is that clear?

Click to expand...

Yes, that's much more clear thank you. I'm still confused about one part, I put it in bold in your quote.

When I'm trying to simplify any reamaining single products by using a Karnaugh map, do I take the single products of f and g and put them into a Karnaugh map together or do I draw seperate Karnaugh maps for the single products (the ones that aren't shared) for both f and g.

Can you clarify?

Thanks again!

No, it's a separate map for each function. You want 2 outputs anyway, one for each function, and a Carnot map always gives you only one output.

Georacer said:

No, it's a separate map for each function. You want 2 outputs anyway, one for each function, and a Carnot map always gives you only one output.

Click to expand...

Okay here's my attempt with your steps.

See figure attached.

I feel pretty confident about my answer!

What do you think?

Also, the answer I posted(the one listed in my textbook) must be wrong as you mentioned.

I also attempted another similar problem.

See figure for problem statement(1 figure) and my attempt(2 figures).

In this question the expression I got for f is correct, but not g.

I'm assuming I must have made a mistake somewhere in g but I don't see it.

But all this has helped me better understand the process for solving these problems! THANK YOU!

jegues said:

Okay here's my attempt with your steps.

See figure attached.

I feel pretty confident about my answer!

What do you think?

Also, the answer I posted(the one listed in my textbook) must be wrong as you mentioned.

Click to expand...

Well done! You simplified the exrpessions correctly, then expanded them to get the right terms and finaly you simplified again the unmatching terms (the ones that could be simplified further).

BUT! You missed a couple of crucial things. First of all, in a Karnaugh map, there is a convention on the position of each minterm. Look at this page http://www.allaboutcircuits.com/vol_4/chpt_8/9.html. Notice that the counting on the very first map there is. It starts horizontaly. I advise you to do the same, since others can keep track of your work better that way. Also notice that you have to change the order of the letters on the top left to match with the new ordering.
Another thing is that you should put Don't Care terms in a Karnaugh map as X's. This way not only you show the other where the X's are, but you can decide on the spot, which ones you want to use, and which not.
Other than that, I don't see anything else to account for.

For the next exercise, before I give a go at it, please explain us how your book counts the cost of the expressions, so we can help you better. Clearly it doesn't count operations.

Georacer said:

Well done! You simplified the exrpessions correctly, then expanded them to get the right terms and finaly you simplified again the unmatching terms (the ones that could be simplified further).

BUT! You missed a couple of crucial things. First of all, in a Karnaugh map, there is a convention on the position of each minterm. Look at this page http://www.allaboutcircuits.com/vol_4/chpt_8/9.html. Notice that the counting on the very first map there is. It starts horizontaly. I advise you to do the same, since others can keep track of your work better that way. Also notice that you have to change the order of the letters on the top left to match with the new ordering.
Another thing is that you should put Don't Care terms in a Karnaugh map as X's. This way not only you show the other where the X's are, but you can decide on the spot, which ones you want to use, and which not.
Other than that, I don't see anything else to account for.

For the next exercise, before I give a go at it, please explain us how your book counts the cost of the expressions, so we can help you better. Clearly it doesn't count operations.

Click to expand...

Karnaugh maps can be done either way and the minterms positions in the map can be found by stating the x4 is the least significant bit and you map the minterms according to their binary value.

It shouldn't matter which way I choose to draw it.

Anyways, I think they count cost as the number of gates (don't worry about fan-in) plus the number of inputs.

I didn't say your map was wrong. I just said it would be easier if we all used the same convention. At least for the smaller maps.

Can you explain to me better that cost thing? No matter how I try I can't explain that 21 cost of the G function at the first exercise (first post).

Georacer said:

I didn't say your map was wrong. I just said it would be easier if we all used the same convention. At least for the smaller maps.

Can you explain to me better that cost thing? No matter how I try I can't explain that 21 cost of the G function at the first exercise (first post).

Click to expand...

Count the gates,

4 AND gates,

1 OR gat

count the inputs,

Inputs for AND gates: 12

Inputs for OR gate: 4

4 + 1 + 12 + 4 = 21

Cost of 21.

Lol, ok, so I am to assume that I have in my disposition 4-input OR, 3-input AND that cost me one unit but I have to be charged separately for every instanse of x4 I use? That's just absurd... but I'll play along...

My solution is the following:
\(\left{ \begin{array}{l} f={x_1}\bar{x_2}\bar{x_3}+\bar{x_2}\bar{x_4}+\bar{x_2}\bar{x_3}{x_4}+{x_1}{x_2}{x_3}{x_4} \\
g={x_1}\bar{x_3}{x_4}+{x_1}{x_2}{x_4}+\bar{x_1}{x_3}{x_4}+\bar{x_2}{x_3}\bar{x_4} \end{array}\right}=\\

\left{ \begin{array}{l} f={x_1}{x_2}{x_3}{x_4}+{x_1}\bar{x_2}\bar{x_3}{x_4}+\bar{x_2}{x_3}\bar{x_4}+{x_1}\bar{x_2}\bar{x_3}{\bar{x_4}}+\bar{x_2}\bar{x_3}\bar{x_4}+\bar{x_2}{\bar{{x_3}}}{x_4} \\
g={x_1}{x_2}{x_3}{x_4}+{x_1}\bar{x_2}\bar{x_3}{x_4}+\bar{x_2}{x_3}\bar{x_4}+{x_1}{x_2}\bar{x_3}{x_4}+{x_1}{x_2}\bar{x_3}{x_4}+\bar{x_1}{x_3}{x_4} \end{array} \right}\\

\left{ \begin{array}{l} f={x_1}{x_2}{x_3}{x_4}+{x_1}\bar{x_2}\bar{x_3}{x_4}+\bar{x_2}{x_3}\bar{x_4}+\bar{x_2}\bar{x_3} \\
g={x_1}{x_2}{x_3}{x_4}+{x_1}\bar{x_2}\bar{x_3}{x_4}+\bar{x_2}{x_3}\bar{x_4}+{x_1}{x_2}\bar{x_3}{x_4}+\bar{x_1}{x_3}{x_4} \end{array} \right}\\

\)

Total cost: 26
Can anyone do better?

Why did you include common terms while simplifying the uncommon terms on the Karnaugh map? You just ramped up the cost for no reason. And you tried to get away from specifying the cost leaving all the hard countin to us, you little rascal...

P.S. Lol again! The "bar" parasite on the second set isn't a typo. LaTex just gave up on me! Just check my code!