Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Napier's Bones versus Booth Encoding
21 views
Skip to first unread message
Quadibloc
Jun 15, 2014, 10:00:50 AM6/15/14
to
As many people here would know, Booth Encoding is a technique which allows the size of the Wallace Tree required to multiply numbers by a multiplier of a given length to be reduced by limiting the number of partial products required.
Instead of just multiplying the number by 0 or 1 to generate a partial product, multiply it by -2, -1, 0, 1, or 2, all of which can be done without carries (one can generate a term with error bits for the minus cases - or just do an end-around-carry, since one isn't propagating carries anyways, in this case to convert to two's complement from one's complement) and that way, one can use two multiplier bits per partial product by shifting offsets between digits.
There are various more sophisticated forms of Booth Encoding extant, but they require such things as computing 3 times the multiplicand, which involves carry propagation.
I was wondering if one could get more flexibility by trying to generate two partial products at once, thereby being able to again employ only easy multiples and yet encode not just four bits but maybe five.
And then it hit me. There is a table-driven algorithm possible that allows encoding *any arbitrary number of multiplier bits* into only two partial products. Depending on how big you want your table.
Without propagating any carries, in decimal, I can work out two numbers that will add up to 7 times 615379 by using the times table: 4032450 and 275196.
These are the tens digits and the units digits of the multiplication table entries for a multiplier of 7 and the digits of the multiplicand.
128K bytes of memory will contain a 256 by 256 multiplication table, and FF times FF is FE01.
Thus, with a table lookup for every 8 bits of the multiplicand, two input terms can be generated for *eight* bits of the multiplier, which *doubles* the efficiency achieved with Booth encoding!
And it's not as if you need an associative memory either, the two numbers being multiplied just index into the table.
I am not so presumptuous as to think that this is a *new* idea on my part; no doubt others have thought of it, and it has a name, but I haven't noticed anyone mentioning it.
John Savard
Instead of just multiplying the number by 0 or 1 to generate a partial product, multiply it by -2, -1, 0, 1, or 2, all of which can be done without carries (one can generate a term with error bits for the minus cases - or just do an end-around-carry, since one isn't propagating carries anyways, in this case to convert to two's complement from one's complement) and that way, one can use two multiplier bits per partial product by shifting offsets between digits.
There are various more sophisticated forms of Booth Encoding extant, but they require such things as computing 3 times the multiplicand, which involves carry propagation.
I was wondering if one could get more flexibility by trying to generate two partial products at once, thereby being able to again employ only easy multiples and yet encode not just four bits but maybe five.
And then it hit me. There is a table-driven algorithm possible that allows encoding *any arbitrary number of multiplier bits* into only two partial products. Depending on how big you want your table.
Without propagating any carries, in decimal, I can work out two numbers that will add up to 7 times 615379 by using the times table: 4032450 and 275196.
These are the tens digits and the units digits of the multiplication table entries for a multiplier of 7 and the digits of the multiplicand.
128K bytes of memory will contain a 256 by 256 multiplication table, and FF times FF is FE01.
Thus, with a table lookup for every 8 bits of the multiplicand, two input terms can be generated for *eight* bits of the multiplier, which *doubles* the efficiency achieved with Booth encoding!
And it's not as if you need an associative memory either, the two numbers being multiplied just index into the table.
I am not so presumptuous as to think that this is a *new* idea on my part; no doubt others have thought of it, and it has a name, but I haven't noticed anyone mentioning it.
John Savard
Terje Mathisen
Jun 15, 2014, 10:30:49 AM6/15/14
to
Quadibloc wrote:
> 128K bytes of memory will contain a 256 by 256 multiplication table,
> and FF times FF is FE01.
>
> Thus, with a table lookup for every 8 bits of the multiplicand, two
> input terms can be generated for *eight* bits of the multiplier,
> which *doubles* the efficiency achieved with Booth encoding!
>
> And it's not as if you need an associative memory either, the two
> numbers being multiplied just index into the table.
>
> I am not so presumptuous as to think that this is a *new* idea on my
> part; no doubt others have thought of it, and it has a name, but I
> haven't noticed anyone mentioning it.
Name: Table lookup?
> 128K bytes of memory will contain a 256 by 256 multiplication table,
> and FF times FF is FE01.
>
> Thus, with a table lookup for every 8 bits of the multiplicand, two
> input terms can be generated for *eight* bits of the multiplier,
> which *doubles* the efficiency achieved with Booth encoding!
>
> And it's not as if you need an associative memory either, the two
> numbers being multiplied just index into the table.
>
> I am not so presumptuous as to think that this is a *new* idea on my
> part; no doubt others have thought of it, and it has a name, but I
> haven't noticed anyone mentioning it.
I bet there was a bunch of old machines without HW multipliers which did
just this, probably based on bcd digits, i.e. 160 bytes (with 60 empty
slots) give you the regular multiplication table.
I don't see where Booth give you any additional gains though, please
explain!
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Quadibloc
Jun 15, 2014, 12:28:52 PM6/15/14
to
On Sunday, June 15, 2014 8:30:49 AM UTC-6, Terje Mathisen wrote:
> I bet there was a bunch of old machines without HW multipliers which did
> just this, probably based on bcd digits, i.e. 160 bytes (with 60 empty
> slots) give you the regular multiplication table.
> I don't see where Booth give you any additional gains though, please
> explain!
I thought I *did* explain.
> I bet there was a bunch of old machines without HW multipliers which did
> just this, probably based on bcd digits, i.e. 160 bytes (with 60 empty
> slots) give you the regular multiplication table.
> I don't see where Booth give you any additional gains though, please
> explain!
I see now where my scheme is impractical, though; it requires too many copies of the multiplication table.
You see, I am well aware of the IBM 1620 computer.
But I wasn't talking about using a multiplication table *to multiply*. I was talking about using a multiplication table _as a substitute for Booth encoding_.
A Wallace Tree is an efficient way to add a bunch of binary numbers. You can repeatedly reduce the numbers you have to add from three to two in carry-save adders without having to propagate carries.
Booth Encoding is a way to modify the multiplier so that the number of partial products you have to add is cut in half; this lets you get by with a smaller Wallace Tree. Fewer gates, less chip area.
What I was noting was that a multiplication table can let you transform *any number of multiplicand bits* into two partial products. Of course, the table size grows exponentially with the number of bits you so transform.
John Savard
0 new messages