Monolithic Discrete-Time Digital Convolution Circuit

The present invention relates generally to circuitry for performing a convolution function, and, more particularly, to convolution circuitry employing digital samples of two input functions taken at discrete time intervals.

Convolution may be expressed as a mathematical relationship combining two time-varying functions. Convolution is used extensively in the signal processing and communications fields, for example in high-speed digital finite-impulse-response filters, and in pulse compression and detection techniques. For two continuous time-varying functions x(t) and c(t), the convolution of the two functions is given by the expression: ##EQU1## where the symbol .tau. represents an independent time variable.

This expression may have little more than an abstract meaning to those outside the communications field, and the physical meaning of convolution can be more readily understood by means of a graphical representation. For example, an explanation along these lines is provided in a book by B. P. Lathi, "Signals, Systems and Communication," published by John Wiley & Sons, Inc., 1965. Basically, if the two input functions are plotted graphically, convolution can be visualized by folding one of the functions about the zero-time axis, and then translating it along the time axis with respect to the corresponding plot of the other function. At each relative position of the two plotted functions, the value of the convolution function is proportional to the sum of the products of corresponding ordinates on the two curves. If one of the curves is of unit height, the graphical representation simplifies further to one of determining areas under the other curve as one curve is translated with respect to the other.

When the time-varying functions to be convolved are represented by samples taken at discrete time intervals, the corresponding expression for the convolution function is: ##EQU2##

Although many convolution circuits have been suggested in the past, no fully digital circuit has been successfully implemented in monolithic form. Design complexity is among the reasons usually given for lack of success in this area. The inherent advantages of integrated circuitry, including higher speed, lower power and potentially lower cost, have still not resulted in the production of any monolithic convolvers prior to this invention. Accordingly, there has been a definite need for monolithic convolver circuit that is well suited to modern integrated-circuit fabrication techniques utilizing very large scale integration (VLSI). The present invention satisfies this need.

The present invention resides in a monolithic discrete-time digital convolution circuit that makes extensive use of concurrent execution of multiplication and addition functions to minimize computation time, and extensive use of a single repeated stage to facilitate manufacture in monolithic form. In addition, the use of adders that produce partial sums at each stage further increases the speed of the circuit.

Basically, and in general terms, the circuit of the invention includes a plurality (N) of storage circuits for holding N respective values of a first function, a like plurality (N) of multipliers each connected to yield the product of a respective one of the values of the first function multiplied by one of a succession of values of a second function that is supplied to all of the multipliers. The circuit also includes a chain of N adders, each coupled to receive corresponding output products from the multipliers, and each combining a multiplier product with a cumulative sum from a prior adder in the chain, and passing the result to the next adder in the chain. Successive values of the convolution of the first and second functions are computed in a concurrent manner by the arrangement of multipliers and adders, and are provided as the convolved result in the last adder in the chain.

An important aspect of the adder chain is that each stage of it computes only a partial sum, i.e. a set of sum bits computed without regard to carry bits, and a full set of carry bits, the partial sum and carry bits being temporarily stored for propagation to the next stage of the adder chain. A full set of partial sum bits and a full set of carry bits are finally presented to a conditional sum adder, for computation of the final result as data leaves the adder chain.

In accordance with another aspect of the invention, the storage circuits for holding N respective values of the first function are loaded in parallel from a serially loadable buffer register. The buffer register can then be loaded with a new set of values of the first function as soon as a prior set has been moved in parallel to the storage circuits.

It will be appreciated from this brief summary that the invention represents a significant advance in the field of convolution circuits. In particular, it provides a hitherto unavailable monolithic circuit for performing the convolution function in discrete form. Other aspects and advantages of the invention will become apparent from the following more detailed description, taken in conjunction with the accompanying drawings.

FIG. 1 is a block diagram of a 16-stage convolver circuit in accordance with the present invention;

FIG. 2 is a diagrammatic plan view showing the layout of an integrated-circuit chip embodying the invention;

FIG. 3 is a logic diagram of the multiplier used repeatedly in the circuit of FIG. 1;

FIG. 4 is a table showing the hybrid encoding logic used in association with the multiplier logic of FIG. 3;

FIG. 5 is a block diagram showing the arrangement of adder modules used in the circuit of FIG. 1;

