# Find x cubed with half adder

My excercise is the following:

Make a circuit which outputs X^3 of two bit input of X.
Use the lowest number of HALF ADDERS as you can.


I don't really understand how to compute x cubed with half adders.

Any hints or help is appriciated.

• That's a good exercise! I don't want to just give you the answer, I think it's better to work it out for yourself however I'll guide you a bit (no pun) in the direction. Try to write a simple binary multiplication on paper. For example 110 x 101 = 110 + 0000 + 11000. Did you notice something? The results you get for each stage of the multiplication are either 110 (shifted by the "weight" of the number multiplying it) or 0. – user34920 Jun 28 '14 at 19:52
• @user34920 thank you, I did want a hint. I'll try now. – Alan Jun 28 '14 at 19:54
• @user34920 I do notice that whatever multiplication I make there are only 2 results possible. However, I still don't know what to do with that fact. – Alan Jun 28 '14 at 20:00
• Here is a link that might help... fullchipdesign.com/binary_multiplier_digital.htm – user34920 Jun 28 '14 at 20:13
• @user34920. thank you. A full answer would be appriciated, since I didn't come with an answer. – Alan Jun 28 '14 at 21:33

The input of the circuit is a 2 bit number (max value = 3) and the hence the maximum value at output will be 27 (a 5 bit number). The truth table of the circuit is:

$$\begin{array}{cccccccl}&\mathbf{x} & &\mathbf{b} &\mathbf{a} & &\mathbf{Y_4} &\mathbf{Y_3} &\mathbf{Y_2} &\mathbf{Y_1} &\mathbf{Y_0} & &x^3\\ \hline &\style{color:red}{0} &\rightarrow &0 &0 & &0 &0 &0 &0 &0 &\rightarrow &\style{color:red}{0}\\ &\style{color:red}{1} &\rightarrow &0 &1 & &0 &0 &0 &0 &1 &\rightarrow &\style{color:red}{1}\\ &\style{color:red}{2} &\rightarrow &1 &0 & &0 &1 &0 &0 &0 &\rightarrow &\style{color:red}{8}\\ &\style{color:red}{3} &\rightarrow &1 &1 & &1 &1 &0 &1 &1 &\rightarrow &\style{color:red}{27}\\ \hline & & & & & &ab &b &0 &ab &a\\ \hline \end{array}$$

The 'carry out' of an half adder, with inputs a and b, will be $ab$. So circuit can be implemented as given below.

$\mathtt{ba}$ is the input and $\mathtt{Y_4Y_3Y_2Y_1Y_0}$ is the output ($\mathtt{Y_0}$ is the LSB).

Let the LSB of the number be $a$ and MSB be $b$. Then the number is $2b+a$ where, $a,b\in\{0,1\}$.

$$(2b+a)^3=8b^3 + 12ab^2+6a^2b+a^3$$

Since $a,b\in\{0,1\}, \ a^3=a^2=a$ , $b^3=b^2=b$ and $a\times b = a\ AND\ b = ab$.

$$\therefore (2b+a)^3=8b+18ab+a$$ $$=16ab+8b+2ab+a$$ $$=2^4\times ab+2^3\times b+2^2\times 0+2^1\times ab+2^0\times a$$

From this we can say that,

• the $0^{th}$ bit (LSB) of answer is $a$
• $1^{st}$ and $4^{th}$ bits are $ab$
• $2^{nd}$ bit is $0$
• $3^{rd}$ bit is $b$

The 'carry out' of an half adder, with inputs $a$ and $b$, will be $ab$. So circuit can be implemented as given below.

$\mathtt{ba}$ is the input and $\mathtt{Y_4Y_3Y_2Y_1Y_0}$ is the output ($\mathtt{Y_0}$ is the LSB).