The computation of the adaptive weight vectors is one of the most difficult of signal processing algorithms used to implement large scale adaptive processing systems. This is due to extremely high computation rates, large dynamic range, and low latency requirements imposed on these systems. For typical adaptive systems, the computation of the adaptive weights requires 50 to 150 GFLOPS of computational throughput. This type of high-throughput adaptive processing calls for special purpose hardware to achieve high efficiency that fully exploits the parallel nature of the adaptive weight computation process.
Current adaptive signal processing research focuses on what is known as the optimal least squares solution to the general adaptive array nulling problem. It is estimated that signal processing for the least squares problem will dominate all other functional requirements for adaptive radar systems in the near future. This dominance occurs as a direct result of the algorithm throughput requirement, which is proportional to the cube of the number of sensor elements in the system. It is estimated that, in many systems, over 90% of the total signal processing load will be dedicated to this function alone. No currently available general purpose signal processing devices or architectures will provide the throughput without the penalty of large card or module counts.
A key application of adaptive least squares computation is in the calculation of beamforming weight vectors for optimal interference suppression (i.e., jamming, multipath) in advanced multi-channel radar, sonar, and adaptive communications systems. However, the same technology is generally applicable to any system that must quickly generate large sample covariance matrices and perform large-scale matrix inversion operations (Least Squares applications).
Previous techniques for finding solutions for these systems have used either a hardwired, non-programmable systolic array approach, or more commonly, programmable digital signal processor (DSP) or microprocessor approaches. The hardwired logic methods can be very efficient, but are quite inflexible. Approaches using multiple programmable DSP devices (such as those from Texas Instruments, Motorola, etc.) are very flexible, but suffer from poor efficiency and high computation latencies, primarily due to the large number of DSP devices that must be utilized to achieve the necessary arithmetic throughput. Although a processor embodying the present invention can be implemented as a highly optimized systolic array, it retains much of the flexibility of a programmable data-flow system, allowing efficient implementation of algorithm variations.
A version of a hardwired linear systolic array of processors, called MUSE, was developed at Massachusetts Institute of Technology Lincoln Laboratory, as described in "MUSE--A Systolic Array for Adaptive Nulling with 64 Degrees of Freedom, Using Givens Transformations and Wafer Scale Integration," Technical Report 886, 18, May 1990. The MUSE array specializes in real-time adaptive antenna nulling computations for a 64 degree-of-freedom ("DOF") sidelobe canceller radar system. The MUSE architecture consists of a linear systolic array of vector rotation cells that perform voltage domain Cholesky factorization of a sample covariance matrix using a series of Givens transformations. The MUSE then partially backsolves the Cholesky factor for an adaptive weight vector using a fixed sidelobe canceller steering constraint.
Although the MUSE architecture does attack the side-lobe canceller problem, there are some limitations that prohibit its use in a more general RLS and signal processing applications. The MUSE architecture uses a fixed steering constraint, specific to a sidelobe canceller radar system, for the computation of adaptive weights. In addition, MUSE only partially solves for these adaptive weights, requiring external processing hardware to compute the final result. Further, the MUSE architecture operates only on a fixed 64 degree-of-freedom problem size, and cannot be used efficiently on other problem sizes. In order to solve general linear system problems, a method of computing weights from a general constraint is needed. If these weights could be computed within the systolic array, the dependency on external processing could be eliminated.
Another limitation of the MUSE architecture is its inability to perform Cholesky factor downdating. Downdating consists of subtracting off contributions of old data samples from the Cholesky factor as new ones are added. This is useful for implementing sliding window functions on the input data, a function necessary in many signal processing applications. The MUSE architecture operates in a mode where the Cholesky factor is continuously updated. A constant forgetting factor is implemented that acts as an exponentially decaying window on the input data. Although this performs adequately in some applications, it imposes limitations on the types of processing that can be performed.