Best way to carry on 2-input architecture?

[Niels Möller]

"Wesley W. Terpstra" <wesley at terpstra.ca> writes:

>> But maybe you can do a circuit for mulhi which is significantly simpler
>> than for a widening multiplication, because you only need to collect the
>> carry out from the low partial products? Something like a Wallace tree
>> where you drop the low output bit from all the half and full adders of
>> the low product half.
>
> If you figure out a way to do this, please let me know.
>
> Personally, I don't see how this could be done. The Wallace tree can
> never reduce you to less than two rows. So, you still have to do the
> full adder to find the carry for the lower half.

Hmm. I'd have to work out a small example to see if I can make sense of
this.

> Don't forget that ASICs do not use ripple adders. They use Kogge-Stone
> adders, or a variation with similar circuit depth,

Cool. This is way beyond what I was tought in the basic digital
electronics course at the university...

Original paper at
http://www.acsel-lab.com/Projects/fast_adder/references/papers/Kogge-Stone-73.pdf,
but a bit too general for me to digest now. An easier description at
http://robey.lag.net/2012/11/14/how-to-add-numbers-2.html.

> So, for a 64x64 multiplier, the circuit starts with 1 level of 64x64
> AND gates, followed by 8 levels of 3:2 Wallace reduction, followed 6
> levels of a KS adder.

Ok, so it really is practical way to do an n=64 multiplier of this size
as a n^2 size combinatorial circuit, and then you split it into stages
at will if it turns out the propagation delay is larger than the clock
cycle.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.