In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiantenna systems employing space-time codes, however, it is not clear what is the best way to obtain the soft information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoding) algorithm to estimate the maximum a posteriori probability of the received symbol sequence. The new algorithm solves a nonlinear integer least squares problem and, over a wide range of rates and signal-to-noise ratios, has polynomial-time complexity. Performance of the algorithm, combined with convolutional, turbo, and low-density parity check codes, is demonstrated on several multiantenna channels. The results for systems that employ space-time modulation schemes seem to indicate that the best performing schemes are those that support the highest mutual information between the transmitted and received signals, rather than the best diversity gain.

Many communications systems employ training, ie, the transmission of known signals, so that the channel parameters may be learned at the receiver. This has a dual effect: too little training and the channel is improperly learned, too much training and there is no time left for data transmission before the channel changes. We use an information-theoretic approach to find the optimal amount of training for frequency selective channels described by a block-fading model. When the training and data powers are allowed to vary, we show that the optimal number of training symbols is equal to the length of the channel impulse response. When the training and data powers are instead required to be equal, the optimal number of symbols may be larger. We further show that at high SNR training-based schemes are capable of capturing most of the channel capacity, whereas at low SNR they are highly suboptimal.

We approach finite impulse response (FIR) equalization problem from an H ∞ perspective. First, we formulate the calculation of the optimal H ∞ performance for a given equalization setting as a semidefinite programming (SDP) problem. H ∞ criterion provides a set of FIR equalizers with different optimality properties. Among these, we formulate the calculation of risk-sensitive or minimum entropy FIR filter as the constrained analytic centring problem and mixed H 2 / H ∞ problem as another SDP. We provide examples to illustrate the procedures we described.

This paper derives an expression for the optimal error nonlinearity in adaptive filter design. Using an energy conservation relation, and some typical assumptions, the choice of the error function is optimized by minimizing the mean-square deviation subject to a fixed rate of convergence. The resulting optimal choice is shown to subsume earlier results as special cases.

We approach FIR equalization problem from an H∞ perspective. \nFirst, we formulate the calculation of the optimal H∞ performance for a given equalization setting as a semidefinite programming (SDP) problem. H∞ criterion provides a set of FIR equalizers with different optimality properties. \nAmong \nthese, \nwe \nformulate \nthe \ncalculation \nof risk sensitive \nor \nminimum \nentropy \nFIR \nfilter \nas \nthe \nconstrained analytic centring \nproblem \nand \nmixed \nH2/H" \nproblem \nas \nanother \nSDP. We \nprovide an \nexample \nto \nil- \nlustrate the \nprocedures \nwe \ndescribed.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// estimation point of view. The H/sup /spl infin// approach is most promising in situations where the statistical properties of the disturbances (arising from quantization, compression, etc.) in each subband of the filter bank are unknown, or are too difficult to model and analyze. For arbitrary analysis polyphase matrices, standard state-space H/sup /spl infin// techniques can be employed to obtain numerical solutions. When the synthesis filters are restricted to being FIR, as is often the case in practice, the design can be cast as a finite-dimensional semi-definite program. In this case, we can effectively exploit the inherent non-uniqueness of the H/sup /spl infin// solution to optimize for an additional average performance and thus obtain mixed H/sup 2//H/sup /spl infin// optimal FIR synthesis filters.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// point of view. For unitary analysis polyphase matrices we obtain an explicit expression for the minimum achievable disturbance attenuation. Numerical examples and comparisons with existing methods are also included.

A technique is proposed for estimating the parameters of two-dimensional (2-D) uniform motion of multiple moving objects in a scene, based on long-sequence image processing and the application of a multiline fitting algorithm. Plots of the vertical and horizontal projections versus frame number give new images in which uniformly moving objects are represented by skewed band regions, with the angles of the skew from the vertical being a measure of the velocities of the moving objects. For example, vertical bands will correspond to objects with zero velocity. An algorithm called subspace-based line detection (SLIDE) can be used to efficiently determine the skew angles. SLIDE exploits the temporal coherence between the contributions of each of the moving patterns in the frame projections to enhance and distinguish a signal subspace that is defined by the desired motion parameters. A similar procedure can be used to determine the vertical velocities. Some further steps must then be taken to properly associate the horizontal and vertical velocities.

As an alternative to existing techniques and algorithms, we investigate the merit of the H-infinity approach to the equalization of communication channels. We first look at causal H-infinity equalization problem and then look at the improvement due to finite delay. By introducing the risk sensitive property, we compare the average performance of the central H-infinity equalizer with the MMSE equalizer in equalizing minimum phase channels.

One of the most crucial emerging challenges in lithography is achieving rapid and accurate alignment under a wide variety of conditions brought about by different processing steps. Current alignment algorithms assume symmetric alignment signals. In this paper, we propose a new algorithm based on subspace decomposition of alignment signals. We assume that the process-induced asymmetries are small enough so that only linear effects need to be considered. We first find the subspace of alignment signals using a set of signals with pre-known positions. The position of a new signal is calculated considering that, if shifted correctly, it will lie in the same subspace of previous signals. Since this method exploits the structure of the signals, it results in more accurate measurement of the position. Simulation results show that the alignment error is about an order of magnitude smaller than that achieved with conventional maximum likelihood or phase-fitting approaches.

This paper reviews two streams of development, from the 1940's to the present, in signal detection theory: the structure of the likelihood ratio for detecting signals in noise and the role of dynamic optimization in detection problems involving either very large signal sets or the joint optimization of observation time and performance. This treatment deals exclusively with basic results developed for the situation in which the observations are modeled as continuous-time stochastic processes. The mathematics and intuition behind such developments as the matched filter, the RAKE receiver, the estimator-correlator, maximum-likelihood sequence detectors, multiuser detectors, sequential probability ratio tests, and cumulative-sum quickest detectors, are described.

The signal-to-noise ratio (SNR) and signal bandwidth have been viewed as the dominant factors determining the channel capacity. In wireless communications, the channel capacity can be increased for a given SNR and a given spectral region, by exploiting the spatial diversity provided by the use of multiple antennas and transceivers at a base station. We calculate the channel capacity enhancement of a so-called space-division-multiple-access (SDMA) system and investigate its dependence with respect to different decoding schemes, terminal positions, and receiver numbers. Inner and outer capacity boundaries for joint decoding and independent decoding are presented, along with physical explanations as to how these boundaries can be achieved. We show that exploitation of the spatial diversity not only increases the overall achievable rates of both joint and independent decoding, but also closes the gap between their corresponding capacity regions, thus bringing the performance of the low-cost independent decoding scheme close to that of the optimal joint decoding. Practical issues of optimum projection and power control are also addressed.

Both experience and analysis show that the widely used subspace methods, such as MUSIC and ESPRIT, perform poorly when applied to estimate closely spaced sinusoidal frequencies. This severely limits the resolution of subspace methods for frequency estimation. In this letter, we present a simple interleaving technique that significantly improves the performance of subspace based methods in the case of closely spaced frequencies. Simulation results show that the improved performance is comparable to the corresponding Cramer-Rao bound (CRB).

The study of matrices with a displacement structure is mainly concerned with recursions for the so-called generator matrices. The recursion usually involves free parameters, which can be chosen in several ways so as to simplify the resulting algorithm. In this correspondence we present a choice for the parameters that is motivated by a maximum-entropy formulation, This choice further motivates the introduction of the so-called generalized reflection coefficients which are, in general, different from the better known Schur coefficients.

In contrast to conventional array processing, in many applications, such as mobile communications, the concept of a parametric array manifold is ill defined. In mobile communications the loss of a well defined array manifold can be attributed to the complex propagation environment consisting of multiple local scatterers near the mobile and remote dominant scatterers, as well as other co-channel signals. In such applications, estimation methods developed in the conventional setting of array processing are of little use and blind estimation of the transmitted signals is of real importance. We present an unconditional maximum likelihood (UML) approach for blind estimation of multiple co-channel digital BPSK signals received by an antenna array, along with the array response matrix A. Based on the idea of fixed point iteration, an efficient algorithm is derived to obtain the UML estimate of A and the maximum a posteriori (MAP) estimates of the digital signals. Simulation results are presented to demonstrate the improved performance of the proposed UML method over the conventional conditional ML (CML) methods. An upper bound on the bit error rate is also presented.

We study the relation between the solutions of two estimation problems with indefinite quadratic forms. We show that a complete link between both solutions can be established by invoking a fundamental set of inertia conditions. While these inertia conditions are automatically satisfied in a standard Hilbert space setting, they nevertheless turn out to mark the differences between the two estimation problems in indefinite metric spaces. They also include, as special cases, the well-known conditions for the existence of H/sup -/spl infin//-filters and controllers. Given two Hermitian matrices {/spl Pi/, W}, a column vector y, and an arbitrary matrix A of appropriate dimensions, we study the relation between two minimization problems with quadratic cost functions, and also refer to the indefinite-weighted least-squares problem.

