Any lazy/dirty FFT technique available?

[hq9000]

Hello all,

I want to see a spectrum of the audio signal but there are no
requirements for it to be extremely precise. I mean no backward conversio
to time domain is supposed to be performed. The fourier transform is fo
visual picture of frequency distribution only.

So I can easily tolerate quite a huge error in frequency coefficients. I
this situation is there any way to achieve any performance gain in FFT?

So we sacrifice on the precision but gain in performance...

Do you think it's feasible?

Thanks!

[Rune Allnor]

On 21 Mar, 12:42, "hq9000" <[email protected]> wrote:
> Hello all,
>
> I want to see a spectrum of the audio signal but there are not
> requirements for it to be extremely precise. I mean no backward conversion
> to time domain is supposed to be performed. The fourier transform is for
> visual picture of frequency distribution only.
>
> So I can easily tolerate quite a huge error in frequency coefficients. In
> this situation is there any way to achieve any performance gain in FFT?
>
> So we sacrifice on the precision but gain in performance...
>
> Do you think it's feasible?

I don't understand what you ask for:

- You want *some* picture ('not precise') of the PSD?
- Computational speed is a requirement?

Both those arguments point straight at the FFT, so I'm
quite a bit puzzled by why you don't want to use it?

Rune

[hq9000]

>- You want *some* picture ('not precise') of the PSD?
>- Computational speed is a requirement?
>
>Both those arguments point straight at the FFT, so I'm
>quite a bit puzzled by why you don't want to use it?
>
>Rune
>

Let me try to explain.

FFT is good both in performance and precision. It is fast and lets u
recompose the signal with 100% accuracy.

Than... For my particular application precision and ability to recombin
the time domain is not necessay...

So the questions is if it is possible to achieve even HIGHER efficienc
for some "specialized" FFT form (sacrifying on the precision and ability t
do the revers transform).

[Paul Russell]

hq9000 wrote:
>> - You want *some* picture ('not precise') of the PSD?
>> - Computational speed is a requirement?
>>
>> Both those arguments point straight at the FFT, so I'm
>> quite a bit puzzled by why you don't want to use it?
>>
>> Rune
>>
>
> Let me try to explain.
>
> FFT is good both in performance and precision. It is fast and lets us
> recompose the signal with 100% accuracy.
>
> Than... For my particular application precision and ability to recombine
> the time domain is not necessay...
>
> So the questions is if it is possible to achieve even HIGHER efficiency
> for some "specialized" FFT form (sacrifying on the precision and ability to
> do the revers transform).
>

Sure - just use an FFT with fewer bins.

Paul

[Rune Allnor]

On 21 Mar, 13:41, "hq9000" <[email protected]> wrote:
> >- You want *some* picture ('not precise') of the PSD?
> >- Computational speed is a requirement?
>
> >Both those arguments point straight at the FFT, so I'm
> >quite a bit puzzled by why you don't want to use it?
>
> >Rune
>
> Let me try to explain.
>
> FFT is good both in performance and precision. It is fast and lets us
> recompose the signal with 100% accuracy.
>
> Than... For my particular application precision and ability to recombine
> the time domain is not necessay...
>
> So the questions is if it is possible to achieve even HIGHER efficiency
> for some "specialized" FFT form (sacrifying on the precision and ability to
> do the revers transform).

The FFT isn't particularly 'precise' (at least in certain senses
of the word), but I see your point. You have a couple of options:

- Use fixed-point arithmetics, which is faster to run but harder
to implement than floating-point arithmetics
- Use some Discrete Cosine Transform (DCT) or similar, which
computes a 'simplified' spectrum. While faster to compute
than the FFT, you might lose information from the data.
Use at your own discretion.
- Combine the above: DCT in fixed-point arithmetics.

Rune

[Vladimir Vassilevsky]

hq9000 wrote:
> Hello all,
>
> I want to see a spectrum of the audio signal but there are not
> requirements for it to be extremely precise. I mean no backward conversion
> to time domain is supposed to be performed. The fourier transform is for
> visual picture of frequency distribution only.
>
> So I can easily tolerate quite a huge error in frequency coefficients. In
> this situation is there any way to achieve any performance gain in FFT?
>
> So we sacrifice on the precision but gain in performance...


And you want the log frequency scale, right? Something like 20 - 30
bands, right? All idiots writing audio plugins are asking about that.

Use Goertzel for lower bins, use short term real value FFT for higher bins.


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

[Rune Allnor]

On 21 Mar, 14:54, Vladimir Vassilevsky <[email protected]>
wrote:
> hq9000 wrote:
> > Hello all,
>
> > I want to see a spectrum of the audio signal but there are not
> > requirements for it to be extremely precise. I mean no backward conversion
> > to time domain is supposed to be performed. The fourier transform is for
> > visual picture of frequency distribution only.
>
> > So I can easily tolerate quite a huge error in frequency coefficients. In
> > this situation is there any way to achieve any performance gain in FFT?
>
> > So we sacrifice on the precision but gain in performance...
>
> And you want the log frequency scale, right? Something like 20 - 30
> bands, right? All idiots writing audio plugins are asking about that.

Ah. I didn't catch the context of the question.

> Use Goertzel for lower bins, use short term real value FFT for higher bins.

If one really is talking about 20-30 bands over
the audio band, use a bank of constant-Q'ish IIR
filters, followed by an amplitude detector (or
maybe just a squared amplitude term).

Rune

[hq9000]

Thanks everybody.

I think I have enough input for the moment.
Yes, it's the this one is for audio analysis.

BTW, if taking FFT on smaller block was meant by "having fewer frequenc
bins"... i think it's not an option here. Since the frequency resolution i
important thing, but not the "amplitude resolution".

Thanks!

[Jerry Avins]

