对于受约束的输入，DFT 的计算次数有很多可能的减少。仔细研究著名的 DFT 库（例如 FFTW）应该是如何利用这些约束的一个很好的资源。对于你的情况，我会看看离散余弦变换（DCT）。离散余弦变换强制均匀对称。“快速”DCT 算法采用针对这些输入约束进行优化的 FFT 结构。DCT 执行的隐式偶对称镜像类型是各种 DCT 类型（I 型、II 型……）的区别所在。如果您的序列确实是偶数对称的，那么您可以使用快速 DCT 算法（基于 FFT 结构的算法），其中一半的数据知道该算法假设另一半是等效的（尽管是时间反转的）。

您还可以将长度为 N 的序列打包成 N/2 个复杂样本，并且不会增加太多复杂性，您可以恢复长度为 N FFT。因此，您可以从另一个角度进行半长复数 FFT 攻击。虽然这看起来效率较低，但对于典型的 FFT 结构，无论如何在第一阶段之后您都会很复杂，因此对于较大的 DFT 尺寸，这变得非常有效。

我不确定将处理时间分成四等份，但这是我现在能想到的。x 的 N 点 DFT。

$X_k = \sum_{n=0}^{N-1}x_nW_N^{kn}$

由偶对称假设

$X_k = \sum_{n=0}^{N/2-1}x_n(W_N^{kn}+W_N^{k(N-1-n)})$

然后我们简化

$X_k = W_N^{k(N-1)/2}\sum_{n=0}^{N/2-1}x_n(W_N^{kn}W_N^{-k(N-1)/2}+W_N^{-kn}W_N^{k(N-1)/2})$

$X_k = 2W_N^{k(N-1)/2}\sum_{n=0}^{N/2-1}x_n\cos(2\pi k\frac{n-(N-1)/2}{N})$

可能存在一些错误，但如果简化有效，则“FFT”大小会减少 2 倍，并且旋转因子是真实的（这可能对应于您的四分法）。与普通 FFT 一样，可以利用对称性和周期性将“对称 FFT”分解为实例的 radix-2 步骤。