# Sliding Discrete Fourier Transform (SDFT)
Forward and inverse Sliding DFT according to [[1]](#1) and [[2]](#2) with following features:
- Arbitrary number of DFT bins
- Built-in analysis window functions Boxcar, Hann (default), Hamming and Blackman
- Customizable time and frequency domain data type in C/C++
- Endless single or multiple sample processing at once
- Optional synthesis latency control parameter
- Real-time low latency<sup>*</sup> analysis and synthesis capability
<sup><sub>*) compared to STFT latency</sub></sup>
The [Sliding Discrete Fourier Transform (SDFT)](https://en.wikipedia.org/wiki/Sliding_DFT) is a recursive approach to compute the Fourier transform sample by sample. In this particular case it's more efficient than the FFT based [Short Time Fourier Transform (STFT)](https://en.wikipedia.org/wiki/Short-time_Fourier_transform) approach with one sample hops. On the other side, the SDFT is still known to suffer from accumulated errors and potential instabilities.
This implementation features the *modulated* SDFT algorithm, which is guaranteed to be stable while being accurate. It takes real valued samples and estimates the corresponding half size complex valued DFT vector for each of them. The length of the estimated DFT vector is not limited to the power of two. The eventually altered DFT vector can also be used to synthesize an output sample.
Compared to STFT, the algorithmic synthesis latency of SDFT is lower and can additionally be reduced at the expense of signal to noise ratio. Spectral data processing coupled with reduced latency is especially useful for real-time applications, e.g. digital audio signal processing.
## Basic usage
### C
```c
#define SDFT_TD_FLOAT // time domain data type (float by default)
#define SDFT_FD_DOUBLE // frequency domain data type (double by default)
#include <sdft/sdft.h> // see also src/c folder
size_t n = ...; // number of samples
size_t m = ...; // number of dft bins
float* x = ...; // analysis samples of shape (n)
float* y = ...; // synthesis samples of shape (n)
double complex* dft = ...; // dft matrix of shape (n, m)
sdft_t* sdft = sdft_alloc(m); // create sdft plan
sdft_sdft_n(sdft, n, x, dft); // extract dft matrix from input samples
sdft_isdft_n(sdft, n, dft, y); // synthesize output samples from dft matrix
sdft_free(sdft); // destroy sdft plan
```
<details>
<summary><strong>MSVC</strong></summary>
<p/>
Due to incomplete [C complex math support](https://docs.microsoft.com/cpp/c-runtime-library/complex-math-support) in MSVC, optionally use following universal typedefs:
* `sdft_float_t` instead of `float`
* `sdft_double_complex_t` instead of `double complex`
or even better the corresponding generic typedefs:
* `sdft_td_t`
* `sdft_fdx_t`
In both cases, the underlying data type results from the `SDFT_TD_*` and `SDFT_FD_*` definitions.
</details>
<details>
<summary><strong>No complex.h? No problem...</strong></summary>
<p/>
Just define `SDFT_NO_COMPLEX_H` to prevent `complex.h` from being included and internally enable compatible complex number representation instead:
```c
typedef struct { sdft_fd_t r, i; } sdft_fdx_t;
```
</details>
### C++
```c++
#include <sdft/sdft.h> // see also src/cpp folder
size_t n = ...; // number of samples
size_t m = ...; // number of dft bins
float* x = ...; // analysis samples of shape (n)
float* y = ...; // synthesis samples of shape (n)
std::complex<double>* dft = ...; // dft matrix of shape (n, m)
SDFT<float, double> sdft(m); // create sdft plan for custom time and frequency domain data types
sdft.sdft(n, x, dft); // extract dft matrix from input samples
sdft.isdft(n, dft, y); // synthesize output samples from dft matrix
```
The time domain data type defaults to `float` and the frequency domain data type to `double`.
### Python
```python
from sdft import SDFT # see also src/python folder
n = ... # number of samples
m = ... # number of dft bins
x = ... # analysis samples of shape (n)
sdft = SDFT(m) # create sdft plan
dft = sdft.sdft(x) # extract dft matrix from input samples
y = sdft.isdft(dft) # synthesize output samples from dft matrix
```
Feel free to obtain current version from [PyPI](https://pypi.org/project/sdft) by executing `pip install sdft`.
## Test spectrogram
Below you can see two spectrograms of the same audio file `test.wav` computed by SDFT and STFT with identical spectral resolution, window function and hop size. Do you see any significant differences between them?
| SDFT | STFT |
| ---- | ---- |
|  |  |
Well, the results are very similar, which is to be considered as the proof of concept...
## See also
If you're interested in Sliding DFT with *logarithmic* frequency resolution, don't forget to browse my [jurihock/qdft](https://github.com/jurihock/qdft) project!
## References
1. <span id="1">Krzysztof Duda (2010). Accurate, Guaranteed Stable, Sliding Discrete Fourier Transform. IEEE Signal Processing Magazine. https://ieeexplore.ieee.org/document/5563098</span>
2. <span id="2">Russell Bradford et al. (2005). Sliding is Smoother Than Jumping. International Computer Music Conference Proceedings. http://hdl.handle.net/2027/spo.bbp2372.2005.086</span>
## License
[github.com/jurihock/sdft](https://github.com/jurihock/sdft) is licensed under the terms of the MIT license.
For details please refer to the accompanying [LICENSE](https://github.com/jurihock/sdft/raw/main/LICENSE) file distributed with it.
Raw data
{
"_id": null,
"home_page": "https://github.com/jurihock/sdft",
"name": "sdft",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3",
"maintainer_email": "",
"keywords": "digital,audio,signal,processing,dasp,sliding,discrete,fourier,transform,sdft,stft,dft,fft,frequency,spectrum,algorithms,analysis,synthesis,c,cpp,python",
"author": "Juergen Hock",
"author_email": "juergen.hock@jurihock.de",
"download_url": "https://files.pythonhosted.org/packages/0b/5d/309683e56c89bdd4672d511f28d8389310ffe541b691b1953f95de1d17b6/sdft-1.4.tar.gz",
"platform": null,
"description": "# Sliding Discrete Fourier Transform (SDFT)\n\n\n\n\n\nForward and inverse Sliding DFT according to [[1]](#1) and [[2]](#2) with following features:\n\n- Arbitrary number of DFT bins\n- Built-in analysis window functions Boxcar, Hann (default), Hamming and Blackman\n- Customizable time and frequency domain data type in C/C++\n- Endless single or multiple sample processing at once\n- Optional synthesis latency control parameter\n- Real-time low latency<sup>*</sup> analysis and synthesis capability\n\n<sup><sub>*) compared to STFT latency</sub></sup>\n\nThe [Sliding Discrete Fourier Transform (SDFT)](https://en.wikipedia.org/wiki/Sliding_DFT) is a recursive approach to compute the Fourier transform sample by sample. In this particular case it's more efficient than the FFT based [Short Time Fourier Transform (STFT)](https://en.wikipedia.org/wiki/Short-time_Fourier_transform) approach with one sample hops. On the other side, the SDFT is still known to suffer from accumulated errors and potential instabilities.\n\nThis implementation features the *modulated* SDFT algorithm, which is guaranteed to be stable while being accurate. It takes real valued samples and estimates the corresponding half size complex valued DFT vector for each of them. The length of the estimated DFT vector is not limited to the power of two. The eventually altered DFT vector can also be used to synthesize an output sample.\n\nCompared to STFT, the algorithmic synthesis latency of SDFT is lower and can additionally be reduced at the expense of signal to noise ratio. Spectral data processing coupled with reduced latency is especially useful for real-time applications, e.g. digital audio signal processing.\n\n## Basic usage\n\n### C\n\n```c\n#define SDFT_TD_FLOAT // time domain data type (float by default)\n#define SDFT_FD_DOUBLE // frequency domain data type (double by default)\n\n#include <sdft/sdft.h> // see also src/c folder\n\nsize_t n = ...; // number of samples\nsize_t m = ...; // number of dft bins\n\nfloat* x = ...; // analysis samples of shape (n)\nfloat* y = ...; // synthesis samples of shape (n)\n\ndouble complex* dft = ...; // dft matrix of shape (n, m)\n\nsdft_t* sdft = sdft_alloc(m); // create sdft plan\n\nsdft_sdft_n(sdft, n, x, dft); // extract dft matrix from input samples\nsdft_isdft_n(sdft, n, dft, y); // synthesize output samples from dft matrix\n\nsdft_free(sdft); // destroy sdft plan\n```\n\n<details>\n<summary><strong>MSVC</strong></summary>\n<p/>\n\nDue to incomplete [C complex math support](https://docs.microsoft.com/cpp/c-runtime-library/complex-math-support) in MSVC, optionally use following universal typedefs:\n\n* `sdft_float_t` instead of `float`\n* `sdft_double_complex_t` instead of `double complex`\n\nor even better the corresponding generic typedefs:\n\n* `sdft_td_t`\n* `sdft_fdx_t`\n\nIn both cases, the underlying data type results from the `SDFT_TD_*` and `SDFT_FD_*` definitions.\n\n</details>\n\n<details>\n<summary><strong>No complex.h? No problem...</strong></summary>\n<p/>\n\nJust define `SDFT_NO_COMPLEX_H` to prevent `complex.h` from being included and internally enable compatible complex number representation instead:\n\n```c\ntypedef struct { sdft_fd_t r, i; } sdft_fdx_t;\n```\n\n</details>\n\n### C++\n\n```c++\n#include <sdft/sdft.h> // see also src/cpp folder\n\nsize_t n = ...; // number of samples\nsize_t m = ...; // number of dft bins\n\nfloat* x = ...; // analysis samples of shape (n)\nfloat* y = ...; // synthesis samples of shape (n)\n\nstd::complex<double>* dft = ...; // dft matrix of shape (n, m)\n\nSDFT<float, double> sdft(m); // create sdft plan for custom time and frequency domain data types\n\nsdft.sdft(n, x, dft); // extract dft matrix from input samples\nsdft.isdft(n, dft, y); // synthesize output samples from dft matrix\n```\n\nThe time domain data type defaults to `float` and the frequency domain data type to `double`.\n\n### Python\n\n```python\nfrom sdft import SDFT # see also src/python folder\n\nn = ... # number of samples\nm = ... # number of dft bins\n\nx = ... # analysis samples of shape (n)\n\nsdft = SDFT(m) # create sdft plan\n\ndft = sdft.sdft(x) # extract dft matrix from input samples\ny = sdft.isdft(dft) # synthesize output samples from dft matrix\n```\n\nFeel free to obtain current version from [PyPI](https://pypi.org/project/sdft) by executing `pip install sdft`.\n\n## Test spectrogram\n\nBelow you can see two spectrograms of the same audio file `test.wav` computed by SDFT and STFT with identical spectral resolution, window function and hop size. Do you see any significant differences between them?\n\n| SDFT | STFT |\n| ---- | ---- |\n|  |  |\n\nWell, the results are very similar, which is to be considered as the proof of concept...\n\n## See also\n\nIf you're interested in Sliding DFT with *logarithmic* frequency resolution, don't forget to browse my [jurihock/qdft](https://github.com/jurihock/qdft) project!\n\n## References\n\n1. <span id=\"1\">Krzysztof Duda (2010). Accurate, Guaranteed Stable, Sliding Discrete Fourier Transform. IEEE Signal Processing Magazine. https://ieeexplore.ieee.org/document/5563098</span>\n\n2. <span id=\"2\">Russell Bradford et al. (2005). Sliding is Smoother Than Jumping. International Computer Music Conference Proceedings. http://hdl.handle.net/2027/spo.bbp2372.2005.086</span>\n\n## License\n\n[github.com/jurihock/sdft](https://github.com/jurihock/sdft) is licensed under the terms of the MIT license.\nFor details please refer to the accompanying [LICENSE](https://github.com/jurihock/sdft/raw/main/LICENSE) file distributed with it.\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Forward and inverse Sliding Discrete Fourier Transform (Sliding DFT)",
"version": "1.4",
"split_keywords": [
"digital",
"audio",
"signal",
"processing",
"dasp",
"sliding",
"discrete",
"fourier",
"transform",
"sdft",
"stft",
"dft",
"fft",
"frequency",
"spectrum",
"algorithms",
"analysis",
"synthesis",
"c",
"cpp",
"python"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "4470d2750abf9bc1d0c398311e2f31222b9bccf2fffb97c1eacc2587823985a3",
"md5": "509425c282fd6bd1293c06f5cb163d48",
"sha256": "276f0c59b723abf28d618639e711eb4d0d5f913e3a1ad1474a3734cf3bb47dc8"
},
"downloads": -1,
"filename": "sdft-1.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "509425c282fd6bd1293c06f5cb163d48",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3",
"size": 9782,
"upload_time": "2023-01-15T11:32:36",
"upload_time_iso_8601": "2023-01-15T11:32:36.983023Z",
"url": "https://files.pythonhosted.org/packages/44/70/d2750abf9bc1d0c398311e2f31222b9bccf2fffb97c1eacc2587823985a3/sdft-1.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0b5d309683e56c89bdd4672d511f28d8389310ffe541b691b1953f95de1d17b6",
"md5": "2fb32d80aa8155743586595d7295db94",
"sha256": "495a591f9ee89d59489b65b25d11548754c9dad3401e884c550f74c51de0a889"
},
"downloads": -1,
"filename": "sdft-1.4.tar.gz",
"has_sig": false,
"md5_digest": "2fb32d80aa8155743586595d7295db94",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3",
"size": 10215,
"upload_time": "2023-01-15T11:32:38",
"upload_time_iso_8601": "2023-01-15T11:32:38.980752Z",
"url": "https://files.pythonhosted.org/packages/0b/5d/309683e56c89bdd4672d511f28d8389310ffe541b691b1953f95de1d17b6/sdft-1.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-15 11:32:38",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "jurihock",
"github_project": "sdft",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "sdft"
}
JSON
