If I have a time-series I normally split it up and take small FFTs but here I have a very large impulse response with about 30,000 points and I need to convert it to the frequency domain. Of course I can use brute force but I wondered if there was a more elegant way you can split do this. I can't see how you can divide it into sections of a smaller size since this is like a transient response I am looking at (of sorts). This is a room impulse response btw.
FFTs of large impulse response
Started by ●February 6, 2014
Reply by ●February 7, 20142014-02-07
On 07.02.14 04.26, gyansorova@gmail.com wrote:> If I have a time-series I normally split it up and take small FFTs but here I have a very large impulse response with about 30,000 points and I need to convert it to the frequency domain. > Of course I can use brute force but I wondered if there was a more elegant way you can split do this. I can't see how you can divide it into sections of a smaller size since this is like a transient response I am looking at (of sorts). > This is a room impulse response btw.What's wrong with with an FFT of this size? I measure room responses quite often. And 30,000 Points is usually by far insufficient to get stable results from phase unwrapping. I usually use an FFT size of 262144. Sometimes one order less sometime even more - especially if I measure multiple channels at once. Libraries like fftw3 do this with much more than real time on quite old hardware. I run two channel FIR filters with 48k kernel length and 64k FFT size on an old AMD K6 at 48k sample rate in real time. No big deal. If you try to split an FFT into several smaller FFTs you will end up with nothing else but the FFT algorithm itself. An Discrete Fourier Transform is nothing else but a (complex) matrix multiplication of the time domain vector with a matrix containing all frequencies that fit into the length of the transform. Like any matrix multiplication you can split this into smaller components. But the trick of the FFT is that it removes redundancies from the calculation by factorizing the FFT size into small prime factors, preferably only 2. That's why it is fast. You have to be quite smart if you want to keep this optimization. And you will never be better (although that has not been finally proven). Marcel
Reply by ●February 7, 20142014-02-07
On 2/7/14 10:52 AM, Marcel M�ller wrote:>...> > If you try to split an FFT into several smaller FFTs you will end up > with nothing else but the FFT algorithm itself. An Discrete Fourier > Transform is nothing else but a (complex) matrix multiplication of the > time domain vector with a matrix containing all frequencies that fit > into the length of the transform. Like any matrix multiplication you can > split this into smaller components. But the trick of the FFT is that it > removes redundancies from the calculation by factorizing the FFT size > into small prime factors, preferably only 2. That's why it is fast. You > have to be quite smart if you want to keep this optimization. And you > will never be better (although that has not been finally proven). >not that i think it's any good, but i thought that Winograd has been proven to have fewer multiplications (O(N)) than Cooley-Tukey (O(NlogN). maybe, now that multiplying numbers is no worse than adding them, it's no better, i dunno. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●February 7, 20142014-02-07
On Saturday, February 8, 2014 4:52:15 AM UTC+13, Marcel M�ller wrote:> On 07.02.14 04.26, gyansorova@gmail.com wrote: > > > If I have a time-series I normally split it up and take small FFTs but here I have a very large impulse response with about 30,000 points and I need to convert it to the frequency domain. > > > Of course I can use brute force but I wondered if there was a more elegant way you can split do this. I can't see how you can divide it into sections of a smaller size since this is like a transient response I am looking at (of sorts). > > > This is a room impulse response btw. > > > > What's wrong with with an FFT of this size? I measure room responses > > quite often. And 30,000 Points is usually by far insufficient to get > > stable results from phase unwrapping. I usually use an FFT size of > > 262144. Sometimes one order less sometime even more - especially if I > > measure multiple channels at once. > > > > Libraries like fftw3 do this with much more than real time on quite old > > hardware. I run two channel FIR filters with 48k kernel length and 64k > > FFT size on an old AMD K6 at 48k sample rate in real time. No big deal. > > > > If you try to split an FFT into several smaller FFTs you will end up > > with nothing else but the FFT algorithm itself. An Discrete Fourier > > Transform is nothing else but a (complex) matrix multiplication of the > > time domain vector with a matrix containing all frequencies that fit > > into the length of the transform. Like any matrix multiplication you can > > split this into smaller components. But the trick of the FFT is that it > > removes redundancies from the calculation by factorizing the FFT size > > into small prime factors, preferably only 2. That's why it is fast. You > > have to be quite smart if you want to keep this optimization. And you > > will never be better (although that has not been finally proven). > > > > > > MarcelOk that is re-assuring. I just though it may not be the done thing. I too have FFT sizes in the several 100s of thousands. I thought truncating the impulse responses may be done since not a lot seems to happen once the thing dies down.
Reply by ●February 7, 20142014-02-07
don't feel bad about using large FFTs. Much of the material on the web comes from days long gone where you had to carry the coal to power the steam-driven automated data processing. Not anymore. It's no big deal nowadays to take the FFT of a whole audio CD, for example (one song at a time may be more practical). If someone comes and says this is not right, tell him it's one cycle of an infinitely periodic signal because on your CD player, the "repeat" button is pressed... suddenly it is mathematically accurate, the Fourier sum _is_ your time- and-bandwidth-limited signal, without _any_ approximation. Whole books on windowing and other assorted man-made FFT problems simlpy disappear into thin air. Now if you need real time processing, it's a different story. _____________________________ Posted through www.DSPRelated.com
Reply by ●February 7, 20142014-02-07
On 07.02.14 20.24, gyansorova@gmail.com wrote:> Ok that is re-assuring. I just though it may not be the done thing. > I too have FFT sizes in the several 100s of thousands. > I thought truncating the impulse responses may be done since not a lot seems to happen once the thing dies down.That's true, you do not need that very end of the impulse response. But in practice the question is where you got the impulse response from and what you intend to do with it. You cannot reasonably measure the response from a Dirac pulse directly. And if you combine different measurements at different frequencies or alternatively a measurement with some well known noise, you need to have an exact phase relation. At least to do reasonable smoothing in the frequency domain. Marcel
Reply by ●February 7, 20142014-02-07
On Saturday, February 8, 2014 12:04:04 PM UTC+13, Marcel M�ller wrote:> On 07.02.14 20.24, gyansorova@gmail.com wrote: > > > Ok that is re-assuring. I just though it may not be the done thing. > > > I too have FFT sizes in the several 100s of thousands. > > > I thought truncating the impulse responses may be done since not a lot seems to happen once the thing dies down. > > > > That's true, you do not need that very end of the impulse response. > > But in practice the question is where you got the impulse response from > > and what you intend to do with it. > > You cannot reasonably measure the response from a Dirac pulse directly. > > And if you combine different measurements at different frequencies or > > alternatively a measurement with some well known noise, you need to have > > an exact phase relation. At least to do reasonable smoothing in the > > frequency domain. > > > > > > MarcelI got it from an online resource and I am using it for a deconvolution algorithm I am working on - which has been quite successful.
Reply by ●February 7, 20142014-02-07
gyansorova@gmail.com wrote:> If I have a time-series I normally split it up and take small FFTs > but here I have a very large impulse response with about 30,000 > points and I need to convert it to the frequency domain. Of course I > can use brute force but I wondered if there was a more elegant way > you can split do this. I can't see how you can divide it into > sections of a smaller size since this is like a transient response I > am looking at (of sorts). This is a room impulse response btw. >Why is 30K points a burden? I have impulse responses @ 44.1K that are seconds long. -- Les Cargill
Reply by ●February 7, 20142014-02-07
On Saturday, February 8, 2014 4:45:28 PM UTC+13, Les Cargill wrote:> gyansorova@gmail.com wrote: > > > If I have a time-series I normally split it up and take small FFTs > > > but here I have a very large impulse response with about 30,000 > > > points and I need to convert it to the frequency domain. Of course I > > > can use brute force but I wondered if there was a more elegant way > > > you can split do this. I can't see how you can divide it into > > > sections of a smaller size since this is like a transient response I > > > am looking at (of sorts). This is a room impulse response btw. > > > > > > > > > > > Why is 30K points a burden? I have impulse responses @ 44.1K that >It's not really, it's what I do with it afterwards that is! Suppose you want to take the impulse response and find it's roots..
Reply by ●February 8, 20142014-02-08
gyansorova@gmail.com wrote:> On Saturday, February 8, 2014 4:45:28 PM UTC+13, Les Cargill wrote: >> gyansorova@gmail.com wrote: >> >>> If I have a time-series I normally split it up and take small >>> FFTs >> >>> but here I have a very large impulse response with about 30,000 >> >>> points and I need to convert it to the frequency domain. Of >>> course I >> >>> can use brute force but I wondered if there was a more elegant >>> way >> >>> you can split do this. I can't see how you can divide it into >> >>> sections of a smaller size since this is like a transient >>> response I >> >>> am looking at (of sorts). This is a room impulse response btw. >> >>> >> >> >> >> >> >> >> >> Why is 30K points a burden? I have impulse responses @ 44.1K that >> > It's not really, it's what I do with it afterwards that is! Suppose > you want to take the impulse response and find it's roots.. > >Call Alex Haley? I don't think I unnerstan' (if impulse responses had roots, I'd farm them. ) -- Les Cargll
