# Determine whether no. of '1's in a 4-bit input is odd or even

Discussion in 'Homework Help' started by circuitforfun, Oct 17, 2013.

1. ### circuitforfun Thread Starter New Member

Oct 16, 2013
3
0
When given a 4-bit input, determine whether the number of '1's in the input is odd or even. For example, if input is 0110, output is 0. if input is 0111, output is 1.

(a) simplify the Boolean logic expression using K-map.
(b) draw the digital circuit using only NAND gates

I tried to draw the truth table and then express the logic expression in sum-of-product form:

A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AB'C'D' + AB'CD + ABC'D + ABCD'

I tried k-map but it cannot be simplified. Is there anything I can do to simplify it?

Hope somebody can help me with this. I would be very thankful if somebody could help me. Thank you for your attention. Look forward to your reply.

2. ### WBahn Moderator

Mar 31, 2012
23,556
7,208
Can you figure out out to do it with three 2-input XOR gates?

Do you know how to implement an XOR gate using four 2-input NAND gates?

The K-map looks like it can't be simplified because you are looking at it from the perspective of "simplifying" it by combining minterms via products (i.e., logical AND). Instead, you want to look at combining minterms via XOR. It's not obvious, but it can be done.

Similarly, you want to "simplify" your Boolean expression by identifying XOR terms.

3. ### circuitforfun Thread Starter New Member

Oct 16, 2013
3
0
At the moment I only know how to implement XOR gate using 2 NOT, 2 AND , 1 OR gate, then I know how to use 1 NAND to make NOT, 2 NANDs to make AND, 3 NANDs to make OR. I can't figure out how to implement XOR using 4 NANDs.

If the question only involves 2-bit, then I can understand the 2 bits are in a relationship of XOR. But when it comes to 4-bit, I can only perceive it as
(A XOR B) XOR ( C XOR D) (don't know if it's correct) . Then I don't know what to do next.

I am sorry if I have made any silly statements because I am not familiar with Boolean Algebra. Could you give more hints on this question please?

4. ### WBahn Moderator

Mar 31, 2012
23,556
7,208
So let's put that on a shelf. You know how to make an XOR using a bajillion NAND gates (well, okay, nine). As long as you know how to do it with NAND gates, we don't need to be concerned with how many for this problem. We can revisit it later.

Well, then determine it is correct!

The nice thing about most engineering fields is that you can verify the correctness of the result from the result itself. Make a truth table and make a column for (A XOR B) and a column for (C XOR D). Then make the final output column the XOR of those two. Is it a 1 if and only if {A,B,C,D} have an odd number of 1s? If so, it is correct and if not, it is not correct. Or turn the crank on the Boolean algebra machine (which is a good, and fairly easy, exercise anyway).

Now, let's assume that it is correct (I will leave it to YOU to verify one way or the other). Could you implement it using just NAND gates?

Don't worry about silly statements. Heck, making a silly statement is often the best way for us to zoom in and identify where you might be making a mistake. The other really important thing is to show your work when and were feasible.

5. ### circuitforfun Thread Starter New Member

Oct 16, 2013
3
0
Thank you for your reply. You have led me to think and understand more about the problem.

Below is what I have done:

Let X = (A XOR B), Y = (C XOR D)
I drew X, Y and X XOR Y and found that it's true. odd + odd = even, even + even = even. Only odd+even OR even+odd = odd.
Also, I noticed that many combinations were the same. e.g. x=1,Y=1 appeared 4 times. According what I have learnt, G+G = G.
So I expressed the truth table in Sum-of-Product form, after simplification,
I got:
X'Y + XY' , which is X XOR Y

With the help of wikipedia, I learnt how to implement XOR using 4 NAND gates and tried to understand why 4 NAND gates is ok, using DeMorgan's Theorem.

I have attached what I drew. Please kindly take a look to see if it's correct.(My drawing is quite poor though )

Is it already the simplest expression? Then what about the K-map?

Thank you again for your help and patience

File size:
306.4 KB
Views:
62
6. ### WBahn Moderator

Mar 31, 2012
23,556
7,208
And that, my friend, is the whole goal of this forum. You are doing great.

Your circuit with twelve NAND gates is correct. I doubt if it can be simplified much more under the constraint of using 2-input NAND gates.

Analyzing the 4 NAND circuit to verify that it is correct is pretty straightforward. Coming up with the circuit in the first place is anything but obvious. It's a pretty elegant circuit, in my opinion.

As for the K-map, they aren't usually that helpful when XORs get involved. Yes, you can see the checkerboard patterns and subpatterns and make sense of them with enough effort, but unless you do a lot of it, I don't think it becomes very natural. What is valuable is to recognize that when you do start seeing checkboard patterns, it might be worthwhile looking for ways to make XORs do some of the work.