在测试输入中，我在Usenet的旧帖子中找到了一些指导，我将其作为答案，但这只是一个人的建议而没有很多建议。理由-我还没有找到看起来像是一个可靠答案的东西。
关于准确性，维基百科说错误应该是O（e log N），但是从绝对意义上讲是合理的期望吗？
编辑添加：实际测试采用以下形式：我存储了输入数据数组和预先计算的“参考”输出数据以进行比较，因此我不一定需要带有封闭形式的解决方案。
#1 楼
如果要验证FFT算法的正确性，就某种意义而言，它要执行的功能具有离散傅里叶变换的已知属性，那么可以使用以下方法中提出的方法：埃尔金，丰达。 （1995年6月）。测试多元线性函数：克服生成器瓶颈。在过程中。第二十七届安。 ACM症状。计算理论。 （第407–416页）。FFTW的制造商将上述论文作为他们选择的方法，以验证特定的FFT实现是否应执行其应做的工作。提出的技术将功能分为三个主要部分，并通过单独的测试进行了验证：线性：DFT（以及傅里叶家族中的其他表亲转换）是线性运算符，因此对于$ a_1，a_2，x_1 [n]，x_2 [n] $的所有值，必须满足以下方程式：
$$
\ mathrm {FFT}（a_1 x_1 [n] + a_2 x_2 [n]）= a_1 \ mathrm {FFT}（x_1 [n]）+ a_2 \ mathrm {FFT}（x_2 [n]）
$$
单位脉冲的DFT：将等于Kronecker增量函数的时域信号应用于FFT算法的输入，并根据输出检查输出。单位脉冲函数的已知DFT（在所有输出仓中转换为恒定值）。如果FFT算法提供了IFFT，则可以对其进行反向测试，以证明它再次产生了单位脉冲函数。
时移：将两组数据应用于FFT算法的输入；两者在时域上的唯一区别是恒定的时移。基于DFT的已知属性，这将影响两个信号的频域表示之间的已知线性相移，其中相移的斜率与时间偏移成比例。
该论文的作者断言，这些测试足以验证FFT实现的正确性。我过去从未使用过这种技术，但似乎确实有道理，我相信FFTW的作者（他们生产了很多免费软件）是可靠的权威，提供了验证问题的好方法。 >
#2 楼
正如问题中提到的，我确实在归档的comp.dsp Usenet帖子中找到了一组建议（http://www.dsprelated.com/showmessage/71595/1.php，由“ tdillon”发布）：A.Single FFT tests - N inputs and N outputs
1.Input random data
2.Inputs are all zeros
3.Inputs are all ones (or some other nonzero value)
4.Inputs alternate between +1 and -1.
5.Input is e^(8*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
6.Input is cos(8*2*pi*i/N) for i = 0,1,2, ...,N-1.
7.Input is e^((43/7)*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
8.Input is cos((43/7)*2*pi*i/N) for i = 0,1,2, ...,N-1.
B.Multi FFT tests - run continuous sets of random data
1.Data sets start at times 0, N, 2N, 3N, 4N, ....
2.Data sets start at times 0, N+1, 2N+2, 3N+3, 4N+4, ....
该线程还建议执行两个正弦，一个正弦幅度较大，另一个正弦幅度较小。
我在主要问题中说，我'不确定这是否是一组特别好的答案，或者它是否很完整，但是我要放在这里以便人们对其进行投票和评论。
评论
$ \ begingroup $
“ 1.输入随机数据”将显示什么？
$ \ endgroup $
– Dilip Sarwate
2011年11月12日在1:46
$ \ begingroup $
@DilipSarwate：模糊测试对于揭示崩溃很有用。并且，根据噪声输入的类型（例如粉红噪声或白噪声），在检查总体能量分布是否符合预期时可能很有用。
$ \ endgroup $
– smokris
2011年11月12日在2:46
$ \ begingroup $
@Dilip-我的fft“烟雾测试”是ifft（fft（random_stuff））〜= random_stuff。
$ \ endgroup $
– hotpaw2
2011年11月12日在8:01
$ \ begingroup $
@ hotpaw2因此，“随机的东西”意味着您仅看到一堆似乎不适合正弦曲线等数字的数字？或者您是否测试输出以查看$ N $数字是否可以被认为是“随机的”，例如将输入设为复杂的高斯$ \ mathcal {CN}（0,1）$，然后进行假设检验，以查看FFT输出的散点图是否看起来像散点图（例如$ 99 \％$置信度）将从$ N $ $ \ mathcal {CN}（0,1）$随机样本中获得的图？
$ \ endgroup $
– Dilip Sarwate
2011年11月12日12:59
$ \ begingroup $
@Dilip：我是硬件专家。我想要的东西可能会在所有乘法器和CSA中的所有位中占很大比例。
$ \ endgroup $
– hotpaw2
2011年11月12日在16:47
评论
$ \ begingroup $
谢谢！作者是否建议将a1，a2，x1 [n]和x2 [n]的值用于线性测试（或者他们断言这在很大程度上无关紧要）？而且，就此而言，用于时移测试的数据集是什么？
$ \ endgroup $
–布鲁克斯·摩西
2011年11月12日5:17
$ \ begingroup $
实际阅读本文后，我可以回答我自己的问题：作者没有描述一个人如何执行线性测试，而是假设一个人所做的足以证明“大多数输入”是正确的。同样，本文在假设精确算术的情况下描述了正确正确性的证明。它没有描述用于表征近似程序中数值误差的手段（这必然是使用有限精度算术得出的结果）。
$ \ endgroup $
–布鲁克斯·摩西
2011年11月12日在7:24
$ \ begingroup $
我将继续并将其标记为已接受，因为它肯定是迄今为止最好的答案-但是我仍然对其他答案感兴趣，这些答案涵盖了要使用的测试输入数据集（以及原因），或者预期精度的详细信息。谢谢！
$ \ endgroup $
–布鲁克斯·摩西
2011年11月15日，0：22
$ \ begingroup $
关于验证FFT算法，您的问题确实包含两个部分：验证其正确性和测量其数值精度。我的回答只针对第一个。很难就期望的数值精度做出任何陈述，因为它本质上取决于实现。算术类型（例如固定点与浮点），用于实现算法的结构，FFT长度（即用于分解问题的阶段数），为提高执行速度而采取的任何捷径等都将发挥作用。因素，很难一概而论。
$ \ endgroup $
–Jason R
2011年11月15日在2:45
$ \ begingroup $
好点；我可能应该将这些作为单独的问题提出来。
$ \ endgroup $
–布鲁克斯·摩西
2011年11月18日在6:29