reducing a function to minimum form using K-map

Georacer

Joined Nov 25, 2009
5,182
Sorry for the late reply.

Clearly we are looking at two different functions. The solution function does not include the minterms 10 and 11, so it's a different problem.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Sorry for the late reply.

Clearly we are looking at two different functions. The solution function does not include the minterms 10 and 11, so it's a different problem.
Thank you, GeoRacer.

Yes, I too wasn't sure about the solution. Okay, the solution is wrong but is my answer correct? Please help me. Thanks.

Regards
PG

PS: The answer given at the back of the book is: F' = BD +BC.
 

Georacer

Joined Nov 25, 2009
5,182
Your answer is correct. It describes the expression for the function F.
The answer F'=BD+BC is also correct and describes the complement of F.

I generally double check my results if they disagree with the ones of a book, but I don't feel to engaged to them. Books were written by humans, after all!
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Thank you, GeoRacer.

Okay. My answer was: F = C'D' + B. But I need to find the complement of the F so I can implement it using NAND gate. The complement of F is: F' = BD + BC. But I don't understand how I get this. Please help me with this.

Best regards
PG
 

Georacer

Joined Nov 25, 2009
5,182
You have reached the result F=C'D'+B by filling the K-map with 1s and grouping them.
It is only reasonable that you can find the F' by filling the K-map with the 0s of the function and grouping them. Do you understand how this will work?

