High Accuracy Digital Acousto-Optic Matrix Computer

The present invention relates to acousto-optic systems for performing basic operations of vector-matrix multiplication with digital (16-bit) accuracy. More specifically the present invention relates to an acousto-optic system comprised of two multi-transducer Bragg cells that can perform at least 10.sup.8 operation/sec of basic vector-matrix multiplication with digital (16-bit) accuracy and which is simple and compact.

Optical processors have the advantages of (a) inherent parallelism of data propagation; (b) ease of performing analog multiplication and additions, and (c) the use of a third spatial dimension to achieve global interconnections between different elements of an array. One generally useful class of operations which inherently require these three properties is that of matrix operations--e.g. vector-matrix and matrix-matrix multiplication. A review of different architectures for optical matrix processors can be found in the literature (R. A. Athale, "Optical Matrix Algebraic Processors: A Review," Proceedings of the 10th International Optical Computing Conference, p. 24, IEEE Catalog No. 83 CH 1880-4). Optical computing is however largely analog. Recently several papers presented ways to improve the accuracy by digital encoding of data--especially as configured for a matrix processor (R. A. Athale, W. C. Collins, P. D. Stilwell, Appl. Opt, Vol. 22, p. 368, 1983; P. S. Guilfoyle, Optical Eng., Vol. 23, p. 20, 1984). In addition to these architecture developments, recently the technology for manufacturing large bandwidth (.about.100 MHz), high performance, multichannel acousto-optic devices for rapid input of data into optical processors has matured considerably ("Acoustooptic Signal Processing Theory and Applications," N. J. Berg and J. N. Lee, eds. Marcel-Dekker Pub., New York, 1983). The wide variety of architectures that are possible with optical systems allow for the desired input/output interfacing to be achieved.

The basic operation chosen for the present optical system architecture is the multiplication of two vectors to produce a scalar (inner or dot product). The vector-matrix multiplication between an N element column vector and an MxN matrix can be accomplished in M steps as successive inner products between the input vector and columns of the matrix ##EQU1## A matrix-matrix multiplication can be accomplished in N.sup.2 steps by a straight forward extension. For higher accuracy the algorithm used will be digital multiplication by analog convolution first proposed by Whitehouse and Speiser (H. J. Whitehouse and J. M. Speiser in "Aspects of Signal Processing with Emphasis on Under Water Acoustics," Vol. 2, Reidel Pub., Boston, 1976, p. 669-702) and first demonstrated optically by D. Psaltis et al. (D. Psaltis, et al., proc. of SPIE, Vol. 232, p. 160-167, 1980). This principle was combined with the optical systolic architecture for vector-matrix multiplier (H. J. Caulfield, W. T. Rhode, M. J. Foster and S. Horvitz, "Optical Implementation of Systolic Array Processing,"Optics Communications, Vol. 40, No. 2, 15 December 1981, pp. 86-90. as well as optical engagement architecture in a paper by P. S. Guilfoyle referred to earlier. The proposed system in this paper has several drawbacks, however. It requires acousto-optical devices with two different materials. The acoustic velocity ratios are not easily adjustable, and therefore the accuracy of the system which is largely determined by those ratio's is difficult to adjust. The optical components required to image two Bragg cells, the commonly used acousto-optic device in the above-identified systems, on each other require a rather large anamorphism (.about.16) thus making it complicated. The output interface requires a linear array of N high speed detectors and each detector requires an analog/digital converter and a digital shift-and-add circuit to decode the output, making it very expensive. The output vector is calculated after (3N-1) steps of the processor.

Accordingly, one object of this invention is to provide a novel acousto-optical system that performs at least 10.sup.8 multiplications per second with 16-bit digital accuracy that is compact and simple.

Another object of the present invention is to provide a novel acousto-optical system that performs at least 10.sup.8 multiplications per second with 16-bit digital accuracy, that is compact and simple and that utilizes two acousto-optical cells of the same material for greater accuracy and easier adjustment.

Another object of the present invention is to provide a novel acousto-optical system that performs at least 10.sup.8 multiplications per second with 16-bit digital accuracy that is compact and simple and requires only simple optical components to image the two acousto-optical cells of the system on each other.

Another object of the present invention is to provide a novel acousto-optical system that performs at least 10.sup.8 multiplications per second with 16-bit digital accuracy that is compact and simple and that requires only one detector, one analog-digital converter and one digital shift and add circuit to decode the output.

Another object of the present invention is to provide a novel acousto-optical system that performs at least 10.sup.8 multiplications per second with 16-bit digital accuracy that is compact and simple and that has a time bandwidth product of (2B-1), where B is the number of bits required to represent the input vector and matrix elements.

