Efficient VLSI array processing structures for adaptive quadratic digital filters

In this paper we introduce a class of efficient architectures for adaptive quadratic digital filters. These architectures are based on the LMS algorithm and use the rank compressed lower-upper (LU) triangular deomposition method. These architectures exhibit high parallelism as well as great modularity and regularity. We also consider affiliated VLSI array processing structures and compare these in terms of hardware cost and data throughput delay. For comparison purposes, the distributed arithmetic structures of adaptive quadratic filters are also included in the paper. Finally, the convergence performance of the adaptive quadratic filters is tested via benchmark simulation examples.This work was supported by National Science Foundation Grant ECS-8601307.     

New class of time-varying filters

A new class of time-varying lowpass and highpass filters is described in which the stopband attenuation is obtained by outphasing in a quadrature-modulation arrangement, the undesired associated frequency translation or inversion being cancelled by a suitably chosen second step of quadrature demodulation or both; bandpass and bandstop filters can be obtained as combinations of lowpass and highpass filters.     

Laguerre-domain adaptive filters

Using a tapped-delay-line as an adaptive fitter, the complexity of the filter increases with increasing correlation length of input and reference signal. The author seeks simple adaptive filter structures such that for a long correlation length only a minor complexity of the filter is needed. He considers adaptive mechanisms governed by an exponentially weighted squared-error criterion. Laguerre-domain adaptive filters are introduced, which lead to a tapped IIR-filter line. These filters contain a discount factor as a free variable, which makes it possible to set the memory and the number of adaptive coefficients independently. Convergence properties of the proposed adaptive filters are discussed     

Factorability of lossless time-varying filters and filter banks

We study the factorability of linear time-varying (LTV) lossless filters and filter banks. We give a complete characterization of all, degree-one lossless LTV systems and show that all degree-one lossless systems can be decomposed into a time-dependent unitary matrix followed by a lossless dyadic-based LTV system. The lossless dyadic-based system has several properties that make it useful in the factorization of lossless LTV systems. The traditional lapped orthogonal transform (LOT) is also generalized to the LTV case. We identify two classes of TVLOTs, namely, the invertible inverse lossless (IIL) and noninvertible inverse lossless (NIL) TVLOTs. The minimum number of delays required to implement a TVLOT is shown to be a nondecreasing function of time, and it is a constant if and only if the TVLOT is IIL. We also show that all IIL TVLOTs can be factorized uniquely into the proposed degree-one lossless building block. The factorization is minimal in terms of the delay elements. For NIL TVLOTs, there are factorable and unfactorable examples. Both necessary and sufficient conditions for the factorability of lossless LTV systems are given. We also introduce the concept of strong eternal reachability (SER) and strong eternal observability (SEO) of LTV systems. The SER and SEO of an implementation of LTV systems imply the minimality of the structure. Using these concepts, we are able to show that the cascade structure for a factorable IIL LTV system is minimal. That implies that if a IIL LTV system is factorable in terms of the lossless dyadic-based building blocks, the factorization is minimal in terms of delays as well as the number of building blocks. We also prove the BIBO stability of the LTV normalized IIR lattice     

On cyclically time-varying autoregressive digital filters

A first-order autoregressive filter is altered by changing the constant gain to two or more gains that cyclically alternate in time. The advantages of this system are shown, and the relation to linear autoregressive moving average difference equations of higher order is derived.     

On a class of linear time-varying filters

This paper is devoted to a special class of linear time-varying filters, members of which are commonly employed in practice. It is shown that some of these filters share a number of desirable properties with linear stationary systems, the most important of which is the preservation of wide sense stationarity of stochastic inputs. An application to the problem of transmitting a continuous signal over a sampled data channel is included. Some results coincide with those for a multichannel system with simultaneous optimum stationary presampling and postsampling filters.     

Multiplication-free adaptive digital filters

The authors update delta modulation digital filter weights using the LMS (least-mean-squares) and the SIGN algorithms to realize an adaptive digital filter without multiplication operations. It is shown that using the SIGN algorithm results in an adaptive filter that can be implemented using the simple up/down counting operations. Learning curves demonstrating convergence properties of the algorithms for a system identification problem are presented     

Convergence of adaptive lattice filters

Some results are presented on the convergence rate of lattice filters when adaptive algorithms are employed for estimating their reflection coefficients. It is shown that, unlike tapped-delay-line filters, adaptive lattices are not affected by ill-conditioned data.     

Unbiased and stable leakage-based adaptive filters

The paper develops a leakage-based adaptive algorithm, referred to as circular-leaky, which in addition to solving the drift problem of the classical least mean squares (LMS) adaptive algorithm, it also avoids the bias problem that is created by the standard leaky LMS solution. These two desirable properties of unbiased and bounded estimates are guaranteed by circular-leaky at essentially the same computational cost as LMS. The derivation in the paper relies on results from averaging theory and from Lyapunov stability theory, and the analysis shows that the above properties hold not only in infinite-precision but also in finite-precision arithmetic. The paper further extends the results to a so-called switching-σ algorithm, which is a leakage-based solution used in adaptive control     

Exponential asymptotic stability of time-varying inverse predictionerror filters

It is a classical result of linear prediction theory that as long as the minimum prediction error variance is nonzero, the transfer function of the optimum linear prediction error filter for a stationary process is minimum phase, and therefore, its inverse is exponentially stable. Here, extensions of this result to the case of nonstationary processes are investigated. In that context, the filter becomes time-varying, and the concept of “transfer function” ceases to make sense. Nevertheless, we prove that under mild condition on the input process, the inverse system remains exponentially stable. We also consider filters obtained in a deterministic framework and show that if the time-varying coefficients of the predictor are computed by means of the recursive weighted least squares algorithm, then its inverse remains exponentially stable under a similar set of conditions     

Partial update and sparse adaptive filters

There has been increasing research interest in developing adaptive filters with partial update (PU) and adaptive filters for sparse impulse responses. On the basis of maximum a posteriori (MAP) estimation, new adaptive filters are developed by determining the update when a new set of training data is received. The MAP estimation formulation permits the study of a number of different prior distributions which naturally incorporate the sparse property of the filter coefficients. First, the Gaussian prior is studied, and a new adaptive filter with PU is proposed. A theoretical basis for an existing PU adaptive filter is also studied. Then new adaptive filters that directly exploit the sparsity of the filter are developed by using the scale mixture Gaussian distribution as the prior. Two new algorithms based on the Student's-t and power-exponential distributions are presented. The minorisation-maximisation algorithm is employed as an optimisation tool. Simulation results show that the learning performance of the proposed algorithms is better than or similar to that of some recently published algorithms     

Efficient approximation of Gaussian filters

This article presents improvements to the efficient approximation of Gaussian filters by sequentially applying uniform box filters. For 1-D filters, a simple and nearly optimal fit criterion for the length S of the box filters to the approximated Gaussian is given. For 2-D filters, a new method is introduced to improve the circular symmetry and the lowpass properties of the approximation without increasing the computational complexity. Finally, a multirate implementation for large Gaussian filters is presented that requires significantly fewer floating-point operations than the standard technique     

Exploiting sparsity in adaptive filters

This paper studies a class of algorithms called natural gradient (NG) algorithms. The least mean square (LMS) algorithm is derived within the NG framework, and a family of LMS variants that exploit sparsity is derived. This procedure is repeated for other algorithm families, such as the constant modulus algorithm (CMA) and decision-directed (DD) LMS. Mean squared error analysis, stability analysis, and convergence analysis of the family of sparse LMS algorithms are provided, and it is shown that if the system is sparse, then the new algorithms will converge faster for a given total asymptotic MSE. Simulations are provided to confirm the analysis. In addition, Bayesian priors matching the statistics of a database of real channels are given, and algorithms are derived that exploit these priors. Simulations using measured channels are used to show a realistic application of these algorithms     

