microfft

microfft 是一个针对嵌入式系统计算快速傅里叶变换的库。它提供了 Radix-2 FFT 算法的就地实现。所有计算都在输入缓冲区上直接执行，无需额外的分配。这使得 microfft 适用于如微控制器之类的 无 std 环境。

速度主要是通过维护一个预计算的正弦表来实现的，该表用于查找所需的倍频因子。通过用简单的内存查找替换算术运算，我们减少了 CPU 循环次数。不幸的是，预计算的表也占用相当大的内存，这可能会成为某些嵌入式项目的杀手锏（见 内存使用）。

microfft 还实现了一个针对实值（而不是复值）FFT的专业算法。直观地说，人们会通过将输入转换为复值（虚部为空）并运行 CFFT 来计算实值 FFT。microfft 的 RFFT 算法相反，将成对的实值打包成一个单独的复数，然后计算原始输入大小一半的 CFFT，之后进行一些重组魔法。这大约可以将 CPU 循环次数减半，这在 基准测试结果 中可以看到。

示例

以下示例演示了在从正弦信号生成的样本集上计算16点 RFFT

use std::convert::TryInto;
use std::f32::consts::PI;

// generate 16 samples of a sine wave at frequency 3
let sample_count = 16;
let signal_freq = 3.;
let sample_interval = 1. / sample_count as f32;
let mut samples: Vec<_> = (0..sample_count)
    .map(|i| (2. * PI * signal_freq * sample_interval * i as f32).sin())
    .collect();

// compute the RFFT of the samples
let mut samples: [_; 16] = samples.try_into().unwrap();
let spectrum = microfft::real::rfft_16(&mut samples);
// since the real-valued coefficient at the Nyquist frequency is packed into the
// imaginary part of the DC bin, it must be cleared before computing the amplitudes
spectrum[0].im = 0.0;

// the spectrum has a spike at index `signal_freq`
let amplitudes: Vec<_> = spectrum.iter().map(|c| c.norm() as u32).collect();
assert_eq!(&amplitudes, &[0, 0, 0, 8, 0, 0, 0, 0]);

要求

需要 Rust 版本 1.61.0 或更高。

正弦表

microfft 只保留一个正弦表来计算所有 FFT 大小的倍频因子。与为每个 FFT 大小保留单独的表相比，这减少了内存开销，因为那些表之间会有重复。

默认的正弦表支持大小为4096的FFT。如果您只想计算较小大小的FFT，建议选择适当的size-*功能，以节省内存。例如，如果您的最大FFT大小是1024，请将以下内容添加到您的Cargo.toml

[dependencies.microfft]
default-features = false
features = ["size-1024"]

这告诉microfft不提供计算大于1024大小的FFT的功能，并只保留1024点正弦表。

如果您想计算超过4096点的FFT，您还需要启用相应的功能。在这种情况下，禁用默认功能不是必需的，因为microfft始终根据请求的最大大小确定正弦表的大小。因此，它按预期工作

[dependencies.microfft]
features = ["size-8192"]

位反转表

可选功能bitrev-tables启用了对每个FFT开始时执行输入值重新排序所需的预计算位反转索引表的使用。如果禁用此功能（默认情况），则位反转将在运行时计算。

请注意，启用位反转表会显著增加microfft的内存使用量。虽然它可以在某些系统上加快FFT计算速度，但也有提供专用位反转指令（如ARMv7上的RBIT）的架构。在这样的架构上，打开位反转表通常对性能有害。

std使用

microfft提供了一个std功能，旨在使库对可以利用Rust标准库的应用程序更有用。目前它所做的只是传递性地启用num-complex存储库的std功能，从而在FFT函数返回的Complex32值上提供更多方法。

由于嵌入式应用程序通常在没有Rust标准库的目标上运行，因此默认禁用了std功能。您可以在Cargo.toml中启用它

[dependencies.microfft]
features = ["std"]

限制

microfft有一些限制，主要是由于其关注速度，这可能会使它不适合某些嵌入式项目。如果您考虑使用此库，您应该了解这些限制

内存使用

使用预计算的正弦和位反转表意味着microfft对只读内存有相当大的需求。如果您的芯片本身就很少闪存，这可能是一个问题。

表所需的内存量取决于size-*和bitrev-tables功能的配置

此外，代码大小也随着FFT大小而增加。

支持的FFT大小

microfft仅支持基数-2算法的限制下的2的幂次FFT点大小。此外，目前支持的最大大小为32768，但根据需要，此限制可以在未来增加。

f64支持

此库目前仅支持单精度浮点输入。类似于FFT大小限制，这是一个可能在需要时取消的限制。

许可证

本项目采用MIT许可协议（许可证 或 http://opensource.org/licenses/MIT）。

除非您明确声明，否则您有意提交给microfft的任何贡献都将按照上述许可协议进行，不附加任何额外条款或条件。