I. 서 론
능동 소나(active sonar)는 음향 펄스를 송신하여 그 반향음의 시간지연을 측정하고, 이를 표적의 거리 값으로 환산한다.[1] 표적에서 반사되어 돌아온 펄스가 송신한 펄스와 동일한 파형을 가진다고 가정할 때에, 반향음의 시간지연을 추정하기 위한 최적의 방법은 정합 필터를 적용하는 것이다.[1] 즉, 송신 파형과 수신한 신호의 상호상관(correlation)을 계산하여, 상호상관이 최대값이 되는 시점에서 반향음의 도달시각을 결정하게 된다.
한편 능동 소나를 이용하여 표적의 탐지 확률을 높이려면, 정합 필터한 결과의 신호대 잡음비를 높여야 한다.[1] 이를 위해 최근 연속적인 긴 펄스신호(continuous wave)를 송신하여 표적을 탐지하는 방안이 연구되고 있다.[2] 이렇게 송신 파형의 길이가 길어지면, 콘볼루션을 이용하여 구현한 정합 필터링은 송신 파형의 길이 T에 비례하는 연산량이 필요하다. 그러나 잘 알려진 FFT와 신호 블록 단위의 중첩-합 또는 중첩-저장 방법을 적용하면 연산량이 log(T)에 비례하므로, 펄스 길이가 길어질수록 연산량 측면에서 매우 유리하다.[3,4]
한편 실제 시스템에서는 신호 블록의 크기를 임의로 결정할 수 없으며, 신호 블록의 길이는 시스템의 허용 시간지연(time delay)과 입출력 연동 방식에 의해 결정된다. 신호 블록의 길이가 주어진 경우 효율적으로 정합 필터를 수행하기 위해 , 필터를 크기가 2배로 증가하는 하부 블록으로 분할하고, 분할된 필터 블록에서 각각 정합필터를 수행한 결과를 합산하여 최소의 연산량을 달성하는 MC 방식이 제안되었다.[5] 이 방법은 가장 작은 크기로 분할된 필터 블록을 이용하여 실시간 연동되는 단위 신호 블록을 처리할 수 있으며, 크게 분할된 필터 블록을 이용하여 낮은 연산량을 달성할 수 있다.[5]
그러나 MC 방법은 분할된 필터 블록의 크기가 가변적이기 때문에, 블록 처리 시점의 스케줄링과 최적화를 위한 로직이 요구된다. 이러한 문제점은 정합 필터를 균등 분할하여 처리하면 해결할 수 있다. 특히 균등 분할된 정합 필터를 각각 주파수 영역에서 처리한 결과를 합산하여, 한번의 IFFT로 처리하는 FDL 방식은 IFFT 연산을 재사용하므로, 정합 필터의 총길이에 비해 필터 블록의 크기가 큰 경우에는 MC 방식에 비해 더 작은 연산량을 달성 할 수 있다.[6,7]
FDL 방법은 한 번에 처리하는 블록의 크기가 크면 효율적이며, 처리 블록의 크기가 작아지면 연산량이 급증할 수 있다. 따라서 필터의 앞단을 작은 길이의 FDL로 분할하고 뒷단을 큰 길이의 FDL로 분할하여, 연동 주기를 만족하면서 동시에 연산량을 감소시키는 방법이 제안되었다.[7] 이 방식은 Viterbi 알고리즘을 이용하여 다단의 FDL을 이용한 모든 필터 분할 구조를 검색하고, 최적의 분할 필터 구조를 결정한다.[7]
이러한 알고리즘에 기반한 최적화 방식은 모든 분할구조를 검색하므로 최적의 필터 분할 구조를 찾아낼 수 있으나, 직관적인 이해가 어렵고 다단의 FDL을 사용함으로써 구조가 복잡해질 수 있다. 따라서 본 논문에서는 모든 필터 분할 구조를 검색하는 Viterbi 알고리즘 대신, 전체 필터를 MC와 FDL의 2개의 단으로 분할하여 이해 및 적용이 용이한 필터 분할방식을 제안하였다. 제안한 MC-FDL 2단 알고리즘은 모든 분할구조를 검색하는 Viterbi 알고리즘에 비해 연산량 측면에서 비효율적이지만 필터의 구조가 단순하여 이해가 용이하며, MC 및 FDL 방법에 비해서는 필터의 구조가 복잡하지만, 보다 효율적인 연산이 가능하다. 따라서 제안 알고리즘은 MC 및 FDL 방법을 적용해도 연산량이 부족한 경우, 복잡한 최적화가 필요한 다단의 FDL 구조를 적용하기 전에 우선적으로 대안으로써 검토될 수 있다.
II. 균등 분할 FDL 정합필터링
송신한 파형을 
, 수신한 파형을 
, 송신 파형의 길이를 T라고 하면, 정합 필터링은 다음의 Eq.(1)과 같이 정의된다.
.Eq.(1)의 상호상관-합 연산은 유한응답(finite impulse response) 필터의 콘볼루션을 이용하여 쉽게 구현이 가능하지만 연산량이 과도하게 요구된다. 반면 Fig. 1과 같이 주파수 영역에서 FFT를 이용하면 Eq.(1)의 연산을 매우 효율적으로 구현할 수 있다.[3-5]
그러나 송신 파형의 길이가 매우 긴 경우에는, Fig. 1과 같은 중첩-합 방법을 적용하면, 신호 블록의 연동 주기가 매우 길어져 시스템의 시간지연이 발생한다. 따라서 이를 줄이기 위해 Fig. 2와 같이 필터를 균등분할 하여 분할된 필터 응답을 각각 구하고 이를 합하여 정합 필터 응답을 얻는 방법이 제안되었다.[6,7] 이 때 분할된 필터 블록의 길이와 연동 단위 신호 블록의 길이가 동일하면(2-기반 FFT 알고리즘 적용을 위해 2n 길이로 분할), Fig. 3과 같이 분할된 정합 필터 출력의 위치가 동일하게 정렬되고, 주파수 영역의 상호상관 스펙트럼을 합한 뒤 IFFT를 실시하는 FDL 방법을 적용할 수 있다. 이 경우 한 블록(샘플 개수 N)의 정합 필터 출력을 얻기 위해 FFT / IFFT 연산을 각 1회만 수행하면 되므로, 매우 효율적이다.[6,7]
단위 신호 블록의 크기를 N, 전체 필터 길이를 T라고 할 때에, 단위샘플 출력 당 FDL 방법의 곱셈 연산량 OFDL은 다음 Eq.(2)와 같이 각 1회의 FFT 연산량 OFFT, 1회의 IFFT 연산량 OIFFT, 주파수 영역의 복소 곱연산 OMUL의 합으로 주어진다.[7] 이때 중첩-합 방법은 Fig. 1에서 확인할 수 있듯이 신호 블록을 영 채우기(zero padding)하여 2배 길이의 블록을 만들어 FFT를 수행하므로, FFT의 경우 IFFT에 비해 연산량을 반으로 줄일 수 있다.[5] 또한 정합 필터 길이 T가 블록 크기 N의 배수가 아니면, 영 채우기를 통해 정합 필터 길이가 N의 배수가 되도록 확장해야 하므로 , 연산량 계산시 가장 가까운 정수로 올림 함수가 적용되었다.
[
]
[
]
,
,
.FDL 방법의 단위 샘플 출력당 연산량은 분할된 필터 블록의 길이에 따라 달라진다. 분할된 필터 블록의 길이는 연동되는 단위 신호 블록의 길이로 주어진다. 이 때 신호 블록의 길이 N 값이 작으면 Eq.(2)의 주파수 영역 복소 곱연산량인 [
]항목에 의해 연산량이 증가하는 문제가 발생한다.
III. 가변 분할 최소 비용 정합필터링
일반적으로 주파수 영역에서 필터링을 수행할 때 한 번에 처리하는 블록의 크기가 늘어나면 연산량이 감소하게 된다. 따라서 연산량을 줄이기 위해서 되도록 많은 신호를 큰 블록으로 처리하는 것이 유리하다. FDL에서 IFFT 재사용을 위한 최적화를 적용하지 않은 경우, 연산량을 최소화하는 MC 방법은 Fig. 3 및 Eq.(3)과 같이 전체 필터를 2의 배수로 증가하는 블록의 길이로 분할하는 것이다.[5,7] 이 때, 예외적으로 최초 블록과 두 번째 블록의 크기는 연동 요구사항을 만족하기 위해 연동 단위 신호 블록의 길이인 N으로 동일하게 주어진다.
.이러한 가변 구조는 큰 블록의 주파수 영역 필터링을 수행하여 연산량이 감소되나, 필터 출력의 길이가 상이하며 이를 주파수 영역에서 합하는 FDL 방법의 적용이 불가하므로, 출력 블록마다 IFFT 연산을 수행하게 되어 효율이 떨어진다. 또한 필터 블록의 입력 역시 N, 2N, 4N, …으로 가변적이므로, 입력 블록마다 FFT 연산을 수행하게 되어 효율이 떨어진다. 한편 입력 블록의 FFT 연산을 효율화하는 방법으로, 작은 블록의 FFT 결과를 이용하여 큰 블록의 FFT를 얻는 방법이 제안되었으나[예를 들면 Fig. 3에서 FFT(x1), FFT(x2)를 재활용하여 FFT(x12)를 계산],[5] 본 논문의 연산량 계산시에는 그러한 최적화 방법은 반영하지 않았다.
전체 정합 필터의 길이를 T라고 할 때 MC 방법을 이용하는 경우, 분할된 블록의 개수 PMC(Fig. 3의 경우 PMC=4)는 아래의 식으로 주어진다. 이때 필터 길이가 N의 2의 승수배가 아니면, 영 채우기를 통해 필터를 연장하여야 하며, 이로 인해 불필요한 연산이 추가된다.
[
]
전체 정합 필터가 PMC개의 블록으로 분할될 때, MC 방법의 단위 샘플 출력당 연산량 OMC는, (a) 최초 블록을 제외하고 길이가 2의 배수로 증가하는 각각의 필터 블록에 의한 연산량 OSB의 합과, (b) 최초 블록의 주파수 영역 복소 곱연산 OMUL 및 IFFT 연산량 OIFFT의 합으로 주어진다.[7] 최초 블록의 입력 신호의 FFT 연산은 두 번째 블록에서 재활용하므로 산입하지 않는다.
.길이가 2의 배수로 증가하는 단위 필터 블록에 의한 연산량 OSB는 다음 Eq.(6)과 같이 입력 주파수 스펙트럼을 얻기 위한 FFT, 주파수 영역의 복소 곱연산, 시간 영역 출력을 얻기 위한 IFFT 연산량의 합으로 주어진다.[7]
.결국 총 연산량은 아래 Eq.(7)과 같이 계산된다.
, 
.한편 실시간 프로세서에서 구현 시에는 시간별 연산 부하를 일정하게 하기 위해, 다음 Eq.(8)과 같은 변형된 분할 구조가 사용된다.[5,7] 이로 인해 연산량이 일부 변동되나, 이미 언급한 방법을 적용하여 쉽게 계산되므로 이와 관련한 논의는 생략한다.
.IV. 제안 알고리즘
FDL 방법은 전체 정합 필터의 길이 T에 비해 연동 단위 신호 블록의 크기 N이 크면 IFFT 재사용을 통해 MC 방법에 비해 작은 연산량을 달성할 수 있다. 그러나 FDL 방법에서 정합 필터의 길이 T에 비해 N이 작아지면 Eq.(2)의 [
] 항목의 연산량이 증가하여 MC 방법에 비해 비효율적이다. 따라서 본 논문에서는 연동 블록의 크기를 충족하면서 연산량을 줄이기 위해 Fig. 4와 같이 필터의 앞단을 MC 방법으로 분할하고, 뒷단을 FDL로 분할하는 MC-FDL 방법을 제안하였다. 이 방법은 연동 단위 신호 블록의 크기 N이 작으면 MC 방법이 유리하며, 신호 블록의 크기가 크면 FDL이 유리한 점에 착안하여 두 가지 방법의 장점을 결합한 것으로, 상대적으로 간단한 최적화가 가능하다.
제안한 MC-FDL 방법에서 최적화시 결정이 필요한 파라미터는 앞의 MC단의 분할 개수 P 밖에 없으므로, 매우 간단한 최적화가 가능하다. 이 때 MC단의 길이가 전체 필터의 길이 T 보다 작아야 하므로, 분할 개수 P의 최대값은 Eq.(4)의PMC로 주어진다. 제안한 분할 알고리즘의 연산량 OMC-FDL은 전체 정합 필터의 길이가 T일 때, 파라미터 P에 대해 Eq.(9)와 같이 얻는다.
,
, 
은 해당 없음. 따라서 최적 분할 파라미터 P는 연산량 OMC-FDL을 최소화하는 조건을 적용하여 얻는다. 즉 제안한 방식은 P = 0, 2, …, [
]
에서 연산량 OMC-FDL이 최소화되는 파라미터 P를 선정한다. 그런데 제안 방법은 
이면 MC 방식이 되고, P = 0이면 FDL 방식이 됨을 알 수 있다. 따라서 제안한 MC-FDL 방식은 MC 및 FDL 방식에 비해 언제나 낮은 연산량으로 수행 가능하므로, 두 방식에 비해 연산량 측면에서 항상 효율적인 알고리즘이다.
V. 모의 분석
제안한 알고리즘과 기존의 MC, FDL 방법의 성능을 비교 분석하기 위해 모의 분석을 실시하였다. 정합 필터의 길이 T는 64부터 최대 131,072까지 가변하여, 충분히 긴 펄스를 송신할 경우에 연산량이 어떻게 되는지를 살펴보았으며, 실시간 연동되는 신호 블록의 길이 N은 256으로 고정하였다. FFT의 연산상수 k는 일반적으로 알려진 값 k=1.5를 적용하였다.[7]
Fig. 5의 모의 분석 결과를 살펴보면, 콘볼루션을 이용하여 직접 정합필터를 수행하는 방식(direct-form)은 연산 측면에서 매우 비효율적으로, 실제 구현시 해당 방식을 적용하기 전에 신중한 검토가 필요함을 알 수 있다. 또한 정합 필터의 길이가 작으면 FDL 방식이 상대적으로 효율적이고, 정합 필터의 길이가 길어지면 MC 방식이 상대적으로 효율적임을 알 수 있다. 이는 FDL 방식의 연산량은 정합 필터의 길이 T에 비례하지만, MC 방식의 연산량은 (log T)2에 비례하기 때문이다. 한편 본 논문에서 제안한 MC-FDL 방식은 비교 대상 알고리즘 중에 가장 낮은 연산으로 수행 가능하여 가장 효율적임을 알 수 있다.
VI. 결 론
능동 소나에서 정합 필터는 가장 기본적인 신호처리 방식이다. 이를 콘볼루션을 이용하여 직접 구현하는 것은 개념적으로는 단순하지만, 연산측면에서 매우 불리하다. 특히 표적의 탐지 성능을 높이기 위해 상당히 긴 펄스를 이용하는 경우, 단위 출력당 연산량이 펄스의 길이에 비례하여 급증하게 되어, 실시간 병렬 처리를 위한 복잡한 설계가 필요하게 된다. 따라서 효율적인 구현을 위해 시간영역 대신 주파수 영역에서 콘볼루션을 구현할 필요가 있다.
본 논문에서는 주파수 영역 정합필터 방식으로 기존에 알려진 FDL 방식과 MC 방식을 검토하고, 두 방식의 장점을 결합한 MC-FDL 방식을 제안하였다. 제안 알고리즘은 필터의 앞단을 MC 방법으로 분할하고, 뒷단을 FDL 방법으로 분할하여, 연동 주기의 제한 사항을 충족하면서 동시에 처리 연산량을 감소시킬 수 있었다.
