- html - 我的下拉菜单的内容关闭得太快
- c# - 使用 Html Agility Pack 从网页中的表中获取值而不使用 "SelectNode'
- html - 内容容器下的 CSS 下拉菜单
- html - 如何停止嵌套列表重叠父列表?
要在频域中插入信号,可以在时域中填充零并执行 FFT。
假设给定向量 X 中的元素数为 N 并且 Y 与 X 相同但在一侧用 N 零填充。然后下面给出相同的结果。
$$\hat{x}(k)=\sum_{n=0}^{2N-1} Y(n)e^{i2\pi k n/2N},\quad k=0,...,2N-1,$$
$$\hat{x}(k)=\sum_{n=0}^{ N-1} X(n)e^{i2\pi k n/2N},\quad k=0,...,2N-1.$$
现在如果我们使用FFTW 包,第一个方程需要2N 内存空间用于输入向量,而第二个只需要N 内存空间(我不知道是否可以在现有的 FFTW 包中完成)!计算复杂度也从2N^2log(2N)降低到2N^2log(N)。每当我们进行 2D FFT 或 3D FFT 时,问题就会变得更糟。是否可以使用 FFTW 包进行第二种方法?不过,这在 MATLAB 中相当容易做到。
最佳答案
如果 x
是一个 2N 信号,在 N 之上用零填充,它的 DFT 写成:
k
是偶数:
因此,偶数频率的系数来自x(n)
的N点离散傅立叶变换。
k
是奇数:
因此,奇数频率的系数来自x(n)exp(i*M_PI*n/N)
的N点离散傅立叶变换。
因此,零填充的 2N 信号的离散傅里叶变换恢复为长度为 N 的信号的两个 DFT,并且可以使用 fftw 来计算它们。
总计算时间为 2*c*N*ln(N)
,其中 c
是常数。它预计比 DFT c*2*N*ln(2*N)
的直接计算更快。请记住 ln(2*N)=ln(2)+ln(N)
:随着 N 变大,与 ln 相比,直接计算的额外工作可以忽略不计(N)
:技巧变得无用, 即使维度大于一。它不影响复杂性。
此外,FFTW 非常高效,如果安装正确,它会使用您 PC 的许多功能,而且在任何情况下都很难做得比这更好,即使使用了所提供的技巧也是如此。 最后,如果输入信号是真实的,你可以使用 fftw_plan fftw_plan_dft_r2c_2d
: 傅立叶空间中只有一半的系数被计算和存储。
关于内存要求,如果实在内存不足,可以使用FFTW_IN_PLACE
标记并使用相同的数组进行输入和输出。然而,它稍微慢一些。
上面介绍的过程可以扩展为计算用 (L-1)N 个零填充的 N 点信号的 LN 信号的 DFT:它恢复到长度为 N 的 L 个 DFT 的计算。
与 FFTW 相比,您是否有任何引用资料显示 MATLAB 如何处理和优化填充信号的 DFT?
编辑:关于 3D 案例的进一步研究:
填充的 3D 信号 x(n,m,p)
的 3D DFT 是:
如果 k_n
、k_m
和 k_p
是偶数:
如果 k_n
和 k_m
是偶数且 k_p
是奇数:
...有8个案例。
因此,将大小为 NxNxN 的 3D x
填充到 2Nx2Nx2N 的 3d dft 的计算恢复到大小为 NxNxN 的 8 个 3d dft 的计算。尺寸a 3d dft是3个1d dft的组合,尺寸N的dft总数为3x8xNxN,而直接计算需要尺寸为2N的3x(2N)*(2N)dft。计算时间是 24cN^3ln(N)
对比 24cN^3ln(2N)
:小的增益是可能的...同样 fftw 很快...
然而,我们不使用黑盒 3d fft,而是通过在每个方向上执行 1d dft,一次计算大小为 N 的 8 个 dft。
NxN
dfts => 2cN^3ln(N)
2NxN
dfts => 4cN^3ln(N)
2Nx2N
dfts => 8cN^3ln(N)
因此,总计算时间预计为 14cN^3ln(N)
而不是 24cN^3ln(2N)
:小增益是可能的...再次fftw 很快...
此外,计算
只需要调用一次 exp
:首先计算 w=exp(I*M_PI/N)
然后更新 wn=wn*w; x(n)=x(n)*wn
或在精度成为问题时使用 pow
。
关于fft - 使用 FFTW 的零填充 FFT,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28961667/
FFT 库(例如 FFTW 或 numpy.fft)通常提供两个函数 fft() 和 ifft()(及其用于实值输入的特殊版本)。这些功能似乎被定义为 ifft(fft(X)) == X 和 fft(
如果我有一个特定大小 M(2 的幂)的 FFT 实现,我如何计算一组大小 P=k*M 的 FFT,其中 k 也是 2 的幂? #define M 256 #define P 1024 comple
下午好! 我正在尝试基于我已有的简单递归 FFT 实现来开发 NTT 算法。 考虑以下代码(coefficients'的长度,让它为m,是2的精确幂): /// /// Calculates the
我正在分析时间序列数据,并希望提取 5 个主要频率分量并将其用作训练机器学习模型的特征。我的数据集是 921 x 10080 。每行是一个时间序列,总共有 921 个。 在探索可能的方法时,我遇到了各
我找不到任何官方文档来证明 scipy.fft 实际上是 numpy.fft.fftpack.fft 的链接。这是显示链接的 iPython session : In [1]: import scip
文档说 np.fft.fft 这样做: Compute the one-dimensional discrete Fourier Transform. 和 np.fft.rfft 这样做: Compu
近一个月来,我一直在与一个非常奇怪的错误作斗争。问你们是我最后的希望。我用 C 编写了一个程序,它集成了 2d Cahn–Hilliard equation在傅里叶(或倒数)空间中使用隐式欧拉 (IE
我一直在制作一个例程,使用 NumPy/Scipy 测量两个光谱之间的相位差。 我已经有了Matlab写的例程,所以我基本上是用NumPy重新实现了函数和相应的单元测试。但是,我发现单元测试失败了,因
我正在研究使用 Renderscript 对大型复杂输入数组执行 FFT。 FFT 是相当标准的,因为它涉及三个循环,但内部循环执行 FFT 中的蝶形运算。因为每个蝴蝶使用数组的不同部分,所以没有明显
我需要通过修改 FFT 结果来均衡音乐样本。 我知道如何获得每个输出虚数的频率,问题是修改这个值以获得“均衡器效果”。 我需要知道如何缩放这个值。 条目大小为 4096 个样本,采样率为 44100
我将在 kiss-fft 之前制定几个计划同时(平行),我可以这样做吗,或者换句话说,kiss-fft 线程安全吗? 谢谢 最佳答案 自述文件: No static data is used. Th
要在频域中插入信号,可以在时域中填充零并执行 FFT。 假设给定向量 X 中的元素数为 N 并且 Y 与 X 相同但在一侧用 N 零填充。然后下面给出相同的结果。 $$\hat{x}(k)=\sum_
我通过相关了解了 DFT 的工作原理,并将其用作理解 FFT 结果的基础。如果我有一个以 44.1kHz 采样的离散信号,那么这意味着如果我要获取 1 秒的数据,我将有 44,100 个样本。为了对其
有人知道 Mayer FFT 的实现吗(我不必花很多时间研究代码)? 我正在尝试执行卷积,ifft 似乎产生了我称之为“镜像”的输出。换句话说,我的内核+信号长度被限制为 N/2 并且占据 n=0..
有人知道 Mayer FFT 的实现吗(我不必花很多时间研究代码)? 我正在尝试执行卷积,ifft 似乎产生了我称之为“镜像”的输出。换句话说,我的内核+信号长度被限制为 N/2 并且占据 n=0..
我有以下代码...请注意#生成正弦曲线下的两行。一个使用比另一个更高的 2pi 精度值,但它们仍然应该给出几乎相同的结果。 import numpy as np import matplotlib.p
我正在努力确保 FFTW 做我认为它应该做的事情,但我遇到了问题。我正在使用 OpenCV 的 cv::Mat。我制作了一个测试程序,给定一个 Mat f,计算 ifft(fft(f)) 并将结果与
我是从事电信项目的计算机程序员。 在我们的项目中,我必须将一系列复数更改为它们的傅立叶变换。因此我需要一个高效的 FFT 代码来满足 C89 标准。 我正在使用以下代码,它运行良好: shor
我目前正在尝试了解 numpy 的 fft 函数。为此,我测试了以下假设: 我有两个函数,f(x) = x^2 和 g(x) = f'(x) = 2*x。根据傅立叶变换定律和 wolfram alph
我一直在使用 FFT,目前正在尝试使用 FFT 从文件中获取声音波形(最终对其进行修改),然后将修改后的波形输出回文件。我得到了声波的 FFT,然后对其使用了反 FFT 函数,但输出文件听起来一点也不
我是一名优秀的程序员,十分优秀!