Cascade lattice IIR adaptive filters

The feedback lattice filter forms, including the two-multiplier form and the normalized form, are examined with respect to their relationships to the feedback direct form filter. Specifically, the transformation matrix between the lattice forms and the direct form is derived; parameter and state relationships between the lattice forms and the direct form are therefore obtained. An IIR filter structure-the cascade lattice IIR structure-is constructed. Based on this structure, three IIR adaptive filtering algorithms in the two-multiplier form can then be developed following the gradient approach, the Steiglitz-McBride approach and the hyperstability approach. Convergence of these algorithms is theoretically analyzed using either the ODE approach or the hyperstability theorem. These algorithms are then simplified into forms computationally as efficient as their corresponding direct form algorithms. Relationships of the simplified algorithms to the direct form algorithms are also studied, which disclose a consistency in algorithm structure regardless of the filter form. Three normalized lattice algorithms can also be derived from the two-multiplier lattice algorithms. Experimental results show much improved performance of the normalized lattice algorithms over the two-multiplier lattice algorithms and the direct form algorithms     

Lattice filters for adaptive processing

This paper presents a tutorial review of lattice structures and their use for adaptive prediction of time series. Lattice filters associated with stationary covariance sequences and their properties are discussed. The least squares prediction problem is defined for the given data case, and it is shown that many of the currently used lattice methods are actually approximations to the stationary least squares solution. The recently developed class of adaptive least squares lattice algorithms are described in detail, both in their unnormalized and normalized forms. The performance of the adaptive least squares lattice algorithm is compared to that of some gradient adaptive methods. Lattice forms for ARMA processes, for joint process estimation, and for the sliding-window covariance case are presented. The use of lattice structures for efficient factorization of covariance matrices and solution of Toeplitz sets of equations is briefly discussed.     

Extended RLS lattice adaptive filters

This paper solves the problem of developing exact fast weighted RLS lattice adaptive filters for input signals induced by general orthonormal filter models. The resulting algorithm can be viewed as a counterpart of the extended fast fixed-order RLS adaptive filters previously derived.     

Envelope-constrained filters: adaptive algorithms

We consider an envelope-constrained (EC) optimal filter design problem involving a quadratic cost function and a number of linear inequality constraints. Using the duality theory and the space transformation function, the optimal solution of the dual problem can be computed by finding the limiting point of an ordinary differential equation given in terms of the gradient flow. An iterative algorithm is developed via discretizing the differential equation. From the primal-dual relationship, the corresponding sequence of approximate solutions in the original EC filtering problem is obtained. Based on these results, an adaptive algorithm is constructed for solving the stochastic EC filtering problem in which the input signal is corrupted by an additive random noise. For illustration,a practical example is solved for both noise-free and noisy cases     

Efficient computation of full Lucas sequences

Recently, Yen and Laih (see IEE Poc. Comput. Digit. Tech., vol. 142, no. 2, p. 165-9, 1995) proposed an algorithm to compute LUC digital signatures quickly. This signature is based on a special type of Lucas sequence V_k. The authors generalise their method to any type of Lucas sequence, and extend it to the `sister' Lucas sequence, U_k . As an application, the order of an elliptic curve over GF(2^m) is computed quickly     

Efficient computation of local geometric moments

Local moments have attracted attention as local features in applications such as edge detection and texture segmentation. The main reason for this is that they are inherently integral-based features, so that their use reduces the effect of uncorrelated noise. The computation of local moments, when viewed as a neighborhood operation, can be interpreted as a convolution of the image with a set of masks. Nevertheless, moments computed inside overlapping windows are not independent and convolution does not take this fact into account. By introducing a matrix formulation and the concept of accumulation moments, this paper presents an algorithm which is computationally much more efficient than convolving and yet as simple.