MATLAB FAST convolution using FFT

이번 포스팅에서는 FFT 를 이용한 고속 convolution 에 대해 알아본다.

 

일반적으로 conv(x, y) 은 filter() 함수로 구현되는 선형 convolution 이다.

 

선형 convolution 은 x 또는 y 의 길이가 증가할수록 그 복잡도는 급격히 증가하는 특징이 있다.

 

이러한 선형 convolution 은 순환(Circular) convolution 을 이용하여 구현이 가능하며, 순환 convolution 은 FFT(Fast Fourier Transform) 와 IFFT(Inverse Fast Fourier Transform)를 이용하여 구현이 가능하다.

 

일단 선형 convolution 을 순환 convolution 으로 변환하는 과정에 대해 살펴 보자.

 

x=[1 2 3 4]

 

y=[1 4 5]

 

위 신호를 이용하여 다음과 같이 convolution 을 하면

 

Z=conv(x,y)

Z =

1 6 16 26 31 20

 

Z는 6 개의 인자를 갖는 수가 나온다. 이는 x 의 길이가 4 이고 y 의 길이가 3 이므로 length(x) + length(y) – 1 = 4+3-1 = 6 에 따른 결과 이다.

 

위에서 실행한 conv() 을 순환 convolution 함수 cconv() 을 이용하여 구성해 보자. 참조 : cconv() 함수는 signal Processing Toolbox 에 포함되어 있다.

 

• x 값을 6 개의 인자를 갖도록 뒤 부분에 0 을 2개 채워준다.

 

x1=[1 2 3 4 0 0]

 

• y 값도 6 개의 인자를 갖도록 뒤 부분에 0 을 3개 채워준다.

 

y1=[1 4 5 0 0 0]

 

• 위 두 벡터를 순환 convlution 한다.

 

Z_cconv=cconv(x1,y1, 6)

Z_cconv =

1.0000 6.0000 16.0000 26.0000 31.0000 20.0000

 

 

위 결과를 보면 선형 convolution 과 순환 convolution 의 결과가 동일함을 확인 할 수 있다.

 

이제 순환 convolution 과 FFT 사이의 관계를 알아보자.

 

(x 와 y 의 circular convolution) = IFFT(FFT(x)∙FFT(y)) 의 관계가 있다.

 

위에서 실행했던 순환 convolution 을 FFT, IFFT 를 이용하여 처리해 보자.

 

Z_fast=ifft(fft(x,6).*fft(y,6)) 을 실행하면 다음과 같은 결과가 나오며 이는 처음 실행했던 선형 convolution 의 결과와 동일한 것을 확인 할 수 있다.

Z_fast=

1.0000 6.0000 16.0000 26.0000 31.0000 20.0000