已经有很多出色的 FFT 库。 Kiss FFT 并不试图比它们中的任何一个更好。它只是尝试成为一个相当高效、适度有用的 FFT，可以使用固定或浮点数据类型，并且可以在几分钟内通过简单的许可将其合并到某人的 C 程序中。

    #include "kiss_fft.h"

    kiss_fft_cfg cfg = kiss_fft_alloc( nfft ,is_inverse_fft ,0,0 );

    while ...
    
        ... // put kth sample in cx_in[k].r and cx_in[k].i
        
        kiss_fft( cfg , cx_in , cx_out );
        
        ... // transformed. DC is in cx_out[0].r and cx_out[0].i 
        
    free(cfg);

注意：频域数据存储从直流到 2π。因此 cx_out[0] 是 FFT 的直流分量，cx_out[nfft/2] 是奈奎斯特分量（如果存在）

声明位于 "kiss_fft.h" 中，以及您需要使用的函数的简要说明。

* multi-dimensional FFTs 
* real-optimized FFTs  (returns the positive half-spectrum: (nfft/2+1) complex frequency bins)
* fast convolution FIR filtering (not available for fixed point)
* spectrum image creation

核心 fft 和大多数 tools/ 代码可以编译为使用 float、double 或 Q15 short 采样。默认值为 float。

我开始编写这段代码是因为我找不到一个不使用汇编代码的定点 FFT。我从浮点数开始，以便在处理定点问题之前先理清理论。最后，我得到了一小段代码，可以很容易地重新编译以使用 short、float 或 double (其他类型也应该很容易) 进行 fft。

Once I got my FFT working, I was curious about the speed compared to

一个备受尊敬且高度优化的 fft 库。我不想批评这个伟大的库，所以我们称之为 FFT_BRANDX。在此过程中，我了解到

1. FFT_BRANDX has more than 100K lines of code. The core of kiss_fft is about 500 lines (cpx 1-d).
2. It took me an embarrassingly long time to get FFT_BRANDX working.
3. A simple program using FFT_BRANDX is 522KB. A similar program using kiss_fft is 18KB (without optimizing for size).
4. FFT_BRANDX is roughly twice as fast as KISS FFT in default mode.

It is wonderful that free, highly optimized libraries like FFT_BRANDX exist.

但此类库背负着巨大的复杂性负担，这些复杂性对于提取每一丝性能是必要的。

1) scaling : is there a constant multiplier between what you got and what you want?
2) mixed build environment -- all code must be compiled with same preprocessor 
definitions for FIXED_POINT and kiss_fft_scalar

答：可能不会，除非你付钱给我。我很乐意回答有针对性和主题性的问题，但我可能会把你推荐给一本书、一个论坛或一些其他资源。

Kiss 在 0.63 秒的 CPU 时间内执行了 10000 个 1024 点 cpx fft。相比之下，md5sum 花费了两倍的时间来处理相同数量的数据。

Kiss FFT 使用时间抽取、混合基、异地 FFT。如果您给它一个输入缓冲区
和输出缓冲区相同，则将创建一个临时缓冲区来保存数据。

不使用静态数据。 kiss_fft 的核心例程是线程安全的（但不是所有 tools 目录中的例程）。

对于浮点版本，不进行缩放（为了速度）。
对于定点版本，两种方式都进行缩放（为了防止溢出）。

实数（即非复数）优化代码仅适用于偶数长度的 fft。它并行执行两个半长 FFT（打包到 real&imag 中），然后通过旋转因子将它们组合起来。结果是从 DC 到奈奎斯特的 nfft/2+1 个复频段。如果您不知道这意味着什么，请在网上搜索。

快速卷积滤波使用重叠丢弃方法，略作修改以将丢弃部分放在尾部。

修订后的 BSD 许可证，请参阅 COPYING 以了解措辞。基本上，“可以免费使用和更改，在适当的地方注明出处，不提供保证”。请注意，此许可证在一端与 GPL 兼容，另一端与封闭的商业软件兼容。请参阅http://www.fsf.org/licensing/licenses

商业许可证可用，它消除了署名的要求。请联系我了解详情。

* Add real optimization for odd length FFTs 
* Document/revisit the input/output fft scaling
* Make doc describing the overlap (tail) scrap fast convolution filtering in kiss_fastfir.c
* Test all the ./tools/ code with fixed point (kiss_fastfir.c doesn't work, maybe others)

Mark Borgerding
Mark@Borgerding.net

Kiss FFT

一种基于“保持简单，傻瓜化”原则的混合基快速傅里叶变换。

用法

背景

常见问题

性能：（在 Athlon XP 2100+ 上，使用 gcc 2.96，float 数据类型）

底层原理

许可证

未来

作者