New webpage on running DFT

Hi Russell, John,

happened across this - does it say anything we don't already know?

http://cnx.org/content/m12029/latest/


I will come into Uni tomorrow (Wednesday) to add some musical control to 
the VST plugin;  away Thursday PM until Monday.

Richard

Richard Dobson wrote:
> Hi Russell, John,
>
> happened across this - does it say anything we don't already know?
>
> http://cnx.org/content/m12029/latest/

Not if you are an astute reader of the DSP Tips & Tricks column of the
Signal Processing Magazine:

The sliding DFT
Jacobsen, E.; Lyons, R.
Signal Processing Magazine, IEEE, Vol.20, Iss.2, Mar 2003
Pages: 74- 80
URL:
http://ieeexplore.ieee.org/iel5/79/26586/01184347.pdf?isnumber=26586&prod=JNL&arnumber=1184347&arnumber=1184347&arSt=+74&ared=+80&arAuthor=Jacobsen%2C+E.%3B+Lyons%2C+R.

> I will come into Uni tomorrow (Wednesday) to add some musical control to
> the VST plugin;  away Thursday PM until Monday.

I hate it when that happens :-).

Regards,
Andor

Andor wrote:
> Richard Dobson wrote:
> 
>>Hi Russell, John,
>>
>>happened across this - does it say anything we don't already know?
>>
>>http://cnx.org/content/m12029/latest/
> 
> 
> Not if you are an astute reader of the DSP Tips & Tricks column of the
> Signal Processing Magazine:
> 
> The sliding DFT
> Jacobsen, E.; Lyons, R.
> Signal Processing Magazine, IEEE, Vol.20, Iss.2, Mar 2003
> Pages: 74- 80
> URL:
> http://ieeexplore.ieee.org/iel5/79/26586/01184347.pdf?isnumber=26586&prod=JNL&arnumber=1184347&arnumber=1184347&arSt=+74&ared=+80&arAuthor=Jacobsen%2C+E.%3B+Lyons%2C+R.
> 
> 
>>I will come into Uni tomorrow (Wednesday) to add some musical control to
>>the VST plugin;  away Thursday PM until Monday.
> 
> 
> I hate it when that happens :-).
> 


So do I! Blasted Thunderbird again (he said, blaming his tools).  I 
already have the Jacobsen/Lyons paper, always glad to add to the 
library. As you may have surmised,  I am more of a musician  than a 
mathematician (which is what the other guys do, so well).

Richard Dobson

On Jul 24, 11:08 am, Andor <andor.bari...@gmail.com> wrote:

> The sliding DFT
> Jacobsen, E.; Lyons, R.
> Signal Processing Magazine, IEEE, Vol.20, Iss.2, Mar 2003
> Pages: 74- 80

There is an alternate formulation for the Sliding DFT.  See "http://
groups.google.com/group/comp.dsp/msg/6800ec6bc25deb8?
safe=images&ie=UTF-8&oe=UTF-8&as_umsgid=ft6uutcn4kq9u8uqvvrn1vh4lhi3tkkcgq@4ax.com&lr=&hl=en".
I don't know whether this alternate formulation is related in any way
to the Sliding Goertzel DFT; I haven't done that analysis.

Greg Berchin

Greg Berchin wrote:
> On Jul 24, 11:08 am, Andor <andor.bari...@gmail.com> wrote:
> 
> 
>>The sliding DFT
>>Jacobsen, E.; Lyons, R.
>>Signal Processing Magazine, IEEE, Vol.20, Iss.2, Mar 2003
>>Pages: 74- 80
> 
> 
> There is an alternate formulation for the Sliding DFT.  See "http://
> groups.google.com/group/comp.dsp/msg/6800ec6bc25deb8?
> safe=images&ie=UTF-8&oe=UTF-8&as_umsgid=ft6uutcn4kq9u8uqvvrn1vh4lhi3tkkcgq@4ax.com&lr=&hl=en".
> I don't know whether this alternate formulation is related in any way
> to the Sliding Goertzel DFT; I haven't done that analysis.
> 
> Greg Berchin
> 

