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 条
[11]  
KUNG SY, 1988, VLSI ARRAY PROCESSOR
[12]   STABILITY OF RECURSIVE QRD-LS ALGORITHMS USING FINITE-PRECISION SYSTOLIC ARRAY IMPLEMENTATION [J].
LEUNG, H ;
HAYKIN, S .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1989, 37 (05) :760-763
[13]  
LING FY, 1986, IEEE T ACOUST SPEECH, V34, P829, DOI 10.1109/TASSP.1986.1164877
[14]  
LIU KJR, 1990, APR P ICASSP ALB, P1631
[15]  
LIU KJR, 1989, MAY P INT C SYST ARR, P401
[16]   A ROTATION METHOD FOR COMPUTING THE QR-DECOMPOSITION [J].
LUK, FT .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1986, 7 (02) :452-459
[17]   ANALYSIS OF A RECURSIVE LEAST-SQUARES SIGNAL-PROCESSING ALGORITHM [J].
LUK, FT ;
QIAO, SZ .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1989, 10 (03) :407-418
[18]  
MCWHIRTER JG, 1983, P SOC PHOTO-OPT INST, V431, P105, DOI 10.1117/12.936448
[19]   SYSTOLIC ARRAY PROCESSOR FOR MVDR BEAMFORMING [J].
MCWHIRTER, JG ;
SHEPHERD, TJ .
IEE PROCEEDINGS-F RADAR AND SIGNAL PROCESSING, 1989, 136 (02) :75-80
[20]  
OWSLEY NL, 1985, ARRAY SIGNAL PROCESS, P115