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

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

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     

A unified algebraic transformation approach for parallel recursiveand adaptive filtering and SVD algorithms

In this paper, a unified algebraic transformation approach is presented for designing parallel recursive and adaptive digital filters and singular value decomposition (SVD) algorithms. The approach is based on the explorations of some algebraic properties of the target algorithms' representations. Several typical modern digital signal processing examples are presented to illustrate the applications of the technique. They include the cascaded orthogonal recursive digital filter, the Givens rotation-based adaptive inverse QR algorithm for channel equalization, and the QR decomposition-based SVD algorithms. All three examples exhibit similar throughput constraints. There exist long feedback loops in the algorithms' signal flow graph representation, and the critical path is proportional to the size of the problem. Applying the proposed algebraic transformation techniques, parallel architectures are obtained for all three examples. For cascade orthogonal recursive filter, retiming transformation and orthogonal matrix decompositions (or pseudo-commutativity) are applied to obtain parallel filter architectures with critical path of five Givens rotations. For adaptive inverse QR algorithm, the commutativity and associativity of the matrix multiplications are applied to obtain parallel architectures with critical path of either four Givens rotations or three Givens rotations plus two multiply-add operations, whichever turns out to be larger. For SVD algorithms, retiming and associativity of the matrix multiplications are applied to derive parallel architectures with critical path of eight Givens rotations. The critical paths of all parallel architectures are independent of the problem size as compared with being proportional to the problem size in the original sequential algorithms. Parallelism is achieved at the expense of slight increase (or the same for the SVD case) in the algorithms' computational complexity     

New fast QR decomposition least squares adaptive algorithms

This paper presents two new, closely related adaptive algorithms for LS system identification. The starting point for the derivation of the algorithms is the inverse Cholesky factor of the data correlation matrix, obtained via a QR decomposition (QRD). Both algorithms are of O(p) computational complexity, with p being the order of the system. The first algorithm is a fixed order QRD scheme with enhanced parallelism. The second is an order recursive lattice type algorithm based exclusively on orthogonal Givens rotations, with lower complexity compared to previously derived ones. Both algorithms are derived following a new approach, which exploits efficient the and order updates of a specific state vector quantity     

Algorithmic engineering in adaptive signal processing: workedexamples

Algorithmic engineering provides a rigorous framework for describing and manipulating the type of building blocks commonly used to define parallel algorithms and architectures for digital signal processing. So far, the concept has only been illustrated by means of relatively simple examples relating to the use of QR decomposition (QRD) by Givens rotations for the purposes of adaptive filtering and beamforming. Two more challenging examples are presented that illustrate the use of simple diagrammatic transformations to develop novel algorithms and architectures, and demonstrate the potential power of algorithmic engineering as a formal design technique. The first example constitutes the only known derivation of a modular processing architecture for generalised sidelobe cancellation based on QR decomposition. The second provides a simple derivation of the QRD-based lattice algorithm for multichannel least-squares linear prediction     

Rotation-based RLS algorithms: unified derivations, numericalproperties, and parallel implementations

This work presents a unified derivation of four rotation-based recursive least squares (RLS) algorithms. They solve the adaptive least squares problems of the linear combiner, the linear combiner without a desired signal, the single channel, and the multichannel linear prediction and transversal filtering. Compared to other approaches, the authors' derivation is simpler and unified, and may be useful to readers for better understanding the algorithms and their relationships. Moreover, it enables improvements of some algorithms in the literature in both the computational and the numerical issues. All algorithms derived in this work are based on Givens rotations. They offer superior numerical properties as shown by computer simulations. They are computationally efficient and highly concurrent. Aspects of parallel implementation and parameter identification are discussed     

QR factorization based blind channel identification withsecond-order statistics

