Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #29373

Re: FFT Speeds

Show all headers | View raw

On 2.4.20 21:16, Rick C wrote:
> On Thursday, April 2, 2020 at 8:02:57 AM UTC-4, Richard Damon wrote:
>> On 4/1/20 12:32 PM, Clive Arthur wrote:
>>>
> <snipped>
>>>
>>> Probably a dumb question, I'm no FPGA expert, but for a fixed-point FFT,
>>> could one use multiple shift and add multipliers instead of one fast
>>> hardware multiplier?  Roughly how many shift-add multipliers could you
>>> fit in the same space as a fast multiplier?
>>>
>>> I use a 128 point FFT for a comms system, and a dsPIC handles this
>>> quickly enough with it's two hardware multipliers and ancillary logic,
>>> but I've wondered if an FPGA with lots of parallel shift-add multipliers
>>> might be quicker.
>>>
>>> In my application, I can't use FPGAs with inbuilt processors or
>>> multipliers.
>>>
>>
>> Going back to this basic question, If I presume you are asking not about
>> the fairly limited number hard core multipliers that many FPGAs have
>> included, but about implementation in the FPGA fabric, and are comparing
>> one design which has a full tree implemented in parrallel, and can run
>> at a throughput of 1 multiply per cycle (it may take several cycle to
>> get a new result, but a new multiply can be done every cycle) verse an
>> implementation that uses reduced hardware but serially iterates the
>> answer in N cycles, my first impression is that the additional control
>> mechanisms to iterate probably take more logic than the fully parallel
>> solution and thus costs space, and thus has a lower throughput for a
>> given number of logic cells dedicated to multipliers. Someone would
>> really need to design this to be sure. Maybe the fact that the sequencer
>> could drive many serial multipliers might make a difference.
> 
> I have designed shift/add multipliers and the control logic is not much.  There is a log2(N) bit counter and minimal other logic.  The shift/add multiplier only works with unsigned multipliers (or is it the multiplicand?) so there needs to be a 2's complement before and after the multiplier.  I'm pretty sure the Booth's algorithm handles sign automagically, but I won't swear to it.  I did this over a decade ago.  I'm pretty sure if you are doing a bunch of multipliers the shift/add uses more real estate for the same throughput, but I don't recall the details of modified Booth's so I can't say for sure.


Booth's algorithm does handle signed operands in two's complement notation.

-- 

-TV

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-30 12:11 -0700
  Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-03-30 21:50 +0200
    Re: FFT Speeds Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-03-31 09:33 +0200
  Re: FFT Speeds dalai lamah <antonio12358@hotmail.com> - 2020-03-31 16:14 +0200
    Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 12:07 +1100
      Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-03-31 18:41 -0700
        Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 13:40 +1100
          Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-31 20:53 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 18:45 +1100
            Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-01 17:32 +0100
              Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-01 12:20 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-02 09:40 +0100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 02:00 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-02 12:50 +0300
              Re: FFT Speeds Richard Damon <Richard@Damon-Family.org> - 2020-04-02 08:02 -0400
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 11:16 -0700
                Re: FFT Speeds Tauno Voipio <tauno.voipio@notused.fi.invalid> - 2020-04-02 21:33 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 12:39 -0700
                Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-02 20:33 -0700
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 20:43 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-03 09:34 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:29 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:23 +0200
                Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-03 21:48 +1100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 10:38 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-04 11:50 +0100
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 09:12 +0200
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:30 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:39 +0200
          Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-01 10:43 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-02 13:26 +1100
      Re: FFT Speeds Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2020-04-01 17:27 -0400

csiph-web