How about the sliding DFT?

[jurihock]

Evaluate following work:

1. Sliding is smoother than jumping
2. The Sliding Phase Vocoder
3. Real-time Sliding Phase Vocoder using a Commodity GPU
4. Understanding and Implementing the Sliding DFT
5. bronsonp/SlidingDFT (prefer [6])
6. Accurate, Guaranteed Stable, Sliding Discrete Fourier Transform (aka mSDFT)
7. Guaranteed stable sliding Goertzel implementation (see paper suggestions by Rick Lyons)
8. Streaming Spectral Processing with Consumer-Level Graphics Processing Units
9. High-Precision, Permanently Stable, Modulated Hopping Discrete Fourier Transform (aka mHDFT; inverse transform?)
10. Recursive sliding DFT algorithms: A review (looks interesting, but have no access to this one...)
11. Guaranteed-Stable Sliding DFT Algorithm With Minimal Computational Requirements (aka oSDFT)

[jurihock]

The sliding DFT will be first implemented and tested out in voyx.

[jurihock]

As mentioned in [3] the classic SDFT implementation suffers from accumulated frequency bin errors. These errors may become visible or audible after about 10 minutes on single precision, depending on the source signal.

The modulated SDFT implementation proposed in [6] offers reduced error level even on single precision, but at "slightly" higher computational cost (by about factor 1.5 in my measurements).

With cyclic chirp or sweep as a source signal the frequency error appears immediately at about -75 dBFS using the classic SDFT [1] and still stays below -100 dBFS using the modulated SDFT [6] after 30 min. That's the difference...

[jurihock]

oSDFT

Not to be confused with oSDFT, which is a completely another nice algorithm and probably most suitable for FPGAs, due to accumulation at the end of the cycle.

The author of [11] reports a lower numerical error level of gSDFT compared to mSDFT from [6], but also a higher workload on larger windows. The finally proposed oSDFT should have exactly the same numerical error level as gSDFT and the lowest workload "among the existing stable" SDFT algorithms...

Unclear:

• The memory consumption of the oSDFT is much higher compared to mSDFT. In other words, if a large space of memory is used excessively, would that cause caching issues on larger DFT windows? (e.g. compared to brute force computation like in mSDFT with much less "random" memory access)
• Like shown in table V in [11], in case of M=16 the oSDFT is about 2 times faster than mSDFT, but in case of M=32 only 1.65 times. I'm assuming a non-linear progression with increasing window size. The window size of 32 bins is too tiny for audio, we need something at least 1024.

---

BTW the gSDFT seems to be patented...

[jurihock]

TODO:

• The SDFT code is consolidated in https://github.com/jurihock/sdft, so use it in the future...
• The QDFT https://github.com/jurihock/qdft might make more sense...
• Applications of a Constant-Q Transform for Time- and Pitch-Scale Modifications (more more)
• Pitch Shifting of Audio Signals Using the Constant-Q Transform
• Audio Pitch Shifting Using the Constant-Q Transform

[NathanRoyer]

Hi, first of all thank you for publishing this project, the python implementation is very clear and I was able to understand your algorithm pretty well.

I see that you have "removed the SDFT prototype" just above.
Have you given up on using the SDFT or one of its variants in this project? If yes, could you give the reason?

Thanks

[jurihock]

Hi Nathan,

the main reason for investigating the SDFT was the ability to reduce the algorithmic latency of the "classic" STFT procedure. Meanwhile I've discovered the properties of the asymmetric windows #38, which allows to lower the algorithmic latency of the "classic" STFT as well. Even if this can lead to artefacts under certain circumstances #44.

In terms of "quality", I believe that the QDFT would be a more suitable tool than the SDFT (and also STFT), due to its logarithmic resolution. It's likely that both QDFT and SDFT approaches would require some major algorithmic redesign. Especially for formant preservation. Real-time processing is another key consideration. Both QDFT and SDFT are definitely more computationally intensive than STFT, due to the sample-by-sample data processing.

In short, the SDFT is not currently in focus. I think QDFT or maybe TFR #43 would make more sense for this kind of application.