Implementing a function using an adder and a multiplier

[timnswede]

Homework Statement

http://imgur.com/a/3Cn7c [/B]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?

Homework Equations

No equations

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?

 

[.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.

 

[timnswede]

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.

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?

 

[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?

 

[timnswede]

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?

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

 

[.Scott]

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?

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

 

[rcgldr]

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

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

 

[.Scott]

I can see getting 2x^2 or 4x^2 from the multiplier, but not 8x^2. The adder will need to be used more than once to get 10x^2.

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.

 

[rcgldr]

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

You aren't programming these things, you're wiring them into a circuit.

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.

 

[.Scott]

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.

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.

 

[rcgldr]

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.

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

 

[.Scott]

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

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.

 

[rcgldr]

Tie multiplier outputs to adder inputs. M0 to M5 to Aa0 to Aa5 and Ab2 to Ab7. Tie all other adder inputs to ground.

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.

most significant bit of 8x^2 going to the carry input of the 8 bit adder.

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

 

[.Scott]

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.

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.

 

[rcgldr]

The only problem with using the carry is that is the question does not state that it is available.

From the op, post #5:

The 8 bit adder has a carry in and carry out as the 9th bit

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.

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.

 

[.Scott]

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.

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

 

[rcgldr]

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

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.