Fast algorithms for digital filtering: Theory and applications

This dissertation consists two parts. In the first part, a new type of least squares adaptive filtering algorithm, named the Euclidean Direction Search (EDS) algorithm has been derived and described from three different approaches. The Euclidean direction search method is a simplified version of the Direction Set (DS) method. It is equivalent to the Gauss-Seidel method in steady-state. It can also be viewed as a modified gradient-based method. For practical implementation, two sample-based EDS algorithms: EDS1 and EDS2 are proposed. By utilizing the time-shifting property of the input data and properly choosing the weights of the objective function, the sample-based EDS algorithms have an O(N) computational complexity for temporal FIR adaptive filtering. A mathematical analysis is also performed for the EDS method. A stability theorem shows that the algorithm converges to the true solution asymptotically. In addition, the convergence rate of the EDS method is superior to the steepest descent method and comparable to the RLS algorithm. Simulation results reveal that the proposed algorithms are very suitable for solving least-squares optimization problems, such as channel equalization, noise cancellation and linear prediction. Those algorithms feature computational simplicity, fast convergence, improved numerical stability and least-squares optimal solution.;The second part of the dissertation presents our contributions in the stability theory of digital filter design and implementation. We present new results about the elimination of limit cycles, when two's complement truncation (TCT) quantization is used in normal form digital filters. Normal form digital filters are attractive due to their desirable properties when implemented in finite wordlength arithmetic. These filters are free from all overflow limit cycles and quantization limit cycles when magnitude truncation (MT) is used. However, with a TCT quantizer, limit cycles can still exist. It is proven that special block structures can be designed that are free of TCT limit cycles. Subsequently, we study the stability of 2-D periodically shift varying (PSV) digital filters. The filters are formulated in the form of Fornasini Marchesini (FM) state-space model with periodic coefficients. As an alterative to considering the PSV filter as a block linear shift-invariant (LSI) system, the stability conditions are established directly from the 2-D PSV difference equations. Two of these results are sufficient conditions and one is a necessary condition. We also propose a 2-D LSI digital filter stability testing algorithm, which converts the stability test to a series of maximum eigenvalue problems. The stability of 2-D filters has received much attention during the last two decades and many stability theorems have been proposed. Most of these methods involve long recursive computations. The proposed algorithm iteratively reduces the gap between the sufficient condition and the necessary condition until the stability or instability of the filter is established.