Multichannel recursive least squares adaptive filtering without adesired signal

The author presents a pair of adaptive QR decomposition-based algorithms for the adaptive mixed filter in which no desired signal is available, but the signal-to-data cross-correlation vector is known. The algorithms are derived by formulating the recursive mixed filter as a least-squares problem and then applying orthogonal QR-based techniques in its solution. This leads to algorithms with the performance, numerical, and structural advantages of the RLS/ QR algorithm, but without the requirement of a desired signal. Both Givens and square-root-free Givens rotations are used in implementing the recursive QR decomposition. Because of their structural regularity, the algorithms are easily implemented by triangular systolic array structures. Simulations show that these algorithms require fewer computations and less precision than recursive sample matrix inversion approaches     

Multiphase systolic algorithms for spectral decomposition

The authors propose two multiphase systolic algorithms to solve the spectral decomposition problem based on the QR algorithm. The spectral decomposition is one of the most computationally intensive modern signal processing operations. While the QR algorithm is well known to be an effective method to solve the eigenvalue problem, there is still no single systolic array architecture that can compute the unitary Q matrix readily and perform the QR algorithm efficiently. Previous methods using the QR algorithm had communication problems among different architectures. Two arrays, a triangular and a rectangular, are presented to implement the multiphase algorithms. Details on these multiphase operations of the QR algorithm as well as architectural consequences and performance evaluation are discussed. Efficient fault-tolerant schemes for these multiphase operations are also considered     

Systolic array designs for Kalman filtering

Systolic Kalman filter (SKF) designs based on a triangular array (triarray) configuration are presented. A least squares formulation, which is an expanded matrix representation of the state space iteration, is adopted to develop an efficient iterative QR triangularization and consecutive data prewhitening formulations. This formulation has advantages in both numerical accuracy and processor utilization efficiency. Moreover, it leads naturally to pipelined architectures such as systolic or wavefront arrays. For an n state and m measurement dynamic system, the SKF triarray design uses n(n+3)/2 processors and requires only 4n+m timesteps to complete one iteration of prewhitened Kalman filtering system. This means a speedup factor of approximately n²/4 when compared with a sequential processor. Also proposed for the colored noise case are data prewhitening triarrays which offer compatible speedup performance for the preprocessing stage. Based on a comparison of several competing alternatives, the proposed array processor may be considered a most efficient systolic or wavefront design for Kalman filtering     

A Taylor synthesis for principal solution patterns ofmultiplicative antenna systems

A multiplicative (cross-correlation) receiving antenna system with a linear aperture can have a power pattern P₀(u ) (the so-called principal-solution power pattern) whose spatial frequency transfer function (SFTF) is uniform over the entire spatial frequency (SF) bandwidth. A modified principal solution system which retains the uniform SFTF except for smooth transitions at the ends of the SF passband is described. The transitions are due to a change in the original pattern P₀(u), which suffers from high sidelobes, to a Taylor (1955) synthesis pattern P_T (u) which involves a slowly varying envelope pattern. All of the slowly varying envelope sidelobes of P_T(u ) are set at the same appropriate low level, e.g. -30 dB. The aperture weighting distributions are free of singularities, unlike those for P₀(u), and can be sampled to provide the current weightings for a linear multiplicative array     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible     

An improved systolic architecture for 2-D digital filters

An improved systolic architecture for two-dimensional infinite-impulse response (IIR) and finite-impulse-response (FIR) digital filters is presented. Comparisons with recently published work are made. When compared with the architecture of M.A. Sid-Ahmed (1989), a substantial reduction in the number of delay elements is observed. This reduction is of the order of 10² for a 2-D IIR filter and equals N+1 for an Nth-order 2-D FIR filter. The clock period has been made independent of the order of the filter. The speed-up factor is the maximum achievable and is independent of the filter order. Comparison with the work of S. Sunder et al. (1990) shows an improvement in the latency of the systolic array, which has been reduced from 1 to 0. A reduction of N+1 delay elements has been achieved for the FIR filter. An error analysis for the architecture is made     

An updating algorithm for subspace tracking

In certain signal processing applications it is required to compute the null space of a matrix whose rows are samples of a signal with p components. The usual tool for doing this is the singular value decomposition. However, the singular value decomposition has the drawback that it requires O(p³) operations to recompute when a new sample arrives. It is shown that a different decomposition, called the URV decomposition, is equally effective in exhibiting the null space and can be updated in O( p²) time. The updating technique can be run on a linear array of p processors in O(p) time     

Design and implementation of a general-purpose median filter unitin CMOS VLSI

