들어가며convolver라고 하는 것은 convolution을 하는 것/장치라고 할 수 있고, convolution이라고 하는 것은 어떤 신호가 어떤 선형 시스템 (이를테면 필터)를 겪는 일이라고 할 수 있다. 다소 추상적일 수 있는데, 더 자세한 것들은 신호처리라든가 공업 수학 같은 텍스트북을 통해서 확인하면 좋을 것 같다. 어쨌든 우리가 응답특성을 익히 알고 있는 선형 시스템이 있다고할 때, 그 응답 특성을 입력신호에 적용하면 출력 신호를 얻을 수 있다. 그 응답 특성을 입력신호에 적용하는 작업을 흔히 filtering 혹은 convolution이라고 이해하면 되겠다. 더 쉽게 이해하자면, 어떤 청년이 군대를 다녀와서 심신의 변화가 생겼다고 하자. 입대전의 청년을 입력으로 보고 시스템을 군대로 보면 군대라는 시스템의 특성이 오랜 동안의 복무를 통해서 그 청년의 몸과 마음을 변화시킨다고 할 때, 그 복무를 통해서 군대라는 시스템의 특성이 청년에게 입혀지는 과정을 convolution이라고 보면 되겠다.이것은 일련의 패턴 (시스템 응답) 을 입력 신호에 고루 적용해서 얻는 과정으로서, 수많은 곱셈과 덧셈을 한꺼번에 수행하는 것이다. 흔히 DSP의 연산 능력을 평가할 때, 1초에 몇 개의 MAC (Multiply + Accumulation)을 수행할 수 있다로 표현하곤 하는데, 바로 그 MAC 연산이 필터링을 수행하는 과정, 다시 말해 convolution을 수행하는 과정, 더 나아가서는 적분을 수행하는 과정에 쓰이는 것이다. 하나의 샘플을 곱해서 이전 결과에 쌓는 과정을 말한다. DSP에서는 이 과정을 1 clock에 마치려고 한다. 더 나아가서는 여러 개의 연산기를 복사해넣어서 한번에 여러 가지 MAC을 수행하게끔도 한다.말이 좀 샜는데, 어쨌든 이 convolution 연산을 스피커 시뮬레이션을 하는데 사용한다거나 reverb 효과를 낼 때 사용한다. 대개 입력 샘플의 개수는 한번 연산할 때 32개라든가 많게는 512개씩 들어오게 되는데, 이 때의 시스템 응답에 해당하는 impulse response의 길이는 수 초에 이르는 경우도 있다. 대략적으로 1초에 44100개 샘플이 필요하다면 2초를 가정하면 88100개 샘플과 512개의 샘플의 패턴과 convolution을 수행해야 한다. 적어도 동일 시간에 512개 샘플로 된 출력을 얻기 위해서는 엄청난 양의 MAC 연산을 수행해야 하는데, 이것은 요새의 좋은 컴퓨터로도 버거운 일이다.### FFT based convolution (Overlap and Add scheme)신호처리 기술을 획기적으로 발전시킨 요소 중에 임팩트가 가장 큰 것이 FFT(Fast Fourier Transform)가 아닐까 하는데, 그 성질 중 하나가 convolution연산을 곱셈으로 바꿀 수 있게 하는 것이다. 즉, MAC으로 계산해야할 것을 곱셈으로 계산해도 되는 것이다. 이게 어떤 장점이 있느냐 물어 볼 수 있는데 이를테면 다음과 같다.32개 샘플과 32개 샘플간에 convolution을 하고 싶다고 하면, 실제로 63개의 응답을 얻게 되는데, 대략적으로 (2N-1) x N (대략 2N^2), 63 x 32 (=2016 < 2048) MAC연산을 필요로 한다. 대신 FFT를 쓰면 64 FFT/IFFT 한번씩 그리고 64회 곱셈으로 끝나게 된다. N-point FFT의 연산 회수는 대략 N log (N) 특성을 가지고 있어서, N이 큰 값이 되면 일반적인 convolution 연산에 비해 엄청난 이득을 보게 된다. 이 때 L개 샘플과 N개 샘플간의 convolution 을 가정하면, convolution결과가 (N+L-1)로 나타나게 되는데, N이 일방적으로 L에 비해 엄청나게 크다고 가정하면, 당장에 필요한 L개의 샘플 결과만 얻고 나머지는 다음 기회에 처리하게 하는 방법이다. 즉, L이 N에 비해 매우 작다고 하면, L+L-1개의 샘플만을 처리하도록 한다. 이때 입력에 L-1개의 0을 채워서 convolution하면 나머지 L-1에 대한 결과는 다음 턴에 처리되는 신호와 더 해져야 하는 이전 블록의 꼬리부분이 되므로 남겨두었다가 다음 블록에서 처리된 결과와 더해서 내보내게 된다.이 때, FFT를 적용하려면 point의 개수가 2^N이 되면 바람직하므로, 32개씩 샘플을 처리하고자 한다면, 32+32-1 < 64 = 2^6 point FFT를 이용하면 31개 샘플에 해당하는 꼬리를 얻게 된다. 이 꼬리를 다음번 처리된 64개 샘플의 첫 머리에 더해서 내보내게 된다. 그런데, 모든 연산이 여기서 끝난 게 아니다 L개 샘플로 N개 샘플 구간 모두를 convolution 해야 되므로, 다음 턴에는 N:N+L-1 구간에 대한 convolution도 처리해야 한다. 따라서, N/L이 P라고 하면 L개의 샘플을 보내기 위해서는 2L point FFT를 P번 수행해야 한다.이를테면 2초짜리 impulse response를 이용해서 32개 샘플에 대한 처리결과를 계산하자면, 64 point FFT를 총 2756번 수행한다.###Speaker simulation/ReverbOverlap and add 방법을 이용해서 엄청나게 긴 impulse response를 짧은 샘플 블록에 적용하는 절차를 생각해 보도록 하자.1. impulse response를 import한다. import시에 적정 길이로 잘라서 미리 모든 FFT를 계산해 놓는다. 이것을 H_0~N-1이라고 하자. 이 길이는 plugin에서 가져오는 블록의 샘플 수와 같다.1. L개 (1블록) 샘플 입력을 받는다. L개 0을 더 채워서 2L point FFT를 계산한다. 1. 2)의 결과를 1)의 모든 H에 대해 곱하고 이전의 처리 결과들에 누적한다. 1. 3)에서 현재 블록에 해당하는 데이터만 가져다가 IFFT 계산하고 이전 IFFT 연산에서 나온 꼬리부분을 더해서 내보낸다. 1. 2)로 돌아가 반복한다.따라서, 결과를 모아보면,1. import시에 FFT는 총 N번 수행하게 된다. (N=M/2L, M은 impulse response 길이)1. 새로운 L개 샘플 입력시, 1. 1회 FFT, N * 2L 회의 MAC 수행 1. 1회 IFFT, L회의 덧셈을 수행신호가 pipeline처리가 되므로 실제로 매 블록별로 수행해야 하는 FFT의 수는 2L point FFT/IFFT 각각 1회밖에 되지 않는다. 다만 convolution을 대신하는 곱셈 처리를 많이 해야 하는 것이 불가피하지만 convolution을 하는 것에 비하면 엄청나게 작은 연산이다. 정말로 신기하지만 그렇다. 그래서 엄청나게 긴 reverb를 처리하더라도 컴퓨터가 큰 고생안하고 처리하는 것이다. ### 실험실제로 build해 보니 FFT based convolution이긴 하지만, 예상대로 fft의 회수는 얼마 되지 않아 실제로 전체 수행시간 중 차지 하는 비율을 0.2%도 안되는 것으로 나타났다. 대부분의 시간은 convolution이 주파수 영역으로 변환된 작업, 즉 frequency response를 곱하고 누적하는 과정에 모든 수행시간이 소요되었다. 이것을 time domain에서 discrete convolution으로 바꾸게 되면 곱셈 연산이 엄청나게 늘어나게 되어 실시간 처리가 거의 불가능할 정도가 되는 반면, fft convolution을 하면 엄청나게 쾌적하게 convolution을 할 수 있으니 비교가 불가하다 할 수 있겠다. 예전에도 재미삼아 시도해보았지만 SSE 명령을 이용해서 complex multiplication을 만들더라도 사실상 SSE register에 값을 옮겨담는 과정에서 대부분의 cycle을 잃어버리게 된다. 실제로 곱셈을 하는 데 드는 싸이클은 얼마되지 않는다고 하더라도 말이다.근본적으로 한번에 처리하는 블록의 크기가 클 수록 수행시간이 상대적으로 줄어들게 된다. 그러나 블록을 크게 할 수록 latency가 늘어나게 되므로 사실상 DAW에서 넘겨주는 block size (audio interface 설정에 따라 결정된다)에 의존하게 된다.