이산 퓨리에 변환이 작동하지 않습니다/매우 비효율적 인 파이썬에서

Question

파이썬에서 신호의 에너지 스펙트럼 밀도를 배열로 그리는 이산 푸리에 변환 함수를 쓰려고합니다 (그래픽으로 출력합니다). 내가 행렬 곱셈을 사용하여 이것을하고있다. 내 코드는 작은 데이터 세트에서 작동하는 것처럼 보이지만 처리하는 데 오랜 시간이 걸립니다. 예를 들어. 작업을 완료하지 못하는 wav 파일 함수는 현재 :

from scipy.io import wavfile 
import numpy as np 
import matplotlib.pyplot as plt 

데프 ESD (데이터 FS)

데이터가 설정 데이터가 fs

a=[] 


for i in range(int(np.size(data)/100)): 

    dt = 1/(fs) 

    fvec = np.arange(100*i , 100+(100*i) , 1) 
    nvec = np.arange(0 , np.size(data) , 1) 

    Wconst = np.exp(-1j*2*np.pi/np.size(data)) 

    ematrix = Wconst**(np.outer(fvec,nvec)) 

    b = (dt**2)*(abs(np.inner(ematrix , data))**2) 

    a = np.concatenate((a,b)) 




return a 

샘플링 주파수이다. 이 기능이 너무 느리거나 비효율적 인 이유가 있습니까? 그렇지 않으면 매트릭스가 매우 커질 수 있으므로 100 블럭의 주파수로 신호를 처리하도록 설계되었습니다.

Answer 1

이 알고리즘은 "순"이산 푸리에 변환 (DFT)의 주파수의 Vandermonde 행렬을 계산하여 변환을 구현한다.

b = (dt ** 2) * abs(np.inner(ematrix, data)) ** 2 

이 원래 구현은 직접 매트릭스 - 벡터 곱셈을 사용하고 O(N**2), N == data.size의 주행 시간을 가지고 문제가 여기된다. 따라서 더 큰 데이터를 얻으면 WAV 파일에 대해 합리적인 시간 내에 완료하지 못할 수도 있습니다.

이 문제의 많은 구조를 활용하는 Fast Fourier Transform 알고리즘을 사용할 때의 요점입니다. 특히, FFT는 문제를 반복적으로 크기가 작은 N/2의 문제로 나눕니다. 재귀 구조는 FFT에 실행 시간이 O(N log N) 인 것입니다.