archive: SETI Re: High bandwidth digitizer, FFT's, and analyzer

SETI Re: High bandwidth digitizer, FFT's, and analyzer

David Woolley ( )
Wed, 30 Sep 1998 08:14:35 +0100 (BST)

> Also, the following statement intrigues me:
> " 10Gflops of processing power to FFT your 100Mhz samples "

The FFT algorithm has complexity order n * log (n) (non-fast DFT approaches
were n ** 2). The bin width is somewhere between 10 Hz and 0.1Hz, so we
need to run over 0.1 to 10s of samples. (0.1Hz is the limit suggested by
various people as a result of frequency spreading of the signal in flight;
I seem to remember that 10Hz is a figure being used by some of the sound
card based systems.) This gives log (n) of the range of 23 to 30.

The number of elementary sequences in the processing will also include
the n factor, but as we reduce n, we get more runs of the transform in
the same time, so the linear dependence on n for a frequency cancels out.

This gives 2.3 to 3 G(elementary sequences)/s.

I arbitrarily assumed of the order of 3 arithmetic operations per elementary
sequence, although, I think it is actually more.

Note that it is not really necessary to use floating point, provided that
you have sufficient precision in your fixed point calculations; I think you
do need a couple of multiplies at each step. There may be a factor of two
error, but not in log (n).

I've used logs base 2, as they more closely model the reality, but using other
values of the base just introduces a multiplicative constant, which would have
to be compensated for in the processing cost per step.