We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum.

H/sup /spl infin// optimal estimators guarantee the smallest possible estimation error energy over all possible disturbances of fixed energy, and are therefore robust with respect to model uncertainties and lack of statistical information on the exogenous signals. We have shown that if the prediction error is considered, then the celebrated LMS adaptive filtering algorithm is H/sup /spl infin// optimal. We consider prediction of the filter weight vector itself, and for the purpose of coping with time-variations, exponentially weighted, finite-memory and time-varying adaptive filtering. This results in some new adaptive filtering algorithms that may be useful in uncertain and non-stationary environments. Simulation results are given to demonstrate the feasibility of the algorithms and to compare them with well-known H/sup 2/ (or least-squares based) adaptive filters.

This paper presents a new lattice algorithm dual to the extended Inverse QR (IQR) algorithm recently derived by the authors. The original IQR and our extended IQR algorithms are transversal filter algorithms. We found that by assuming a spatial displacement property on the initial correlation matrix of reference data consistent with a time-shifting property of reference data stored in taps of a transversal filter, we could develop a fast version of the extended IQR algorithm. This fast IQR algorithm turns out to have a lattice filter structure instead of a transversal filter structure. Whereas the extended IQR algorithm requires O(M(2)p) computations per iteration, its fast version called a new hybrid QR/LLS algorithm requires O(Mp(2)) computations per iteration, where M, the number of taps, is usually much greater than p, the number of channels. This new hybrid QR/LLS algorithm differs from Regalia and Bellanger's hybrid QR/LLS algorithm, because the former is dual to the IQR algorithm and is based on the use of variance-normalized a priori backwards prediction errors, while the latter is dual to the QR algorithm and is based on the use of variance-normalized a posteriori backwards prediction errors.

In this communication, necessary and sufficient conditions are presented for the unique blind identification of possibly nonminimum phase channels driven by cyclostationary processes. Using a frequency domain formulation, it is first shown that a channel can be identified by the second-order statistics of the observation if and only if the channel transfer function does not have special uniformly spaced zeros. This condition leads to several necessary and sufficient conditions on the observation spectra and the channel impulse response. Based on the frequency-domain formulation, a new identification algorithm is proposed.>

Learning and convergence properties of linear threshold elements or perceptrons are well understood for the case where the input vectors (or the training sets) to the perceptron are linearly separable. Little is known, however, about the behavior of the perceptron learning algorithm when the training sets are linearly nonseparable. We present the first known results on the structure of linearly nonseparable training sets and on the behavior of perceptrons when the set of input vectors is linearly nonseparable. More precisely, we show that using the well known perceptron learning algorithm, a linear threshold element can learn the input vectors that are provably learnable, and identify those vectors that cannot be learned without committing errors. We also show how a linear threshold element can be used to learn large linearly separable subsets of any given nonseparable training set. In order to develop our results, we first establish formal characterizations of linearly nonseparable training sets and define learnable structures for such patterns. We also prove computational complexity results for the related learning problems. Next, based on such characterizations, we show that a perceptron does the best one can expect for linearly nonseparable sets of input vectors and learns as much as is theoretically possible.

Mobile radio channels can be generally characterized as a fading multipath channel with multipath spread delay that ranges from a few microseconds (/spl mu/s) up to as much as 15 /spl mu/s. Such large delays result in intersymbol interference which raises the need for equalization. A semi-blind maximum likelihood sequence estimation (MLSE) with an antenna array is studied as an adaptive equalization method for time division multiple access (TDMA) digital cellular systems. The MLSE is implemented using a Viterbi algorithm (VA). An antenna array is used to utilize both temporal and spatial structure in the received signal to provide the VA with the estimate of the channel impulse response necessary for it to perform MLSE.>

Most methods for sensor array signal processing require the covariance matrix of the background noise to be known. Various techniques for overcoming this limitation have recently been proposed. While most of these are based on assumptions on the noise, we present herein an alternative approach based on partial knowledge of the signals. Methods yielding minimum variance estimates for the model in question are presented and analyzed.>

An analogy is made between each straight line in an image and a planar propagating wavefront impinging on an array of sensors so as to obtain a mathematical model exploited in recent high resolution methods for direction-of-arrival estimation in sensor array processing. The new so-called SLIDE (subspace-based line detection) algorithm then exploits the spatial coherence between the contributions of each line in different rows of the image to enhance and distinguish a signal subspace that is defined by the desired line parameters. SLIDE yields closed-form and high resolution estimates for line parameters, and its computational complexity and storage requirements are far less than those of the standard method of the Hough transform. If unknown a priori, the number of lines is also estimated in the proposed technique. The signal representation employed in this formulation is also generalized to handle grey-scale images as well. The technique has also been generalized to fitting planes in 3-D images. Some practical issues of the proposed technique are given.>

A so-called inverse QR algorithm was recently introduced for recursive adaptive filtering under the exponentially weighted least-squares criterion. It has some attractive features, including the absence of inversions. The extension to the multi-channel case does require inversion however. We present a new derivation of the inverse QR algorithm, based on the technique of Sayed and Kailath, for reformulating the above adaptive filtering problem as a state-space estimation problem. A well-known square-root covariance algorithm for the latter problem is shown to directly give (a multi-channel version of) the inverse QR algorithm. A new extended square-root covariance algorithm is then applied to get a new inversion-free ‘extended inverse QR’ algorithm, even in the multi-channel case. Kürzlich wurde ein sogenannter inverse QR-Algorithms für rekursive adaptive Filter bei Verwendung des Kriteriums der exponentiell gewichteten kleinsten Quadrate eingeführt. Er weist einige attraktive Merkmale auf, darunter das Fehlen von Matrixinversionen. Die Erweiterung auf den mehrkanaligen Fall benötigt jedoch Inversionen. Wir stellen eine Herleitung des inversen QR-Algorithmus vor, die auf der Methode von Sayed und Kailath beruht, das obige adaptive Filterproblem als Schätzproblem im Zustandsraum umzuformulieren. Es wird gezeigt, daß ein allgemein bekannter Wurzel-Kovarianzalgorithmus für das letztere Problem unmittelbar (eine mehrkanalige Version für) den inversen QR-Algorithmus liefert. Ein neuer erweiterter Wurzel-Kovarianzalgorithmus wird danach angewendet, um sogar für den mehrkanaligen Fall einen neuen inversionsfreien ‘erweiterten inversen QR-Algorithmus’ zu erhalten. Un algorithme appelé QR inverse a récemment été introduit pour le filtrage adaptatif récursif utilisant le critère des moindres carrés pondérés exponentiellement. Cet algorithme a quelques propriétés intéressantes, incluant l'absence d'inversions. Toutefois, l'extension au cas multi-canal réclame l'inversion. Nous présentons une nouvelle dérivation de l'algorithme QR inverse, basés sur la technique de Sayed et Kailath, pour reformuler le problème, de filtrage adaptatif ci-dessus comme un problème d'estimation dans l'espace d'état. Nous montrons qu'un algorithme de la racine carrée de la covariance, bien connu pour la résolution de ce dernier problème, donne directement (une version multi-canal de) l'algorithme QR inverse. Un nouvel algorithme de racine carr'ee de la covariance est alors appliqué pour obtenir un nouvel algorithme ‘QR inverse étendu’ ne nécessitant pas d'inversion, même dans le cas multi-canal.

