Working out what's possible and what's not in DSP

Hi all,

So, the background to this is that it's 11 years since I finished undergrad
DSP, and haven't touched it since (RF and microwave hardware is my day
job).  Consequently, I'm very rusty on the theory and extremely ignorant of
the working practicalities of DSP.  Oppenheimer and Schaeffer is on my
desk, but it just gives me a headache.

The scenario is very basic: a time domain waveform (sometimes infinite,
sometimes less than 1 microsecond, sometimes in between) that I need to do
an FFT on to find the frequency components.

I know some of the boundary conditions:
- The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
higher, nothing lower
- I need to bin the FFT down to approx 1 kHz resolution
- It needs to happen in real time (or very close to)

My question is: is this possible?  If so, what sort of parameters will I
need (FFT length, memory size, clock speed, particular DSP chips to
avoid/pursue)?  

If any of the boundary conditions change, how will that affect things?  I'm
sure there'll be some kind of trade-off between frequency and resolution
and processing time/memory and input waveform length.  I know higher
frequency components need faster clocks, but what about things like the
trade off between processing time and chip/memory size and power
dissipation?

Right now I'm not even sure what to put into Google, so any guidance is
greatly appreciated.

Cheers,

Dave

On 19 Des, 13:51, "DavidE" <enchelmaier@n_o_s_p_a_m.ieee.org> wrote:


> The scenario is very basic: a time domain waveform (sometimes infinite,
> sometimes less than 1 microsecond, sometimes in between) that I need to do
> an FFT on to find the frequency components.

'Infinite' what? Duration? Amplitude?

> I know some of the boundary conditions:
> - The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
> higher, nothing lower

Really? That's a first. What is outside that
band might not be very interesting to you, but
it will be there.

> - I need to bin the FFT down to approx 1 kHz resolution

'Need'? Or want? Why? That would be 40 million
data points of interest, twice that for DFT symmetry
and another 40 mill to cover the DC-20 MHz band.

>> 100 million computed DFT points, in total. Why?

> - It needs to happen in real time (or very close to)

Even if you can justify the cost, computing that
kind of DFTs will take on the order of seconds.
While a DSP chip or CPU might work with several
GHz clock frequency, memory managment and data
shuffling will take time.

> My question is: is this possible? &#4294967295;If so, what sort of parameters will I
> need (FFT length, memory size, clock speed, particular DSP chips to
> avoid/pursue)?
>
> If any of the boundary conditions change, how will that affect things? &#4294967295;I'm
> sure there'll be some kind of trade-off between frequency and resolution
> and processing time/memory and input waveform length. &#4294967295;I know higher
> frequency components need faster clocks, but what about things like the
> trade off between processing time and chip/memory size and power
> dissipation?
>
> Right now I'm not even sure what to put into Google, so any guidance is
> greatly appreciated.

The spec doesn't make sense. If you want help,
attempt to describe what you want to do, and
somebody might help out with a way of achieving it.

Rune

On Dec 19, 7:51&#4294967295;am, "DavidE" <enchelmaier@n_o_s_p_a_m.ieee.org> wrote:
> Hi all,
>
> So, the background to this is that it's 11 years since I finished undergrad
> DSP, and haven't touched it since (RF and microwave hardware is my day
> job). &#4294967295;Consequently, I'm very rusty on the theory and extremely ignorant of
> the working practicalities of DSP. &#4294967295;Oppenheimer and Schaeffer is on my
> desk, but it just gives me a headache.
>
> The scenario is very basic: a time domain waveform (sometimes infinite,
> sometimes less than 1 microsecond, sometimes in between) that I need to do
> an FFT on to find the frequency components.
>
> I know some of the boundary conditions:
> - The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
> higher, nothing lower
> - I need to bin the FFT down to approx 1 kHz resolution
> - It needs to happen in real time (or very close to)
>
> My question is: is this possible? &#4294967295;If so, what sort of parameters will I
> need (FFT length, memory size, clock speed, particular DSP chips to
> avoid/pursue)?
>
> If any of the boundary conditions change, how will that affect things? &#4294967295;I'm
> sure there'll be some kind of trade-off between frequency and resolution
> and processing time/memory and input waveform length. &#4294967295;I know higher
> frequency components need faster clocks, but what about things like the
> trade off between processing time and chip/memory size and power
> dissipation?
>
> Right now I'm not even sure what to put into Google, so any guidance is
> greatly appreciated.
>
> Cheers,
>
> Dave

Is your signal periodic or not ?

