A CLASS OF SQUARE-ROOT AND DIVISION FREE ALGORITHMS AND ARCHITECTURESFOR QRD-BASED ADAPTIVE SIGNAL-PROCESSING

The least squares (LS) minimization problem constitutes the core of ma ny real-time signal processing problems, such as adaptive filtering, s ystem identification and adaptive beamforming. Recently efficient impl ementations of the recursive least squares (RLS) algorithm and the con strained recursive least squares (CRLS) algorithm based on the numeric ally stable QR decomposition (QRD) have been of great interest. Severa l papers have proposed modifications to the rotation algorithm that ci rcumvent the square root operations and minimize the number of divisio ns that are involved in the Givens rotation. It has also been shown th at all the known square root free algorithms are instances of one para metric algorithm. Recently, a square root free and division free algor ithm has also been proposed. In this paper, we propose a family of squ are root and division free algorithms and examine its relationship wit h the square root free parametric family. We choose a specific instanc e for each one of the two parametric algorithms and make a comparative study of the systolic structures based on these two instances, as wel l as the standard Givens rotation. We consider the architectures for b oth the optimal residual computation and the optimal weight vector ext raction. The dynamic range of the newly proposed algorithm for QRD-RLS optimal residual computation and the wordlength lower bounds that gua rantee no overflow are presented. The numerical stability of the algor ithm is also considered. A number of obscure points relevant to the re alization of the QRD-RLS and the QRD-CRLS algorithms are clarified. So me systolic structures that are described in this paper are very promi sing, since they require less computational complexity (in various asp ects) than the structures known to date and they make the VLSI impleme ntation easier.