SYSTOLIC BLOCK HOUSEHOLDER TRANSFORMATION FOR RLS ALGORITHM WITH 2-LEVEL PIPELINED IMPLEMENTATION

被引:31
作者
LIU, KR
HSIEH, SF
YAO, K
机构
[1] NATL CHIAO TUNG UNIV,DEPT COMMUN ENGN,HSINCHU 30039,TAIWAN
[2] UNIV CALIF LOS ANGELES,DEPT ELECT ENGN,LOS ANGELES,CA 90024
关键词
D O I
10.1109/78.127965
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
The QR decomposition, recursive least squares (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 Givens 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 known 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, a modified HT algorithm permits a two-level pipelined implementation of the SBHT systolic array at both the vector and word levels. 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.
引用
收藏
页码:946 / 958
页数:13
相关论文
共 27 条
[1]  
BELLANGER MG, 1988, P IEEE ISCAS FINLAND, P2635
[2]   LIMITED-PRECISION EFFECTS IN ADAPTIVE FILTERING [J].
CIOFFI, JM .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1987, 34 (07) :821-833
[3]  
CIOFFI JM, 1990, APR P IEEE INT C AC, P1619
[4]  
GENTLEMAN WM, 1981, P SOC PHOTO-OPT INST, V298, P19
[5]  
Golub G.H., 1996, MATH GAZ, VThird
[6]  
Haykin S., 1986, ADAPTIVE FILTER THEO
[7]   SYSTOLIC NETWORKS FOR ORTHOGONAL DECOMPOSITIONS [J].
HELLER, DE ;
IPSEN, ICF .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1983, 4 (02) :261-269
[8]  
JOHNSSON L, 1982 P C ADV RES VLS, P123
[9]  
Kalson S., 1985, Proceedings of the SPIE - The International Society for Optical Engineering, V564, P28
[10]   WAFER-SCALE INTEGRATION AND 2-LEVEL PIPELINED IMPLEMENTATIONS OF SYSTOLIC ARRAYS [J].
KUNG, HT ;
LAM, MS .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1984, 1 (01) :32-63