# Homework Help: Implementing a function using an adder and a multiplier

Tags:
1. Feb 27, 2017

### timnswede

1. The problem statement, all variables and given/known data
http://imgur.com/a/3Cn7c
Z is an unsigned 9 bit number and X is an unsigned 3 bit number. The only available components are an 8 bit adder and a 4-bit x 4-bit multiplier.
c.) We have a single 8 bit adder and a single 4-bit x 4-bit multiplier. We would like to implement the function Z=kX^2 where k is a constant. What is the maximum possible for k that can be achieved?

2. Relevant equations
No equations

3. The attempt at a solution
My thinking was that with the multiplier we can get 4X^2 (X2 X1 X0 0)*(X2 X1 X0 0). Then with adder we can add that with itself to get 8X^2 so the largest value for k is 8? Is my logic correct?

2. Feb 27, 2017

### .Scott

X is a 3-bit number, so max(X) is 7, squared it 49.
Z is unsigned 9-bit, so max(Z) is 511.
511/49 is less than 11, so k cannot be greater than 10.

Can you think of a solution for Z=10X*X ?

Bear in mind that a multiply by a power of 2 is free. All you need to do is wire things up for a bit shift.

3. Feb 27, 2017

### timnswede

Ok the logic for why the max is 10 makes total sense to me, but I'm not sure how I would implement that. Since I could either get 2x^2 or 4x^2 from the output. But I don't think I could get the 10x^2 required from the adder could I?

4. Feb 28, 2017

### rcgldr

Does the 8 bit adder have a carry output to go into a ninth bit? If not, what's the point in Z having 9 bits?

5. Feb 28, 2017

### timnswede

Yes I tried to put a picture, but it wouldn't show up. The 8 bit adder has a carry in and carry out as the 9th bit

6. Feb 28, 2017

### .Scott

Here's the final hint: You want to get both 8x^2 and 2x^2 from the output of the multiplier.

7. Feb 28, 2017

### rcgldr

I can see getting 2x^2 or 4x^2 from the multiplier, but not 8x^2.

Last edited: Mar 1, 2017
8. Feb 28, 2017

### .Scott

This isn't a software problem. It's an EE problem.
You aren't programming these things, you're wiring them into a circuit.

I said I wasn't going to give anymore hints, but I think the OP is past this point.
Lets say I have a 4-bit input, represented by nodes I0 to I3. And I want to generate a 20-bit output with a value of 1024 times the input value. The output is represented by nodes O0 to O19. So I start by wiring nodes O0 to O9 to ground. Then O14 to O19 to ground. Then I0 to I3 to O10 to O13, respectively.

Get the picture?

Oh yes, and please note that my gate count is zero.

9. Feb 28, 2017

### rcgldr

OK, but the way I see this, the circuit isn't getting 8x^2 from the multiplier. Instead the two inputs to the adder could be x^2 "shifted left" 1 bit (2x^2) and x^2 "shifted left" 3 bits (8x^2), with the most significant bit of 8x^2 going to the carry input of the 8 bit adder.

Last edited: Mar 1, 2017
10. Mar 1, 2017

### .Scott

Here's how I see it:

Input nodes X0 to X2. Output nodes Y0 to Y8. Y=10X^2.

Well all agree on the first step:
Tie X0 to X2 into the multiplier inputs Ma0 to Ma2 and Mb0 to Mb2. Tie Ma3 and Mb3 to ground.

Now you can call the output of the multiplier X^2 or 2X^2 or 4X^2 or 8X^2 - or any combination.

I think we all agree, on the second step:
Tie multiplier outputs to adder inputs. M0 to M5 to Aa0 to Aa5 and Ab2 to Ab7. Tie all other adder inputs to ground.
Exactly how you describe the adder input and outputs is optional. I treated this as 8X^2+2X^2=10X^2. Equally valid would be 4X^2+X^2=5X^2.
In either case, you don't need to use the carry bit.

11. Mar 1, 2017

### rcgldr

Max value for X == 7 => X^2 == 49 => 8X^2 == 352, which will need the adder's carry (ninth) bit).

12. Mar 1, 2017

### .Scott

8X^2 ranges from 0 to 392, in steps of 8, so you need 6 bits. 2X^2 ranges from 0 to 98 in steps of 2, so you need 6 bits. Combined: 10X^2 ranges from 0 to 490 in steps of 2, so you need 8 bits (no carry), the units position is always 0.

I'm doing everything I can to avoid simply blurting out the answer.

13. Mar 1, 2017

### rcgldr

That will produce 5 X^2. I'm assuming the goal is to be produce 10 X^2 in the 9 bit combination of adder carry out and adder 8 bit sum.

This was a mistake, I struck it out in my prior post.

Last edited: Mar 1, 2017
14. Mar 1, 2017

### .Scott

There is no difference between 5X^2 and 10X^2. If you think that 5X^2 does not require the carry (which it does not), then you should easily see that the carry is not required for 10X^2. The only problem with using the carry is that is the question does not state that it is available.

15. Mar 1, 2017

### rcgldr

From the op, post #5:

Based on post #5, I assume the 9 bit output is adder carry + adder 8 bit sum, and that shifting the output left 1 or more bits to get sum * power of 2 is not the goal. With this limitation, generating 8 X^2 isn't an issue, but I don't know about 10 X^2, with only a single multiply and single add allowed, even though 10 X^2 fits in 9 bits.

16. Mar 2, 2017

### .Scott

You have 9 output nodes O0 to O9. Tie O0 to ground.

17. Mar 2, 2017

### rcgldr

It wasn't clear to me if this would be allowed, or if the output had to be the carry bit and 8 bits from the adder sum.