VLSI algorithms and architectures for complex householder transformation with applications to array processing

The Householder transformation is considered to be desirable among various unitary transformations due to its superior computational efficiency and robust numerical stability. Specifically, the Householder transformation outperforms the Givens rotation and the modified Gram-Schmidt methods in numerical stability under finite-precision implementations, as well as requiring fewer arithmetical operations. Consequently, the QR decomposition based on the Householder transformation is promising for VLSI implementation and real-time high throughput modern signal processing. In this paper, a recursive complex Householder transformation (CHT) with a fast initialization algorithm is proposed and its associated parallel/pipelined architecture is also considered. Then, a CHT based recursive least-squares algorithm with a fast initialization is presented. Its associated systolic array processing architecture is also considered.This work was supported in part of the National Science Council of the R.O.C. under grant NSC80-E-SP-009-01A.This work was supported in part by a UC Micro grant and NSF grant NCR-8814407.     

Systolic implementations of up/down-dating cholesky factorization using vectorized Gram-Schmidt pseudo orthoganalization

We propose a new class ofhyperbolic Gram-Schmidt methods to simultaneously update and downdate the Cholesky factor of a sample covariance matrix efficiently with applications to sliding window recursive least squares (RLS) filtering problems. Several vectorized versions of this Gram-Schmidt approach are introduced, which include conventional column-updating, modified row/column-updating, and square-root-free methods. Comparisons to the existing known methods, such as Householder transformation and Givens rotation, are also given. Upon further reformulating these algorithms, a systolic triarray structure is proposed to facilitate VLSI implementations.This work is partially supported by a UC MICRO grant and the NSF grant NCR-8814407. It is also partially supported by NSF grant ECD-8803012-06.     

Adaptive set-membership identification in O(m)time for linear-in-parameters models

Some fundamental contributions to the theory and applicability of optimal bounding ellipsoid (OBE) algorithms for signal processing are described. All reported OBE algorithms are placed in a general framework that demonstrates the relationship between the set-membership principles and least square error identification. Within this framework, flexible measures for adding explicit adaptation capability are formulated and demonstrated through simulation. Computational complexity analysis of OBE algorithms reveals that they are of O(m²) complexity per data sample with m the number of parameters identified. Two very different approaches are described for rendering a specific OBE algorithm, the set-membership weighted recursive least squares algorithm, of O(m) complexity. The first approach involves an algorithmic solution in which a suboptimal test for innovation is employed. The performance is demonstrated through simulation. The second method is an architectural approach in which complexity is reduced through parallel competition     

Multiweight optimization in optimal bounding ellipsoid algorithms

Optimal Bounding Ellipsoid (OBE) algorithms offer an attractive alternative to traditional least-squares methods for identification and filtering problems involving affine-in-parameters signal and system models. The benefits-including low computational efficiency, superior tracking ability, and selective updating that permits processor multi-tasking-are enhanced by multiweight (MW) optimization in which the data history is considered in determining update times and optimal weights on the observations. MW optimization for OBE algorithms is introduced, and an example MW-OBE algorithm implementation is developed around the recent quasi-OBE algorithm. Optimality of the solution is discussed, and simulation studies are used to illustrate performance benefits.     

Efficient solutions to multicast routing in communication networks

An important problem in both wireless and wired communication networks is to be able to efficiently multicst information to a group of network sites. Multicasting reduces the transmission overhead of both wireless and wired networks and the time it takes for all the nodes in the subset to receive the information. Since transmission bandwidth is a scarce commodity especially in wireless networks, efficient and near minimum-cost multicast algorithms are particularly useful in the wireless context. In this paper, we discuss methods of establishing efficient and near minimum-cost multicast routing in communication networks. In particular, we discuss an efficient implementation of a widely used multicast routing method which can construct a multicast tree with a cost no greater than twice the cost of an optimal tree. We also present two efficient multicast tree constructions for a general version of the multicast routing problem in which a network consists of different classes of nodes, where each class can have one or more nodes of the same characteristic which is different from the characteristics of nodes from other classes. Because of their efficient running times, these multicast routing methods are particularly useful in the mobile communication environments where topology changes will imply recomputation of the multicast trees. Furthermore, the proposed efficient and near minimum-cost multicast routing methods are particularly suited to the wireless communication environments, where transmission bandwidth is more scarce than wired communication environments.Partially supported by NSF/LaSER under grant number EHR-9108765, by LEQSF grant number 94-RD-A-39, by NASA under grant number NAG 5-2842.     

System identification techniques for adaptive signal processing

Many problems in adaptive filtering can be approached from the point of view of system identification. The close interconnection between these two disciplines is explored in some detail. This approach makes it possible to apply recursive parameter estimation algorithms to adaptive signal processing. Several examples are discussed including: adaptive line enhancement, generalized adaptive noise cancelling, adaptive deconvolution and adaptive TDOA estimation. It is shown how the recursive maximum likelihood algorithm can be used for both FIR and IIR filtering, and some preliminary results are presented. Several alternative algorithms are briefly discussed.This work was supported by the Office of Naval Research, Contract No. N00014-79-C-0743.     

