Den søndag den 4. september 2016 kl. 00.10.56 UTC+2 skrev rickman:
On 9/3/2016 8:46 AM, lasselangwadtchristensen_at_gmail.com wrote:
Den lørdag den 3. september 2016 kl. 03.45.13 UTC+2 skrev rickman:
On 9/2/2016 8:08 PM, lasselangwadtchristensen_at_gmail.com wrote:
Den lørdag den 3. september 2016 kl. 01.37.56 UTC+2 skrev rickman:
On 9/2/2016 4:01 PM, lasselangwadtchristensen_at_gmail.com wrote:
Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:
On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:
Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev
On 9/1/2016 4:24 PM, Tim Wescott wrote:
On Thu, 01 Sep 2016 13:19:09 -0700, lasselangwadtchristensen
Den torsdag den 1. september 2016 kl. 21.53.33 UTC+2 skrev
There's a method that I know, but can't remember the
name. And now I want to tell someone to Google for it.
It basically starts with the notion of multiplying by
shift-and-add, but uses the fact that if you shift and
then either add or subtract, you can minimize "addition"
I.e., 255 = 256 - 1, 244 = 256 - 16 + 4, etc.
That's it. Thanks.
That is very familiar from college, but I don't recall the
utility. It would be useful for multiplying by constants, but
otherwise how would this be used to advantage? It would save
add/subtract operations, but I can't think of another situation
where this would be useful.
If the algorithm is doing an add and shift, the add does not
increase the time or the hardware. If building the full
multiplier, an adder is included for each stage, it is either
used or not used. When done in software, the same applies. It
is easier to do the add than to skip over it.
you only need half the stages so it is half the size* and the
critical path through your adders are only half as long
I think you need to look at the algorithm again. The degenerate
case is a multiplier with alternating ones and zeros. An add or
subtract is needed at each 1->0 or 0->1 transition. Since every
bit is a transition you still need an adder/subtractor for every
Of course you could add logic to detect these cases and do fewer
adder ops, but then that is not Booth's algorithm anymore and is
much more complex. Booth's algorithm looks at pairs of bits in the
multiplier, this would require looking at more bits.
you are right, I was thinking of "modified Booth" it looks at 3 bits
at a time,
If you are thinking in terms of constant multiplication then again,
this is a modified method that combines Booth's with straight
* you need a few multiplexors to choose between x1 and x2,
subtract is invert and carry in
Multiplexers are not low cost in any sense in many technologies,
but it doesn't matter. Booth's algorithm doesn't use
may not be low cost, but compared to a full adder?
In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.
Because there is extra carry logic in the LC one bit of an adder is the
same logic as one bit of a multiplexer. The only disadvantage of an
adder is the carry propagation time, but they don't cascade, properly
designed you end up with one ripple cascade through one adder and then
the other logic delays as the adders all cascade in parallel.
sure most fpgas have fast carry chains or build in multipliers so hand
coding "fancy" multiplier structures might not come out ahead
and since the inputs come from the multiplicand and the multiplier
not from other intermediate results it shouldn't be in the critical
I don't see how you use multiplexers instead of adders. If the
multiplier changes from one calculation to the next you need adders in
every position. If the multiplier is fixed the combinations of sums is
fixed and no multiplexers are needed.
with a regular multiplier you have to go through N layers of adders
with a modified Booth you only have to go through N/2 adders
and N/2 multiplexers which have the same delay... PLUS the selectable
inverter which may or may not be combined with the adder. What's the
the multiplexers get their input from the multiplicant not the output
of the previous adder
Look at your diagram again. The multiplexer is muxing the output of the
previous stage or the output of the stage prior to that if the previous
stage is skipped. The multiplicand is the other input to the adder and
the control signal is derived from the multiplier which means there is
an added level of delay into the first stage with then has to ripple
through the entire structure. The multiplexers *must* be in the path of
the multiplexers can be moved to multiplicand, adding zero is the same as skipping
implementable in an FPGA using the carry chain. Without carry chain the
adds get much slower and/or use twice as much space. The decoders and
It might be possible to use the carry chain across the adds. This would
be difficult to code in a way that is implemented with carry chains.
using 2N FFs for every stage. In that case the multiplier would also
the fabric typically. I think this would only be useful in an ASIC.