小白弱弱的问一句补零和2的整数幂是啥意思
失心控 发表于 2016-7-12 16:15
小白弱弱的问一句补零和2的整数幂是啥意思
FFT是离散傅里叶变换的快速算法，速度提升非常大，但是FFT要求做变换的原始信号长度必须是2的整数幂才行，因此对于长度随机的信号，需要补零到2的整数幂才能应用FFT
多谢各位回复，目前的解决方法是：对原始信号末尾补零到2的整数幂，在进行FFT。
时域补零，相当于频域插值，不会改变频谱的包络。
lebronze 发表于 2016-7-13 10:21
多谢各位回复，目前的解决方法是：对原始信号末尾补零到2的整数幂，在进行FFT。
时域补零，相当于频域插值 ...
你的程序只能做2的整数幂的FFT，加零的工作应由调用者去做，不能由程序本身去做，加零以后的结果肯定与不加零有区别的，从算法来看就不合适，而且也有具体问题，比如你并不能确定原来的数组空间够不够加零？
lebronze 发表于 2016-7-13 10:19
FFT是离散傅里叶变换的快速算法，速度提升非常大，但是FFT要求做变换的原始信号长度必须是2的整数幂才行 ...
就是补一些0进去是数据长度为2的整数次幂对吗？
hcharlie 发表于 2016-7-13 13:01
你的程序只能做2的整数幂的FFT，加零的工作应由调用者去做，不能由程序本身去做，加零以后的结果肯定与不 ...
恩，我就是这么做的。在调用fft前先判断是不是2的整数幂，如果是：直接做fft； 如果不是：补零再做fft。
lebronze 发表于 2016-7-13 14:23
恩，我就是这么做的。在调用fft前先判断是不是2的整数幂，如果是：直接做fft； 如果不是：补零再做fft ...
搜噶 明白了 谢谢你！！
本帖最后由 hcharlie 于 2016-7-14 07:29 编辑
lebronze 发表于 2016-7-13 14:23
恩，我就是这么做的。在调用fft前先判断是不是2的整数幂，如果是：直接做fft； 如果不是：补零再做fft ...
我们也可以换个思路来考虑你的问题，也就是根据你们的用处，你们对FFT速度的要求是多少？
30几年前，我们花了很大力气，在IBM-PC机上调试FFT程序，1024点FFT速度达到700ms，完成了我们的任务，而用DFT需要几十秒，是根本不行的。
现在不一样了，我们测试了我们同一个程序，在现在的普通微机上1024点FFT只需要0.1ms，以此速度计算，做DFT也只需要10ms以下了!
所以你们认真考虑一下你们对速度的具体要求是什么，如果合适是不是可以全部用DFT来完成你们的工作，放弃FFT，而满足所有任务精度的要求！DFT公式极其简单，自己编程也不难。
就是计算速度上有差异呗
lebronze 发表于 2016-7-12 14:56
多谢
我也尝试过将任意点数信号补零或者截断到2的整数幂，结果做FFT后发现相位会有变化。如下图：原始信号 ...
经过FFT之后所有的相位都会有变化，只不过一般我们用不到而已，如果你想得到准确的相位值，那么最好再做一下矫正！！！
希望对你能有帮助，里边有DFT，FFT C程序
本帖最后由 hcharlie 于 2016-7-19 11:08 编辑
chybeyond 提供了DFT代码，它在DFT正变换时不除Ｎ，在逆变换时除Ｎ。
这个代码不复杂，我试了一下速度，做1024点DFT需时100ms，看看能不能满足LZ的需要了。
研究一下上述代码，写得挺简单，但显然没有经过优化，本人初步速度优化以后，速度能提高5倍，到20ms左右，应该不错了。
下面是本人经过速度优化后的DFT代码，经过算例考核过。
x[ ],y[ ]为变换前的实部虚部，a[ ],b[ ]为变换后的实部虚部，n为数据长度，sign=1为正变换，=-1为逆变换。
空口无凭赶紧上算例看看否则犟也是白犟