For an aperiodic signal doing spectral analysis with this much
precision does not make any sense at all.

For periodic signal your first step would be to find a period very
precisely with the least amount of data, and FFT is highly NOT
recommended for this purpose
(Despite what Oppenheimer and Schaeffer and some folks in this group
might tell you...)

On Mon, 19 Dec 2011 06:51:01 -0600, DavidE wrote:

> Hi all,
> 
> So, the background to this is that it's 11 years since I finished
> undergrad DSP, and haven't touched it since (RF and microwave hardware
> is my day job).  Consequently, I'm very rusty on the theory and
> extremely ignorant of the working practicalities of DSP.  Oppenheimer
> and Schaeffer is on my desk, but it just gives me a headache.
> 
> The scenario is very basic: a time domain waveform (sometimes infinite,
> sometimes less than 1 microsecond, sometimes in between) that I need to
> do an FFT on to find the frequency components.
> 
> I know some of the boundary conditions: - The waveform only contains
> frequencies between 20 MHz and 60 MHz; nothing higher, nothing lower
> - I need to bin the FFT down to approx 1 kHz resolution - It needs to
> happen in real time (or very close to)
> 
> My question is: is this possible?  If so, what sort of parameters will I
> need (FFT length, memory size, clock speed, particular DSP chips to
> avoid/pursue)?
> 
> If any of the boundary conditions change, how will that affect things? 
> I'm sure there'll be some kind of trade-off between frequency and
> resolution and processing time/memory and input waveform length.  I know
> higher frequency components need faster clocks, but what about things
> like the trade off between processing time and chip/memory size and
> power dissipation?
> 
> Right now I'm not even sure what to put into Google, so any guidance is
> greatly appreciated.

As well as agreeing with everything that Rune said, I will also point out 
that you're not going to get good resolution on your 1kHz spacing unless 
your sample is over 1ms (that's _milli_, not _micro_ second).

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

On Mon, 19 Dec 2011 07:49:26 -0800, fatalist wrote:

> Is your signal periodic or not ?
> 
> For an aperiodic signal doing spectral analysis with this much precision
> does not make any sense at all.
> 
> For periodic signal your first step would be to find a period very
> precisely with the least amount of data, and FFT is highly NOT
> recommended for this purpose
> (Despite what Oppenheimer and Schaeffer and some folks in this group
> might tell you...)

I wouldn't go that far, but I would certainly agree to the extent that a 
FFT isn't _necessarily_ what you want, and that your post does not give 
enough information for anyone to say what might be closer to "best".

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

This is not something that could be done over the weekend.
Seek professional assistance; get ready for 6 digit budget.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com




DavidE wrote:

> Hi all,
> 
> So, the background to this is that it's 11 years since I finished undergrad
> DSP, and haven't touched it since (RF and microwave hardware is my day
> job).  Consequently, I'm very rusty on the theory and extremely ignorant of
> the working practicalities of DSP.  Oppenheimer and Schaeffer is on my
> desk, but it just gives me a headache.
> 
> The scenario is very basic: a time domain waveform (sometimes infinite,
> sometimes less than 1 microsecond, sometimes in between) that I need to do
> an FFT on to find the frequency components.
> 
> I know some of the boundary conditions:
> - The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
> higher, nothing lower
> - I need to bin the FFT down to approx 1 kHz resolution
> - It needs to happen in real time (or very close to)
> 
> My question is: is this possible?  If so, what sort of parameters will I
> need (FFT length, memory size, clock speed, particular DSP chips to
> avoid/pursue)?  
> 
> If any of the boundary conditions change, how will that affect things?  I'm
> sure there'll be some kind of trade-off between frequency and resolution
> and processing time/memory and input waveform length.  I know higher
> frequency components need faster clocks, but what about things like the
> trade off between processing time and chip/memory size and power
> dissipation?
> 
> Right now I'm not even sure what to put into Google, so any guidance is
> greatly appreciated.
> 
> Cheers,
> 
> Dave
> 
> 

On Mon, 19 Dec 2011 06:51:01 -0600, "DavidE"
<enchelmaier@n_o_s_p_a_m.ieee.org> wrote:

>Hi all,
>
>So, the background to this is that it's 11 years since I finished undergrad
>DSP, and haven't touched it since (RF and microwave hardware is my day
>job).  Consequently, I'm very rusty on the theory and extremely ignorant of
>the working practicalities of DSP.  Oppenheimer and Schaeffer is on my
>desk, but it just gives me a headache.
>
>The scenario is very basic: a time domain waveform (sometimes infinite,
>sometimes less than 1 microsecond, sometimes in between) that I need to do
>an FFT on to find the frequency components.