I 'd also like to note that, in order to get NAND circuit, we use the F minterm expression. After you write F=C'D'+B (a Sum of Products) form, you double negate the expression and have a NAND circuit:
F=((C'D'+B)')'
=(C'D')'B')'
=((C' NAND) D') NAND B')
which is a NAND circuit.

If you want a NOR circuit, you have to work with the F' (maxterm) representation:
F=(F')'=(BD+BC)'
=(BD)'(BC)'
=(B'+D')(B'+C')

Now you double negate this form and get what you wish:
F=(((B'+D')(B'+C'))')'
=((B'+D')'+(B'+C')')'
=(B' NOR D') NOR (B' NOR C')
which is a NOR circuit.

Is that clear?
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Hi

Please have a look on the attachment. Thanks a lot.

And if possible, please expand a little on this section from your previous post:
I 'd also like to note that, in order to get NAND circuit, we use the F minterm expression. After you write F=C'D'+B (a Sum of Products) form, you double negate the expression and have a NAND circuit:
F=((C'D'+B)')'
=(C'D')'B')'
=((C' NAND) D') NAND B')
which is a NAND circuit.

If you want a NOR circuit, you have to work with the F' (maxterm) representation:
F=(F')'=(BD+BC)'
=(BD)'(BC)'
=(B'+D')(B'+C')

Now you double negate this form and get what you wish:
F=(((B'+D')(B'+C'))')'
=((B'+D')'+(B'+C')')'
=(B' NOR D') NOR (B' NOR C')
which is a NOR circuit.
Many thanks.

Regards
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
You did the same steps, but you put the variable groups directly to the NAND circuit, essentially skipping over the double negation part. Had you tried to write the circuit expression only with NAND Boolean operations, you would have actively double-negate the F expression.

BUT! We do have a serious problem with K-map minimizations! Variable groups can only be rectangle and contain as many elements as powers of 2. This is very important. You cannot draw groups that do corners of contain 3 or 7 elements.

I strongly suggest you take another read in K-maps, in your book, in the AAC book or any other source you prefer.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Thank you very much. It has been very kind of you.

You did the same steps, but you put the variable groups directly to the NAND circuit, essentially skipping over the double negation part. Had you tried to write the circuit expression only with NAND Boolean operations, you would have actively double-negate the F expression.
Actual after our last correspondence I read some of the pages from Mano's book (sorry to say that book sucks and is not for beginners :(). The book says to implement a function using NAND logic you need to express the F in SoP form and it says a term with single literal requires an inverter in the first level; however if it's already complemented then it can be input directly into second level. Don't you find attached solution in my last post correct?

BUT! We do have a serious problem with K-map minimizations! Variable groups can only be rectangle and contain as many elements as powers of 2. This is very important. You cannot draw groups that do corners of contain 3 or 7 elements.
I haven't read about that rectangle rule. I have been through AAC e-book and I didn't come across such a rule there too. Please have a look on the attachment to see what I'm trying to say. Please help me with it because it's confusing me. Thank you.

With best wishes
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
We 'll sort out the K-map thing and then we 'll go on to circuit implementation.

Just as you noticed, the red group isn't a rectangle and thus isn't a valid variable minimization. You just can't get anything out of it!

Take a look at the green group. It includes the terms w'x'y'z, w'x'yz, w'xy'z and w'xyz which can be grouped as w'x'y'z+w'x'yz+w'xy'z+w'xyz=w'z. Indeed you have such a group in your minimization.

Then there is the purple group. w'xy'z+w'xyz+wxy'z+wxyz=xy. You have that group too in your expression for F. OK so far.

But now for the red group: w'x'yz+w'xyz+wxyz+wxyz'<>y. It's just isn't equal. The group that gives y as minimization is the whole Σ(2,3,6,7,10,11,14,15).

Another way to see it is to look at the side labels of the columns and rows.
The green group has w=0 at both its rows and z=1 for both its columns. Thus it has an expression of w'z. Only the elements of the green group satisfy the constraints w=0 and z=1.

The purple group has x=1 in both its rows and z=1 at both its columns. Thus the expression xz. Only the elements of the purple group satisfy the constraints x=1 and z=1.

The red group has y=1 in every element that it includes but there still are elements in the table that satisfy the constraint y=1 that aren't included in the red group. This is why the red group can't be minimized into y.

Is that easier to understand?
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
I'm extremely sorry for the confusion. But please don't think that I wasn't paying any attention. As a matter of fact, I have checked again, both books (especially, the Floyd's one) don't say anything specifically about rectangular rule. That what confused me. Sorry. Now I won't make this mistake. I'm extremely thankful for your patience and help.

Cheers
PG
 

Georacer

Joined Nov 25, 2009
5,182
It's more important that you understand why anything else than a rectangle with number of elements in powers of 2 won't work, rather than apologizing. Are you sure that you have understood why?

I 'll give you another positive and negative example:


In this image, the green group is a valid group. It is rectangle (not necessarily square) and has 2^2 elements. These elements are the only ones that satisfy the constraints B=0 and C=1. Because they do, this group can be minimized into the term B'C.

The cyan group isn't rectangle and thus invalid. There is not constant variable value throughout its elements that can be factorized towards a minimization. A isn't constant, B isn't either, the same for C and D. There are elements in the cyan group that have different values for at least one of the above variables. That means that no minimization is feasible for that group.

Another thing to remember is that for each valid group, for each power of 2 of elements that include, your minimized term will have as many less variables in it. I 'll explain it a bit more:
Take the green group for example. Your map has 4 variables. the green group has 2^2 elements. Thus the term that the group is minimized into will have 4-2=2 variables in its expression. Namely B and C.

A function f(A,B,C,D)=Σ(0,1) has one group with two (2^1) elements in it which will be minimized into a term with 4-1=3 terms. Indeed that term is A'B'C'.
The function f(A,B,C,D)=Σ(0,1,2,3,4,5,6,7) has one group with eight (2^3) elements in it and its term will have 4-3=1 variable, namely A'.


If you have a better understanding of the K-maps now, try to minimize the F' of your post #9.

P.S. It helps me very much when you colour your groups, because it tags them and I can refer to them very easily. Continue doing it.
 

Georacer

Joined Nov 25, 2009
5,182
Excellent! Now you nailed it!

One minute detail, just to be perfect: It's usually ok to draw the NOR gate as you did with the final one on the right, but to be clear, it's better in your final design to draw it as the ones on the left, with an OR gate and an inverter on top of it.

Now go to your other threads and correct any mistakes you have done in these K-maps.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Excellent! Now you nailed it!

One minute detail, just to be perfect: It's usually ok to draw the NOR gate as you did with the final one on the right, but to be clear, it's better in your final design to draw it as the ones on the left, with an OR gate and an inverter on top of it.

Now go to your other threads and correct any mistakes you have done in these K-maps.
Thank you.

Now I have started working on the problems again (had to sleep! :)). Seriously, it wouldn't have been possible without your help. Many thanks.

Regards
PG
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Hi

Could you please have a look on the attachment and help me with that query? It would be really kind of you. Thank you.

Regards
PG

PS: In the attachment, at the top, you can find the question statement.
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
It's a different grouping in the K-map. Instead of taking the group B'C to cover the terms m2 and m10, it groups vertically the terms m2, m6, m10 and m14.

Not really visible in the function expression, only in the K-map.
 
Top