Finite impulse response (FIR) digital filters are one of the most frequently used functions in digital signal processing. In recent digital signal processing systems, FIR filters are implemented as dedicated hardware blocks due to the demand of high throughput and low power consumption, but its hardware implementation still takes large area. In digital systems, multiplications are composed of many additions and the area overhead of digital FIR filter block can be reduced by finding an optimum adder graph which maximizes the sharing of partial sums between several multiplications.
In this thesis, a digital FIR filter synthesis algorithm is proposed to reduce the area overhead of FIR filter blocks. By considering multiple adder graphs for a filter coefficient, the proposed algorithm selects an adder graph that can be maximally sharable with the remaining filter coefficients, while previous dependence-graph algorithms consider only one adder graph when implementing a filter coefficient. In addition, an addition reordering technique is proposed to derive multiple adder graphs from a seed adder graph generated by using previous dependence-graph algorithms. Experimental results show that the proposed algorithm reduces the hardware cost of FIR filters by 22% and 3.4% on average compared to the Hartely and RAGn-hybrid algorithms.
This thesis also proposes a FIR filter optimization algorithm to reduce the hardware cost of FIR filter blocks. There are many feasible FIR filters which meet the given frequency response constraints and we can select a proper FIR filter which minimizes the hardware costs. Though the number of odd-positive unique values and the adder cost of each unique value affect to the hardware cost of FIR filter blocks, previous optimization algorithms considers only the adder cost of unique value. The proposed optimization algorithm considers both effect during optimization. By maximizing odd-positive value sharing between coefficients during optimization process, the proposed algorithm reduces the hardware cost of FIR filter blocks. Experimental results show that the proposed algorithm can reduce hardware cost of FIR filters up to 16% when compared to the previous optimization approaches.
FIR 필터는 디지탈 신호처리 시스템에서 가장 많이 사용되는 기능 중의 하나이다. 최근의 신호처리 시스템에서는 고속의 데이터 처리 능력이 요구됨에 따라서 FIR 필터를 전용 하드웨어 블럭을 이용해서 구현하는 경향이 높아지고 있다. 그러나 FIR 필터는 많은 수의 곱셈으로 이루어져 있기 때문에, 범용 곱셈기를 이용해서 하드웨어를 구현할 경우, 하나의 칩에 집적하지 못할 정도로 면적이 너무 커지는 문제가 있게 된다. 따라서 FIR 필터를 하드웨어로 구현할 때 면적을 최소화하는 것이 중요하며, FIR 필터의 계수 값들이 동작 중에 변경되지 않는 경우에는, 각 FIR 필터 계수들간의 상관 관계들을 이용한 전용 다중 곱셈 블럭을 이용하여 FIR 필터 구현에 필요한 면적을 줄일 수 있다. 필요한 면적을 줄이면서 디지털 FIR 필터를 구현하는 방법은 크게 두 가지로 나눌 수 있다.
첫 번째 방식은 FIR 필터의 계수 값들이 상수로 주어 졌을 때, FIR 필터 계수들로 이루어진 다중 곱셈(Multiple-Constant Multiplication) 블럭을 최소한의 덧셈기만을 이용해서 설계하는 것이다. 기존의 덧셈 의존 관계 그래프(Dependence-Graph)를 이용한 접근 방식에서는 하나의 곱셈 값을 구현할 때 생성되는 중간 값(Partial Sum)들이 아직 합성되지 않은 필터 계수들에 의해 다시 활용될 수 있는지의 여부를 따지지 않는다. 그러나 제안한 알고리즘에서는 한 개의 곱셈 값을 구현할 때 다양한 그래프를 후보 군으로 고려하고, 이들 중에서 전체 FIR 필터 계수를 합성하였을 때 필요한 덧셈의 수를 최소화 할 수 있는 그래프를 선택하게 된다. 이렇게 전체 FIR 필터 계수에 대한 영향을 고려함으로써 현재 가장 좋은 성능을 보이는 합성 알고리즘에 비해 성능 저하되는 경우 없이 평균적으로 3.4%의 성능 개선을 이루어 낼 수 있었다.
두 번째 방식은 주어진 주파수 응답 조건을 만족하면서 FIR 필터 블럭 구현에 필요한 면적을 최소화 할 수 있는 FIR 필터 계수 값들을 찾아내는 것이다. 상수 곱셈(Constant Multiplication)의 구현에 필요한 덧셈기의 수는 상수 값을 특정 number-system으로 표현했을 때 표현에 필요한 non-zero bit의 수에 비례한다. 따라서 기존의 알고리즘들에서는 필터 계수 최적화 과정에서 각 계수들의 non-zero bit의 수만을 최소화 하는 데 집중하고 있다. 그러나 여러 필터 계수들이 동일한 bit 패턴으로 이루어진 값을 공유할 수 있다면, 공통된 값을 한번만 만들고 난 뒤 서로 공유해서 사용함으로써 추가적으로 구현에 필요한 덧셈의 수를 줄일 수 있게 된다. 따라서 제안하는 FIR 필터 계수 최적화 알고리즘에서는 여러 필터 계수들이 동일한 홀수이면서 자연수인 값(odd-positive value)을 이용해서 표현될 수 있는지를 추가로 고려하고, 가능한 많은 필터 계수들이 동일한 홀수이면서 자연수인 값(odd-positive value)을 공유할 수 있도록 하고 있다. 제안하는 FIR 필터 최적화 알고리즘의 경우, 기존의 최적화 알고리즘과 동일한 성능을 보이거나 최대 16%의 성능 개선을 가져옴을 확인할 수 있었다.
