# Minimize Two bit Multiplication in Binary function

the input are X=(x1,x0), Y=(y1,y0).

the output is Z=(z3,z2,z1,z0).

the component: Z=X*Y .

I got these simplified expressions by Karnaugh maps: (* = AND / + = OR / ~ = NOT )

z3=x1*x0*y1*y0

z2=x1*(~x0)*y1+x1*y1*(~y0)

z1=x1*(~y1)y0+x1(~x0)*y0+(~x1)*x0*y1+x0*y1*(~y0)

z0=x0*y0

now I want to minimize these 4 expressions with the less number of component using (AND/OR/NOT/NOR/NAND/XOR) every component have only 2 inputs.

z0 I am sure that it's minimized (it has only one component) and I think also z3 minimized.

can someone show me how to minimize z2 and z1 ?

this the best that I found but I need to minimize it for 7 gates or less (not 8)

• is this a homework question? Commented Dec 9, 2017 at 15:55
• yes it is homework Commented Dec 9, 2017 at 16:32
• Just as a note, I take it that you are looking to separately minimize each of the outputs, independently and not collectively. If that's wrong, you need to say so. But that said, take Z2, for example. What do you think the minimum gate arrangement might be? Have you even composed an example from your logic statement for it? (It's not hard to see an immediately obvious optimization there.) Put some effort into just that one and let's see what you can do here. I might help, then. But do note that these optimizations would be appropriate across all your outputs, too.
– jonk
Commented Dec 9, 2017 at 20:26
• @jonk I added a picture I want to minimize the gates to seven or less Commented Dec 9, 2017 at 21:51

In order for me to stay sane while I write this answer, I will use the nomenclature that I am more familiar with.

• $\bar x$ instead of ~x
• $xy$ instead of x*y
• $x+y$ instead of x+y
• $x_0$ instead of x0

can someone show me how to minimize z2 and z1 ?

Let's deal with $z_2$ first. \begin{align} z_2&=x_1(\bar x_0)y_1+x_1y_1(\bar y_0)\\ z_2&=x_1y_1(\bar x_0+\bar y_0)\\ z_2&=x_1y_1\overline{x_0 y_0}\\ \end{align}

Okay, now we're done with $z_2$

Time for $z_1$

\begin{align} z_1&=x_1(\bar y_1)y_0+x_1(\bar x_0)y_0+(\bar x_1)x_0y_1+x_0y_1(\bar y_0)\\ z_1&=x_1y_0(\bar y_1 + \bar x_0)+x_0y_1(\bar y_0 + \bar x_1)\\ z_1&=x_1y_0\overline{y_1x_0}+x_0y_1\overline{y_0x_1}\\ \end{align}

So let's recap what we actually have.

$z_3 = x_0x_1y_0y_1\\ z_2 = x_1y_1\overline{x_0 y_0}\\ z_1 = x_1y_0\overline{y_1x_0}+x_0y_1\overline{y_0x_1}\\ z_0 = x_0y_0$

Can you see any algebraic expression that is used several times in all 4 of them?

I can see that $x_1y_0$ and $x_0y_1$ is used twice in $z_1$. Let's introduce two signals. One called $A = x_1y_0$ and $B = x_0y_1$.

I can see that $x_1y_0$ and $x_0y_1$ makes $z_3$.

I can see that $z_0$ is a part of $z_2$.

Let's update what we got.

$z_3 = AB\\ z_2 = x_1y_1\overline{z_0}\\ z_1 = A\overline{B}+B\overline{A} = A \oplus B\\ z_0 = x_0y_0\\ A = x_1y_0\\ B = x_0y_1$

Let's count how many gates we got.

$z_3 = \text{ 1 AND gate}\\ z_2 = \text{ 2 AND gates, 1 NOT gate}\\ z_1 = \text{ 1 XOR gate}\\ z_0 = \text{ 1 AND gate}\\ A = \text{ 1 AND gate}\\ B = \text{ 1 AND gate}$

8, same as you. Which one do you think we need to work with in order to reduce the number of gates?

I think $z_2$, because that one has the most number of gates. The problem is clearly how $z_0$ is added into $z_2$.

So how can we rewrite $z_2=x_1y_1\overline{x_0 y_0}$?

\begin{align} z_2&=x_1y_1\overline{z_0}\\\\ z_2&=(x_1y_1)\overline{z_0}\\\\ z_2&=\overline{\overline{(x_1y_1)\overline{z_0}}}\\\\ z_2&=\overline{\overline{(x_1y_1)}+\overline{\overline{z_0}}}\\\\ z_2&=\overline{\overline{(x_1y_1)}+z_0}\\\\ \end{align}

That's better! $z_2$ now require only one NOR gate and one NAND gate. 2 gates rather than 3. Mission accomplished.

So for clarity, these are your final algebraic expressions that you want to use:

$z_3 = AB\\ z_2 = \overline{\overline{(x_1y_1)}+z_0}\\ z_1 = A \oplus B\\ z_0 = x_0y_0\\ A = x_1y_0\\ B = x_0y_1$

• Nicely handled, I think.
– jonk
Commented Dec 9, 2017 at 23:38
• I agree with @jonk, I think. Commented Dec 10, 2017 at 10:22
• @STD Is this the correct answer? Commented Dec 11, 2017 at 6:14