Synchronous system

[electroRF]

Hi,

I'm trying to sketch a block diagram of the following system using discrete components (as counters, etc).

the output of this system would be
n: 1, 2, 3, 4, 5, 6 ....
n^2: 1, 4, 9, 16, 25, 36, ....

for getting n, you just use a counter.

but, how do you get n^2?

Thank you very much.


---- EDIT ----

In SW I could do the following:
if k'th bit in n is '1', I'd shift-left n by k.
then, I'd sum up all the shift results, to get n^2.

But -> How do you do that by HW?

Example:
if n = 1010
then
n^2 = 1010 << 1 + 1010 << 3

 

[Mike odom]

what is the n and n outputs? Digital, or analog (assuming digital but don't like to assume). If so, what is the max numbers... so we can determine how many bits...

 

[electroRF]

hi Mike.

n and n^2 are k-bit numbers (digital).

it was not specified in the question, but we can assume that k determines how long the outputs could grow.

i.e. for k = 20, the limit of the system would be
MAX(n^2) = 2^20 - 1

--> MAX(n) = sqrt(2^20 - 1)

 

[jrz126]

Easiest HW solution would be a lookup table implemented in read only memory.
the memory would be initialized to the address^2

 

[electroRF]

Hi jrz,
wow, that's a great solution.

I was hoping for an answer which doesn't use a look-up table.

As the shift-left suggestion I mentioned, but I don't know how to implement it in HW.

 

[WTP Pepper]

Depending on how many bits the input is, you could do it with combinational logic (could be messy) or you could also look at the CD4089.

 

[crutschow]

You could add the numbers together n number of times. For this you would need an adder with n^2 -1 bits. Thus the adder output would go to a D-register which is also one of the inputs to the adder with n being the other. A counter would perform the addition by clocking the D register n-1 times.

 

[electroRF]

Hi,

@crutschow
performing (n-1) add operations would be very inefficient.
Same as in SW, you wouldn't do (n-1) add operations, but you'd rather use log(n) shift-left operations.

How would you implement the following by HW?
if n = 1010
then
n^2 = 1010 << 1 + 1010 << 3

 

[crutschow]

I wasn't worried about efficiency, just a simple way to to the task.

Here's a shift-and-add scheme that should work to multiply any two numbers in n steps. You need one n-bit shift register and one 2n-bit shift register. You put the number into the n-bit shift-register LSB first. You put the second number (or same number if you are squaring) into the 2n-bit shift-register MSB first. You look at the last (LSB) bit of the first shift register. If it's 1 you add the contents of the 2n-bit shift register to a 2n-bit accumulator (D-latch) register, if it's a 0 you don't. Then you shift each shift-register one step in their respective registers and look at the last bit of the n-bit register (which is now second to the LSB). Again you add the shift register contents if it's a 1 and not if its a 0. Repeat this N times. The multiplied (or squared) number is now in the accumulator.

 

[Mike odom]

This is how it's done in hardware...
1. clear counter 2. enable counter for timing period 3. disable timer... you now have your count = n = multiplicand.
4. Load shift register with counter value = multiplier (note: since we're doing n² then multiplicand = multiplier). 5. Clear Accumulator (Accumulator must be x * 2 bits wide).
6. check shift register LSB. If 1, add multiplicand + accumulator register back into accumulator.
7. shift the Shift register once to the right, shift the accumulator once to the right.
8. Repeat 6-7 x times (x = number of bits in counter/shift register). 9. Shift the accumulator x more times to the right to resync MSB/LSB. Note: If the accumulator is larger than 2x bits, then you have to shift it that many more times. Results in accumulator = n².

 

[Mike odom]

note about the above... your algorithm shows shift lefts. You can do the above with shift lefts, but you check the MSB instead of the LSB.

 

[NorthGuy]

I would notice that n^2 = (n-1)^2 + (n-1) + n (Here ^2 stands for square)

Then at every change you just get (n-1)^2, which you already have on the second output, and add (n-1), which you already have on the first output, then you advance the first counter, so that it has n now on the first output, and, once it's done, you add this n to the second counter, so that now it holds (n-1)^2 + (n-1) + n = n^2.

 

[ChrisP58]

Probably the simplest would be to use a microcontroller. Doing shifts and adds, as well as something to control the sequence will take a small handful of chips. A uC would do it all with one chip.

Just choose a part with enough pins to output N and N^2.

 

[MikeMl]

Even simpler, just use a parallel multiplier with n fed to both inputs.

 

[electroRF]

I would notice that n^2 = (n-1)^2 + (n-1) + n (Here ^2 stands for square)

Then at every change you just get (n-1)^2, which you already have on the second output, and add (n-1), which you already have on the first output, then you advance the first counter, so that it has n now on the first output, and, once it's done, you add this n to the second counter, so that now it holds (n-1)^2 + (n-1) + n = n^2.

North Guy,
Thank you very much.

I tried implementing your solution in HW.

Would you do it like that?

 

[electroRF]

This is how it's done in hardware...
1. clear counter 2. enable counter for timing period 3. disable timer... you now have your count = n = multiplicand.
4. Load shift register with counter value = multiplier (note: since we're doing n² then multiplicand = multiplier). 5. Clear Accumulator (Accumulator must be x * 2 bits wide).
6. check shift register LSB. If 1, add multiplicand + accumulator register back into accumulator.
7. shift the Shift register once to the right, shift the accumulator once to the right.
8. Repeat 6-7 x times (x = number of bits in counter/shift register). 9. Shift the accumulator x more times to the right to resync MSB/LSB. Note: If the accumulator is larger than 2x bits, then you have to shift it that many more times. Results in accumulator = n².

wow mike, thank you very much for this professional solution!

I got one thing i didn't understand - how do you get n^2 by shifting right the accumulator result?

 

[Mike odom]

wow mike, thank you very much for this professional solution!

I got one thing i didn't understand - how do you get n^2 by shifting right the accumulator result?

It doesn't matter if you shift left or right, as long as you do it the exact number of times as you have bits in the register. Every time you shift, you are weighting the added values by the multiplier bit position. When you do math long hand, you're actually shifting right, you work from right to left, you are moving your 'pointer' left, so the data you are working with is actually shifting right...

So you start with the LSB, if a '1', you add that value in, then you shift the result right, and the multiplier... if the new LSB bit is a '1', and you add in your value again, that value adds twice the value to the result as the previously added amount, because the result has been shifted right... and the bit in the multiplier has a weight of twice the previous LSB bit... so like in long hand math, every time you shift your pointer left, the intermediate result shifts left also, giving a weight of 10x to that value, but if you look at your old data in relation to the new data, it has shifted right! Since we're not shifting our multiplicand, we have to shift our result the other direction.

When you do left shifts, you start with the MSB, as that bit has the most weight, and if you're shifting left, then what you're adding in has less weight in the result than the previously added...

 

[NorthGuy]

Would you do it like that?

That's a beatiful hardware implementation of my idea