FIG. 6 is a logic diagram of an adder module used in each element of the diagram of FIG. 5; and

FIG. 7 is a detailed schematic of the adder module.

As shown in the drawings for purposes of illustration, the present invention is principally concerned with convolver circuits, which, in the past, have been unsuitable for implementation in monolothic form. In accordance with the present invention, extensive use is made of concurrent processing of information, sometimes referred to as "pipelining," and the circuitry provides for the use of repeated stages, which are more conveniently formed in the fabrication of a monolithic device. To maximize computation speed, summation is performed using an array of adders that produce partial sum bits together with a set of carry bits, the partial sum bits and the carry bits being summed only at the end of the computation, in a conditional sum adder.

More specifically, the illustrative embodiment of the invention comprises sixteen repeated stages referred to by reference numerals 10.0-10.15. The only additional components shown in FIG. 1 are the conditional sum adder 12 and three AND gates 14, 16 and 18. Each of the repeated stages 10 includes a flip-flop 20, a latch 22, a multiplier 24, an adder 26, and a shift register 28. All of these items are referred to in FIG. 1 using reference numeral suffixes 0.0 through 0.15, consistent with the reference numerals for the repeated stages 10. Each of the flip-flops 20 is three bits wide and is connected to the flip-flops in the next stage by lines shown at 30. The first flip-flop 20.0 is provided with three input bits on line 32, and the Q output of the last flip-flop 20.15 is connected to line 34, which is referred to by the signal name COUT.

Sixteen three-bit quantities are input to the flip-flops 20 over line 32, as directed by a clocking signal on line 36, and are shifted serially through the flip-flops until the sixteen values are appropriately stored in corresponding flip-flops. The output of each flip-flop 20 is also connected as an input to a corresponding latch 22, and the digits stored in the flip-flops are transferred to the latches 22 upon the occurrence of an appropriate clocking signal on a line 38. This line is designated by the signal name LOAD. The values stored in the latches 22 are sixteen samples of a function c(n), which is one of two functions of which the convolution is required. The other input signals x(n) are shown as being supplied over line 40, which is four bits in width and is shown as connected as an input to AND gate 18. The output of the AND gate 18, which is also four bits wide, is connected as one input to each one of the multipliers 24. A succession of values x(n) is supplied over line 40 and applied to the multipliers in synchronism with a clocking signal on line 42.

The other inputs to the multipliers 24 are the values from the respective latches 22, which are each three bits in width. The other input to AND gate 18 is from line 44, designated by the signal name ZEROX, the purpose of which is to apply zero values to the multipliers 24 for initialization purposes. The ZEROX signal on line 44 and the most significant bit of the x(n) value on line 40 are also applied as inputs to AND gate 16, a third input of which is supplied over line 46, designated TCM. The purpose of this line is to indicate to the convolver circuitry whether it should operate in accordance with a two's-complement mode or whether an unsigned integer mode of operation is required. For two's-complement operation, AND gate 16 generates a "one" bit of output to be applied as a control signal to each of the multipliers 24. Operation in this mode will be explained in more detail below.

The outputs of the multipliers are connected as inputs to the corresponding adders 26. In simple terms, each of the adders 26 combines a multiplier product with an accumulated sum and carry received from an adjacent adder. Thus, the sum generated by adder 26.1 is stored temporarily in shift register 28.1, and subsequently is transferred to the next adder in sequence 26.0. In adder 26.0 the accumulated sum is combined additively with the multiplier product from multiplier 24.0 and the accumulated carry from adder 26.1. The output of shift register 28.0 passes to the conditional sum adder 12, since the adders 26 and shift registers 28 do not produce a final sum, but rather produce a partial sum and a set of carry bits. The conditional sum adder 12 adds the partial sum bits and the carry bits to produce the final result on line 50, designated by the signal name YOUT.

To understand how the convolver circuit operates, coonsider again the expression for discrete convolution: ##EQU3## From this expression, y(0)=x(0).c(0)

y(1)=x(1).c(0)+x(0).c(1)

y(2)=x(2).c(0)+x(1).c(1)+x(0).c(2)

y(15)=x(15).c(0)+x(14).c(1)+ . . . +x(0).c(15)