Another object of the present invention is to provide a novel high-speed acousto-optical system that utilizes two multi-transducer Bragg cells imaged onto each other and in parallel so that data fed into the Bragg cells acts to modulate light passing therethrough.

These and other objects are realized by an apparatus for performing at least 10.sup.8 multiplications per second with 16-bit digital accuracy comprising: a first multichannel acousto-optic device which receives impulses representing a matrix (MxN) through its channels in a first acoustic propagation direction; means for generating light which illuminates the first acousto-optic device; a second multichannel acousto-optic device which receives impulses representing a vector (Nxl) through its channels in an acoustic propagation direction opposite to the first acoustic propagation direction; said second acousto-optic device being of the same type as the first acousto-optic device, the second acousto-optic device aligned parallel to and imaged at a 1:1 correspondence on the first acousto-optic device so that any light passing through the first acousto-optic device from the light means will strike the second acousto-optic device; an imaging optic means; a focusing lens; and a photo-detector.

Additional embodiments include an analog to digital converter that receives input from the photodetector, a shift register that receives input from the converter and an accumulator that receives input from the shift register.

A more complete appreciation of the invention and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein:

FIG. 1 is a schematic diagram of the high accuracy digital acousto-optics matrix computer.

FIG. 2 is a schematic diagram showing multiplication of two numbers by an acousto-optic convolver.

FIG. 3 is a schematic diagram of the data configuration shown at clock cycle 1 in an acousto-optic computer.

Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views, and more particularly to FIG. 1 thereof, a light source 10 illuminates the face of a multitransducer acousto-optic cell 12 (the number of transducers is determined by the number of elements of the vector and matrix, which must be identical, and the propagation length of the acousto-optic cell must be at least large enough to hold the longest binary word of an element in it along one column at a given moment). A second multitransducer acousto-optic cell 14 is alongside and parallel to cell 12. Acousto-optic cell 14 is identical to acousto-optic cell 12 except that the acoustic propagation direction is opposite resulting in an acoustic wave propagating in opposite directions in these two cells (counter propagation). These two cells are imaged on each other with a simple 1:1 imaging system 13 (no demagnification required) and aligned so the transducers of the two cells are aligned. The imaging system can simply be a lens. The light from the light source 10 that passes through the cell 12 is focused by a lens 16 onto a single high speed photodetector 18 after the light is modulated by cell 14 positioned one focal length away from the lens 16.

The acoustic cell 12 receives N elements of the input column vector in parallel through the N transducers 20. Each element is input in a bit-sequential fashion with a zero (gap) inserted between the bits. The second cell receives the N-elements of a row vector of A in parallel through the N transducers 22 with each element applied in a bit serial fashion as shown in FIG. 2. The second cell 14 receives all the rows of A in a sequential fashion, while the first cell 12 receives the same b vector (N x 1) data over and over. The data streams in the two cells are synchronized with respect to each other. The detector 18 output stream contains the elements of the output vector c (M.times.1) that are sequential with respect to bits as well as to index. Each channel in these cells is required to have a time bandwidth product of (2B-1), where B is the number of bits required to represent the input vector and matrix elements. (It does not matter whether the first cell or the second cell receives the vector or the matrix as long as it is consistent).

The detector 18 output stream is subsequently processed by an analog to digital convertor 24 and then by a shift register 26 and an accumulator/adder 28.

Briefly, when an element inputted through a transducer is nonzero (one) the localized area around an inputted pulse in the Bragg cell undergoes an index of refraction change allowing light from the laser to be deflected through the Bragg cell. If the second Bragg cell also has a nonzero pulse inputted at the respective corresponding parallel prints to the first Bragg cell, then light will also be deflected through the second Bragg cell. The photodetector 18 is disposed such that it will only receive the doubly deflected light (the undeflected light can be stopped by an absorbing baffle-not shown in FIG. 1). This simple optical system effectively performs a binary multiplication between different bits of a vector element and different bits of the corresponding matrix element in parallel. This procedure thus simulates actual vector multiplication, since there is a non zero product only when two vectors share at least one dimension corresponding non zero dimension that is the same. Additionally, in vector multiplication, the final product is determined by adding all the individual elemental products. Here all the individual elemental products of the same binary significance are calculated at the same time, according to the inputs of the various transducers in the 2 Bragg cells, so the intensity of the light reaching the photodetector has the information proportional to the mixed binary bit of the same significance of actual sum. Other mixed binary bits of the sum are subsequently calculated and stored. It should be remembered that the vector multiplication in the two Bragg cells is binary vector multiplication but the result collected by the photodetector is binary weighted. The part of the system in operation subsequent to the photodetector converts the binary weighted output to ordinary binary numbers.

The operation of the device will further be explained with the help of the following steps:

(i) Multiplication of binary numbers by analog convolution.

