In this paper, we discuss rank-one eigenvector updating schemes that are appropriate for tracking time-varying, narrow-band signals in noise. We show that significant reductions in computation are achieved by updating the eigenvalue decomposition (EVD) of a reduced rank version of the data covariance matrix, and that reduced rank updating yields a lower threshold breakdown than full rank updating. We also show that previously published eigenvector updating algorithms [1], [10], suffer from a linear build-up of roundoff error which becomes significant when large numbers of recursive updates are performed. We then show that exponential weighting together with pairwise Gram Schmidt partial orthogonalization at each update virtually eliminates the build-up of error making the rank-one update a useful numerical tool for recursive updating. Finally, we compare the frequency estimation performance of reduced rank weighted linear prediction and the LMS algorithm.

The development of VLSI has changed the important parameters in signal processing algorithms and structures. Technology developments are dictating new and different criteria for "efficient" realizations. In VLSI the number of computations performed per output sample is not enough to measure the "goodness" of a realization/implementation. This work is an attempt to quantify the important parameters in VLSI implementations for DSP problems and apply the theory to the task of digital filtering.

We present an optimization theoretic framework for spectral estimation. A theorem is given which provides a unification of several prevalent estimates and gives us the ability to systematically generate new classes of estimators. As one application a new optimal estimate was derived, tailored to smooth bandlimited spectra. A fast polynomial recursion exists for computing this estimate, and an extension makes it suitable for data consisting of sinusoids and noise. The high performance of this new estimate is indicative of the effectiveness of the proposed optimization techniques.

This work describes a multifactor algorithm for two-dimensional, noncyclic, convolution of two finite sequences. This type of processing occurs in such applications as image enhancement and in the processing of data from radar and sonar arrays.

This work compares block processing structures using as a figure of merit the product of the chip area needed to implement the structure in NMOS and the reciprocal of the word rate. It considers both distributed arithmetic schemes and conventional multiplier implementation of block filters and compares these structures with conventional filter structures. By fixing the output signal quality of the filters one is able to find the best block processing configurations in terms of the assumed figure of merit.

The computation of the (noncyclic) convolution of two sequences occurs in a variety of digital signal processing applications, e.g., correlation and linear filtering. Direct evaluation involving sequences of length N requires N multiplications and (N-1)2additions. A std. approach for large N uses the FFT to reduce the number of computations. This requires that one append a guard band of N zeros. Recently new convolution algorithms have been proposed based on rectangular transform techniques [1]. While these algorithms are highly efficient they are not easily implemented. The objective of this work is the development of a unified theory for multifactor convolution algorithms which are efficient and easily implemented. An algorithm has been developed which is a composition of a number of prime factor algorithms. IfN = n_{1}^{k_{1}}n_{2}^{k_{2}} ... n_{r}^{k_{r}}(where the niare prime and the kiare integers) is a product of many factors, this new algorithm can result in a significant savings. Computational comparisons are given for these new algorithms against the most efficient FFT methods as described in [2]. It is shown that the algorithms in [3] for N=2kare a special case of the multifactor algorithms.

Spectral estimation of real data can be performed by a number of algorithms. This paper compares four methods of estimation. The comparisons are based on three examples which are evaluated in terms of the quality of the estimate, the complexity of the algorithm, and the noise immunity of the estimate. The four estimators are the well-known periodogram, Burg's maximum entropy (AR modelling) method, and two autoregressive-moving average (ARMA) models that have been developed recently here at the University of Colorado [1,2]. The examples chosen contain a smooth spectrum, a spectrum with "high peaks" and "deep valleys", and two sinusoids in white noise. Our results indicate that the ARMA methods are superior in a majority of cases.

Good digital filter realizations for hardware implementation in narrowband filtering applications should have low roundoff noise, low coefficient sensitivity, and freedom from overflow oscillations. The hardware implementations presented here incorporate the above properties into a highly modular structure which can perform computations in pipeline fashion. That is, after an initial delay an output sample is obtained for each input sample. The realization and implementations discussed here contain more multipliers than direct form realizations. However, by using shorter word lengths because of their increased performance and distributed arithmetic implementations (instead of multiplier structures) these implementations can have less total hardware complexity.

Spectral pole-zero models are used as a method of reducing the number of parameters needed to represent certain classes of spectra, e.g., spectral envelopes having deep valleys. We present here an iterative algorithm for Autoregressive-Moving Average (ARMA) models that is based on a repeated use of Levinson's algorithm to obtain both poles and zeros. The procedure allows one to increase the number of poles and zeros iteretively, similar to linear prediction methods. Empirical results indicate that a slow growth of the orders of the denominator and numerator polynomials usually produces better ARMA models.

