This paper reviews recent developments in signal processing and surveys recent progress in parallel processing algorithms and architectures for their real-time implementation. It has previously been shown^1-2 that the major computational requirements for many important real-time signal processing tasks can be reduced to a common set of basic matrix operations including matrix-vector multiplication, matrix-matrix multiplication and addition, matrix inversion, solution of systems of linear equations, least squares approximate solution of linear systems, eigensystem solution, generalized eigen-systems solution, and singular value decomposition (SVD) of matrices. To this list, we would now add the generalized singular value decompositions of Van Loan³,⁴ and Paige-Saunders⁵. The first five matrix operations listed above may be computed non-iteratively, and systolic array architectures and algorithms are available which provide modular parallelism, local interconnects, regular data flow, and high efficiency, with the efficiency essentially constant as the parallelism is increased^6-8. Parallel computation of eigensystems, generalized eigensystems, the singular value decomposition, and the generalized singular value decomposition is more difficult, since the computation is necessarily iterative, and it is difficult to utilize only local communication between processing elements while maintaining high efficiency. Algorithms for the latter problems are therefore still the subject of intensive research.

Linear Algebra (i.e., the algebra of vector spaces) provides widely used mathematical tools and concepts which are today being considered for implementation in special compute architectures. It seems that so many signal processing problems can be expressed and, more importantly, implemented efficiently as a sequence of vector and matrix operations, that a signal processing system with a capability for high speed linear algebra is necessary if the more advanced signal processing algorithms are to be implemented to operate in real time. The purpose of this paper is to support the notion that linear algebra is a sound basis for important signal processing system implementations and, further, to suggest that multilinear algebra (i.e., the algebra of vector, bivector, trivector, etc. spaces) offers an even broader set of signal processing "tools". Examples and ideas from direction finding and time series analysis are discussed.

New methods for adaptive detection and estimation are presented for one-dimensional and two-dimensional signals. These methods have been developed by the writers during the past four years [1-9]. It is assumed that little prior information is known and that the spatial and tempral frequencies of monochromatic, plane wave signals may be closely spaced relative to the reciprocals of the sizes of apertures in space and time.

Architectural solutions to large signal and data processing problems can now in many cases be implemented in VLSI-complexity silicon integrated circuits in a majority of cases, provided that the economic constraints of design costs, unit costs, and schedule can be resolved. However, for a small subclass of signal processing tasks involving very high input data bandwidths and/or large volume computation, VLSI implementations of parallel architectures are a useful but incomplete solution, or in some cases even an ina dequate one; alternate device technologies, e.g., high speed Gallium Arsenide digital com-ponents, must be considered for very high clock rate processors. This paper explores the tradeoffs between architectures and device technologies and the roles which they can play in very high bandwidth classical signal processing tasks.

This paper describes the real time processing requirements for radio synthesis arrays. The processing is real time, not in the sense that it must occur synchronously with the data collection, but that it must progress at the rate data is collected if a growing backlog is to be avoided. Two types of radio synthesis arrays are used in radio astrophysics, real time or connected arrays and arrays using the Very Long Baseline Interferometry (VLBI) tech-nique. In the former, the elements are phase locked to a common clock and data are corre-lated in real time. In the latter, the elements are phased to a local clock and the data are recorded locally. Two basic processing steps, fringe processing and map processing, are involved. Both steps are shown to be computationally demanding. The large number of computing instructions involved combined with the nature of the algorithms makes the development of special purpose hardware very attractive. The technology involving the development of optimum processing algorithms, however, has been progressing rapidly. This greatly complicates the choice of hardware.

The applications of adaptive least-squares lattice structures to problems in underwater acoustics are discussed. Both single and dual channel problems are considered. The prewhitening of acoustic reverberation data is used as an illustration of the former while sea surface reverberation rejection is suggested as an application of the latter.

Special-purpose hardware has previously been proposed for recursive filter computations. In some cases the hardware capacity may not match the filter order, requiring the problem to be partitioned. Tradeoffs between hardware design, hardware dimensions and partitioning methods will be discussed.

This article is a survey in which several examples of hardware implementation of floating-point arithmetic are discussed. Examples include chip-sets, single-chip proces-sors and single/multi board processors.

This paper concerns the systolic array computation of the generalized singular value decomposition. Numerical algorithms for both one-and two-dimensional systolic architectures are discussed.