(ii) Addition of binary numbers without carry propagation.

(iii) Inner product of two binary encoded vectors via multiple simultaneous convolutions and summations without carries.

(iv) Vector-Matrix multiplication via several inner products.

This procedure can be explained with the help of an example. Two numbers to be multiplied are 6 and 3, which are represented by 3-bit binary numbers 110 and 011 respectively. The answer is 18 which can be represented as a 5-bit binary word 10010. Ordinarily the binary multiplication is carried out by forming partial products between the two numbers and then adding shifted partial products as illustrated below:

The similarity between this operation and a convolution operation suggests that this binary multiplication can be carried out by a convolution operation. The convolution of two sequences a2a1a0 and b2b (where the arrows point the direction the sequences are moving) is shown below: ##EQU2## resulting in c.sub.0 c.sub.1 c.sub.2 c .sub.3 c.sub.4

where

c.sub.0 =a.sub.0 b.sub.0

c.sub.1 =a.sub.0 b.sub.1 +a.sub.1 b.sub.0

c.sub.2 =a.sub.0 b.sub.2 +a.sub.1 b.sub.1 +a.sub.2 b.sub.0

c.sub.3 =a.sub.1 b.sub.2 +a.sub.2 b.sub.1

c.sub.4 =a.sub.2 b.sub.2

Now if we substitute a.sub.2 a.sub.1 a.sub.0 =110 and b.sub.2 b.sub.1 b.sub.0 =011, then c.sub.4 c.sub.3 c.sub.2 c.sub.0 =0 1 2 1 0. This represents the final answer in a mixed binary form from the photodector 18 in which the weights associated with each digit are still successive powers of two, but the bits themselves can be greater than 1. To convert the mixed binary number into conventional binary number, each digit is converted into a binary representation using an Analog-to-Digital(A/D) converter and the binary words of the mixed digits are added after being shifted with respect to each other. In the current example, each digit is represented by two bits. This operation is shown below:

The convolution operation can be implemented using two acousto-optic devices 12 and 14, one light source 10, an imaging system 13, a focusing lens 16 and a photodetector array 18 arranged as shown in FIG. 2. The detector is followed by an A/D converter 22, a shift register 24 and an accumulator 26 to convert the mixed binary digits resulting from the acousto-optic convolver. The two binary numbers are fed to the two acousto-optic cells synchronously but in the opposite direction. As the two binary sequences move past each other, the light deflected by both of them contain a multiplication between bits of the shifted sequences. The lens performs addition by collecting all the light on a detector. The mixed binary digits are thus generated serially (c.sub.0, c.sub.1, c.sub.2, etc...).

In conventional binary addition, summation of two bits of the same significance from different numbers to be added generate a sum bit of the same significance and a carry bit of higher significance. The carry bit is then inputted to the next significant bit addition. This is illustrated by addition of two numbers 3=011 and 2=010.

The carry bit can be avoided by using mixed binary representation. Now the addition of all bits can be carried out in parallel.

The answer can be converted to a conventional binary representation using a procedure similar to that described for binary multiplication by analog convolution.

The inner product (or dot product) of two three-element vectors a (a=a.sub.1 a.sub.2 a.sub.3) and b (b=b.sub.1 b is defined as c=a.multidot.b=a.sub.1 b.sub.1 +a.sub.2 b.sub.2 +a.sub.3 b.sub.3 and therefore involves summation of products of corresponding elements of the input vectors. If the vector elements are represented as binary words then each of these products can be performed via an acousto-optic convolver. The summation of the products can also be accomplished one mixed binary digit at a time (i.e. without carries) if these convolvers are synchronized such that the results of the multiplications are generated in a bit-synchronous fashion. FIG. 3 shows the expanded view of the two multi-channel acousto-optic cells (12 and 14 in FIG. 1) and the lens (16) along with the data streams. In this example each vector element is digitized to 3-bits.

Table I shows the contents of the three convolver channels and the detector output for first three clock cycles of the processor where the superscript indicates bit significance and subscript indicates vector index.

Similarly during clock cycles 4 and 5, c.sup.3 and c.sup.4 will be calculated, thus accomplishing 3-element vector inner product to 5-bit accuracy in 5-clock cycles.

The multiplication of an N-element vector by an M.times.N matrix A is defined below: ##EQU3##

It can be seen that element b.sub.1 of the output vector b is equal to the inner product of the first row of matrix A and the input vector b. Since this inner product can be performed with high accuracy via a multi-channel acousto-optic convolver shown in FIG. 1. The same system can perform the useful operation of vector-matrix multiplication as successive inner products of rows of matrix A and the input vector x without any physical modification of the system.

Obviously, numerous (additional) modifications and variations of the present invention are possible in light of the above teachings. It is therefore to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein.