Note : DFT & Circular Convolution
Reference
The Scientist and Engineer's Guide to Digital Signal Processing (By Steven W. Smith, Ph.D.)
https://www.dspguide.com/ch9.htm
CH 9. 내용을 보고 작성함.
Circular Convolution
Convolution 연산은 계산이 복잡하고 계산 자원이 많이 들어 기피 대상이고, 그래서 많은 경우에 Frequency Domain 으로 전환해서 거기에서 곱셈을 하는 방식을 사용한다.
x[n] * h[n] 을 계산하고 싶은데? 직접 계산하면 O(N^2) 로 느리니까 FFT (DFT) 를 쓰면 O(N log N) 으로 빠르니까 이걸로 주파수 도메인으로 바꾼다음에 곱해서 iDFT 하면 쉽게 계산할 수 있겠지?
그런데 DFT 를 가지고 Convolution을 계산할 때 꼭 짚고 넘어가야 하는 문제가 있다.
DFT를 계산 시에 입력되는 신호는 time-domain 에서의 주기성을 가정한다. (입력으로 들어가는 신호는 원래는 finite 한 비주기 신호인데, DFT 수식에 넣으면 입력 신호 자체를 주기신호로 가정하고 계산한다. )
그래서 생기는 문제가 Circular Convolution 인데 더 자세히 알아보자.
입력 신호의 길이 N, Impulse Response 의 길이 M 일때, 두 신호를 convolution 해서 나오는 output 의 길이는 N+M-1 개이다.
(이때 N, M 에서 zero-padding 된 부분은 빼고 non-zero 한 부분만 개수를 센다. 왜냐면, Convolution 연산의 정의를 생각해보면, 시그마이기때문에 zero 인 부분은 무시된다.)
위 그림을 보면, 입력신호 a 의 길이: 255, b의 길이: 51
컨볼루션 결과는 255 + 51 - 1 = 305 의 길이를 가지는 시퀀스가 된다.
(그리고 a, b는 sampled signal, sampled impulse response 이다.)
DFT 에서는 이 결과를 주기적인 신호로 가정하는데, a와 b 모두 신호의 길이가 256개이므로 주기 256의 신호로 취급한다.
그런데 실제 컨볼루션의 결과의 길이는 305 이므로 256 보다 크기 때문에, 이것을 주기신호로서 나열하면 데이터가 있는 부분이 겹치게 된다.
-> Circular convolution 발생
마지막 e 그림과 d 그림을 비교하면, overlap 때문에 convolution 결과가 원하는대로 나오지 않는 것을 볼 수 있다.
그러므로 circular convolution 은 일반적인 상황에서는 피해야 한다. (의도하는 결과와 다른 연산 결과가 도출되므로)
어떻게 피할 수 있을까?
지금 우리가 하는 작업은 x[n] * h[n] 을 구하기 위해 DFT 를 수행하여 frequency domain 의 연산으로 바꾸고자 하는 작업이었다.
컨볼루션의 결과가 처음 주기 신호의 256보다 큰 게 문제였으므로 그것보다 DFT point 의 크기를 크게 해주면 된다.
즉, a, b에 각각 zero-padding 을 해줘서 길이를 305보다 크게 잡아주면 된다. 그렇게 하면 d 의 각 segment 의 길이가 더 길어지고 overlap 이 발생하지 않을 것이다.
FFT 알고리즘에 의하여 segment size 는 2의 승수로 하기 때문에 이 경우에는 256이 아니고 주기를 512로 잡아서 계산하면 왜곡이 없을 것이다.
-> 이런 경우에 대해 circular convolution 이 linear convolution 과 같다고 표현한다.
수식으로 표현하자면 DFT의 길이 L >= N + M - 1 인 경우에 성립한다.
예시로 따지면
- L < 305 : Circular convolution 발생
- L = 305 : Linear convolution과 동일, y[n] 305개
- L = 512 : 실용적으로 2의 승수를 사용하기 때문에 512개로 만들것이고, y[n]은 305개의 non-zero 신호 + 207개의 0 이 붙은 형태로 나타난다. (전체 길이 205)
