Logarithmic number system (LNS) is an attractive alternative to realize finite-length impulse response filters because of multiplication in the linear domain being only addition in the logarithmic domain. In the literature, linear coefficients are directly replaced by the logarithmic equivalent. In this paper, an approach to directly optimize the finite word length coefficients in the LNS domain is proposed. This branch and bound algorithm is implemented based on LNS integers and several different branching strategies are proposed and evaluated. Optimal coefficients in the minimax sense are obtained and compared with the traditional finite word length representation in the linear domain as well as using rounding. Results show that the proposed method naturally provides smaller approximation error compared to rounding. Furthermore, they provide insights into finite word length properties of FIR filters coefficients in the LNS domain and show that LNS FIR filters typically provide a better approximation error compared to a standard FIR filter. 1. Introduction Finite-length impulse response (FIR) filters constitute a class of digital filters commonly used for their stability properties and the ability to obtain a linear phase response. The transfer function of an th-order FIR filter is where are the impulse response coefficients. The filter order and, therefore, the number of multiplications and additions for a straightforward realization grows approximately inversely proportional to the transition bandwidth of the magnitude response [1, 2]. As multiplications traditionally have a larger area complexity and power consumption compared to additions, much work has focused on reducing the number of multiplications in FIR filter realizations by using sparse filters or frequency response masking filters [3–5]. Work has also been done to reduce the complexity of each multiplication, for example, by introducing filter coefficients easily realizable using shifts, additions, and subtractions, sometimes referred to as multiplierless realizations [6–8]. Furthermore, the representation of data and coefficients affects both the switching activity and implementation complexity which, in turn, affects power consumption as well. Commonly, a fixed-point two’s complement number representation is used to represent data in DSP systems, but other number representations have also been investigated as an efficient way of data representation for such systems [9–11]. Among them is the logarithmic number system (LNS) [12], which over the past few decades has been studied as an
References
[1]
L. Wanhammar and H. Johansson, Digital Filters, Department of Electrical Engineering, Link？ping University, 2007.
[2]
S. K. Mitra, Digital Signal Processing, Tata McGrawHill, Santa Barbara, Calif, USA, 2006.
[3]
Y. C. Lim, “Frequency-response masking approach for the synthesis of sharp linear phase digital filters,” IEEE Transactions on Circuits and Systems, vol. 33, no. 4, pp. 357–364, 1986.
[4]
T. Saram？ki, “Finite impulse response filter design,” in Handbook for Digital Signal Processing, S. K. Mitra and J. Kaiser, Eds., pp. 155–277, John Wiley & Sons, New York, NY, USA, 1988.
[5]
T. Saram？ki, T. Neuvo, and S. K. Mitra, “Design of computationally efficient interpolated FIR filters,” IEEE Transactions on Circuits and Systems, vol. 35, no. 1, pp. 70–88, 1988.
[6]
H. Samueli, “An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients,” IEEE Transactions on Circuits and Systems, vol. 36, no. 7, pp. 1044–1047, 1989.
[7]
W. J. Oh and Y.-H. Lee, “Implementation of programmable multiplierless FIR filters with powers-of-two coefficients,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 42, no. 8, pp. 553–556, 1995.
[8]
O. Gustafsson, A. G. Dempster, K. Johansson, M. D. Macleod, and L. Wanhammar, “Simplified design of constant coefficient multipliers,” Circuits, Systems, and Signal Processing, vol. 25, no. 2, pp. 225–251, 2006.
[9]
P. E. Landman and J. M. Rabaey, “Architectural power analysis: the dual bit type method,” IEEE Transactions on Very Large Scale Integration Systems, vol. 3, no. 2, pp. 173–187, 1995.
[10]
T. Stouraitis and V. Paliouras, “Considering the alternatives in low-power design,” IEEE Circuits and Devices Magazine, vol. 17, no. 4, pp. 23–29, 2001.
[11]
K.-H. Chen and T.-D. Chiueh, “A low-power digit-based reconfigurable FIR filter,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 53, no. 8, pp. 617–621, 2006.
[12]
E. E. Swartzlander Jr. and A. G. Alexopoulos, “The sign/logarithm number system,” IEEE Transactions on Computers, vol. C-24, no. 12, pp. 1238–1242, 1975.
[13]
N. G. Kingsbury and P. J. W. Rayner, “Digital filtering using logarithmic arithmetic,” Electronics Letters, vol. 7, no. 2, pp. 56–58, 1971.
[14]
M. G. Arnold, T. A. Bailey, J. R. Cowles, and M. D. Winkel, “Applying features of IEEE 754 to sign/logarithm arithmetic,” IEEE Transactions on Computers, vol. 41, no. 8, pp. 1040–1050, 1992.
[15]
D. V. S. Chandra, “Error analysis of fir filters implemented using logarithmic arithmetic,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 45, no. 6, pp. 744–747, 1998.
[16]
M. Haselman, M. Beauchamp, A. Wood, S. Hauck, K. Underwood, and K. S. Hemmert, “A comparison of floating point and logarithmic number systems for FPGAs,” in Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '05), pp. 181–190, Napa, Calif, USA, April 2005.
[17]
P. Lee, “An FPGA prototype for a multiplierless FIR filter built using the logarithmic number system,” in Field-Programmable Logic and Applications, vol. 975, pp. 303–310, Springer, Berlin, Germany, 1995.
[18]
V. Paliouras and T. Stouraitis, “Logarithmic number system for low-power arithmetic,” in Integrated Circuit Design: Power and Timing Modeling, Optimization and Simulation, vol. 1918, pp. 285–294, Springer, Berlin, Germany, 2000.
[19]
V. Paliouras and T. Stouraitis, “Low-power properties of the logarithmic number system,” in Proceedings of the15th IEEE Symposium on Computer Arithmetic, pp. 229–236, June 2001.
[20]
A. He？mánek, Z. Pohl, and J. Kadlec, “FPGA implementation of the adaptive lattice filter,” in Field Programmable Logic and Application, vol. 2778 of Lecture Notes in Computer Science, pp. 1095–1098, Springer, Berlin, Germany, 2003.
[21]
C. Basetas, I. Kouretas, and V. Paliouras, “Low-power digital filtering based on the logarithmic number system,” in Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation, vol. 4644, pp. 546–555, Springer, Berlin, Germany, 2007.
[22]
Y. Sun and M. S. Kim, “A high-performance 8-tap FIR filter using logarithmic number system,” in Proceedings of the IEEE International Conference on Communications (ICC '11), pp. 1–5, Kyoto, Japan, June 2011.
[23]
I. Kouretas, C. Basetas, and V. Paliouras, “Low-power logarithmic number system addition/subtraction and their impact on digital filters,” IEEE Transactions on Computers, vol. 62, no. 11, pp. 2196–2209, 2013.
[24]
R. E. Morley Jr., G. L. Engel, T. J. Sullivan, and S. M. Natarajan, “VLSI based design of a battery-operated digital hearing aid,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '88), vol. 5, pp. 2512–2515, New York, NY, USA, April 1988.
[25]
J. R. Sacha and M. J. Irwin, “Number representations for reducing switched capacitance in subband coding,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '98), vol. 5, pp. 3125–3128, Seattle, Wash, USA, May 1998.
[26]
M. G. Arnold, “Reduced power consumption for MPEG decoding with LNS,” in Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, pp. 65–67, 2002.
[27]
J. H. Lang, C. A. Zukowski, R. O. LaMaire, and C. An, “Integrated-circuit logarithmic arithmetic units,” IEEE Transactions on Computers, vol. C-34, no. 5, pp. 475–483, 1985.
[28]
O. Vainio and Y. Neuvo, “Logarithmic arithmetic in FIR filters,” IEEE Transactions on Circuits and Systems, vol. 33, no. 8, pp. 826–828, 1986.
[29]
O. Vainio, “Biased logarithmic arithmetic in FIR filters,” Electronics Letters, vol. 41, no. 10, pp. 580–581, 2005.
[30]
K. Johansson, O. Gustafsson, and L. Wanhammar, “Implementation of elementary functions for logarithmic number systems,” IET Computers and Digital Techniques, vol. 2, no. 4, pp. 295–304, 2008.
[31]
H. A. Taha, Operations Research—An Introduction, Pearson Prentice Hall, 8th edition, 2007.
[32]
L. R. Rabiner, “Linear program design of finite impulse response FIR digital filters,” IEEE Transactions on Audio and Electroacoustics, vol. 20, no. 4, pp. 280–288, 1972.
[33]
D. M. Kodek, “Design of optimal finite wordlength FIR digital filters using integer programming techniques,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 28, no. 3, pp. 304–308, 1980.
