무곱셈 구현을 위한 FIR 필터 계수의 압축 센싱

doi:10.6109/jkiice.2014.18.10.2375

OA학술지
Journal of the Korea Institute of Information and Communication Engineering

무곱셈 구현을 위한 FIR 필터 계수의 압축 센싱 Compressive Sensing of the FIR Filter Coefficients for Multiplierless Implementation

DOI : 10.6109/jkiice.2014.18.10.2375
Publish: Journal of the Korea Institute of Information and Communication Engineering Volume 18, Issue10, p2375~2381, 31 Oct 2014

ABSTRACT

무곱셈 구현을 위한 FIR 필터 계수의 압축 센싱

In case the coefficient set of an FIR filter is represented in the canonic signed digit (CSD) format with a few nonzero digits, it is possible to implement high data rate digital filters with low hardware cost. Designing an FIR filter with CSD format coefficients, whose number of nonzero signed digits is minimal, is equivalent to finding sparse nonzero signed digits in the coefficient set of the filter which satisfies the target frequency response with minimal maximum error. In this paper, a compressive sensing based CSD coefficient FIR filter design algorithm is proposed for multiplierless and high speed implementation. Design examples show that multiplierless FIR filters can be designed using less than two additions per tap on average with approximate frequency response to the target, which are suitable for high speed filtering applications.

KEYWORD

FIR 필터 설계 , CSD(canonic signed digit) , 압축센싱 , 탐욕 알고리듬

본문

Collapse all

I. 서 론

고속 디지털 필터는 광대역 통신, 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 필터 구현 성능을 보인다.

II. 무곱셈 디지털 필터 설계 알고리듬

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, 2h_M−1, ..., 2h₀)^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에 가까운 값을 가지게 된다.

[그림 1.] 압축센싱 기반 부호 자릿수 계수 FIR 필터 설계 알고리듬

반복과정은 크게 선택, 추가, 갱신의 세 단계로 구성된다. 첫 번째 단계에서는 하나의 부호자릿수를 추가할 계수 즉, 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를 사용하여 잔차를 갱신하고, 반복과정을 다시 수행한다.

III. 필터 설계 예

이 장에서는 두 가지의 설계 예를 이용하여 제안된 알고리듬이 낮은 구현 복잡도를 갖는 부호자릿수 FIR 필터의 설계에 활용될 수 있음을 보인다. 모든 예에서 사용되는 목표 주파수 응답의 크기 특성은 다음과 같은 저역 통과 필터이다.

ω_p는 통과대역 절단 주파수이고, ω_s는 정지대역 절단 주파수이다. 같은 주파수 특성과 같은 차수를 갖는 부동소수점 필터를 Matlab으로 설계하여 비교하였다.

3.1. 설계 예 1

이 예는 참고문헌 [11]에서 사용된 예를 사용하였다. 필터의 차수는 25이고 통과대역과 정지대역의 절단 주파수는 각각 ω_p=0.15, ω_s=0.25 cycle/sample이다. 먼저 Matlab에서 이러한 규격으로 equiripple FIR 필터를 설계하였다. 통과대역 ripple δ_p와 정지대역 ripple δ_s는 모두 0.005(-46dB)이다. 주파수 응답의 크기는 그림 2의 “Equiripple” 항목과 같다.

[그림 2.] 예제 1의 25-탭 FIR 필터의 주파수 응답 (a) 전 대역 (b) 통과대역

그림 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에는 각각의 필터의 계수를 나타낸다.

[표 1.] 설계 예 1의 부호자릿수 계수

설계 예 1의 부호자릿수 계수

3.2. 설계 예 2

이 설계 예는 [12]에서 언급된 저역 통과 필터 규격을 사용하였다. 필터의 차수는 35이고 통과대역과 정지대역의 절단 주파수는 각각 ω_p=0.025, ω_s=0.0725 cycle/sample이다. 먼저 Matlab에서 이러한 규격으로 equiripple FIR 필터를 설계하였다. 통과대역 ripple δ_p와 정지대역 ripple δ_s는 모두 -38.1dB이다. 주파수 응답의 크기는 그림 3(a)의 “Equiripple” 항목과 같다. 제안된 방법으로 주어진 규격의 부호자릿수 계수를 갖는 필터를 설계하였다.

[그림 3.] 예제 2의 35-탭 FIR 필터의 주파수 응답 (a) 전 대역 (b) 통과대역

첫 번째로 총 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에는 각각의 필터의 계수를 나타낸다.

[표 2.] 설계 예 2의 부호자릿수 계수

설계 예 2의 부호자릿수 계수

IV. 결 론

본 논문에서는 무곱셈 FIR 필터 구현을 위해 압축센싱 기법에 기반을 둔 CSD 형식의 계수 설계 알고리듬을 제안하였다. 탐욕적(greedy)인 제안된 알고리듬은 주어진 주파수 응답특성을 잔차신호의 초기값으로 설정한 후 매 반복단계마다 잔차 신호에 가장 큰 기여를 하는 atom을 찾고, 그 계수로부터 가장 큰 크기의 부호 자릿수를 결정하여 FIR 필터의 계수에 추가한다. 설계 예에 의하면 약간의 성능 저하의 비용으로 탭 당 두 번 이하의 덧셈으로 FIR 필터링을 수행할 수 있음을 알 수 있다. 특히 설계 예 2에서는 1.5dB의 비용으로 탭 당 평균 1.72번의 덧셈으로 필터를 구현할 수 있었다. 제안된 알고리듬은 광대역 신호의 초고속 무곱셈 FIR 필터 구현에 필요한 CSD 계수 설계에 적용될 수 있다.

참고문헌

1. Hewlitt R., Swartzlantler E. 2000 “Canonical signed digit representation for FIR digital filters,” [Proc. IEEE Workshop on Signal Processing Systems] P.416-426
2. Hwang K. 1979 Computer Arithmetic, Principles, Architecture, and Design
3. Candes E., Romberg J., Tao T. 2006 “ Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” [IEEE Trans. Information Theory] Vol.52 P.489-509
4. Donoho D. 2006 “Compressed sensing,” [IEEE Trans., Information Theory] Vol.52 P.1289-1306
5. Candes E., Tao T. 2005 “Decoding by linear programming,” [IEEE Trans. Information Theory] Vol.51 P.4203-4215
6. Mallat S., Zhang Z. 1993 “Matching pursuit with time-frequency dictionalries,” [IEEE Trans. Signal Processing] Vol.41 P.3397-3415
7. Tropp J. A. 2004 “Greed is good: algorithmic results for sparse approximation,” [IEEE Trans. Information Theory] Vol.50 P.2231-2242
8. Donoho D., Tsaig Y., Drori I., Starck J. 2012 “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit,” [IEEE Trans. Information Theory] Vol.58 P.1094-1121
9. Needell D., Tropp J. A. 2009 “CoSaMP: Iterative signal recovery from incomplete and inaccurate samples,” [Appl. Comput. Harmon.Anal.] Vol.26 P.301-321
10. Wei D. 2009 “Non-convex optimization for the design of sparse FIR filters,” [Proc. IEEE Signal Processing Workshop] P.117-120
11. Samueli H. 1989 “An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients,” [IEEE Trans. Circuits and Systems] Vol.36 P.1044-1047
12. Takahashi N., Suyama K. 2010 “Design of CSD coefficient FIR filters based on branch and bound method,” [Proc. International Symposium on Communications and Information Technologgies] P.575-578