65.9K
CodeProject 正在变化。 阅读更多。
Home

关于 .NET 的 FFT 实现比较

Christian Woltering
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (22投票s)

2016年5月15日

CPOL

5分钟阅读

viewsIcon

90984

downloadIcon

2573

对 .NET 平台上的快速傅里叶变换 (FFT) 实现进行比较和基准测试

引言

在这篇简短的文章中，我们将比较 .NET 平台上的几种快速傅里叶变换 (FFT) 实现。参赛选手包括：

  Accord Exocortex Math.NET NWaves NAudio Lomont DSPLib FFTW
版本 3.8.0 1.2 5.0 0.9.6 2.1 1.1 (2017) 3.3.9
许可证 LGPL BSD MIT MIT MIT - MIT GPL
Assemblies 3 1 1 1 1 - - 1+1
大小 3.6 MB - 1.6 MB 0.3 MB 0.2 MB - - 2.3 MB
Nuget 是 否 是 是 是 否 否 否

备注

  • Accord.NET 是一个结合了机器学习、音频和图像处理的框架。它已不再积极开发。
  • Exocortex 项目创建于 .NET 1.0 早期。本文提供的副本已更新以支持 .NET Standard 2.0 并使用 System.Numerics 命名空间中的 Complex 类型。
  • NAudio 使用自定义的 Complex 类型实现，具有单精度实部和虚部。
  • DSPLib 是一个简洁的库，用于对实值输入进行 FFT 和频谱分析。未实现逆 FFT。
  • FFTW 是一个流行的原生 FFT 实现。它可能是互联网上你能找到的最快的开源实现，因此与托管代码进行比较有点不公平。不过，我认为看看代码的表现如何会很有趣。

FFTW 二进制文件未随本文分发。如果你想在基准测试中包含 FFTW，则必须手动下载 fftw3.dll 和 fftw3f.dll 二进制文件。要获取最新版本，请尝试 Conda 或访问 Github 项目获取更多选项：https://github.com/wo80/SharpFFTW。

基准测试

我对实值输入（音频处理）的一维 FFT 特别感兴趣。所有测试都使用了以下接口。如果你有自己的 FFT 实现，可以通过实现此接口并实例化 Util.LoadTests() 方法中的测试来轻松将其集成到基准测试中。

interface ITest
{
    /// <summary>
    /// Gets the name of the test.
    /// </summary>
    string Name { get; }

    /// <summary>
    /// Gets the FFT size of the test.
    /// </summary>
    int Size { get; }

    /// <summary>
    /// Gets or sets a value indicating whether the test should be run.
    /// </summary>
    bool Enabled { get; set; }

    /// <summary>
    /// Prepare the real valued data for FFT processing.
    /// </summary>
    /// <param name="data">The samples array.</param>
    void Initialize(double[] data);

    /// <summary>
    /// Apply FFT to data.
    /// </summary>
    /// <param name="forward">If false, apply inverse FFT.</param>
    void FFT(bool forward);

    // Ignore for benchmark (used only for 'FFT Explorer', see next section)
    double[] Spectrum(double[] input, bool scale);
}

请查看 fftbench.Common 项目的 fftbench.Benchmark 命名空间中的不同测试，了解如何正确实现接口。

Exocortex、Lomont 和 FFTW 对实值数据有专门的实现，预计代码速度将是标准复数实现的近两倍。

Accord.NET、Math.NET 和 FFTW 支持任意大小的输入数组（即大小不必是 2 的幂）。由于 Exocortex、NAudio、NWaves 和 Lomont 只支持基数为 2 的算法，因此基准测试使用了大小为 2 的幂的数组。

结果

运行 fftbench 控制台应用程序，输出可能如下所示。第一列显示了与 Exocortex (real) 相比的相对速度。
 

$ ./fftbench 10 200
FFT size: 1024
  Repeat: 200

[14/14] Done

    FFTWF (real):  0.2  [min:    1.29, max:    1.64, mean:    1.33, stddev:    0.03]
     FFTW (real):  0.2  [min:    1.34, max:    1.60, mean:    1.43, stddev:    0.05]
            FFTW:  0.5  [min:    2.86, max:    3.13, mean:    2.87, stddev:    0.03]
