Best way to carry on 2-input architecture?
nisse at lysator.liu.se
Wed Aug 20 20:02:26 UTC 2014
"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
> 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
but a bit too general for me to digest now. An easier description at
> 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
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel