Binary adder and subtractor
For large values of N, the delay becomes unacceptably large so that a special solution needs to be adopted to accelerate the calculation of the carry bits. This solution involves a "look-ahead carry generator" which is a block that simultaneously calculates all the carry bits involved. The design of the look-ahead carry generator involves two Boolean functions named Generate and Propagate.
For each input bits pair these functions are defined as: In the first case, the carry bit is activated by the local conditions the values of Xi and Yi. In the second, the carry bit is received from the less significant elementary addition and is propagated further to the more significant elementary addition. The input signals need to propagate through a maximum of 4 logic gate in such an adder as opposed to 8 and 12 logic gates in its counterparts illustrated earlier. This will produce a carry, which is added to the next BCD position.
Determine if the sum of this addition is greater than ; if yes, then add to this sum and generate a carry to the next decimal position.
Subtracter Subtracter circuits take two binary numbers as input and subtract one binary number input from the other binary number input. Similar to adders, it gives out two outputs, difference and borrow carry-in the case of Adder. There are two types of subtracters. Half Subtracter The half-subtracter is a combinational circuit which is used to perform subtraction of two bits.
It has two inputs, X minuend and Y subtrahend and two outputs D difference and B borrow. The logic symbol and truth table are shown below. However, none is known which has the capability of bypassing a function, while at the same time maintaining circuit awareness of the effect of not bypassing the function.
Such a capability is particularly required in the high speed utilization of parallel computation techniques generally and, in certain aspects, serial computation techniques. This capability is especially important when the arithmetic unit is combined in an arithmetic complex see the above copending application which is to perform multiplication, division, power generation and root taking without non-pertinent peripheral computations.
In addition, prior art full binary adders and subtracters usually have certain disadvantages in that 1 they rely on so-called standard logic symbols for their formation and explanation, and 2 they are constructed unilaterally in terms of either increased signal logic or decreased signal logic. The first restriction is detrimental in that it does not easily show where elements of an AND gate may, for example, combine with, or perform duties in, an OR gate in order to perform some such function as inhibit or.
The second restriction generally results in the inclusion of devices, such as inverters, to convert signals, that have been changed from plus logic to minus logic by the mathematics, back to plus logic. Both restrictions result in undue circuit complexity and the incorporation of unnecessary active or passive elements with attendant increase in circuit delay, instability and unreliability. For example, an important feature of this invention is the provision of an improved adder-subtracter having means for bypassing a function, such as addend or sub tracting a subtrahend, but at the same time providing a signal representing a carry or borrow which would have been generated if the function had not been bypassed.
In the prior art, there is a diversity of methods for representing the signal state of the various points of a logical block diagram, such as: This problem of choosing appropriate symbols is further complicated by the Well-known capability of most computing devices to work interchangeably in two different modes depending on the input signals; thus, a conventional diode-resistor OR gate for circuits where a high voltage represents a logical 1 and a low voltage represents a logical zero, will function as an AND gate in those circuits where a high voltage represents a logical zero and a low voltage represents a logi cal one.
Since this invention uses both logic conditions, it becomes expeditious to define the signal states only in terms of whether or not a signal exists. This will create no hardship for those skilled in the art and will provide a much simplified explanation. For those less skilled, the explanation, below, of the operation of the preferred embodiment of FIG. Accordingly, a zero is considered to exist at any point in a logic device when that point is at its at rest or null state as determined by the condition that all input signals to the device are zero.
Conversely, a one is said to exist when the point is significantly disturbed from its null position or state. In the same sense the two conditions will be designated as N for null or no signal, i. Summary of the invention Therefore, the primary object of the invention is to provide an improved arithmetic unit having a function bypass control.
Another object is to provide an improved full binary adder-subtracter having means to bypass a function and also means to generate a signal representing the effect of the bypassed function just as if it had not been bypassed. A further object is to provide an improved binary arithmetic unit which can be controlled to perform either addition or subtraction.
Still another object is to provide an improved logic circuit incorporating suppression logic to provide function bypass control in addition and subtraction operations. A further object is to provide an improved semiconductor arithmetic unit having add-subtract control and function bypass control. A more specific object of the invention is to provide a full binary subtracter having means to bypass a subtrahend which would produce a negative difference and also having means to produce a signal representing a borrow which would have been generated if the subtrahend had not been bypassed.
Briefly, in accomplishing the foregoing object in a preferred embodiment of the invention, there is provided a full binary adder-subtracter having add, subtract and bypass control terminals. When the bypass control signal is activated, a function such as an add or subtract operation is bypassed so that the input appears at the output unaffected by the function, but at the same time, there is generated a signal representing the effect a borrow or carry of the function as if it had not been bypassed.
Brief description of the drawings The foregoing and other objects and advantages of the invention will become apparent from the following description read in conjunction with the accompanying drawings in which:. FIGURE 1 is a logic diagram of an improved binary arithmetic unit utilizing suppression logic having add-subtract control and function bypass control;. FIGURE 3b is a schematic block diagram of a portion of a matrix or arithmetic complex in which the improved arithmetic unit is particularly useful; and.
Description of the preferred embodiment In FIG. At the same time, it adds to such a matrix the novel feature of bypass or K control described earlier.
As such, it must be capable of adding one to three bits on command and producing a sum and, if required, a carry signal. Furthermore, in performing division, it must be capable of subtracting one or two bits from zero or one and producing the proper difference and borrow signals.
Beyond these requirements, and as described in detail below, it must be capable of producing appropriate carry or borrow signals without affecting the sum or difference signals under certain conditions. The buffer B of FIG. When an N signal i. Terminals 10 and 11 receive the bit signals of the augend or minuend and addend or subtrahend , respectively, and terminal 19 receives the carry in or borrow in signal from the next lower order stage.
The control input terminals 16, 28 and 32 receive control signals which set the mode of the arithmetic unit and will be discussed later. The sum or difference signal appears on terminal 38 and the carry out or borrow out on terminal Operation of the improved arithmetic unit as a full binary adder will now be described for the eighth condition, or row 8, of Truth Table No.
For this condition, the inputs are:. At the same time, the Y on terminal 11 produces a Y at the inputs of suppressors 14 and Suppressor 14 however is closed by the control input Y supplied by buffer 13 resulting in an N on line On the other hand, the Y on the input of suppressor 15 is transmitted to the output of 15 since the gate is open because of the N signal impressed thereon from the K control entry, The Y on the output of 15 is impressed on one input of OR gate 17 causing a Y in the suppressor Suppressor 31, however is closed because of the Y control gate signal impressed from Shh input The result is an N signal on the output of suppressor 31 being impressed on the input of buffer 34 causing an N signal on the output of 34 and on line Output of 17 and q n ly a Y on the inp of Similarly, the N signal on line 42 and the Y signal suppressor It will be noted also that the Y on input on li 39 are impressed as inputs t OR gat 26, proterm nal 10 is impressed on one input of OR gate 1 ducing aY in the output of OR gate 26 which is impressed causlng a Y in Output of 17 a on the input of suppressor Suppressor 29 is open be- The Y the mput of ,Suppressor 18 not translmtted 10 cause of the N signal received from m input 28; therehowever, since gate 18 is closed due to the action of fore there will be a Y Signal appearing on the Output the Y signal from buffer 13 which is impressed on the of Suppressor 29 and accoidingly on line 46 controlmput of gate It will be recalled that the output of OR gate 26 was It W noted that the Y slgnal m the output a Y signal appearing on line Now considering AND of buffer 1s Impressed 15 gate 30, it is apparent that one input of this gate is sup- The critical signal conditions as of this stage in the plied from input 16 the K control input, which is an explanatlon can be Summarized as follows: I 20 is impressed as an input to OR gate These two f inputs combine to produce a Y signal in the output Lme 39 Y of OR gate 33, which is impressed as an in ut to butter Lme 40 N 35, resulting in a Y signal output from buffer 35 which Lme 41 N 25 appears on line 47 and thence on output terminal 38, Input 19 Y which is the sum or difference output of the add-subtract Resuming the description from this point, it can be seen f yi the slgnal 0n 'llne a d he Y that the Y signal at input 19 and the N signal on line slgnal 4 46, an?
P as Inputs g t are both impressed as inputs to AND gate The Y signal on input 19 is also applied as an input to suppressor Since the control gate of suppressor 22 is driven by the N signal from buffer 21, there will be a Y signal in the output of suppressor 22 which will appear on line In like fashion, the Y signal on input 19 is also impressed as an input to suppressor The control gate of this suppressor has an N signal from the K control input 16;.
The other input to OR gate 24 is the N signal on line However, by the truth table for OR gates, only one Y signal is required to produce a Y signal in the output and, therefore, there will be a Y signal from the output of OR gate 24 applied to the input of suppressor The control gate of suppressor 25 is driven by the N signal from buffer 21, therefore, there will be a Y appearing at the output of suppressor 25 and impressed on line Finally, the N signal output of butter 21 appears on line With the foregoing in mind, let us now review the logic required of an arithmetic unit if it is to fulfill the requirements of such a unit in an arithmetic complex.
FIGURE 3b shows a plurality of similar arithmetic units arranged in a matrix to perform calculations as described in more detail in co-pending application Ser. Let us now consider unit AU from row 1, column 3, of the matrix. K or not add; S or no subtract; and K or bypass. For the operation of add, as reqiured in addition, multiplication, power generation, etc.
Y signal indicating do not substract S. No signal, or N, indicating do not add, i. The logic arguments for this operation may be stated as follows: Y signal, on the T output terminal, and there must not be a carry output, i.
Continuing this one step further, by substituting 1s and zeros for the signals or no signals respectively, one can summarize the add operations to the eight possibilities shown in truth table number 1. For application of the arithmetic unit to the general operation of multiply, wherein the various multiplication partial products are supplied to a matrix multiplier as addends, it is obvious that the add operation pertains throughout all phases. Divide, on the other hand, is conventionally performed as a series of trial subtractions.
In co-pe'nding application, Ser. Reference should be made to that application for greater understanding of the process. It is sufficient here to state, however, that in the case of a not-permitted subtraction in the division or root taking process, it is essential that an unsatisfied borrow signal one that, if it were used, would cause a negative difference be maintained to indicate the unsatisfied, or not-permitted, subtraction condition. At the same time, in such a case it is required that the inputs appearing at the E and F terminals of the particular row of the matrix of arithmetic units not affect the output signals appearing at the T terminals.
In other words, the information at the P terminals of the row must be repeated at the T terminals of that row, and the borrow conditions if the E and F inputs of that row are used must be maintained.
For this reason, there is provided as an important feature of this invention, a bypass or K control circuit. The need for K or bypass control in add operations is not as obvious, but there are certain conditions in the evaluation of mathematical series or in curve fitting where it is desirable to have this bypass capability.
For example, it is advantageous to know when the addition of a certain sum causes a carry to be extended to the left beyond a certain column of the matrix. If there are undue mathematical calculations or test operations, then this particular certain sum should be recorded continually in the add matrix, yet its effect on the total be nil. A description of the function of the K control requires reference again to FIG. In the case of subtraction, the.
Looking at FIGURE 1, it is seen that the application of a K control signal to terminal 16 by means of suppressor gates and 23 prevents any input signal supplied to subtrahend input 11 or to borrow input 19, respectively, from entering the sum chains formed by elements 17, 18, 40, 24, 25, 43, 33, 35, 47, and T or sum output terminal At the same time, however, note that the effects of the subtrahend E or the borrow in F with respect to developing a borrow out signal G are determined by chain 11, 14, 41 for the subtrahend and chain 19, 22, 44 for the borrow in.
Consequently, chain 27, 31, 34, 48, 36, 49 and G borrow out terminal 37 is not suppressed and produces the borrow out signal which'would have been generated if the difference output T had not been suppressed for the trial subtraction. In addition, through AND gate 30 and OR gate 33, the K or bypass signal, along with a possible borrow signal, serves to regenerate at terminal T a sum signal that might otherwise be lost.
The logic of this operation is as follows. With respect to the minuend and the subtrahend, the combination of AND gate 12, buffer 13 and suppressor 18 serves to provide a sum output of zero in those cases where both the minuend and the subtrahend exist as ls. Similarly, in the case of the borrow and a possible sum output on line 40, the combination of AND gate 20, buffer 21 and suppressor 25 serves to assure a zero sum output for those conditions wherein a minuend and a subtrahend or a borrow exist.
In Boolean terminology, this is stated as,. Since the described logic chains, when a K signal appears, would suppress this sum signal, it is necessary to regenerate the P signal as a sum signal at the T output terminal The logic followed to accomplish this is that, if there is a K signal and there is a borrow signal on line 45, then there must have been both a P signal and an E signal; therefore, there must be a Y signal at the T output. To produce this result, the K signal Y from input 16 and the borrow signal Y from line 45 are applied to the inputs of AND gate 30, thereby producing a Y signal on its output which is then applied to one of the inputs of OR gate 33, which transmits a Y signal through buffer 35 and via line 47 to T output terminal It is to be noted that this preferred embodiment does not include speed up devices such as capacitors, back biased diodes, anti-saturation or anti-cutoff clamps, or precisely adjusted voltages since the use of these techniques is well-known in the art and incorporation is not essential to the novel operation of the invention.
Of course, different operating parameters such as high speed, or low current, or different or even inverted signal polarities, or diverse ambient environments may require different design parameters. The resistors 52, 53, and 54, the bias supply voltage -V and the emitter-base characteristics of transistor 51 comprise the AND gate 12 of FIG.
Similarly, the resistors 82, 83 and 81, the bias supply voltage V and the emitter-base characteristics of transistor comprise the AND gate 20 of FIG. Their operations are identical, so only AND gate 12 will be explained. The values of the resistors and the bias potential V,, are so chosen that a positive Y signal on either the P input 10 or the E input 11, but not on both, will leave point at a potential below that slight positive with respect to ground potential required at the base of transistor 51 to cause conduction in transistor However, when Y signals positive are applied simultaneously to both the P input 10 and the E input 11, point will be raised to a high enough potential to cause base current flow in transistor 51, which, as is well known, produces an amplified collector current flow, thereby lowering the potential at the collector of transistor 51, point , to a value very slightly above ground, corresponding to a Y negative signal on point The resistor 62 and the diode 61 comprise the suppressor 14 of FIG.
Its action is such that a Y signal impressed on terminal 11 transmitted through resistor 62 would tend to raise line 41 to a level considerably above ground; however, in the event that a Y signal appears on both terminals and 11, then the previously defined and action at point causes transistor 51 to conduct. Transistor 51 and its collector resistor 50 comprise the buffer of FIG.
As mentioned earlier, when this transistor conducts, the point is maintained at a position only slightly above ground due to the low impedance of transistor This constitutes a Y signal which is impressed through diode 61 as the suppress or control input of buffer 14 of FIG. Similarly, resistor 73 and diode 63 comprise the suppressor 15 of FIG. The action again is such that a Y signal on terminal 11, in the absence of a Y signal on terminal 16, will raise point considerably above ground as a Y signal; however, a Y signal appearing at terminal 16 and transmitted through diode 63, the suppressor gate, holds point at, or very near, ground potential, suppressing the signal appearing through resistor The action is such that a Y signal impressed on entry 10 or at point will raise point to a high positive potential, constituting a Y signal at point Resistors 73 and 74 and diode 70 and transistor 69 comprise the suppressor gate 18 of FIG.
Their operation is such that a positive signal propagated through either diode 71 or 72 would normally raise point to a high positive potential; however, if transistor 51 is conducting, resulting in a Y signal on point , then point and the output of transistor 69, line 40, are clamped to a low potential which is effectively an N signal on line Resistors 82, 83, 81, transistor 80 and resistor 79 perform identical functions with their counterparts, resistors 52, 53, 54, 50 and transistor 51 above.
Resistor 96 and diode 90 comprise suppressor 21 of FIG. Resistor 98 and diode 97 comprise suppressor 23 of FIG.