2
$\begingroup$

It seems to me that this is a difficult mathematical problem where research is still carried on: Is there an efficient way to find fixed-point coefficients whose zeros are closest to those calculated from the given floating-point coefficients?

$\endgroup$
  • 2
    $\begingroup$ uh, that problem seems as old as DSP; I'd assume it's probably well-researched and available in literature. I'm no filter design expert, though, so I don't have great references. $\endgroup$ – Marcus Müller Feb 16 '17 at 21:18
  • $\begingroup$ @MarcusMüller, the OP can just break out a good textbook like O&S. doesn't look real cheap, but maybe the OP can find one used because EEs taking this course in the 80s or 90s, some of them may have this book in their bookshelf collecting dust. we all die eventually and i hope some appreciative EE gets my copy. and there are libraries. look up "the effect of coefficient quantization". $\endgroup$ – robert bristow-johnson Feb 17 '17 at 4:48
  • $\begingroup$ Sebastian, probably the first thing to consider is the Direct I or Direct II forms and stick to 2nd-order (biquad). look at the numerator and denominator of $H(z)$ separately and figure out where the poles and zeros are, as a function of the coefficients. $\endgroup$ – robert bristow-johnson Feb 17 '17 at 4:51
  • $\begingroup$ @robert bristow-johnson It seems that in O&S the subject how to round coefficients with respect to their zeros is not covered. [link This article] (link.springer.com/article/10.1007/s10958-012-0842-z) is probably nearer to the subject I'm investigating. $\endgroup$ – Sebastian Gutzwiller Feb 17 '17 at 7:11
  • $\begingroup$ the effect of poles on the response of an LTI system is, of course, different than the effect of zeros. but the effect of quantization of coefficients in the numerator of a transfer function is similar the same effect that quantization of denominator coefficients have on the pole locations (there are only two degrees of freedom in the denominator and three degrees of freedom in the numerator). and with your transfer function factored down to biquads, that effect is as easy as solving the quadratic equation. $\endgroup$ – robert bristow-johnson Feb 17 '17 at 8:36
2
$\begingroup$

It is definitely a difficult mathematical problem (integer programming), but I don't see much research going on in the DSP community. I do not know about the maths community. There were some important papers in the early 1980's on the optimum design of FIR filters with quantized coefficients:

  • D. M. Kodek, "Design of Optimal Finite Wordlength FIR Digital Filters Using Integer Programming Techniques," IEEE Trans. ASSP 28, 304-308 (1980).
  • D. M. Kodek and K. Steiglitz, "Comparison of Optimal and Local Search Methods for Designing Finite Worldlength FIR Digital Filters," IEEE Trans. Circuits Systems 28, 28-32 (1981).

But as far as I know none of the published methods developed into a standard design method for filters with quantized coefficients, unlike for the design of filters with infinite precision coefficients (e.g., Parks McClellan).

I think there are two reasons for that: first, optimum methods use integer programming techniques, which are computationally inefficient, and which will only compute a local optimum that can be arbitrarily bad. These problems become aggravated for large filter lengths. Second, there is not so much need anymore for the optimum design of filters with quantized coefficients. This has to do with the fact that more and more systems are implemented in floating point, and - if fixed-point is needed - the word length is usually large enough such that suboptimal heuristic design methods are sufficient. Such methods iteratively design the filter assuming infinite precision, quantize the coefficients, check the filter properties and, if necessary, adapt the specs (including the filter length, error weighting, etc.), re-design the filter according to the new specifications, and so on, until the requirements are met.

For IIR filters, the optimum design for quantized filter coefficients is even more difficult than for FIR filters due to the rational transfer function. I haven't seen any useful optimization methods in the DSP literature, only heuristic methods such as the one described above. Note that different filter structures will result in different possible pole locations in the complex plane after coefficient quantization. The possible pole locations for the direct-form structure are relatively sparse at small pole angles, i.e., for low cut-off frequencies, whereas the pole locations of the coupled-form structure are evenly distributed on a rectangular grid.

$\endgroup$
  • $\begingroup$ Could the reference I gave in the comment to the question be a starting point to investigate for such an optimizer or am I completely wrong? $\endgroup$ – Sebastian Gutzwiller Feb 17 '17 at 11:28
  • $\begingroup$ @SebastianGutzwiller Sure it could. It's probably rather theoretical and not directly applied to the filter design problem, but obviously a FIR transfer function is a polynomial. I'm not sure, however, if the paper deals with any optimization strategies or if it just describes the change in zero locations due to coefficient quantization. If you're looking for efficient strategies, I guess resorting to heuristic methods is a good starting point. $\endgroup$ – Matt L. Feb 17 '17 at 11:34
  • $\begingroup$ Recently, optimization methods based on a hierarchy of semi-definite programming relaxations have been shown to handle "rational fraction functions" under polynomial constraints. The latter may treat discrete variables. Do you have knowledge on their applications to IIR design with finite-word-length? $\endgroup$ – Laurent Duval Jul 31 at 8:09
  • 1
    $\begingroup$ @LaurentDuval: Thanks for pointing that out; I haven't heard of those methods yet, so I don't know if they are applicable to IIR design with integer coefficients. $\endgroup$ – Matt L. Aug 1 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.