Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

Finite Wordlength Linear-Phase FIR Filter Design Using Babai's Algorithm

Andraz Bozicek

Pages - 146 - 152 | Revised - 15-11-2012 | Published - 31-12-2012

Published in Signal Processing: An International Journal (SPIJ)

MORE INFORMATION

KEYWORDS

FIR filter design, Finite Wordlength Coefficients, Babai's Algorithm, LLL Algorithm, Closest Vector Problem

ABSTRACT

Optimal finite linear-phase impulse response (FIR) filters are most often designed using the Remez algorithm, which computes so-called infinite precision filter coefficients. In many practical applications, it is necessary to represent these coefficients by a finite number of bits. The problem of finite wordlength linear-phase filters is not as trivial as it would seem. The simple rounding of coefficients computed by the Remez algorithm gives us a suboptimal filter. Optimal finite wordlength linear-phase FIR filters are usually designed using integer linear programming, which takes a lot of time to compute the coefficients. In this paper, we introduce a new approach to the design of finite wordlength FIR filters using very fast Babai's algorithm. Babai's algorithm solves the closest vector problem, and it uses the basis reduced by the LLL algorithm as an input. We have used algorithms which solve the problem in the L2 norm and then added heuristics that improve the results relative to the L? norm. The design method with Babai's algorithm and heuristics has been tested on filters with different sets of frequency-domain specifications.

1 | Google Scholar |

2 | CiteSeerX |

3 | Scribd |

4 | SlideShare |

5 | PdfSR |

1 | J. G. Proakis and D. G. Manolakis, Introduction to Digital Signal Processing., pp. 614-726. |

2 | D. M. Kodek, "Design of optimal finite wordlength FIR digital filters using integer programming techniques," IEEE Transactions on Acoustics, Speech and Signal Processing,vol. 38, no. 3, pp. 304- 308, junij 1980. |

3 | D. M. Kodek, "Performance Limit of Finite Wordlength FIR Digital Filters," IEEE Transactions on Signal Processing, vol. 53, no. 7, pp. 2462- 2469, julij 2005. |

4 | D. M. Kodek, "LLL Algorithm and the Optimal Finite Wordlength FIR Design," IEEE Transactions on Signal Processing, vol. 60, no. 3, pp. 1493-1498 , March 2012. |

5 | N. Brisebarre and S. Chevillard, "Efficient polynomial L-approximations," Computer Arithmetic, 2007. ARITH '07. 18th IEEE Symposium on, pp. 169-176, junij 2007. |

6 | A. K. Lenstra, H. W. Lenstra, and L. Lovász, "Factoring polynomials with rational coefficients," Mathematische Annalen, vol. 264, no. 4, pp. 515-634, december 1982. |

7 | N. P. Smart, The algorithmic resolution of diophantine equations.: Cambridge University Press, 1998, pp. 59-76. |

8 | L. Babai, "On Lovász' Lattice Reduction and the Nearest Lattice Point Problem," in Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science (STACS'85), London, 1985, pp. 13-20. |

9 | E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, "Closest point search in lattices," IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2201-2214, August 2002. |

10 | A. D. Murugan, H. El Gamal, M. O. Damen, and G. Caire, "A unified framework for tree search decoding: rediscovering the sequential decoder," IEEE Transactions on Information Theory, vol. 52, no. 3, pp. 933-953 , March 2006. |

11 | J. W. Adams and J. L. Sullivan, "Peak-constrained least-squares optimization," IEEE Transactions on Signal Processing, vol. 46, no. 2, pp. 306-321, February 1998. |

12 | I. W. Selesnick, M. Lang, and C. S. Burrus, "Constrained least square design of FIR filters without specified transition bands," IEEE Transactions on Signal Processing, vol. 44, no. 8,pp. 1879-1892, August 1996. |

Dr. Andraz Bozicek

Faculty of Computer and Information Science University of Ljubljana - Slovenia

andraz.bozicek@fri.uni-lj.si