Most eigenstructure-based blind channel identification and equalization algorithms with second-order statistics need SVD or EVD of the correlation matrix of the received signal. In this paper, we address new algorithms based on QR factorization of the received signal directly without calculating the correlation matrix. This renders the QR factorization-based algorithms more robust against ill-conditioned channels, i.e., those channels with almost common zeros among the subchannels. First, we present a block algorithm that performs the QR factorization of the received data matrix as a whole. Then, a recursive algorithm is developed based on the QR factorization by updating a rank-revealing ULV decomposition. Compared with existing algorithms in the same category, our algorithms are computationally more efficient. The computation in each recursion of the recursive algorithm is on the order of O(m²) if only equalization is required, where m is the dimension of the received signal vector. Our recursive algorithm preserves the fast convergence property of the subspace algorithms, thus converging faster than other adaptive algorithms such as the super-exponential algorithm with comparable computational complexities. Moreover, our proposed algorithms do not require noise variance estimation. Numerical simulations demonstrate the good performance of the proposed algorithms     

一种基于QR-RLS算法的多项式预失真方法

在传统预失真技术的基础上,提出了一项基于QR-RLS算法的多项式预失真方法。该算法利用Givens旋转技术对输入信息矩阵进行QR分解,避免了传统RLS算法中对其自相关矩阵的求逆运算,提高了数值的稳定性,并且降低了运算的复杂性,提高了运算速度。计算机仿真分析表明,QR-RLS多项式预失真算法对互调失真的抑制依然有非常好的效果。     

一种基于Householder变换的递归 QRD-LS算法

本文提出了一种采用Householder变换实现的递归QRD-LS算法,该算法通过采用Householder变换取代Giv- ens旋转递归实现复矩阵的QR分解来求解LS问题,可以获得比基于Givens旋转的QRD—LS算法更快的处理速度。此外, 算法引入了复数QR分解,解决了算法只能处理实数信号的问题。通过定义新的数据矩阵,算法还可以合并求解数据域正规方程中的系数矩阵和右侧向量,从而提高了计算效率。通过对其在智能天线中的应用进行仿真,验证了算法的性能。     

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     

基于QR分解自适应波束形成算法的FPGA实现

为了在当前的通信环境中选择合适的QR分解算法来硬件实现矩阵的求逆,需要提前了解该算法的硬件性能。分析常用于复数QR分解的Givens rotation法和Modified Gram—Schmidt正交法的算法原理和硬件实现。在Xilinx公司的ISE软件上进行两种算法的底层设计和硬件仿真,经过综合在Xilinx的Kintex-7系列的XC7K325T芯片上实现了整个设计。通过对比两种算法的硬件性能后发现,在输入数据宽度相同的前提下,两种算法的误差值相差很小,其中MGS算法的实时性比GR算法差,但是硬件资源消耗更小。因此在对系统实时性要求较高的环境中,选择GR算法更好一些。     

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.     

Fast QR Algorithms Based on Backward Prediction Errors: A New Implementation and Its Finite Precision Performance

QR decomposition techniques are well known for their good numerical behavior and low complexity. Fast QRD recursive least squares adaptive algorithms benefit from these characteristics to offer robust and fast adaptive filters. This paper examines two different versions of the fast QR algorithm based on a priori backward prediction errors as well as two other corresponding versions of the fast QR algorithm based on a posteriori backward prediction errors. The main matrix equations are presented with different versions derived from two distinct deployments of a particular matrix equation. From this study, a new algorithm is derived. The discussed algorithms are compared, and differences in computational complexity and in finite-precision behavior are shown.     

Multichannel fast QRD-LS adaptive filtering: new technique andalgorithms

A direct, unified approach for deriving fast multichannel QR decomposition (QRD) least squares (LS) adaptive algorithms is introduced. The starting point of the new methodology is the efficient update of the Cholesky factor of the input data correlation matrix. Using the new technique, two novel fast multichannel algorithms are developed. Both algorithms comprise scalar operations only and are based exclusively oh numerically robust orthogonal Givens rotations. The first algorithm assumes channels of equal orders and processes them all simultaneously. It is highly modular and provides enhanced pipelinability, with no increase in computational complexity, when compared with other algorithms of the same category. The second multichannel algorithm deals with the general case of channels with different number of delay elements and processes each channel separately. A modification of the algorithm leads to a scheme that can be implemented on a very regular systolic architecture. Moreover, both schemes offer substantially reduced computational complexity compared not only with the first algorithm but also with previously derived multichannel fast QRD schemes. Experimental results in two specific application setups as well as simulations in a finite precision environment are also included     

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     

A class of square root and division free algorithms andarchitectures for QRD-based adaptive signal processing

The least squares (LS) minimization problem constitutes the core of many real-time signal processing problems, such as adaptive filtering, system identification and adaptive beamforming. Recently efficient implementations of the recursive least squares (RLS) algorithm and the constrained recursive least squares (CRLS) algorithm based on the numerically stable QR decomposition (QRD) have been of great interest. Several papers have proposed modifications to the rotation algorithm that circumvent the square root operations and minimize the number of divisions that are involved in the Givens rotation. It has also been shown that all the known square root free algorithms are instances of one parametric algorithm. Recently, a square root free and division free algorithm has also been proposed. In this paper, we propose a family of square root and division free algorithms and examine its relationship with the square root free parametric family. We choose a specific instance for each one of the two parametric algorithms and make a comparative study of the systolic structures based on these two instances, as well as the standard Givens rotation. We consider the architectures for both the optimal residual computation and the optimal weight vector extraction. The dynamic range of the newly proposed algorithm for QRD-RLS optimal residual computation and the wordlength lower bounds that guarantee no overflow are presented. The numerical stability of the algorithm is also considered. A number of obscure points relevant to the realization of the QRD-RLS and the QRD-CRLS algorithms are clarified. Some systolic structures that are described in this paper are very promising, since they require less computational complexity (in various aspects) than the structures known to date and they make the VLSI implementation easier     

抗串扰QR格型自适应滤波算法

本文就抗串扰自适应噪声抵消器，研究了一种递归最小二乘(RLS)格型自适应算法。算法的导出仅利用数值稳健的Givens。旋转方法，因此具有优越的数值性能和较好的模块化结构性能。算法不含平方根运算，十分适合用通用数字信号处理器实现。文中还就算法的阵列实现进行了探讨，只需增加少量的时间，即可实现高性能的自适应噪声抵消器。模拟结果表明，算法的收敛速度明显优于现有的LMS算法。     

Algorithmically engineered fast multichannel adaptive filter basedon QR-RLS

A fast version of the multichannel QR algorithm for RLS adaptive filtering, with channel filters of unequal length, is derived. This is achieved by applying the techniques of algorithmic engineering to a signal flow graph representation of the basic QR RLS algorithm. By virtue of this graphical approach, the derivation is relatively straightforward and circumvents the complex and notationally verbose matrix algebra usually involved in the derivation of fast RLS algorithms in general and the previously published, unequal-length, multichannel RLS lattice algorithm in particular     

基于脉动阵的自适应波束形成算法仿真

为了满足自适应波束形成技术对实时性的要求,将脉动阵应用于波束形成算法中,以实现自适应权向量的实时获取.通过对QR分解采样矩阵求逆算法、混合型QR分解采样矩阵求逆算法和逆QR分解采样矩阵求逆算法的理论分析,利用脉动阵,对输入数据矩阵进行QR分解,得到旋转因子,实现自适应权向量的实时更新.针对三种算法各自的脉动阵进行仿真,结果表明,基于脉动阵的自适应波束形成算法实现了权向量的高速获取,并为后续的工程实践提供了理论依据.     

Reduced‐rank space–time adaptive interference suppression for navigation systems based on QR decomposition and approximations of basis functions

This paper presents a novel reduced‐rank space–time adaptive processing (STAP) algorithm for interference suppression in global positioning system (GPS) receivers with low computational complexity for protection against the multipath and jamming interferences. The proposed STAP algorithm is based on the least‐squares (LS) criterion to jointly optimize a projection matrix, which is used for dimensionality reduction, and the reduced‐rank filter. The main novelties are the design of the projection matrix based on approximations of basis functions, the pattern matching between the projection matrix and the received data, and the derivation of a QR decomposition‐based reduced‐rank recursive LS algorithm for practical implementations. The proposed scheme works on an instantaneous basis, i.e. at each time instant, the most suitable pattern and the rank of the projection matrix are selected to reduce the dimensionality of the received data aiming at minimizing the squared error, while using an improved search algorithm to save the effort in finding the best projection matrix. Simulation results in a GPS system show that compared to existing reduced‐rank and full‐rank algorithms, the proposed algorithm has a much lower computational complexity, and remarkably better performance for interference suppression. Copyright © 2011 John Wiley & Sons, Ltd.