Forums

Experience with the Sliding DFT, anyone?

Started by hxtasy December 15, 2008
Hello I would like to know if anyone has experience with the sliding DFT
algorithm. It is somewhat similar to the Goertzel algorithm.

All I would like to know is what application this algorithm would be
useful in?


 I cannot find that much information on the internet and have not had time
to look into any books about the sliding DFT. So if anyone could mention
the mathematics behind it the help would be appreciated.


On Mon, 15 Dec 2008 06:53:09 -0600, "hxtasy" <atijon58@gmail.com>
wrote:

>Hello I would like to know if anyone has experience with the sliding DFT >algorithm.
http://groups.google.com/group/comp.dsp/browse_thread/thread/cd1cd30422feadd3
hxtasy wrote:
> Hello I would like to know if anyone has experience with the sliding DFT > algorithm. It is somewhat similar to the Goertzel algorithm. > > All I would like to know is what application this algorithm would be > useful in? >
Probably the most unorthodox and extravagant of all possible applications, but I have been using it for musical (audio) applications, mainly in its use as part of a full (but very slow!) "sliding phase vocoder" (SPV): http://dream.cs.bath.ac.uk/SDFT/index.html Now fully incorporated in Csound. Our initial paper on the SDFT was for ICMC2005, which can be found via here: http://dream.cs.bath.ac.uk/DigitalLibrary/index.php (use the ICMC link; see also the Dafx08 link for some initial explorations of a ConstQ form) We have yet to put our 2007 ICMC paper online, but the first link above gives access to the slides we used with some sound examples (though it is far more about the SPV than the SDFT itself). I am not the one to ask about the maths though - not my area! Richard Dobson
On Dec 16, 3:31&#2013266080;am, Richard Dobson <richarddob...@blueyonder.co.uk>
wrote:
> hxtasy wrote: > > Hello I would like to know if anyone has experience with the sliding DFT > > algorithm. It is somewhat similar to the Goertzel algorithm. > > > All I would like to know is what application this algorithm would be > > useful in? > > Probably the most unorthodox and extravagant of all possible > applications, but I have been using it for musical (audio) applications, > mainly in its use as part of a full (but very slow!) "sliding phase > vocoder" (SPV): > > http://dream.cs.bath.ac.uk/SDFT/index.html > > Now fully incorporated in Csound. > > Our initial paper on the SDFT was for ICMC2005, which can be found via here: > > http://dream.cs.bath.ac.uk/DigitalLibrary/index.php > > (use the ICMC link; see also the Dafx08 link for some initial > explorations of a ConstQ form) > > We have yet to put our 2007 ICMC paper online, but the first link above > gives access to the slides we used with some sound examples (though it > is far more about the SPV than the SDFT itself). > > I am not the one to ask about the maths though - not my area! > > Richard Dobson
Do you have a ref for the original sliding DFT paper? H
HardySpicer wrote:
..
>> >> Our initial paper on the SDFT was for ICMC2005, which can be found via here: >> >> http://dream.cs.bath.ac.uk/DigitalLibrary/index.php
> > Do you have a ref for the original sliding DFT paper? >
Not sure what you mean - ~our~ original paper is via the link above. If you mean some particular original (older) publication, I have no idea. Not sure there is one, as such. The basic principle (a complex rotation applied to an input DFT buffer, for each sample) is the sort of thing that might have been regarded as too trivial to write a whole paper on - it is probably documented in the classic DSP reference texts from the 70's (none of which I own, sadly). I found a few papers dating from the late 80's to early 90's (e.g. "Generalized Sliding FFT..." by B. Farhang-Bouroujeny, IEEE somewhere, 1994), but doubt if they can be called "the original". Richard Dobson
On 15 Dez., 18:55, HardySpicer <gyansor...@gmail.com> wrote:
> On Dec 16, 3:31&#2013266080;am, Richard Dobson <richarddob...@blueyonder.co.uk> > wrote: > > > > > > > hxtasy wrote: > > > Hello I would like to know if anyone has experience with the sliding DFT > > > algorithm. It is somewhat similar to the Goertzel algorithm. > > > > All I would like to know is what application this algorithm would be > > > useful in? > > > Probably the most unorthodox and extravagant of all possible > > applications, but I have been using it for musical (audio) applications, > > mainly in its use as part of a full (but very slow!) "sliding phase > > vocoder" (SPV): > > >http://dream.cs.bath.ac.uk/SDFT/index.html > > > Now fully incorporated in Csound. > > > Our initial paper on the SDFT was for ICMC2005, which can be found via here: > > >http://dream.cs.bath.ac.uk/DigitalLibrary/index.php > > > (use the ICMC link; see also the Dafx08 link for some initial > > explorations of a ConstQ form) > > > We have yet to put our 2007 ICMC paper online, but the first link above > > gives access to the slides we used with some sound examples (though it > > is far more about the SPV than the SDFT itself). > > > I am not the one to ask about the maths though - not my area! > > > Richard Dobson > > Do you have a ref for the original sliding DFT paper?
It is just the standard recursive algorithm to compute a running sum (store the sum in a state variable, subtract the oldest input and add the newest input) with an additional twiddle factor multiplication. You'll find tons on the web. Regards, Andor
On Dec 15, 4:11&#2013266080;pm, Andor <andor.bari...@gmail.com> wrote:
> On 15 Dez., 18:55, HardySpicer <gyansor...@gmail.com> wrote: > > > > > > > On Dec 16, 3:31&#2013266080;am, Richard Dobson <richarddob...@blueyonder.co.uk> > > wrote: > > > > hxtasy wrote: > > > > Hello I would like to know if anyone has experience with the sliding DFT > > > > algorithm. It is somewhat similar to the Goertzel algorithm. > > > > > All I would like to know is what application this algorithm would be > > > > useful in? > > > > Probably the most unorthodox and extravagant of all possible > > > applications, but I have been using it for musical (audio) applications, > > > mainly in its use as part of a full (but very slow!) "sliding phase > > > vocoder" (SPV): > > > >http://dream.cs.bath.ac.uk/SDFT/index.html > > > > Now fully incorporated in Csound. > > > > Our initial paper on the SDFT was for ICMC2005, which can be found via here: > > > >http://dream.cs.bath.ac.uk/DigitalLibrary/index.php > > > > (use the ICMC link; see also the Dafx08 link for some initial > > > explorations of a ConstQ form) > > > > We have yet to put our 2007 ICMC paper online, but the first link above > > > gives access to the slides we used with some sound examples (though it > > > is far more about the SPV than the SDFT itself). > > > > I am not the one to ask about the maths though - not my area! > > > > Richard Dobson > > > Do you have a ref for the original sliding DFT paper? > > It is just the standard recursive algorithm to compute a running sum > (store the sum in a state variable, subtract the oldest input and add > the newest input) with an additional twiddle factor multiplication. > You'll find tons on the web. > > Regards, > Andor- Hide quoted text - > > - Show quoted text -
It's a very old technique. You can find it in many textbooks from the 1970's (e.g.: Rabiner and Gold, p. 382-3). Googling "sliding dft'" found >1600 hits; among them: http://www.comm.utoronto.ca/~dimitris/ece431/slidingdft.pdf http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/SlidingDFT_BW.pdf The second link is the 'dsp tricks and tips' paper from IEEE Signal Processing Magazine. It's often used when you don't want all N frequency points that you would get from a regular DFT or FFT. And, just as with the conventional DFT, you can compute it for fractional frequencies, and your data can be any length N.
"hxtasy" <atijon58@gmail.com> wrote in message 
news:IoudnXG0AIuoztvUnZ2dnUVZ_rbinZ2d@giganews.com...
> Hello I would like to know if anyone has experience with the > sliding DFT > algorithm. It is somewhat similar to the Goertzel algorithm. > > All I would like to know is what application this algorithm > would be > useful in? > > > I cannot find that much information on the internet and have > not had time > to look into any books about the sliding DFT. So if anyone > could mention > the mathematics behind it the help would be appreciated. > >
Try Rick Lyons' book, Understanding Digital Signal Processing. In the 2nd edition (Nineth [sic] printing) it on pages 532 to 540, a very lucid treatment.