US 4,041,297 AGrant
Real-Time Multiplier With Selectable Number of Product Digits
Issue Date:1977-08-09
•5 Claims
•5 Drawing Sheets
Abstract
A real-time multiplier capable of providing any desired number of the most significant product digits is described. The multiplier and multiplicand are provided concurrently to the multiplier as serial digital numbers. The least significant product digit is provided as the first digit of the serial digits of the product. Undesired less significant product digits are suppressed within the multiplier and do not appear as product digits, thereby allowing the successive operands to be provided to the multiplier without the waiting period between operands which would otherwise be required to allow all product digits to be read out of the multiplier from the previous multiplication. The number of stages in the multiplier is equal to the maximum number of digits in the operand.
Metadata
Inventor
- Harold V. Jesse
Application Information
Application Number:US 6141439
Filing Date:1975-09-17
Priority Date:1971-08-24
Art Unit:236
Classifications
IPC:
G06F 752
Field of Search:
235156;159;160;164
Patent Drawings (5 sheets)
Description
This invention relates to an apparatus and method for performing real-time multiplication of digital numbers and providing only the desired number of most significant digits in the product.
Real-time multiplication of digital numbers has been obtained previously as described in the U.S. Pat. No. 3,300,627 of Dean Arden. Real time means that the least significant output digit of the product is produced concurrently with the simultaneous input of the least significant digit of each of the operands. However, the circuit there described must provide as its output all the digits of the product. Since there will be twice as many digits in the product as in the multiplier or multiplicand, which are of equal length, a succession of multiplier (and concurrent multiplicand) digital numbers must be spaced from each other to allow the multiplier circuit to complete the multiplication process before a new multiplier is provided to the circuit. This waiting period slows down the rate at which multiplications may be performed to one-half the rate at which they could be performed if the circuitry could accept numbers for multiplication without requiring that they be spaced by a time equal to their own length.
It is, therefore, an object of this invention to provide multiplication in real time where the number of digits of the product may be less than twice the number of digits in the multiplier or multiplicand. The least significant digit provided by the multiplier is produced at the same time relative to the least significant digit of the operands as in the prior art real time multiplier. In particular, if the product digits desired are equal in number to that of the multiplier or multiplicand, the successive multipliers (and multiplicands) may be introduced into the multiplier adjacent to each other. If more significant product digits are desired, the multiplier (and multiplicand) numbers are spaced by a time corresponding to the number of extra product digits.
A feature of the apparatus employed in the preferred embodiment is that the circuit is iterative; that is, it is constructed by interconnecting a number of substantially identical modules so that a multiplier is obtained by merely using as many modules as the maximum number of digits, binary or any other base, in the operands.
Other and further objects will be explained hereinafter and will be more particularly pointed out in connection with the appended claims in conjunction with the figures:
FIG. 1 is a timing diagram of signals applied to the multiplier.
FIG. 2(a) shows the first two stages of a serially connected six-stage digital multiplier.
FIG. 2(b) shows the second two stages of a serially connected six-stage digital multiplier.
FIG. 2(c) shows the third two stages of a serially connected six-stage digital multiplier.
FIG. 3 shows two stages of a decimal multiplier.
The real-time multiplier of this invention concurrently accepts the serially provided digits in each of the numbers to be multiplied on two separate inputs. The n input digits of the operand are successively multiplied to yield, for example, the n most significant of the 2n product digits. The successive operands are processed one after the other without delay. The multiplier is formed by cascading substantially identical stages, one stage per operand digit.
Specifically, the stages are identical in blocks of two. The difference between the two stages in a block can readily be seen in FIGS. 2 and 3. These differences occur in the timing lines t.sub.a, t.sub.b, t.sub.c and t.sub.d, the input lines A, B, and the output line c.sup.0 carrying the output partial products from each of the summers.
The apparatus of the invention produces only the desired most significant digits of the product of the multiplier and multiplicand. For example, for two six digit binary numbers a.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 a.sub.5 and b.sub.0 b.sub.1 b.sub.2 b.sub.3 b.sub.4 b.sub.5, where a.sub.0 and b.sub.0 are the least significant numbers, the product is a twelve digit binary number c.sub.0 c.sub.1 - - - c.sub.5 c.sub.6 - - - c.sub.10 c.sub.11. The least significant product terms, which are not generated by the multiplier because they are suppressed within the multiplier without affecting the generation of desired product terms are
The most significant digits c.sub.6 - - - c.sub.11 appear at the output of the multiplier at a time which begins six time intervals (the time interval occupied by the undesired six product digits) from the least significant digit of the numbers being multiplied. Thus for the situation where successive operand sets are being supplied to the multiplier without interruption, the least significant digit of the product of the preceding operands would be produced as an output at the same time as the least significant digit of the next set of operands was being provided as an input. These most significant product digits are:
It is seen that the product terms a.sub.i b.sub.j of the least significant product digits c.sub.0, - - - 5 c.sub.5 have the property that their subscript sum i+j<m where m is the least significant desired digit of the product. It is also observed that conversely, the most significant product digits c.sub.6, - - - c.sub.11 have product terms a.sub.i b.sub.j such that i+j.gtoreq.m. Therefore, as in the preferred embodiment disclosed herein, a multiplier which suppresses the least significant products c.sub.0, - - - c.sub.m.sub.-1 will suppress all product terms a.sub.i b.sub.j where i+j<m. In general, for any base, it will be necessary to suppress those digit products which are part of the summation which produce the least significant digit terms of the final product. However, this must be done without interference in the formation of the terms a.sub.i b.sub.j where i+j.gtoreq.m. Note that 0<m.ltoreq. 2n-1 where n is the maximum number of digits in the multiplicand (a.sub.0 - - - a.sub.n.sub.-1) and is not constrained to m=n-1.
A preferred embodiment of the invention for performing binary multiplication is shown in FIGS. 2(a), (b) and (c). Each figure contains two stages of the multiplier, each of which is essentially identical. The two stages of each figure constitute an iterative circuit which is cascaded to form a multiplier having as many stages as there are digits in each operand. The diagram of FIG. 1 shows the timing of the operand signals and the control pulses applied to the multiplier for the situation where the operands are considered to have six digits and where the product produced by the multiplier also has six digits.
Timing
For the purpose of illustrating the invention, the multiplier and multiplicand are each six binary digit words a.sub.0 a.sub.1 - - - a.sub.5, b.sub.0 b.sub.1 - - - b.sub.5, respectively. The time intervals during which these digits occur are t.sub.0 t.sub.1 - - - t.sub.5. A pulse on line t.sub.a from pulse generator 10 causes the line to become "high" occurs during the time interval t.sub.0. This pulse travels down line t.sub.a where it becomes available to the multiplier stages 0 through 5 at a time determined by the number of time delay elements 11, each of which delays the pulse by T units of time. The time duration of each pulse interval is also T.
At and during time interval t.sub.5 pulse generator 12 causes the usually "high" level on line t.sub.b to become "low". This pulse also travels down line t.sub.b to multiplier stages 0 through 5 and is delayed by delay elements 11 so that it is applied to multiplier stages 0 through 5 at times determined by the number of delay elements 11 between pulse generator 12 and a particular stage.
The voltage level on line t.sub.d is normally in the low state and is caused to become high by a pulse from pulse generator 13. This pulse is a double length pulse in that it has a duration of two time intervals, i.e., 2T. For an even-number of stages, as in the embodiment herein presented, the line t.sub.d is severed before stage (n/2), stage "3" of FIG. 2(b), where "n" is the number of stages, in this case six (n=6). Note that the stages are numbered through n-1. Also the double-length pulse is caused to occur when the digit a.sub.(n/2) (a.sub.3), [also b.sub.(n/2), (b.sub.3)] arrives to be stored in stage n/2 (stage 3), i.e., when it arrives at point A.sub.3 [B.sub.3 ]. Therefore, for the case of six stages, the pulse from pulse generator 13 occurs during time intervals t.sub.4, t.sub.5 and pulse generator 13 is connected at terminal 14 and line t.sub.d is severed, as represented by the "X" at point 15 between stages 3 and 4.
For an odd number of stages the line t.sub.d is cut at stage (n-1)/2, and the pulse from generator 13 begins at the time interval when digit a.sub.(n.sub.+1)/2 arrives to be stored in stage (n+1)/2. For example, for the case where n=5, the cut at point 15' is made between stages 2 and 3, the pulse from generator 13 will begin at time t.sub.4, and generator 13 is connected to line t.sub.d at point 14'. (Of course, the last stage 5 would not be needed in this case.)
In the particular case where the product has the same number of digits as each of the operands the line t.sub.d is cut between the first and second stages (between points T.sub.d.sup.0 and T.sub.d.sup.1 in FIG. 2(a)). This cut, represented by the "X" at point 9, prevents the formation of undesired terms a.sub.o b.sub.r and b.sub.o a.sub.r, where 0<r<m-1 which would not otherwise be properly inhibited by the pulse on line t.sub.d.
The pulse signals which occur on line t.sub.c result from its connection through OR circuits 16 to line t.sub.d. The pulses on lines t.sub.d and t.sub.c reach a particular stage through OR circuit 17 or through the connection to line t.sub.c as at T.sub.c.sup.2 and T.sub.c.sup.4.
The operand signals and control signals existing in each stage of the multiplier for several cycles of operation are shown in the following Tables O-V, each table corresponding to a stage 0-5 of FIGS. 2(a), (b) and (c). These tables completely describe for each interval of time the input signals, the output signals and the signals contained within the multiplier. Starting at time t=t.sub.o, it is possible to refer to the table for each stage and determine the signals contained therein at any time interval.
The multiplier and multiplicand each have six binary digits which occur during six intervals of time, i.e., during t.sub.0, t.sub.1 , - - - t.sub.5. This constitutes a cycle. The cycle is repeated every six intervals of time, t.sub.6 - - - t.sub.11, t.sub.12 - - - t.sub.17, etc. during which intervals new operands are provided as inputs. The operands of one cycle have their product occur during the next cycle at the output c.sup.0 of stage 0 for the case being considered where n(n = 6) significant product digits are desired. The control signals which are provided as gating signals are represented as a "1" to indicate a "high" state, a "0" 0 indicating a "low" state. The AND gates of FIG. 2 are considered to pass a signal "a" or "b" applied to one input when its other input is also high.
Although it is believed that the operation of the multiplier of FIG. 2 is apparent from a consideration of Tables 0-5 in conjunction with FIG. 2, a brief description of the operation of the multiplier is presented to assist in an understanding of the invention.
It is assumed that prior to time t.sub.0 the multiplier circuit of FIG. 2 has not been provided with operand signals for a time sufficient to have cleared all operand binary digits from the multiplier circitry. In other words, no multiplication has occured in the previous cycle because of the absence of operands, hence the multiplier is clear of stored digits. As will be seen, this assumption is made only to simplify the presentation of the manner of operation of the multiplier and that multiplication is not affected by the simultaneous presence in the multiplier of digits from successive operands as represented by t.sub.6 to t.sub.11, and t.sub.12 to t.sub.19, etc.
At time t.sub.0, the least significant binary digits a.sub.0, b.sub.o of the operands are applied on lines A and B, respectively. As seen by examination of FIG. 1, pulse generators 10, 12 provide a high level output at time t.sub.0 and pulse generator 13 provides a low level output. Reference to the Table for Stage 0, discloses that these inputs result in A.sup.0 = a.sub.0, B.sup.0 = b.sub.0, T.sub.a.sup.0 =1, T.sub.b.sup.0 =1, T.sub.c.sup.0 =0, T.sub.d.sup.0 =0 where the superscript 0 of the letter T refers to the terminals at stage 0 and the subscripts refer to the lines on which the terminals are located. For these signal inputs to stage 0,"and" gates 1.sup.0, 2.sup.0 are provided with time coincident pulses a.sub.0 and T.sub.a.sup.0, b.sub.0 and T.sub.a.sup.0, respectively, to provide at their outputs E.sub.1.sup.0, E.sub.2.sup.0 the signals a.sub.0 and b.sub.0, respectively. This signal condition at t=t.sub.0 is presented in the table for stage 0 as E.sub.1.sup.0 =a.sub.0 and E.sub.2.sup.0 =b.sub.0. Signal E.sub.1.sup.0 is provided as an input to OR gate 3.sup.0 which is an entrance point to recirculating loop 4. Since E.sub.1.sup.0 =a.sub.0 at t=t.sub.0, and is zero at all other times during the cycle, a.sub.0 will be introduced into the loop at t=t.sub.0 and continue to recirculate until interrupted by a low-level input from T.sub.b.sup.0 at time t.sub.5 applied to AND gate 26.sup.0. Thus signal E.sub.3.sup.0 is zero at time t.sub.5 and also at t.sub.0 since time delay element 5.sup.0 of loop 4.sup.0 introduces a delay of one pulse duration T. Signal E.sub.4.sup.0 in loop 6.sup.0 is obtained in the same manner except that its source is E.sub.2.sup. 0 =b.sub.0 and therefore it stores the signal b.sub.0 during times t.sub.1 - - - t.sub.4, wherein E.sub.4.sup.0 =b.sub.0 during time intervals t.sub.1 - - - t.sub.4. Signals E.sub.1.sup.0 and E.sub.2.sup.0 also are presented as inputs to AND gate 7.sup.0 whose output is a.sub.0 b.sub.0 at time t.sub.0 and zero at all other times since E.sub.1.sup.0 and E.sub.2.sup.0 are then zero. The output a.sub.0 b.sub.0 is presented as an input to AND gate 8.sup.0 whose other input is signal E.sub.0.sup.0 obtained from OR gate 16.sup.0 whose inputs are T.sub.c.sup.0 and T.sub.d.sup.0. Since line t.sub.d is severed at point 9 in this embodiment, where the number of digits in the product is equal to that in each of the operands, there are never any signals applied to lines t.sub.c and t.sub.d at points T.sub.c.sup.0 and T.sub.d.sup.0. Therefore all AND gates to which E.sub.0.sup.0 is applied as one input produce a zero output regardless of its other input.
Therefore, AND gates 18.sup.0, 19.sup.0 to which a.sub.0 b.sub.0 are applied, respectively, produce zero outputs to AND gates 20.sup.0, 21.sup.0. Then the only possible input to summing circuit 22.sup.0 is the signal E.sub.11.sup.0, which is the signal C.sup.1, received from the summer 22.sup.1 of Stage 1 after it has been delayed by delay unit 23.sup.0.
The delay units 24.sup.0, 25.sup.0 are connected to the carry outputs of the summing circuit 21.sup.0 during the time the subsequent digits are applied to the summing circuit. The more significant carry digit has been delayed by two units of time, 2T, by delay elements 25.sup.0 while the less significant carry digit has been delayed by one unit of time, T, by delay element 24.sup.0. The necessity for providing carry digits is well understood by those skilled in the art. For example, reference may be made to page 209 of the book, Arithmetic Operation in Digital Computers, R. K. Richards, Von Nostrand Co., 1955, for a description of a multiple-input adder suitable for use in this invention.
No other stage of the remaining stages has any operand signal contained within it since they were assumed to be clear at time t = t.sub.0 and therefore these stages may be disregarded at time t = t.sub.0.
Time t = t.sub.1
At time t = t.sub.1 stages 0 and 1 have operand signals a.sub.1, b.sub.1 at points A.sup.0, A.sup.1, and B.sup.0, B.sup.1, respectively. The pulse on line t.sub.a has progressed to point T.sub.a.sup.1 so that AND gates 1.sup.1, 2.sup.1 of stage 1 is gated "on" to store a.sub.1, b.sub.1 in loops 4.sup.1 and 6.sup.1, respectively, as signals E.sub.3.sup.1, E.sub.4.sup.1. Although lines t.sub.c and t.sub.d are connected to stage 1 through gate 17.sup.1, the gate 17.sup.1 output E.sub.0.sup.1 is low since a pulse is not produced by pulse generator 13 until time t=t.sub.4. Therefore, at t=t.sub.1, stage 1 merely stores a.sub.1 and b.sub.1 in loops 4.sup.1, 6.sup.1, respectively.
Stage 0 is unaffected at t=t.sub.1 by gates 1.sup.0 and 2.sup.0 since T.sub.a.sup.0 is low when A.sup.0 =a.sub.1, B.sup.0 =b.sub.1. This condition exists for all other values of a and b in the cycle so that signals a.sub.0, b.sub.0 stored in loops 4.sup.0, 6.sup.0 remain unaffected by subsequent signals on lines A and B until the next T.sub.a.sup.0 pulse at time t=t.sub.6 (which corresponds to t=t.sub.0 of the next cycle) concurrent with the new a.sub.0, b.sub.0, of the next operands supplied at that time.
Time t=t.sub.2
At time t=t.sub.2, the pulse on line t.sub.a has advanced to point 27 and has not yet reached point T.sub.a.sup.2 so that no operand digit is supplied to stage 2 through gates 1.sup.2, 2.sup.2. Stages 0 and 1 are also not producing any outputs at c.sup.0 and c.sup.1 since E.sub.0.sup.0 and E.sub.0.sup.1 are still at a low level.
Time t=t.sub.3
At time t=t.sub.3, the pulse on line t.sub.a has reached point T.sub.a.sup.2, so that the operand signals a.sub.2, b.sub.2 then appearing at points A.sup.2, B.sup.2 respectively are stored in Stage 2 through gates 1.sup.2, 2.sup.2. Pulse generator 13 has not yet produced a pulse so that stages 2, 1, and 0 are producing no outputs.
Time t=t.sub.4
At time t=t.sub.4, the pulse on line t.sub.a has reached points T.sub.a.sup.3, T.sub.b.sup.3 and operand signals a.sub.3, b.sub.3 have reached A.sup.3, B.sup.3, respectively, so that they are stored in stage 3 through gates 1.sup.3, 2.sup.3. It is at time t=t.sub.4 that pulse generator 13 produces a pulse which is two units, 2T, of time in length. This causes E.sub.0.sup.3 to be high thus activating AND gates 8.sup.3, 18.sup.3 and 19.sup.3. The product term a.sub.3 b.sub.3 produced in AND gate 7.sup.3 is passed through gate 8.sup.3 as the only input to summer 22.sup.3. The output of summer 22.sup.3 is therefore c.sup.3 =a.sub.3 b.sub.3. All other inputs to summer 22.sup.3 are zero because there are no carries in delay units 24.sup.3 or 25.sup.3, there is no signal c.sup.4 yet occurring and the signals E.sub.g.sup. 3, E.sub.10.sup.3 are zero since E.sub.3.sup.3, E.sub.4.sup.3 are zero in loops 4.sup.3, 6.sup.3 at time t=t.sub.4 (but will be a.sub.3,b.sub.3 respectively at t=t.sub.5).
Time t=t.sub.5
At time t=t.sub.5, the pulse on line t.sub.a has not reached T.sub.a.sup.4 of stage 4 because of delay unit 11.sup.3 on line t.sub.a on line so that nothing is stored in stage 4 and c.sup.4 =0.
In stage 3, the double length pulse at T.sub.d.sup.3 is applied through gate 17.sup.3 to gates 8.sup.3, 18.sup.3 and 19.sup.3 to produce signals E.sub.8.sup.3 =0, E.sub.6.sup.3 =a.sub.4 and E.sub.5.sup.3 =b.sub.4. Signal E.sub.8.sup.3 =0 since E.sup.3.sub.1 and E.sub.2.sup.3 are both zero. E.sub.6.sup.3 =a.sub.4 is applied as one input to gate 20.sup.3 whose other input is the stored signal E.sub.4.sup.3 =b.sub.3 thereby producing E.sub.9.sup.3 =a.sub.4 b.sub.3. Similarly gate 21.sup.3 produces E.sub.10 =a.sub.3 b.sub.4. The output of summer 22.sup.3 is then c.sup.3 =a.sub.3 b.sub.4 +a.sub.4 b.sub.3 since there are no other inputs to summer 22.sup.3. The pulse from generator 13 which begins at t=t.sub.4 has passed through delay element 27.sup.3 at t=t.sub.5. This pulse passes through "or" gate 16.sup.2 to produce a "high" output from gate 16.sup.2 (E.sub.0.sup.2 =1). This condition, E.sub.0.sup.2 =1, applied to gates 8.sup.2, 18.sup.2 and 19.sup.2 produces signals E.sub.8.sup.2 =0, E.sub.6.sup.2 =a.sub.3 and E.sub.5.sup.2 =b.sub.3. Signal E.sub.8.sup.2 =0, since E.sub.1.sup.2 and E.sub.2.sup.2 are both zero. E.sub.6.sup.2 =a.sub.4 is applied as one input to gate 20.sup.2 whose other input is E.sub.4.sup.2 =b.sub.2, thereby producing E.sub.9.sup.2 =a.sub.4 b.sub.2. Similarly gate 21.sup.2 produces E.sub.10.sup.2 =a.sub.2 b.sub.4. The remaining input E.sub.11.sup.2 to summer 22.sup.2 is E.sub.11.sup.2 = a.sub.3 b.sub.3, which was originally produced in stage 3 at time t=t.sub.4 but delayed in delay unit 23.sup.2 until t=t.sub.4.
The output c.sup.2 from stage 2 at t=t.sub.4 is therefore a.sub.3 b.sub.3 + a.sub.4 b.sub.2 + a.sub.2 b.sub.4 which is applied as input E.sub.11.sup.1 of stage 1.
At time t=t.sub.5, stage 1 has the first portion of the double length pulse from generator 13 applied through "or" gate 17.sup.1 to provide E.sub.0.sup.1 =1 as an input to gates 8.sup.1, 18.sup.1 and 19.sup.1. The E.sub.8.sup.1 output of gate 18.sup.1 is zero since E.sub.1.sup.1 and E.sub.2.sup.1 are zero because of the T.sub.a.sup.1 =0 input to gates 1.sup.1, 2.sup.1. The E.sub.5.sup.1 output of gate 19.sup.1 is b.sub.5 since b.sub.5 is the value at B.sub.1. Similarly the output of gate 18' is E.sub.6.sup.1 =a.sub.5 since A.sub.1 =a.sub.5 with E.sub.0.sup.1 =1. E.sub.5.sup.1 and E.sub.6.sup.1 are applied as inputs to gates 21.sup.1, 20.sup.1, respectively, where they are gated with E.sub.3.sup.1 =a.sub.1, E.sub.4.sup.1 =b.sub.1, respectively, to produce E.sub.10.sup.1 =a.sub.1 b.sub.5 and E.sub.9.sup.1 =a.sub.5 b.sub.1. Therefore the inputs to summer 21.sup.1 are E.sub.8.sup.1 =0 (E.sub.8.sup.1 =0 because E.sub.1.sup.1 =0 and E.sub.2.sup.1 =0), E.sub.9.sup.1 =a.sub.5 b.sub.1, E.sub.10.sup.1 =a.sub.1 b.sub.5, E.sub.11.sup.1 =a.sub.4 b.sub.2 +b.sub.4 a.sub.2 +a.sub.3 b.sub.3. The output c.sup.1 of summer 22.sup.1 is thus a.sub.1 b.sub.5 +a.sub.5 b.sub.1 +a.sub.2 b.sub.4 +a.sub.4 b.sub.4 +a.sub.3 b.sub.3. References to the table associated with stage 1 at time t=t.sub.4 expresses this output in a shorthand notation 1-5, 2-4, 3--3 where 1-5 means a.sub.1 b.sub.5 +a.sub.5 b.sub.1, 2-4 means a.sub.2 b.sub.4 +a.sub.4 b.sub.2 and 3--3 means a.sub.3 b.sub.3. This same shorthand notation is used throughout the tables for all stages.
At time t=t.sub.5, stage 0 has a zero output c.sup.0 =0 because the inputs to summer 22.sup.0 are all zero. The a.sub.0 value for E.sub.3.sup.0 is erased from loop 4.sup.0 by the occurrence of a "low" level at gate 26.sup.0 from line t.sub.b at point T.sub.b.sup.0. Similarly, E.sub.4.sup.0 =0 instead of b.sub.0. Therefore, E.sub.9.sup.0 and E.sub.10.sup.0 are zero. E.sub.8.sup.0 =0, E.sub.5.sup.0 =0 and E.sub.6.sup.0 =0 since line t.sub.d is cut after stage 0 at point 9 thereby preventing E.sub.0.sup.0 from ever becoming high and activating gates 8.sup.0, 18.sup.0 and 19.sup.0. Input E.sub.11.sup.0 of summing circuit 22.sup.0 is zero since the value of c.sup.1 at time t.sub.4 was zero, and E.sub.11.sup.0 is c.sup.1 delayed one digit time interval T by delay unit 23.sup.0.
Time t.sub.0 =t.sub.6
At this time the first digits a.sub.0, b.sub.0 of the next succeeding operands to be multiplied are provided to the input terminals of lines A and B along with a "high" pulse on line T.sub.a. All functions of the components of the stages have been explained at length previously and it is believed that further recitation of the details of which pulses occur on what stages would not serve to further elucidate the invention. Reference to the tables associated with each stage will provide the signal conditions which exist at each stage at time t=t.sub.6. Of interest is the observation that at this time interval not only is the first digit of each new number to be multiplied being provided as an input but also c.sup.6 =a.sub.3 b.sub.3 +a.sub.2 b.sub.4 +a.sub.4 b.sub.2 +a.sub.1 b.sub.5 +a.sub.5 b.sub.1, the least significant digit of those digits desired, is being provided by stage 0 as the first digit of the product.
With the input of the second operand digits, it is to be noted that the multiplier is not assumed cleared. Hence, the state tables indicate the state of the multiplier and its operation upon both the preceeding operand digits and the currently inputted digits.
Times t=t.sub.7 through t=t.sub.11
During these time intervals the other digits C.sub.7-C.sub.11 of the products are being provided by the output of stage 0. For each time interval the signal conditions for each stage may be obtained by referring to the table for that stage. During these time intervals some of the stages, for example, stage 0 at t=t.sub.11, will produce a digit solely due to the final carry.
The invention has been described as one where the number of stages is equal to the number of digits in the multiplicand, multiplier and product. As described thus for this embodiment makes no provision for including carries from less significant digits into the least significant product digit. Hence, if greater accuracy is desired, more of the less significant product digits can be formed and then truncation or round-off performed. This would require a zero binary digit between operands for each such additional product digit. The number of stages in the multiplier circuit would remain unaltered with only a slight modification in lines t.sub.c and t.sub.d.
More specifically, if the least significant product digit desired is c.sub.k, where k is less than n--1, where n is the number of operand digits, the cut 9 of lines t.sub.c and t.sub.d at stage 0 is eliminated. The connection point 14 on line t.sub.d and the time of occurrence of the pulse from pulse generator 13 is determined as follows:
If a.sub.i, b.sub.j are the binary digits of the operands stored in a particular stage and when i+j=k for i=j, then the cut 15 of line t.sub.d is between stage k/2 and (k/2)+1 and the pulse from generator 13 occurs when a.sub.i =a.sub.(k/2) arrives to be stored in stage k/2.
If i+j=k and i.noteq.j, then the cut 15 of line t.sub.d is between stages (k-1)/2 and (k+1)/2 and the pulse from generator 13 occurs at a time when signal a.sub.(k.sub.+1)/2 arrives to be stored in stage (k+1)/2.
For stages after the cut 15, no inhibition occurs because the line t.sub.c will have a high level at all times that operand signals are present in these stages. The cut 15 on line t.sub.d was made for aesthetic reasons since it is seen that the line t.sub.d may remain connected to generator 13 without affecting the operation of stages after the cut 15. An alternative arrangement would be to eliminate "and" gates 8, 18 and 19 from these stages together with lines t.sub.c, t.sub.d and their associated "or" gates 16, 17. If k is greater than m-1, the above algorithm of cut 15, insertion of pulse generator 13 and the time of occurrences of the pulse on line t.sub.d remains unchanged. However, no blanks (or 0's) need be inserted between operand sets.
While the invention has been described in the form of an embodiment of a binary digit multiplier, decimal and other bases of multiplication may also be employed. A decimal system embodying the principles underlying the invention is shown in FIG. 3. Comparison of FIG. 3 with FIG. 2 discloses that the general arrangement is the same in the two figures particularly with respect to the lines containing delay elements T and their associated signal and pulse sources which are numbered accordingly the same in both figures. The binary summer 22 of FIG. 2 is replaced by the decimal summer 121 of FIG. 3. The function of decimal summer 121 is to sum its decimal inputs to provide a decimal output and a carry in delay loop 123. The carry is applied as an input to summer 121 during the next succeeding decimal digit interval. The inputs to summer 121 are the decimal equivalents of the inputs to the binary summer 22. Each stage has storage loops 124, 120 where a decimal digit a.sub.m, b.sub.m, 0.ltoreq.m.ltoreq.n-1 is stored, respectively. The digit a.sub.m is introduced into loop 124 through gate 101 which is gated "on" by the pulse on line t.sub.a. The stored digit a.sub.m in loop 124 is removed by the pulse on line t.sub.b becoming low on gate 116. This timing of the pulse on line t.sub.b has been explained in connection with FIG. 2. Gate 101 also provides a signal b.sub.m to gate 105. The pulses from line t.sub.c determine whether b.sub.m will pass through gate 105 in order to be multiplied by decimal multiplier 103 in the same manner as AND gates 7 and 8 function in FIG. 2. Gates 107, 108 provide other "A" and "b" decimal digits to decimal multiplier 119, 120 in the same manner as gates 18, 19 provided signals to gates 20, 21 in FIG. 2. The delay unit 122 serves the same function as delay unit 23 of FIG. 2 in delaying the output digit of a preceeding summer.
In the decimal multiplier two outputs are obtained when the product equals ten or greater. The "unit" term is designated by the letter "u" at the multiplier output and this output is provided without delay as an input to summer 121. The other multiplier output is the "tens" term, designated by the letter "t", which must be delayed by one signal digit time interval in order to cause it to be summed to form the next most significant digit. This delay is produced by delay units 104. Delay units equivalent to units 104 are not to be found in FIG. 2 since the "and" circuits used for binary multiplication of two binary inputs do not produce a carries.
While there has been described in the preceding specification a preferred embodiment of the invention, further modifications will also occur to those skilled in the art and all are considered to fall within the spirit and scope of the invention as defined in the appended claims.
Claims
What is claimed is:
1. A real time multiplier for multiplying digital serial operand electrical signals representing a multiplicand, a.sub.o a.sub.1 - - - a.sub.n.sub.-1 and a multiplier b.sub.0 b.sub.1 - - - b.sub.n.sub.-1 to provide a product c.sub.k c.sub.k.sub.+1 - - - c.sub.2n.sub.-1, where 0.ltoreq.k.ltoreq.2n-1 comprising a plurality of serially connected multiplier stages, a first, second, third, fourth, fifth and sixth electrically conducting lines, means for simultaneously applying each of the multiplicand and multiplier signals serially at a fixed rate in time coincidence to the input terminals of said first and second lines, respectively, with the signals corresponding to the least significant digit a.sub.0, b.sub.0, being applied first, a plurality of delay elements each having a delay of one digit-time-duration, said first and second lines being connected to corresponding inputs of each multiplier stage, said first and second lines having a delay element in each line between alternate mutiplier stages, the first delay element being in said first and second lines between the connections to the inputs of the second multiplier stage "1 " and the third multiplier stage "2", means for applying a first gating pulse to the input terminal of the third line t.sub.a connected to one input of each multiplier stage, said third line t.sub.a having a delay element between corresponding inputs of each multiplier stage and an additional delay element in line t.sub.a between the multiplier stages having said delay elements in said first and second lines, said first gating pulse being in time coincidence with the least significant digits a.sub.0, b.sub.0 of the operands at the input to said multiplier, means for applying a second gating pulse to the input terminal of a fourth line t.sub.b connected as a second input to each multiplier stage, said fourth line t.sub.b having a delay element between corresponding inputs of each multiplier stage and an additional delay element in line t.sub.b between the multiplier stages having said delay element in said first and second lines, said second gating pulse being applied to the input of the first multiplier stage at the same time as the most significant operand digits a.sub.n.sub.-1, b.sub.n.sub.-1 are applied on their respective signal lines to the input of the first multiplier stage, means for applying a third gating pulse to a fifth line t.sub.d, a plurality of two-input OR gates, the output of each OR gate being connected as an input to each of said multiplier stages, the input of each OR gate being connected to said fifth line at locations such that said third gating pulse on said fifth line is applied as an input to the OR gate connected to the input of stage n/2 at a time when operand signal a.sub.n/2 arrives to be stored in stage n/2 for n even, (or stage (n+1)/2 and at a time when operand signal a.sub.(n.sub.+1)/2 arrives to be stored in stage (n+1)/2 for n odd,) said fifth line t.sub.d containing a means for delay of one pulse interval between the first and second stages and alternate stages following the second stage, the OR gate whose output is connected to the input of the first multiplier stage "0" also being connected to the input of the sixth line, the sixth line being connected as an input to each OR gate connected to the remaining multiplier stages, said sixth line containing a delay element of unit-pulse-length delay after the second multiplier stage "1" and the following alternate multiplier stages, said third gating pulse being of time duration equal to that of two signal digits, means for effecting the storage of each successive digit of the multiplier and multiplicand in each successive serially-connected multiplier stage in response to the first gating pulse on said third line t.sub.a and the multiplicand and multiplier on said first and second lines, respectively, means for effecting the removal by gating from storage of said stored digit in each stage in response to the second gating pulse on line t.sub.b means for summing and providing a carry in the summing means of each stage of those product terms a.sub.i b.sub.j where i+j=r and where k.ltoreq.r.ltoreq.2n-1, r=2n-1 for the first multiplier stage and increasing by one for each stage until r=k for the last stage, said product terms being provided to the input of said summing means from said storage means and the delayed output of the summing means of the next successive stage, means for delaying the summed product terms, a.sub.c.sup.0 j of the output of a summing means of each stage by a delay element between the output of the summing means of a stage and an input of the summing means of a preceding stage, the first multiplier stage producing at its output c.degree. the product terms c.sub.k, c.sub.k.sub.+1,---c.sub.2n.sub.-1 in serial time sequence.
2. A circuit for use in a real time multiplier circuit comprising: a first and second multiplier stage, a first and second AND gate, a first pulse line t.sub.a connected to each multiplier stage through a first input of said first AND gate (1) and a first input of said second AND gate (2); a second pulse line t.sub.b connected to each stage through an input of third (26.sup.0) and fourth (26') AND gates; said first and second pulse lines having delay elements (11') between their connections to said first and second stages, said delay element providing a unit of delay equal to the time duration of a digit of the operand; said first and second pulse lines having two delay elements 11' between said second stage connections and their output terminals which provide two units of delay; a first A and second B signal line, each connected through a second input of said first (1) and second (2) AND gates, respectively, to each stage, and each line having a delay element (11') between its connection to said second stage and its output terminal, said delay element providing a unit of delay; a third t.sub.d and a fourth t.sub.c pulse line, each connected to the inputs of a first OR gate (16) whose output is connected to said first stage AND gate (8) and to the input of a second OR gate (17); said second OR gate (17) having its other input connected to said third pulse line at the line output terminal; said third pulse line t.sub.d having a delay element (11) having one unit of delay between the connection to OR gate (17) and gate (16); a delay element (11) of one unit of delay having one terminal connected to the second input of the second OR gate (17) and having its other terminal at the output terminal of said fourth pulse line t.sub.c ; each multiplier stage comprising: a summing circuit (22); a first (4) and second (6) storage loop each comprising a serially connected OR gate (3), a delay element (5) providing one unit of delay, and said third and fourth AND gates (26) respectively; the output of said first (1) and second (2) AND gates being connected to an input of the OR gates (3) of said first (4) and second (6) storage loops, respectively; said second pulse line t.sub.b being connected to each stage as an input to the third and fourth AND gate (26) of said first (4) and second (6) storage loops, respectively; said first (1) and second (2) AND gates also providing the inputs to a fifth AND gate (7) whose output is provided as an input to a sixth AND gate (8); said first signal line A providing an input to a seventh AND gate (18); said second signal line B providing an input to a eighth AND gate (19); the other to each of the sixth (8), seventh (18) and eighth (19) AND gates being connected to said first OR gate (16) output; for the first stage and to the second OR gate (17) for the second stage; said seventh AND gate (18) output being connected as an input to a ninth AND gate (20) whose output is connected to one of the inputs of said summing circuit (22); said eighth AND gate (19) output being connected as an input to a tenth AND gate (21) whose output is connected to one of the inputs of said summing circuit; said ninth AND gate (20) having its other input connected to the output of the AND gate (26) of the second storage loop (6) and its output connected as an input to the summing circuit (22); said tenth AND gate (21) having its other input connected to the output of the AND gate (26) of the first storage loop (4) and its output connected as an input to the summing circuit (22); said summing circuit (22) having a delay element of one unit of delay connected between one of its "carry" outputs and one of its inputs; said summing circuit (22) having a delay element of two units of delay connected between one of its "carry" outputs, the higher order one, and one of its inputs; a delay element (23) connected between the output of the second stage summing circuit and an input of the first stage summing circuit.
3. A real time decimal multiplier circuit comprising: a first and second multiplier stage, a first pulse line t.sub.a connected to each multiplier stage through a first input of first and second gates (101); a second pulse line t.sub.b connected to each stage through an input of third and fourth gates (116); said first and second pulse lines having a delay element (11) between the connections to said first and second stages, said delay element providing a unit of delay equal to the time duration of a digit of the operand; said first and second pulse lines have delay elements 11 between said second stage connections and their output terminals which provide two units of delay; a first A and second B signal line, each connected through a second input of said first and second gates (101), respectively, to each stage, and each signal line having a delay element (11) between its connection to said second stage and its output terminal, said delay element providing a unit of delay; a third t.sub.d and fourth t.sub.c pulse line, each connected to the inputs of a first OR gate (16) whose output is connected to said first stage; a second OR gate (17) having a first input connected to said third pulse line at the line output terminal and a second input connected to said first OR gate (16) output; said third pulse line t.sub.d having a delay element 11 having one unit of delay between the connection to OR gate (17) and gate (16); a delay element of one unit of delay having one terminal connected to the second input of the second OR gate (17) and having its other terminal at the output terminal of said fourth pulse line; each multiplier stage comprising: a summing circuit (121); a first (120) and second (124) storage loop each comprising a serially connected delay element (5), providing one unit of delay, and AND gate (116); the output of said first and second AND gates (101) being connected to an input of the said first (120) and second (124) storage loops, respectively; said second pulse line t.sub.b being connected to each stage as another input to the third and fourth AND gates (116) of said first (120) and second (124) storage loops, respectively; said first AND gate (101) also providing the input to a fifth AND gate (105) whose output is provided as an input to a decimal multiplier (103); said first signal line A providing an input to a sixth AND gate (107); said second signal line B providing an input to a seventh AND gate (108); the other input of each of the fifth AND gate (105), the sixth AND gate (107), and the seventh AND gate (108) being connected to the output of said OR gate (16), and the outputs of gates (105), (107) and (108) to decimal multiplier (103), (119) and (120), respectively; each decimal multiplier having two outputs, a first output providing the unit term of the product output of the multiplier and the second output providing the "tens" term; the first output of multiplier (103), (119) and (120) being connected as inputs to decimal summer (121); the second output of each multiplier (103), (119) and (120) being connected through a time delay element (104) of one unit of delay as an input to decimal summer (121); said summer (121) having a delay element (24) of one unit of delay connected between the summer "carry" output and one of the summer inputs; a delay element (122) having one unit of delay connected between the output of the second stage summer and an input of the first stage summer.
4. A real time multiplier circuit comprising: a plurality of first and second multiplier stages, a first and second AND gate, a first pulse line t.sub.a connected to each multiplier stage through a first input of said first AND gate (1) and a first input of said second AND gate (2); a second pulse line t.sub.b connected to each stage through an input of third (26.sup.0) and fourth (26') AND gates; said first and second pulse lines having delay elements (11') between their connections to said first and second stages, said delay element providing a unit of delay equal to the time duration of a digit of the operand; said first and second pulse lines having two delay elements (11' ) between said second stage connections and their output terminals which provide two units of delay; a first A and second B signal line, each connected through a second input of said first (1) and second (2) AND gates, respectively, to each stage, and each line having a delay element (11') between its connection to said second stage and its output terminal, said delay element providing a unit of delay; a third t.sub.d and fourth t.sub.c pulse line, each connected to the inputs of a first OR gate (16) whose output is connected to said first stage AND gate (8) and to the input of a second OR gate (17); said second OR gate (17) having its other input connected to said third pulse line at the line output terminal; said third pulse line t.sub.d having a delay element (11) having one unit of delay between the connection to OR gate (17) and gate (16); a delay element (11) of one unit of delay having one terminal connected to the second input of the second OR gate (17) and having its other terminal at the output terminal of said fourth pulse line t.sub.c ; each multiplier stage comprising: a summing circuit (22); a first (4) and second (6) storage loop each comprising a serially connected OR gate (3), a delay element (5) providing one unit of delay, and said third and fourth AND gates (26), respectively; the output of said first (1) and second (2) AND gates being connected to an input of the OR gates (3) of said first (4) and second (6) storage loops, respectively; said second pulse line t.sub.b being connected to each stage as an input to the third and fourth AND gate (26) of said first (4) and second (6) storage loops, respectively; said first (1) and second (2) AND gates also providing the inputs to a fifth AND gate (7) whose output is provided as an input to a sixth AND gate (8); said first signal line A providing an input to a seventh AND gate (18); said second signal line B providing an input to an eighth AND gate (19); the other input to each of the sixth (8), seventh (18) and eighth (19) AND gates being connected to said first OR gate (16) output, for the first stage and to the second OR gate (17) for the second stage; said seventh AND gate (18) output being connected as an input to a ninth AND gate (20) whose output is connected to one of the inputs of said summing circuit (22); said eighth AND gate (19) output being connected as an input to a tenth AND gate (21) whose output is connected to one of the inputs of said summing circuit; said ninth AND gate (20) having its other input connected to the output of the AND gate (26) of the second storage loop (6) and its output connected as an input to the summing circuit (22); said tenth AND gate (21) having its other input connected to the output of the AND gate (26) of the first storage loop (4) and its output connected as an input to the summing circuit (22); said summing circuit (22) having a delay element of one unit of delay connected between one of its "carry" outputs and one of its inputs; said summing circuit (22) having a delay element of two units of delay connected between one of its "carry" outputs, the higher order one, and one of its inputs; a delay element (23) connected between the output of the second stage summing circuit and an input of the first stage summing circuit; the output terminals of signal and pulse lines of a second multiplier stage being connected to the input terminals of the corresponding signal and pulse lines of a first multiplier stage circuit to form a cascaded serial connection of first and second stages, means for applying a pulse of one digit-time duration to the input of said first pulse line t.sub.a of the first stage of the cascade at the same time as the first signal digit of an operand number is being applied to the input of signal lines A, B of the first stage of the cascade, means for applying a pulse of one-digit-time duration to the input of second pulse line t.sub.b of the first stage of the cascade at the same time as the last signal digit of an operand number is being applied to the input of signal lines A, B of the first stage of the cascade, means for applying a pulse of two digit-time duration to said third pulse line t.sub.d at stage (n/2) at a time when an operand digit a.sub.(9n/2) arrives at stage (n/2) if n is even, otherwise at stage (n+1)/2 at a time when operand digit a.sub.(n.sub.+ 1)/2 arrives at stage (n+1)/2, the first stage being designated by n=0, with n increasing by one for each stage of the serial connection of first and second stages; said third pulse line t.sub.d being electrically open between said first and second stages of the first two stages of said serially connected multiplier.
5. A real time decimal multiplier circuit comprising: a plurality of first and second multiplier stages, a first pulse line t.sub.a connected to each multiplier stage through a first input of first and second gates (101); a second pulse line t.sub.b connected to each stage through an input of third and fourth gates (116); said first and second pulse lines having a delay element (11) between the connections to said first and second stages, said delay element providing a unit of delay equal to the time duration of a digit of the operand; said first and second pulse lines having delay elements (11) between said second stage connections and their output terminals which provide two units of delay; a first A and second B signal line, each connected through a second input of said first and second gates (101), respectively, to each stage, and each signal line having a delay element (11) between its connection to said second stage and its output terminal, said delay element providing a unit of delay; a third t.sub.d and fourth t.sub.c pulse line, each connected to the inputs of a first OR gate (16) whose output is connected to said first stage; a second OR gate (17) having a first input connected to said third pulse line at the line output terminal and a second input connected to said first OR gate (16) output; said third pulse line t.sub.d having a delay element 11 having one unit of delay between the connection to OR gate (17) and gate (16); a delay element of one unit of delay having one terminal connected to the second input of the second OR gate (17) and having its other terminal at the output terminal of said fourth pulse line; each multiplier stage comprising: a summing circuit (121); a first (120) and second (124) storage loop each comprising a serially connected delay element 5, providing one unit of delay, and AND gate (116); the output of said first and second AND gates (101) being connected to an input of the said first (120) and second (124) storage loops, respectively; said second pulse line t.sub.b being connected to each stage as another input to the third and fourth AND gates (116) of said first (120) and second (124) storage loops, respectively; said first AND gate (101) also providing the input to a fifth AND gate (105) whose output is provided as an input to a decimal multiplier (103); said first signal line A providing an input to a sixth AND gate (107); said second signal line B providing an input to a seventh AND gate (108); the other input of each of the fifth AND gate (105), the sixth AND gate (107), and the seventh AND gate (108) being connected to the output of said OR gate (16), and the outputs of gates (105), (107) and (108) to decimal multiplier (103), (119) and (120), respectively; each decimal multiplier having two outputs, a first output providing the unit term of the product output of the multiplier and the second output providing the "tens" term; the first output of multiplier (103, (119) and (120) being connected as inputs to decimal summer (121); the second output of each multiplier (103), (119) and (120) being connected through a time delay element (104) of one unit of delay as an input to decimal summer (121); said summer (121) having a delay element (24) of one unit of delay connected between the summer "carry" output and one of the summer inputs; a delay element (122) having one unit of delay connected between the output of the second stage summer and an input of the first stage summer; the output terminals of the signal and pulse lines of the second multiplier stage of each multiplier circuit being connected to the input terminals of the corresponding signal and pulse lines of the first stage of a different multiplier circuit to form a cascaded serial connection of first and second stages; means for applying a pulse of one digit-time duration to the input of said first pulse line t.sub.a of the first multiplier stage of the cascade at the same time as the first signal digit of an operand number is being applied to the signal lines A, B, of the first multiplier stage of the cascade, means for applying a pulse of one-digit-time duration to the input of second pulse line t.sub.b at the same time as the last signal digit of an operand number if being applied to the input of signal lines A, B, of the first multiplier stage of the cascade; means for applying a pulse of two digit-time duration to said third pulse line t.sub.d at stage (n/2) at a time when an operand digit a.sub.(n/2) arrives at stage (n/2) if n is even, otherwise at stage (n+ 1)/2 at a time when operand digit a.sub.(n+1)/2 arrives at a stage (n+ 1)/2. the first stage being designated by n=0, with n increasing by one for each stage of the serial connection of first and second stages; said third pulse line t.sub.d being electrically open between said first and second stages of the first two stages of said serially connected multiplier.
Patent Citations (3)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3407290 | 1968-10-01 | Atrubin | |
| US3610907 | 1971-10-01 | Taylor | |
| US3670956 | 1972-06-01 | Calhoun |