我的任务是使用cooley-tukey算法在某些信号数据上实现傅立叶变换。我不允许使用Numpy模块,因此我必须自己实现算法。但是,通过遵循我给出的伪代码,当我尝试运行它时,我会收到" indexError:list index out范围"错误。该信号是512个元素的列表。以下是我的代码。错误发生在" t = sig [k m] -sig [k m r]
def fft(sig,d):
N=len(sig)
theta = (-2*math.pi*d)/N
r=N//2
for i in range(1,N):
omega=math.cos(i*theta)+j*math.sin(i*theta)
for k in range(0,N):
u = 1
for m in range(0,r):
t=sig[k+m]-sig[k+m+r]
sig[k+m] = sig[k+m] + sig[k+m+r]
sig[k+m+r]=t*u
u=omega*u
k=k+2*r
i=2*i
r=r/2
for i in range(0,N):
r=i
k=0
for m in range(1,N):
k=2*k+(r%2)
r=r/2
m=2*m
if k>i:
t=sig[i]
sig[i]=sig[k]
sig[k]=t
if d<0:
for i in range(0,N):
sig[i]=sig[i]/N
我知道K M最终会大于512(信号的大小(,这就是错误,但是老实说,我只是遵循伪代码。我知道我在某个地方犯了某种愚蠢的错误。感谢您的任何帮助!哦,伪代码(直到发生错误发生的位置(,直接从我的来源
1. set theta = -2pi*d/N and r = N/2
2.For i=1 to N-1 do
{
(a) set omega = cos(i*theta)+jsin(i*theta)
(b) For k=0 to N-1 do
{
(1) Set u=1
(2) For m=0 to r-1 do
{
t = z(k+m) - z(k+m+r)
z(k+m) = z(k+m) + z(k+m+r)
z(k+m+r) = tu
u=omega*u
}
(3) Set k=k+2r
}
(c) Set i = 2i and k=0
}
3. For i=0 to N-1 do
{
(a) Set r = i and k = 0
(b) For m=1 to N-1 do
{
k=2k+(r%2)
r=r/2
m=2m
}
(c) if k > i do
{
t=z(i)
z(i)=z(k)
z(k) = t
}
}
4. If d < 0 then for i=0 to N-1 do
{
z(i)=z(i)/n
}
我想我应该添加z(pseudocode(,我的信号是值的nx1向量,n = 512
索引错误的原因是您使用k,而我在for loops中,但是算法也在用语句修改这些变量。
。k=k+2*r i=2*i
请注意,范围语句的python在这里不像传统的C样式那样工作,无论您如何在循环中操纵迭代器,都只会继续以一步的步幅迭代范围。/p>
编辑,这是一个至少可以完成的版本。但是注意:我不相信它会产生正确的结果。您可以将其用作起点,然后将其与Numpy,Octave或您喜欢的数学套件的结果进行比较。
import math
import cmath
d=1
z=[1,2,1,0,-1,-2,-1,0]
N=len(z)
theta = -2*math.pi*d/N
r = math.floor(N/2)
i=1
while i < N-1: #2.For i=1 to N-1 do
omega = math.cos(i*theta)+ cmath.sin(i*theta)
k=0
while k < N-1: #For k=0 to N-1 do
u=1
m=0
while m < r-1 :#For m=0 to r-1 do
t = z[k+m] - z[k+m+r]
z[k+m] = z[k+m] + z[k+m+r]
z[k+m+r] = t*u
u=omega*u
m=m+1
k=k+2*r
i = 2*i
i=0
while i < N-1:#For i=0 to N-1 do
r = i
k = 0
m=1
while m < N-1: # For m=1 to N-1 do
k=math.floor(2*k+(r%2))
r=r/2
m=2*m
if k > i:
t=z[i]
z[i]=z[k]
z[k] = t
i=i+1
if d < 0:
i=0
while i < N-1: # for i=0 to N-1:
z[i]=z[i]/N
i=i+1
i=0
while i < N-1:
print("z[i]",z[i].real, z[i].imag);
i=i+1;