Determine no. of '1's in a 4-bit input

[circuitforfun]

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.

 

[Laplace]

What if you did a K-map in stages? For example, do a map for A & B, then another one for C & D, then combine those outputs together into another map.

 

[circuitforfun]

What if you did a K-map in stages? For example, do a map for A & B, then another one for C & D, then combine those outputs together into another map.

Thank you for your reply. But when I split the k-map into 2 stages, each function cannot be further simplified as well.

I wonder if my approach in the beginning is wrong. Should I treat each bit as input A,B,C,D respectively? Is there any other way to do this question?

 

[(*steve*)]

Perhaps you should draw up a simple truth table for a pair of bits.

Then imagine you do this for two pairs of bits and draw up another truth table to generate the overall output from these two intermediate outputs.

Now see if you notice anything...

 

[circuitforfun]

Perhaps you should draw up a simple truth table for a pair of bits.

Then imagine you do this for two pairs of bits and draw up another truth table to generate the overall output from these two intermediate outputs.

Now see if you notice anything...

Do you mean each pair of bits (2 bits) form a relationship of XOR (Exclusive OR)?

 

[(*steve*)]

That would be a great observation.

What about how you combine these exclusive-or-ed outputs to get a final result?

Exclusive-OR is not handles well by kernough maps. You kinda just have to recognise them. See here.

 

[Laplace]

FYI: It takes five 2-input NAND gates to make one 2-input XOR gate.