Thanks, I'll pass that on. We are looking specifically at the "classic" 
SDFT where the hopsize is 1, inspired by James Moorer's paper in JAES 
May 2000, "Audio in the New Millennium", about what us audio folk might 
be doing come 2020, with teraflop processing speeds as routine as Gflop 
speeds are today. We have a prototype Sliding Phase Vocoder (horribly 
slow!), which may be tolerably fast in 2020. Hoping to try out some cool 
uber-hardware with go-faster stripes to run it on.

If anyone on this list is audio-oriented enough to go to the ICMC in 
Copenhagen next month, we will be there presenting results so far of our 
explorations. May not impress the comp.dsp pros, but the computer music 
people may find it quite interesting (we hope).

Richard Dobson

On Jul 24, 4:25 pm, Richard Dobson <richarddob...@blueyonder.co.uk>
wrote:
> Greg Berchin wrote:
> > On Jul 24, 11:08 am, Andor <andor.bari...@gmail.com> wrote:
>
> >>The sliding DFT
> >>Jacobsen, E.; Lyons, R.
> >>Signal Processing Magazine, IEEE, Vol.20, Iss.2, Mar 2003
> >>Pages: 74- 80
>
> > There is an alternate formulation for the Sliding DFT.  See "http://
> > groups.google.com/group/comp.dsp/msg/6800ec6bc25deb8?
> > safe=images&ie=UTF-8&oe=UTF-8&as_umsgid=ft6uutcn4kq9u8uqvvrn1vh4lhi3tkk...@4ax.com&lr=&hl=en".
> > I don't know whether this alternate formulation is related in any way
> > to the Sliding Goertzel DFT; I haven't done that analysis.
>
> > Greg Berchin
>
> Thanks, I'll pass that on. We are looking specifically at the "classic"
> SDFT where the hopsize is 1, inspired by James Moorer's paper in JAES
> May 2000, "Audio in the New Millennium", about what us audio folk might
> be doing come 2020, with teraflop processing speeds as routine as Gflop
> speeds are today. We have a prototype Sliding Phase Vocoder (horribly
> slow!), which may be tolerably fast in 2020. Hoping to try out some cool
> uber-hardware with go-faster stripes to run it on.

A sliding DFT for doesn't seem close to demanding teraflop
hardware... only requires a few complex flops per sample,
times the dft length... around a gigaflop or few per channel
maybe.  Probably not to difficult to fit in a medium-sized
FPGA these days.

If you really want a phase vocoder technique requiring a
lot of brute force hardware, then think about continuously
resampling the waveform so that the fft aperature is always
an integer number of periods; then slide the phase vocoder
a fractional hop to match one period (or n), per each
sinusoid/frequency of interest.  This does a decent job of
removing most window artifacts, but requires a fair amount
of compute power if you are looking at a harmonically rich
multi-tonal signal.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On Jul 24, 6:41 pm, "Ron N." <rhnlo...@yahoo.com> wrote:
>
(snipped)
>
> A sliding DFT for doesn't seem close to demanding teraflop
> hardware... only requires a few complex flops per sample,
> times the dft length... around a gigaflop or few per channel
> maybe.  Probably not to difficult to fit in a medium-sized
> FPGA these days.
>
> If you really want a phase vocoder technique requiring a
> lot of brute force hardware, then think about continuously
> resampling the waveform so that the fft aperature is always
> an integer number of periods; then slide the phase vocoder
> a fractional hop to match one period (or n), per each
> sinusoid/frequency of interest.  This does a decent job of
> removing most window artifacts, but requires a fair amount
> of compute power if you are looking at a harmonically rich
> multi-tonal signal.
>
> IMHO. YMMV.
> --
> rhn A.T nicholson d.0.t C-o-M

This -would- use a lot more cycles, which is one point.

In each aperture resampled to integer periods for a tone of interest,
the tone of interest would be prevented from leaking into other tone
bins, but the other tones would not be prevented from leaking into the
bin you are transforming this resampled aperture to generate, so you
only fix leakage into the bins you don't use. This fix to the leakage
out of the bin (scallopping loss) can be corrected by a small complex
convolution of the fft coefficients in the frequency domain if you
know the frequency of the tone of interest, as you must to be able to
resample the aperture as proposed.

