Givns变换无开方根算法

本文提出一种Givens变换算法,它用一系列位移——相加操作或指数相加——相加操作代替正常要求的开方根、乘、除等运算,以改善计算效率,这对systolic阵列结构的VLSI实现特别有效。     

Pipelined RLS adaptive filtering using scaled tangent rotations(STAR)

The QR decomposition-based recursive least-squares (RLS) adaptive filtering algorithm (referred to as QRD-RLS) is very popular because it has good numerical properties and can be mapped onto a systolic array. However, in this architecture, pipelining of the operations within the systolic array cells is difficult. Pipelining would be necessary to operate at high speeds or to reduce the power dissipation in a VLSI implementation. Pipelining QRD-RLS using look-ahead techniques leads to a large hardware overhead. The square-root free forms of QRD-RLS are also difficult to pipeline. In this paper, a new scaled tangent rotation (STAR) is used instead of the Givens rotations used in QRD-RLS. The STAR-based RLS algorithm (referred to as STAR-RLS) is designed such that fine-grain pipelining can be accomplished with little hardware overhead The scaled tangent rotations are not exactly orthogonal transformations but tend to become orthogonal asymptotically. The STAR-RLS algorithm is square-root free and has less complexity and lower intercell communication than the QRD-RLS algorithm. The properties of the STAR-RLS algorithm, such as stability, numerical property, and dynamic range, are examined with and without pipelining and compared with those of QRD-RLS. Simulation results are presented to compare the performance of STAR-RLS and QRD-RLS algorithms     

Givens rotation based least squares lattice and related algorithms

The author presents a general and systematic approach for deriving new LS (least squares) estimation algorithms that are based solely on Givens rotations. In particular, this approach is used to derive efficient Givens-rotation-based LS lattice algorithms-the Givens-lattice algorithms. By exploiting the relationship between the Givens algorithms and the recursive modified Gram-Schmidt algorithm, it is shown that the time and order update of any order-recursive LS estimation algorithm can be realized by employing only Givens rotations. Applying this general conclusion to LS estimation of time-series signals results in the Givens-lattice algorithms. Two Givens-lattice algorithms, one with square roots and the other without, are presented. It is shown that the Givens-lattice algorithms are computationally more efficient than the fast QR algorithm of Cioffi (1987). The derivation of other Givens rotation-based LS estimation algorithms and their systolic array implementations are discussed     

无平方根定标Givens旋转算法脉动阵实现的有限字长分析

最小二乘(LS)是许多实时自适应信号处理问题的核心。本文针对无平方根的定标Givens旋转方法,分析了用脉动(Systolic)阵实现时各处理单元和内部传递参数的动态范围,并确定了保证算法正确实现所需的字长下界。计算机仿真结果表明,这样选取字长是合适的,所得的算法也是稳定的。     

Systolic block Householder transformation for RLS algorithm withtwo-level pipelined implementation

The authors propose a systolic block Householder transformation (SBHT) approach to implement the HT on a systolic array and also propose its application to the RLS (recursive least squares) algorithm. Since the data are 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. The present 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     

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 linearly constrained inverse QRD-RLS beamforming algorithm for moving jammers suppression

A general, linearly constrained (LC) recursive least squares (RLS) array-beamforming algorithm, based on an inverse QR decomposition, is developed for suppressing moving jammers efficiently. In fact, by using the inverse QR decomposition-recursive least squares (QRD-RLS) algorithm approach, the least-squares (LS) weight vector can be computed without back substitution and is suitable for implementation using a systolic array to achieve fast convergence and good numerical properties. The merits of this new constrained algorithm are verified by evaluating the performance, in terms of the learning curve, to investigate the convergence property and numerical efficiency, and the output signal-to-interference-and-noise ratio. We show that our proposed algorithm outperforms the conventional linearly constrained LMS (LCLMS) algorithm, and the one using the fast linear constrained RLS algorithm and its modified version.     

适于参数识别的多信道QRD自适应格型算法

本文基于格型滤波器的阶递归特性和Givens旋转算法的优越数值性能,推导了两种多信道递归最小二乘格型算法。第一种算法的推导是直接基于对输入数据矩阵进行正交-三角分解,并利用Givens旋转方法来计算其正交-三角分解。首先对输入数据矩阵进行预旋转,然后重复利用单信道Givens格型算法,便可得到第二种算法。两种算法都具有优越的数值性能,尤其是对有限字长的稳健性。待估计的滤波器参数矢量可根据算法的内部变量直接提取,而无需额外的三角阵进行后向代入求解运算。两信道参数识别的计算机模拟结果验证了本文的推导。     

QRD-BASED MULTICHANNEL ADAPTIVE LATTICEALGORITHMS FOR THE PARAMETERIDENTIFICATION PROBLEM