Clearly you don't have an infinite signal, but I think you mean that
sometimes you have a continuous signal and sometimes a burst.  That's
understandable.


>I know some of the boundary conditions:
>- The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
>higher, nothing lower
>- I need to bin the FFT down to approx 1 kHz resolution
>- It needs to happen in real time (or very close to)
>
>My question is: is this possible?  If so, what sort of parameters will I
>need (FFT length, memory size, clock speed, particular DSP chips to
>avoid/pursue)?  

Of course it's possible, but it may be a bigger project than makes
sense to pursue.  You're asking the right questions, but it's a long
ways to a practical implementation.   The system you're describing
will not be a trivial one.

>If any of the boundary conditions change, how will that affect things?  I'm
>sure there'll be some kind of trade-off between frequency and resolution
>and processing time/memory and input waveform length.  I know higher
>frequency components need faster clocks, but what about things like the
>trade off between processing time and chip/memory size and power
>dissipation?
>
>Right now I'm not even sure what to put into Google, so any guidance is
>greatly appreciated.
>
>Cheers,
>
>Dave

Some basic analysis is pretty easy and might get you going.   You want
to analyze across 40MHz of bandwidth with 1kHz resolution.   Assuming
an FFT bin width fits your definition of "resolution" (which is
something you will ultimately have to sort out and clarify), then you
need at least a 20,000 point DFT.  

Picking a closest larger power-of-two suggests a 2^15 = 32,768 point
FFT.   You'll need extra beyone the 20k, anyway, for guard band,
unless you've already budgeted for that in your 40MHz analysis region.


You'll need to sample at a minimum of 40 MHz if you use two ADCs for
complex sampling with the analysis region mixed to baseband.   If you
need to sample differently (e.g., a single ADC and no mix or some IF
mix) then you'll need to make adjustments.   For the 40 MHz sample
rate case it will take 819.2 microseconds to collect enough data to
fill a buffer for the 32k-pt FFT.  That assumes the absolute minimum
sample rate, which really just puts a bound on the data collection
time.   In practice you'll probably need to sample faster, which will
reduce the frequency resolution compared to the slower sample rate.
You can always manage your ultimate sample rate and ultimate FFT size
to get the "resolution" you want, also considering whether you need to
apply any data windows, etc.

The delay from the end of the time-domain data collection time to
finishing the computation of the transform will depend entirely on the
implementation, but it is still true that you can trade cost and
complexity for latency.   If you want it to complete computation more
quickly, it will cost more money and complexity to do so.  How well
that fits into your definition of "real time" can be sorted out from
there.

You can search the internet for FFT implementations that fit in
processors (slower) or FPGAs (faster) and try to sort out various cost
and implementation strategies that way.   A 32k FFT is still
considered pretty big, but implementations do exist and there are
always oddball optimizations that can be done if you pick one size and
stick with it.   There are lots of different ways to implement FFTs,
and what might fit your application best will depend on a lot of
things, like cost, complexity, latency, etc.