Advances in technology usually don't get spent just on doing
inefficient methods faster. We usually can dream big enough to use up
all speed gains without relying on inefficient algorithms to consume
computer cycles. There are, of course, obvious exceptions like
Microsoft software.

Dale B. Dalrymple
http://dbdimages.com

Ron N. wrote:
..
> 
> A sliding DFT for doesn't seem close to demanding teraflop
> hardware... only requires a few complex flops per sample,
> times the dft length... around a gigaflop or few per channel
> maybe.  Probably not to difficult to fit in a medium-sized
> FPGA these days.
>

This is a music-oriented project, so we are not trying to process 
relatively simple multi-tone signals whose charater is known a-priori, 
but full-bandwidth music sources. The CPU load is indeed not so much in 
the SDFT itself, but in the processing applied to each analysis frame, 
which is now at a rate equal to the sampling rate. It becomes comparable 
to addditive synthesis with 1000 oscillators or more - actually, it is 
analysis plus modified additive resynthesis. A conventional overlap-add 
pvoc has an analysis rate more like 344Hz, and we already have many 
systems doing that in real-time on very ordinary computers. But as soon 
as we increase the number of channels being processed (e.g. 5.1 audio at 
96KHz), those computers will struggle. We are looking at massively 
parallel SIMD-style solutions, whcih may well become mainstream 
resources in years to come.


> If you really want a phase vocoder technique requiring a
> lot of brute force hardware, then think about continuously
> resampling the waveform so that the fft aperature is always
> an integer number of periods; then slide the phase vocoder
> a fractional hop to match one period (or n), per each
> sinusoid/frequency of interest. 

See above - the source may be a full drum-kit, or symphony orchestra, 
contemporary electronica, or even wind and sea sounds etc; generally 
there will be no single period to match. We need entirely general 
solutions, we cannot make any assumptions about the source.


Richard Dobson

dbd wrote:
..
> Advances in technology usually don't get spent just on doing
> inefficient methods faster. We usually can dream big enough to use up
> all speed gains without relying on inefficient algorithms to consume
> computer cycles. There are, of course, obvious exceptions like
> Microsoft software.
> 

This question is the heart of the project - Moorer proposed we would 
want to do this (frequency-domain processing as a matter of routine), so 
we are exploring if there is any musical advantage to doing so. We have 
for example already established that the SDFT approach offers usefully 
lower latency than conventional block-based pvoc. Latency is a real 
handicap to live real-time performance, and even if there are no other 
advantages, being able to run such processes without an obviously 
noticeable delay will be sufficient to interest musicians.

And of course we are exploring new possibilities for musical 
transformations, pitch shifting, modulation, etc.

Richard Dobson

On Jul 24, 9:41 pm, "Ron N." <rhnlo...@yahoo.com> wrote:

> A sliding DFT for doesn't seem close to demanding teraflop
> hardware... only requires a few complex flops per sample,
> times the dft length... around a gigaflop or few per channel
> maybe.  Probably not to difficult to fit in a medium-sized
> FPGA these days.

Depends upon what you're doing.  For pro audio nowadays, you're not
even serious unless you're running at 96 kHz or better.  Suppose you
want 10 Hz bin spacing.  Then you need 9600 point DFTs.  Your signals
are real, so you only need to compute 4800 bin values ... per
channel ... per sample.  If it takes ~10 operations per bin value,
that's 4800x10x96000=4.6 Gflops per channel for the forward
transform.  Double that for the inverse transform, and that's 9.2
Gflops per channel just for the transforms.  To implement frequency-
domain filtering and add 4800 complex flops (at seven ops per complex
flop) per channel per sample, your total is 12.4 Gflops per channel.

Do the same at 192 kHz, and that number increases to 49.8 Gflops per
channel.  Do it for five channels at 192 kHz, and you're at a cool 1/4
Tflop.  And that's just for simple filtering.

Do it with 1 Hz bin spacing (which is really not so outrageous) at 192
kHz for five channels, and you get ... 1.24 Tflops.

Why would we do this?  Because we can.  As Dale B. Dalrymple wrote,
"We usually can dream big enough to use up all speed gains ..."

Greg