A pair of multichannel recursive least squares (RLS) adaptive lattice algorithms based on the order recursive of lattice filters and the superior numerical properties of Givens algorithms is derived in this paper. The derivation of the first algorithm is based on QR decomposition of the input data matrix directly, and the Givens rotations approach is used to compute the QR decomposition. Using first a prerotation of the input data matrix and then a repetition of the single channel Givens lattice algorithm, the second algorithm can be obtained. Both algorithms have superior numerical properties, particularly the robustness to wordlength limitations. The parameter vector to be estimated can be extracted directly from internal variables in the present algorithms without a backsolve operation with an extra triangular array. The results of computer simulation of the parameter identification of a two-channel system are presented to confirm efficiently the derivation.     

基于最小均方和递归最小二乘的有源滤波器谐波检测

针对当前有源滤波器谐波检测算法的精度低、运算量大、实时性差等不足,为了获得更加理想的谐波检测结果,提出了基于最小均方和递归最小二乘的有源滤波器谐波检测算法。首先针对锁相环获取输入信号运算量大、谐波检测时间长的难题,将过负载电流作为参考输入,加快有源滤波器的响应速度,然后基于最小均方算法和递归最小二乘算法快速、准确的实现谐波检测,最后在MATLAB 1204平台对本文算法的有效性和先进性进行了仿真验证性实验。 实验结果表明,本文算法得到了较高的有源滤波器谐波检测精度,能够提高有源滤波器的补偿性能,而且具有较快的动态响应速度,改善了算法的实时性。     

A QRD-RLS-Based Predistortion Scheme for High-Power Amplifier Linearization

A digital baseband predistortion (PD) scheme for high-power amplifier (HPA) linearization is proposed and analyzed in this brief. The proposed approach utilizes the QR-decomposition-based recursive least squares (QRD-RLS) algorithm to estimate the memoryless complex polynomial coefficients that characterize the HPA. The inverse polynomial model coefficients corresponding to the PD are similarly extracted using QRD-RLS. The performance of the proposed PD scheme is analyzed via simulations and compared with previously published techniques. Results show that the QRD-RLS-based solution offers improved performance over its comparatives     

Annihilation-reordering look-ahead pipelined CORDIC-based RLSadaptive filters and their application to adaptive beamforming

The novel annihilation-reordering look-ahead technique is proposed as an attractive technique for pipelining of Givens rotation (or CORDIC)-based adaptive filters. Unlike the existing relaxed look-ahead, the annihilation-reordering look-ahead does not depend on the statistical properties of the input samples. It is an exact look-ahead based on CORDIC arithmetic, which is known to be numerically stable. The conventional look-ahead is based on multiply-add arithmetic. The annihilation-reordering look-ahead technique transforms an orthogonal sequential adaptive filtering algorithm into an equivalent orthogonal concurrent one by creating additional concurrency in the algorithm. Parallelism in the transformed algorithm is explored and different implementation styles including pipelining, block processing, and incremental block processing are presented. Their complexities are also studied and compared. The annihilation-reordering look-ahead is employed to develop fine-grain pipelined QR decomposition-based RLS adaptive filters. Both QRD-RLS and inverse QRD-RLS algorithms are considered. The proposed pipelined architectures can be operated at arbitrarily high sample rate without degrading the filter convergence behavior. Stability under finite-precision arithmetic are studied and proved for the proposed architectures. The pipelined CORDIC-based RLS adaptive filters are then employed to develop high-speed linear constraint minimum variance (LCMV) adaptive beamforming algorithms. Both QR decomposition-based minimum variance distortionless response (MVDR) realization and generalized sidelobe canceller (GSC) realization are presented. The complexity of the pipelined architectures are analyzed and compared. The proposed architectures can be operated at arbitrarily high sample rate and consist of only Givens rotations, which can be scheduled onto CORDIC arithmetic-based processors     

A state-space approach to adaptive RLS filtering

Adaptive filtering algorithms fall into four main groups: recursive least squares (RLS) algorithms and the corresponding fast versions; QR- and inverse QR-least squares algorithms; least squares lattice (LSL) and QR decomposition-based least squares lattice (QRD-LSL) algorithms; and gradient-based algorithms such as the least-mean square (LMS) algorithm. Our purpose in this article is to present yet another approach, for the sake of achieving two important goals. The first one is to show how several different variants of the recursive least-squares algorithm can be directly related to the widely studied Kalman filtering problem of estimation and control. Our second important goal is to present all the different versions of the RLS algorithm in computationally convenient square-root forms: a prearray of numbers has to be triangularized by a rotation, or a sequence of elementary rotations, in order to yield a postarray of numbers. The quantities needed to form the next prearray can then be read off from the entries of the postarray, and the procedure can be repeated; the explicit forms of the rotation matrices are not needed in most cases     

Optimal tracking of time-varying channels: a frequency domainapproach for known and new algorithms

In this paper, we developed a systematic frequency domain approach to analyze adaptive tracking algorithms for fast time-varying channels. The analysis is performed with the help of two new concepts, a tracking filter and a tracking error filter, which are used to calculate the mean square identification error (MSIE). First, we analyze existing algorithms, the least mean squares (LMS) algorithm, the exponential windowed recursive least squares (EW-RLS) algorithm and the rectangular windowed recursive least squares (RW-RLS) algorithm. The equivalence of the three algorithms is demonstrated by employing the frequency domain method. A unified expression for the MSIE of all three algorithms is derived. Secondly, we use the frequency domain analysis method to develop an optimal windowed recursive least squares (OW-RLS) algorithm. We derive the expression for the MSIE of an arbitrary windowed RLS algorithm and optimize the window shape to minimize the MSIE. Compared with an exponential window having an optimized forgetting factor, an optimal window results in a significant improvement in the h MSIE. Thirdly, we propose two types of robust windows, the average robust window and the minimax robust window. The RLS algorithms designed with these windows have near-optimal performance, but do not require detailed statistics of the channel     

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     

Recursive least-squares algorithms of modified Gram-Schmidt typefor parallel weight extraction

This paper presents some new algorithms for parallel weight extraction in the recursive least-squares (RLS) estimation based on the modified Gram-Schmidt (MGS) method. These are the counterparts of the algorithms using an inverse QR decomposition based on the Givens rotations and do not contain the square root operation. Systolic-array implementations of the algorithms are considered on a 2-D rhombic array. Simulation results are also presented to compare the finite word-length effect of these new algorithms and existing algorithms     

Improved approximate QR-LS algorithms for adaptive filtering

This paper studies a class of O(N) approximate QR-based least squares (A-QR-LS) algorithm recently proposed by Liu in 1995. It is shown that the A-QR-LS algorithm is equivalent to a normalized LMS algorithm with time-varying stepsizes and element-wise normalization of the input signal vector. It reduces to the QR-LMS algorithm proposed by Liu et al. in 1998, when all the normalization constants are chosen as the Euclidean norm of the input signal vector. An improved transform-domain approximate QR-LS (TA-QR-LS) algorithm, where the input signal vector is first approximately decorrelated by some unitary transformations before the normalization, is proposed to improve its convergence for highly correlated signals. The mean weight vectors of the algorithms are shown to converge to the optimal Wiener solution if the weighting factor w of the algorithm is chosen between 0 and 1. New Givens rotations-based algorithms for the A-QR-LS, TA-QR-LS, and the QR-LMS algorithms are proposed to reduce their arithmetic complexities. This reduces the arithmetic complexity by a factor of 2, and allows square root-free versions of the algorithms be developed. The performances of the various algorithms are evaluated through computer simulation of a system identification problem and an acoustic echo canceller.     

Multiprocessor Implementation of Adaptive Digital Filters

Adaptive filters, employing the transversal filter structure and the least mean square (LMS) adaptation algorithm, or its variations, have found wide application in data transmission equalization, echo cancellation, prediction, spectral estimation, on-line system identification, and antenna arrays. Recently, in response to requirements of fast start-up, or fast tracking of temporal variations, fast recursive least squares (FRLS) adaptation algorithms for both transversal and lattice filter structures have been proposed. These algorithms offer faster convergence than is possible with the LMS/ transversal adaptive filters, at the price of a five-to-tenfold increase in the number of multiplications, divisions, and additions. Here we discuss architectures and implementations of the LMS/transversal, fast-converging FRLS filter, and lattice filter algorithms which minimize the required hardware speed. We show how each of these algorithms can be partitioned so as to be realizable with an architecture based on multiple parallel processors.     

A fast learning algorithm for Gabor transformation

An adaptive learning approach for the computation of the coefficients of the generalized nonorthogonal 2-D Gabor (1946) transform representation is introduced. The algorithm uses a recursive least squares (RLS) type algorithm. The aim is to achieve minimum mean squared error for the reconstructed image from the set of the Gabor coefficients. The proposed RLS learning offers better accuracy and faster convergence behavior when compared with the least mean squares (LMS)-based algorithms. Applications of this scheme in image data reduction are also demonstrated.     

一种基于拟牛顿法的递归最小二乘方法

基于拟牛顿优化方法,提出了一种稳健的自适应FIR滤波算法。新算法用最小二乘误差(LSE)代替了均方误差(MSE)作为代价函数,它具有和常规递归最小二乘(CRLS)算法相近似的追踪能力,且不存在数值计算不稳定性的问题,在收敛速度以及稳态效果方面也要优于De Campos的拟牛顿(QN)算法。通过计算机仿真比较了有关算法的性能。