A general-purpose median filter unit configuration in the form of two single-chip median filters, one extensible and one real time, is described. The networks of the chips are pipelined and systolic at bit level and based on odd/even transposition sorting. The chips are implemented in 3-μm standard CMOS using full-custom VLSI design techniques. The exact median of elements, in a window size w=9 with arbitrary word length L, can be found using only one extensible median filter chip. The filter can be extended to arbitrary window size and word lengths by using many chips. Simulation results show that the extensible median filter chip can be clocked up to 40 MHz and can generate 30/L megamedians per second. The real-time median filter chip can find the exact running medians of elements in a window of a fixed size w=9 with L=8. Simulations show that it can generate up to 50 megamedians per second with a 50-MHz clock. The algorithms, VLSI implementations, and chip test results are presented, along with some possible applications     

The generalized eigenproblem: pole-zero computation

A modification-decomposition (MD) method is used to compute linear system transfer function poles and zeros by transforming an N-dimensional generalized eigenvalue problem to an M-dimensional standard eigenvalue problem with M⩾ r, where r is the lesser of the ranks of the dynamic or nondynamic component matrix of the system. Hence, network eigenvalue problems normally solved by applying the QZ algorithm directly, or after deflation preprocessing, are solvable with the more efficient QR algorithm. It is shown that the flop (floating-point operations) count for MD-QR algorithms is always less than the flop count for the most efficient deflation-QZ algorithms. For r⩽N, the MD-QR algorithms are exceptionally efficient. Using a parameter matrix decomposition of the dynamic or nondynamic component matrix, the MD method gives physical insight, and it provides a general proof of manifold constraints relating network time constants and poles and zeros. From these relations, accurate dominant and subdominant pole approximations are derived. A general eigenvalue sensitivity formula and a very flexible method for computing eigenvectors is developed and applied to pole sensitivity computation     

A system for systolic modules for the MUSIC algorithm

The authors believe that special-purpose architectures for digital signal processing (DSP) real-time applications will use closely coupled processing elements as array processor modules to implement the various portions of the new algorithms, and several such modules will cooperate in a pipelined manner to implement complete algorithms. Such an architecture, based upon systolic modules, for the MUSIC algorithm is presented. The architecture is suitable for VLSI implementation. The throughput of the pipelined approach is O(N), whereas the sequential approach is O(N³)     

In the optimum design of the block adaptive FIR digital filter

A general optimum block adaptive (GOBA) algorithm for adaptive FIR (finite impulse response) filtering is presented. In this algorithm, the correction terms for the filter coefficients in each block, instead of the convergence factors, are optimized in a least squares sense. There are no constraints on the block length L and the filter tap number N. It is shown that the GOBA algorithm is reduced to the normalized LMS algorithm when L⩾N. The convergence of the GOBA algorithm can be assured if the correlation matrix of the input signal is positive definite. Computer simulations based on an efficient computing procedure confirm that the GOBA algorithm achieves faster convergence with slightly degraded convergence accuracy in stationary environments and better weight tracking capability in nonstationary environments as compared to existing block adaptive algorithms with no constraints on L and N     

On the LP which finds a MMAE stack filter

Two methods are proposed to modify the linear program (LP) developed by E.J. Coyle and J.-H. Lin (1988) to find a stack filter which minimizes the mean absolute error (MAE). In the first approach, the number of constraints is substantially reduced at the expense of requiring a zero-one LP to solve for an optimal filter. This scheme reduces the number of constraints from O(n2ⁿ) to O(28ⁿ), which is exactly the cardinality of the set of possible binary vectors which can appear in the window of the filter. In the second approach, the LP is transformed into a max-flow problem. This guarantees that the problem can be solved in time which is a polynomial function of the number of variables in the LP, as opposed to the worst-case exponential time that may occur with the simplex method. It also allows the many fast algorithms for the max-flow problem to be used to find an optimal stack filter. Recursive algorithms for construction of the window width n constraint matrix for both the original LP and the max-flow modification are also provided     

Block 2-D interpolation, efficient matrix factorization andapplication to signal processing

A block 2-D decomposition and a new block LU matrix factorization based on a Newton approach are presented for solving quickly and efficiently polynomial or exponential 2-D interpolation problems. The sample grids under consideration are described by the product representation {x₀, x₁, . . ., x_n} x{y₀, y ₁, . . ., y_m}, where the x grid and the y-grid are not necessarily uniformly spaced. The attractive features of the method are the inherent efficient parallelism, the reduced computational requirements needed for the LU decomposition, and the capability of implementation of 1-D fast and accurate algorithms. The proposed method can be used for modeling 2-D discrete signals, designing 2-D FIR filters, 2-D Fourier matrix factorization, 2-D DFT, etc     

Numerical analysis of electromagnetic scattering by electricallylarge objects using spatial decomposition technique

