List of publications

Current projects:

Constrained Coefficient Polynomial Minimax Approximation

I have been working on this problem on and off since 1975. It began with the linear phase FIR digital filter application in which the filter coefficients had to be no longer than 8 bits. Rounding of the so called "infinite precision" coefficients to a finite number of bits b was (and often still is) the standard approach. The rounding, however, does not give the optimal finite wordlength coefficients and a much better set of coefficients almost always exists.

Finding the optimal b bit coefficients is difficult because it leads to a type of constrained coefficient approximation problem. This problem is almost certainly  NP-hard, although there seems to be no formal proof yet. In the beginning  it was often not clear if the problem is worth pursuing at all because the difference between the rounded and the optimal filter may be insignificant. This was an important question in the time when almost no one has tried to compute the optimal b bit coefficients for a filter of practical size. To answer it  a general purpose integer programming software was used to compute such filters in the following paper. The results have indicated that the optimal filter can indeed often be substantially better than the rounded one. This lead to the development of the first version of a program that uses special properties of the constrained coefficient minimax approximation problem. The program was much faster than the general purpose software and allowed experiments on a large number of design cases in a reasonable time. These experiments confirmed the original expectations: the optimal filters can be up to 30 dB better than the rounded ones as can be seen from the following example. Practical design of optimal finite wordlength filters requires an efficient algorithm, which is a problem from the field of combinatorial optimization. Development of such an algorithm is possible only if the theoretical aspects of the corresponding constrained coefficient polynomial minimax approximation problem are well understood. Most of the work was therefore directed into study of this problem. A theorem on the approximation error lower bound was derived and proved to be very useful in speeding up the algorithm. It is interesting to note that theoretical results are more general and hold for a large class of problems in which the filter design is just a special case. Some of these results are summarized in the following papers. 

Even though the problem is almost certainly NP-hard, this does not mean that it cannot be solved in a reasonable time even for more complex practical design cases where the number of coefficients is large. One of the somewhat surprising properties of the problem is that for each filter there exists the maximum number of non-zero coefficients. Or in other words, there exists a polynomial degree nmax (because of symmetry this corresponds to the filter length Nmax=2nmax) beyond which all coefficients are always equal to zero. The degree nmax depends on the number of bits b and on the frequency specifications but is in practice typically lower than 50. This fact makes the problem tractable in spite of being NP-hard.

Theoretical explanation for the existance of nmax and a simple method that gives an extimate for nmax are given in the paper

"Length limit of optimal finite wordlength FIR filters," D. M. Kodek, Digital Signal Processing, vol. 25, no. 5, pp. 1798-1805, Sep. 2013.

The most recent work focuses on the case in which the proportional scaling factor (also known as filter gain) is a variable and not a constant as in the previous research. This increases the complexity of the problem but also gives lower approximation error. The long-term goal is the development of a program that could be used for designing practical finite wordlength filters in a reasonable time. The current version of the program FWFIR is not far from this goal. Optimal linear phase FIR filters of length up to N=100 (corresponds to n=50 polynomial coefficients) and the number of bits b up to 14  can be designed in about a minute of computing time (on a 3 GHz Core i7). Note that higher number of bit b are rarely needed in practice.

An optimal algorithm for a class of flowshop scheduling problems

This class of scheduling problem appears, for example, in production cycle time minimization of a printed circuit board assembly line. It is NP-hard and notoriously difficult to solve. A novel approach which is based on the cycle time lower bound is used in the new algorithm. The lower bound of a subproblem in the branch-and-bound tree is easier to compute than solving the subproblem. It is no longer necessary to use the simplex algorithm which makes the algorithm very fast. Experiments have shown that it works well for problems with a large number of variables.

It is described in the following paper. Comments are welcome.

Non-standard window functions for short-time frequency analysis

Standard window functions (Hann, Hamming, etc.) are all symmetric. This makes them linear phase which is useful in many applications. It also makes them suboptimal from the pure amplitude response point of view. An asymmetric window should, in principle, work better for analysis of signals in which the phase information is not important. Speech is such a signal. Several types of non-standard asymmetric windows were developed and tested on two different speech recognition systems. The preliminary results are very promising and show a significant improvement in the robustness of both speech recognizers. The following papers describes some of the results. Comments are most welcome.

Back to home.