Systolic Block Householder Transformation for RLS Algorithm with Two-level Pipelined Implementation

Abstract

The QRD RLS algorithm is one of the most promising RLS algorithms, due to its robust numerical stability and suitability for VLSI implementation based on a systolic array architecture. Up to now, among many techniques to implement the QR decomposition, only the Given rotation and modified Gram-Schmidt methods have been successfully applied to the development of the QRD RLS systolic array. It is well-known that Householder transformation (HT) outperforms the Givens rotation method under finite precision computations. Presently, there is no know technique to implement the HT on a systolic array architecture. In this paper, we propose a Systolic Block Householder Transformation (SBHT) approach, to implement the HT on a systolic array as well as its application to the RLS algorithm. Since the data is fetched in a block manner, vector operations are in general required for the vectorized array. However, by using a modified HT algorithm, a two-level pipelined implementation can be used to pipeline the SBHT systolic array both at the vector and word level. The throughput rate can be as fast as that of the Givens rotation method. Our 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 in this paper.