Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Hsieh, S.F.Subject: search.filters.subject.VLSI architectures

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    VLSI Algorithms and Architectures for Complex Householder Transformation with Applications to Array Processing
    (1991) Tang, C.F.T.; Liu, K.J. Ray; Hsieh, S.F.; Yao, K.; ISR
    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 with a fast initialization algorithm is proposed and its associated parallel/pipelined architecture is also considered. Then, a complex Householder transformation based recursive least-squares algorithm with a fast initialization is presented. Its associated systolic array processing architecture is also considered.
  • Thumbnail Image
    Item
    A Unified Approach for QRD-Based Recursive Least-Squres Estimation without Square Roots
    (1991) Hsieh, S.F.; Liu, K.J. Ray; Yao, K.; ISR
    The QR-decomposition (QRD)-based recursive least-squares (RLS) methods have been shown to be useful and effective towards adaptive signal processing in modern communications, radar, and sonar systems implementable with various modern parallel and systolic array architectures. The planar (Givens) and hyperbolic rotations are the most commonly used methods in performing the QRD up/downdating. But the generic formula for these rotations require explicit square-root (sqrt) computations, which constitute the computational bottleneck and are quite undesirable from the practical VLSI circuit design point of view. There has been more than ten sqrt-free algorithms known so far. In this paper, we provide a unified systematic approach for the sqrt-free QRD-based RLS estimation problem. By properly choosing two parameters, and v, all existing known sqrt-free methods fall in the category of our unified approach. The proposed method not only can generalize all currently known sqrt-free QRD algorithms, but also new sqrt-free algorithms as long as the parameters and v are properly chosen. The unified treatment is also extended to the QRD-based RLS problems for optimal residual acquisition without sqrt operations, and the systolic array implementation.
  • Thumbnail Image
    Item
    Fast Orthogonalization Algorithm and Parallel Implementation for AR Spectral Estimation Based on Forward-Backward Linear Prediction
    (1991) Liu, K.J. Ray; Hsieh, S.F.; ISR
    High-resolution spectral estimation is an important subject in many applications of modern signal processing. The fundamental problem in applying various high-resolution spectral estimation algorithms is the computational complexity. Recently, the truncated QR methods have been shown to be comparable to the SVD- based methods for the sinusoidal frequency estimation based on the forward-backward linear prediction (FBLP) model. However, without exploiting the special structure of the FBLP matrix, the QR decomposition (QRD) of the FBLP matrix has the computational complexity on the order of n cubic for a 2m x n FBLP matrix. Here we propose a fast algorithm to perform the QRD of the FBLP matrix. It is based on exploiting the special Toeplitz-Hankel form of the FBLP matrix. The computational complexity is then reduced to the order of n square. The fast algorithm can also be easily implemented onto a linear systolic array. The number of time steps required is further reduced to 2m + 5n - 4 by using the parallel implementation. The geometric transformation, which improves the numerical stability, for the downdating of the Cholesky factors is also considered.
  • Thumbnail Image
    Item
    Dual-State Systolic Architectures for Adaptive Filtering Using Up/Downdating RLS
    (1991) Hsieh, S.F.; Liu, K.J. Ray; Yao, K.; ISR
    We propose a dual-state systolic structure to perform joint up/down-dating operations encountered in windowed recursive least squares (RLS) estimation problems. It is derived by successively performing Givens rotations for updating and hyperbolic rotations for down-dating. Due to the data independency, a series of Givens and hyperbolic rotations can be interleaved and parallel processing can be achieved by alternatively performing updating and downdating both in time and space. This flip-flop nature of up/down-dating characterizes the feature of dual-state systolic triarray. To further reduce the complexity and increase the throughput rate, Cordic cells can be used to mimic the operations of rowbroadcasting and only one control bit is required along each row of processors. Efficient implementation to obtain optimal residuals and a transformation of the hyperbolic rotation to an algebraically equivalent orthogonal operation to provide a more stable implementation are also considered. This systolic architecture is very promising in VLSI implementation of the sliding-window recursive least squares estimations.
  • Thumbnail Image
    Item
    Systolic Implementations of Up/Down-dating Cholesky Factorization Using Vectorized Gram-Schmidt Pseudo Orthogonalization
    (1991) Hsieh, S.F.; Liu, K.J. Ray; Yao, K.; ISR
    We propose a new class of hyperbolic 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.
  • Thumbnail Image
    Item
    Dynamic Range, Stability, and Fault-tolerant Capability of Finite-precision RLS Systolic Array Based on Givens Rotations
    (1990) Liu, K.J. Ray; Hsieh, S.F.; Yao, K.; Chiu, Ching-Te; ISR
    The QRD RLS algorithm is generally recognized as having good numerical properties under finite-precision implementation. Also, it is very suitable for VLSI implementation since it can be easily mapped onto a systolic array. However, it is still unclear how to obtain the dynamic range of the algorithm such that a wordlength can be chosen to ensure correct operations of the algorithm. In this paper, we first propose a quasi-steady state model by observing the rotation parameters generated by boundary cells will eventually reach quasi steady-state regardless of the input data statistics if l is close to one. With this model, we can obtain upper bounds of the dynamic range of processing cells. Thus, the wordlength can be obtained from upper bounds of the dynamic range to prevent overflow and to ensure correct operations of the QRD RLS algorithm. Then we reconsider the stability problem under quantization effects with more general analysis and obtain tighter bounds than given in a previous work [13]. Finally, two fault-tolerant problems, the missing error detection and the false alarm effect, the arise under finite- precision implementation are considered. Detail analysis on preventing missing error detection with a false alarm free condition is presented.
  • Thumbnail Image
    Item
    Systolic Block Householder Transformation for RLS Algorithm with Two-level Pipelined Implementation
    (1990) Liu, K.J. Ray; Hsieh, S.F.; Yao, K.; ISR
    The QRD RLS algorithm is one of the most promising RLS algorithms, due to its robust numerical stability and suitability for VLSI implementation based on a systolic array architecture. Up to now, among many techniques to implement the QR decomposition, only the Given rotation and modified Gram-Schmidt methods have been successfully applied to the development of the QRD RLS systolic array. It is well-known that Householder transformation (HT) outperforms the Givens rotation method under finite precision computations. Presently, there is no know technique to implement the HT on a systolic array architecture. In this paper, we propose a Systolic Block Householder Transformation (SBHT) approach, to implement the HT on a systolic array as well as its application to the RLS algorithm. Since the data is fetched in a block manner, vector operations are in general required for the vectorized array. However, by using a modified HT algorithm, a two-level pipelined implementation can be used to pipeline the SBHT systolic array both at the vector and word level. The throughput rate can be as fast as that of the Givens rotation method. Our approach makes the HT amenable for VLSI implementation as well as applicable to real-time high throughput applications of modern signal processing. The constrained RLS problem using the SBHT RLS systolic array is also considered in this paper.