FIR 필터의 계수가 CSD(canonic signed digit) 형식으로 표현되고 계수 당 0이 아닌 자릿수가 매우 적다면 적은 하드웨어 비용으로 고속 필터링을 수행할 수 있다. 주어진 주파수 응답 특성을 따르며 최소의 0이 아닌 부호자릿수(signed digit)를 갖는 CSD 형식의 FIR 필터 계수를 설계하는 문제는 목표 주파수 응답과의 최대 오차를 최소화하는 희소한 0이 아닌 부호자릿수 계수를 찾는 문제와 같다. 본 논문에서는 FIR 필터의 무곱셈 초고속 구현을 위해 압축센싱 기법에 기반을 둔 CSD 형식의 계수 설계 알고리듬을 제안한다. 탐욕(greedy) 방법을 채용한 본 알고리듬에서는 매 반복 단계에서 잔차 신호를 구성하는 가장 큰 크기의 atom을 선택하고, 그 atom의 계수를 나타내는 가장 큰 부호자리를 찾아 FIR 필터의 계수를 갱신한다. 설계 예를 통해 평균적으로 탭 당 두 번 이하의 덧셈만으로 목표 주파수 응답에 근접한 FIR 필터링을 수행할 수 있음을 확인하였고, 이는 적은 하드웨어 비용으로 고속 필터링 구현에 적합하다. 고속 디지털 필터는 광대역 통신, SDR (software defined radio), UHD-TV, 고해상도 측정 장비 등에 널리 사용되고 있다. 실시간으로 이러한 높은 데이터율의 신호를 다루기 위해 범용 DSP와 같이 프로그램할 수 있는 소자를 사용할 수도 있으나 병렬 처리 기법을 도입하지 않는다면 요구되는 성능을 얻기 힘들다. 또한 이 방법은 설계, 제조 등 여러 측면에서 높은 비용을 수반한다. 필터의 계수가 고정되어 있다면 ASIC이나 FPGA등과 같은 전용 하드웨어를 이용하는 것이 성능과 비용 측면에서 좋은 방법이 될 수 있다. 특히 필터의 계수가 2의 지수승의 합으로 표현된다면 범용 곱셈기를 사용하는 대신 덧셈기와 쉬프터(shifter)만으로 필터링의 곱셈 연산을 구현할 수 있다. 쉬프터는 신호의 연결만으로 구현할 수 있으므로 추가의 비용 없이 실현할 수 있으며, 덧셈기의 하드웨어 비용은 범용 곱셈기에 비해 매우 적다. 따라서 디지털 필터의 계수를 최소 개수의 2의 지수승의 합으로 표현할 수 있다면 필터의 구현 비용을 상당히 낮출 수 있다. 2의 지수승의 합과 차로 수를 표현하는 방식을 radix-2 부호자릿수 (signed digit) 형식이라고 한다. 이 표현 형식으로 한 수를 나타낼 수 있는 방법은 여러 가지이다. 또한 최소 개수의 0이 아닌 자릿수로 어떤 수를 표현하는 방법도 여러 가지이다. CSD (canonic signed digit) 방식은 최소 개수의 0이 아닌 2의 지수승의 자릿수로 유일하게 수를 표현하는 방식이다 [1] . CSD 형식에서는 두 개의 0이 아닌 자릿수가 인접할 수 없다는 특징을 가지고 있다. 또 하나의 CSD 표현 방식의 장점은 2진 표현 방식보다 적은 개수의 0이 아닌 자릿수로 임의의 수를 표현할 수 있다는 점이다. 2진수를 CSD 형식으로 변환하는 간단한 알고리듬도 널리 알려져 있다 [2] . 일반적인 FIR 필터의 차수는 수십 또는 수백이므로 필터 계수가 최소 개수의 0이 아닌 자릿수를 갖는 CSD 형식으로 표현된다면, 계수의 전체 자릿수 중에서 0이 아닌 자릿수의 개수는 매우 희소(sparse)하다. 압축센싱(compressive sensing)은 신호의 획득 및 압축의 새로운 접근 방법으로서 최근 연구자들의 높은 관심을 받고 있다. 전통적인 아날로그 신호의 획득 방법은 Nyquist 이론에 기반을 두고 있다. 이 이론은 모든 신호의 획득에 적용되는 충분조건이며 따라서 특정 성질을 갖는 신호를 다룰 때에는 그 효율성이 매우 떨어지는 단점이 발생한다. 예를 들어 길이가 N 인 신호 x 의 0이 아닌 성분의 개수 K 가 N 보다 매우 작다면, 즉 x 가 희소하다면 N 보다 작은 M 의 길이를 갖는 측정값 y 로도 x 를 완전하게 복원해낼 수 있음이 압축센싱 이론에서 증명되어 있다 [3 , 4] . 달리 말하면, 𝛷를 통하여 y 를 만족시키는 희소한 x 를 찾을 수 있다. K 는 희소도 수준(sparsity level)이라 하고 x ∈ R^N 는 K -희소( K -sparse)하다고 한다. y ∈ R^M 는 x 와 샘플링 벡터 { ϕ_i | i ∈ [1: M ]} 사이의 내적(inner product)으로 계산된다. 식으로 표현하면 다음과 같다. 𝛷는 M × N 측정행렬이며, M < N 이므로 y 로부터 x 를 복원하는 문제는 하나 이상의 해를 갖는 underdetermined 상황이다. 따라서 일반적으로 x 를 구할 수 없다. Candes [3] 와 Donoho [4] 는 x 가 충분히 희소하고 측정행렬 𝛷의 투사 특성이 적절히 균일하다면 M = O ( K log( N / K ))개의 측정값으로 x 를 복원해 낼 수 있음을 보였다. 이 때 복원에 사용할 수 있는 방법으로는 비선형 컨벡스 최적화 기법으로 식 (2)와 같은 l ₁ -norm을 최소화하는 기저추구(Basis Pursuit, BP) 방법 [5] 이 있다. 그러나 이 방법의 요구되는 계산량은 O ( N ³ )으로 대부분의 응용에서 사용하기 어렵다. 이러한 과도한 계산량의 문제점을 해결하기 위해 다양한 연구가 진행되고 있으며 특히 탐욕 (greedy) 알고리듬에 기반을 둔 연구가 많은 연구자들의 관심을 받고 있다. 이러한 노력은 정합추구 (matching pursuit, MP) 알고리듬 [6] 에서 시작하여 직교정합추구 (orthogonal matching pursuit, OMP) [7] 를 비롯하여 여러 가지 방법들이 제안되었다 [8 , 9] . 본 논문에서는 압축센싱 기법을 이용하여 0이 아닌 2의 지수승의 개수가 최소인 CSD 계수를 갖는 FIR 필터를 설계하는 방법을 제안하고자 한다. 먼저 제안된 알고리듬을 단계별 동작을 기술하고 이어서 설계 예를 통해 제안된 알고리듬의 무곱셈 디지털 FIR 필터 구현 성능을 보인다. N 차 선형 위상 FIR 필터의 주파수 응답은 다음과 같이 표현된다. { h_n , 0 ≤ n ≤ N }은 이 필터의 임펄스 응답이다. 만약 N 이 짝수이고 h_n = h _N−n 이라면, 즉 이 필터가 Type-I FIR 필터이라면 식(3)은 다음과 같이 쓸 수 있다. 물론 이 필터가 Type-I이 아니라고 하여도 아래와 유사하게 식을 전개할 수 있다. 단 M = N /2이다. x ≡ ( h_M , 2 h _M−1 , ..., 2 h ₀ ) ^T 라 정의하면 이 필터의 주파수 응답의 크기는 다음과 같다. 단 𝜙( w ) ≡ (cos(0), cos( w ), ..., cos( Mw )) ^T 이다. 주어진 목표 주파수 응답의 크기가 | H _d ( e ^jw )|라고 하면 필터를 설계하는 문제는 다음과 같아진다. 식 (6)의 해를 구하기 위해 이산화 과정 [10] 을 적용한다. 즉, 0과 π 사이의 연속 변수 ω 를 균등하게 표본화하여 이산 변수 ω_i , 0 ≤ i ≤ L 를 만들고, 이를 식 (6)에 적용하여 모두 모으면 다음과 같다. 단 x 의 각 성분 x_i 를 B 개의 부호자릿수 s _ij 로 표현한다면 다음과 같다. 단 s _ij ∈{−1,0,1}이다.. x 를 행렬로 표현하면 이고, 성분의 위치를 조정하여 다시 쓰면 다음과 같다. 식 (14)를 식(7)에 대입하면 다음과 같다. 단, 이고 s 는 식 (14)의 오른편에 보이듯이 x 의 부호자릿수로 구성된 ( M +1) B ×1 열벡터이다. x 는 설계하려는 필터의 계수이므로 부호자릿수 형식으로 표현된다면 병렬 곱셈기를 사용하지 않고 쉬프터와 덧셈기로 필터를 구현할 수 있다. 더불어 0이 아닌 부호자릿수의 개수를 최소화하면, 즉 희소한 s 를 찾으면 하드웨어 비용을 최소화할 수 있다. 식 (15)는 측정값 y 로부터 오차의 l ₂ 크기가 최소이며 희소한 신호 s를 복원하는 전형적인 압축센싱 문제이다. 그런데 s 의 각 성분은 –1, 0, 또는 1의 값만 허용되는 확장 Bernoulli 분포를 갖는다. 즉, 복원할 신호에 제약 조건이 존재한다. 또한 식 (16)에서 𝛹는 크기가 반씩 줄어드는 𝛷들이 연립된 형태임에 주목하면, 식 (15)의 문제는 각 부호자릿수 위치별로 복원되어야할 신호가 있는지를 결정하고 이를 모든 부호자릿수에 대해 반복함으로써 풀 수 있다. 본 논문에서는 주어진 주파수 응답 특성을 만족하는 FIR 필터의 희소한 부호자릿수 표현을 찾는 알고리듬을 그림 1 과 같이 제안한다. 알고리듬의 시작을 위해 필요한 𝛷와 y 는 각각 식 (9)와 (10)과 같이 주어진다. 또한 반복 횟수를 제한하기 위해 최대 반복횟수 n _max 와 최대 오차 𝜖가 필요하다. 반복 과정을 시작하기 전에 복원할 신호 x 와 잔차 신호 r 은 각각 0과 y 로 초기화한다. 반복과정이 종료되면 x 는 FIR 필터 계수가 부호자릿수 형식으로 저장되어 있고, r 은 l ₂ 크기가 𝜖보다 작거나 0에 가까운 값을 가지게 된다. 반복과정은 크게 선택, 추가, 갱신의 세 단계로 구성된다. 첫 번째 단계에서는 하나의 부호자릿수를 추가할 계수 즉, x_μ 와 그 값, 2 ^−δ 를 선택한다. 좀 더 자세하게 살펴보면 단계 1a에서는 잔차에 대한 least squares 해 ρ 를 구한다. 단, 𝛷 ⁺ 는 𝛷의 pseudo inverse이다. ρ 의 성분 중 크기가 가장 큰 성분의 위치를 𝜇에 저장한다(단계 1b). ρ 의 각 성분은 잔차에 대한 해당 atom들의 기여도이므로, x 의 𝜇번째 성분인 x_μ 에 적절한 Δ x_μ 를 더함으로써 x 를 가장 크게 개선시킬 수 있다. 그런데 x 는 부호자릿수 형식으로 표현되어야 하므로 Δ x_μ 는 ρ_μ 에 가장 가까우며 크기도 가장 큰 2의 지수승이어야 한다. 만약 2 ⁻ⁱ < ρ_μ ≤ 2 ⁻ⁱ⁺¹ 이라면, (2 ⁻ⁱ +2 ⁻ⁱ⁻¹ )을 문턱값으로 삼아 Δ x_μ 는 문턱값보다 작으면 2 ⁻ⁱ 이 되고 아니면 2 ⁻ⁱ⁺¹ 이 된다. 즉, 2의 지수 ν 는 다음과 같은 식을 만족하는 i 로 결정된다 (단계 1c). 두 번째 단계에서는 이전 단계에서 결정한 Δ x_μ 를 x_μ 에 더한다. 즉, 이 단계가 실행될 때마다 x 에 하나의 부호자릿수가 추가되어 x 에 의한 주파수 응답 특성을 개선해 나간다. 갱신된 주파수 응답으로부터 통과영역과 정지대역의 최대 ripple δ_p 와 δ_s 를 구한 후 최대 허용오차 𝜖와 비교한다. W 는 ripple 가중치이다. W =1이면 δ_p 와 δ_s 를 동등하게 비교하고, W >1이면 정지대역 ripple을 성능 비교의 주 대상이 된다. 최대 ripple이 성능 조건을 만족하면 반복은 종료된다. 즉, 더 이상 필터계수에 추가의 부호자릿수를 할당하지 않는다. 마지막으로 세 번째 단계에서는 수정된 x 를 사용하여 잔차를 갱신하고, 반복과정을 다시 수행한다. 이 장에서는 두 가지의 설계 예를 이용하여 제안된 알고리듬이 낮은 구현 복잡도를 갖는 부호자릿수 FIR 필터의 설계에 활용될 수 있음을 보인다. 모든 예에서 사용되는 목표 주파수 응답의 크기 특성은 다음과 같은 저역 통과 필터이다. ω_p 는 통과대역 절단 주파수이고, ω_s 는 정지대역 절단 주파수이다. 같은 주파수 특성과 같은 차수를 갖는 부동소수점 필터를 Matlab으로 설계하여 비교하였다. 이 예는 참고문헌 [11] 에서 사용된 예를 사용하였다. 필터의 차수는 25이고 통과대역과 정지대역의 절단 주파수는 각각 ω_p =0.15, ω_s =0.25 cycle/sample이다. 먼저 Matlab에서 이러한 규격으로 equiripple FIR 필터를 설계하였다. 통과대역 ripple δ_p 와 정지대역 ripple δ_s 는 모두 0.005(-46dB)이다. 주파수 응답의 크기는 그림 2 의 “Equiripple” 항목과 같다. 그림 2(a) 에서는 전체 대역의 주파수 응답을 보여주며, 그림 2(b) 에서는 통과대역에서의 주파수 응답 특성을 보인다. 제안된 방법으로 주어진 규격의 부호자릿수 계수를 갖는 필터를 설계하였다. 첫 번째로 총 26개의 자릿수를 사용하여 필터를 설계하였다. ( 그림 2 의 “Proposed-26”) 이는 필터 탭(tap)당 평균 두 번의 덧셈만으로 필터링 연산을 수행할 수 있음을 의미한다. 정지대역 감쇄는 약 43.0dB로 부동 소수점 계수의 equiripple 필터보다 3dB정도 적다. 두 번째로 설계된 필터는 덧셈 횟수를 총 20번 즉, 탭당 1.54번만 요구한다( 그림 2 의 “Proposed-20”). 대신 정지대역 감쇄는 약 41.8dB로 equiripple 필터보다 4.2dB 부족하다. 연산 속도의 비교를 위해 하나의 덧셈기를 사용하는 하드웨어를 가정하였다. 덧셈기의 최대 동작 주파수를 f_A 라 하고 26 자릿수와 20 자릿수를 갖는 필터를 각각 F26, F20이라하면 이들의 최대 동작 주파수는 각각 f_A /26과 f_A /20이다. 단, 파이프라인 기법은 사용하지 않는다고 가정한다. F20은 F26보다 약 1.2dB 성능이 떨어지지만 필터링 연산 속도는 30% ( f_A /20÷ f_A /26≃1.3) 정도 빨라지므로 F20는 고속 필터링이 요구되는 응용에서 좋은 trade-off가 될 수 있다. 표 1 에는 각각의 필터의 계수를 나타낸다. 이 설계 예는 [12] 에서 언급된 저역 통과 필터 규격을 사용하였다. 필터의 차수는 35이고 통과대역과 정지대역의 절단 주파수는 각각 ω_p =0.025, ω_s =0.0725 cycle/sample이다. 먼저 Matlab에서 이러한 규격으로 equiripple FIR 필터를 설계하였다. 통과대역 ripple δ_p 와 정지대역 ripple δ_s 는 모두 -38.1dB이다. 주파수 응답의 크기는 그림 3(a) 의 “Equiripple” 항목과 같다. 제안된 방법으로 주어진 규격의 부호자릿수 계수를 갖는 필터를 설계하였다. 첫 번째로 총 36개의 자릿수를 사용하여 필터를 설계하였다 ( 그림 3(a) 의 “Proposed-36”). 이는 필터 탭 당 평균 두 번의 덧셈만으로 필텅링 연산을 수행할 수 있음을 의미한다. 정지대역 감쇄는 약 37.0dB로 부동 소수점 계수의 equiripple 필터보다 1.1dB정도 적다. 두 번째로 설계된 필터는 덧셈 횟수를 총 31번 즉, 탭 당 1.72번만 요구한다 ( 그림 3 의 “Proposed-31”). 대신 정지대역 감쇄는 약 36.6dB로 equiripple 필터보다 1.5dB 부족하다. 36개의 자릿수를 갖는 계수보다 약 0.4dB 성능이 떨어지지만 필터링 연산 속도는 16% 정도 빨라지므로 31개의 자릿수를 갖는 계수의 필터는 고속 필터링이 요구되는 응용에서 좋은 trade-off가 될 수 있다. 표 2 에는 각각의 필터의 계수를 나타낸다. 본 논문에서는 무곱셈 FIR 필터 구현을 위해 압축센싱 기법에 기반을 둔 CSD 형식의 계수 설계 알고리듬을 제안하였다. 탐욕적(greedy)인 제안된 알고리듬은 주어진 주파수 응답특성을 잔차신호의 초기값으로 설정한 후 매 반복단계마다 잔차 신호에 가장 큰 기여를 하는 atom을 찾고, 그 계수로부터 가장 큰 크기의 부호 자릿수를 결정하여 FIR 필터의 계수에 추가한다. 설계 예에 의하면 약간의 성능 저하의 비용으로 탭 당 두 번 이하의 덧셈으로 FIR 필터링을 수행할 수 있음을 알 수 있다. 특히 설계 예 2에서는 1.5dB의 비용으로 탭 당 평균 1.72번의 덧셈으로 필터를 구현할 수 있었다. 제안된 알고리듬은 광대역 신호의 초고속 무곱셈 FIR 필터 구현에 필요한 CSD 계수 설계에 적용될 수 있다. 김시현(Seehyun Kim) 1996년 서울대학교 제어계측공학과 박사 ~ 1997년 University of California, Berkeley, Postdoctorate researcher ~ 2001년 LG전자 책임연구원 ~ 2010년 ㈜넥실리온 연구소장 ~ 현재 수원대학교 정보통신공학과 조교수 ※관심분야 : 신호처리, 디지털통신, 영상신호처리, SoC