信息处理 - 我可以对更大的输入样本进行分段 FFT 吗？ - 吾爱随笔录

我可以对更大的输入样本进行分段 FFT 吗？

信息处理 fft

2022-01-31 21:20:01

我有一个 N 点序列 x。令 X 为 fft(x)。（假设 x 是任意的）

在哪里，

x=[x1 x2 x3 x4 x5 x6 x7 x8] 

fft(x)=[X1 X2 X3 X4 X5 X6 X7 X8]

如何通过级联 4 点 DFT 和 2 点 DFT 得到 8 点 DFT 的结果？

假设我将信号“x”（尺寸为“1 x 8”）重塑为“x1”（尺寸为“2 x 4”）

x1=[x1 x2 x3 x4;
   x5 x6 x7 x8]

fft(x1 (first row)) i.e. fft(x1 x2 x3 x4) say =  [Y1 Y2 Y3 Y4]
fft(x1 (second row)) i.e. fft(x4 x5 x6 x7)  say = [Y5 Y6 Y7 Y8]

然后再次明智地采取 fft 列

fft(Y1 Y5)  say = [Z1 Z2]
fft(Y2 Y6)  say = [Z3 Z4]
fft(Y3 Y7)  say = [Z5 Z6]
fft(Y4 Y8)  say = [Z7 Z8]

但是，这个 Z 不等于 X。我如何通过这些较小的点 FFT 继续获得 X？

任何帮助都会很棒！谢谢

1个回答

你需要Cooley-Tukey 算法，它可以用来表示大小的 DFT $N=N_1N_2$ 按大小的 DFT $N_1$ 和 $N_2$ . 它有点像您在问题中勾勒的内容，但是您忘记了旋转因素。这个答案解释了算法的细节，它还包括一个简单的 Matlab 实现。

编辑（见评论）：如果你真的想计算连续数据块的 FFT，你需要拆分偶数和奇数频率索引的计算（假设 DFT 长度 $N$ 甚至）：

\begin{matrix} (1) & X [2 k] = \sum_{n = 0}^{N / 2 - 1} (x [n] + x [n + N / 2]) W_{N / 2}^{n k} X [2 k + 1] = \sum_{n = 0}^{N / 2 - 1} (x [n] - x [n + N / 2]) W_{N}^{n} W_{N / 2}^{n k} \end{matrix}

$X[2k]=\sum_{n=0}^{N/2-1}\left(x[n]+x[n+N/2]\right)W_{N/2}^{nk}\\ X[2k+1]=\sum_{n=0}^{N/2-1}\left(x[n]-x[n+N/2]\right)W_N^nW_{N/2}^{nk}\tag{1}$

在哪里 $W_N=e^{-j2\pi/N}$ . 请注意，您当然可以计算长度的 DFT $N/2$ 子块分开而不是在 DFT 之前添加（或减去）块（如（1）中），但这在计算上效率较低。

其它你可能感兴趣的问题

上一篇系统响应：时间与频率。为什么我得到不同的量级？下一篇的含义X( - j ω ) =X*( j ω )X(−jω)=X∗(jω)