In the first cycle of operation on the convolver circuit in FIG. 1, the expression for y(0) will be computed in multiplier 24.0 and adder 26.0, and subsequently shifted out of the shift register 28.0. All of the component products having x(0) as a multiplicand will also be computed in this cycle by the other multipliers 24. For example, x(0).c(1) will be computed in multiplier 24.1 and stored in shift register 28.1. On the next cycle, x(1).c(0) will be computed in multiplier 24.0 then will be added to the product x(0).c(1) in adder 26.0 and will subsequently be output to the conditional sum adder 12. Computation of y(15), the convolution value with the largest number of component products, is initiated in multiplier 24.15 and adder 26.15, where the product x(0).c(15) is first computed. Additional component products are added to the cumulative sum of y(15) as it progresses along the repeated stages of the adders 26 and shift registers 28. The final component x(15).c(0) is added in adder 26.0, just before the total is output to the conditional sum adder 12. Thus, it will be seen that computation of the convolution values results proceeds as nearly concurrently as possible.

FIGS. 3 and 4 illustrate how hybrid encoding of the value c(n) is used to achieve a fast multiplier operation in the multipliers 24. Each of the multipliers includes a first stage comprising five two-to-one multiplexers 60-64, a second stage comprising six exclusive OR gate 66-71, and a first stage comprising seven additional two-to-one multiplexers 74-80. The x(n) signal lines are indicated at 81-84, and each line is connected to two of the multiplexers 60-64, in the following manner. The least significant bit on line 81 is connected to the B input of multiplexers 64 and to the A input of multiplexers 63; line 82 is connected to the B input of multiplexer 63 and to the A input of multiplexes 62, line 83 is connected to the B input of multiplexer 62 and to the A input of multiplexer 61, and the most significant bit on line 84 is connected to the B input of multiplexer 61 and to the A input of multiplexes 60. The A input of multiplexer 64 is permanently supplied with a zero logic input level, as indicated at 86. The two's-complement mode bit on line 46, is connected as one input to an AND gate 88, which is logically equivalent to the AND gate 16 in FIG. 1. The other input to AND gate 88 is derived from the most significant bit line 84. The output of AND gate 88 is connected both to the B input of multiplexer 60 and to one input of exclusive OR gate 66 in the second stage of the multiplier.

The three c(n) input lines are indicated at 90, 91 and 92 in FIG. 3. Line 90 carries a signal designation CMX1, line 91 carries the signal designation CSINV, and line 92 carries the signal designation CZERO. The significance of these signal names will be explained in relation to FIG. 4. The CMX1 signal on line 90 is connected to the control signal input to each of the multiplexers 60-64. The CSINV line on 91 is connected as a second input to each of the exclusive OR gates 66-71 and as a B input to multiplexer 80 in the third stage of the multiplier. Finally, the CZERO line 92 is connected as a control input to each of the multiplexers 74-80 in the third stage. To complete the connections of the three stages, the outputs of multiplexers 60-64 in the first stage are connected as inputs to exclusive OR gates 67-71, respectively. The outputs of multiplexers 74-79 are, as will be explained, the multiplier result lines, the output from multiplexer 79 being the least significant bit and the output from multiplexer 74 the most significant bit.

Before turning to an explanation of the operation of the multiplier logic, the method of encoding the values of c(n) needs to be explained with reference to FIG. 4. In the exemplary convolver circuit disclosed in this application, the value of c(n) can take any of five states, including +2, +1, 0, -1, and -2. To improve the speed of multiplication, these are coded in the hybrid format indicated in FIG. 4. If the c value has a magnitude of 1, whether positive or negative, then the first signal CMX1 on line 90 is at a logical one level; otherwise it is at a logical zero level. If the c signal value is negative, the signal CSINV on line 91 has a logical value of one, and otherwise has a value of zero. Finally, if the c value is zero the signal CZERO on line 92 has a logical level of one; otherwise it has a logical zero level.

The purpose of the first level of the multiplier, controlled by the signal CMX1 on line 90, is to multiply the incoming x(n) signal by two if the corresponding c value is a 2, either positive or negative. The purpose of the second stage of the multiplier is to reverse the sign of the product developed by the multiplier. Finally, if the c value is zero, the entire product is replaced by zeros, as indicated by the zero signal level on line 94, which is connected to all of the A inputs of the multiplexers 74-80.