Minimal roundoff noise IIR digital filters require (n+1)2multiplies per output sample for an nth order filter. By optimizing second-order sections which are then parelleled or cascaded, one can reduce this to approximately 4n multiplies per output. This compares to approximately 3n multiplies for the direct form. This paper presents explicit design equation and noise performance equations for low roundoff noise, second-order filters with fewer multipliers than optimal forms. These structures are a compromise between direct forms (minimal number of multipliers) and minimal roundoff noise structures.

Normal realizations of IIR digital filters possess many desirable properties including freedom from overflow oscillations, low coefficient sensitivity, and invariance of form and roundoff noise under frequency transformations of the filter. Normal realizations are closely related to minimal roundoff noise structures. Given a state variable model {A,b,c,d} of a filter, we define a normal structure as a filter whose A matrix satisfies AAT=ATA. This paper develops design equations and roundoff noise equations for normal and minimal roundoff noise filters in terms of the poles and zeros of the filter transfer function. The development has geometric interpretations which yield additional insights into low roundoff noise structures.

Most of the literature dealing with overflow oscillations in fixed-point digital filters has considered the direct form realization exclusively. In direct forms the question of whether oscillations are possible depends on the location of the poles of the filter. We show that it is possible to eliminate overflow oscillations, regardless of pole locations, by considering more general realizations. A sufficient condition is given for a state variable realization (using two's complement arithmetic) of any order to be free of overflow oscillation. A simple characterization of this condition is given for second order filters. Among second order realizations which meet the condition are so-called normal realizations and structures which minimize roundoff noise.

We have outlined a synthesis procedure which minimizes the output noise in cascade and parallel connections of second-order sections caused by roundoff of internal storage registers. Theorem 1 characterizes the optimal fi Iter and dictates the synthesis procedure. The output noise is made up of two terms. The dominant noise term for block optimal fi lters is independent of bandwidth unl ike the usual cascade and paralle I connections of second-order di rect forms. For narrow band filters improvements of 30 to 40 db are not uncommon. Numerical results yield excellent agreement between theory and simulation.

A formulation of finite-memory information processing problems is presented. The total state space of the system, including the "memory" of the source and processor, is assumed to be finite. A cost functional is specified over the trajectories of the system and a variational approach is used to minimize cost. There results a two-point boundary value problem and an associated improvement algorithm. Special attention is given to two types of cost functionals: finite-time problems, and time-average problems over an infinite time interval. Several examples are included.

A procedure is given for optimizing the sequential estimation of a random variable in the mean-square sense, with the constraint that the data must be summarized by a finite-valued statistic. This finite-valued statistic can be considered to be the memory of the processor. The estimate is constrained to be a function of the contents of the memory and the time of the estimate. An example is given to illustrate the results.

The problem of sequentially deciding upon one ofmmutually exclusive and exhaustive hypotheses has been studied in detail for the case ofm = 2. This correspondence presents the structure for the Bayesm-ary sequential detector. Computational results depend on a property called subspace separability, which allows one to reduce the dimensionality of the essential averaging process. Numerical results are presented for the case of Gaussian observation statistics andm = 3.

A finite-state model for sequential minimum-mean-square-error estimation of a random variable in additive noise is analyzed to determine the dependence of optimum performance and structure on the memory size of the estimator. Necessary conditions for determining the structure of the optimum finite-state estimator are derived for arbitrary statistics. Numerical results are presented for Gaussian statistics. The performance of several different estimators is used to show the trade-off one may obtain between memory size, observation quality, and number of observations.

The optimum sequential detector for two-hypotheses problems when both hypotheses are simple is a likelihood ratio processor in tandem with the optimum stopping rule. When one of the two hypotheses is composite, the optimum detector consists of a likelihood ratio processor, an optimum stopping rule, and an updating processor on the distributed parameters of the composite hypothesis. Discussed is a general theory for obtaining the optimum sequential detector for a composite hypothesis when the available observation length is finite. The general theory is applied to the problem of a signal of unknown amplitude to obtain the optimum receiver design and its evaluation. Limited numerical results indicate the deferred-decision detector is better than the comparable fixed-time detector because it makes terminal decisions of better quality as opposed to making terminal decisions of the same quality in a shorter time.

Observation-decision procedures which associate a cost with observing are generally sequential in nature in order to reduce the observation length. Presented in this paper is the optimum nonsequential procedure in the sense of minimum expected loss for a terminal decision. The procedure is presented in generality and evaluated for normal observation statistics. Two numerical examples are presented for normal observation statistics.

The optimum (likelihood ratio) design and evaluation of a detection receiver is presented for a signal known except for a class of unimodal distributed phases. Sequential and nonsequential realizations are presented. From the evaluation, we conclude that phase angle information which locates the phase to within65^{\circ}is, approximately, for detection, a phase known exactly.