Python（无 Numpy）索引错误中的 Cooley-Tukey FFT 算法

Question

我的任务是使用 Cooley-Tukey 算法对一些信号数据进行傅里叶变换。我不允许使用 Numpy 模块，所以我必须自己实现算法。但是，按照给出的伪代码，当我尝试运行时出现 "IndexError: list index out of range" 错误。该信号是 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（伪代码）并且我的信号是 Nx1 个值向量，其中 N = 512

Answer 1

索引错误的原因是您在 for 循环中使用了 k 和 i，但随后算法也在使用语句修改这些变量。

   k=k+2*r
 i=2*i

请注意，python for range 语句在这里不像传统的 C 风格 for 循环那样工作，无论您如何操作循环内的迭代器。

编辑，这里是至少运行完成的版本。但是 注意： 我不相信它会产生正确的结果。您可以将其用作起点，然后与 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;

Python（无 Numpy）索引错误中的 Cooley-Tukey FFT 算法

Cooley-Tukey FFT Algorithm in Python (no Numpy) Index Error

python

algorithm

fft