Systolic architectures due to Brent, Luk, and Van Loan are today the most promising idea for computing the symmetric eigenvalue and singular value decompositions in real time. These systolic arrays, however, are only able to solve problems of a given, fixed size. Here we present two modified algorithms and a modified array that do not have this disadvantage. The results of a numerical experiment show that a combination of one of the new algorithms and the new array is just as efficient as the Brent-Luk-Van Loan method.

In this paper we present a tree architecture for eigendecomposition based on a Divide-and-Conquer approach. A comparison of this method with the previously proposed systolic array architecture is made. Strategies for serial-parallel computation and fault-tolerant design are indicated. The suitability of this architecture for VLSI implementation is pointed out.

In this paper we evaluate several techniques for solving the symmetric tridiagonal problem based on the method of isospectral flow. Architectures which result from these considerations are discussed. Their advantages and disadvantages from the viewpoints of numerical accuracy and ease of implementation in VLSI are also investigated.

We discuss the relationship between communication constraints for families of processor arrays and the time complexity of problem solution for sorting and matrix multiplication. We then describe what seems a promising family of arrays for achieving near optimal time complexity for these and other problems.

This paper describes a systolic signal processor architecture which is well suited for digital filtering, target tracking, image processing and signal processing. The architecture is based on apping the widely-used Kalman filter equations onto a linearly connected systolic array. A detailed analysis of finite wordlength effects, roundoff-error propagation, stability and estimation sensitivity is presented for the systolic Kalman filter architecture.

A systolic array for performing recursive least-squares minimization is desc/ performs an orthogonal triangularization of the data matrix using a pipelined SE

The mapping of matrix x matrix multiplication on to both word and bit level systolic arrays has been investigated. It has been found that well defined word and bit level data flow constraints must be satisified within such circuits. An efficient and highly regular bit level array has been generated by exploiting the basic compatibilities in data flow symmetries at each level of the problem. A detailed description of the circuit which emerges is given and some details relating to its practical implementation are discussed.

This paper introduces "Interlaced Counter Propagating (ICP) Systolic Array", a new architecture for high speed systolic digital correlator operation. The interlaced arrangement of Multiply/Accumulate Units (MAUs) allow the processor to achieve 100% efficiency in MAU usage without need for complicated clocking scheme. It also shows a pipelined multiply and accumulate hardware combined with ICP architecture which allows the throughput to exceed the one with an array of conventional MAUs.

A VLSI Multiplication Oriented Processor (MOP) element has been designed for use in array-based 1-D and 2-D modern digital radar applications. We describe how this chip can be used to provide extremely high throughput rates for problems such as beam forming, adaptive Doppler filtering, and high resolution direction finding.

This paper addresses two important problems in systolic arrays: fault-tolerance and two-level pipelining. The fault-tolerant scheme we propose maintains the original data flow patterns by simply by-passing defective cells with a small number of registers. As a result, the desirable properties of systolic arrays, such as local and regular communication, massive parallelism and high data throughput, are all preserved. 'Iwo-level pipelining refers to the use of pipelined functional units in the implementation of systolic cells. This paper also addresses the problem of efficiently utilizing such units to increase overall system throughput. We show that both of these problems can be reduced to the same mathematical problem of incorporating extra delays on certain data paths in originally correct systolic designs. We introduce the mathematical notion of a cut which enables us to handle this problem systematically. The results obtained by applying the techniques described in this paper arc encouraging. When applied to systolic arrays without feedback cycles, the arrays can tolerate large numbers of faults with the addition of very little hardware, while maintaining the original throughput. Furthermore, all of the pipeline stages in the cells can be kept fully utilized through the addition of a small number of delay registers. However, adding delays to systolic arrays with cycles typically induces a significant decrease in throughput. In response to this, we have derived a new class of systolic algorithms in which the data cycle around a ring of processing cells The systolic ring architecture has the property of degrading gracefully as cells fail. It can be used in place of many systolic arrays with feedback cycles. Using our cut theory for arrays without feedback and the ring architecture approach for arrays with feedback, we have an effective fault-tolerant scheme for every systolic array that we have considered. Furthermore, as by-products of the ring architecture approach we have derived new systolic algorithms. These algorithms generally require only one-third to one-half of the number of cells used in previous designs to achieve the same throughput. Included in these new systolic algorithms are ones for LU-decomposition, QR-decomposition and the solution of triangular linear systems.

Inexpensive, efficient VLSI circuits combined with a highly parallel systolic architecture will allow the construction of one gigaflop linear algebra processors for signal processing. This paper presents some results in increasing the efficiency of such processors to 100%.

