n 배 FFT 컨볼 루션 및 순환 오버랩

Question

문제 설명

필자는 컨볼 루션을 효율적으로 계산하기 위해 회선 정리를 사용했습니다. 길이가 N 인 두 개의 실제 신호 s1과 s2이 있다고 가정합니다. I는 fft_size가 순환 중복을 피하기 위해

fft_size = int(2 ** np.ceil(np.log2(k * size - 1))) 

를 판독하도록 수정되어야 k singals이 경우 I 그러나

import numpy as np 
import numpy.fft as fft 

size = len(s1) 
fft_size = int(2 ** np.ceil(np.log2(2 * size - 1))) #The size for the FFT algorithm 

S1 = fft.rfft(s1, fft_size) #Take FTs 
S2 = fft.rfft(s2, fft_size) 

convolution = fft.irfft(S1 * S2) #Take IFT 

에서 컨볼 루션을 얻을 수있다.

불행히도, 나는 선험적으로 k을 모른다. 하나의 옵션은 최대 값 k_max을 선택하는 것이지만 절대적으로 필요하지 않으면 많은 양의 메모리를 사용할 필요가 없으며 k 변경이있을 때마다 FT를 다시 평가하지 않는 것이 좋습니다.

질문

는 다음과 같은

• 중 하나를 수행하는 것이 가능 필요에 따라 k=1에 대한 신호 "푸리에 공간에서 제로 패드 '의 FFT를 타고?
• FFT에서 순환 포장을 방지 하시겠습니까? 주파수 도메인에서

Answer 1

1. 제로 패딩이 가능하지만, 시간 영역에서하는 것보다 훨씬 더 계산 노력 (슬리퍼)이 필요하다. IFFT, zeropad 및 re-FFT를 사용하면 빠른 컨볼 루션을 추가 할 때마다 "룸"을 만드는 것이 더 빠를 것입니다.

2. 완전한 컨볼 루션의 결과가 어딘가에 있어야하므로 FFT를 사용할 때 순환 컨볼 루션을 방지 할 수 없습니다. 제로 패딩 (zero-padding)조차도 순환 오버랩 계산을 막지는 못하지만, 결과에서의 오버랩이 제로의 추가와 동등한 지 확인합니다.