A methodology for fast scheduling of partitioned systolic algorithms

Various methods for mapping signal processing algorithms into systolic arrays have been developed in the past few years. In this paper, efficient scheduling techniques are developed for the partitioning problem, i.e. problems with size that do not match the array size. In particular, scheduling for the Locally Parallel-Globally Sequential (LPGS) technique and the Locally Sequential-Globally Parallel (LSGP) technique are developed. The scheduling procedure developed exploits the fact that after LPGS and LSGP partitioning, the locality constraints are less stringent allowing for more flexibility in the choice of algorithms and inter-processor communication. A flexible scheduling order is developed that is useful in evaluating the trade-off between execution time and size of storage buffers. The benefits of the scheduling techniques are illustrated with the help of matrix multiplication and least squares examples. This work was supported in part by the UCSD/NSF Integrated Circuits And Systems Research Center and by the ARMY Research Office under Grant No. DAAL-03-90-G-0095.     

On fast algorithms for one-dimensional digital signal processing in finite integer and complex integer rings

In this work, we present and analyze a number theoretic approach to computing one-dimensional cyclic convolution of sequences defined in finite integer and complex integer rings. A fundamental result of this work is that under the nonrestrictive condition, (N, M)=1, the algorithms defined in finite integer and complex integer rings are as intensive computationally as the corresponding algorithms defined in rational and complex rational number systems only in the worst case. They simplify considerably for a large number of cases of importance in digital signal processing.This research work is supported by the National University of Singapore under its Academic Research Fund, grant no. RP960699.     

Analysis of finite precision effects on a recursive set membershipparameter estimation algorithm

Analysis of error propagation in an optimal bounding ellipsoid (OBE) algorithm is performed which shows that the errors in the estimates due to an initial perturbation are bounded. Simulation results demonstrate that the OBE algorithm can perform better than the conventional recursive least squares (RLS) in small wordlength environments. The analysis presented could also be applied for the finite-precision analysis of recursive weighted least squares algorithms     

Image restoration using a conjugate gradient-based adaptive filtering algorithm

A new two-dimensional (2D) sample-based conjugate gradient (SCG) algorithm is developed for adaptive filtering. This algorithm is based on the conjugate gradient method of optimization and therefore has a fast convergence characteristic. The SCG is computationally simpler than the recursive least squares (RLS) algorithm. The SCG algorithm with the equation-error and output-error methods is investigated for application in image restoration. Simulation results show that the new algorithm significantly outperforms existing algorithms in the restoration of noisy images.This work was supported in part by a grant from the Colorado Advanced Software Institute.     

Power dissipation of VLSI array processing systems

The Power Factor Approximation (PFA) power estimation method is reviewed and applied to VLSI array processing systems. The power dissipation of 1, 2, and 3 dimensional algorithms implemented on linear, hexagonal, and cubic processor arrays is investigated. Closed form equations are developed which show how the overall power dissipation is influenced by an algorithm's size and dimensionality, the target array processor's size and dimensionality, and the adopted partitioning strategy. The power estimation methods developed in this paper can be applied in the early phases of VLSI algorithm/architecture design, selection, and partitionment. The power dissipation of a matrix-matrix multiplication operation is estimated as an example application.This work was supported in part by the Hughes Aircraft Company fellowship program and the NSF initiation grant MIP-99-10437.     

Least-square identification with error bounds for real-time signalprocessing and control

Set-membership (SM) identification, which refers to a class of algorithms using certain a priori knowledge about a parametric model to constrain the solutions to certain sets, is considered. The focus is on a class of SM-based techniques that are of particular interest in applications requiring real-time processing. The optimal bounding ellipsoid (OBE) algorithms are interpreted as a blending of the classical least-square error minimization approach with knowledge of bounds on model errors arising from SM considerations. Using this interpretation, a general framework embracing all currently used OBE algorithms is developed, and strategies for adaptation and for implementation on parallel machines are discussed. Computational complexity benefits are considered for the various algorithms. The treatment is tutorial, leaving many of the formal details to an appendix that presents an archival theoretical treatment of the key results. A second appendix gives an overview of current research in the general SM identification field     

Fast adaptive algorithms for multichannel filtering and systemidentification

Fast transversal and lattice least squares algorithms for adaptive multichannel filtering and system identification are developed. Models with different orders for input and output channels are allowed. Four topics are considered: multichannel FIR filtering, rational IIR filtering, ARX multichannel system identification, and general linear system identification possessing a certain shift invariance structure. The resulting algorithms can be viewed as fast realizations of the recursive prediction error algorithm. Computational complexity is then reduced by an order of magnitude as compared to standard recursive least squares and stochastic Gauss-Newton methods. The proposed transversal and lattice algorithms rely on suitable order step-up-step-down updating procedures for the computation of the Kalman gain. Stabilizing feedback for the control of numerical errors together with long run simulations are included     

