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     

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.     

Block filtered-s least mean square algorithm for active control of non-linear noise systems

In this study, the authors propose a block formulation of an algorithm, called the block-filtered-s LMS (BFSLMS) algorithm, for active control of non-linear noise processes for a multichannel setup. A reduced structure of the fast Fourier transform (FFT)-based BFSLMS-M (FBFSLMS-M) algorithm has also been studied. From this, the multichannel block filtered-x LMS (FBFXLMS-M) algorithm has been derived as a special case. The simulation results show that these algorithms have a matching performance with the already existing algorithms, with a relatively low computational complexity. A reduced structure delayless FBFSLMS algorithm for the multichannel case has also been developed which has a lesser computational complexity than its time-domain counterpart. Apart from this, it has no delay which, in general, is inherent in the block adaptive algorithms.     

Fast time-series adaptive-filtering algorithm based on the QRDinverse-updates method

A new adaptive filtering algorithm for time-series data based on the QRD inverse updates method of Pan and Plemmons (1989) is derived from first principles. In common with other fast algorithms for time-series adaptive filtering, this algorithm only requires O(p) operations for the solution of a pth-order problem. Unlike previous fast algorithms based on the QRD technique, the algorithm presented here explicitly produces the transversal filter weights. Furthermore the derivation of the algorithm is achieved, quite simply, by means of signal-flow-graph manipulation. The relationship between this fast QRD inverse updates algorithm and the FTF algorithm is briefly discussed. The results of some preliminary computer simulations of the algorithm, using finite-precision floating-point arithmetic, are presented     

Regular implementation algorithms of time domain aliasingcancellation

The authors propose two highly regular algorithms for realising the time domain aliasing cancellation (TDAC) technique. The first TDAC implementation, which is based on the fast discrete cosine transform, effectively adopts analysis and synthesis window functions in the transform structure. This implementation algorithm achieves the least computational complexity in TDAC processes. The second TDAC implementation, which extends Goertzel's concept, uses a simple selectable-fixed-coefficient second-order infinite impulse response (IIR) filter to recursively achieve multichannel audio encoding and decoding processes. With a properly selected coefficient, this recursive implementation achieves a lower round-off-error than the current fast implementations and the direct implementation in finite wordlength. In recently developed high quality consumer products, the first algorithm is suitable to be realised in digital signal processing chips and the second one will be a better choice for VLSI implementation     

Adaptive lattice bilinear filters

Two fast least-squares lattice algorithms for adaptive nonlinear filters equipped with bilinear system models are presented. The lattice filter formulation transforms the nonlinear filtering problem into an equivalent multichannel linear filtering problem, thus using multichannel lattice filtering algorithms to solve the nonlinear filtering problem. The computational complexity of the algorithms is an order of magnitude smaller than that of previously available methods. The first of the two approaches is an equation error algorithm that uses the measured desired response signal directly to compute the adaptive filter outputs. This method is conceptually very simple, but results in biased system models in the presence of measurement noise. The second is an approximate least-squares output error solution; the past samples of the output of the adaptive system itself are used to produce the filter output at the current time. Results indicate that the output error algorithm is less sensitive to output measurement noise than the equation error method     

A two-dimensional fast lattice recursive least squares algorithm

This paper is mainly devoted to the derivation of a new two-dimensional fast lattice recursive least squares (2D FLRLS) algorithm. This algorithm updates the filter coefficients in growing-order form with linear computational complexity. After appropriately defining the “order” of 2D data and exploiting the relation with 1D multichannel, “order” recursion relations and shift invariance property are derived. The geometrical approaches of the vector space and the orthogonal projection then can be used for solving this 2D prediction problem. We examine the performances of this new algorithm in comparison with other fast algorithms     

Hybrid Iterative Decoding for Low-Density Parity-Check Codes Based on Finite Geometries

In this letter, a two-stage hybrid iterative decoding algorithm which combines two iterative decoding algorithms is proposed to reduce the computational complexity of finite geometry low-density parity-check (FG-LDPC) codes. We introduce a fast weighted bit-flipping (WBF) decoding algorithm for the first stage decoding. If the first stage decoding fails, the decoding is continued by the powerful belief propagation (BP) algorithm. The proposed hybrid decoding algorithm greatly reduces the computational complexity while maintains the same performance compared to that of using the BP algorithm only.     