There is no problem applying a DFT/FFT to random, non-periodic data.
You just need to be aware of how to interpret the results.



Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On Dec 19, 3:58�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 19 Dec 2011 06:51:01 -0600, "DavidE"
>
> <enchelmaier@n_o_s_p_a_m.ieee.org> wrote:
> >Hi all,
>
> >So, the background to this is that it's 11 years since I finished undergrad
> >DSP, and haven't touched it since (RF and microwave hardware is my day
> >job). &#4294967295;Consequently, I'm very rusty on the theory and extremely ignorant of
> >the working practicalities of DSP. &#4294967295;Oppenheimer and Schaeffer is on my
> >desk, but it just gives me a headache.
>
> >The scenario is very basic: a time domain waveform (sometimes infinite,
> >sometimes less than 1 microsecond, sometimes in between) that I need to do
> >an FFT on to find the frequency components.
>
> Clearly you don't have an infinite signal, but I think you mean that
> sometimes you have a continuous signal and sometimes a burst. &#4294967295;That's
> understandable.
>
> >I know some of the boundary conditions:
> >- The waveform only contains frequencies between 20 MHz and 60 MHz; nothing
> >higher, nothing lower
> >- I need to bin the FFT down to approx 1 kHz resolution
> >- It needs to happen in real time (or very close to)
>
> >My question is: is this possible? &#4294967295;If so, what sort of parameters will I
> >need (FFT length, memory size, clock speed, particular DSP chips to
> >avoid/pursue)?
>
> Of course it's possible, but it may be a bigger project than makes
> sense to pursue. &#4294967295;You're asking the right questions, but it's a long
> ways to a practical implementation. &#4294967295; The system you're describing
> will not be a trivial one.
>
> >If any of the boundary conditions change, how will that affect things? &#4294967295;I'm
> >sure there'll be some kind of trade-off between frequency and resolution
> >and processing time/memory and input waveform length. &#4294967295;I know higher
> >frequency components need faster clocks, but what about things like the
> >trade off between processing time and chip/memory size and power
> >dissipation?
>
> >Right now I'm not even sure what to put into Google, so any guidance is
> >greatly appreciated.
>
> >Cheers,
>
> >Dave
>
> Some basic analysis is pretty easy and might get you going. &#4294967295; You want
> to analyze across 40MHz of bandwidth with 1kHz resolution. &#4294967295; Assuming
> an FFT bin width fits your definition of "resolution" (which is
> something you will ultimately have to sort out and clarify), then you
> need at least a 20,000 point DFT.
>
> Picking a closest larger power-of-two suggests a 2^15 = 32,768 point
> FFT. &#4294967295; You'll need extra beyone the 20k, anyway, for guard band,
> unless you've already budgeted for that in your 40MHz analysis region.
>
> You'll need to sample at a minimum of 40 MHz if you use two ADCs for
> complex sampling with the analysis region mixed to baseband. &#4294967295; If you
> need to sample differently (e.g., a single ADC and no mix or some IF
> mix) then you'll need to make adjustments. &#4294967295; For the 40 MHz sample
> rate case it will take 819.2 microseconds to collect enough data to
> fill a buffer for the 32k-pt FFT. &#4294967295;That assumes the absolute minimum
> sample rate, which really just puts a bound on the data collection
> time. &#4294967295; In practice you'll probably need to sample faster, which will
> reduce the frequency resolution compared to the slower sample rate.
> You can always manage your ultimate sample rate and ultimate FFT size
> to get the "resolution" you want, also considering whether you need to
> apply any data windows, etc.
>
> The delay from the end of the time-domain data collection time to
> finishing the computation of the transform will depend entirely on the
> implementation, but it is still true that you can trade cost and
> complexity for latency. &#4294967295; If you want it to complete computation more
> quickly, it will cost more money and complexity to do so. &#4294967295;How well
> that fits into your definition of "real time" can be sorted out from
> there.
>
> You can search the internet for FFT implementations that fit in
> processors (slower) or FPGAs (faster) and try to sort out various cost
> and implementation strategies that way. &#4294967295; A 32k FFT is still
> considered pretty big, but implementations do exist and there are
> always oddball optimizations that can be done if you pick one size and
> stick with it. &#4294967295; There are lots of different ways to implement FFTs,
> and what might fit your application best will depend on a lot of
> things, like cost, complexity, latency, etc.
>
> There is no problem applying a DFT/FFT to random, non-periodic data.
> You just need to be aware of how to interpret the results.
>
> Eric Jacobsen
> Anchor Hill Communicationswww.anchorhill.com

"There is no problem applying a DFT/FFT to random, non-periodic data.
You just need to be aware of how to interpret the results."

No, there is a problem, rather big problem with applying DFT/FFT to
"random" numbers

Try it on the output of any nonlinear chaotic oscillator e.g Lorenz
attractor

What you should say is this: FFT will always take some (any) numbers
in and output some numbers out

garbage in - garbage out

Hi everyone,

Thanks for the quick responses.  I knew I was in over my head :)

Yes, infinite was a poor choice of words, but the signal in question is
continuous wave RF signal, so I assumed that for all practical purposes it
could be treated as infinite.

I'll need a day or two to get my head around your replies, then hopefully I
can re-phrase the question and the specs in a way that makes more sense.

Dave

On Mon, 19 Dec 2011 13:24:51 -0800 (PST), fatalist
<simfidude@gmail.com> wrote:

>On Dec 19, 3:58=A0pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>> On Mon, 19 Dec 2011 06:51:01 -0600, "DavidE"
>>
>> <enchelmaier@n_o_s_p_a_m.ieee.org> wrote:
>> >Hi all,
>>
>> >So, the background to this is that it's 11 years since I finished underg=
>rad
>> >DSP, and haven't touched it since (RF and microwave hardware is my day
>> >job). =A0Consequently, I'm very rusty on the theory and extremely ignora=
>nt of
>> >the working practicalities of DSP. =A0Oppenheimer and Schaeffer is on my
>> >desk, but it just gives me a headache.
>>
>> >The scenario is very basic: a time domain waveform (sometimes infinite,
>> >sometimes less than 1 microsecond, sometimes in between) that I need to =
>do
>> >an FFT on to find the frequency components.
>>
>> Clearly you don't have an infinite signal, but I think you mean that
>> sometimes you have a continuous signal and sometimes a burst. =A0That's
>> understandable.
>>
>> >I know some of the boundary conditions:
>> >- The waveform only contains frequencies between 20 MHz and 60 MHz; noth=
>ing
>> >higher, nothing lower
>> >- I need to bin the FFT down to approx 1 kHz resolution
>> >- It needs to happen in real time (or very close to)
>>
>> >My question is: is this possible? =A0If so, what sort of parameters will=
> I
>> >need (FFT length, memory size, clock speed, particular DSP chips to
>> >avoid/pursue)?
>>
>> Of course it's possible, but it may be a bigger project than makes
>> sense to pursue. =A0You're asking the right questions, but it's a long
>> ways to a practical implementation. =A0 The system you're describing
>> will not be a trivial one.
>>
>> >If any of the boundary conditions change, how will that affect things? =
>=A0I'm
>> >sure there'll be some kind of trade-off between frequency and resolution
>> >and processing time/memory and input waveform length. =A0I know higher
>> >frequency components need faster clocks, but what about things like the
>> >trade off between processing time and chip/memory size and power
>> >dissipation?
>>
>> >Right now I'm not even sure what to put into Google, so any guidance is
>> >greatly appreciated.
>>
>> >Cheers,
>>
>> >Dave
>>
>> Some basic analysis is pretty easy and might get you going. =A0 You want
>> to analyze across 40MHz of bandwidth with 1kHz resolution. =A0 Assuming
>> an FFT bin width fits your definition of "resolution" (which is
>> something you will ultimately have to sort out and clarify), then you
>> need at least a 20,000 point DFT.
>>
>> Picking a closest larger power-of-two suggests a 2^15 =3D 32,768 point
>> FFT. =A0 You'll need extra beyone the 20k, anyway, for guard band,
>> unless you've already budgeted for that in your 40MHz analysis region.
>>
>> You'll need to sample at a minimum of 40 MHz if you use two ADCs for
>> complex sampling with the analysis region mixed to baseband. =A0 If you
>> need to sample differently (e.g., a single ADC and no mix or some IF
>> mix) then you'll need to make adjustments. =A0 For the 40 MHz sample
>> rate case it will take 819.2 microseconds to collect enough data to
>> fill a buffer for the 32k-pt FFT. =A0That assumes the absolute minimum
>> sample rate, which really just puts a bound on the data collection
>> time. =A0 In practice you'll probably need to sample faster, which will
>> reduce the frequency resolution compared to the slower sample rate.
>> You can always manage your ultimate sample rate and ultimate FFT size
>> to get the "resolution" you want, also considering whether you need to
>> apply any data windows, etc.
>>
>> The delay from the end of the time-domain data collection time to
>> finishing the computation of the transform will depend entirely on the
>> implementation, but it is still true that you can trade cost and
>> complexity for latency. =A0 If you want it to complete computation more
>> quickly, it will cost more money and complexity to do so. =A0How well
>> that fits into your definition of "real time" can be sorted out from
>> there.
>>
>> You can search the internet for FFT implementations that fit in
>> processors (slower) or FPGAs (faster) and try to sort out various cost
>> and implementation strategies that way. =A0 A 32k FFT is still
>> considered pretty big, but implementations do exist and there are
>> always oddball optimizations that can be done if you pick one size and
>> stick with it. =A0 There are lots of different ways to implement FFTs,
>> and what might fit your application best will depend on a lot of
>> things, like cost, complexity, latency, etc.
>>
>> There is no problem applying a DFT/FFT to random, non-periodic data.
>> You just need to be aware of how to interpret the results.
>>
>> Eric Jacobsen
>> Anchor Hill Communicationswww.anchorhill.com
>
>"There is no problem applying a DFT/FFT to random, non-periodic data.
>You just need to be aware of how to interpret the results."
>
>No, there is a problem, rather big problem with applying DFT/FFT to
>"random" numbers
>
>Try it on the output of any nonlinear chaotic oscillator e.g Lorenz
>attractor
>
>What you should say is this: FFT will always take some (any) numbers
>in and output some numbers out
>
>garbage in - garbage out
>

Nothing about that is inconsistent with what I said.


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com