^ m Ij: f /.;->:■:■ litiUH'hii'lll'l'i' immmmm i m L I B R.AFIY OF THL U N IVLRS'ITY Of ILLINOIS >-; The person charging this material is re- sponsible for its return on or before the Latest Date stamped below. Theft, mutilation and underlining of books are reasons for disciplinary action and may result in dismissal from the University. UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN ^UG 1 2 1971 km ' ^ R ;c"3 6?/ 31 tilL)} ^/ 9' mo Ldim WO4 i BuIbM i mi JSE O^LY 1982 i LI6I— O-1096 '•''}. '^^•?.<' i \'\<: M m "^ mt^ .^c REPORT m. 195 tie o • >^ METHODS OF BINARY ADDITION by Roger E. Wiegel COO -1018-1069 1x1 \ ^b 7^^ February 1, I966 The person charging this material is re- sponsible for its return on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. University of Illinois Library FEB 6 Rh jU L16I— O-1096 r* m\ Report No. 195 METHODS OF BINARY ADDITION* by Roger E. Wiegel February 1, 1966 Department of Computer Science University of Illinois Urbane, Illinois 618OI This work was supported in part by Contract No. US AEC AT(11-1)1018 and was submitted in partial fulfillment of the requirements for the degree of Master of Science in Electrical Engineering, January, I966. '\. ACKNOWLEDGNENT The author wishes to express his sincere thanks to Professor S. R. Ray whose advice and assistance were greatly appreciated in the C^/ ^ preparation of this paper. Thanks are also due to Miss Bonnie Malcor for typing the final draft. The excellent drawings in this report are a result of the good work of Mrs. L. A. Prendergast of the Department of Computer Science Drafting Department. Ill TABLE OF CONTENTS Page 1. INTRODUCTION 1 2. HISTORY OF BINARY ADDERS 3 3. RIPPLE CARRY ADDER 5 3.1 Half -Adder 5 3.2 Full-Adder 5 3.3 Ripple Carry Adder 8 k. CARRY LOOKAHEAD ADDER 10 k.l Principles of Operation .10 k.2 Adder Logic 11 U.3 Second Level Lookahead 1^ ^.U Lookahead Variations 15 ^.5 Lookahead Adder Sujumary l8 5. CARRY SKIP ADDER 20 5.1 Basic Skip Circuit 20 5.2 Extension of Carry Skip 22 5.3 Conclusion , 26 6. THE CONDITIONAL SUM ADDER 30 6.1 Basic Theory and Logic 30 6.2 Improved Conditional Sum Logic 32 6.3 F\urther Speed Increases .38 6 „h Conditional Sum Adder Summary ^2 7. THE ASYNCHRONOUS ADDER ^3 7.1 Principles of Operation ^3 7.2 Asynchronous Carry Logic ^'+ 7.3 Self-Timing Adder Stage U6 7.^ Variable-Time Adder Summary ^8 8. SEPARATE CARRY-STORAGE ADDER , ^9 8.1 Principles of Operation ^9 8.2 Adder Logic .51 8.3 Summary 5^ 9. SUMMARY OF ADDER-TYPES 55 9.1 Adder Design Notes .56 9.2 Future 57 APPENDIX 1 59 APPENDIX 2 . . . 6l BIBLIOGRAPHY - ^^ IV <«^r>; 1 . INTRODUCTION An "adder" is defined as the physical realization of some logical scheme to achieve the (binary) addition of two niombers within the framework of some larger system. The purpose of this paper is to present and discuss the logical organization and operating principles of various types of parallel binary adders. Since neither the physical realization of the adder nor the larger system siorrounding the adder are our principal concern, certain assumptions will be made about the environment in which the adder is embedded. First, it is assumed that the system operates, in parallel, on binary number fields, n bits in length, as contrasted to a serial machine, which operates on bits of a binary number one at a time, i.e., in series. Examples of parallel machines are computers such as the ILLIAC II, IBM 7090, and the CDC 660O. A series computer is one such as the EDVAC^ which operates on UU-'bit words. The number field bits are represented by X^ , ..., X , with X ^ ^ 1' ' n^ n being the least significant (right-most) bit. The number representation employed in the system may be any one of signed-magnitude I's complement (diminished radix complement), or 2^s complement (radix complement). The basic adder mechanism functions independently of number representation. Auxiliary operations such as pre- and post-addition complementing logic, overflow, underflow, and zero detection logic, and end-around and low-order carry injection circuitry are performed in the peripheral circuitry. Flores' book [5]'^ contains a complete summary and examples of the rules for addition, subtraction, etc. in the various number systems . * Numbers in brackets refer to the corresponding entry in the Bibliography. -1- -2- Furthermore^ it is assumed that both true and complemented inputs are available from the necessary input and output buffering registers which are provided along with control and gating logic exterior to the adder. For each adder-type discussed, two or more logical design variations will be presented. The first will best illustrate the operating and logical principles of the adder in question, and will be based on the unrealistic assumption that the physical elements have an indefinitely large fanin and fanout capability. The alternate design(s) will be guided by physical constraints, i.e., elements are capable of fanins of 2 to 10; fanouts of 1 for an AND or OR, and fanouts of 2 to 20 for a NOT (or NAND) . Direct-coupled rather than pulse-type logic will be used. m 2. HISTORY OF BINARY ADDERS Addition is one of the more common processes occurring in general purpose and scientific computers. It is not uncommon to find two or more adders of different types in a single machine. These adders are often used several times during the execution of the various instructions. Since the adder is so central to the operation of a computer, it pays to carefully choose and design an adder to match the machine and its projected use. The ENIAC, put into operation in 19^5^ was the first chiefly electronic computer. It had a word length of 10 decimal digits plus sign and effected addition by using 10 stage decade counters. ENIAC used 10' s complement representation of numbers for subtraction. Its add time was about 100 |j.sec. EDVAC (l9^9) was a serial machine with a word length of ^1+ bits. ILLIAC I, completed in 1952, was based upon the IAS computer described by Burkes, et al [h] . Additions on ILLIAC s UO-bit words were performed in parallel, using a ripple carry adder, with an add time of about 15 [isec. A carry could propagate through eight stages in about l.l.iasec, and the s\im for any given bit was formed wittin l/^ usee after the arrival of the carry. In the worst case, a carry had to ripple the full, UO-position length of the adder before the addition could be completed. It can be seen (especially in ILLIAC l) that most of the time required by adders is needed for carry propagation. This was one of the more serious obstacles to overcome in speeding up the addition process as computers were made faster. One obvious way to decrease carry propagation time (increase speed) is to use faster components -- i.e., faster transistors, diodes, etc. but there are limits in doing this, since as the speed of a device increases, -3- -h- so does its cost. So the designer has two paths open to him: he may develop faster components and circuitry, or he may organize slower components into faster, more efficient systems. It is the latter course which will be followed in this paper, which describes several methods which have been developed for reducing the carry propagation time. 3. RIPPLE CARRY ADDER The ripple carry adder is fundamental to all adder-types. It was one of the first adders used in computers. From it, all other odder-types have evolved. Before discussing the ripple carry adder, its building blocks, the half- and full-adders, will be introduced. 3.1 Half -Adder The basic building block of the ripple carry adder is the half -adder, When two binary digits X. and Y. are added, a sum digit, S., and an output carry digit, C. ., , are obtained. The relations between X., Y. , S. , and C. ^ D > i-l-" 1^ i' i' 1-1 are given in the truth table below. The logical realization with "ideal" elements-^ is shown in Figure 1. The block diagram which represents the half -adder is also given. Half -Adder Truth Table x; 1 : Y. 1 =i-l s. 1 1 1 1 1 1 1 S. = (X. ^ Y. ) X. Y. = X. Y. ^ X. Y. 11 111 11 11 C. = X. Y. 1 11 3.2 Full-Adder To form the sum of two binary digits when an input carry, C, is present, two half-adders, plus an additional OR to assemble the output carry, C. , are necessary. The truth table from which the full-adder logic . * Definitions of all logic symbols are given in Appendix 1, -5.- > .-. J -6- HA Ci-i S; FIGURE I. HALF-ADDER *Si Xi Yj _L__L HA 1 L HA Ci-i Si X; Y; FA Ci-l S; PICTURE 2. ALTERNATE LOGICS FOR ONE BIT OF FULL BINARY ADDER -7- is realized is Full-Adder Truth Table X. 1 Y. 1 c. ]. =i-l s. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2 illustrates the full-adder logic. The partial sum output from the first half-adder and the carry input to the stage form the inputs to the second half -adder. An output carry (C. ) may come from either half -adder and arises whenever a majority of the inputs (X., Y.j and C.) to the stage are '1'. The s\im, S., is '1' when only one or all three of the inputs are ' 1' . Equations for the full-adder are: I I or and or S. = X. Y. C. ^ X. Y. C. ^ X. Y. C. ^ X. Y. C. 1 111 111 111 111 S. = (X. © Y. ) . C. ^ (X. © Y. ) . C. 1 i^^i 1 i^-^i 1 C. , - X Y. ^ X. C. ^ Y. C. 1-1 11 11 11 ;. , = (x. Y.) • C. ^ X. Y. 1-1 1^^ 1 111 -8- Figure 3 gives an alternate logical realization, using NANDS, for one bit position of the full-adder. This logic is better than that of Figure 2 in that the NANDS provide signal level restoration and amplification, for the carry in particular. Collector logic is used in two instances to produce a negative OR function, i.e., if the output of either NAND of the common pair falls to '0', the output from the common junction goes to '0'. 3.3 Ripple Carry Adder The one bit full-adder blocks of Figure 2 or 3 can be inter- connected as shown in Figure h to form an n-bit ripple carry adder. The term "ripple carry" is used since the sum bit at stage i cannnot be formed until the carry C. is input. C. depends on the inputs to stage i+1, which depend on stage i+2, etc. Hence, carries must ripple through from the low-order stage (n) to the high-order stage (bit l) in order to complete an addition. If the NAND logic of Figure 3 is used, two delays per stage are needed to propagate the carry (one delay is the time needed for a signal to pass through a NAND circuit), for a total of 2n delays* to form the sum in an n-bit adder. The speed of addition in the ripple carry adder is limited by the maximvun time required to propagate a carry through the adder. In modern computers, this time can be excessive. The obvious way to speed up the addition process is to decrease the carry propagation time. The following sections describe different methods of reducing carry propagation time. * 2n = 2 delays in the first stage to generate the carry, plus two in the middle stages to propagate it, plus two in the last stage to form the. sum. -9- Xi Yj FA T"~T Ci-l Si C: FIGURE 3. ONE POSITION OF FULL BINARY ADDER USING NAND LOGIC X| Yj LA. FA Ci_ J ^i+l Yj+i X;+2 Yi+2 ^i+S ^1+3 LI _L_L J_l FA FA Ci +1 FA 1+2 'i+3 S|+| '1 + 2 + 3 FIGURE 4, 4- BIT SECTION OF RIPPLE CARRY ADDER t I h. CARRY LOOKAHEAD ADDER The carry lookahead adder (or simultaneous carry or distant carry adder) is a direct descendant of the ripple carry adder. Instead of waiting for carries to ripple through to some stage 1, logic is employed vhich "looks ahead" to see what the true input carry to stage i will be without waiting for it to ripple up to the stage. k.l Principles of Operation In the ripple carry adder, the carry into stage i was defined as: C. = X Y. ^ ^ C. ^ (X. _ -^ Y. J 1 1-1 1-1 1-1 1-1 1-1 As mentioned above, the formation of each carry digit must await the generation of the next lower-order carry. If the following fimctions are defined ; G. = X. Y. 1 11 T. = X. ^ Y. Ill then the carry expression becomes C. = G. , ^ T. ■ C. , 1 1-1 1-1 1-1 Note that X. 0Y. will work as well as X. v- Y. in the expression for T., since if both X and Y are '1' , then'G. Is '1' and it does not matter i i 1 ' if T'. is '1' or '0' . : The. carry expression now consists of two parts: G, which is produced independently of an input carry, and T, which ■ causes' a carlry to be generated on t]ie condition that there is an input carry. In effect,' G is a generated carry, and T is a propagated (transmitted) carry. -10- -11- From this description^ the carry into any stage i con be written in terms of the C ' s ' and T's of the preceding stages so that any bit position can "look ahead" to see what its true carry input will be. The lookahead equation is ^i=^i-l^^i-l^i-l 1-1 1-1 1-2 1-1 1-2 1-3 1-1 1-2 1-3 i-3 This expression can be continued as far as desired, limited only by physical considerations. ^.2 Adder Logic Figure 5b illustrates the application of the carry lookahead principle to an adder section of h bits. (Figure 5a is the modified full- adder logic used in the FA' blocks of Figure 5b.) X. and Y. are the addend and augend inputs, S. is the sum output from bit position i, C. is the ^1 in carry input from the preceding lookahead group, and C is the output carry to the next group. If the logic of Figures 5a, 5t) is replaced by the equivalent NAND logic, an n-bit adder can be assembled using n/U lookahead groups. This adder would have full carry lookahead within ^-bit groups, with ripple carry between groups. The adder would need two delays to generate all T's and G's; two delays per group are then needed to propagate the carries through the adder. Two of the four delays needed for sum generation are taken simultaneously with the output carry generation from the last group. Thus, for a UO-bit adder (ten groups), 2k delays are required to complete an addition. In this case a 39 per cent increase in hardware X, Yj ■12- FA' G; C, Tj FIGURE 5a. MODIFIED FULL- ADDER OF FIGURE 2 FOR USE IN CARRY LOOKAHEAD ADDER •13- < LU o Q q Q -I < >- I- ^ ? < ^'2 IT) X liJ I- O ( o u -lU- over the ripple carry adder will increase the addition speed by a factor of 3.3.* k.^ Second Level Lookahead Carry lookahead between bits in a group is called level one lookahead; between groups within a section (two or more groups) level two lookahead, and between sections, level three. The philosophy behind level one lookahead is that since it is easy to tell whether or not a given bit position will generate (X. Y. = '1') or propagate (X. v Y. = '1') a carry, the carry into a bit position can be determined from the G's and T's of lower-ordered positions. This idea can be extended from single bits to groups of bits; so it can be determined whether or not a given group will generate a carry, propagate through , or absorb an incident carry. A section can be defined as consisting of three or four groups; the l+-bit groups of Figure ^b in the present case. The equations for the level two output carry, C_, from the section are, for a three group section: C^G^TG^/TTG^TTTG, ^PG^PTG^-^ 1 1 2 1 2 3 1 2 3 ^ 1 5 1 5 6 P T T^G^/P T T^T Go-^P P G'^P P Gv- 1 5 6 7 1 5 6 7 8 ^1 2 9 1 2 9 PPG^PPTG vpPTT G vPPTT T G ^ 129 1 2 9 10 129 10 11 1 2 9 10 11 12 1 2 3 in where the T's and G's are defined above, and the P's are the propagate functions * Appendix 2 contains a chart which compares various adder types with the ripple carry adder. Hardware and speed comparisons are given there. and P^ = •15- "l ^2 ^3 ^h T^ T^ T^ Tg T T T T 9 10 11 12 If a carry is generated anywhere within the 12 bits, and all intervening bits would transmit it, the carry will immediately appear as C . All of the above functions, except the P.'s, are available in the level one logic, and the P's can be added at little cost. The above discussion can be extended to level two lookahead over any number of groups in a section, or to level three lookahead between sections. The realization of the above equations in hardware is similar to the logic of Figure 5c and will not be given. Level three lookahead, in general, will be of little use or benefit in adders operating on word lengths of fewer than ^0. to 50 bits. h ,k Lookahead Variations Figure 6 illustrates three of the many possible ways of segmenting a ^0-bit adder into sections. The first contains sections of 1, 3; 3, and 3 groups, the second contains 2, H, and h groups, and the third has 1, 2, 3^ ai^d h groups per section. Each group is comprised of h bits with full lookahead as shown in Figure 5b. Carries ripple through the second level lookahead units^and, from them, through the individual groups in each section. The maximum length carry ripple path in Figirre 6a traverses second level functions S2 and S3, then through all groups fed by the S2 function {ch, G3, and G2). In all variants, two delays are needed to form all G and T functions and two delays per section lookahead unit (Sl, S2, S3) are necessary for carry propagation. Each of the left-most groups (Gl and G?) requires two delays for carry propagation and finally, sum generation requires two more delays. i! •l6- 'OUT Gl G2 Tl G3 T2 G4 T3 T4 'IN Pj OUTPUT IS USED IN SECOND LEVEL CARRY LOOKAHEAD (SEE FIGURE 6) ^i FIGURE 5 C. ALTERNATE CARRY GENERATION LOGIC FOR CARRY LOOKAHEAD ADDER SECTION FIGURE 5d. ADDER LOGIC OF FIGURE 3 MODIFIED FOR USE IN CARRY LOOKAHEAD ADDER -IT- z o i o o O Q. 1 CD CD Q.*^ i 00 CD CL» 1 ' ro ( <. J 1 1^ CD qT Q."* 1 CD I CD of 1 i i r ■ CVJ si 1 CD a5 1 CD to a. 1 C\J CD 1 (O o CD X CVJ o a Ui CO (rt CD L.: ^ fO O CVJ if) >• ca cc < o Q UJ Z O X -3 1- ^ UJ Q CO Q Q. < 3 O q: CD < UJ X cr < o V Lj_ o o (.n _I \- •z. V UJ ^ ^ nr UJ < CD c> z < rr o tr ^ < 1- UJ UJ > UJ _l UJ 1- u. _i o CO CD UJ a q: CO -18- For version (a) of Figure G, ik delays total are needed; version (b) of the UO-bit adder likewise requires 1^ delays; version (c), however, can complete an addition in 12 delays although it needs no more hardware than (a) or (b). It is seen that a rearrangement of groups can decrease the add time. For the lookahead adder using level two lookahead, a U6 per cent hardware increase cuts the add time by a factor of 7 over the ripple carry adder. Further time savings may be realized if the group size were increased from U to 5 or 8 bits (for the i+O-bit adder). The lookahead adders described above can be modified in various ways to suit the needs and desires of the logic designer. One possible variant might have carry lookahead within groups with ripple carry between groups. Some of the other changes which could be made if a larger or smaller size adder, or faster or slower operation is desired, are (l) use ripple carry within groups and full lookahead between groups; (2) use full lookahead within groups and between groups; and (3) use the logic of the completion recognition adder (Section 7) to detect the completion of the carry propagation between groups. The speeds and hardware requirements for two variations of this adder are given in Appendix 2. Most of the design ideas and methods covered in the following section on carry skip adders applies equally well to the design of carry lookahead adders, so nothing more will be said here about adder design. U.5 Lookahead Adder Summary The carry lookahead adder, first described by Weinberger and Smith [18] in 195^, is basically a fixed-time adder, i.e., the addition is completed in a fixed allotted time. If modification (3)^ above, is employed, the adder becomes a variable-time device. -19- MacSorley [10] gives a comparison of five lookahead adder variants using 50 and 100 bits. The lookahead adder has an ultimate speed capability of 8 delays, The amount of logic required would be quite large compared to that for the ripple carry adder. In most cases, though, a slightly slower version requiring much less hardware, would suffice. I I 5 . CARRY SKIP ADDER The carry skip, or anticipatory carry, technique may at first appear quite similar to the carry lookahead method for decreasing carry propagation time. The lookahead method, however, determines the true carry into each bit position as an explicit function of preceding positions; the carry skip method uses a form of ripple carry, bypassing (skipping) carries around bits or groups of bits which would only cause the carry to be propagated, 5 »1 Basic Skip Circuit One of the first, and simplest, carry skip circuits was described by Morgan and Jarvis [12] in 1959. They fragmented the adder into 6-bit groups and made provision for bypassing the carry around the groups. Their basic logic is given in Figure 7. If the condition 1. = X. ^ Y. Ill is satisfied at stage i, an incident carry is enabled to pass on to the next stage through a skip gate. If the above condition is satisfied by all stages in a group, a carry incident on the group will be shunted around the group with minimal delay (Fig-ure 7). In Figure 7 the only true skip occurs when the input carry, C. , is bypassed through the AND at the bottom of the figure. All remaining carries, wherever generated, must ripple through the logic to C + or be absorbed internally. A carry chain of up to 8 delays (using NANDS), in the present case, can exist within one group. ■20- -21- •"Q. V (D a. _) o >- tr cn CO on < (J LlI Q >- n tr < < h- t: 1- UJ m ^ 1 III _J ^ UJ oc o u. f^ o LU (0 tr o _) ...J e> (1 o u -22- The equation for C of Figure 7 is C ^ = G, N^ T, C, N/ P C. out 111 m which is identical to the expression for the ripple carry, except for the P C. term, the carry skip term, where P is the propagation function, equal to T^ T^ T^ T^. The carry skip group of Figiore 7 can be employed in a ^0-bit adder like that of Figure 8a. This adder yields a worst-case add time of UO per cent of that of the ripple carry adder with but a h per cent hard- ware increase (using the adder stage of Figure ll) . 5.2 Extension of Carry Skip In view of the ideas and logic presented in the previous section, Lehman and Bur la [9] posed the following fundamental questions: (1) What is the optimum group size for equal-sized groups for n-bit binary adders? (2) Can the circuit be further speeded up by using unequal-sized groups? (3) Is it advantageous and economical to provide skip gates within or between the groups, or both? In answer to (l), it was shown [9] that the optimum group size is about n/lO bits for an adder n bits long (n greater than 30) • This is the optim-um size only if fixed group size is used throughout. As for (2). unequal groups will speed up the logic. The optimiun division is obtained when group sizes increase by one stage (bit) for each group up to the middle group (pair of groups), and then decrease in a similar manner. Thus, the dependence of the carry propagation time on the carry chain length is almost eliminated. ■23- o LlI q: UJ N CO Q. ID O q: o Q UJ X Ljl o o en hi _j CD < (O li- o q: UJ Ul ^ Q n 1- < Q n O < ^ U) P" o >- a: tr 1- < o u Ul U_ 2 Ul Ul N CO 00 a. -1 UJ o tr q: ^ CO o ■ Z3 O o -2U- Figiore 8b gives an example of the adder obtained using unequal groups, Figiore 8a shows a ^0-bit adder made up of U-bit groups like the group of Figure 7. The adder of Figure 8a has an add time of 32 delays; that of Figure 8b is 26 delays. Moreover, the faster adder of Figure 8b uses less hardware' It can be concluded that an adder should be composed of fixed length groups of optimum size only if it is not feasible to use groups of varying size. The skip techniques discussed so far are essentially primitive since only a few of the many possible carry chains have been bypassed. Inter- and intra-group skips may be postulated. By adding a sufficient number of skip circuits, the add time may be reduced as much as desired to a lower limit of eight delays (for a i+O-bit adder) -- two to form carries, four to propagate them everywhere, and two to form the final sum. Figure 9 gives the logic for a ^-bit adder group with skip circuitry capable of sum formation within six delays after X, Y, and C. m are -Dresented, C , will be present within four delays. Without any skip ^ out gates except the group bypass, the add time is eight delays, and C formation also takes eight. It is not possible to add another nonredimdant skip gate to this group (Figure 9). As the group size is increased, the time savings becomes more significant when full carry skip logic is employed. A 7-bit group, for example, needs lU delays without skip gates, and only six delays with all possible nonredundant skip paths to form the output carry. Groups of groups may also be bypassed. The propagate signals, P., output from each group (Figure 7 or 9) are brought together to J control the inter-group skips. Again, the idea of increasing the n\imber of groups in a section by one for each section, from the outside to the center, pays off. Figiire 10 shows two adders, one using U-bit groups. -25- -26- the other, 5-bit groups. The U5-bit adder using 5-bit groups and fixed section size adds in 26 delays; the U8-bit adder using i|-bit groups and variable section size, adds in 2U delays by employing the adder logic of Fig\ire 11 in the group logic shown in Figure 7. Even more time savings would be realized if the end groups were shortened and the center group(s) increased in size as outlined above. Figure 12 gives an abbreviated form for the logic of a UO-bit adder with full carry bypassing. This is the ultimate speed carry skip adder since all possible skip paths have been provided. Regardless of the adder size, eight delays are required to complete an addition. (The actual adder size, and hence, speed, will be limited by gate capabilities . ) 5.3 Conclusion In the design of a carry skip adder, the designer should try several combinations of group size and arrangements of inter- and intra- group skip paths in order to obtain the desired speed at minimum cost. Where the alternative exists, the groups should be made smaller, increasing inter-group skips while decreasing the number of skips internal to the groups . The adder design should be inspected for redundant carry skip gates. A gate is redundant if it enables an input carry to be present at a bit position before the total time needed for carry propagation has elapsed. Redundant skip gates, if present, may be eliminated with no accompanying degradation in add time. The carry skip adder offers the logic designer a method by which the add time can be significantly decreased with but little increase in hardware over the ripple carry adder. As the skip paths become more numerous and complex, the logic approaches that of the full carry lookahead adder as the limiting case. ■27- ^m' z o — ''^ or - -^ 00"^ Q? \ J 1 y dJ lO o oT' ^ ^ 1 ^ com o 1 UJ K' < CO LJ cr UJ 3 < u. in z Q. — 3 o z q: % o o X lij V) (- o (O 2 < CO q: LU Q Q < Q_ i^ (/) I >- q: < o m I 00 o z < lO Ijj o IJ- •>'y;x:..>;;.-.;.',: ,' '■•I'X '.V ■?8- X, Yj Xi Yi 'OUT X-Y XvY X®Y A r D^ * S\ r\ x®Y yi}" FIGURE II. ADDER STAGE OF FIGURE 3 MODIFIED FOR USE IN CARRY SKIP ADDER ■29- X H ^ q: LlI rr Q o Q ii. < n Q. LlI :^ Q CO > o > en Q. tt: < CO o X h- 1- s GD 1 a. O V ^ CO Q UJ 1- 1- z: 1 1 LlI _) i 1 q: o OQ UJ CD tr < z / o 1/ z CsJ < LU Ql CD 6, THE CONDITIONAL SUM ADDER The designs of the previous three adder-types were based^ in part, on the philosophy that no action should be taken towards the generation of the true sum bit at any stage until the true carry into that stage is present, The carry lookahead and carry skip logics were means to propagate the carries as fast as possible so that the sum bit could be formed in the shortest time possible (or desired). The question now arises as to whether the true carry must be present in order for the true sum bit to be generated. Answer: it must. However, in a binary adder, there are but two possible carries into any bit position or group of bits: a '1' or a '0' . So there is no reason not to construct an adder which generates sums subject to the conditions that a carry is and is not input to each stage or group. The true sum can then be selected "later", when the true carry, be it a '1' or a '0', comes along. Hence, the conditional sum or carry select adder results. 6.1 Basic Theory and Logic Conditional sum addition was first described in I960 [16]. It is based on the computation of "conditional" sums and carries which result from all possible distributions of input carries for various bit positions. Each bit position of the adder generates a sum bit and a carry bit under the assumption that there is a carry into that position, and another sum and carry bit under the opposite assumption that there is no carry input. Then pairs of conditional sums and carries are combined assuming there is (and is not) a carry into that pair of bits. This process continues until the true sum results. Figure I3 illustrates this process, with a forced input carry, C , of '0'. Since the carry input to the low order position is known, the true sum can be formed. -30- -31- X Y 1 10 1 1 1 1 1 1 ASSUMED INITIAL CARRY TIME INTERVAL Cy 1 i 1 1 1 10 1 1 10 1 ¥: 1 10 1 1 1 f, Cn Sy Cy 1 1 10 10 1 10 1 10 1 1 "^2 Sy Cy 1 1 1 10 1 1 ^3 TRUE SUM TRUE CARRY 1 1 1 ■^4 X CARRY INPUT IS KNOWN TO BE '0' SO THIS DOES NOT NEED TO BE COMPUTED FIGURE 13. EXAMPLE OF ONE METHOD OF CONDITIONAL SUM ADDITION -32- The relations are the sums and carries out of each bit position are ^Ni -\®\ S(i+1) - \ ^i El Ni Ni n . = X. ^ Y. El 1 1 for '0' carry input for '1' carry input where the subscripts N and E indicate no carry input and an input carry (exists)^ respectively. The first row sums and carries are generated according to the above relations. The second (t ) and succeeding rows are formed similarly with the right-hand member of each pair (group) using an assiomed input carry (no carry) and the left-hand member(s) using the output carry of the right-hand member(s) from the row above. The process continues until all stages have been paired and re-paired until the true sum is output. The details will become clearer as the reader studies Figure 13. Sklansky [17] has a more detailed explanation with illustrations. 6.2 Improved Conditional Sum Logic The above method of generating conditional sums is not particularly attractive for use in a high-speed system since it is limited in speed to two delays per row. A UO-bit adder would need, therefore, about 1^ delays to complete an addition. Also, the logical structure is, perhaps, somewhat more complex than is desirable. The adder of Section 6,1 is further limited in size and speed by the fanout of the logical elements used. A version which does not need high fanout logic, though it may be slower than that of Section 6.1, employs the ripple carry adder of Section 2. -33- In this case^ the adder system is divided into groups of from 3 to 6 bits each. Each group contains two identical ripple carry adder sections „ If the groups are assumed to be h bits long, then one ripple carry- adder section forms the sums S through S , (input carry assumed 'l')» and El EU the other, similar section forms S through S , (input carry assumed '0'). Simultaneously with carry propagation within the group, two output carries, C and C , are produced using lookahead principles. While carries are rippling through the adders internal to each group, the conditional carries are rippling between groups, forming the true input carries to each group. The conditional output carries from every group are combined with carries from all preceding groups. The forced carry, C , is the input to the low order group. These true input carries and their complements, in turn, are routed to the output select gate which selects the proper sum bit group, S or S , and causes it to be gated out of the adder system via the output select gate. Figure 1^ gives the logic for one of the ^bit groups described above. The true carries are formed according to C. - C ^ C„. C. , 1 Uj_ El 1-4 C. I - C^w . I N ^ C^/. I X C., etc. 1+4 N(i+^) E(i+4) 1^ Two versions of the conditional sum adder logic are given: ripple through and lookahead (Figure 15 ) « The ripple carry propagate realization is slower, but requires a lower fanin/fanout from the elements than does the lookahead version, which also requires more hardware. The basic adder group {k bits) for the conditional sum adder is shown in Figure lU. Complete circuit duplication is not necessary since both the S_, and S^^ adder sections utilize the same primary functions: E JM •3Ji- tvj z CO z o H o UJ -• CO C/) >- , q: ^ tt: < < 2: <\J CO t UJ Q _J Z Q. Q. ^ E uJ t CO m z 1 CO ^ => o z o o UJ o UJ or S2 ■35- ^4 ^Nl ^N4 Cj ,Cj ARE COMMON TO ALL BITS IN A GROUP FIGURE 15 a. OUTPUT SELECT GATE (OG) ONE PER BIT '12 FIGURE 15b. RIPPLE THROUGH TRUE CARRY SELECTION LOGIC FIGURE I5C. LOOKAHEAD TRUE CARRY SELECTION LOGIC -36- X©Y and X • Y. In this ripple carry version, the carry out of stage h is given by: C = X) -^ Y, for an assiomed input carry of '1' (S generation) C = X, • Y, for an assumed input carry of '0' (S generation) Figure l6 presents the block logic for a UO-bit carry lookahead conditicnal sum adder. This particular realization uses ripple carry in the sum generation blocks and carry lookahead over sections of three groups each for true carry generation. If straight ripple carry logic were used (Figure 15t)) for true carry selection, 25 delays would be necessary to generate and propagate the carries. The conditional sums, however, are all ready after only eight delays. If the carry lookahead logic (Figure 15c) is employed rather than ripple carry logic (retaining carry ripple between sections), the true carry propagation time can be reduced to 13 delays. Two fiorther delays are necessary for siim selection in the output gates (OG in Figiire 15a). Using the ripple and lookahead carry logic as described above in the adder of Figure l6, an adder is obtained which will complete an addition in 15 delays. However, a 75 per cent increase in hardware over the ripple carry adder is needed. One of the "secrets" of conditional sum adder logic is the matching of the sum production and true carry propagation times. The example given in Figure l6 did not achieve this match, but a closer match could be realized by utilizing full-carry lookahead for the carry propagation logic in place of partial lookahead. .>x: -37- >b lO , X (D •lO ^ ■cn >'^ pj ro X •<7) CJ X CO •«o 00 PJ X ■in >v >1p CM X 'n X to >f- , 'ro >^ X ■jO , X CJ >^ , CJ X X 00 X X X o 1 o 1 o C/) ) *" (3 O o cn i ) [ CD o C/) ( ) 1 C^ c o o CO ) i C CD O [ C3 cn I CT CD O CD cn I . 1 1 r o CD cn 1 CT C CD O " ' CD CO I , cr c- CD O" o CO ( 1 - CT C O O" cn \ ] 1 CT C i ^ in in h o _ _ * CO UJ UJ UJ t^ oc cr CE CO 3 o 3 CD CD CD U. U. U. <0 LU UJ hi CO UJ UJ 111 cn cn cn 'to ro CO (M to CO < UJ o 1- o UJ cn UJ H CJ _J (ll < CD cn UJ cn o K > 3 (r Q- CO 2 or H =) - o cc < 1 Q o < ^ LU X < ^ o CD o _l LiJ (.0 or ■z. 3 77. CD CO fc -38- 6.3 Further Speed Increases It was seen above how the use of carry lookahead in the true carry propagation logic reduced the add time from 25 to 15 delays. But the version given there uses ripple carry in the U-bit sum groups. One could therefore suppose that introducing full carry lookahead into the conditional sum generating groups and full carry lookahead into the true carry propagation path would yield a further increase in speed. This is the case; however^ the increase in speed obtained may not justify the extra hardware needed. Figure 17 presents the logic of a U-bit conditional sum group with full carry lookahead. The sums and output carries from this group are generated according to the equations Sj,3 = X3 e Y^ © G^ Se3 = X3©Y3 0T^' Sj2 =X2©^2©<°3"^3 ''O where ^Nl = \A. •39- UJ Q Q < CO < < O X p < < Z) O _l q: _j UJ q: ID U. fl: :t _i -40- If NMD logic is assiimed, four delays are necessary to form the conditional output carries, C^. and C^,. , and two more are needed to propagate them ^ •'El Ni' to the output gates and form the true carries everywhere in the adder. S\am generation takes five delays. After two further delays needed to combine the sums and carries in the output select gates, the addition is complete within eight delays. The price for this speed is high compared to other addition methods: an 88 per cent increase in hardware over the ripple carry adder. The conditional sum adder with full— carry lookahead is not the same as a single sum adder with full lookahead logic. The lookahead adder waits for the true carry to arrive before it outputs a sum bit. The conditional sum adder does not concern itself with carries when forming the sum bits -- sums and carries are formed simultaneously, and on the basis of the decoded carries, the proper set of sum bits is selected. A theoretical delay total of eight is not the ultimate in speed for a conditional sum adder. By changing the form of the expressions for the carry into each bit position, and by using some AND-OR networks in place of NAND cascades (where fanout conditions permit), the add time can be cut to four to six delays. The original expressions for the input carries were °N3 = °3 °E3 = ^i = °U ^ \ So = Gi - T^ Gg - \ Tg G^ ^ T^ Tg T^ G^ ''eO - =1 - T^ Gg - T^ T^ Gj ^ T^ Tg T^ T^ -Ul- If the complements of the carries are formed, this results in the following expressions % = % E3 k h So = °i \ - °i % ^2 - °i "^a S '3 " '1 "2 S \ So = °1 \ - °1 °2 ^2 - h «S S ^3 " "1 °2 °3 °U "^i which are simpler than the original expressions (one fewer term than before) and faster in formation, since, using NANDS, the function G = XY = XY = X ^ Y takes two NMDS to form, but G needs only one. Also, an AND-OR-INVERT cascade is often faster than an INVERT-INVERT cascade. Another two delays can be saved in the output gate, by using an AND-OR complex in place of the NANDS, and one in the true carry lookahead/propagation logic. In its ultimate form, the conditional sum adder with full-carry lookahead needs four NAND delays plus three AND-OR delays to form and output the sum. The speed-limiting factor is the driver fanout and gate fanin capacity, since as the adder size increases, these limits are quickly attained. For a driver fanout capability of 18, 2U bits is the maximiom length of the adder which can be constructed within the framework outlined above. However, the true carry out of the last stage can be used as the input to another section of up to 2U bits, with one additional delay. The use of the AND-OR in place of NANDS will realize a hardware savings and will probably give a speed increase as a bonus. i ' _U2- 6 Jk Conditional Siim Adder Siaininary The conditional sum adder is the fastest of the fixed-time adders; it is also the most expensive in terms of the number of components used. Its add time is independent of number length to the limits of hardware fanout capability. The conditional sum addition method is a powerful scheme which should not be overlooked by the designer. 7, THE ASYNCHRONOUS ADDER This section introduces, and concludes, the discussion of asynchronous (speed-independent or variable-time) adders. Previous sections have covered fixed— time addition methods, so designated because a fixed interval of time is allotted for each addition. In the fixed-time adder, even if the addition is completed long before the allotted time has elapsed, the full time is taken to allow for the worst-case conditions. The variable-time adder takes advantage of the fact that, in a ripple carry adder in particular, the addition may be completed before the worst-case add time elapses, 7.1 Principles of Operation The worst-case add time condition in a ripple carry adder occurs when a carry injected into the lowest-order position ripples completely through to the highest-order position, A fixed-time adder must allow for this case on every addition even though the average carry propagation path length is about log„n positions, where n is the adder length. For example, in a ^O-bit adder, the average carry length is 5=6 stages. This carry path length is seen to be short compared to the adder length. The asynchronous adder uses this fact and achieves its speed by detecting the end of carry propagation. When the carry ripple completion is detected, the adder outputs a "done" signal signifying the completion. One of the problems associated with this method is in insuring that the "done" signal is not transmitted until the addition is truly complete. Also, the "done" signal should be removed if any of the inputs is changed during an addition. The above problems can be overcome if two carry propagation lines, rather than one are used -- one for the 'one' or true carry signal; the other for the 'zero' or no carry signal. These lines both rest in the '0' state. 1 ■k3- When an addition is performed, "I's" will propagate down the 'one' and 'zero' carry lines according to the expressions: c} = X. Y. ^ (X. ^^ Y. ) C. , 1 111 1 1+1 c° = X . ~. ^ (T. ^~. ) c. , 1 111 1 1+1 where C is the 'one' carry and C. the 'zero' carry out of stags i. The i 1 expression for the 'done' (addition complete) or reply signal may be written as R= (C^-C°)(C^v.c°)(...)(C^^/C°) When the addition is complete, exactly one of the two lines out of every stage will be '1'. If the state of all C.'s and C.'s is sensed, the addition will be finished when exactly one of each pair {(C^, C) : i - 1, 2, ..., n) 1' 'i is simultaneously in the '1' state. The C. signal may be thought of as meaning "no true carry can be propagated through this stage now. nor will one originate here." 7.2 Asynchronous Carry Logic The truth table of Figure l8a will enable the determination of the carry logic. The carry out is determined by C. or by X. and Y. . The in 1 1 carry logic used in the fixed-time ripple carry adder is given in Figure l8b. This circuit is incapable of providing a "done" signal because there is only one carry path, and an input of X. = Y. = '0' will cause an output of zero, which is exactly what is not wanted. •■'X<^" -^5- 1 r C|N X Y CouT 1 1 1 1 1 1 1 1 DETERMINED BY C|N DETERMINED 1 ONLY BY 1 1 1 1 1 1 1 X SY- NOT C|^, FIGURE 18a. TRUTH TABLE FOR ASYNCHRONOUS ADDER CARRY DETERMINATION 'OUT FIGURE 18b. STANDARD RIPPLE CARRY LOGIC Cqut* KX ^OUT X, Y, FIGURE ISC. LOGIC FOR CARRY PROPAGATION IN ASYNCHRONOUS ADDER -h6- Flgure l8c shows a carry logic which is self -timing since it provides both a 'one'- and a 'zero'- carry path. Both carry paths rest at '0' at the start of an addition. When X and Y are input, one of two conditions is impressed on each carry line at each stage: (1) A 'one' or a 'zero' carry is Injected and the 'zero' or 'one' carry path is blocked, corresponding to X. • Y. and X. * Y. inputs respectively; or (2) An input 'one' or 'zero' carry is allowed to propagate through the stage, corresponding to X. ^ Y. and X. ^ Y. inputs respectivelyo The input 'one' and 'zero' carries propagate along their corresponding paths until they are blocked by a carry injected into the opposite path. After propagating through log n stages on the average, the carry sequence is finished, and a '1' is output from every end-condition OR circuit (D , .., D ; Figure l8c) to the n-input carry completion AND gate. When all inputs to this AND go to '1', the output follows, signalling the completion of the addition. (All carry sequences start at the same time.) If any input changes state during the addition, the carry paths will be affected and the carry completion signal will fall to '0' until equilibri\am is again established. 7.3 Self -Timing Adder Stage The adder of Figure 11 may be used in the variable-time adder with little modification. Figure I9 presents the logic, using NANDS, for one stage of the self -timing adder. It is identical to that of the ripple carry adder except for the addition of three NANDS per stage and the n- input (for an n-bit adder) NAND for carry detection. '^ XY / / N.Vt*'^' N INPUTS -U7- X, Y, X. Y XvY XvY X®Y -n A A Hr*Si IN IN i ! FIGURE 19. ONE STAGE OF ASYNCHRONOUS ADDER USING NANDS -U8- In this example, the carry lines rest at '1' rather than '0' as described above. This is good since this enables the NAND connected to the C and C lines to function as a negative OR. When one of its inputs goes to '0', signifying a true carry on the other line, the NMD's output will rise to 'I'o When the outputs of all such NMDS are '1', the output of the n-input NAND will fall to '0% thus indicating the completion of the addition, A 40-bit self -timing adder may be constructed using about 3^ per cent more NANDS than the ripple carry adder. Its speed of operation will vary between a minimum of four delays to a maximum of 82 as compared with 80 delays for a ^0-bit ripple carry adder » The average time required will be about l6 delays » 7.U Variable-Time Adder Summary Nothing in general may be said about whether a fixed- or variable-time adder is better. The choice of one type or the other depends on the features of the system in which the adder is to be used. If the system will allow a wide spread between average and maximum operation times, the asynchronous adder may suffice. If, however, high-speed operation is essential, or strict timing delays required, then the choice of a fixed- time adder is indicated. As one might think, the asynchronous adder is not too suitable for use in a synchronous machine since it operates as "fast" or as "slow" as necessary, sending out a "done" signal whenever the addition is complete. •■■iSj" 8, SEPARATE CARRY-STORAGE ADDER The adder to be discussed here is not a true adder in the sense of those of Sections 2 through 7, This is a "pseudo-adder," forming partial sums and carries from three inputs: X, Y, and the previous carries, and storing the output sum and carries separately. No attempt is made to propagate carries through the adder -- the carries are only absorbed one stage higher than the stage in which they were generated. 8ol Principles of Operation The purpose of the carry-storage adder is to form a pseudo-sum and carry as quickly as possible (in a fixed— time) and then store them in separate registers. Figure 20a shows the register arrangement in which an "ordinary" adder would function. Figure 20b gives the layout for a carry- storage adder system. In ordinary adders, the contents of the X and Y registers are added one way or another and the sum is placed in the S-register. In the carry- storage adder, the contents of the X and Y registers are combined on the first cycle, the pseudo-siim is placed in the S-register, and the carries (b. ), out of each position are stored in the B register. The pseudo-sum and carries are then gated to the X and C registers (they may also be shifted left or right in transit). On the second and succeeding cycles, the contents of the X, Y, and C registers are combined to form new pseudo-sums and carries. During the final addition, the carries must be propagated through the adder in order to produce the true sum in S. For this carry assimilation, any of the methods of Sections 2 through 7 inay be used. The carry-storage adder by itself does not have the power to assimilate carries; external circuitry is required for this. ^ •k9- ■ 50- S: SUM ADDER FIGURE 20a. "ORDINARY" ADDER REGISTER ARRANGEMENT X: S: SUM/PSEUDO-SUM 1 CARRY PSEUDO-ADDER 1 1 T X/PSEUDO-SUM CARRY FIGURE 20b. CARRY- STORAGE "PSEUDO- ADDER" REGISTER LAYOUT -51- It has been shown [13], that additions, multiplications, etc. can be performed in a consistent fashion using separate stored carries. 8.2 Adder Logic The adder itself is exactly the same as the ripple carry adder, with but a single modification. The carry propagation chain is broken at the output of each bit position so that the carry produced there might be stored. There are two places at which the carry chain may be cut: points A and B in Figure 21a. Although the choice is not obvious, the following reasoning supports the choice of point B. Let U. - X. © Y. 1 1 ^^ 1 K. = X. ' Y. , ^ b. 1 1+1 1+1 1 where K. is the carry into bit position i and b. is defined below. Then S. = U. ©K. = (X. QY.) . b. ^/ X. . Y. 1 i^-^i i^^i 1 1 1 and b. , =: U. • K. = X. • Y. 1-1 11 11 where S. is the pseudo-sum digit and b is part of the carry out of stage i . Note that S. • b. , =: (U. ©K.) . U..K. = 1 1-1 1 ^^ 1 1 1 and X. ' Y. - b. , = 1 1 1-1 ■52- X, Y, ^l+l '"'i + l A ® A B : C: , ■ - M A B; 'i + l Si i-fl FIGURE 210. LOGICAL STRUCTURE OF CONVENTIONAL ADDER FIGURE 21b. CARRY -SAVE ADDER LOGIC -53- so both S. and b. cannot both be ones simultaneously. For this reason, point B is chosen as the break point. The function b is the controlling expression for this point in the carry path. The fact that S. ■ b. =0 will simplify expressions for the sum digit. Since S. becomes the X. for the next addition, this relation will hold if b. is stored rather than propagated. The stored b. will appear as c during the next addition. Figure 21b shows the logic for two stages of a separate carry-storage adder. Its pseudo-addition time is a fixed four delays (using NANDS), For carry-assimilation, it is assumed that an adder with the structure of Figure 21a is needed with inputs X. and C., with internal (ripple) carry d. , and sum digit output S. , From the relation S. » b. ^ = i' 1 11-1 given above, and other relations derived from it, it can be shown [13] that the carry-assimilation equations become i'. ; I S. =: X. © (c. ^ d.) d. , = X. » (c. ^ d. ) 1-1 111 The adder of Figure 21b can be employed to form the sum digits if the d. in the above equation are generated first. To use the adder, the Y. inputs to the AND circuits are set to zero; and the Y. inputs to the EXCLUSIVE OR circuits are set equivalent to d. •> c. . The equation for 11 S. then beomes 1 or S. - X. 0T. © (X. • Y. , ^ C.) 1 1 ^^ 1 ^-^ 1+1 1+1 1 S. = X. 0d.. C. ©C. 1 1 ^^ 1 1 1 which can be simplified to .5U- 5. = X. ©d. ©c. .: X.0(d. - c.) also. d. , - X. * (c. ^ d.) 1-1 11 1 The carry propagation implied by the last recursion relation may be speeded up by any of the techniques of Sections 3 through 7. There is no way the add time of the basic carry storage adder can be decreased by rearranging or adding to the logic. It can only operate faster through the use of faster circuit elements. It uses exactly the same number of components as the ripple carry adder^ exclusive of carry propagation logic and the extra registers needed. It "adds" in as short a time as is logically possible. 8, 3 Summary The carry-save adder finds its major application in machines with operations in which a large number of additions are performed in series, without an intervening store order which would require the assimilation of carries. Such an operation is multiplication, which may require n additions with an n-bit number. Using a carry-save adder reduces the add time, and, hence, the multiply time to a minimum, since the pseudo-addition amounts to little more than a data-transfer between the X, Y and C registers and the S and B registers. The adder is, however, rather unhandy to use for a single addition requiring carry-assimilation. The separate carry-storage adder, when used in the proper manner, will give high-speed addition at minimal cost. 9, SUMMARY OF ADDER-TYPES The one-position binary full adder was initially introduced. This basic building-block was then employed in the logical construction of an n-bit ripple carry adder, the first type of adder used in electronic computers . It was seen that the time required for carry propagation in the ripple carry adder is excessive (2n delays for an n-bit adder) compared with the time necessary for sum generation (four delays) in each bit position. Means for reducing this propagation time were then presented. One of the first ways devised for speeding carries on their way was by using lookahead logic „ In this method, each bit position "looks ahead" to lower-ordered positions to see what the carry into it will be, and then forms the sum bit accordingly. By varying the complexity and "reach" of the lookahead logic, in combination with ripple carry logic, the carry lookahead adder can be made as fast as desired, with a limit of eight delays being the maximum speed of operation attainable. Closely resembling the lookahead adder is the carry skip adder. This method uses signals from each bit position in a group to enable an input carry to "skip" around the group, if conditions are such that the carry would otherwise propagate through. If the carry is not "skipped" around the group, it ripples through until it is absorbed. As the complexity of the skip logic increases, the adder looks more and more like a lookahead adder, until, in the limit, both adder types are almost identical. The conditional sum adder takes a new approach to addition. This adder cares not what the input carry to a group of bits will be, but generates two sum groups and two output carries from the group. -55- -56- The proper s\im and carry bits are then selected vhen the true input carry- becomes known. By using lookahead techniques within and between the groups^ the conditional sum adder's speed can be increased to a maximum of five NAND delays plus the delays of three MD-OR cascades. This adder^ one of the fastest available, does not degenerate into another adder type when full carry lookahead is used. The above mentioned adders are all fixed-time adders, i.e., they complete their additions within a predetermined, invariant period of time. The asynchronous adder, a variable-time device, knows no fixed limits for add time. This adder takes advantage of the fact that the average maximun! ripple carry length is less than log^n positions for an n-bit number. The carry propagation path is monitored during addition, and when carry propagation is completed, regardless of time consumed, an "addition completed" signal is generated and sent to the control logic. This adder type uses no carry speed-up logic. It works best, as one might suspect, in an asynchronous, or speed-independent system. In a clocked, or synchronous system^ or where a tight bound on add tirre is required, the use of the asynchronous adder may well be questioned. The last adder variant mentioned, the carry-save or separate carry-storage adder, is not a true adder since the carries generated in each bit position are not immediately assimilated as in other adder types, but are stored separately from the pseudo-sum. This adder finds use when a long sequence of additions must take place without the necessity for carry propagation. When carry assimilation becomes necessary, any of the above techniques may be used to speed up the process. 9.1 Adder Design Notes When the designer approaches the problem of selecting and designing an adder for operation in a given system, he must consider many -57- factors before making the final choice. Some things to take notice of are a) Number of adder stages needed^ i.e., what is the word length? b) Speed of the system. Must the adder complete its job quickly^ or would a ripple carry adder prove adequate? c) System timing. Is it synchronous (clocked) or asynchronous? d) Circuit availability and capability. What types of circuits are available for use? What are the circuits' fanin and fanout limitations and their speed of operation? e) Number representation. Will numbers be represented internal to the system in two's complement, BCD code, floating point, etc.? f) Register arrangement. How many and what types of registers and gating logic are available for the adder to use? g) Multiple adders. Two different types of adders may be justified if large numbers of additions as well as many multiplications are anticipated. I p; 1 1 1 1 9.2 Future What does the future hold for adders in terms of speed and logical advances? Present adders can be quite complex as one can see by looking at the conditional sum adder. A radix-3 adder has been described [l^]. This is another approach to addition, although it is of little use in a binary system. Perhaps future speed increases will be realized only through the development of multi -state and faster- operating devices. -58- Ten years ago the add time barrier -- the time needed to / -9 \ complete an addition -- was around 100 nsec (100 x 10 sec.j. Today- it is of the order of 10 nsec. This barrier can be penetrated today only through the use of "exotic" devices. An 8-bit ripple carry adder using very high-speed transistors and tunnel diodes has been constructed [l] which can produce the correct sum output in 3 to 5 nsec. With special devices and higher density packaging, the ripple carry delay per stage can be reduced to 0.2 nsec or less. A -&► Z = A V B A B Z 1 1 1 1 1 1 1 : I EXCLUSIVE OR: EQUIVALENCE: NOT: JS> "V, ^ w- ~T>- Z = A 0B Z = A 0B A B z 1 1 A B z 1 1 1 1 1 1 Z = A -59- A z 1 1 -60- NAND: 32)— Z = A A B Z 1 1 1 1 1 1 1 APPENDIX 2. HARDWARE AND TIMING COMPARISONS The chart on the following page gives a comparison between modifications of the various adder types and the ripple carry adder. Each adder was designed using only NAND circuits with no limitations on fanin or fanout. Each NAND is assumed to have a time delay of one unit^ regardless of its loading. Many NANDs are counted in the chart which do not appear in the logic drawings when a reference to a figure is given. The number of inputs to the NANDs is an indication of the number of logic diodes needed, while the coiont of NANDs gives an idea of the number of transistors or tubes necessary to construct the adder. The chart gives the impression that the carry skip adder yields the greatest speed increase for the smallest additional cost. This is possibly true if NAND circuits alone are used. However, if AND-OR circuits are used, the "cost" of the conditional sum adder (as well as other types) will be greatly reduced with an accompanying increase in speed. The numbers on the chart should be taken only as an indication of the relative costs and speeds of the various adder types since these factors will vary widely depending on the detailed logical structure of the adder and especially on the characteristics of the circuit elements used. -61- OJ w CO (L) t3 0) ^ r-l >> ^ QJ Sh (U ft ?H 01 0) CJ > ft ?H •n ft G o •H CD ^ CO •H J^ CJ a U CO CL) l>5 o X2 Ch CD X O ,H CD •^ 0) s s O m K (U H w Q CD ^ (D Q 0) 0) rH >> ?H < ^1 > ft ^ 0) ^ o o ft ^ Td Eh c •H CD ^ M •H ^ O CD m o iH u W fc rH 0) -P o CD -2 Ch 1:3 +J S O ft CO O ^ G w ^ S M Qh >-> EH (U CO w p CD ^ 0) o QJ H >. ^ M U > ft u (D K ^ a o ft u ■X? < G ■H CD ^ > •H ^ U CD K O ^ tn rH M (D CO CO CO ^ Ch Q s -p S O S o o ;ii < CO EH S S 1— 1 K S o o w K < t3 ^2 c Q CO K -P ^ 0) ft >3 CO •H Q EH U W CO w ^^ > p^ (D CO 'C! T3 <; O CO O VD O VD -cf fcfl •rH no C\J o o o On oo O O X3 I 43 LTA CD fe O — - CD T3 (D CD rH ftl CD 0; ft 4:: ft CO -H O O rH CO H US rH O ■a u O CO 00 o C\J I^ UA CVI VD •H cvj OJ on o^ o (D 01 -P 0> a CO CO ft '^ o • +J M -H •H ^ P^ I - — -:t >i u u CO 13 CJ CO OJ 01 ^ ,-\ >^ CD ft U X ft u •H CD K ij o o 1>- -ct- o Cv-^ CO §^ O •H ^^ ^ •H -p. a ^( iri CO O u • u CO (U rH ft ft ■H ft ^ -H CO ^ CD CO VD CVI 0^ VD VD 00 GO VD. O) CO ft • ft b£ ■H -H CO C ft -H Ml CO O U bD 0) ISl •H CO 00 J- CM CVJ o rH CJn O CM a\ •H ^ 0> -P rH •H ft > ft ■H ft ?H •H ^ -^ CO CO ft !h O U U CD M O -P rH -H rH ^ ;3 I ■H o CO fti+J •H :2 CVJ rH UA UA CO -P ■H I o u W ft O S OJ CD 'a CO CO ' PJ tiD pi •H (in ft •H 02 !>> U U CO O VD ro CVI CVJ rH r-{ CVJ rH -J- t— CO OJ VD r-\ -P CO -H C X3 ?H 1 o> J- +J - — ^ G -4- •H C r-{ 0) >> 01 • ?H > t>D ^ 4^ •H CO 01 PiH X2 ^— ' cu t:3 CO rH a ft ft CD ^ ft •H U K -P M 00 CJ\ CO o CJ\ UA LTN o VD CD r-\ CU •H CO >-5 o u CD O +J •H 0> X2 rH I ftJ- ft •H O CO ft o OJ 0) 0) X5 r^ ,— CD vo 01 rH CD O -H O P-H M CO VD O C7\ VD CO CO o 00 •H VD 43 rH I ■ri -d- 'C! CO G O) C CD ^ 01 CD CU CVJ 4^ :3 rH O -P O (D ° rH 43 CO >J T3 -H ^ G Ph ^ CO w CD (J C CO •H p. rH 4:1 lilS H -P O Hi -H O CO OJ o -p O o -62- rj 0) (u 5-1 'Ci OJ > r— I S cu OJ ?H O Pi ^ --Ci Ph fn 'X3 ■H CO CD (U CJ ^- (L) H CD CO (U O Ph ^ CD Pi ^ T3! •H CD rp 5h O CD a) O O CJ fl X •H CO e E -^ OJ CO iH OJ CD Xi -P S o 3 ^^ c/j ■P 1^ Pi a; H >. ^ Ph Jh CU Pi ?H T3 ■rH CO T3 ^ O CD O OJ CO o s ^ f.^ CD -p OJ G P^ CD >^ •H H ^ CD ^ > (D TJ ^ <; m H cX) 03 pi O o CJ c/j QJ -H rO -p CD ^1 +J CD Pi ^ OJ O O O 0) CD ^ +J (L) P ill (U CD is ^ -P a> P w o O fi S <; P s o ^1 o 0) rH ;5 OJ CfH CD U P P (U •H t>0 Xi P •H bO CD W -H Ch CD X, ^ 'P CD OJ H CD OJ ;j ^ > C/J -P QJ CD O -H CO CD ^ O CD P CD CD < > ^ P -P • CD •H OJ CD "v •N CD CfJ CD O -P P 1 P (U -P P^ ^ CD P S ?H -H P o P > p 0) (U (u :s CD P 0) (U CD Ch ^ -P P nd (D P w > CD p •■^ ^ •H bO a? P D •H CD -p CO (U CO -P P o X3 P -H o biJ -P •H P p P^ -H H I I ! I H CM -63- BIBLIOGRAPHY [1] [2] [3] [5] [6] [?] [8] [9] [10] [11] [12] [13] Amodei, J,, "High-Speed Adders and Comparators Using Transistors and Tunnel Diodes/' IEEE Transactions on Electronic Computers , EC-6, October 196k, pp. 563-575- Beckman, A,, "Developments in the Logical Organization of Computer Arithmetic and Control Units/' Proceedings of the IRE , h^, January I961, pp, 60-66. Bedrij^ 0. J., "Carry Select Adder/' IRE Transactions on Electronic Computers , EC-11, JuJie I962, pp. 3^0-3^6. Burks^ A. W., H. Goldstine, and J. Von Neumann, " Preliminary Discussion of the Logical Design of an Electronic Computing Instrument/' The Institute for Advanced Study, Princeton, New Jersey, 19^7. Flores, Ivan, The Logic of Computer Arithmetic , Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 19o3;. PP^ 70-119. Gilchrist, B„, J. H, Pomerene, and S. Y. Wong, "Fast Carry Logic for Digital Computers," IRE Transactions on Electronic Computers , EC-U, December 1955, PP- 133-13^0 Hendrickson, H. C, "Fast High-Accioracy Binary Parallel Addition," IRE Transactions on Electronic Computers , EC-9, December I960, pp. U65-U66, Hsiao, M., "The Carry-Dependent Sum Adder," IEEE Transactions on Electronic Computers , EC-12, June I963, pp. 265-268. Lehman, M, and N. Burla, "Skip Techniques for High-Speed Carry- Propagation in Binary Arithmetic Units," IRE Transactions on Electronic Computers , EC-10, December I961, pp. 691- MacSorley, 0. L., "High Speed Arithmetic in Binary Computers," Proceedings of the IRE , U9, January I961, pp. 67-7I. Metze, G., "A Binary, Parallel, Asynchronous Arithmetic Unit with Separate Carry or Borrow Storage," Department of Computer Science, University of Illinois, Urbana, Illinois 61803, File No, 22^, July 1957. (Presented at the 12th National Meeting of the ACM, Houston, Texas.) Morgan, C. and D. Jarvis , "Transistor Logic Using Current Switching and Routing Techniques and Its Application to a Fast-Carry Propagation Adder," Proceedings of the lEE , Pt. B, IO6, September 1959, pp. h6j-h68. Robertson, J. E,, "Theory of Computer Arithmetic Employed in the Design of the New Computer at the University of Illinois," Department of Computer Science, University of Illinois, Urbana, Illinois 61803, File No. 319, June I960. -6k- -65- [lU] Rozmarich, T. A.^ "Synthesis of Three-Level Logic Circuits with Application to a Radix Three Computer Arithmetic Unit," Department of Computer Science, University of Illinois, Urbana, Illinois 61803, Report No, I81, June I965 , [15] Salter, Forrest, "High-Speed Transistorized Adder for a Digital Computer," IRE Transactions on Electronic Computers , EC-9^ December I960, p. ^61. [16 [IT [18] Weinberger, A. and J. Smith, "A One Microsecond Adder Using One Megacycle Circuitry," IRE Transactions on Electronic Computers , EC-5, June I956, pp. 65-73= Sklansky, J,, "Conditional Sum Addition Logic," IRE Transactions on Electronic Computers , EC-9, June I960, pp.. 226-231. , "Ultimate- Speed Adders," IEEE Transactions on Electronic Computers , EC-12, April I963, pp„ 1^2-lU8. 11 I(tf N .,„,., .UiiiiikUniikit^Hi.iniiiiHiiiiW^ w »ry<««ww»M»a«B»atraiii»5»nHff-*im»ton ii; ■;in>MMHf ror/o»nrniHi»JiM;]<>"^^' -'^^*==1 Aimj6L£i.iittnmimKMt 'iiatafMttnstiemsMMsiisat*tfiinfitmmiSH'aun^uii\tuiibiniW(iuWw:',iu^ m«t2««i111f mrnmmmm I'j'iK-.** ; ;,! ?»,')!? ""^^ OF ILUNOW-URBAN* 30112103707086