On the duality between the fast transversal and the fast QRDadaptive least squares algorithms

The duality between the fast transversal and the fast QRD adaptive least squares algorithms is established. It is shown that these two algorithmic families are related via a time-varying state transformation. The state transformation method is then applied to both the fast Kalman as well as the FAEST (PTF) algorithm to derive fast QRD counterparts     

Efficient optimal and suboptimal radio resource allocation in OFDMA system

A fast optimal algorithm for solving radio resource allocation (RRA) problems in orthogonal frequency division multiple access (OFDMA) systems is proposed based on branch- and-bound (BnB) approach. The proposed algorithm offers the same performance as that achieved by some other existing optimal algorithms but with much reduced average computational complexity. As an effort in providing trade-off between performance and computational complexity, two suboptimal algorithms are also developed. Simulation results are shown to compare the performance and complexity of the proposed suboptimal algorithms with several existing algorithms.     

Efficient detection algorithms for MIMO channels: a geometrical approach to approximate ML detection

It is well known that suboptimal detection schemes for multiple-input multiple-output (MIMO) spatial multiplexing systems (equalization-based schemes as well as ing-and-cancelling schemes) are unable to exploit all of the available diversity, and thus, their performance is inferior to ML detection. Motivated by experimental evidence that this inferior performance is primarily caused by the inability of suboptimal schemes to deal with "bad" (i.e., poorly conditioned) channel realizations, we study the decision regions of suboptimal schemes for bad channels. Based on a simplified model for bad channels, we then develop two computationally efficient detection algorithms that are robust to bad channels. In particular, the novel sphere-projection algorithm (SPA) is a simple add-on to standard suboptimal detectors that is able to achieve near-ML performance and significantly increased diversity gains. The SPA's computational complexity is comparable with that of ing-and-cancelling detectors and only a fraction of that of the Fincke-Phost sphere-decoding algorithm for ML detection.     

Multirate-based fast parallel algorithms for 2-D DHT-based real-valued discrete Gabor transform

Novel algorithms for the multirate and fast parallel implementation of the 2-D discrete Hartley transform (DHT)-based real-valued discrete Gabor transform (RDGT) and its inverse transform are presented in this paper. A 2-D multirate-based analysis convolver bank is designed for the 2-D RDGT, and a 2-D multirate-based synthesis convolver bank is designed for the 2-D inverse RDGT. The parallel channels in each of the two convolver banks have a unified structure and can apply the 2-D fast DHT algorithm to speed up their computations. The computational complexity of each parallel channel is low and is independent of the Gabor oversampling rate. All the 2-D RDGT coefficients of an image are computed in parallel during the analysis process and can be reconstructed in parallel during the synthesis process. The computational complexity and time of the proposed parallel algorithms are analyzed and compared with those of the existing fastest algorithms for 2-D discrete Gabor transforms. The results indicate that the proposed algorithms are the fastest, which make them attractive for real-time image processing.     

A fast recursive total least squares algorithm for adaptive IIR filtering

This work develops a new fast recursive total least squares (N-RTLS) algorithm to recursively compute the total least squares (TLS) solution for adaptive infinite-impulse-response (IIR) filtering. The new algorithm is based on the minimization of the constraint Rayleigh quotient in which the first entry of the parameter vector is fixed to the negative one. The highly computational efficiency of the proposed algorithm depends on the efficient computation of the gain vector and the adaptation of the Rayleigh quotient. Using the shift structure of the input data vectors, a fast algorithm for computing the gain vector is established, which is referred to as the fast gain vector (FGV) algorithm. The computational load of the FGV algorithm is smaller than that of the fast Kalman algorithm. Moreover, the new algorithm is numerically stable since it does not use the well-known matrix inversion lemma. The computational complexity of the new algorithm per iteration is also O(L). The global convergence of the new algorithm is studied. The performances of the relevant algorithms are compared via simulations.     

Fast adaptive algorithms for multichannel filtering and systemidentification