It will be seen from an examination of the first stage of the multiplier that if the CMX1 signal on line 90 is a one, indicating that the c value is +1 or -1, the B inputs of the multiplexers 60-64 are selected. Thus, the values on the x(n) input lines 81-84 are passed through to the outputs of multiplexers 64, 63, 62 and 61, respectively. On the other hand, if the value of CMX1 is a zero, indicating that the c value is +2 or -2, the x(n) values on lines 81-84 are passed through to the outputs of multiplexers 63, 62, 61 and 60, respectively. In addition, a zero is inserted after the least significant bit, in multiplexer 64. Thus, a left shift of one binary digit is accomplished, multiplying the x(n) value by two. In the second multiplier stage, the exclusive OR gates 66-71 accomplish inversion of the signal if the control signal on line 91 is a one. Finally, in the last multiplier stage, if a zero c(n) value is being processed the output signals are replaced by zeros in the multiplexers 74-80.

As mentioned earlier, the multiplier operates either in integer mode or in two's-complement mode. First, in integer mode the TCM signal on line 46 will be zero and the output of AND gate 88 will also be zero. Thus, the leading digit output from multiplexer 60 will be a zero if no doubling of the input signal was required, and will be equal in value to the most significant bit one line 84 if doubling was required. This leading digit will be transmitted through exclusive OR gate 67 and through multiplexer 75. The leading digits which may be derived from the TCM signal, will be inverted in exclusive OR gates 66 and 67 if sign reversal is called for.

In two's-complement mode, the most significant x(n) bit, on line 84, will be coupled through AND gate 88 and presented both to the B input of multiplexer 60 and as an input of exclusive OR gate 66. This most significant bit will be either a one or a zero, depending upon the sign of the two's-complement integer contained in the x(n) bits presented to the multiplier. In any event, the sign bit is appropriately generated at the most significant end of the product formed in the multiplier. The output 96 of the additional multiplexer 80 in the third stage of the multiplier is referred to as the "hot one" and is significant only if inversion of the product is called for in the second stage of the multiplier. If the CSINV signal on line 91 is a one, this one level is applied to the B input of multiplexer 80 and appears at the output on line 96 for non-zero values of c(n). Computing the reverse sign value of a number in two's-complement arithmetic involves inverting the value of each bit and then adding one bit to the least significant digit. This one bit is commonly known as the "hot one". It should logically be added to the least significant bit of the multiplier result presented from the output multiplexer 79. However, the addition is more conveniently and quickly performed in the adder logic to be described next It will be seen that a modular "slice" of the multiplier, indicated at 98, can be repeated throughout the multiplier, to facilitate fabrication in monolithic form.

Each adder 26 and shift register 28 comprises eleven one-bit adder modules as indicated by the boxes labeled A.sub.0 -A.sub.10 in the right-hand column of FIG. 5. For consistency with the other figures, this is referred to as the "15th" stage of the adder array. Similarly, each of the other fifteen stages of the convolver circuit has eleven one-bit adder modules. Also shown in FIG. 5 are the eleven adder modules for the 14th stage and eleven for the zero stage. Each one-bit adder module is as shown in FIG. 6, to be described, and includes an input line 100 for the "old sum" value, an input line 102 for the "old carry" value, and an input line 104 for one bit of a new value to be added to the old sum and carry. The adder module provides two outputs, a "new sum" output on line 106 and a "new carry" output on line 108.

In the 15th stage shown in FIG. 5, the "old sum" and "old carry" inputs are not fully utilized, since there will be no carries from a preceding stage. The "old sum" inputs to adder modules A.sub.0 through A.sub.7 are used to input an eight-bit y input value, which may be utilized when two or more convolver circuits are coupled together. The additional input lines 104 in adder modules A.sub.0 -A.sub.5 are used to input the result from the multiplier 24.15. The least significant bit of the multiplier product is input to adder module A.sub.0, the next most significant bit to adder module A.sub.1, and so forth. The "old carry" input bit of the A.sub.0 adder in each stage is used to input the "hot one" from the multiplier in each stage. The new sum output from adder A.sub.0 in the 15th stage is connected to the old sum input of adder module A.sub.0 in the 14th stage. Likewise, the new sum outputs from each of the other adder modules A.sub.1 -A.sub.10 is coupled to the old sum input of the correspondingly numbered adders in the next or 14th stage. The new carry output from adder module A.sub.0 in the 15th stage is coupled to the old carry input of A.sub.1 adder in the 14th stage, this being the next most significant bit. Likewise, the new carry signals from each of the adders A.sub.1 -A.sub.9 are coupled to the old carry inputs of adder modules A.sub.2 -A.sub.10, respectively, in the 14th stage. The same manner of connection is carried across all 16 stages of the adder array until the zero stage is reached. At this point, the shift registers of the adders A.sub.0 -A.sub.10 contain an eleven-bit accumulated partial sum and eleven bits of carry information.

