我试图在Python中实现以下FFT算法，但输出几乎总是错误的。我不理解我的错误。有人能澄清我的错误吗？那太好了！
编辑：
- cpo2(x，y(返回最接近的max(x，y(的2次方
- fill(A，n(填充列表A(列表末尾为零(，直到A达到长度n
- 我的函数工作的一个例子(根据numpy.fft.fft(：
输入[1，2]->输出[3，-1]
- 以下是我的函数不起作用的一些示例：
- 输入：->输出(错误(//输出(基于np.fft.fft为真(
- [1,2,3,4]->[(10+0j(，(-2-2j(，"-2+0j"，"-2+2j"]//[10.+0.j-2.+2.j-2.+0.j-2.-2.j]
- [1，2，3]->[6，2]//[6+0.j-1.5+0.8660254j-1.5-0.8660254j]
- [1,4,4,0]->[(9+0j(，(-3+4j(
def FFT(A):
n = int(len(A))
if n == 1:
return A
w_n = np.exp(complex(0,2*np.pi/n))
w = 1
(A0,A1) = decomp(A)
A0_star = FFT(A0)
A1_star = FFT(A1)
A_star0 = list()
A_star1 = list()
for k in range(int(n/2)):
A_star0.append(A0_star[k] + w*A1_star[k])
A_star1.append(A0_star[k] - w*A1_star[k])
w = w*w_n
A_star = A_star0 + A_star1
return list(np.around(A_star))
def decomp(A):
l = len(A)
n = cpo2(l,l)
A = fill(A,n)
A0 = A[0::2]
A1 = A[1::2]
return(A0,A1)
有两件事让我眼前一亮：
- 您的
for k in range(int(n/2)):意味着这只适用于n的偶数值。由于您递归调用FFT，这可能意味着只有当n是2的幂时，这才有效。也许这没关系，通常你所关心的只是2的幂的输入长度。但你的一个失败例子是n=3，这不是二的幂 - 当n=4时，所有的失败案例都只是失败，其中结果的想象部分是你预期的负面。FFT有不同的定义，其不同之处在于复指数中的指数符号(代码中的
w_n(。看来您已经实现了一个与np.fft.fft实现的定义相反的定义。np.fft.fft的实现可能遵循电气工程中使用的惯例，其中指数中有减号。您的实现似乎遵循了物理学中使用的惯例，其中指数中有一个加号。因此，请尝试使用w_n = np.exp(complex(0,-2*np.pi/n))
可能还有更多问题，但从这些问题开始。。。