Fast transversal and lattice least squares algorithms for adaptive multichannel filtering and system identification are developed. Models with different orders for input and output channels are allowed. Four topics are considered: multichannel FIR filtering, rational IIR filtering, ARX multichannel system identification, and general linear system identification possessing a certain shift invariance structure. The resulting algorithms can be viewed as fast realizations of the recursive prediction error algorithm. Computational complexity is then reduced by an order of magnitude as compared to standard recursive least squares and stochastic Gauss-Newton methods. The proposed transversal and lattice algorithms rely on suitable order step-up-step-down updating procedures for the computation of the Kalman gain. Stabilizing feedback for the control of numerical errors together with long run simulations are included     

On maximum-likelihood detection and the search for the closest lattice point

Maximum-likelihood (ML) decoding algorithms for Gaussian multiple-input multiple-output (MIMO) linear channels are considered. Linearity over the field of real numbers facilitates the design of ML decoders using number-theoretic tools for searching the closest lattice point. These decoders are collectively referred to as sphere decoders in the literature. In this paper, a fresh look at this class of decoding algorithms is taken. In particular, two novel algorithms are developed. The first algorithm is inspired by the Pohst enumeration strategy and is shown to offer a significant reduction in complexity compared to the Viterbo-Boutros sphere decoder. The connection between the proposed algorithm and the stack sequential decoding algorithm is then established. This connection is utilized to construct the second algorithm which can also be viewed as an application of the Schnorr-Euchner strategy to ML decoding. Aided with a detailed study of preprocessing algorithms, a variant of the second algorithm is developed and shown to offer significant reductions in the computational complexity compared to all previously proposed sphere decoders with a near-ML detection performance. This claim is supported by intuitive arguments and simulation results in many relevant scenarios.     

A delta least squares lattice algorithm for fast sampling

Most shift operator-based adaptive algorithms exhibit poor numerical behavior when the input discrete time process is obtained from a continuous time process by fast sampling. This includes the shift operator based least squares lattice algorithm. We develop a delta least squares lattice algorithm. This algorithm has a low computational complexity compared with the delta Levinson RLS algorithm and shows better numerical properties compared with the shift least squares lattice algorithm under fast sampling. Computer simulations show that the new algorithm also outperforms an existing delta least squares lattice algorithm     

Nonlinear error modified equalization algorithm in high-order modulation of satellite communication

Aiming at the larger computation and the slower speed of nonlinear error compensation of traditional equalization algorithms,the fast nonlinear error equalization algorithm with amplitude and phase separation was constructed.It combined the feedback equalization to reduce the computational complexity respectively.In order to eliminate nonlinear interference and memory interference,the algorithm utilized the Volterra model to modify the error and it was adapted to update the feedback equalization parameters.The theoretical analysis and simulation compared proposed algorithm and existing conventional equalization algorithms from the bit error rate,convergence speed and computational complexity.The results show that the computational complexity is only equivalent to 14.1%～24.9% of other algorithms and proposed method can cancel the nonlinear interference quickly.     

A unified framework for finite-memory detection

In this paper, we present a general approach to finite-memory detection. From a semi-tutorial perspective, a number of previous results are rederived and new insights are gained within a unified framework. A probabilistic derivation of the well-known Viterbi algorithm, forward-backward, and sum-product algorithms, shows that a basic metric emerges naturally under very general causality and finite-memory conditions. This result implies that detection solutions based on one algorithm can be systematically extended to other algorithms. For stochastic channels described by a suitable parametric model, a conditional Markov property is shown to imply this finite-memory condition. This conditional Markov property, although seldom met exactly in practice, is shown to represent a reasonable and useful approximation in all considered cases. We consider, as examples, linear predictive and noncoherent detection schemes. While good performance for increasing complexity can often be achieved with a finite-memory detection strategy, key issues in the design of detection algorithms are the computational efficiency and the performance for limited complexity.     

最大阵元利用率MIMO雷达阵列优化快速算法

针对MIMO雷达最大阵元利用率阵列结构优化算法中使用穷举搜索运算量太大的问题,提出了一种快速算法。该算法在只包含两个阵元的最优阵列基础上,通过迭代的方式向前一个最优阵列增加一个新阵元来寻找包含指定阵元数的最优阵列。文中对该算法的有效性进行了证明,并与穷举搜索方法做了复杂度比较。理论分析和仿真实验表明,该算法能够显著降低运算量,尤其在阵元数目较大时具有明显优势。并且,在阵元数一定的情况下,所得到的优化阵列与穷举搜索的结果具有等同的性能。