hq9000 wrote:
> Hello all,
>
> I want to see a spectrum of the audio signal but there are not
> requirements for it to be extremely precise. I mean no backward conversion
> to time domain is supposed to be performed. The fourier transform is for
> visual picture of frequency distribution only.
>
> So I can easily tolerate quite a huge error in frequency coefficients. In
> this situation is there any way to achieve any performance gain in FFT?
>
> So we sacrifice on the precision but gain in performance...
>
> Do you think it's feasible?

See if you can speed things up by using numbers with fewer bits. There
might be chance of a slight improvement.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

[Malachy Moses]

On Mar 21, 4:42*am, "hq9000" <[email protected]> wrote:
> Hello all,
>
> I want to see a spectrum of the audio signal but there are not
> requirements for it to be extremely precise. I mean no backward conversion
> to time domain is supposed to be performed. The fourier transform is for
> visual picture of frequency distribution only.
>
> So I can easily tolerate quite a huge error in frequency coefficients. In
> this situation is there any way to achieve any performance gain in FFT?
>
> So we sacrifice on the precision but gain in performance...
>
> Do you think it's feasible?
>
> Thanks!

Along the lines of the suggestion from Jerry Avins, you might be able
to apply a coarse quantization to the input signal. By doing so, an
approximate FFT can be computed from selective addition and
subtraction of pre-computed numbers, without using any multiplications
at all (other than a final scale factor). Depending on the coarseness
of the quantization, there have been reports of a 10x increase in
computational speed, with large (but perhaps acceptable -- only you
will know) losses in accuracy.

For example, the authors in the following paper suggest a three-level
coarse quantization, where numbers in the input amplitude range of -2A
to +2A are quantized to one of only three values: -2A/3, 0, +2A/3.
They rescale this to -1, 0, +1. Then, all multiplications by the sin/
cos basis functions can be pre-computed and stored in a table, for
selective addition and subtraction, on an as-needed basis, in
dependence on the coarse quantization of the actual signal:

"Efficient STFT approximation using a quantization and differencing
method", by S. Hamid Nawab, Erkan Dorken, Proc. IEEE Int. Conf.
Acoustics, Speech, and Signal (1993)

at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.1149

(Unfortunately, the third page of this article is not readable)

Naturally, with such a coarse quantization, the technique introduces
significant error. The authors report a resulting SNR in the
quantized version of approx 9 dB. The trade-off is speed: They also
report an approximate 10X increase in speed over "standard" STFT

In addition, they later reported a technique for incremental
refinement to improve precision:

"Incremental refinement of DFT and STFT approximations", by Joseph M.
Winograd, S. Hamid Nawab, IEEE Sig. Proc. Letters (1995)

at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1499

[hq9000]

Thanks!

Sounds really promising!

>at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.52.1149
>
>(Unfortunately, the third page of this article is not readable)

Unfortunatelly the link is broken.
But here:
http://en.scientificcommons.org/145329
I've found the same paper I guess... with some text survived at p 3.

[glen herrmannsfeldt]

hq9000 <[email protected]> wrote:

> I want to see a spectrum of the audio signal but there are not
> requirements for it to be extremely precise. I mean no backward conversion
> to time domain is supposed to be performed. The fourier transform is for
> visual picture of frequency distribution only.

How are you doing it, and how much faster should
it be?

If you do the FFT in 16 bit fixed point it could
be a lot faster than in 32 bit or 64 bit floating
point.

What processor are you using?

You might look at the ICT, which was specifically
designed for processors without hardware multiply,
and especially without floating point.

(google for ict site:jpl.nasa.gov and it should come out.)

-- glen

[Vladimir Vassilevsky]

Rune Allnor wrote:

> On 21 Mar, 14:54, Vladimir Vassilevsky <[email protected]>
> wrote:
>

>>And you want the log frequency scale, right? Something like 20 - 30
>>bands, right? All idiots writing audio plugins are asking about that.
>
>
> Ah. I didn't catch the context of the question.
>
>
>>Use Goertzel for lower bins, use short term real value FFT for higher bins.
>
>
> If one really is talking about 20-30 bands over
> the audio band, use a bank of constant-Q'ish IIR
> filters, followed by an amplitude detector (or
> maybe just a squared amplitude term).

Utter punk method to produce something that looks like auduo spectrum:

1. Whiten the signal by [1 -1] filter.
2. Measure the distances between zero crossings. Make a histogram. The
histogram it is.


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

[hq9000]

>How are you doing it, and how much faster should
>it be?
>
>If you do the FFT in 16 bit fixed point it could
>be a lot faster than in 32 bit or 64 bit floating
>point.
>
>What processor are you using?

Actually the final goal is to create cross-platform application, thu
there could be no any assumtions.

I can say for sure though that the input will be most likely provided a
double precision float.

In this case... Does it worth converting the data to 16 bit integer prio
to FFTizing it? 16 bit int would be more than enough goood approximation.

The question is - how much will I gain? Taking into consideration the cos
of preliminary conversion.

[John]

On Mar 21, 4:17*pm, "hq9000" <[email protected]> wrote:
> >How are you doing it, and how much faster should
> >it be?
>
> >If you do the FFT in 16 bit fixed point it could
> >be a lot faster than in 32 bit or 64 bit floating
> >point. *
>
> >What processor are you using?
>
> Actually the final goal is to create cross-platform application, thus
> there could be no any assumtions.
>
> I can say for sure though that the input will be most likely provided as
> double precision float.
>
> In this case... Does it worth converting the data to 16 bit integer prior
> to FFTizing it? 16 bit int would be more than enough goood approximation.
>
> The question is - how much will I gain? Taking into consideration the cost
> of preliminary conversion.

If you are working on a modern Pentium-based PC, consider converting
to single precision floating point.