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!
Any lazy/dirty FFT technique available?
Started by ●March 21, 2009
Reply by ●March 21, 20092009-03-21
On 21 Mar, 12:42, "hq9000" <psy...@mail.ru> 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
Reply by ●March 21, 20092009-03-21
>- 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).
Reply by ●March 21, 20092009-03-21
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
Reply by ●March 21, 20092009-03-21
On 21 Mar, 13:41, "hq9000" <psy...@mail.ru> 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
Reply by ●March 21, 20092009-03-21
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
Reply by ●March 21, 20092009-03-21
On 21 Mar, 14:54, Vladimir Vassilevsky <antispam_bo...@hotmail.com> 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
Reply by ●March 21, 20092009-03-21
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 frequency bins"... i think it's not an option here. Since the frequency resolution is important thing, but not the "amplitude resolution". Thanks!
Reply by ●March 21, 20092009-03-21
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. �����������������������������������������������������������������������
Reply by ●March 21, 20092009-03-21
On Mar 21, 4:42�am, "hq9000" <psy...@mail.ru> 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