The Massively Parallel Processor (MPP) was developed to support ultra high-speed ground based image processing. The architecture comprises an array unit (ARU) which processes arrays of data; an array control unit (ACU) which controls the operation of the ARU and performs scalar arithmetic; front-end computers which control the flow of data; and a unique staging memory (SM) which buffers and permutes data. The ARU contains a 128 by 128 array of bit-serial processing elements (PE's). Two-by-four subarrays of PE's are packaged in a custom VLSI HCMOS chip. The staging memory is a large multidimensional-access memory whose primary purpose is to perform a "corner-turning" operation which converts data stored in conventional format to the bit plane format required for ARU processing.

A new generation of opto-electronic signal processors, many exploiting acousto-optic technology, has been developing during the past several years. These processors are designed to perform algebraic operations like matrix-vector and matrix-matrix multiplication. A number of major architectures are reviewed, including some that operate using digital arithmetic. Fundamental limitations are discussed.

Outer product optical processors can perform high accuracy matrix multiplication using binary representations of input matrices. It has been discovered that the outer product matrix between a binary column vector and a binary row vector is formed naturally in a 2-D matrix-addressed display if the components of the column vector and the row vector are applied in parallel to the row and column electrodes, respectively, of the display. One matrix-addressed display device is the Litton magneto-optic Spatial Light Modulator. The design and operational parameters of an outer product optical processor based on this device will be discussed. Initial experimental results will be presented. This outer product optical processor has the potential for compact, rugged design and high speed operation.

An electro-optical engagement-array architecture for performing matrix-matrix multiplication using twos complement arithmetic is pre-sented. Twos complement arithmetic offers a convenient means for handling bipolar numbers, avoids the need for matrix partitioning when the matrices are real, and offers a means for improvement in accuracy over conventional optical analog techniques.

Direct and indirect solutions to linear algebraic equations (LAEs) are considered with attention to the use of optical acousto-optic (AO) systolic array processors. Specific attention is given to error sources in one AO systolic processor. A case study of an LAE solution is conducted. The first error source model for an optical systolic array processor is advanced. Using this and digital computer modeling, a direct solution is found to be less sensitive to various optical system error sources than is an indirect solution. Acoustic attenuation is found to be the dominant error source in the AO systolic array processor considered. Related error source remarks on different bipolar data representation schemes and on optical versus digital solutions to a triangular system of equations are also advanced.

Optical computation is usually performed on signals from the electronic domain, but it is especially powerful when applied to signals already in the optical domain. An example is shown here. Spatial filters representing the positive and negative parts of computer-designed linear discriminants operating in the spectral domain can be used to recognize and classify colors, species, and events. A demonstration in which colors are automatically sorted is given.

Deformable mirror and charge coupled devices are combined with parallel high speed electronics in order to produce a nearest neighbor computer in which the value at each point in a 2D array may be simultaneously updated based on values at the immediately surrounding points. The concept of such a machine is described together with its application to image processing and partial differential equation solution. Repeated iteration enables filtering which involves points at greater distance than the nearest neighbor. The problem is discussed of overcoming the limited dynamic range of the deformable mirror device for application to the solution of partial differential equations.

A working paper is presented on the mathematical development and analysis of an optically implemented multiple-stage Kalman filter algorithm which uses two previously developed estimation models (linear first-order Gauss-Markov and constant turn-rate) for high energy laser pointing and tracking. An overview of the estimation models reveals model equivalence in mid- to long-range tracking applications and superiority of the constant turn-rate model (at the expense of a much higher computational burden) for both short-range and evasive target tracking. Real world constraints are to be forcibly imposed on the optical filter by limiting the choice of all system components to off-the-shelf units whose performance criteria are well characterized. Derivation of the filter architecture subject to the real world constraints shows the pielined iterative systolic array architecture to be significantly superior. Filter development based on this architecture is expected to generate a MTF which yields superior performance of the optical filter over its electronic counterpart based both on the output statistics produced and system throughput capability Additional analyses of filter performance reveal potential filter enhancement with the incorporation of range and relative velocity data obtained through use of a laser doppler velocimeter and an optical heterodyne detector. Current and planned future research efforts are also presented.

A recent research and development effort at Emerson Electric's Electronics and Space Division has been concerned with the development of a new type of modular reconfigurable signal processor called the Distributed Signal Processor (DSP). Such a processor would be capable of processing several different types of sensors simultaneously by operating in a multiple instruction, multiple data stream (MIMD) mode. This MIMD architecture would allow for the development of both general purpose and highly algorithm-specific processor modules which could be coupled together in varying numbers depending on the processing requirements. In addition, the processors should be dynamically reconfigurable to allow a degree of flexibility in the processor as the mission needs change and to provide a measure of fault tolerance.

Discrete fourier transform is represented as a real transform through using number groups and removing redundancy. The resulting configuration is further written in terms of (skew) circular correlations, which can be implemented by fast correlation techniques. The number of data points considered is a power of 2, even though the method can be generalized to any number of data points.

An experimental data processing system has been developed to investigate the feasibility of processing high-speed multispectral image data in real time, onboard the spacecraft. The key design objective was to achieve the desired high throughput rate while maintaining processing accuracy and maximizing system programmability and adaptability. The real-time processor is coupled to test support and computing equipment for the purpose of evaluating and demonstrating the operational performance of the individual processing functions as well as the overall architectural approach. The test and evaluation procedure is described and results of that activity are presented.

Many linear algebra operations, matrix inversions, etc. are required in pattern recognition as well as in signal processing. In this paper, we concentrate on feature extraction pattern recognition techniques (specifically a chord distribution and a moment feature space). For these two case studies, we note the various linear algebra operations required in distortion-invariant pattern recognition. Systolic processors can easily perform all reauired linear algebra functions.

Digital processing of audio signals requires high speed and usually expensive hardware. A design approach using a processor with filtering multuplexing technique is described. This design was developed to achieve a high signal dynamic range of ten octave bands and to minimize hardware complexity.

This paper reports on a set of experiments involving an acousto-optic RF spectrum analyzer, an electro-optic tunable frequency filter, and a slit detection configuration. The system extracts in real time any wanted signal out of a multifrequency RF population and recovers its temporal modulation information. Its rise time is faster than the acoustic pulse transit time through the optical beam in the Bragg cell, yet its frequency resolution remains as fine as its A/O spectrum analyzer parameters dictate. The E/0 tunable frequency filter operates as a real time optical processor, hence significantly reducing digital processing of the RF spectrum. First, a conceptual system using the 5376 electrode Xerox linear Total Internal Reflection (TIR) spatial light modulator is described. Experimental results using a 10 channel TIR spatial light modulator are then presented which verify the concepts, demonstrate the retrieval of a weak signal, > 20 dB dynamic range, and real time selection of desired frequency signals. The recovery of temporal information is demonstrated using an imaging technique showing 5 1 μs modulation pulse rise time using a narrow slit at the photodetector. Tradeoffs exist between dynamic range, recovered rise time, laser power, Bragg cell efficiency, TIR efficiency and channels cross-talk, and photodetector/amplifier noise. These aspects will be discussed.

An acousto-optic system for the calculation of a signal bispectrum is described. The system is a modification of a time-integrating signal correlator and has the capability of real or near-real time operation. Preliminary experimental results are presented indica-ting the nature of the bispectral output.

Pseudorandom sequences are series of apparently random numbers generated, for example, by linear or nonlinear feedback shift registers. An important application of these sequences is in spread spectrum communication systems, in which, for example, the transmitted carrier phase is digitally modulated rapidly and pseudorandomly and in which the information to be transmitted is incorporated as a slow modulation in the pseudorandom sequence. In this case the transmitted information can be extracted only by a receiver that uses for demodulation the same pseudorandom sequence used by the transmitter, and thus this type of communication system has a very high immunity to third-party interference. However, if a third party can predict in real time the probable future course of the transmitted pseudorandom sequence given past samples of this sequence, then interference immunity can be significantly reduced.. In this application effective pseudorandom sequence prediction techniques should be (1) applicable in real time to rapid (e.g., megahertz) sequence generation rates, (2) applicable to both linear and nonlinear pseudorandom sequence generation processes, and (3) applicable to error-prone past sequence samples of limited number and continuity. Certain optical processing techniques that may meet these requirements are discussed in this paper. In particular, techniques based on incoherent optical processors that perform general linear transforms or (more specifically) matrix-vector multiplications are considered. Computer simulation examples are presented which indicate that significant prediction accuracy can be obtained using these transforms for simple pseudorandom sequences. However, the useful prediction of more complex pseudorandom sequences will probably require the application of more sophisticated optical processing techniques.