Abstract:
A sonar or radar permits primary distributed scatterers that are close to the sonar or radar relative to the array dimension to be rapidly and accurately located and pertinent characteristics to be estimated, such as Doppler and complex scattering strength. The region viewed is partitioned in annuli instead of in angular pie shaped slices as is normally the case for conventional sonar. This avoids the difficulty with conventional sonar or radar of distinguishing whether a scatterer is in a side lobe or the main beam an dis preferable to conventional sonars or radars in the important case of approaching multiple scatterers, e.g. robotic vehicle sensors or torpedo terminal homing on a target, because near regions may be examined in all directions prior to further regions. Computational speed is achieved by utilizing precomputation and leaving only part of the computation to be performed in real time.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates sonar and radar, and, more particularly, to methods of rapid and accurate mapping of the characteristics of nearby scatterers for array sonar and radar. 
     It is a problem in known array sonar systems to rapidly obtain an accurate map of the location, strength and movement of primary scatterers in the media immediately surrounding a sonar array. This is important where there are multiple sources of interest, e.g. determining ocean surface and volume backscatter characteristics, estimation of fish population, robotic vehicle sensors, target identification, and torpedo terminal homing. In the latter cases, the multiple sources are from a single target and may be used to establish vital charateristics of the target: class, position, orientation and motion. Critical requirements in many of these situations are the ability to perform rapid computations and the ability to survey near regions in all directions prior to ones further away. 
     Several features of conventional sonars limit the accuracy or ability of these systems to solve this problem. These features include the general practice for the simplest to the most sophisticated sonar receivers of partitioning the receiver into a spatial and a temporal part. This practice is based on Middleton D. and Groginsky. H. L., &#34;Detection of Random Acoustic Signals by Receivers with Distributed Elements: Optimum Receiver Structures for Normal Signal and Noise Fields&#34;, Journal Acoustic Society of America 38, 727 (1965) and Straddling C. S. and Baggeroer A. B. &#34;Joint Active and Passive Sonar Signal Processing using Arrays&#34;, Naval Research and Development Center TP 121, December 1968. The first part of the sonar receiver processor depends only on array properties and involves spatial processing or beamforming. Samples of the received signal are multiplied by a weight and delayed before combining in order to provide different sensitivities to different angular directions. Usually this sensitivity is maximized for a given direction. The second part of the processor depends on statistical properties of the signal and external and internal noise, e.g. matched filtering. These approaches encounter difficulties when applied to the specific problem of close, fast moving multiple scatterers. 
     Several problems arise directly from this use of receiver beamforming. (1) A major source of performance degradation with beams is caused by the existence of side lobes or directions having sensitivity peaks other than the desired main lobe peak. A source in a side lobe direction, a direction substantially different from that of the main lobe, cannot be distinguished in direction from a weaker source in the main lobe direction. Reduction of side lobe sensitivity magnitude may be accomplished at the expense of an undesirable degradation in angular resolution of the main lobe. Widlely spread scatterers may not be accurately located due to sidelobes. Adaptive beamforming, including recent developments in high resolution eigen beamforming (see Schmidt R., &#34;Multiple Emitter Location and Signal Parameter Estimation&#34;, Proc. RADC Spectral Estimation Workshop, Rome N.Y. 1979, p243-258 and Wax M and Kailath T, &#34;Extending the Thresholds of the Eigenstructure Methods&#34;, Proc. International Conference on Acoustics, Speech and Signal Processing, (1985) enable the determination of accurate direction for discrete far scatterers and would not be expected to perform well with close, fast moving sources or scatterers. (See items (3) and (4) below.) 
     (2) The desire for wide or omnidirectional coverage, with narrow beams for directional information, means that the beam must be rotated by mechanical or electronic means through a wide angle. The rotation must be sufficiently slow so that energy from the furthest distance to be scanned has time to return to the array before the beam is moved to the next angular direction. An approaching object has time to approach from a given direction while the beam is scanning other directions. The cost of simultaneously forming a large number of beams for substantial angular coverage is normally too great for practical consideration. Close, fast moving multiple scatterers, as might arise in torpedo terminal homing, do not permit time for scanning. Simultaneous forming of multiple beams would generally require more equipment than would be economic or physically reasonable. 
     (3) Conventional beamforming assumes that the sources are at a sufficient distance that the waves striking the array have plane wave fronts. This determines the phase delays to be incorporated at each receiving element so that signals from the elements will add for waves coming from a specific direction. Near sources will not generate plane wave fronts at the array. Near may be many kilometers for surveillance arrays spreading over tens of kilometers. 
     (4) Partitioning a sonar receiver into spatial and temporal parts is optimal only for stationary processes. Scatterers with speeds having high transverse components at short range will not meet this criteria and will present difficulties for a scheme that scans by pie slices. 
     (5) A source of scatterers falling between two adjacent beams is not distinguishable from two sources, one for each beam direction. 
     (6) Environmental conditions are not normally accounted for during beamforming. 
     (7) The entire computation is performed at the time of beamforming. Prior computation is not normally used to reduce real time computational load or to permit more complex computations. In addition spectral methods such as Fast Fourier transforms cannot be used when the array elements are not evenly spaced. 
     The receiver beamformers described above are followed by a temporal processor that for an active sonar involves correlations with matched filters having a range of time delays for range estimation and a range of Doppler frequencies for transverse speed estimation; see Van Trees H. L. &#34;Detection, Estimation and Modulation Theory, Pt III, Radar-Sonar Signal Processing and Gaussian Signals in Noise&#34;, Wiley and Sons, 1971. Variations in Doppler frequency across the array for near sources cannot be taken into account because beamforming was previously performed. Similarly variations in range across the array represent error for near sources. Also detection performance is degraded for near sources because of the variation of signal across the array not accurately accounted for by beamforming. 
     SUMMARY OF INVENTION 
     The present invention provides for processing received sonar or radar array data in space and time simultaneously in order to obtain the best estimate in a least square sense for the immediately surrounding scatterers and their characteristics. This contrasts with the separation into spatial and temporal parts characteristic of present day sonars. Information regarding the array and environmental propagation are used to precompute a matrix in a lengthy computation. This computation includes conditioning of the matrix so that accurate rapid results will be obtained when this matrix is used for real time sonar computation. The real time computation involves matrix-vector multiplication and takes advantage of the development of new high speed computer architectures for matrix-vector computation, e.g. systolic, and decreasing cost of memory. The region in which scatterers are to be located and characterized is divided by radial annuli instead of by angular pies as in conventional sonar. Storage is reduced in most cases by storing only part of the matrix relevant to a specific annulus and modifying this matrix for use with different annuli. 
     This simultaneous processing and annular division solves the problems discussed previously which are characteristic of general sonar practice. Direct estimation of the scatterer environment is used which makes no assumptions regarding noise and signal statistics other than dominance of primary scattering. As a result, the response is uniform across angle thus avoiding multiple beam related side lobe degradation and resolution issues, scanning is omnidirectional for first identification of close scatterers in all directions, scatterers may be close to the array relative to array size as plane wave fronts are not assumed, scatterers may be moving at speeds with transverse components large enough to present difficulties for mutlibeam sonars, the use of extensive prior computation permits a more sophisticated sonar than that used in general practice to operate in real time, non uniform spacing of array elements is easily incorporated into the precomputation with no additional cost in real time performance, and environmental propagation characteristics may be included in the prior computation without degrading real time speed. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic block diagram for a first preferred embodiment sonar system; 
     FIG. 2 shows a typical display produced by the first preferred embodiment system; 
     FIG. 3 illustrates the manner of subdividing the region illuminated by a sonar transmit beam for the purpose of processing. 
     FIG. 4 shows the matrix-vector systolic processor for computing scatterer strengths as a function of location. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 illustrates the components of a first preferred embodiment sonar system for an active sonar in a typical application. The system, generally denoted 30, includes hydrophone array 32, transmit/receive switch 34, transmitter electronics 36, analog to digital converters 38, matrix-vector systolic array processor 40, interface 42, and console and display 44. 
     The operator console 44 keyboard or a specially designed control panel acts as the input to the system. The operator selects the desired region of ocean he wishes to see and the parameter which he desires to see displayed as a contour plot. For example, he may select a range of 100 to 1000 feet, a range resolution of 20 feet and a Doppler velocity of 10 feet per second and magnitude of scattering strength as the contour or color display parameter. Alternatively, he could select Doppler velocity as the contour parameter and display only scattering strengths above a certain threshold. A control microprocessor reads in the desired display parameters input by the operator at the console 44 keyboard. The unit determines the frequency (e.g. 30 kHz to 120 kHz) and pulse length (e.g. 0.3 msec) to be used based on these inputs and compatibility and equipment preferences. For example, a long maximum range requires a long pulse for energy which then precludes the highest resolution which is only obtainable with the short pulse. 
     Four by four hydrophone array 32, sensitive to acoustic pressure, acts as the transducer for converting acoustic pressure to electronic voltage in receive mode and vice versa in the transmit mode. A transmit-receive switch 34 enables the hydrophone array to both transmit and receive. The signals supplied to each transducer are appropriately phase shifted with respect to each other so as to form a transmit beam to illuminate the desired region of the medium surrounding the array with a pulse having a narrow band of frequencies as determined by operator inputs. The transmit-receive switch switches to receive as soon as transmission of the transmit pules is completed. The signal from each hydrophone is passed through an analog to digital converter 38. The analog to digital converter box 38 in FIG. 1 is assumed to include appropriate conventional signal processing prior to conversion, such as antialias filters, time varying gain, and signal conditioners. Processing is carried out in systolic matrix-vector processor 40 as described in following sections. 
     A TV or graphics display 44 displays the scattering strength for the region of ocean specified by the operator with the parameter selected as a contour or color plot, see FIG. 2 for a tyical display. The operator selects the angular cross section of the region to be displayed on the screen or asks for some rotating sequence. If the operator specifies inconsistent parameters, for example, a higher resolution at longer ranges than reasonable, the highest possible resolution will be used. The display will be correctly annotated and also used to display messages regarding operator inconsistencies or equipment malfunctions. 
     The complete region illuminated by the transmit beam is subdivided into slightly overlapping annular segments. Parts of two annuli are illustrated in FIG. 3 and referenced as A and B. Matching the received signal for a specific time interval with sources in an annulus corresponding to this time interval is reasonable if primary scattering (including local interscatterer mutliple reflections) dominate and the region covered by the transmit beam is fully covered by the subdivided region. Overlap also accounts for the length of the transmitted pulse. The subdivision into annuli permits much faster computation than computing strengths of scatterers for all ranges simultaneously. For example, the number of multiply and add operations required for multiplying an M by M matrix by an M length vector is M**2. Performing N matrix-vector computations with matrices of size M/N by M/N is N times faster. The partitioning is by annuli rather than by angular slices as in conventional sonar. 
     A given annular segment is now further subdivided into volume elements by means of a grid as shown in FIG. 3; a typical element is illustrated by shading. The grid is selected so that the midpoints of the elements are closer to each other than the distance associated with the highest resolution of the full array. This may be determined approximately from the inverse of the overall width of the array for each direction or more exactly by using appropriate equations; see Urick R. J., &#34;Fundamentals of Underwater Sound for Engineers&#34; McGraw-Hill, 1983. A single scatterer located at the center of a volume element is assumed to be representative of that element. Assuming a Gaussian scatterer, i.e. the region has many appropriately equal scatterers, the scatterer at the pth element can be represented by a complex magnitude, Apl, for the lth Doppler frequency. At the frequencies of interest, the complex received signal at the kth time instant and ith array element due to the pth scatterer, having the lth Doppler relative to the center of the array, may be written as a function of the propagation characteristics between them, e.g. the attenuation, time delay and relative direction of the Doppler, 
     
         Zip(Tk,Wl)=Re{QipAplF(Tk-Sip) exp [jWiplTk]}               (1) 
    
     where F(t)=f(t)exp[jg] is the complex envelope of the transmitted pulse, Sip is the propagation delay between the ith receiver and pth scatterer, Wipl is the lth array center Doppler frequency adjusted to the ith array element and pth scatterer, Qip is the attenuation from the ith array element to the pth scatterer including the attentuation resulting from the transmit beam pattern, Re indicates real part, lower case letters are generally indices, upper case letters are variables, and j is the imaginary unit. 
     The attenuation, time delay and angles for Doppler computation may be obtained from ray tracing or other means. 
     The effect due to uncoupled primary scatterers at the ith receiver is then the sum of the effect of each of the P scatterers in the annulus considered, 
     
         Zi(Tk,Wl)=Zil(Tk,Wl)+. . . +Zip(Tk,Wl)+. . . +ZiP(Tk,Wl)   (2) 
    
     If we form a vector of measurements Z(Tk,Wl) for the I receivers, we can write this as ##EQU1## where Al is the P component vector of complex magnitudes Apl and C is an I by P matrix of all other terms for the kth time sample and lth Doppler and defined by equation (3). 
     The K received time signals can be concatenated to form a vector Z of length IK for the lth Doppler frequency, ##EQU2## where Cl has IK rows and P columns and applies to the lth Doppler and is defined by equation (4). Of course, Cl is essentially the C(Tk,Wl) stacked up with C(T1,Wl) on top and C(TK,Wl) at the bottom. 
     As Al and Cl are complex we may write them as sums of real and imaginary parts 
     
         Al=Al&#39;+jAl&#34;   Cl=Cl&#39;+jCl&#34;                                  (5) 
    
     Hence ##EQU3## The minimum mean square estimate can be derived as ##EQU4## Where Dl is a 2P by IK matrix defined by equation (8) and * indicates transpose (all the matrices and vectors are real) and ˜ indicates inverse. However, Ml will probably be ill conditioned because the original space was oversampled. For example, the scattering strengths of two close scatterers, having indistinguishable effect on the data within the level of noise present, cannot be separately estimated. The ill conditioning resulting from such situations will prevent the determination of a correct solution with equation (8) unless it is taken into account in formulating Dl. Ill conditioning is handled during the precomputation by using singular value decomposition (see Lawson C. L and Hanson R. J. &#34;Solving Least Squares Problems&#34;, Prentice-Hall, 1974) of the matrix Ml to form, 
     
         Ml=UlLlVl*                                                 (9) 
    
     where the unitary matrices Ul and Vl are the eigenvector matrices for MlMl* and Ml*Ml, respectively. Consequently, equation (6) may be written as ##EQU5## Ll is a diagonal IK by 2P matrix having the singular values of Ml as the values on the diagonal. Assuming that only B singular values exceed a selected percentage of the maximum, the others are replaced with zeroes. As a result the matrix Dl in equation (8) may be replaced by a conditioned matrix, 
     
         Dlc=VltLlt˜Ult*                                      (11) 
    
     where Ult is a truncated version of Ul and has dimension IK by B, Vlt is a truncated version of Vl and has dimension 2P by B and Llt˜ is a diagonal matrix having reciprocals of the dominant singular values on the diagonal and has dimension B by B. 
     The matrix Dlc is a properly conditioned version of matrix Dl and has the same dimension, 2P by IK. It is only necessary to multiply the data by the matrix Dlc in real time operation of the sonar in order to determine the scatterer strengths for each of the scatterers in the annulus selected having a Doppler of Wl. ##EQU6## The matrix-vector multiplication can be performed in 2P times I times K &#34;multiply and add&#34; operations. The major part of the computation, deriving Dlc is performed in advance and stored. 
     If strengths over a range of Doppler frequencies are required the computation is repeated for l=1 to L. A number of matrices must be stored or computed from a typical one by adjusting for the change in Doppler frequency. 
     In addition to computing the optimum least square scatterer strength for the lth Doppler we compute the mean square error El between the actual measurements Z and those estimated by solution of equation (12), ZlAl 
     
         El=[Z-MlAl]*[Z-MlAl]                                       (13) 
    
     This involves a further matrix-vector computation of MlAl and an inner product computation. If this error is above a certain value it is assumed that negligible scatterers exist at this Doppler frequency and the results of the scattering strength computation are not displayed. The confidence number obtained in the form of this error is normally displayed for the operator to determine the significance of the scattering strength results presented. 
     Each segment in FIG. 3 for a different radius annulus would require a separate different matrix Dlc. We assume for this implementation that the environment and distances involved to the scatterers is such that the acoustic energy propagates in a straight path. Also each annulus is assumed to be subdivided in a similar manner differing only by expanding the geometry. In this case, the matrices for the different annuli are related in simple manner. Consequently only one matrix need be stored and the others for different annuli may be computed from it. This reduces the storage required substantially. Specific properties of environmental propagation may be included from ray tracing at the cost of additional storage. 
     An alternative procedure, frequently followed in signal processing, is to generate an analytic function for which the real part is the actual data and the imaginary part is computed by quadrature filtering or obtained during sampling. A parallel formulation of the equations to that presented may be used to derive a matrix-vector real time computation as in the case described here. 
     FIG. 4 shows a systolic implementation for the matrix-vector multiplication of equation (12), the major part of the real time computation. A systolic implementation is economic to manufacture because only nearest neighbor connections are used. The input samples from the hydrophones are fed sequentially into a serial stream of processing multiply and add elements; see Kung H. T., &#34;High Performance Microprocessor to be used in Groups of Hundreds&#34;, IEEE EASCON, Sep., 1983. The illustration shows how a two by three matrix D may be multiplied by a three vector Z. Each processor stores a diagonal of the matrix D as shown. The result of the multiplication is accumulated from right to left. At the third processor M3 the multiplication z1×d11 is performed and the result passed to processor M2. At processor M2 z2 has just arrived from the left and this is multiplied by the stored value d12 and the result added to the accumulated result from the right. At the same time the multiplication of z1 and d21 occurs in processor M4 and so on. Consequently, up to (P+IK-1) processors could be used effectively in parallel. The matrix coefficients are used in sequence and may therefore be rapidly addressed via stacks in each processor. These coefficients remain in the processors and are modified by scaling for different range computations as suggested previously. The only input and output are the measured data flowing into the processor from the left and the output estimates of scattering strength exiting from the left. 
     The magnitude of the scattering strength is computed before passing the output to the display. Note that this can be accomplished with negligible memory if the matrix rows are rearranged so that odd indexed values are the real parts and even number indices the imaginary parts, rather than having all real parts first and then all imaginary parts next. The magnitude values are displayed across the screen in the manner prescribed by the geometry configuration for the case selected. 
     The same matrix-vector processor may be used to compute the error, equation (13), indicating the validity of the scatterer computation as described previously. In this case the error is passed to the display unit for display. 
     VARIATIONS AND MODIFICATIONS 
     1. Doppler independent system 
     A simplification for the previously described active sonar permits much more rapid computation by neglecting consideration of Doppler. In this case, all matrices for the different Dopplers, Ml, l=1 to L are added and only one computation is required to determine scattering strength in real time. Singular value decomposition is again used to compute the matrix Dc for use in the real time processor. The result is an equation similar to equation (12), ##EQU7## 
     2. Passive Sonar 
     In the case of a passive sonar, a similar procedure to that for the active sonar is followed. The region illuminated by the array is subdivided into regions, (FIG. 3). A representative source is taken at the center of each region. In this case the source is assumed to emit a signal representable by a stationary random process with a power spectrum Y(w) and a sample function y(t). We use the time function of the source in order to utilize the array properties. The kth time sample of the received signal at the ith array element resulting from the pth source is 
     
         Zip(Tk)=QipYp(Tk-Sip)                                      (15) 
    
     where Qip is attenuation between the pth source and ith array element Sip the propagation delay between the pth source and the ith element and Yp is the sample function at the pth source. The Fourier Transform of the k=1 to K set of time samples at the ith receiver is ##EQU8## The ith receiver signal for aII sources is 
     
         Zi(w)=Zi1(w)+Zi2(w)+ . . . +ZiP(w)                         (17) 
    
     Forming a vector for all array elements 
     
         Z(w)=C(w)Y(w)                                              (18) 
    
     where C(w) contains the terms other than source terms in the above equations. The minimum mean square estimate of the Fourier Transform of the time function at the sources is (defining D) 
     
         Y(w)=(C*C).sup.˜ C*Z(w)=DZ(w)                        (19) 
    
     In a similar manner to that used for the active sonar, we precompute D(w) using a singular value decomposition to take care of the singularities; see Lawson C. L and Hanson R. J. &#34;Solving Least Squares Problems&#34;, Prentice-Hall, (1974). Hence, in real time we need to take an FFT of the data and multiply by the matrix D to obtain the estimates of the transforms of the sample function at each source. An estimate of the power spectrum of each source is now obtained by squaring the magnitude of this frequency function and averaging over several sets of data observations as in the direct method of spectral estimation; see Oppenheim A. V. and Schafer R. W. &#34;Digital Signal Processing&#34;, Prentice-Hall 1975. 
     3. Alternative fast computation techniques 
     Another example of reducing computation by partitioning occurs when we perform detection of a single target in a background of noise using a large array. Only one source or reflector is considered inside the region at a time and all other sources or reflectors are considered to be adequately modeled as plane wave generators. In this case the matrices are reduced in dimension to include only the outermost segments and the selected segment. The matrix is much smaller but there is now a matrix for each new segment selected. 
     A fast solution technique is to store all the inverse matrices. The parameters associated with each specific segment are computed in turn by multiplication of the measurements with the specific inverse matrix. The results may be combined to generate a map as if all segment parameters had been computed simultaneously. The outermost segments, for which parameters are computed at each computation, are averaged to generate the composite plot. 
     A second method requires significantly less storage but is slower. The inverse part of the matrix concerned with the outermost (plane wave) sources is stored. The matrix inverse is updated, as part of the real time computation, to include the effects of the specific segment of interest. The results are combined as before for the purpose of post processing and display. 
     A residual value or error indicating a goodness of fit is obtained corresponding to each internal segment in a similar manner as described previously. The residual is the root mean square of the difference between the actual measurements and those estimated using the solutions for the segment sources or reflectors as described previously. In this case, the residual may be provided as a spatial map in both active and passive cases. The smallness of the residual value indicates the likelihood of a target at that position. A high residual everywhere may indicate the presence of more than one target in the interior region. In this case it may be desirable to partition differently, for example compute all segments in a specific range of times.