Artificial neural networks are comprised of an interconnected collection of certain nonlinear devices; examples of commonly used devices include linear threshold elements, sigmoidal elements, and radial-basis elements. We employ results from harmonic analysis and the theory of rational approximation to obtain almost tight lower bounds on the size (i.e., number of elements) of neural networks. The class of neural networks to which our techniques can be applied is quite general it includes any feedforward network in which each element can be piecewise approximated by a low degree rational function. For example, we prove that any depth-d+1 network of sigmoidal units or linear threshold elements computing the parity function of n variables must have R(dn/sup 1//d-/spl epsiv/) size, for any fixed /spl epsiv/>0. In addition, we prove that this lower bound is almost tight by showing that the parity function can be computed with O(dn/sup 1/d/) sigmoidal units or linear threshold elements in a depth-(d+1) network. These almost tight bounds are the first known complexity results on the size of neural networks with depth more than two. Our lower bound techniques yield a unified approach to the complexity analysis of various models of neural networks with feedforward structures. Moreover, our results indicate that the in the context of computing highly oscillating symmetric Boolean functions, networks of continuous-output units such as sigmoidal elements do not offer significant reduction in size compared with networks of linear threshold elements of binary outputs.>

A new blind channel identification and equalization method is proposed that exploits the cyclostationarity of oversampled communication signals to achieve identification and equalization of possibly nonminimum phase (multipath) channels without using training signals. Unlike most adaptive blind equalization methods for which the convergence properties are often problematic, the channel estimation algorithm proposed here is asymptotically ex-set. Moreover, since it is based on second-order statistics, the new approach may achieve equalization with fewer symbols than most techniques based only on higher-order statistics. Simulations have demonstrated promising performance of the proposed algorithm for the blind equalization of a three-ray multipath channel.>

A polynomial time algorithm for solving the combinatorial problem that underlies the reconfiguration issues in the m1/2-track-m-spare model, for any arbitrary m, is discussed. The following combinatorial problem is solved: Given a set of points in a two-dimensional grid, find a set of noninteracting straight lines such that every line starts at a point and connects to one of the boundaries of the grid, there are no more than m lines overlapping in any row or column of the grid, and there are no near-miss situations. The time complexity of the algorithm is shown to be O(m mod F mod /sup 2/), where mod F is the number of faulty processors.>

Present new results on systematic procedures for reconfiguring processor arrays in the presence of faulty processors. In particular, the authors consider models that use multiple tracks along every channel and a single spare row (or column) of processing elements (PEs) along each boundary of the array. In the presence of faulty PEs the general methodology for reconfiguration involves replacing every faulty PE logically (rather than physically) by a spare PE through a sequence of logical substitutions; these sequences of substitutions are referred to as compensation paths. The authors show that if there exists a set of compensation paths subjected only to the constraints of continuity and nonintersection, then routing channels with three tracks are enough for the reconfiguration of the array. They refer to the underlying model as a S-track-l-spare model; this is done to distinguish it from other models that not only use multiple tracks but also multiple spare rows (or columns) along each boundary. An efficient algorithm for reconfiguration in our 3-track-1-spare model is presented and its performance evaluated. Experimental results show that the 3-track-1-spare model has much higher reconfiguration probability than other models that use considerably more spare processors.>

A signal processing method is developed for solving the problem of fitting multiple lines in a two-dimensional image. It formulates the multi-line-fitting problem in a special parameter estimation framework such that a signal structure similar to the sensor array processing signal representation is obtained. Then the recently developed algorithms in that formalism can be exploited to produce super-resolution estimates for line parameters. The number of lines may also be estimated in this framework. The signal representation used can be generalized to handle problems of line fitting and of straight edge detection. Details of the proposed algorithm and several experimental results are presented. The method exhibits considerable computational speed superiority over existing single- and multiple-line-fitting algorithms such as the Hough transform method. Potential applications include road tracking in robotic vision, mask wafer alignment in semiconductor manufacturing, aerial image analysis, text alignment in document analysis, and particle tracking in bubble chambers.

An artificial neural network (ANN) is commonly modeled by a threshold circuit, a network of interconnected processing units called linear threshold gates. It is shown that ANNs can be much more powerful than traditional logic circuits, assuming that each threshold gate can be built with a cost that is comparable to that of AND/OR logic gates. In particular, the main results indicate that powering and division can be computed by polynomial-size ANNs of depth 4, and multiple product can be computed by polynomial-size ANNs of depth 5. Moreover, using the techniques developed, a previous result can be improved by showing that the sorting of n n-bit numbers can be carried out in a depth-3 polynomial-size ANN. Furthermore, it is shown that the sorting network is optimal in depth.>

A new fundamental signal processing method is developed for solving the problem of fitting multiple lines in a two-dimensional image. The proposed technique formulates the multiline fitting problem in a special parameter estimation framework such that a signal structure similar to the sensor array processing signal representation is obtained. Then, recently developed algorithms in that formalism (e.g., the ESPRIT technique) are exploited to produce superresolution estimates in this framework. The signal representation used in this formulation can be generalized in a fashion to handle both problems of line fitting (in which a set of binary-valued discrete pixels is given) and of straight edge detection (in which one starts with a gray-scale image). The proposed method possesses extensive computational speed superiority over previous single- and multiple-line fitting algorithms such as the Hough transform method. Details of the new formulation are explained, and several experimental results are presented.>

The authors use the classical Schur reduction procedure to give a lattice filter implementation of the Chandrasekhar recursions. The derivation is based on the observation that the covariance matrix of a process with a time-invariant state-space model is structured. This allows one to easily derive the connection between the Schur algorithm and spectral factorization and to extend the Chandrasekhar recursions to the case of nonsymmetric Riccati equations. The Chandrasekhar recursions can be implemented in scalar steps using a sequence of well-defined elementary (hyperbolic and Givens) rotations.>

Forward/backward (FB) averaging is employed when possible in sensor array processing to improve parameter estimation accuracy by exploiting a centro-symmetry of the signal subspace. While FB averaging effectively doubles the number of data samples, it also introduces intersample correlation. This correlation complicates not only the performance analysis, but the detection of the number of sources as well. It is shown how existing detection procedures such as sequential hypothesis (or likelihood ratio) tests, minimum description length criterion (MDL), and AIC (Akaike information criterion) can be modified when FB averaging is used.>

A self-reference technique is developed for detecting the location of defects in repeated pattern wafers and masks. The application area of the proposed method includes inspection of memory chips, shift registers, switch capacitors, and CCD arrays. Using high resolution spectral estimation algorithms, the proposed technique first extracts the period and structure of repeated patterns from the image to sub-pixel resolution, and then produces a defect-free reference image for making comparison with the actual image. Since the technique acquires all its needed information from a single image, there is no need for a database image, a scaling procedure, or any a-priori knowledge about the repetition period of the patterns.>

A fast signal-subspace decomposition (FSD) algorithm is presented for sample covariance matrices, which only needs O(M/sup 2/d) flops, where d(>

Most high-resolution algorithms for sensor array processing require an eigendecomposition which is difficult to implement in parallel and costs at least O(M/sup 3/) multiplications for an M*M matrix, corresponding to M sensors. Recently, S.D. Silverstein et al, (1991) presented a subband parallel scheme, which reduced the computation time from O(M/sup 3/) to O(L/sup 3/), where L(>

The tradeoffs between the depth (i.e., the time for parallel computation) and the size (i.e., the number of threshold gates) in neural networks are studied. The authors focus the study on the neural computations of symmetric Boolean functions and some arithmetic functions. It is shown that a significant reduction in the size is possible for symmetric functions and some arithmetic functions, at the expense of a small constant increase in depth. In the process, several neural networks which have the minimum size among all the known constructions have been developed. Results on implementing symmetric functions can be used to improve results about arbitrary Boolean functions. In particular, it is shown that any Boolean function can be computed in a depth-3 neural network with O(2/sup n/ /sup 2/) threshold gates; it is also proven that at least Omega (2/sup n/ /sup 3/) threshold gates are required.>

Classical methods from optimal control theory are used in deriving general forms for neural network weights. The network learning or application task is encoded in a performance index of a general structure. Consequently, different instances of this performance index lead to special cases of weight rules, including some well-known forms. Comparisons are made with the outer product rule, spectral methods, and recurrent back-propagation. Simulation results and comparisons are presented.

The problem of estimating signal parameters from sensor array data is addressed. If the array is composed of two identical subarrays, (i.e. one invariance) the ESPRIT algorithm is known to yield parameter estimates in a very cost efficient manner. Recently, the total least squares (TLS) version of ESPRIT has been formulated in a subspace fitting framework. In this formulation, the ESPRIT concept is easily generalized to arrays exhibiting more than one invariance. The asymptotic properties for this class of algorithms are derived. The estimates are shown to be statistically efficient under certain assumptions. The case of a uniform linear array is studied in more detail, and a generalization of the ESPRIT algorithm is proposed by introducing row weighting of the subspace estimate.>

The recently introduced class of subspace fitting algorithms for sensor array signal processing (e.g. direction-of-arrival (DOA) estimation) includes deterministic maximum likelihood, ESPRIT, weighted subspace fitting, and both one- and multidimensional MUSIC as special cases. The performance of this class of algorithms is examined for situations where the sensor array response is perturbed from its nominal value. Theoretical expressions for the error in the DOA estimates are derived and compared with several simulation examples. It is shown that in difficult cases the algorithms are especially sensitive to the choice of subspace weighting. For a particular perturbation model, and optimal subspace weighting is proposed which minimizes the DOA estimate error variance over all possible weightings when finite sample effects are neglected.>

The study of Regular Iterative Algorithms (RIAs), which was introduced in a seminal pa.per by Knrp, Miller, and Winograd in 1967, forms the basis for systematic design and analysis of regular processor arrays, including the class of systolic arrays.The RIAs have also been studied under different contexts and different names (on the last count RIAs were reintroduced, as late as 1987, under the name of dynamic graphs).In spite of the interest such algorithms have received over the years, many important issues that were left unresolved in the original paper by Karp e2 al., have remained unanswered.In this paper we answer many such questions, particularly those relating to parallel scheduling and implementation of RIAs.Based on the analysis of a simple graph that captures the dependence structure of a given RIA, we are able to determine linear subspaces in the index space of a given RIA such that all variables lying on the same subspace can be scheduled at the same time; this generalizes the so-called hyperplanar scheduling which was shown by Karp et.al. to work for only a subclass of RIAs.This geometric scheduling scheme is shown to be asymptotically optimal and is used to completely characterize the extent of parallelism in any RIA.Moreover, we develop procedures to determine explicit schedules (;.e, a closed form expression for the schedule of every computation in the algorithm) that correspond to the geometric schedules, and also show that every RIA can be automatically mapped onto regular processor arrays.

This paper is concerned with the analysis of synchronous, special purpose, multiple-processor systems (including, e.g., systolic arrays). The analysis problem is that of determining the algorithm executed by the system. There has been some prior work in this area, especially by Melhem and Rheinboldt [SIAM J. Comput.,13 (1984), pp. 541–565], who were the first to obtain a general solution. The approach used here is different and apparently simpler. By combining ideas well known in system theory with certain graph-theoretical concepts, a simple procedure for recovering, within a natural equivalence, the iterative algorithm executed by a given special purpose synchronous computing array is obtained. The solution is based on reversing (modulo equivalence) the process by which an iterative algorithm is translated into a logical circuit.

The issue of developing efficient algorithms for reconfiguring processor arrays in the presence of faulty processors and fixed hardware resources is discussed. The models discussed consist of a set of identical processors embedded in a flexible interconnection structure that is configured in the form of a rectangular grid. An array grid model based on single-track switches is considered. An efficient polynomial time algorithm is proposed for determining feasible reconfigurations for an array with a given distribution of faulty processors. In the process, it is shown that the set of conditions in the reconfigurability theorem is not necessary. A polynomial time algorithm is developed for finding feasible reconfigurations in an augmented single-track model and in array grid models with multiple-track switches.>

Model-free learning for synchronous and asynchronous quasi-static networks is presented. The network weights are continuously perturbed, while the time-varying performance index is measured and correlated with the perturbation signals; the correlation output determines the changes in the weights. The perturbation may be either via noise sources or orthogonal signals. The invariance to detailed network structure mitigates large variability between supposedly identical networks as well as implementation defects. This local, regular, and completely distributed mechanism requires no central control and involves only a few global signals. Thus, it allows for integrated, on-chip learning in large analog and optical networks.

The authors present scalar implementations of multichannel fast recursive least squares algorithms in transversal filter form (so-called FTF). By processing the different channels sequentially, i.e one at a time, the processing of any channel reduces to that of the single-channel algorithm. This sequential processing decomposes the multichannel algorithm into a set of intertwined single-channel algorithms. Geometrically, this corresponds to a modified Gram-Schmidt orthogonalization of multichannel error vectors. Algebraically, this technique corresponds to matrix triangularization of multichannel error covariance matrices and converts matrix operations into a regular set of scalar operations. Algorithm structures that are amenable to VLSI implementation on arrays of parallel processors follow naturally from this approach. Numerically, the resulting algorithm benefits from the advantages of triangularization techniques in block processing. Stabilization techniques for control of numerical error propagation in the update recursions are incorporated.>

The third moment matrix R/sub 3/ is proposed as a tool for use in the detection and estimation of phase-coupled sine waves. The advantages of such an approach are that the structure of R/sub 3/ can be exploited by means of the singular value decomposition (SVD) to estimate directly the number of coupled sine waves and their frequencies. After a brief introduction to the bispectrum and the phase coupling problem, the following key results are presented: (1) The rank of R/sub 3/ is (asymptotically) equal to the number of coupled sine waves. (2) A pseudobispectrum can be generated using a MUSIC-like algorithm with vectors orthogonal to the (column) signal subspace. (3) The coupled frequencies can be directly estimated from the (row) signal subspace using techniques such as Root-MUSIC or ESPRIT. Examples of simulations using this approach are given.>

The authors present a regular iterative algorithm for matrix multiplication and show that several well-known matrix multiplication arrays are directly obtained from it, differing only in the choice of iteration vector. They then present a regular iterative algorithm for matrix multiplication using the S. Winograd method (1968) and show in detail how to derive one array from this algorithmic description. Other arrays in the same family can similarly be obtained for different choices of the iteration space. The new arrays compute the product of two matrices faster than available conventional arrays and use a smaller number of processor cells.>

Several computationally efficient versions of the Levinson algorithm for solving linear equations with Toeplitz and quasi-Toeplitz matrices are presented, motivated by a new stability test. The new versions require half the number of multiplications and the same number of additions as the conventional form of the Levinson algorithm. The saving is achieved by using three-term (rather than two-term) recursions and propagating them in an impedance/admittance (or immittance) domain rather than the conventional scattering domain. One of the recursions coincides with recent results of P. Delsarte and Y. Genin (IEEE Trans., Acoust. Speech, Signal Proc., vol.ASSP-34, p.470-8, June 1986) on split Levinson algorithms for symmetric Toeplitz matrices, where the efficiency is gained by using the symmetric and skew-symmetric versions of the usual polynomials. This special structure is lost in the quasi-Toeplitz case, but one still can obtain similar computational reductions by suitably using three-term recursions in the immittance domain.>

A universal characterization of maximum-entropy covariances for multidimensional signals is presented. It is shown that the maximum-entropy extension of an arbitrary partial covariance of a nonstationary multidimensional signal always has a banded inverse, i.e the inverse is sparse and has the same support as the given partial covariance. A dual formulation of the problem that makes it possible to approximate maximum-entropy extensions with models selected from suitably constrained model sets is introduced. It is proved that the best approximation in terms of multidimensional recursible autoregressive models can be determined by solving a set of linear equations. A simple graph-theoretic criterion is introduced to characterize those partial covariances whose maximum-entropy extension coincides with its autoregressive approximation, as in the conventional (one-dimensional stationary) maximum-entropy problem.>

A novel direction-of-arrival (DOA) estimation algorithm is proposed that applies to wideband emitter signals. A sensor array with a translation invariance structure is assumed, and an extension of the ESPRIT algorithm for narrowband emitter signals is obtained. Following the ideas of G. Su and M. Morf (1986) the authors model the emitter signals as the stationary output of a finite-dimensional linear system driven by white noise. The array response to a unit impulse from a given direction is represented as the impulse response of a linear system. The measured data from the sensor array can then be seen as the output of a multidimensional linear system driven by white noise sources and corrupted by additive noise. The emitter signals are characterized by the modes of the linear system. The ESPRIT algorithm is applied at the poles of the system, the power of the signals sharing the pole is captured and the effect of noise is reduced.>

A simple general method for overcoming singularities in the Levinson (and Schur) recursions for Toeplitz systems is presented. It is based on a generalization of the conventional three-term recursion for polynomials orthogonal on the unit circle: the scalar coefficients of the conventional three-term recursion are replaced by polynomial coefficients whose degree is determined by the depth of singularity. The depth of the singularity is related to the number of additional zero elements that occur in the Schur recursion. The authors' method also makes it possible to recursively determine the inertia of a Hermitian Toeplitz matrix.>

The problem of numerical stability of fast recursive least-squares transversal filter (FTF) algorithms is addressed. The prewindowing case with exponential weighting is considered. A framework for the analysis of the error propagation in these algorithms is developed. Within this framework, it is shown that the computationally most efficient 7N form (dealt with by G. Carayanmis et al. (1983) and by J.M. Cioffi (1984)) is exponentially unstable. By introducing redundancy in this algorithm, feedback of numerical errors becomes possible. This leads to a numerically stable FTF algorithm with complexity 9N. The results are presented for the complex multichannel joint-process filtering problem.>

The Viterbi algorithm is a well-established technique for channel and source decoding in high-performance digital communication systems. Implementations of the Viterbi algorithm on three types of locally connected processor arrays are described. The restriction is motivated by the fact that both the cost and performance metrics of VLSI favour architectures in which on-chip interprocessor communication is localized. Each of the structures presented can accommodate arbitrary alphabet sizes and algorithm memory lengths.>

Some recent results are summarized concerning a class of algorithms known as regular iterative algorithms, particularly with respect to their implementations on processor arrays. Regular iterative algorithms contain all algorithms executed by systolic arrays as a proper subclass and are therefore of considerable importance in real-time signal processing applications. Some general concepts concerning the design of parallel architectures are introduced, and the importance of devising special techniques that utilize any available structure in the algorithm is highlighted. A generic description of the existing methodologies for the systematic design of systolic arrays is given. Using some simple examples, the limitations of these methods are shown. A formal methodology is proposed that overcomes the difficulties in the existing procedures.>

Several lattice forms and algorithms which constitute the immittance domain alternatives to the PARCOR lattice algorithm are presented. The immittance variables were shown to offer more efficient Levinson algorithms than the conventional scattering algorithms for both symmetric and Hermitian Toeplitz matrices. This paper presents the lattices associated with the new recursions and provides algorithms to determine their coefficients directly from the signal segments. The new lattices are of interest for speech processing as they offer a different parametrization and process real signal segments with only one multiplier and two adders per section. Complex signal segments require two multipliers and adders per section. Stability conditions for the new parametrizations are also presented.

A new approach to optimum beamforming in the presence of signal correlated interfences that completely eliminates the signal cancellation problem is described. Three new, fundamentally distinct beamformers corresponding to different optimality criteria are derived by exploiting the underlying signal model.

A new approach to stability of adaptive filters is presented. The notion of constrained-input/constrained-output (CICO) stability is introduced as a generalization of the standard notion of bounded-input/bounded-output (BIBO) stability. This new notion involves a set of constraints on the filter data (i.e., signals and parameters) that, unlike boundedness, are specific to the filter in consideration. The set of all data that satisfy the constraints is the feasibility domain of the adaptive filter. Three particular adaptive lattice filters are analyzed: (i)Burg's lattice, (ii)the unnormalized RLS lattice, and (iii)the normalized RLS lattice. We derive the feasibility domains of these adaptive filters and prove that they are CICO stable.

A recursive-least-squares (RLS) adaptive fast transversal filter (FTF) for processing of continuous-time signals is presented. It has the same structure as the discrete-time least-squares FTF, namely, a tapped-delay-line with time-varying gains, which are updated by propagating a set of coupled recursions. However, while the discrete-time scheme involves a fundamental unit of time (i.e., the sampling period of the signal), which determines both the duration of the delay and the rate of gain updating, our continuous-time scheme involves a delay of arbitrary duration and continuously-varying gains. Also, the conceptual and computational complexity of the continuous-time FTF is reduced in comparison to the to that of the discrete-time FTF. The rate of parameter updating in the continuous-time FTF configuration is essentially independent of the bandwidth and center frequency of the processed signal. Consequently, the gain-update module of the proposed algorithm can be implemented with slow devices (or with digital hardware), whereas the signal-path filter must match the frequency characteristics of the processed signal.

ESPRIT is a new algorithm for signal parameter estimation with applications to direction-of-arrival estimation in a multiple source environment. It has considerable computational advantages (e.g., faster and applies to sensor arrays with unknown and nearly arbitrary geometry requiring no array calibration and storage) over the well-known conventional MUSIC algorithm. Herein, results of computer simulations carried out to compare their resolution and error (bias and variance) performance are presented. A new multi-dimensional spectral measure for the MUSIC algorithm is also introduced and preliminary investigations of its performance are presented.

In this paper we introduce a new adaptive array able to separate superimposed directional signals without requiring any a priori information. The new adaptive array combines beating estimation and adaptive array processing. The suggested adaptive array utilizes a root-tracking algorithm that is based on Pisarenko's harmonic retrieval method which can handle correlated array input signals.

The important problem of Adaptive Line Enhancing (ALE) is addressed in this paper. Its solution involves an Adaptive Notch Filter (ANF) proposed in [1],[2] using a minimal parameter constrained infinite impulse response (IIR) model in conjunction with the Recursive Prediction Error Method (RPEM) [3]. A Fast Transversal Filter (FTF) algorithm for the adaptive RLS-type updating of the linear phase filter is presented.

Regular mesh-connected arrays are shown to be isomorphic to a class of so-called regular iterative algorithms. For a wide variety of problems it is shown how to obtain appropriate iterative algorithms and then how to translate these algorithms into arrays in a systematic fashion. Several "systolic" arrays presented in the literature are shown to be specific cases of the variety of architectures that can be derived by the techniques presented here. These include arrays for Fourier Transform, Matrix Multiplication, and Sorting.

Several computationally extra-efficient versions of the Levinson algorithm are presented. The new versions require half the number of multiplications and the same number of additions as the conventional form of the Levinson algorithm. The saving is achieved by using three- (rather than two) term recursions and propagating them in an Impedance/Admittance domain rather than the conventional scattering domain. Our result apply both to Toeplitz and to close to Toeplitz systems. Moreover they provide a general method for reducing computational requirements in various recursive algorithm, e.g. adaptive least-square lattice algorithms.

We present a time-domain method for estimating the number and delay times for overlapping signals with a priori known shape, from noisy observations received by a sensor. The method is based on a recently developed eigenstructure technique for multiple direction finding with sensor arrays and exploits the structure of the received signal covariance matrix. The method presented also solves more general problems of signal detection and resolution.

This paper concerns systolic arrays and the broader class of synchronous, special-purpose systems. We establish the properties of such systems relative to synchronism, and develop a procedure to determine the algorithm that a specific array implements. Such a procedure is crucial for checking the correct use of the architecture.

The application of the eigenstructure algorithm for estimating the Doppler (frequency shift) of wideband signals in noise is described. The problem is formulated in the context of a FM-CW radar where, the target range appears as a frequency shift which is then estimated. Our approach generalizes the well known results of Pisarenko for determining the Doppler (frequency shifts) of multiple harmonics in noise to the problem of estimating the frequency shifts of multiple wideband signals. Results of computer simulations that verify the performance of our proposed algorithm are also presented.

Results of simulations comparing the performance of ESPRIT (Estimation of Signal Parameters via Rotational Invariance Techniques) and the MUSIC (MUltiple Signal Classification) algorithm are presented. ESPRIT exploits an underlying rotational invariance among signal subspaces induced by an array of sensors with a translational invariance structure. In contrast, the MUSIC algorithm uses intersections between the array manifold and the signal subspace to estimate the directions. ESPRIT is shown to have performance advantages over MUSIC in certain scenarios apart from its previously reported implementational advantages.

We propose a statistical procedure known as the smoothed rank profile (SRP) test that can be applied to an array covariance matrix to determine the source coherency structure and solvability of the directions-of-arrival estimation problem in the presence of coherent sources. The SRP is the rank profile of a telescoping series of matrices extracted from the observed array covariance matrix. Results of computer simulations are presented that verify the efficacy of the proposed test.

Eigenstructure methods for direction of arrival estimation have become well established for radar, sonar and radio array applications for which coherent (i.e. amplitude and phase) measurements are available. In many IR and optical applications incoherent detectors are used that measure the power rather than signal amplitude/phase. In this paper, we derive a subspace algorithm for high resolution direction of arrival estimation for such measurement models. Results of computer simulation that verify the performance of our proposed algorithm are also presented.

The MUSIC algorithm is one of the more important high resolution approaches for direction finding and spectral estimation that have been developed in recent years. Asymptotically (i.e. infinite data or SNR) the MUSIC algorithm has been shown to yield efficient unbiased estimates. However the performance of the algorithm for the non-asymptotic situation of high noise and limited data has not been fully addressed. In this paper we study the performance of the MUSIC algorithm when only finite noise corrupted data is available. We focus on the role of array design in the performance of MUSIC algorithm for direction finding and introduce certain measures to characterize its performance. We show that in the single target situation these measures can be described in terms of the familiar conventional beampatterns. Results of computer simulations carried out to check the usefulness of such measures are also presented.

A new approach to Estimation of Signal Parameters by Rotational Invariance Techniques (ESPRIT) is described in the context of direction-of-arrival estimation, but is also applicable to other problems. The method relies on finding the underlying rotation between the common subspaces associated with an array of pairwise-matched and codirectional sensor doublets. ESPRIT has several remarkable advantages over earlier techniques such as MUSIC, and also provides asymptotically unbiased and efficient estimates.

In this paper, we take a hard look at scheduling considerations in computing arrays. A simple sufficient condition is developed for determining whether a computing array can be pipelined. If the array cannot be pipelined in the form given, the condition also indicates the direction in which to proceed to make it pipelineable. The overall framework and methodology take a good part of the load off the logical architect of the array, and make the translation from the logical to the physical architecture a mechanical process.

We consider a source radiated signal arriving at an array as a group of wavefronts, each having a different angle of arrival and with arbitrary amplitude, phase and inter wavefront correlation. Several such sources may be present and the measurement data is assumed to be corrupted by sensor to sensor uncorrelated noise. The task of the beamformer is to make optimal estimates of each source signal of interest by using the information in all the wavefronts generated by the source. The proposed processor begins with no apriori information about the environment and constructs the optimal beamformer by a bootstrapping approach which uses a two tier eigenstructure analysis of the array covariance. We show that this new beamformer has substantial advantages over the usual optimal beamformers and present results of computer simulation carried out to verify its performance.

Direction of arrival estimation by eigenstructure methods requires knowledge of the array covariance matrix and an exact characterization of the array in terms of geometry, sensor gain and phase, etc. It often happens that the actual sensor gain and phase are perturbed from their assumed nominal values. If eigenstructure methods are applied with incorrect sensor parameters, the method essentially breaks down or at best gives poor results. We propose a new approach which uses information in the observed covariance matrix to correct for these effects. This method yields substantially improved performance, a fact illustrated by the results of computer simulations.

We present new eigenstructure based methods for spatial-temporal processing in passive sensor arrays. Unlike the existing methods of Schmidt and Bienvenu and Kopp, the new estimators are not based only on the underlying orthogonality relation between the "noise" subspace and the "signal" subspace, but also on statistical considerations stemming from the structure of the maximum likelihood estimator. As such, these estimators make better use of the available data and therefore have superior performance, especially in the threshold region, where efficient utilization of the data is most rewarding.

Computationally efficient recursive-least-squares (RLS) procedures are presented specifically for the adaptive adjustment of the data-driven echo cancellers (DDEC's) that are used in voiceband fullduplex data transmission. The methods are shown to yield very short learning times for the DDEC, while they also simultaneously reduce computational requirements to below those required for other leastsquare procedures, such as those recently proposed by Salz (1983). The new methods can be used with any training sequence over any number of iterations, unlike any of the previous fast-Converging methods. The methods are based upon the fast transversal filter (FTF) RLS adaptive filtering algorithms that were independently introduced by the authors of this paper; however, several special features of the DDEC are introduced and exploited to further reduce computation to the levels that would be required for slower-converging stochastic-gradient solutions. Several tradeoffs between computation, memory, learning time, and performance are also illuminated for the new initialization methods.

Redheffer scattering theory is reviewed in a generalized setting as a method to derive recursive solutions of linear two-point boundary value problems (TPBVP) over arbitrarily varying intervals. The results can be used to derive a complete solution for the problem of limited-memory (or sliding-window) estimation, when a usual state-space model for the signal is available. Recursive limited-memory filters are derived for both continuous and discrete time signals.

Most techniques for computing beamformer tap weights do so by maximizing the overall signal-to-noise ratio at the system output, where noise includes both thermal noise and directional interference. This is the optimal solution if the two noise sources count equally. However, there do exist scenarios where directional interference is more harmful to system performance. For this reason, the authors introduced a new beam-former based on eigenvector techniques[1] which is able to exactly null interference even when thermal noise is present. Unfortunately, however, the new method can also cause signal cancellation, depending on the geometry of the interference. This cancellation can be reduced by introducing additional eigenvectors in the tap weight solution. We develop a criterion for choosing these additional vectors which allows the user to set the maximum tolerable signal cancellation. Given this signal cancellation constraint, the directional interference power is minimized. Simulation results are presented which demonstrate the modified eigenvector beamformer. We also comment on the extension of the method to wide-band signals.

In this paper, we present a systematic way to describe the logical architecture of the system implementing a given algorithm by means of an extended block diagram, and develop a standard notation to describe each block. We then show a technique for correctly transforming a block diagram into a physical circuit description by introducing the notion of time into the block diagram, and describe an algorithm that optimally assigns a limited number of hardware modules to all the function blocks in the diagram.

We present a framework for the design and description of Systolic-type Arrays. The framework is based on the definition of a conceptual tool, Lines of Computation (LOC's) that allows us to systematically define a generalization of the idea of Systolic Arrays and Wavefront Array Processors. We use three different architectures for parallel matrix multiplication to show the power of LOC's to describe and generate Systolic-type Arrays. Finally, we present some topographical properties of Systolic Arrays that can be readily analyzed using LOC's ideas.

An algorithm is presented for the design of systolic arrays that implement single-input single-output time-invariant digital filters. The algorithm is then specialized to the case where the realized array consists only of orthogonal rotational modules and delay elements interconnected in such a manner as to render the circuit pipelineable.

In this paper we introduce a new adaptive processor able to work well even when the desired signal and the interference are coherent. The present adaptive processors fail to operate in these cases. The results of simulations appear to confirm the theoretical predictions.

This paper considers some asymptotic statistical properties of covarianee eigenstructure spectral analysis techniques. It is shown that when the signal model is of the appropriate form, and the observations are Gaussian, the signal parameter estimates, obtained by locating the nulls in the eigen-spectrum, are asymptotically zero mean normal random variables. Based on this observation, the paper then considers the formation of confidence regions for the signal parameters. The paper presents the general case of a multi-dimensional eigenstructure algorithm, which estimates one or more parameters of each signal in the observed data.

The determination of the number of signals in a wide class of problems, including array processing, harmonic retrieval and pole retrieval, is addressed. A new approach, based on the application of the information theoretic criteria for model identification introduced by Akaike, Schwartz and Rissanen, is presented. It is shown that the criterion introduced by Schwartz and Rissanen yields a consistent estimate of the number of signals, while the criterion introduced by Akaike yields an inconsistent estimate that tends, in the large-sample limit, to overestimate the number of signals.

The problem of of decentralizing the processing in a passive array composed of subarrays at geographically dispersed sites is addressed. A new scheme, based on obtaining estimates of the covariance matrices from each subarray is presented, and its performance is compared to the conventional triangulation method. It is shown that the new scheme offers improved accuracy with only a modest increase in the communication load. Moreover, unlike the conventional triangulation scheme, it does not require any data association step; the data association is done automaticly in the proposed algorithm.

An efficient exact-least-squares procedure is presented specifically for the adaptive adjustment of a fractionally spaced equalizer (FSE). The intersymbol interpolation of the desired training sequence is used by this new procedure to reduce computational requirements and to improve convergence. For aT/pFSE (1/Tbeing the data symbol rate andpthe number of taps that span one symbol period), a factor ofpimprovement in "start-up" time is attained by this new procedure in comparison to the multichannel FSE versions of the "fast-Kalman" leastsquares algorithms of Falconer and Ljung [7] and in comparison to the Ling-Proakis [10] simplification for multichannel versions of the "fastlattice" least-squares algorithms of Satorius and Pack [8 ]Substantial reductions in computational and storage requirements are also achieved by the new procedure through the elimination of the inversion ofp \times pmatrices in these multichannel versions. Additional reductions in computational requirements are achieved by a special exact-least-squares modification for the passband "Nyquist" FSE structure of Mueller and Werner [6]. The procedure is shown to be most efficiently implemented using a transversal-filter realization of the fast exact-least-squares algorithmns. The per-iteration and per-unit-time computational requirements of the new procedure (T/4FSE) are found to be approximately the same as those of the more conventional, but much slower converging, (T/2) tap-leakage stochastic-gradient algorithms of Gitlin, Meadors, and Weinstein [15]. Finally, simulations are conducted to verify the operation of the new procedure for both the training and decision-directed modes of operation.

A general theory of constant-parameter modular lattice models for discrete-time nonstationary second-order processes is presented. A complete parametrization of such processes in terms of Schur and congruence coefficients is derived by developing a natural connection between the displacement structure of a covariance matrix and Schur's test for positive-definiteness of matrices. Schur coeffieients provide a simple solution to problems of covariance extension and rational spectral approximation for nonstationary covariances, and they coincide with the well-known reflection (or PARCOR) coefficients when the covariance is stationary. The congruence coefficients provide the time-varying gains of a tapped-delay-line realization of the whitening filter for the process. A constant-parameter realization of the same filter is derived by combining a lattice filter structure with a tapped delay line, both with time-invariant gains. This configuration also provides a recursive relation for the congruence coefficients (namely, a generalized Levinson-Szego recursion). The tapped-delay-line part of the realization can be eliminated by introducing the concept of admissibility. Admissibility also reduces the parametrization of a nonstationary process to Schur coefficients alone, in analogy to stationary processes, which are completely characterized by their PARCOR coefficients.

A unified theory is presented to characterize least-squares adaptive filters, in either lattice or transversal-filter form, for nonstationary processes. The derivations are based upon a geometric formulation of least-squares estimation and on the concept of displacement rank. A few basic geometric relations are shown to underlie the various algorithms. Insights into the fundamental concepts that unify lattice- and transversal-filter approaches to least-squares adaptive filters are also given. The general results are illustrated by applications to the so-called "pre-windowed" and "growing-memory covariance" formulations of the deterministic least-squares problem.

Fast, fixed-order, exact-least-squares algorithms for tapped-delay-line adaptive-filtering applications are presented in this paper. These new recursive algorithms require fewer operations per iteration and exhibit better numerical properties than the so-called Fast-Kalman algorithm of Ljung and Falconer [1978] and the unnormalized, least-squares, joint-process-lattice algorithms of Morf and Lee [1978]. In comparison with the currently used stochastic-gradient or LMS adaptive algorithm of Widrow and Hoff, the new, fixed-order, least-squares algorithms yield substantial improvements in transient behavior at a modest increase in computational complexity. Additionally, over a wide range of practical applications, the new algorithms demonstrate numerical properties comparable to those of the normalized lattice introduced by Lee, Morf, and Friedlander [1981], but at a considerable reduction in complexity.

We propose the application of modified recursive least-squares algorithms and least-squares lattice algorithms to echo cancellation problems to provide fast convergence and overcome the effects of the double-talking. The modified algorithms run continuously, but the gain updates become negligibly small during the double-talking intervals. Thus, detection of the double-talking and virtual freezing of the adaptive filter weights are both built into the algorithm. Simulations are used to verify the performance of the proposed algorithms, And the results confirm the theoretical predictions. A comparison of performances of different algorithms applied to real speech signals is also given in the paper.

An iterative algorithm for the inversion of a doubly block Toeplitz matrix consisting of m × m blocks of size p × p is described. The algorithm presented exploits the structure of the doubly block Toeplitz matrix and outperforms Akaike's algorithm by a factor of\max {2 \frac{p}{m},2}. The use of this algorithm for an iterative solution of a doubly block Toeplitz set of linear equations is also presented.

A new approach is presented to the problem of estimating the directions-of-arrival and the frequencies of multiple narrowband sources--the so-called 2-D harmonic retrieval problem. The approach presented applies to the general case of correlated sources and includes multipath propagation as a special case. The estimators presented yield high resolution and asymptotically unbiased estimates of the directions-of-arrival and frequencies of the impinging sources and enable trade-offs between resolution and accuracy.

This short paper presents a performance comparison of several recently proposed spectral estimation methods for short data lengths. The performance measures used are bias and variance of the estimate as obtained in simulations. The results show that the forward and backward prediction method is better than the forward prediction method, and Ulrych and Clayton's method [11 appears to perform better than Cadzow's ARMA technique [ Z ] . A modified form of Ulrych and Clayton's method, which exploits the symmetry in the AR coeffiecients that exists in the special case of sinusoids, is proposed and its performance is evaluated.

It is known that a covariance matrix of a stationary discrete-time process can be uniquely characterized by a set of partial correlation coefficients (or matrices, for a vector process) which can be efficiently computed by the Levinson, or better by the Schur algorithm, each requiring O(N2) operations for an N×N covariance matrix. In this paper we point out that the same is true for any covariance matrix, stationary or not, but the corresponding nonstationary Levinson- and Schur-type algorithms require O(N3) operations which is the same amount as required by any direct method of matrix inversion. However, by introducing a classification of processes in terms of their closeness to stationarity we can obtain natural extensions of the stationary algorithms that now require only O(αN2) operations, where α is our measure of closeness to stationarity. As in the stationary case, both algorithms can be implemented by a cascade of time-invariant ladder (or lattice) sections. Some implications for the definition of a power spectral density of α-stationary processes are also noted.

The Levinson algorithm, implemented via a ladder filter, has been widely used in seismic signal processing and more recently in speech analysis. This algorithm was originally developed (in 1947) for prediction of stationary stochastic processes. It has been adapted to applications where only a single sample function (time-series) is available by the use of appropriate "window functions" to "simulate stationarity". Such windowing is often somewhat artificial and can introduce undesirable artefacts in situations where only a limited amount of data is available. However, more realistic "windowing" will destroy the analogy to the stationary stochastic process case and thus apparently prohibit use of the Levinson-ladder- filter implementations. In this talk, we shall first show how by using a concept of how close a given process is to being stationary, we can develop generalized Levinson algorithms and generalized ladder filters applicable to any stochastic process, stationary or not. The complexity of the algorithm and the filter is proportional to the distance from stationarity of the given process. We shall then show that this structure can include analyses of several windowing strategies for applications where only a single observed record is available, thus including results obtained earlier for such problems by Morf, Vieira and Lee. The present results are based on work with D. Lee and H. Lev-Ari.

Given a wide-sense forwards Markovian model, namely a state-space system driven by a white-noise process that is uncorrelated with the random initial state of the system, several papers have shown how to obtain a corresponding {\sl backwards} Markovian model: a system driven backwards in time from a 'terminal' state by a white-noise process that is uncorrelated with this state, and such that the joint second-order statistics of the backwards-model state and output processes equal those of the corresponding forwards-model processes. A very direct derivation is presented that shows in effect how a simple rearrangement of the forwards

A new implementation is presented for the optimum likelihood ratio detector for stationary Gaussian signals in white Gaussian noise that uses only two causal time-invariant filters. This solution also has the advantage that fast algorithms based on the Levinson and Chandrasekhar equations can he used for the determination of these time-invariant filters. By using a notion of "closeness to stationarity,' there is a natural extension of the above results for nonstationary signal processes.

A state-space model of a second-order random process is a representation as a linear combination of a set of state-variables which obey first-order linear differential equations driven by an input process that is both white and uncorrelated with the initial values of the state-variables. Such a representation is often called a Markovian representation. There are applications in which it is useful to consider time running backwards and to obtain corresponding backwards Markovian representations. Except in one very special circumstance, these backwards representations cannot be obtained simply by just reversing the direction of time in a forwards Markovian representation. We show how this problem can be solved, give some examples, and also illustrate how the backwards model can be used to clarify certain least squares smoothing formulas.

In analogy with the Wiener-Itô theory of multiple integrals and orthogonal polynominals, a set of functionals of general square-integrable martingales is presented which, in the case of independent-increments processes, is orthogonal and complete in the sense that everyL^{2}-functional of the independent-increment process can be represented as an infinite sum of these elementary functionals. The functionals are iterated integrals of the basic martingales, similar to the multiple iterated integrals of Itô and can be also thought of as being the analogs of the powers1,x,x^{2}, \cdotsof the usual calculus. The analogy is made even clearer by observing that expanding the Doleans-Dade formula for the exponential of the process in a Taylor-like series leads again to the above elementary functionals. A recursive formula for these functionals in terms of the basic martingale and of lower order functionals is given, and several connections with the theory of reproducing kernel Hilbert spaces associated with independent-increment processes are obtained.

The theory of reproducing kernel Hilbert spaces is used to obtain a simple but formal expression for the likelihood ratio (LR) for discriminating between two Gaussian processes with unequal covariances, and to develop a test by which the formal expression can be checked for validity. This LR formula can be evaluated by working separately with each covariance, thus reducing the calculations for the random signal case to those for the simpler known signal problem. In contrast, all previous LR formulas for the unequal covariance problem seem to require calculations involving both covariances simultaneously.

We apply some recent results in martingale theory and the innovations method to obtain the evolution of the conditional mean and conditional density of a process that modulates the rate of a counting process.

We treat the problem of modeling events happening randomly in time at a rate determined by some other random "signal" process. It is shown that a martingale model includes all previously proposed models for such problems and also covers the difficult case of "past-dependent" signals that arises in feedback communication and control problems. It turns out that this model is very similar to the well-known signal-in-additive-white-Gaussian-noise model, so that it can be used conveniently in solving problems of detection of signals in jump processes and estimation of signals from jump processes.

Developments in the theory of linear least-squares estimation in the last thirty years or so are outlined. Particular attention is paid to early mathematica[ work in the field and to more modern developments showing some of the many connections between least-squares filtering and other fields.

It is shown how certain innovations decompositions can be used to obtain aa alternative derivation of some new estimating algorithms, based on Chandrasekhar-type equation. Such equations were originally obtained in radiative-transfer theory by using some invariance principles due to Ambartsumian and Chandrasekhar. Stationary processes have a natural shift invariance, but we show here how state-space descriptions can be used to bring out such invariances for nonstationary processes generated as the response to white noise of constant-parameter state-space models.

We introduce the reproducing-kernel Hilbert space (RKHS) associated with the characteristic functional of a random process and use it to develop a general RKHS theory for non-Gaussian detection. Previously known results for choosing between processes with Gaussian and Poisson statistics are obtained as specializations of this theory.

Using reproducing-kernel Hilbert space (RKHS) techniques, we obtain new results for three different parameter estimation problems. The new results are 1) an explicit formula for the minimum-variance unbiased estimate of the arrival time of a step function in white Gaussian noise, 2) a new interpretation of the Bhattacharyya bounds on the variance of an unbiased estimate of a function of regression coefficients, and 3) a concise formula for the Cramér-Rao bound on the variance of an unbiased estimate of a parameter determining the covariance of a zero-mean Gaussian process.

Recursive least-squares estimates for processes that can be generated from finite-dimensional linear systems are usually obtained via ann \times nmatrix Riccati differential equation, wherenis the dimension of the state space. In general, this requires the solution ofn(n + 1)/2simultaneous nonlinear differential equations. For constant parameter systems, we present some new algorithms that in several cases require only the solution of less than2nporn(m + p)simultaneous nonlinear differential equations, wheremandpare the dimensions of the input and observation processes, respectively. These differential equations are said to be of Chandrasekhar type, because they are similar to certain equations introduced in 1948 by the astrophysicist S. Chandrasekhar, to solve finite-interval Wiener-Hopf equations arising in radiative transfer. Our algorithms yield the gain matrix for the Kalman filter directly without having to solve separately for the error-covariance matrix and potentially have other computational benefits. The simple method used to derive them also suggests various extensions, for example, to the solution of nonsymmetric Riccati equations.

The concept of a white Gaussian noise (WGN) innovations process has been used in a number of detection and estimation problems. However, there is fundamentally no special reason why WGN should be preferred over any other process, say, for example, an nth-order stationary autoregressive process. In this paper, we show that by working with the proper metric, any Gaussian process can be used as the innovations process. The proper metric is that of the associated reproducing kernel Hilbert space. This is not unexpected, but what is unexpected is that in this metric some basic concepts, like that of a causal operator and the distinction between a causal and a Volterra operator, have to be carefully reexamined and defined more precisely and more generally. It is shown that if the problem of deciding between two Gaussian processes is nonsingular, then there exists a causal (properly defined) and causally invertible transformation between them. Thus either process can be regarded as a generalized innovations process. As an application, it is shown that the likelihood ratio (LR) for two arbitrary Gaussian processes can, when it exists, be written in the same form as the LR for a known signal in colored Gaussian noise. This generalizes a similar result obtained earlier for white noise. The methods of Gohberg and Krein, as specialized to reproducing kernel spaces, are heavily used.

We first show how reproducing kernel Hilbert space (RKHS) norms can be determined for a large class of covariance functions by methods based on the solution of a Riccati differential equation or a Wiener-Hopf integral equation. Efficient numerical algorithms for such equations have been extensively studied, especially in the control literature. The innovations representations enter in that it is they that suggest the form of the RKHS norms. From the RKHS norms, we show how recursive solutions can be obtained for certain Fredholm equations of the first kind that are widely used in certain approaches to detection theory. Our approach specifies a unique solution: moreover, the algorithms used are well suited to the treatment of increasing observation intervals.

First it is shown how the Karhunen-Loève approach to the detection of a deterministic signal can be given a coordinate-free and geometric interpretation in a particular Hilbert space of functions that is uniquely determined by the covariance function of the additive Gaussian noise. This Hilbert space, which is called a reproducing-kernel Hilbert space (RKHS), has many special properties that appear to make it a natural space of functions to associate with a second-order random process. A mapping between the RKHS and the linear Hilbert space of random variables generated by the random process is studied in some detail. This mapping enables one to give a geometric treatment of the detection problem. The relations to the usual integral-equation approach to this problem are also discussed. Some of the special properties of the RKHS are developed and then used to study the singularity and stability of the detection problem and also to suggest simple means of approximating the detectability of the signal. The RKHS for several multidimensional and multivariable processes is presented; by going to the RKHS of functionals rather than functions it is also shown how generalized random processes, including white noise and stationary processes whose spectra grow at infinity, are treated.

We give a comprehensive discussion of the structure of the likelihood ratio (LR) for discrimination between two Gaussian processes, one of which is white. Several more general problems can be reduced, usually by differentiation, to this form. We shall show that nonsingular detection problems of this form can always be interpreted as problems of the apparently more special "signal-in-noise" type, where the cross-covariance function of the signal and noise must be of a special "one-sided" form. Moreover, the LR for this equivalent problem can be written in the same form as that for known signals in white Gaussian noise, with the causal estimate of the signal process replacing the known signal. This single formula will be shown to be equivalent to a variety of other formulas, including all those previously known. The proofs are based on a resolvent identity and on a representation theorem for second-order processes, both of which have other applications. This paper also contains a discussion of the various stochastic integrals and infinite determinants that arise in Gaussian detection problems

A general likelihood ratio formula of the author's for the detection of signals in independent white Gaussian noise is extended to allow a "one-sided" dependence in which only the future white noise is required to be independent of past signal and noise. The assumption of Gaussian additive noise is also somewhat relaxed. The proof is based on some recent martingale theorems and on the concept of the innovations process.

It is shown that the likelihood ratio for the detection of a random, not necessarily Gaussian, signal in additive white Gaussian noise has the same form as that for a known signal in white Gaussian noise. The role of the known signal is played by the casual least-squares estimate of the signal from the observations. However, the "correlation" integral has to be interpreted in a special sense as an Itô stochastic integral. It will be shown that the formula includes all known explicit formulas for signals in white Gaussian noise. However, and more important, the formula suggests an "estimator-correlator" philosophy for engineering approximation of the optimum receiver. Some extensions of the above result are also discussed, e.g., additive finite-variance, not necessarily Gaussian, noise plus a white Gaussian noise component. Purely colored Gaussian noise can be treated if whitening filters can be specified. The analog implementation of Itô integrals is briefly discussed. The proofs of the formulas are based on the concept of an innovation process, which has been useful in certain related problems of linear and nonlinear least-squares estimation, and on the concept of covariance factorization.

We shall show that the solution of Fredholm equations with symmetric kernels of a certain type can be reduced to the solution of a related Wiener-Hopf integral equation. A least-squares filtering problem is associated with this equation. When the kernel has a separable form, this related problem suggests that the solution can be obtained via a matrix Riccati differential equation, which may be a more convenient form for digital computer evaluation. The Fredholm determinant is also expressed in terms of the solution to the Riccati equation; this formula can also be used for the numerical determination of eigenvalues. The relations to similar work by Anderson and Moore and by Schumitzky are also discussed.

The problem of the detection of known signals in colored Gaussian noise is usually studied through infinite-series representations for the signals and noise. In particular, the Karhunen-Loève (K-L) expansion is often used for this purpose. Such infinite-series methods, while elegant, often introduce mathematical complications because they raise questions of convergence, interchange of orders of integration, etc. The resolution of these problems is difficult and has led, when the K-L expansion is used, to the introduction of subsidiary conditions whose physical meaning is often unclear. We present a method of reducing the detection problem to a finite-dimensional form where many of the difficulties with the infinite-series K-L expansion do not arise. The resulting simplicity provides more direct derivations of and more physical insights into several earlier results. It has also suggested some new results. The method is essentially based on the use of a projection in a special kind of Hilbert space called a reproducing kernel Hilbert space.

Fredholm integral equations of the first and second kind arise in many problems in statistical communication theory. However, almost all cases in which solutions are known, for equations over finite intervals, involve covariance kernels with rational Fourier transforms. We present solutions for two classes of "non-rational" kernels--triangular kernels of the formR(t) = \max [0, 1 - |t|]and Gauss-Markov kernels of the formR(t, s) = f(t)g(s), t \leq s, R(t, s) = f(s)g(t), s \leq t. We also treat kernels that are combinations of the two types.

In some communication problems, it is a good assumption that the channel consists of an additive white Gaussian noise forward link and an essentially noiseless feedback link. In this paper, we study channels where no bandwidth constraint is placed on the transmitted signals. Such channels arise in space communications. It is known that the availability of the feedback link cannot increase the channel capacity of the noisy forward link, but it can considerably reduce the coding effort required to achieve a given level of performance. We present a coding scheme that exploits the feedback to achieve considerable reductions in coding and decoding complexity and delay over what would be needed for comparable performance with the best known (simplex) codes for the one-way channel. Our scheme, which was motivated by the Robbins-Monro stochastic approximation technique, can also be used over channels where the additive noise is not Gaussian but is still independent from instant to instant. An extension of the scheme for channels with limited signal bandwidth is presented in a companion paper (Part II).

We discuss the problems of making detailed measurements of instantaneous values and the statistical parameters of time-variant filters when observations are permitted at the filter terminals only. It appears that the product of the maximum time- and frequency-spreadings produced by the time-variant filter sets a limit on our ability to determine the instantaneous values unambiguously even in the absence of additive noise. This limit can be relaxed when it comes to determining average or statistical parameters of the filter. For the determination of second-order filter statistics a fourth-moment method is presented that exhibits some novel aspects.

We show that the concept of correlation detection of deterministic signals in additive Gaussian noise can be extended in a natural manner to the detection of signals that are transmitted through a "Gaussian" random channel besides being corrupted by additive Gaussian noise. Such situations are typical in communication over scatter-multipath channels (with or without a specular component). In the deterministic case, the receiver essentially crosscorrelates the received signal with the signal before the additive noise was introduced. When a random channel is present, however, this latter signal, i.e., the output of the random channel, is not known at the receiver, However, knowing the statistics of the channel and the noise, the receiver can make an estimate of it from the received signal on the hypothesis that a particular signal was transmitted. The optimum receiver then crosscorrelates this estimate with the received signal.