Fast algorithms for the computation of sliding discrete sinusoidal transforms

Fast algorithms for computing various discrete cosine transforms and discrete sine transforms in a sliding window are proposed. The algorithms are based on a recursive relationship between three subsequent local transform spectra. Efficient inverse algorithms for signal processing in a sliding window are also presented. The computational complexity of the algorithms is compared with that of known fast discrete sinusoidal transforms and running recursive algorithms.     

Decentralized array processing using the MODE algorithm

Centralized methods for source location using sensor arrays have computational and communication burdens that increase significantly with the number of sensors in the array. Therefore, these methods may not be usable in the applications involving very large arrays. In such applications, the data processing may need to be decentralized. This paper introduces two methods for decentralized array processing, based on the recently proposed MODE algorithm. For prescribed nonoverlapping subarrays, both methods are shown to be statistically optimal in the sense that asymptotically they provide the most accurate decentralized estimates of source location parameters. The problem of subarray selection to further optimize the estimation accuracy is only briefly addressed. The two methods are intended for different types of applications: the first should be preferred when there exist significant possibilities for local processing or for parallel computation in the central processor; otherwise the second method should be preferred. The accuracy of the two decentralized methods is compared to the centralized Cramér-Rao bound, both analytically and numerically, in order to provide indications about the loss of accuracy associated with decentralized processing.The work of P. Stoica was supported by a grant from the Royal Swedish Academy of Engineering Sciences and by the Swedish Research Council for Engineering Sciences under contract 91-676. The work of A. Nehorai was supported by the Air Force Office of Scientific Research under grant no. AFOSR-90-0164, and by the Office of Naval Research under grant no. N00014-91-J-1298.on leave at the Department of Applied Electronics, Chalmens University of Technology, 2-41296 Göthensberg, Sweeden.     

Array resolutions of linear maps

The identification of concurrency is a critical factor in the high-speed calculation of algorithms. This study considers maps onX, a discrete resolution space. We establish a resolution on the space of linear maps onX which exhibit compatibility with array processing. Our results are extended to the partially ordered resolution space setting. While on-line array processing motivates our study, the results also suggest efficient processing procedures for off-line applications.This work was sponsored in part by NSF Grant 83/6731.     

Fast recursive algorithms for short-time discrete cosine transform

Local adaptive signal processing can be carried out using the short-time discrete cosine transform (DCT). Two fast recursive algorithms for computing the short-time DCT are presented. The algorithms are based on a recursive relationship between three subsequent local DCT spectra. The computational complexity of the algorithms is compared with that of fast DCT algorithms     

Design and applications of a CMOS analog multiplier cell using the differential difference amplifier

This paper presents design techniques for a wide input range CMOS differential difference amplifier (DDA) and discusses its application as a basic block in the implementation of a simple four-quadrant multiplier cell. The cell can be configured as an amplitude modulator or a one-over circuit, which are widely used in many analog signal processing applications. The DDA can also be reconfigured as an opamp, and hence can be used to design many of the opamp-based multiplier circuits. The DDA amplitude modulator (AM) uses a transistor and a resistor as the only components external to the DDA. A DDA one-over circuit, which provides an output proportional to the inverse of the input, is also achieved with the same level of simplicity. High-frequency effects due to the DDA's finite gain-bandwidth (GB) and MOS parasitic capacitances are investigated. Experimental results obtained from a 2µm CMOS MOSIS chip are given.Parts of this work have been presented at the 10th Norchip Seminar, Helsinki, Finland, November 3–4, 1992 and included in the Seminar's proceedings, pp. 9–14. This work was supported in part by the NSF grant MIP-8896244 and by the Semiconductor Research Corporation contracts 90-DJ-066 and 91-DJ-066, and in part by the Norwegian NTNF, SINTEF and Nordic VLSI.     

Restructured recursive DCT and DST algorithms

The discrete cosine transform (DCT) and the discrete sine transform (DST) have found wide applications in speech and image processing, as well as telecommunication signal processing for the purpose of data compression, feature extraction, image reconstruction, and filtering. In this paper, we present new recursive algorithms for the DCT and the DST. The proposed method is based on certain recursive properties of the DCT coefficient matrix, and can be generalized to design recursive algorithms for the 2-D DCT and the 2-D DST. These new structured recursive algorithms are able to decompose the DCT and the DST into two balanced lower-order subproblems in comparison to previous research works. Therefore, when converting our algorithms into hardware implementations, we require fewer hardware components than other recursive algorithms. Finally, we propose two parallel algorithms for accelerating the computation