4 bit binary number multiplier by 3 (mod 16)

Question

I have a question in a past paper which asks to design as a minimised sum of products, and using only NAND gates, a circuit which takes 4 bit binary input and multiplies that number by 3 (mod 16)

Here is the truth table I have derived

Inputs    Outputs
w x y z | a b c d
0 0 0 0 | 0 0 0 0 
0 0 0 1 | 0 0 1 1
0 0 1 0 | 0 1 1 0
0 0 1 1 | 1 1 0 0 
0 1 0 0 | 1 0 0 0
0 1 0 1 | 1 1 1 0
0 1 1 0 | 0 1 0 0 
0 1 1 1 | 1 0 1 0
1 0 0 0 | 0 0 0 0 
1 0 0 1 | 0 1 1 0 
1 0 1 0 | 1 1 0 0 
1 0 1 1 | 0 0 1 0 
1 1 0 0 | 1 0 0 0 
1 1 0 1 | 1 1 1 0 
1 1 1 0 | 0 1 0 0 
1 1 1 1 | 1 0 1 0

From here I have created 4 Karnaugh Maps:

wx|yz|00 01 11 10
_____|___________
00   |0  0  1  0
01   |1  1  1  0
11   |1  1  1  0
10   |0  0  0  1
(a)
wx|yz|00 01 11 10
_____|___________
00   |0  0  1  1
01   |0  1  0  1
11   |0  1  0  1
10   |0  1  0  1
(b)
wx|yz|00 01 11 10
_____|___________
00   |0  1  0  1
01   |0  1  1  0
11   |0  1  1  0
10   |0  1  1  0
(c)
wx|yz|00 01 11 10
_____|___________
00   |0  1  0  0
01   |0  0  0  0
11   |0  0  0  0
10   |0  0  0  0
(d)

Here are my questions: Will there be any don't care conditions in these Karnaugh Maps. how do I tell if there are or not?

Also, this will give me four boolean expressions resulting in 4 independent circuits. Do I need to connect them together as one big circuit somehow?

Finally, is there a certain mechanical procedure I can apply to the final boolean expressions in order to convert then to NAND Gates?

Answer 1

One way:

You have w,x,y,z. Use four NAND gates with the inputs connected together as inverters and so generate !w, !x, !y and !z.

Use 4-input NAND gates to implement your Karnaugh maps for a, b, c, and d - wherever there's a 1 in the map, use a gate to generate a 1 by connecting its inputs to w, x, y, z, !w, !x, !y and !z as directed by the map.

There will be as many gates as 1's in the map, so you will need to invert their outputs and NAND them all together to get !a, !b, !c and !d, (yes, you may have to invert yet again).