福
福

雨辰枫司的小栈

离散傅里叶级数

  • 950 字
  • 条评论
  1. 1. 离散傅里叶级数
  2. 2. python代码
  3. 3. 非2的幂的情况

离散傅里叶级数

当 时， ，记为 。

当 时， ，记作 。（这里在 时， ，相当与乘了，后续不在说明）

当 时， ，记作 。

化为 。

可以看出 。

当 时

记作 。

化为

可以看出

以此类推…

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
import math

def FFT(P):
    n = len(P)
    if n == 1: return P
    even = FFT(P[0::2])
    odd = FFT(P[1::2])
    w = math.e ** (-2j * math.pi / n)
    y = [0] * n
    for i in range(n//2):
        y[i] = even[i] + w ** i * odd[i]
        y[i + n//2] = even[i] - w ** i * odd[i]
    return y

非2的幂的情况

这里采用补0的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import math

def FFT(P):
    n = len(P)
    old_n = n
    if n == 1: return P
    if n & (n - 1) != 0:
        new_n = 1 << n.bit_length()
        P = P + [0] * (new_n - n)
        n = new_n
    even = FFT(P[0::2])
    odd = FFT(P[1::2])
    w = math.e ** (-2j * math.pi / n)
    y = [0] * n
    for i in range(n//2):
        y[i] = even[i] + w ** i * odd[i]
        y[i + n//2] = even[i] - w ** i * odd[i]
    return y[:old_n]