FFT로 하는 정합 필터

정합 필터를 실제로는 어떻게 계산하는가? 받은 샘플 $N$개에 replica $L$개를 밀며 곱하면 곱셈이 $NL$번 필요하다. 상호상관은 주파수 영역에서 곱이므로, FFT로 바꾸어 곱하고 되돌리면 빠르다.

예제 펄스(300개 샘플, 30 MHz)의 에코 둘(진폭 1과 0.5)을 n = 200과 206에 넣고 잡음(샘플당 분산 0.5)을 더했고, FFT 길이는 M = 2048이다. 샘플 간격 하나는 c/(2f_s) = 5.0 m이고, 거리는 받기 시작한 시각에서 잰 값이다.

받은 샘플에서는 10 µs 길이의 두 에코가 겹쳐 눈으로 갈라지지 않는다. 스펙트럼은 chirp의 대역 ±7.5 MHz를 채운다. replica의 켤레 스펙트럼을 곱하고 되돌리면 999 m와 1029 m에 피크 둘이 선다. 30 m는 분해능 10.0 m의 세 배라 두 피크가 갈라진다. 직접 상호상관은 받은 샘플 $N$개마다 replica $L$개를 곱하므로 곱셈이 $NL$번 들고, FFT 방식의 계산량은 $M\log_2M$에 비례한다. 이 예에서 직접 상호상관은 곱셈 307 200번, FFT 세 번과 곱은 약 35 840번이 들어 FFT 방식이 9배쯤 적다. replica가 길수록 이 차이가 벌어진다.