递归反快速傅里叶变换

Question

我已经以递归模式实现了两个函数FFT和InverseFFT。

这些是函数：

def rfft(a):
    n = a.size
    if n == 1:
        return a
    i = 1j
    w_n = e ** (-2 * i * pi / float(n))
    w = 1
    a_0 = np.zeros(int(math.ceil(n / 2.0)), dtype=np.complex_)
    a_1 = np.zeros(n / 2, dtype=np.complex_)
    for index in range(0, n):
        if index % 2 == 0:
            a_0[index / 2] = a[index]
        else:
            a_1[index / 2] = a[index]
    y_0 = rfft(a_0)
    y_1 = rfft(a_1)
    y = np.zeros(n, dtype=np.complex_)
    for k in range(0, n / 2):
        y[k] = y_0[k] + w * y_1[k]
        y[k + n / 2] = y_0[k] - w * y_1[k]
        w = w * w_n
    return y

def rifft(y):
    n = y.size
    if n == 1:
        return y
    i = 1j
    w_n = e ** (2 * i * pi / float(n))
    w = 1
    y_0 = np.zeros(int(math.ceil(n / 2.0)), dtype=np.complex_)
    y_1 = np.zeros(n / 2, dtype=np.complex_)
    for index in range(0, n):
        if index % 2 == 0:
            y_0[index / 2] = y[index]
        else:
            y_1[index / 2] = y[index]
    a_0 = rifft(y_0)
    a_1 = rifft(y_1)
    a = np.zeros(n, dtype=np.complex_)
    for k in range(0, n / 2):
        a[k] = (a_0[k] + w * a_1[k]) / n
        a[k + n / 2] = (a_0[k] - w * a_1[k]) / n
        w = w * w_n
    return a

根据IFFT的定义，将FFT函数转换为IFFT函数可以通过将2*i*pi更改为-2*i*pi并将结果除以N来完成。 rfft()函数工作正常，但是经过这些修改的rifft()函数不起作用。

我将我的函数的输出与scipy.fftpack.fft和scipy.fftpack.ifft函数进行比较。

我输入了以下NumPy数组：

a = np.array([1, 0, -1, 3, 0, 0, 0, 0])

下面的框显示了rfft()函数和scipy.fftpack.fft函数的结果。

//rfft(a)
[ 3.00000000+0.j -1.12132034-1.12132034j 2.00000000+3.j 3.12132034-3.12132034j -3.00000000+0.j 3.12132034+3.12132034j 2.00000000-3.j -1.12132034+1.12132034j]
//scipy.fftpack.fft(a)
[ 3.00000000+0.j -1.12132034-1.12132034j 2.00000000+3.j 3.12132034-3.12132034j -3.00000000+0.j 3.12132034+3.12132034j 2.00000000-3.j -1.12132034+1.12132034j]

这个框展示的是 rifft() 函数和 scipy.fftpack.ifft 函数的结果。

//rifft(a)
[ 0.04687500+0.j -0.01752063+0.01752063j 0.03125000-0.046875j 0.04877063+0.04877063j -0.04687500+0.j 0.04877063-0.04877063j 0.03125000+0.046875j -0.01752063-0.01752063j]
//scipy.fftpack.ifft(a)
[ 0.37500000+0.j -0.14016504+0.14016504j 0.25000000-0.375j 0.39016504+0.39016504j -0.37500000+0.j 0.39016504-0.39016504j  0.25000000+0.375j -0.14016504-0.14016504j]

- mpourreza

Answer 1

除以大小为N的值是一个全局缩放因子，应该在递归的结果上执行，而不是在每个递归阶段都进行除法（随着递归的深入，按递减因子进行除法；总体上将结果缩小太多）。您可以通过在原始实现的最终循环中删除/ n因子来解决此问题，该循环由执行缩放的另一个函数调用：

def unscaledrifft(y):
  ...
  for k in range(0, n / 2):
    a[k] = (a_0[k] + w * a_1[k])
    a[k + n / 2] = (a_0[k] - w * a_1[k])
    w = w * w_n
  return a

def rifft(y):
  return unscaledrifft(y)/y.size

或者，由于您正在执行基数为2的FFT，全局因子N应该是2的幂，使得N=2**n，其中n是递归中步骤的数量。因此，您可以在递归的每个阶段除以2，以达到相同的结果：

def rifft(y):
  ...
  for k in range(0, n / 2):
    a[k] = (a_0[k] + w * a_1[k]) / 2
    a[k + n / 2] = (a_0[k] - w * a_1[k]) / 2
    w = w * w_n
  return a

- SleuthEye