Improvements to the Sliding Discrete Fourier Transform Algorithm (kSDFT)

[jurihock]

kSDFT

A modulated SDFT network was presented in [mSDFT, Fig. 3]. That network frequency translates the N-delay comb stage’s output spectral energy, originally centered at kfs /N Hz, down to 0 Hz and implements a complex resonator where exact pole/zero cancellation occurs at z = 1 on the z-plane. Although that network is guaranteed stable, it is less computationally efficient than is our proposed SDFT network in Figure 3.

[jurihock]

kSDFT

mSDFT

[jurihock]

BTW: An Efficient Full-Band Sliding DFT Spectrum Analyzer as extension of oSDFT for real-valued input

Statement:

Two surprising properties of both Figure 1 networks are: 1) although they use recursive complex multiplications the networks are guaranteed stable, and 2) the networks compute sliding DFT samples without a comb delay-line section required by traditional sliding DFT networks!

Comment:

I have no experience in OFDM processing, but if your OFDM processing requires you to compute all N output spectral samples of an N-point DFT in real time then one of the networks in this blog’s Figure 1 should achieve your goal.
 
If your OFDM processing requires you to compute, say 8, real time N-point DFT spectral samples (where N is greater than 8) then you merely need to implement 8 sliding DFT networks. That is, one comb section driving 8 separate resonator sections.

Would be a great opportunity to ask Rick about a logarithmic frequency resolution extension on April 1...

[jurihock]

Summary of findings:

• mSDFT
• kSDFT
• oSDFT1
• oSDFT2

My conclusions so far:

• mSDFT is the current implementation, which is still "accurate", "guaranteed stable" and "reasonable fast" (and meanwhile well tested btw).
• kSDFT implementation seems to be more computationally efficient compared to mSDFT (incl. phase correction stage).
• kSDFT implementation seems to be about as fast as oSDFT1 (in case of "full-band" DFT computation).
• oSDFT2 will be definitely faster than oSDFT1 for real-valued input (which an audio signal definitely is).
• oSDFT1 appears to have better noise characteristics compared to mSDFT (not sure about kSDFT).
• Both oSDFT1 and oSDFT2 require a "full-band" DFT computation.
• Both mSDFT and kSDFT can compute a disjointed subset of DFT bins if required.
• kSDFT provides a fractional/noninteger DFT bin estimation extension.
• Both oSDFT1 and oSDFT2 don't require large input buffering (comb stage).

Thoughts:

• The ability to estimate a subset of DFT bins (e.g. upper limit) will be nice, but still not officially supported by the current API.
• Otherwise, an elementary integer downsampling can be applied to reduce the number of DFT bins (while losing time resolution).
• The noninteger DFT bin feature of the kSDFT could be useful for future QDFT estimation.
• But maybe there is a chance to space the oSDFT bins in a logarithmic way.

[jurihock]

oSDFT2

The oSDFT2 is somehow faster than mSDFT (it's hard to verify it in python). On the other side, it seems to produce an artefact in the analysis.py example right at the beginning of the sequence. But except of this area, the estimated spectrogram looks pretty decent (no idea what's about the phase).

[jurihock]

kSDFT (C++)

The C++ kSDFT implementation seems to be nearly as fast as the current mSDFT.

Benchmark:

• analysis.cpp
• single sine wave
• 1s at 44100 Hz
• boxcar window

Measurements:

• mSDFT ➡ 0.14s
• kSDFT ➡ 0.12s

It's true, the kSDFT has less mults, but more adds and a larger delay line.

Also the kSDFT seems to produce strange artefacts, which I did not observe in mSDFT. Maybe there is still a twiddle computation bug, but the benchmark measurements should be correct.

[jurihock]

oSDFT2 (C++)

Benchmark:

• analysis.cpp
• single sine wave
• 1s at 44100 Hz
• boxcar window

Measurements:

• mSDFT ➡ 0.14s
• oSDFT2 ➡ 0.09s

Probably I'll keep both mSDFT (as default implementation) and oSDFT2 (C++ only)...

[jurihock]

Recent blog post by Rick introduces A Fast Guaranteed-Stable Sliding DFT Algorithm.

Where reference [3] is the mSDFT.

Conclusion:

• Practically there is only marginal performance benefit compared to mSDFT
• The even k and odd k+1 bins cannot be stitch together as is (unless there is a special window function to smooth the alternating bins)
• The combination of even k and odd k+1 bins does not provide a higher frequency resolution while reducing the comb delay line length at the same time (unless there is a special window function to virtually shrink the mainlobe's null-to-null width or something)

See also fast_sdft_response.py