Apparent computational difficulties with the direct integral equation and method of moments have prompted an alternative numerical solution procedure based on the spatial decomposition technique. Using rigorous electromagnetic equivalence, the spatial decomposition technique virtually divides an electrically large object into a multiplicity of subzones. It permits the maximum size of the method of moments system matrix that needs to be inverted to be strictly limited, regardless of the electrical size of the large scattering object being modeled. The requirement on the computer resources is O(N ), where N is the number of spatial subzones and each subzone is electrically small, spanning on the order of a few wavelengths. Numerical examples are reported along with comparative data and relative error estimation to expose the applicability and limitations of the spatial decomposition technique for the two-dimensional scattering study of electrically large conducting and dielectric objects     

Parallel VLSI matrix pencil algorithm for high resolution directionfinding

Algorithms to find the directions of arrival (DOAs) of multiple signals from measurements on an array of antenna doublets (ESPRIT method) and their parallel VLSI implementation are discussed. In particular, algorithms that allow large-scale pipelining and use only robust, unitary transformations are identified. This problem is solved by a matrix pencil approach in which the generalized eigenvalues of a pair of data matrices are determined. A modified Stewart Jacobi approach is used for which convergence is improved and parameter computations are simplified. The resulting architecture is a two-layer Jacobi array that can handle all the subproblems: two QR factorizations, two SVDs, and a single generalized Schur decomposition. The mapping of the subproblems on a single parallel array of CORDIC processors is considered     

Superresolution by structured matrix approximation

The bearing estimation problem is formulated as a matrix-approximation problem. The columns of a matrix X are formed by the snapshot vectors from an N-element array. The matrix X is then approximated by a matrix in the least-square sense. The rank as well as the partial structure of the space spanned by the columns of the approximated X matrix are prespecified. After the approximated X matrix is computed, the bearings of the sources and, consequently, the spatial correlation of the source signals are estimated. The performance of the proposed technique is compared with two existing methods using simulation. The comparison is made in terms of bias, mean-squared error, failure rates, and confidence intervals for the mean and the variance estimates for all three methods at different signal-to-noise ratios. When the sources are moving slowly and the number of snapshot vectors available for processing is large, a simple online adaptive algorithm is suggested     

Quadtree-structured recursive plane decomposition coding of images

The approximation of two-dimensional highly correlated grey value functions can be performed using a linear model of the type f( x, y)=a+bx+cy. The set of plane parameters (PPs) [a, b, c] can be determined in the least squares sense for a block of size N×N pixels, for example. Starting with a block size of 2×2 pixels, it is shown that the PPs obey a recursive law such that the PPs of a 2N×2N block can be computed recursively when only the PPs of the four adjacent subblocks of size N×N in the lower decomposition level are known. This concept of recursive plane decomposition (RPD) is embedded in a quadtree data structure to obtain a new variable block size image coding algorithm that offers a high performance at a low computational cost. Extensive comparisons to other state-of-the-art image coding algorithms are reported     

Maximum-rank array codes and their application to crisscross errorcorrection

A μ-[n×n,k] array code C over a field F is a k-dimensional linear space of n×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k⩽n(n-μ+1). A family of so-called maximum-rank μ-[n×n,k=n ( n-μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C, given a received array Γ+E, where rank (E)+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n×n. . .×n hyper-arrays     

Regularized fast recursive least squares algorithms for finitememory filtering

Novel fast recursive least squares algorithms are developed for finite memory filtering, by using a sliding data window. These algorithms allow the use of statistical priors about the solution, and they maintain a balance between a priori and data information. They are well suited for computing a regularized solution, which has better numerical stability properties than the conventional least squares solution. The algorithms have a general matrix formulation, such that the same equations are suitable for the prewindowed as well as the covariance case, regardless of the a priori information used. Only the initialization step and the numerical complexity change through the dimensions of the intervening matrix variables. The lower bound of O (16m) is achieved in the prewindowed case when the estimated coefficients are assumed to be uncorrelated, m being the order of the estimated model. It is shown that a saving of 2m multiplications per recursion can always be obtained. The lower bound of the resulting numerical complexity becomes O(14m ), but then the general matrix formulation is lost     

A fast quasi-Newton adaptive filtering algorithm

The convergence rate of an adaptive system is closely related to its ability to track a time-varying optimum. Basic adaptive filtering algorithms give poor convergence performance when the input to the adaptive system is colored. More sophisticated algorithms which converge very rapidly regardless of the input spectrum algorithms typically require O(N²) computation, where N is the order of the adaptive filter, a significant disadvantage for real-time applications. Also, many of these algorithms behave poorly in finite-precision implementation. An adaptive filtering algorithm is introduced which employs a quasi-Newton approach to give rapid convergence even with colored inputs. The algorithm achieves an overall computational requirement of O(N) and appears to be quite robust in finite-precision implementations