fftea

一个简单高效的FFT实现。

使用Cooley-Tukey算法支持实数或复数幂次为2的数组的FFT。还包括一些相关实用程序，如窗口函数、STFT和逆FFT。

之所以构建此包，是因为package:fft不再积极维护，并且实现效率不高。有几项改进使此实现更有效。

• 主FFT类使用给定的大小进行构造，这样只需计算一次扭曲因子。这对于STFT特别有用。
• 不使用复数的包装器类，仅使用Float64x2List。每个小型包装器类都是单独分配和解引用的。对于FFT复数数学等内部循环代码，这会产生很大差异。Float64x2还可以利用SIMD优化。
• FFT算法是就地执行的，因此不会分配额外的数组。
• 基于循环的FFT，而不是递归。
• 使用三角函数技巧，只计算四分之一的扭曲因子。

用法

运行基本的实值FFT

// myData.length must be a power of two. Eg 2, 4, 8, 16, ...
List<double> myData = ...;

final fft = FFT(myData.length);
final freq = fft.realFft(myData);

freq是一个Float64x2List，表示复数列表。有关Float64x2List的有用扩展方法，请参阅ComplexArray。

为了效率，请避免每次都重新创建FFT对象。而是创建一个所需大小的FFT对象，并重复使用它。

运行STFT计算频谱图

// audio.length *doesn't* need to be a power of two. It can be any legnth.
List<double> audio = ...;

final chunkSize = 1024;  // Must be a power of two.
final stft = STFT(chunkSize, Window.hanning(chunkSize));

final spectrogram = <Float64List>[];
stft.run(audio, (Float64x2List freq) {
  spectrogram.add(freq.discardConjugates().magnitudes());
});

实值FFT的结果大约有一半是冗余数据，因此discardConjugates会从结果中删除这些数据。

[和项，...项...，奈奎斯特项，...共轭项...] ^—— 这些项被保留 ——^ ^- 已丢弃 -^

然后magnitudes会丢弃复数的相位数据，只保留幅度，这通常是进行频谱图分析时所需的。

如果你想知道频谱图中某个元素的频率，请使用stft.frequency(index, samplingFrequency)，其中samplingFrequency是audio录制时的频率，例如44100。频谱图的最大频率（也称为奈奎斯特频率）将是stft.frequency(chunkSize / 2, samplingFrequency)。

有关更详细的用法，请参阅示例。

基准测试

我发现了一些其他有前景的FFT实现，因此决定也对它们进行基准测试：scidart和smart_signal_processing。

运行基准测试

1. 转到bench目录并运行pub get，cd bench && dart pub get
2. 运行dart run bench.dart

fftea通过缓存两次运行之间的扭曲因子以及就地执行FFT来获得其部分速度。因此，基准测试被分为缓存和就地变体。在适当的情况下，缓存和就地执行也应用于其他一些库。

在下表中，“cached”表示FFT对象的构造不计入基准测试时间。而“in-place”表示使用就地FFT，并且将输入数据转换为FFT所需格式的转换和复制时间不计入基准测试。在Ubuntu上的Dell XPS 13上运行。

实际上，您通常会提前知道FFT的大小，因此可以轻松地一次性构造FFT对象，以利用缓存。有时也可以利用就地加速，例如，如果您必须从其他源复制数据，那么您最好自己构造扁平的复数数组。由于并非总是可能这样，因此“fftea, cached”时间可能最具代表性。在这种情况下，fftea比package:fft快约60-80倍，比smart_signal_processing快约30%。不确定scidart出了什么问题，但它似乎是O(n^2)。

* Scidart的FFT没有就地模式，但它们确实使用了自定义格式，因此就地表示转换为该格式的时间不包含在基准测试中。

GitHub

查看 Github