Exocortex (real):  1.0  [min:    5.72, max:    6.20, mean:    5.76, stddev:    0.05]
   Lomont (real):  1.1  [min:    6.12, max:    8.04, mean:    6.26, stddev:    0.17]
   NWaves (real):  1.5  [min:    8.44, max:   10.73, mean:    8.52, stddev:    0.24]
          NWaves:  1.7  [min:    9.70, max:   11.90, mean:    9.79, stddev:    0.21]
       Exocortex:  1.9  [min:   10.56, max:   12.93, mean:   10.71, stddev:    0.22]
          Lomont:  1.9  [min:   10.58, max:   15.90, mean:   10.77, stddev:    0.38]
          NAudio:  2.1  [min:   11.80, max:   14.17, mean:   12.03, stddev:    0.20]
          AForge:  2.6  [min:   14.72, max:   15.90, mean:   14.93, stddev:    0.12]
          DSPLib:  2.8  [min:   15.30, max:   22.10, mean:   15.91, stddev:    0.94]
          Accord:  3.8  [min:   21.06, max:   29.19, mean:   21.69, stddev:    0.93]
        Math.NET:  7.4  [min:   38.26, max:   73.53, mean:   42.74, stddev:    4.60]

Timing in microseconds.

在基准测试中，每个 FFT 实际上被调用了 50 * 200 次（重复次数取自第二个命令行参数 (200)，乘以默认的 50 次内部迭代）。FFT 大小为 2^10（第一个命令行参数）。基准测试是在 AMD Ryzen 3600 处理器上运行的。

下一个图表显示了不同 FFT 大小为 1024、2048 和 4096 的基准测试结果。使用了 fftbench-win 应用程序，重复次数为 200。

解释 FFT 结果

fftbench-win 应用程序（仅包含在文章下载中，不在 Github 上）包含一个名为 FFT Explorer 的工具。你可以通过单击基准测试窗口中最左侧的图标来打开它。

FFT Explorer 允许你选择 FFT 实现、输入信号和 FFT 大小。三个图将显示输入信号、所选 FFT 计算出的频谱以及逆 FFT 计算出的信号。

让我们来看一个 SignalGenerator 类的示例信号。生成的信号是一个简单的正弦波，频率为 **1.0 Hz**，幅度为 **20.0**。

public static double[] Sine(int n)
{
    const int FS = 64; // sampling rate

    return MathNet.Numerics.Generate.Sinusoidal(n, FS, 1.0, 20.0);
}

将 FFT 帧大小设置为 n = **256**。采样率为 **64 Hz**，我们的周期性信号将在选定的窗口内精确重复四次。请注意，所有值都选择为使信号周期、采样率和 FFT 大小精确匹配。这样，我们就无需处理频谱泄漏。

FFT 输出的每个 bin 的间隔由频率分辨率 (采样率) / (FFT 大小) 决定，在本例中为 **64 / 256 = 0.25**。因此，我们预计对应于我们 **1.0 Hz** 信号的峰值将出现在 bin 号 **4**（因为 **1.0 = 4 * 0.25**）。

由于离散傅里叶变换 (DFT) 的性质，信号的频谱将被缩放 n = **256** 倍，因此如果不对其进行进一步缩放，我们预计值为 **20.0 * 256 / 2** = **2560**。我们除以 **2**，因为幅度分布在两个 bin 中。第二个 bin 位于索引 256 - 4 = *252*，将具有相同的幅度，因为对于实值输入信号，FFT 输出是（共轭）对称的（跨 n/2，即奈奎斯特频率对应的 bin）。

峰值的实际值在不同的 FFT 实现之间可能不一致，因为没有通用的缩放约定。如果 FFT 大小为 n，则某些实现将 FFT 乘以 1/n，某些实现将逆 FFT 乘以 1/n，而某些实现则将两者都乘以 1/sqrt(n)。有些则根本不缩放（例如 FFTW）。

下表显示了不同 FFT 对上述示例计算出的幅度。

  Accord.NET Exocortex.DSP Math.NET NAudio NWaves Lomont DSPLib FFTW
值 2560 2560 160 10 2560 160 10 2560

可以看到 NAudio 和 DSPLib 按 1/n 缩放，而 Math.NET 和 Lomont 按 1/sqrt(n) 缩放（Math.NET 和 Lomont 都允许用户更改缩放约定；上面计算的值并用于基准测试的值代表默认设置）。

结论

显然，并且并非完全出乎意料，FFTW 是明显的赢家。因此，如果使用原生 GPL 许可的库对你来说是一个选择，那就用它吧。放眼托管代码，NWaves 的表现相当不错。Exocortex 和 Lomont 对于较小尺寸的 FFT 表现都很好，但复数 FFT 的性能似乎随着尺寸增大而下降。对于实值信号，Exocortex 和 Lomont 的表现都非常好，即使对于较大的尺寸。

历史

  • 2016-05-15 - 初始版本
  • 2016-06-14 - 添加评论中请求的信息
  • 2018-09-02 - 更新库，包含 DSPLib 并修复基准测试（感谢 I'm Chris，见评论）
  • 2022-07-02 - 更新库，包含 NWaves，链接到 SharpFFTW/fftbench Github 项目
© . All rights reserved.