It will be appreciated that the formation of partial sums in each of the 16 stages represents a considerable savings in time, but without any loss of information. All that remains to be done to produce the convolution function values for the result is to add the eleven-bits of partial sum information to the eleven bits of carry information. This is effected in the conditional sum adder 12. Conditional sum adders have been known for some years and the one used here will not be described in detail. It utilizes the algorithm first described in a paper entitled "Conditional-Sum Addition Logic" by J. Sklansky published in the IRE Transactions on Electronic Computers, June, 1960, page 226. Basically, the conditional sum adder computes all possible sum and carry digits in each column. The Sklansky method allows the computation from this information of all of the possible sums and carry digits for each pair of columns, then all of the sums and carry digits for each group of four columns, then each group of eight columns and so forth until the entire sum is a known to a certainty. The time required to perform this operation is several times less than the time to perform a conventional addition operation with ripple carry generation from column to column.

The adder module used in each of the elements in the adder array shown in FIG. 5 is basically as shown in FIG. 6. Each adder module includes two AND gates 110 and 112, two exclusive OR gates 114 and 116, one OR gate 118, and two flip-flops 120 and 122. The "old sum" signal on line 100 and the result from the corresponding multiplier on line 104 are exclusive OR'd in gate 114, then the result is exclusive OR'd in gate 116 with the "old carry" signal 102. The result on line 124 is input to flip-flop 122 as the new sum signal. The output of exclusive OR gate 114, on line 126, is provided at one input to AND gate 112, the other input being the old carry signal from line 102. The output from AND gate 112, on line 128, is provided as one input to OR gate 118. The old sum on line 100 and the multiplier result on line 104 are AND'ed together in AND gate 110, and the result is applied over line 130 as the other input to OR gate 118, the output of which is applied over line 132 to the other flip-flop 120 which holds the new carry signal.

As shown in FIG. 2, the convolver circuit of FIG. 1 can be conveniently laid out on a single monolithic chip. The y output buffers and the conditional sum adder are conveniently positioned at one end of the chip, together with c input and reference cells. At the other end of the chip the x and y and clock input cells are located, and the repeated stages are located in the remaining mid regions of the chip. It will be appreciated that the repeated stages could easily be expanded in number from 16 to 32 without affecting the design criteria of the chip.

The convolver circuit is implemented in the form of current-mode logic (CML) using an advanced one-micron bipolar technology and a triple diffusion process. Transistor geometries include metal widths of 4 microns and minimum metal spacings of 1.0 micron. Spacing between N+ emitter regions and P type base regions was maintained at 1.75 micron, with a typical breakdown voltage of 12.5 volts.

Power consumption for the 16-stage circuit is 750 milliwatts and the chip size is 245.times.133 mil. To minimize chip area, ringless or unguarded transistors are used instead of ringed transistors. Although the ringless transistors have characteristics that reduce operating logic margins, they represent an area saving of about 32 percent. The 16-stage convolver circuit performs 0.96.times.10.sup.9 operations per second, which corresponds to a functional throughput rate of 6.92.times.10.sup.11 gate-Hz/cm.sup.2.

The CML circuitry of a single adder cell is shown by way of example in FIG. 7. CML is used for all internal circuitry of the chip, with conversion being made to TTL-compatible logic in the input and output circuits.

It will be appreciated from the foregoing description that the present invention represents a significant advance in the field of convolver circuits. In particular, the invention provides a monolithic convolver circuit utilizing to the greatest extent possible concurrent processing of information and use of repeated stages for efficient chip layout. Although a particular form of the invention has been described in detail for purposes of illustration, it will be appreciated that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, the invention is not to be limited except as by the appended claims.