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     

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     

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.     

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

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

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     

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     

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     

Plane rotation-based EVD updating schemes for efficient subspacetracking

We present new algorithms based on plane rotations for tracking the eigenvalue decomposition (EVD) of a time-varying data covariance matrix. These algorithms directly produce eigenvectors in orthonormal form and are well suited for the application of subspace methods to nonstationary data. After recasting EVD tracking as a simplified rank-one EVD update problem, computationally efficient solutions are obtained in two steps. First, a new kind of parametric perturbation approach is used to express the eigenvector update as an unimodular orthogonal transform, which is represented in exponential matrix form in terms of a reduced set of small, unconstrained parameters. Second, two approximate decompositions of this exponential matrix into products of plane (or Givens) rotations are derived, one of which being previously unknown. These decompositions lead to new plane rotation-based EVD-updating schemes (PROTEUS), whose main feature is the use of plane rotations for updating the eigenvectors, thereby preserving orthonormality. Finally, the PROTEUS schemes are used to derive new EVD trackers whose convergence and numerical stability are investigated via simulations. One algorithm can track all the signal subspace EVD components in only O(LM) operations, where L and M, respectively, denote the data vector and signal subspace dimensions while achieving a performance comparable to an exact EVD approach and maintaining perfect orthonormality of the eigenvectors. The new algorithms show no signs of error buildup     

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     

FINITE WORDLENGTH ANALYZING FOR RLS SYSTOLIC ALGORITHM BASED ON THE SQUARE-ROOT-FREE SCALED GIVENS ROTATIONS

The least squares(LS) minimization problem constitutes the core of many real-time signal processing problems. A square-root-free scaled Givens rotations algorithm and its systolic architecture for the optimal RLS residual evaluation are presented in this paper. We analyze upper bounds of the dynamic range of processing cells and the internal parameters. Thus the wordlength can be obtained to prevent overflow and to ensure correct operations. Simulation results confirm the theoretical conclusions and the stability of the algorithm.     

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

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

Echo Cancellation of Voiceband Data Signals Using Recursive Least Squares and Stochastic Gradient Algorithms

The convergence properties of adaptive least squares (LS) and stochastic gradient (SG) algorithms are studied in the context of echo cancellation of voiceband data signals. The algorithms considered are the SG transversal, SG lattice, LS transversal (fast Kalman), and LS lattice. It is shown that for the channel estimation problem considered here, LS algorithms converge in approximately2Niterations whereNis the order of the filter. In contrast, both SG algorithms display inferior convergence properties due to their reliance upon statistical averages. Simulations are presented to verify this result, and indicate that the fast Kalman algorithm frequently displays numerical instability which can be circumvented by using the lattice structure. Finally, the equivalence between an LS algorithm and a fast converging modified SG algorithm which uses a maximum length input data sequence is shown.     

A least squares path-loss estimation approach to handoveralgorithms

In this paper, a new class of linear handover algorithms is introduced and analyzed for two conflicting performance measures, namely, the average number of outages and the average number of handovers, for a given trip of the mobile station (MS). The new algorithm is based on the least squares (LS) estimate of path-loss parameters of the various radio links, assuming the distances between the MS and surrounding base stations (BSs) are known. First, a simplified system scenario consisting of only two BSs in a lognormal fading environment is assumed. Performance measures are derived through a theoretical approach, along the trip of a mobile terminal from one BS to the other. It is seen that for an average number of 1.2 handovers (the minimum value is one, given by the ideal reference case), the LS algorithm reduces the average number of outages by more than 30% with respect to the classical averaging algorithm. Furthermore, the above performance measures improve for longer estimation windows: both the estimation of the mobile speed and the window length tradeoff of averaging algorithms do not apply to the LS method. By using an extended version of the basic algorithm, these results were also observed in simulations of a more general system scenario, consisting of several BS's and a mobile terminal moving along a generic path     

A novel algorithm and architecture for adaptive digital beamforming

A novel algorithm and architecture are described which have specific application to high performance, digital, adaptive beamforming. It is shown how a simple, linearly constrained adaptive combiner forms the basis for a wide range of adaptive antenna subsystems. The function of such an adaptive combiner is formulated as a recursive least squares minimization operation and the corresponding weight vector is obtained by means of theQ-Rdecomposition algorithm using Givens rotations. An efficient pipelined architecture to implement this algorithm is also described. It takes the form of a triangular systolic/wavefront array and has many desirable features for very large scale integration (VLSI) system design.     

NB-IoT系统基于导频信道估计算法研究

NB-IoT(Narrow Band Internet of Things)是一种基于蜂窝的窄带物联网技术,该技术如今发展非常迅速,为了协助终端更好地解调出发射信号,在现有的LS算法和基于DFT的LS算法基础上进行改进,设计了基于阀值的变换域信道估计算法,并且通过MATLAB对以上三种算法的BER(误码率)进行仿真和验证,最终仿真结果显示改进算法的性能优于另外两种算法.     

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     

Amplitude spectrum estimation for two-dimensional gapped data

The amplitude and phase estimation (APES) approach to nonparametric spectrum estimation of uniformly sampled data has received considerable interest. We consider the extension of APES to gapped data, i.e., uniformly sampled data with missing samples. It has been shown that the APES estimate of the spectrum is the minimizer of a certain least-squares (LS) criterion, and our extension of APES is based on minimizing this LS criterion with respect to the missing data as well. A computationally efficient method for doing this based on cyclic minimization and the conjugate gradient algorithm is proposed. The new algorithm is called gapped-data APES (GAPES) and is developed for the two-dimensional (2-D) case, with the one-dimensional (1-D) case as a special instance. Numerical examples are provided to demonstrate the performance of the algorithm and to show the advantages of 2-D data processing over 1-D (row or column-wise) data processing, as well as to show the applicability of the algorithm to synthetic aperture radar (SAR) imaging     

基于导频的OFDM系统信道估计

正交频分复用（0FDM）是一种高效的数字传输技术,因其较高的频带利用率以及抗多径衰落的性能,被视为下一代无线通信的核心技术。信道估计是视线OFDM系统的关键技术之一。主要研究了OFDM无线通信系统中基于导频的信息估计算法——LS算法,MMSE算法以及改进的LS算法,并通过仿真算法的最小均方误差性能和误码率特性证明了改进的LS算法要优于LS算法。     

伪叠加Zadoff-Chu序列的LTE下行信道估计

分析了正交频分复用系统中基于叠加训练序列的最小二乘和线性最小均方误差信道估计算法,在此基础上针对LTE信道的结构特征,提出了一种利用伪叠加Zadoff-Chu序列进行信道估计的最小二乘算法。该方法可以大大降低算法复杂度,并且不需要信道先验信息、不占用带宽资源。仿真结果验证了该方法的有效性,其性能比频域的离散傅里叶变换算法和线性最小均方误差算法性能更优。     

SMI算法的线性Systolic阵实现

本文给出了一种用线性Ｓｙｓｔｏｌｉｃ阵实现ＳＭＩ算法的新方法。ＳＭＩ算法全部由快速Ｇｉｖｅｎｓ变换实现，阵列只需一种工作状态，与现有常规方法相比，计算时间相同，但阵列设计、实现和控制都得到简化。