关于快速傅里叶变换蝶形图的问题

Question

如下图，请问这个旋转因子Wnk为什么这样标，有什么规律吗，怎么标谢谢

Answer 1

引自免费微信小程序：皆我百晓生

在快速傅里叶变换（Fast Fourier Transform, FFT）中，特别是按照时间抽取法（Time-Shifting FFT）构建的信号流图中，旋转因子 ( W_N^k ) 用于在复数域中对输入序列进行相位旋转。这里 ( N ) 是信号的长度，而 ( k ) 表示旋转次数。( W_N ) 是一个单位根，满足 ( W_N^N = 1 )，通常选择为 ( W_N = e^{-j2\pi/N} )，其中 ( j ) 是虚数单位。

在你提供的信号流图中，可以看到 ( W ), ( WQ ), ( W^2 ) 等表示不同的相位旋转因子。这些旋转因子的规律是根据它们的位置以及在蝶形结构中的层次关系决定的。具体来说，每个 ( W_N^k ) 都是在前一层的两个子序列相乘之后应用的，这里的 ( k ) 值取决于位置。

对于给定的 ( N = 8 ) 的FFT，我们可以将 ( W_N = e^{-j2\pi/8} ) 写成 ( W_N = \cos(-\frac{\pi}{4}) - j\sin(-\frac{\pi}{4}) = \frac{1}{\sqrt{2}} - j\frac{1}{\sqrt{2}} )。然后我们可以通过指数运算得到其他的 ( W_N^k )：

• ( W_N^1 = W_N )
• ( W_N^2 = W_N^2 )
• ( W_N^3 = W_N^3 )
• ( W_N^4 = W_N^4 ) （这实际上是 ( W_N^4 = (W_N)^4 = (\frac{1}{\sqrt{2}} - j\frac{1}{\sqrt{2}})^4 = 1 )，因为 ( W_N^N = 1 )）
• ( W_N^5 = W_N^1 \cdot W_N^4 = W_N )
• ( W_N^6 = W_N^2 \cdot W_N^4 = W_N^2 )
• ( W_N^7 = W_N^3 \cdot W_N^4 = W_N^3 )

因此，在你的信号流图中，( W ) 对应于 ( W_N^1 )，( WQ ) 对应于 ( W_N^2 )，依此类推。由于 ( W_N^4 = 1 )，所以在流图中出现了 ( -1 )，这是因为 ( W_N^4 ) 实际上就是 ( 1 )，但在某些情况下为了区分可能会写作 ( -1 )，尤其是在涉及实数域的FFT实现时。

下面是根据上述规则生成的完整信号流图的描述：

x(0)    X(0)    W_N^0 = 1
x(4)    X(1)    W_N^1
x(2)    X(2)    W_N^0 * W_N^1 = W_N^1
          X(3)    W_N^2
x(1)    X(4)    W_N^1 * W_N^2 = W_N^3
x(6)    X(5)    W_N^0 * W_N^3 = W_N^3
x(3)    X(6)    W_N^1 * W_N^3 = W_N^4 = 1
x(5)    X(7)    W_N^2 * W_N^3 = W_N^5

注意：在实际计算中，我们通常不会写成 ( W_N^0 )、( W_N^1 ) 这样的形式，而是直接使用 ( 1 ) 和 ( W_N ) 来简化表示。在这个例子中，( W_N ) 就可以被看作 ( W )，( W_N^2 ) 可以被看作 ( WQ )。

如果你需要一个具体的Python代码实现，我可以提供一个简单的版本。但需要注意的是，现代编程库（例如numpy或scipy）已经提供了高效的FFT函数，通常不需要手动实现整个过程。下面是一个简单实现的例子：

import numpy as np

def simple_fft(x):
    N = len(x)
    if N == 1:
        return x
    else:
        even = simple_fft(x[::2])
        odd = simple_fft(x[1::2])
        w = np.exp(-2j * np.pi / N)
        half_size = N // 2
        result = np.zeros(N, dtype=np.complex128)
        for i in range(half_size):
            result[i] = even[i] + w**i * odd[i]
            result[i+half_size] = even[i] - w**i * odd[i]
        return result

# 示例
x = np.array([1, 2, 3, 4, 5, 6, 7, 8], dtype=np.float)
X = simple_fft(x)
print(X)

这段代码实现了递归的FFT算法，并计算了一个简单的输入向量。如果你想了解更详细的FFT实现，包括时间抽取法（radix-2），可能需要进一步研究相关资料或者查看专业教程。