快速傅立叶变换 (FFT) 的 C# 实现

Question

Closed. This question is seeking recommendations for software libraries, tutorials, tools, books, or other off-site resources. It does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

我们不允许提出寻求软件库、教程、工具、书籍或其他场外资源推荐的问题。 您可以编辑问题，以便用事实和引文来回答。

7 年前已关闭。

Answer 1

开发 AForge 的人做得相当不错，但还达不到商业质量。 从中学习很棒，但你可以看出他也在学习，所以他犯了一些非常严重的错误，比如假设图像的大小，而不是使用正确的每像素位数。

我并不是要打击这个人，我尊重他学习所有这些并向我们展示如何做到这一点。 我认为他现在是一名博士，或者至少他即将成为一名博士，所以他真的很聪明，只是不是一个商业可用的图书馆。

Math.Net 库在处理傅立叶变换和复杂图像/数字时有其自身的怪异之处。 就像，如果我没记错的话，它以人类可见的格式输出傅立叶变换，如果您想查看变换的图片，这对人类来说很好，但当您期望数据处于某种特定格式时，它就不太好了格式（正常格式）。 我可能会弄错，但我只记得有一些奇怪的地方，所以我实际上去了他们用于傅里叶东西的原始代码，它工作得更好。 (ExocortexDSP v1.2 http://www.exocortex.org/dsp/)

Math.net 也在处理来自 FFT 的数据时，还有一些我不喜欢的其他时髦之处，我不记得那是什么了，我只知道从 ExoCortex DSP 库中获得我想要的东西要容易得多。 但我不是数学家或工程师； 对于那些人来说这可能很有意义。

所以！ 我使用从 ExoCortex 中提取的 FFT 代码，这是 Math.Net 的基础，没有任何其他东西，而且效果很好。

最后，我知道这不是 C#，但我已经开始考虑使用 FFTW (http://www.fftw.org /）。 这个人已经制作了一个 C# 包装器，所以我打算检查一下，但还没有实际使用它。 (http://www.sdss.jhu.edu/~tamas/bytes/ fftwcsharp.html）

哦！ 我不知道你这样做是为了学校还是工作，但无论怎样，iTunes 大学上都有斯坦福大学教授提供的精彩免费系列讲座。

https://podcasts.apple.com/us /podcast/the-fourier-transforms-and-its-applications/id384232849

Answer 2

AForge.net 是一个免费（开源）库，支持快速傅里叶变换。 （请参阅 Sources/Imaging/ComplexImage.cs对于使用，Sources/Math/FourierTransform.cs 用于实施）

Answer 3

Math.NET 的 Iridium 库 提供快速、定期更新的数学相关函数集合，包括 FFT。 它根据 LGPL 获得许可，因此您可以在商业产品中自由使用它。

Answer 4

我看到这是一个旧线程，但就其价值而言，这是我在 2010 年编写的免费（MIT 许可证）一维 2 次方长度 C# FFT 实现。

我还没有将其性能与其他实现进行比较C# FFT 实现。 我写它主要是为了比较Flash/ActionScript和Silverlight/C#的性能。 后者要快得多，至少对于数字运算来说是这样。

/**
 * Performs an in-place complex FFT.
 *
 * Released under the MIT License
 *
 * Copyright (c) 2010 Gerald T. Beauregard
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */
public class FFT2
{
    // Element for linked list in which we store the
    // input/output data. We use a linked list because
    // for sequential access it's faster than array index.
    class FFTElement
    {
        public double re = 0.0;     // Real component
        public double im = 0.0;     // Imaginary component
        public FFTElement next;     // Next element in linked list
        public uint revTgt;         // Target position post bit-reversal
    }

    private uint m_logN = 0;        // log2 of FFT size
    private uint m_N = 0;           // FFT size
    private FFTElement[] m_X;       // Vector of linked list elements

    /**
     *
     */
    public FFT2()
    {
    }

    /**
     * Initialize class to perform FFT of specified size.
     *
     * @param   logN    Log2 of FFT length. e.g. for 512 pt FFT, logN = 9.
     */
    public void init(
        uint logN )
    {
        m_logN = logN;
        m_N = (uint)(1 << (int)m_logN);

        // Allocate elements for linked list of complex numbers.
        m_X = new FFTElement[m_N];
        for (uint k = 0; k < m_N; k++)
            m_X[k] = new FFTElement();

        // Set up "next" pointers.
        for (uint k = 0; k < m_N-1; k++)
            m_X[k].next = m_X[k+1];

        // Specify target for bit reversal re-ordering.
        for (uint k = 0; k < m_N; k++ )
            m_X[k].revTgt = BitReverse(k,logN);
    }

    /**
     * Performs in-place complex FFT.
     *
     * @param   xRe     Real part of input/output
     * @param   xIm     Imaginary part of input/output
     * @param   inverse If true, do an inverse FFT
     */
    public void run(
        double[] xRe,
        double[] xIm,
        bool inverse = false )
    {
        uint numFlies = m_N >> 1;   // Number of butterflies per sub-FFT
        uint span = m_N >> 1;       // Width of the butterfly
        uint spacing = m_N;         // Distance between start of sub-FFTs
        uint wIndexStep = 1;        // Increment for twiddle table index

        // Copy data into linked complex number objects
        // If it's an IFFT, we divide by N while we're at it
        FFTElement x = m_X[0];
        uint k = 0;
        double scale = inverse ? 1.0/m_N : 1.0;
        while (x != null)
        {
            x.re = scale*xRe[k];
            x.im = scale*xIm[k];
            x = x.next;
            k++;
        }

        // For each stage of the FFT
        for (uint stage = 0; stage < m_logN; stage++)
        {
            // Compute a multiplier factor for the "twiddle factors".
            // The twiddle factors are complex unit vectors spaced at
            // regular angular intervals. The angle by which the twiddle
            // factor advances depends on the FFT stage. In many FFT
            // implementations the twiddle factors are cached, but because
            // array lookup is relatively slow in C#, it's just
            // as fast to compute them on the fly.
            double wAngleInc = wIndexStep * 2.0*Math.PI/m_N;
            if (inverse == false)
                wAngleInc *= -1;
            double wMulRe = Math.Cos(wAngleInc);
            double wMulIm = Math.Sin(wAngleInc);

            for (uint start = 0; start < m_N; start += spacing)
            {
                FFTElement xTop = m_X[start];
                FFTElement xBot = m_X[start+span];

                double wRe = 1.0;
                double wIm = 0.0;

                // For each butterfly in this stage
                for (uint flyCount = 0; flyCount < numFlies; ++flyCount)
                {
                    // Get the top & bottom values
                    double xTopRe = xTop.re;
                    double xTopIm = xTop.im;
                    double xBotRe = xBot.re;
                    double xBotIm = xBot.im;

                    // Top branch of butterfly has addition
                    xTop.re = xTopRe + xBotRe;
                    xTop.im = xTopIm + xBotIm;

                    // Bottom branch of butterly has subtraction,
                    // followed by multiplication by twiddle factor
                    xBotRe = xTopRe - xBotRe;
                    xBotIm = xTopIm - xBotIm;
                    xBot.re = xBotRe*wRe - xBotIm*wIm;
                    xBot.im = xBotRe*wIm + xBotIm*wRe;

                    // Advance butterfly to next top & bottom positions
                    xTop = xTop.next;
                    xBot = xBot.next;

                    // Update the twiddle factor, via complex multiply
                    // by unit vector with the appropriate angle
                    // (wRe + j wIm) = (wRe + j wIm) x (wMulRe + j wMulIm)
                    double tRe = wRe;
                    wRe = wRe*wMulRe - wIm*wMulIm;
                    wIm = tRe*wMulIm + wIm*wMulRe;
                }
            }

            numFlies >>= 1;     // Divide by 2 by right shift
            span >>= 1;
            spacing >>= 1;
            wIndexStep <<= 1;   // Multiply by 2 by left shift
        }

        // The algorithm leaves the result in a scrambled order.
        // Unscramble while copying values from the complex
        // linked list elements back to the input/output vectors.
        x = m_X[0];
        while (x != null)
        {
            uint target = x.revTgt;
            xRe[target] = x.re;
            xIm[target] = x.im;
            x = x.next;
        }
    }

    /**
     * Do bit reversal of specified number of places of an int
     * For example, 1101 bit-reversed is 1011
     *
     * @param   x       Number to be bit-reverse.
     * @param   numBits Number of bits in the number.
     */
    private uint BitReverse(
        uint x,
        uint numBits)
    {
        uint y = 0;
        for (uint i = 0; i < numBits; i++)
        {
            y <<= 1;
            y |= x & 0x0001;
            x >>= 1;
        }
        return y;
    }

}

Answer 5

一个老问题，但它仍然出现在 Google 结果中...

找到一个非常不受限制的 MIT 许可的 C# / .NET 库

可以在https://www.codeproject.com/articles/1107480/dsplib-fft-dft-fourier-transform-library-for- net

这个库速度很快，因为它在多个内核上并行线程，并且非常完整且易于使用。

Answer 6

这是另一个； Ooura FFT 的 C# 端口。 这是相当快的。 该软件包还包括重叠/相加卷积和一些其他 DSP 内容，均获得 MIT 许可。

https://github.com/hughpyle/inguz-DSPUtil/blob/ master/Fourier.cs

Answer 7

http://www.exocortex.org/dsp/ 是一个带有 FFT 的开源 C# 数学库算法。

Answer 8

如果您不介意输入的话，Numerical Recipes 网站 (http://www.nr.com/) 有一个 FFT。我正在开展一个项目，将 Labview 程序转换为 C# 2008、.NET 3.5 以获取数据和然后看频谱。 不幸的是，Math.Net 使用最新的 .NET 框架，所以我无法使用该 FFT。 我尝试了外皮质 - 它有效，但结果与 Labview 结果相匹配，而且我不知道足够的 FFT 理论来知道是什么导致了问题。 所以我在数字食谱网站上尝试了 FFT，它成功了！ 我还能够对 Labview 低旁瓣窗口进行编程（并且必须引入缩放因子）。

您可以在他们的网站上以访客身份阅读《数值食谱》一书的章节，但这本书非常有用，因此我强烈建议购买它。 即使您最终使用了 Math.NET FFT。

Answer 9

对于针对 Intel 处理器调整的多线程实现，我会查看 Intel 的 MKL 库。 它不是免费的，但是价格实惠（不到 100 美元）并且速度极快 - 但您需要通过 P/Invokes 调用它的 C dll。 Exocortex 项目在 6 年前停止了开发，所以如果这是一个重要的项目，我会小心使用它。