Browsing by Author "HSIEH, SF"

Now showing 1 - 6 of 6

A UNIFIED SQUARE-ROOT-FREE APPROACH FOR QRD-BASED RECURSIVE LEAST-SQUARES ESTIMATION
(1993-03-01)
HSIEH, SF
;
LIU, KJR
;
YAO, K
;
電信工程研究所
;
Institute of Communications Engineering
Givens rotation is the most commonly used method in performing the QR decomposition (QRD) updating. The generic formula for these rotations requires explicit square-root (sqrt) computations which constitute a computational bottleneck and are quite undesirable from the practical VLSI circuit design point of view. So far, there has been more than ten known sqrt-free algorithms. In this correspondence, we provide a unified systematic approach for the sqrt-free Givens rotation. By properly choosing two parameters, mu and nu, all previously known sqrt-free, as well as new methods, are included in our unified approach. This unified treatment is also extended to the QRD-based recursive least squares (RLS) problem for optimum residual acquisition without sqrt operations.
DUAL-STATE SYSTOLIC ARCHITECTURES FOR UP DOWNDATING RLS ADAPTIVE FILTERING
(1992-06-01)
HSIEH, SF
;
LIU, KJR
;
YAO, K
;
電信工程研究所
;
Institute of Communications Engineering
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 based on successively performing Givens rotations for updating and hyperbolic rotations for downdating. Due to 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 the dual-state systolic triarray. Efficient implementation on the evaluation of optimal residuals is also considered. This systolic architecture is promising for the VLSI implementation of fixed size sliding-window recursive least-squares estimations.
DYNAMIC-RANGE, STABILITY, AND FAULT-TOLERANT CAPABILITY OF FINITE-PRECISION RLS SYSTOLIC ARRAY BASED ON GIVENS ROTATIONS
(1991-06-01)
LIU, KR
;
HSIEH, SF
;
YAO, K
;
CHIU, CT
;
電信工程研究所
The QRD RLS algorithm is generally recognized as having good numerical properties under a finite-precision implementation. Furthermore, it is quite suited 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 in order 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 lambda 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 a 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, that arise under finite-precision implementation are considered. Detailed analysis on preventing missing error detection with a false alarm free condition is presented.
ESTIMATION OF MULTIPLE SINUSOIDAL FREQUENCIES USING TRUNCATED LEAST-SQUARES METHODS
(1993-02-01)
HSIEH, SF
;
LIU, KJR
;
YAO, K
;
電信工程研究所
;
Institute of Communications Engineering
Various SVD-based methods have been shown effective for resolving closely spaced frequencies. However, the massive computations required by SVD makes it unsuitable for real-time applications. To reduce the computational complexity, three truncated QR methods are proposed: 1) truncated QR without column pivoting (TQR); 2) truncated QR with reordered columns (TQRR); and 3) truncated QR with column pivoting (TQRP). It is demonstrated that many of the benefits of the SVD-based methods are achievable under the truncated QR methods with much lower computational cost. Based on the forward-backward linear prediction model, computer simulations and comparisons are provided for different truncation methods under various SNR's. Comparisons of asymptotic performance with large data samples are also given.
FAST ORTHOGONALIZATION ALGORITHM AND PARALLEL ARCHITECTURE FOR AR SPECTRAL ESTIMATION BASED ON FORWARD - BACKWARD LINEAR PREDICTION
(1993-03-01)
LIU, KJR
;
HSIEH, SF
;
電信工程研究所
;
Institute of Communications Engineering
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 2(6m - n)n2/3 + O(n2) for a 2m x n FBLP matrix. Here we propose a fast algorithm to perform the QRD of the FBLP matrix by exploiting its special Toeplitz-Hankel form. The computational complexity is then reduced to 10n2 + 4mn + O(n). 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.
SYSTOLIC BLOCK HOUSEHOLDER TRANSFORMATION FOR RLS ALGORITHM WITH 2-LEVEL PIPELINED IMPLEMENTATION
(1992-04-01)
LIU, KR
;
HSIEH, SF
;
YAO, K
;
電信工程研究所
;
Institute of Communications Engineering
The QR decomposition, recursive least squares (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 Givens 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 known 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, a modified HT algorithm permits a two-level pipelined implementation of the SBHT systolic array at both the vector and word levels. 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.