[oc] multiplier

[tom st denis <tomstdenis@yahoo.com>]

I was wondering what types of integer multipliers (i.e full n x n ->
2n) are typically used.

Off the top of my head I could imagine a parallel circuit that
computers n partials (by shifting the correct amount of bits) then
adding (i.e balanced tree form) the partials (anding out partials that
should not be there) in log2(n) steps.  So a 4x4 -> 8 multiplier for
let's say "a * b" would compute a, a<<1, a<<2, a<<3, then add the terms
(b&1?a:0)+(b&2?a<<1:0) to form one side of the tree, then
(b&4?a<<2:0)+(b&8?a<<3:0) to form the other half.  Finally add the two
terms together to form a the result in two cycles.

So a 1024x1024->2048 bit multiplier would require only 10 cycles
(assuming addition takes a single cycle) and tons of hardware.

Are there any better techniques (well I am sure there are) but could I
get any insight please?

Tom

__________________________________________________
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/