"L I B RAR.Y 
 
 OF THE 
 U N IVLRSITY 
 Of ILLINOIS 
 
 510. 84 
 »o. 271-278 
 
 cop. 2 
 
 « ».' * 
 
The person charging this material is re- 
 sponsible for its return to the library from 
 which it was withdrawn 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 
 
 HOV 22 13* 
 JAN 2 8 1982 
 
 L161 — O-1096 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/logicaldesignofc275boro 
 
M ' ^ Report No. 275 
 up*- 
 
 COO-1018-1152 
 
 THE LOGICAL DESIGN OF A CLASS OF 
 LIMITED CARRY-BORROW PROPAGATION ADDERS* 
 
 by 
 
 Richard T. Borovec 
 
 August 1, I968 
 
Report No. 275 
 
 THE LOGICAL DESIGN OF A CLASS OF 
 LIMITED CARRY-BO KROW PROPAGATION ADDERS* 
 
 by 
 
 Richard T. Borovec 
 
 August 1, 1968 
 
 Department of Computer Science 
 University of Illinois 
 Urbana, Illinois 618OI 
 
 *This work was supported in part by the National Science Foundation under 
 contract NSF GP-U636 and Contract AT(ll-l)-10l8 with the U.S. Atomic Energy 
 Commission and the Advanced Research Projects Agency, and was submitted in 
 partial fulfillment for the degree of Master of Science in Electrical 
 Engineering, 1968. 
 
Ill 
 ACKNOWLEDGMENT 
 
 The author would like to thank his advisor, Professor J. E. 
 Robertson, for his helpful advice and guidance in the preparation of 
 this thesis. 
 
 The author would also like to thank Miss Colette Portugal 
 for her capable typing and Mr. John Otten for the drawing of the 
 figures in the thesis. 
 
IV 
 
 TABLE OF CONTENTS 
 
 Page 
 
 1. INTRODUCTION 1 
 
 2. DESIGN PROCEDURE 3 
 
 3. NORMALIZED ADDER 7 
 
 k. SYMMETRIC ADDER AND SUBTRACTER 11 
 
 5. COUPLED DON'T CARES 25 
 
 6. SUMMARY 33 
 
 LIST OF REFERENCES 35 
 
1 . INTRODUCTION 
 
 It has been recognized for some time (3,5) that one of the 
 ways of increasing the speed of arithmetic operations in a digital 
 computer is to introduce redundancy into the arithmetic unit, i.e. 
 using k digital values in radix r where k > r. Redundancy allows 
 such techniques as multiplier recoding to increase the shift average 
 and the possibility of performing division using a truncated divisor 
 and partial remainder in a model division scheme. 
 
 The arithmetic unit of the Illiac III computer (1,2) uses 
 four redundant subtracters in cascade to perform, effectively, radix 
 256 arithmetic. This means that fewer operations are necessary since 
 larger parts of the operands may be operated on at once. The sub- 
 tracter used in this arithmetic unit, the block diagram of which is 
 shown in Figure 1, allows one redundant input and one conventional 
 input. In Figure 1 an asterisk represents a redundant digit while a 
 variable standing alone represents a conventional digit. 
 
 The basis for this paper is the work by Rohatsch (8) on the 
 algebraic structure of adders and the work by Robertson (6) on the 
 design procedures for redundant adders. 
 
 The purpose of this thesis is to determine the logical 
 structure of a class of redundant adders which allow both the addend 
 and the augend to be expressed redundantly. Rohatsch has shown that 
 such adders must consist of three "levels", i.e. three transformations 
 are necessary to map the input digit set onto the output digit set. 
 
 Numbers in parentheses refer to List of References at the end of the 
 paper. 
 
Two different design procedures were used and these will be discussed 
 in the next chapter. Chapter three will give the results of the 
 designs of the normalized adder; Chapter four the symmetric adder and 
 subtracter. Chapter five will describe a logical design problem, 
 believed to be new, encountered in the design procedure, the problem 
 of coupled don't cares. A systematic method of assigning covers will 
 also be introduced. Finally, the results will be summarized in 
 Chapter six. 
 
 S i-1 
 
 S i+1 
 
 i-1 
 
 b i-2— | 
 
 b i-l 
 
 d. 
 
 1 
 
 TT Tl 
 
 d i+ i 
 
 n 
 
 i+l 
 
 a. n m. , 
 l-l l-l 
 
 a. m. 
 l l 
 
 a i+l m i + l 
 
 Figure 1. Illiac III Signed Digit Subtracter 
 
2. DESIGN PROCEDURE 
 
 The following notation and assumptions will be used for the 
 
 * 
 
 rest of this thesis: i) x. represents a redundant digit while x. rep- 
 resents a conventional digit, ii) numbers with overbars , e.g. 1, 2, 
 etc., are negative numbers while unsigned numbers are positive, iii) 
 all designs to be considered will be radix two devices with minimal 
 redundancy, i.e. a redundant digit will be able to assume one of r + 1 
 or three possible values, and iv) the format for expressing the input 
 digits will be the same as the format for expressing the output digits. 
 This is the most interesting case as it allows the output to be used 
 as an input; a property useful in the implementation of recursive 
 processes such as multiplication and division. 
 
 Since the designs under investigation are of radix two with 
 minimal redundancy, two variables, i.e. four states, are necessary to 
 represent the possible values a digit may assume. Robertson (6) has 
 shown that there exist only nine distinct ways , under permutation and 
 negation, to assign three values to four states (two binary digits). 
 This implies that there are nine possible designs for each structure 
 type. 
 
 Two methods of approaching the logical design were used. 
 The first was to recognize that it was possible to add another level 
 to the design for the two level structures which already existed (7). 
 Using Rohatsch's idea this corresponds to an additional transformation 
 from the new digit set (two redundant inputs) to the original digit 
 set (one redundant input, one conventional input). This entailed the 
 design of a box as shown in Figure 2. 
 
* 
 
 a. .. m. 
 l-l 1 
 
 * * 
 
 1. k. 
 i i 
 
 Figure 2 
 
 The inputs to the box at the ith digital position were 
 
 redundant digits 1. and k. while the outputs were a. and m. . The 
 
 * * * 
 
 three redundant digits 1. , k. , and a. ., were of the same format. The 
 
 11 l-l 
 
 outputs of the "box were used as inputs to the existing structures. 
 This design procedure will henceforth he known as procedure A. 
 
 The second procedure, suggested by Robertson (7)» consisted 
 of designing the lower two levels of the adder without considering the 
 format of interstage signals. This design allows two redundant inputs 
 and gives three binary outputs which are format independent. The 
 structure for this procedure is shown in Figure 3. The second pro- 
 cedure, procedure B, uses the top levels of the adders which have been 
 designed. 
 
 The complete structures for procedure A and procedure B are 
 illustrated in Figures h and 5 respectively. 
 
b i-2 d i-l 
 
 m. 
 
 1 
 i 
 
 II i 
 
 n 
 
 m 
 
 i-1 
 
 F? 
 
 1. k. 
 1 i 
 
 Figure 3 
 
 S i+1 
 
 * 
 
 s . 
 
 l 
 
 S i+1 
 
 b i-2*l 
 
 n ji 
 
 -^ 
 
 m 
 
 I r 
 
 d i-i 
 
 Vi 
 
 a i-i 
 
 i 
 
 m. 
 
 i-1 
 
 n 
 
 l. , k. . 
 
 i-l i-l 
 
 i, 
 
 n 
 
 * * 
 
 1. k. 
 
 i i 
 
 I L 
 
 d i + i 
 
 i+l 
 
 a i + l 
 
 m 
 
 i+l 
 
 n 
 
 h+i k i + i 
 
 Figure k. Procedure A Structure 
 
m 
 
 i-1 
 
 In it | 
 
 * * 
 
 1. k. 
 1 1 
 
 * * 
 
 * * 
 
 X i+2 k i+2 
 
 Figure 5- Procedure B Structure 
 
3. NORMALIZED ADDER 
 
 The normalized adder is the first structure to he designed 
 using Robertson's deterministic procedure (6) as it uses the normal- 
 ized digit set {0,1,2}. The adder is defined by the values the 
 
 * # * * 
 
 variables may assume, namely a., 1. , k. , s. {0,1,2}; b., d. , m. {0,1}. 
 
 The format assignments for the adder are given in Table 1. In the 
 designs a Greek letter and a Roman letter are used to denote the first 
 and second variable in the assignment respectively. Thus a. is given 
 
 by a . a . . 
 
 li 
 
 State 
 
 
 
 
 Digital 
 
 Values 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 D.C. 
 
 
 
 
 
 1 
 
 2 
 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 
 2 
 
 D.C. 
 
 
 
 2 
 
 
 
 1 
 
 2 
 
 
 
 
 
 
 
 
 2 
 
 2 
 
 D.C. 
 
 2 
 
 2 
 
 2 
 
 2 
 
 2 
 
 Design 
 Number 
 
 1 
 
 2 
 
 3 
 
 k 
 
 5 
 
 6 
 
 7 
 
 8 
 
 9 
 
 Table 1. Format Assignments for Normalized Adder 
 
 The Boolean equations for design procedure A are given in 
 Table 2. Design procedure B was not used in the case of the normal- 
 ized adder. The use of the normalized adder to perform subtraction 
 is not a trivial matter and thus it was deemed that the other designs 
 (symmetric adder and subtracter) were of more interest. 
 
 In Table 2 designs 2,3,^- and 8 appear to be minimal in 
 that they require the fewest gates to implement. 
 
1. a. _ = A. 1. 
 l-l l l 
 
 a. . = K.k. v (A. © 1. ) (k. n/ k. ) 
 l-l 11 l w l i i 
 
 m. = K.k. © A.l. 
 l 1111 
 
 d. = m. © a. a. 
 
 l ill 
 
 b . n = a.a. v- a. a.m. 
 
 l-l li ill 
 
 a. = b.d. a. = b. © d. 
 
 i 11 i i v ^ i 
 or 
 
 s. = b. © d. s. = b. n/ d. 
 
 i i v_y l i i i 
 
 2. a. . = A.l. K.k. 
 l-l 1111 
 
 a. , = l.k. s/ K.k. n/ A.l. 
 l-l li li li 
 
 m. = A.l. © K.k. 
 l 1111 
 
 d. = m. © a.a. 
 i i w i i 
 
 b. .. = a. ^ a.m. 
 l-l l li 
 
 o. = b.d. 
 i 11 
 
 s. = b. ^ d. 
 
 ill 
 
 3. a. n = A.l. K.k. 
 l-l 1111 
 
 a. n = l.k. ^ K.k. v A.l. 
 l-l 11 11 11 
 
 m. = 7.1. © K.k. 
 
 d. = m. © a. a. 
 l i w l l 
 
 b. ., = a. (a. ^ m. ) 
 l-l li l 
 
 a. = b.d. 
 l li 
 
 s. = b. ^ d. 
 ill 
 
 Table 2. Boolean Equations for Normalized Carry-Save Adders 
 
k. a. - ~ \.k. 
 
 i-I 1 1 
 
 a. , = A. © k. v l.k. 
 i-I i^i 11 
 
 m. = 1. © k. 
 i li 
 
 d. = a. © m. 
 l 11 
 
 b. .. = a. ^ a.m. 
 i-I l li 
 
 a. = b.d. 
 l 11 
 
 s. = b. © d. 
 l li 
 
 5. a. ., = A.l.K.k. ^ 1.(k. ^ k. ) ^ A.k. 
 i-I 1111 11 l 11 
 
 a. . = l.k. ^ K.k. ^ A.l. 
 i-I 11 11 11 
 
 m. = A. © k. 
 l li 
 
 d. = a. © m. 
 
 i i w l 
 
 b . ., = a. (a. ^ m. ) 
 i-I li l 
 
 a. = b. © d. 
 i l v l 
 
 s. = "b. v d. 
 
 ill 
 
 6. a. , = A.l.K.k. * (k. ^ k .) (A. © 1. ) v A.(<.©k.) 
 i-I 1111 i i 1^1 ill 
 
 a. , = A.l. k .k. 
 i-I 1111 
 
 m. = K.k. © A.l. 
 l l l w l l 
 
 d. = a. © a. © m. 
 
 i l w i w l 
 
 b. ., = a.m. ^ a. a. ^ a.m. 
 i-I li li li 
 
 a. = b. a. = d. 
 
 11 11 
 or 
 
 s . = d. s . = b. 
 
 li li 
 
 Table 2. Boolean Equations for Normalized Carry-Save Adders (Continued) 
 
10 
 
 7- a. . - X.k. 
 i-I i i 
 
 a. ., = X. ss k . \y l.k. 
 i-I l l 11 
 
 m. = T.l. ic.k. 
 i l l w i i 
 
 d. = m. © a. a. 
 
 l ill 
 
 b. _. = a. ^ a.m. 
 i-I l li 
 
 c. = b.d. 
 l 11 
 
 s. - b. v d. 
 
 ill 
 
 8. a. .. = X.1.(k. v k. ) \/ X.K.k. \/ X.l.K.k. 
 i-I ill l ill 1111 
 
 a. n =X.l. or a. , = x.k. 
 i-I i l i-I l i 
 
 m. = X. © k. 
 l i^i 
 
 d. = a. © m. 
 i i w i 
 
 b. . = a. a. ^ a.m. 
 i-I li li 
 
 a. = b. © d. 
 l i N -' i 
 
 s. = b. or s . = d. 
 li li 
 
 9. a. . * (ic.k. © X.l.) n/ <.(k.©X.)^ X.(1.©k.) 
 i-I 1111 ill i i w i 
 
 i. , = ic.k. X.l. v K.k.(X.©l.) v <.X.(k.@l.) 
 i-I 1111 i i i v - / i iii v ^ i 
 
 m. = (ic.k. © X.l. ) v X.l.k. 
 i i i v l i ill 
 
 d. = m. © a. a. 
 
 i ill 
 
 b. ., = a. a. ^ a.m. ^ a. a. 
 
 i-I li li li 
 
 a. = b. © d. a. = b.d. 
 
 i i v ^ i l 11 
 or 
 
 s. = b. ^ d. s. = b. © d. 
 
 i l l l li 
 
 Table 2. Boolean Equations for Normalized Carry-Save Adders (Continued) 
 
11 
 
 k. SYMMETRIC ADDER AND SUBTRACTER 
 
 The symmetric adder and subtracter may be derived from the 
 normalized adder by adding a constant to the input digit set and the 
 output digit set, namely -1. Thus the values which may be assumed by 
 the variables are as follows: 
 
 SYMMETRIC ADDER 
 SYMMETRIC SUBTRACTER 
 
 * * * * 
 
 a., 1., k., s. 
 
 b. , m. 
 i l 
 
 d. 
 
 i 
 
 {1,0,1} 
 
 {0,1} 
 
 {1,0} 
 
 {1,0,1} 
 
 {1,0} 
 
 {0,1} 
 
 The format assignments for the designs are given in Table 3. 
 Tables h and 5 give the Boolean equations for the symmetric adder 
 
 State 
 
 
 
 Digital 
 
 Values 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 D.C. 
 
 
 
 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 l 
 
 1 
 
 1 
 
 1 
 
 1 
 
 D.C. 
 
 
 
 1 
 
 
 
 1 
 
 I 
 
 
 
 
 
 1 1 
 
 
 
 1 
 
 1 
 
 D.C. 
 
 1 
 
 T 
 
 I 
 
 1 
 
 1 
 
 Design 
 Number 
 
 1 
 
 2 
 
 3 
 
 1* 
 
 5 
 
 6 
 
 7 
 
 8 
 
 9 
 
 Table 3. Format Assignments for Symmetric Adder and Subtracter 
 
 procedures A and B. Tables 6 and 7 give the Boolean equations for the 
 symmetric subtracter procedures A and B. 
 
 In Table h designs 2, U, 5 and 7 appear to be minimal in the 
 sense that they use the fewest numbers of gates. Designs 2, k and 5 
 have don't care entries in their format assignments. 
 
 Design 3, however, is probably of the most practical value 
 since it allows digitwise complementation by complementing the first 
 
12 
 
 or sign bit of each digit. Thus, forming the negative value of a 
 number is accomplished simply by complementing the sign bit of every 
 digit. 
 
 In Table 5 designs 2, k and 5 appear to be minimal while in 
 Tables 6 and 7 designs 2, h, 5 and 7 appear to be minimal. Again the 
 same comment about design 3 holds. 
 
 It is interesting to note that in general the results of 
 procedure A are more complicated than those of procedure B. This is 
 due to the constraint that the input and output formats of the box 
 designed in procedure A be the same. 
 
13 
 
 1. a. .. = K.k.l. ^ A.I.k. ^ K.k.A. ^ K.k.l. 
 l-l ill ill ill ill 
 
 a. , = 7.1. s/ X.T. v (k. © 1. ) v T.7. 
 l-l 11 11 11 11 
 
 m. = k. © k. © A. © 1. 
 l 1111 
 
 d. = a. © a. © m. 
 
 l ill 
 
 b. .. = a.m. n/ a. a. \/ a.m. 
 
 l-l li li li 
 
 a. = d. a. = b. 
 
 11 11 
 or 
 
 s . = b. s. = d. 
 
 li li 
 
 2. a. _, = A.k. v- k.1. v A.k. 
 
 l-l 11 11 li 
 
 a. n = A.k. v- k.1. v' x.k. v A.l.K.k. 
 
 l-l 11 11 11 1111 
 
 m. = 1. © k. 
 
 l li 
 
 d. = a. © m. 
 
 i i w l 
 
 b. .. = a. (a. ^ m. ) 
 l-l li i 
 
 a. = b.d. 
 i 11 
 
 s. = b. © d. 
 l li 
 
 3. a. , — A. n/ k. 
 
 i-I i i 
 
 a. , = T.k. (l. © k. ) ^ A.K.k. ^ A.l. (k. v k . ) 
 i-I ill l ill ill i 
 
 m. = 1. © k. 
 
 l li 
 
 d. = a. © m. 
 
 l 11 
 
 b . , = a. a. sy a.m. 
 i-I li li 
 
 a. = d. or a. = b. 
 11 11 
 
 s. = b. © d. 
 
 i li 
 
 Table h. Boolean Equations for Symmetric Carry-Save Adders 
 
1U 
 
 h. a. . = X.k. ^ k.1. v/ X.k. 
 i-I 11 11 11 
 
 a. _ = l.k. 
 i-I i i 
 
 m. = r.r. K\k. 
 
 1 1111 
 
 d. = m. © (a. \/ a. ) 
 
 i 11 i 
 
 b. .. = a. v a.m. 
 i-I l li 
 
 a. = b.d. 
 
 i 11 
 
 s. = b.d. 
 
 l ii 
 
 5. a. _ = X. >• k. 
 
 i-I i i 
 
 a. , = X. k . (k. N/1.) v/A.ic. 
 i-I ill i ii 
 
 m. = 1. © k. 
 
 i ii 
 
 d. = a. © m. 
 
 l i ^ l 
 
 b. . = a. v a.m. 
 i-I l ii 
 
 a. = b. \x d. 
 
 ill 
 
 s. = b. © d. 
 l ii 
 
 6. a. n = K.k. v/ X .1. (k. N/k.) 
 i-I ii ill l 
 
 a. , = X.l. v X. (k. + k. ) 
 i-I ii ii l 
 
 m. = X.l. © <".k. 
 l 1111 
 
 d. = m. © (a. v a. ) 
 
 l ii l 
 
 b. .. = a. a. \/ a.m. ^ a. a. 
 
 i-I ii ii ii 
 
 a. = b.d. a. = b. © d. 
 
 l ii l ii 
 or 
 
 s. = b. © d. s. = b.d. 
 
 i ii i ii 
 
 Table k. Boolean Equations for Symmetric Carry-Save Adders (Continued) 
 
15 
 
 7. a. , = X.k. ^ X.k. ^ k.1. 
 l-l 11 11 11 
 
 a. , = X.l. x.k. 
 l-l 1111 
 
 m. = "X.l. © K.k. 
 l 1111 
 
 d. = m. © (a. v a. ) 
 i 11 i 
 
 b. .. = a. (a. ^ m. ) 
 l-l li l 
 
 a. = b.d. 
 l li 
 
 s. = b.d. 
 l li 
 
 8. a. , = X. v k. 
 
 l-l l l 
 
 a. , = X.k. (l. v k. ) 
 l-l ill l 
 
 m. = X.l. © K.k. 
 i x x x x 
 
 d. = m. © (a. v a. ) 
 
 i 11 i 
 
 b. . = a. v a.m. 
 l-l i li 
 
 a. = b. v d. 
 
 ill 
 
 s. = b.d. 
 
 l li 
 
 9. a. , = K.k. v (X.©1.) (k. ^ k.) v K.k. X.l. 
 i-I li i w i i i iiii 
 
 a. , = (k. © k. ) v (X. © 1.) v k.l. 
 
 i-I li l ^ i li 
 
 m. = X.l. © K.k. 
 l li li 
 
 d. = m. © (a. v a. ) 
 
 l 11 i 
 
 b . , = a. a. v a. a.m. 
 i-I li ill 
 
 a. = b. © d. a. = b. v d. 
 i i w i i i i 
 
 or 
 
 s. = b.d. s. = b. © d. 
 i 11 i 11 
 
 Table h. Boolean Equations for Symmetric Carry-Save Adders (Continued) 
 
16 
 
 1. m. = k. © X. © 1. + k. 
 i ill i 
 
 a 
 
 . _ = m. , © (<.k. n/ X.l. v K.k.(A. ^ 1.) v a.1.(k. v k.)) 
 l-l l-l 11 11 ill i ill i 
 
 b. „ = K.k. X.l. ^ m. _ (X.l. ^ K.k. ^ l.k. ^ k . X . ) 
 1-2 1111 l-l li li li li 
 
 a. = d. a. = b. 
 
 11 11 
 or 
 
 s . = b. s. = d. 
 
 li li 
 
 2. m. = k. © 1. 
 l 11 
 
 d. ., = k.X. n/ m. n K.X.(k. ^ 1. ) v m. ,(X. ^I.k. ^l.k.) 
 l-l l l l-l ill l l-l l 11 11 
 
 b. _. = k.X. -^ m. ,(X. ^ k . v l.k. ) 
 1-2 l l l-l l l li 
 
 a. = b.d. 
 l 11 
 
 s. = b. © d. 
 l li 
 
 3. m. = k. © 1. 
 l li 
 
 d. , = m. n © (k.A.1. vk.X.l. v K.k.l. ^K.k.X.l.) 
 l-l l-l ill ill ill 1111 
 
 b. _ = K.k. X.l. v m. n (<.k. v X.l. N/k.l.) 
 1-2 1111 l-l li li li 
 
 a. = d. or a . = b. 
 11 11 
 
 s. = b. © d. 
 l li 
 
 h. m. = K.k. © X.l. 
 l 1111 
 
 d. , = m. -, (k.1. ss k.X. ^ k.X.) ^ m. -, (k. © X. ) 
 l-l l-l 11 11 11 l-l l l 
 
 b. n = k.X. v m. n (<. v X. v k.l. ) 
 1-2 i i l-l i l li 
 
 a. = b.d. 
 
 l 11 
 
 s. = b.d. 
 
 l li 
 
 Table 5. Boolean Equations for Symmetric Carry-Save Adders 
 
IT 
 
 5. m. = k. © 1. 
 1 li 
 
 d. , = m. ..(K.k. X.l. ^ k.X. ^ k.1. v k.A.) 
 l-l l-l 1111 11 11 11 
 
 -v m. .(k.1. v K.X.I, s/ K.k.l. v/ K.k.X.) 
 l-l 11 ill ill ill 
 
 b. n = K.k. X.l. v m. ,(ic.k. ^ X.l. v k.X.) 
 1-2 1111 l-l li li li 
 
 0. - b. v d. 
 
 ill 
 
 s. = b. © d. 
 l i v j 
 
 6. m. = K.k. © X.l. 
 i 1111 
 
 d. . =m. ,©((X. v 1.) (K.©k.)^k.(X.©l.)vK.k.X.l.) 
 
 l-l i-I l ill ill i i i i 
 
 b. _ = K.k. X.l. \/ m. ..(K.k. v X.l. ^ K.k. X.l.) 
 i-2 1111 l-l li li 1111 
 
 o. = b.d. a. = b. © d. 
 
 l 11 l 11 
 or 
 
 s. = b. © d. s. = b.d. 
 
 i li i li 
 
 7. m. = k.X.l. ^ K.k.l. 
 i ill ill 
 
 d. , = m. ..(K.k.X. v K.X.l. ^k.X.) 
 i-I i-I ill ill li 
 
 v m. ,((k. © X. ) ^ 7.k.T. ) 
 i-I i i ill 
 
 b. _ = k.X. ^ m. , (k. ^ x. ^ k.l. ) 
 i-2 i i i-I i i li 
 
 a. = b.d. 
 
 l 11 
 
 s. = b.d. 
 
 l li 
 
 Table 5. Boolean Equations for Symmetric Carry-Save Adders (Continued) 
 
8. m. = K.k. © X.l. 
 1 1111 
 
 d. -, = m. _ © (k.X. ^ k.X. v k.1. ^ K.k. X.l.) 
 i-i l-l 11 11 11 1111 
 
 b. _ = K.k. X.l. ^ m. ..(K.k. ^ k.X. v k.X.l.) 
 1-2 1111 i-l li li ill 
 
 a. = b. ^ d. 
 ill 
 
 s. = b.d. 
 l li 
 
 9. m. = K.k. © X.l. 
 i 1111 
 
 d i-l = m i-l® ( K i@ k i© ^©V 
 
 b. . = X.1.(k. v k. ) v X.l. (k. © k. ) 
 i-2 ill l l l l ^ i 
 
 v m.((K. © k.) v/ (X. ©1.)) 
 
 18 
 
 a. = b. © d. a. = b. v d. 
 
 i i v ^ i i i i 
 or 
 
 s. = b.d. s. = b. © d. 
 
 i 11 i l w i 
 
 Table 5. Boolean Equations for Symmetric Carry-Save Adders (Continued) 
 
19 
 
 1. o. , - A.l. ^ K.k. v l.K.k. 
 l-l 11 11 ill 
 
 a. , = A.l. v/ K.k. v (X.l. X.k. ) 
 l-l 11 11 1111 
 
 m. = k. © k. © A. © 1. 
 i i v i li 
 
 d. = a. © a. © m. 
 l i i w i 
 
 b. ., = a.m. v a. a. v a.m. 
 l-l li li li 
 
 a. = b. a. = d. 
 
 11 11 
 or 
 
 s . = d. s . = b. 
 
 li li 
 
 2. a. , ■ A.k. 
 l-l i i 
 
 a. , = A.k. v A.k.(1. v- k. ) 
 l-l 11 ill l 
 
 m. = 1. © k. 
 l li 
 
 d. = a. © m. 
 
 l i w l 
 
 b. , = a . v a.m. 
 l-l l li 
 
 a. = b.d. 
 l 11 
 
 s. = b. © d. 
 
 l li 
 
 3. a . .. = A . k . or X.l. or K.k. 
 
 l-l 11 11 11 
 
 a. ., = A.1.(k. v k. ) s^ K.k.l. ss A. l.K.k. 
 
 l-l ill i ill 1111 
 
 m. = 1. © k. 
 l li 
 
 d. = a. © m. 
 
 l 11 
 
 b. . = a. a. v a.m. 
 l-l li li 
 
 a. = b. or a. = d. 
 11 11 
 
 s. = b. © d. 
 l li 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
20 
 
 h. a. . = A.k. 
 l-l 1 l 
 
 a. . = 1. k . ^ A.k. 
 l-l 11 11 
 
 m. = A.l. © K.k. 
 l 1111 
 
 d. = m. © (a. v a. ) 
 
 i 11 i 
 
 b. .. = a. v a.m. 
 l-l i li 
 
 a. = "b.d. 
 i li 
 
 s. = b.d. 
 i li 
 
 a. n = A.l. n/ K.k. \/ A.k. 
 
 l-l 11 11 11 
 
 a. , = k.(A. ^ 1.) ^ K.k. v/ A.l. K.k. 
 
 l-l 11 l 11 1111 
 
 m. = 1. © k. 
 
 l li 
 
 d. = a. © m. 
 
 i i w i 
 
 b . _, = a. (a. \s m. ) 
 l-l li i 
 
 a. = b. v/ d. 
 ill 
 
 s. = b. ©d. 
 i l w l 
 
 6. a. , = K.k.(A.©l.)v A.l. K.k. 
 l-l li 1^1 1111 
 
 a. , = K.k.(A.©l.)^ A.l. K.k. v (k. © k. ) (A.©1.) 
 l-l i i i v - / i 1111 i 11 i 
 
 m. = X.T. © 7.k. 
 
 l 1111 
 
 d. = m. © (a. v a. ) 
 l 11 l 
 
 b. . = a. a. v a. a.m. 
 l-l 11 ill 
 
 o. = b.d. a. = b. © d. 
 
 ill ill 
 
 or 
 
 s. = b. © d. s. = b.d. 
 
 l 11 l 11 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
 (Continued) 
 
21 
 
 7. o. , ■ A.k. 
 l-l l l 
 
 a. . = 1.7.(1. v k. ) 
 l-l ill i 
 
 m. = ~. I. © K.k. 
 l 1111 
 
 d. = m. © (a. v a. ) 
 
 b. . = a. ^ a.m. 
 l-l l li 
 
 o. = b.d. 
 
 l 11 
 
 s. = b.d. 
 
 l li 
 
 8. a. ., = A.l. n/ K.k. \^ A.k. 
 
 l-l 11 11 11 
 
 a. ., = A.l. K.k. 
 
 l-l 1111 
 
 m. = A.T. © K.k. 
 
 i 1111 
 
 d. = m. © (a. ^ a. ) 
 
 i 11 i 
 
 b. .. = a. (a. ^ m. ) 
 l-l li l 
 
 a. = b. ^ d. 
 ill 
 
 s. = b.d. 
 
 i li 
 
 a. ., = k. v k. v X. v 1. 
 
 l-l 1111 
 
 i. , = (k. v/k.) (A.©l.)^l.(K.©k.)^K.k.A.l. 
 l-l i ii v ^i ii v ^i 1111 
 
 m. = A.l. © K.k. 
 l 1111 
 
 d. = m. © (a. ^ a. ) 
 
 l 11 l 
 
 b. ., = a. a. ^ a.m. ^ a. a. 
 l-l li li li 
 
 o. = b. ^ d. a. = b. © d. 
 
 i i i i 11 
 
 or 
 
 s. = b. © d. s. = b.d. 
 
 i 11 i 11 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
 (Continued) 
 
22 
 
 1. m. = k. © k. © A. © 1. 
 l 1111 
 
 d. = m. , © (kXI. s/ K.k.A. s/ k.A.I. v/ K.X.I, n/ iT.k.T.l.) 
 
 i l-l ill ill ill ill 1111 
 
 b. = k. k.A.I. v m. n (A.l. v <.k. ^ k.l. v k.A. v k.1.) 
 1-2 1111 l-l li li li li li 
 
 a. = Id . a. = d. 
 
 11 11 
 or 
 
 s. = d. s . = b. 
 
 li li 
 
 2. m. = k. © 1. 
 i 11 
 
 d. . = m. , © (k. A. v k.l. v/ k.X. ^ k. k.A.I. ) 
 l-l l-l 11 11 11 1111 
 
 b. „ = k. k.A.I. ^ m. ., ( A .1. ^ K.k. ^ k.A.) 
 1-2 1111 l-l li li li 
 
 a. = b.d. 
 i 11 
 
 s. = b. © d. 
 
 i li 
 
 3. m. = k. © 1. 
 i 11 
 
 d. , =m. , © (k.A.I. v k. X.l. *" K.k.A. ^ 7.k.X. 1. ) 
 l-l l-l ill ill ill 1111 
 
 b. _ = K.k.A.l. ^ m. , k. k.A.I. ^ m. n (K.k. ^ X.l. ^ k.l. 
 i-2 1111 l-l 1111 l-l li li li 
 
 o . = b . or a . = d . 
 li ii 
 
 s. = b. © d. 
 
 i ii 
 
 k. m. = K.k. © X.l. 
 l ii ii 
 
 d. . = m. , © (k.l. vk.i, ^k.X.) 
 l-l i-I ii ii ii 
 
 b. _ = k.l. ^ m. n (k. v 1. ^k.A.) 
 1-2 l l i-I l l ii 
 
 a. = b.d. 
 
 i ii 
 
 s. = b.d. 
 l ii 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
 (Continued) 
 
23 
 
 5. m. = k. 1. 
 
 i i ^ i 
 
 d 
 
 b. ^ = k.X. ^ m. ,(k. ^ X. v k.l.) 
 1-2 l l l-l l l li 
 
 a. = t>. ^ d. 
 
 ill 
 
 s. = b. © d. 
 i li 
 
 6. m. = K.k. ©X.l. 
 l 1111 
 
 d.^ = m.^© ((k. ©k.) (X.©1.) ^ K i k i (X i ©l i ) ^ k^X^) 
 b i-2 = ^i© k i^ (^©V - m._ 1 ((X i ©l.) 
 
 (k. © k. ) ^ k.X. ) 
 i i li 
 
 a. = b.d. a. = b. © d. 
 
 i 11 l 11 
 or 
 
 s. = b. © d. s. = b.d. 
 
 i li l li 
 
 7. m. = K.k. © X.l. 
 l 1111 
 
 d. n =m. n © (k.X. v k.X. vk.L vic.kll.) 
 l-l l-l 11 li 11 1111 
 
 b. _ = K.k. X.l. v/ m. n (K.k. \/ X.l. ^ k.X.) 
 1-2 1111 l-l li li li 
 
 a. = b.d. 
 
 l 11 
 
 s. = b.d. 
 
 i li 
 
 8. m. = K.k. © X.l. 
 l 11 11 
 
 d. . =m. .k.X. vm. n ((K.©X.)v/K.k.X.l.) 
 l-l l-l i i l-l i i 1111 
 
 b. _ = k.X. ^ m. ,(k. v A. v K.k. X.l.) 
 1-2 l l l-l l l 1111 
 
 a. = b. v d. 
 
 ill 
 
 s. = b.d. 
 l 11 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
 (Continued) 
 
2k 
 
 9. m. = <.k. © X.l. 
 1 1111 
 
 d. . = m. , © U.k.X.l. v/ (X. v 1.) (K.©k.)^K.(A.@l.)) 
 l-l i-l v 1111 l l l w l l l w i 
 
 b. _ = K.k.X.l. ^ m. ., (k .k. v X . 1. ^K.k.X.l.) 
 i-2 1111 l-l li li 1111 
 
 a. = b. v d. a. = b. © d. 
 
 i i i i i ^ i 
 
 or 
 
 s. = b. © d. s. = b.d. 
 
 i 11 i 11 
 
 Table 6. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
 (Continued) 
 
25 
 
 5. COUPLED DON'T CARES 
 
 One of the interesting problems encountered in the design of 
 redundant adders is the coupled don't care. This condition arises when 
 a digital value has two representations and the two variables used to 
 represent the value are mutually complementary in the two represen- 
 tations. That is, if X.l. is one representation, the other is X.I.. 
 
 11 r 11 
 
 An example showing the coupled don't care condition is shown in Table 8, 
 the truth table for the symmetric subtracter for design 1A. 
 
 A 1 k k a a b Line 
 
 
 
 
 
 
 
 
 
 0/1 
 
 o/i 
 
 
 
 1 
 
 
 
 
 
 
 
 
 
 
 
 1 
 
 1 
 
 2 
 
 
 
 
 
 1 
 
 
 
 0/1 
 
 0/1 
 
 1 
 
 3 
 
 
 
 
 
 1 
 
 1 
 
 0/1 
 
 0/1 
 
 
 
 k 
 
 
 
 1 
 
 
 
 
 
 
 
 1 
 
 1 
 
 5 
 
 
 
 1 
 
 
 
 1 
 
 
 
 1 
 
 
 
 6 
 
 
 
 1 
 
 1 
 
 
 
 0/1 
 
 0/1 
 
 
 
 7 
 
 
 
 1 
 
 1 
 
 1 
 
 
 
 1 
 
 1 
 
 8 
 
 1 
 
 
 
 
 
 
 
 0/1 
 
 0/1 
 
 1 
 
 9 
 
 1 
 
 
 
 
 
 1 
 
 0/1 
 
 o/i 
 
 
 
 10 
 
 1 
 
 
 
 1 
 
 
 
 1 
 
 
 
 
 
 11 
 
 1 
 
 
 
 1 
 
 1 
 
 0/1 
 
 0/1 
 
 1 
 
 12 
 
 1 
 
 1 
 
 
 
 
 
 0/1 
 
 o/i 
 
 
 
 13 
 
 1 
 
 1 
 
 
 
 1 
 
 
 
 1 
 
 1 
 
 14 
 
 1 
 
 1 
 
 1 
 
 
 
 o/i 
 
 o/i 
 
 1 
 
 15 
 
 1 
 
 1 
 
 1 
 
 1 
 
 0/1 
 
 0/1 
 
 
 
 16 
 
 Table 8 
 
 Notice that the value for a. in lines 1, 3, h, 7» 9, 10, 12, 
 13, 15 » and 16 may be chosen as either or 1 but that the choice for 
 
26 
 
 a. is then constrained to be the same. It is readily apparent that 
 the choice of don't cares to simplify a. may make a. more complicated. 
 This problem is similar to the case of trying to minimize two 
 functions simultaneously. 
 
 While no procedure has been discovered which will guarantee 
 the absolute minimal functions, a procedure which gives all possible 
 functions has been investigated. 
 
 The procedure begins by introducing a function <j) consisting 
 
 of all the don't cares chosen to be one. Then one minimizes the 
 
 functions f v <j> and g v <j>. The steps in the procedure are as follows: 
 
 i) Find all implicants of f and g. 
 
 ii) Find all prime implicants of f ^ <j> . which simplify the 
 the expression for f. 
 
 iii) Using the <f>. determined in step ii) find all prime 
 implicants of g ^ <f> . . 
 
 iv) Find all minimal covers for f using the prime impli- 
 cants of f ^ (J). . 
 1 
 
 v) Select cover from step iv) which gives minimal expres- 
 sion for g. 
 
 The functions from Table 8 will be used to illustrate the procedure. 
 
 For convenience a Karnaugh map showing both functions is given on the 
 
 following page. 
 
27 
 
 YZ Y Z YZ YZ 
 
 W X 
 
 W X 
 
 W X 
 
 W X 
 
 
 
 f 
 1 
 
 3 
 
 2 
 
 k f 
 
 f 
 5 
 
 f 
 7 
 
 6 
 
 12 
 
 f 
 13 
 
 15 
 
 lU 
 
 8 
 
 9 
 
 11 
 
 io g 
 
 Implicants of f and g 
 
 f: 1,U, 5, 7, 13 
 g: 10 
 
 Prime implicants of f v | which give reduction of f 
 
 0,2,3,6 
 6,12,1*+, 15 
 0,8,9,12 
 3,9,11,15 
 
 0,2,3 
 
 0,8,12 
 
 
 
 0,2,6 
 
 9 
 
 3 
 
 3,9,11 
 
 2,3,6 
 
 3,11,15 
 
 6 
 
 12 
 
 6,12,14 
 
 15 
 
 6,ll+,15 
 
 12.lU.15 
 
 9,11,15 
 
 8,9,12 
 
 0,8,9 
 
 Null 
 
 0,1, 2, 3,1+, 5, 6, 7 
 1+, 5, 6, 7,12,13,11+, 15 
 0,1,1+, 5, 8, 9,12, 13 
 1,3,5,7,9,11,13,15 
 
 0,1,2,3 
 0,1+, 8, 12 
 0,1,1+, 5 
 0,2,1+, 6 
 1,5,9,13 
 1,3,5,7 
 1,3,9,11 
 2,3,6,7 
 3,7,11,15 
 U, 5,6,7 
 U, 5, 12 ,13 
 1+, 6, 12,11+ 
 5,7,13,15 
 6, 7,1*+, 15 
 12,13,11+, 15 
 9,11,13,15 
 8,9,12,13 
 0,1,8,9 
 
 1,5 
 
 5,7 
 5,13 
 
28 
 
 3. Using cf> determined in step 2 prime implicants of g ^ <f> 
 
 0,2,3,6 0,2; 2,3; 2,6; 2,10 
 
 6,12, lU, 15 6,lU; lU,15; 12, lU; 10, Ik 
 
 0,8,9,12 0,8; 8,12; 8,9; 8,10 
 
 3,9,11,15 3,11; 11,15; 9,11; 10,11 
 
 0,2,3 0,2; 2,3; 2,10 
 
 0,8,12 0,8; 0,12; 8,12; 8,10 
 
 0; 10 
 
 0,2,6 0,2; 2,6; 6,10 
 
 9 9; 10 
 
 3 3; 10 
 
 3.9.11 3,11; 9,11; 10,11 
 2,3,6 2,3; 2,6; 2,10 
 3,11,15 3,11; 3,15; 10,11 
 6 6; 10 
 
 12 12; 10 
 
 6,12,lU 6,lU; 12, Ik; 10, Ik 
 
 15 10; 15 
 
 6,lU,l5 6,lU; 14,15; 10, Ik 
 
 12,1*1,15 12, Ik; lU,15; 10, Ik 
 
 9,11,15 9,11; 11,15; 10,11 
 
 8.9.12 8,9; 8,12; 8,10 
 0,8,9 0,8; 8,9; 8,10 
 
 Null 10 
 
Covers for f using prime implicants of f v <j> 
 
 29 
 
 R 
 
 B 
 
 R 
 
 10 
 
 f ii 
 
 ! 12 
 'l3 
 
 lit 
 f 15 
 <16 
 ( 1T 
 
 18 
 
 ha 
 
 <20 
 '21 
 ! 22 
 '23 
 *2H 
 '25 
 <26 
 
 •ime implicants of 
 f v 4 
 
 1 
 
 Impli c 
 k 
 
 ants 
 5 
 
 of f 
 
 7 
 
 1 
 
 0,1,2,3,^,5,6,7 
 
 X 
 
 X 
 
 X 
 
 X 
 
 
 U,5,6,7,12,13,lU,15 
 
 
 X 
 
 X 
 
 X 
 
 X 
 
 0,1, U, 5, 8,9, 12 ,13 
 
 X 
 
 X 
 
 X 
 
 
 X 
 
 1,3,5,7,9,11,13,15 
 
 X 
 
 
 
 X 
 
 X 
 
 0,1,2,3 
 
 X 
 
 
 
 
 
 0,4,8,12 
 
 
 X 
 
 
 
 
 0,1,^,5 
 
 X 
 
 X 
 
 X 
 
 
 
 0,2,1+, 6 
 
 
 X 
 
 
 
 
 1,5,9,13 
 
 X 
 
 
 X 
 
 
 X 
 
 1,3,5,7 
 
 X 
 
 
 X 
 
 X 
 
 
 1,3,9,11 
 
 X 
 
 
 
 
 
 2,3,6,7 
 
 
 
 
 X 
 
 
 3,7,11,15 
 
 
 
 
 X 
 
 
 U,5,6,7 
 
 
 X 
 
 X 
 
 X 
 
 
 **, 5,12,13 
 
 
 X 
 
 X 
 
 
 X 
 
 U,6,12,lU 
 
 
 X 
 
 
 
 
 5,7,13,15 
 
 
 
 X 
 
 X 
 
 X 
 
 6,7,1^,15 
 
 
 
 
 X 
 
 
 12, 13, 1U, 15 
 
 
 
 
 
 X 
 
 9,11,13,15 
 
 
 
 
 
 X 
 
 8,9,12,13 
 
 
 
 
 
 X 
 
 0,1,8,9 
 
 X 
 
 
 
 
 
 1,5 
 
 X 
 
 
 X 
 
 
 
 k,5 
 
 
 X 
 
 X 
 
 
 
 5,7 
 
 
 
 X 
 
 X 
 
 
 5,13 
 
 
 
 X 
 
 
 X 
 
30 
 
 f = (R x v R 3 v R u v R 5 v R T v R 9 v R 1Q v ^ - R^ - R^) 
 (R 1 v R 2 >/ R 3 v R 6 v R ? - Rg - R lU - R 15 - R^ - R^) 
 (R i - R 2 - R 3 - R ? - R 9 - R 10 - R lU - R 15 - R 1? 
 
 V 
 
 V 
 
 R 23 V R 2U v R 25 v R 26 } (R 1 v R 2 v R U v R 10 V R 12 
 R 13 v R lU v R 1T v R l8 v *W ^ R 2 v R 3 v R l+ v R 9 
 
 \/R v R ^ R v R v R ^ R ^) 
 15 17 19 20 21 26' 
 
 Obviously all possible covers which give a reduction of f 
 
 are given by the above. The task remains to select the minimal ones. 
 
 Many of the covers are not minimal and may be disregarded. Implicants 
 
 R , R , R and R, correspond to W, X, Y and Z respectively. Minimal 
 
 covers of f are formed by choosing any two of the above implicants. 
 
 Thus there are 6 covers corresponding to R-,R p > R-,Ro 5 R^h* RpRo» 
 
 R^R, and R^R, . The functions for these covers are tabulated below. 
 2 k 3 4 
 
 Cover 
 
 f 
 
 R 1 R 2 
 
 W ^ X 
 
 R 1 R 3 
 
 W v Y 
 
 R A 
 
 W v z 
 
 R 2 R 3 
 
 X v y 
 
 *2*k 
 
 X v z 
 
 R 3 R 4 
 
 Y v z 
 
 Y Z v (Y v Z) (WO X) 
 X Z v (X v/ Z ) (W© Y) 
 
 Y X v (Y v x) (W© Z) 
 WZ^ (W v Z) (X© Y) 
 
 WIv(Wvl) (X© Z) 
 
 W X v (w v x) (Y© Z) 
 
 These functions are also the minimal functions as can be 
 seen by checking the covers provided by choosing a more complicated 
 function for f. 
 
 It is apparent that one may also apply this procedure to 
 g first and find covers for f. This is not necessary, however, as 
 shown by the following theorem (7). 
 
31 
 
 Theorem : Given a solution of the form 
 
 f. = f \/ <fc. and g. = g v d>. 
 1 1 °i i 
 
 there exists a solution of the form 
 fj = g. and g. = f., 
 where f and g indicate the minterms where f and g 
 are 1 respectively and <f>. indicates the don't cares 
 chosen to be 1. 
 
 Proof: 
 
 where cj) . = cf> 
 
 
 
 — 
 
 
 1 
 
 
 .1 
 
 
 
 
 
 ,0 
 
 
 ^.1 
 
 
 ,1 
 
 f . 
 
 = 
 
 8,- 
 
 = 
 
 g 
 
 v/ 
 
 *, 
 
 = 
 
 g 
 
 V 
 
 *,• 
 
 = 
 
 f 
 
 N/ 
 
 *J 
 
 J 
 
 
 l 
 
 
 
 
 1 
 
 
 ^0 
 
 
 1 
 
 n 
 
 
 1 
 
 
 
 1 
 
 
 T 
 
 1 
 
 g j 
 
 = 
 
 f . 
 
 1 
 
 
 f 
 
 •>s 
 
 ♦i 
 
 = 
 
 f 
 
 V 
 
 ♦i 
 
 = 
 
 g 
 
 V 
 
 ♦j' 
 
 ,1 
 
 
 ,0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Thus, one need only find minimal functions starting with f, 
 complement the results and obtain the functions which would be 
 obtained starting with g. In the above example, therefore, there are 
 actually twelve minimal solutions. 
 
 The case described in this example is very symmetric as are 
 all the other cases encountered in the adder design. This is due to 
 the symmetry of the problem and the format assignment. 
 
 The problem of complementary coupled don't cares (that is, 
 a. may be chosen as either or 1 but then a is constrained to be the 
 complement of a ) is solved in a similar manner. That is, one finds 
 the covers for f and then picks the corresponding minimal function for 
 the complement of g. 
 
32 
 
 Note: The reader unfamiliar with the notation used in 
 representing implicants and covers is referred to (k) . 
 
33 
 
 6. SUMMARY 
 
 This thesis has shown the steps used in the logical design 
 of a class of limited carry-borrow propagation adders. Fifty four 
 designs were presented, most of them for the first time. Some designs 
 were pointed out as appearing to he minimal. 
 
 No logic drawings or gate counts were presented as this is a 
 function entirely of implementation. These designs, in fact, lend 
 themselves readily to Large Scale Integration since they are modular, 
 fairly simple, and have only a few lines crossing module boundaries. 
 
 The primary use of these designs would probably be in a 
 machine dedicated to total redundancy. In the case that this were not 
 practical, the designs may be used for assimilation also. For example, 
 in the case of the symmetric adder and symmetric subtracter the redun- 
 dant number to be assimilated is applied to a. and a., b. ., is used as 
 
 1 i l-l 
 
 a propagating signal and is applied to input m s and the conventional 
 (i.e. assimilated) result is available at d. . This configuration is 
 
 shown in Figure 6. 
 
 m i-i 
 
 m. 
 
 i-l 
 
 1+1 
 
 Figure 6. Adder Structure Used as Assimilator 
 
3U 
 
 Using Rohatsch's transformation theory, it is readily appar- 
 ent that more levels may be added to the adder structure allowing more 
 redundant inputs. For example, a fourth level may be added to the 
 three level structure which will allow six redundant inputs. It is 
 also evident that one can add a conventional input to the three level 
 structure with no increase in cost. This was not done, however, since 
 we were interested only in total redundancy. 
 
 Furthermore , the requirement that the format of all redun- 
 dant interstage signals be the same is not necessary. In fact the 
 recognition of this fact prompted design procedure B. As a result 
 there are actually 729 possible designs which are simply all possible 
 combinations of the three levels. 
 
 The most interesting area for future investigation is the 
 statistical properties of the adders. The analysis of the structures 
 has just begun (7>8) and has pointed out the difficulty of the process. 
 
35 
 LIST OF REFERENCES 
 
 1. Atkins, D. E. , "Arithmetic Unit of Illiac III: Simulation and 
 Logical Design - Part I", Department of Computer Science, Univer- 
 sity of Illinois, Urbana, Illinois 6l801, File No. 713, 
 September, 1966. 
 
 2. Atkins, D. E. , "The Theory and Implementation of SRT Division", 
 Department of Computer Science, University of Illinois, Urbana, 
 Illinois 61801, Report No. 230, June, 1967 (M.S. Thesis). 
 
 3. Avizienis, A., "Signed-Digit Number Representation for Fast 
 Parallel Arithmetic", IRE Transactions on Electronic Computers , 
 Vol. EC-10, No. 3, pp. 389-^00, September, 196l. 
 
 k. Hohn, F. E. , Applied Boolean Algebra, MacMillan Company, New York, 
 1966. 
 
 5. Robertson, J. E. , "Increasing the Efficiency of Digital Computer 
 Arithmetic Through Use of Redundancy", Notes for EE^97B, Univer- 
 sity of Illinois, Urbana, Illinois 6l801, Fall, 196k. 
 
 6. Robertson, J. E. , "A Deterministic Procedure for the Design of 
 Carry-Save Adders and Borrow - Save Subtracters", Department of 
 Computer Science, University of Illinois, Urbana, Illinois 618OI, 
 Report No. 235, July, 1967. 
 
 7. Robertson, J. E. , Private Communication, March, 1968. 
 
 8. Rohatsch, F. A., "A Study of Transformations Applicable to the 
 Development of Limited Carry - Borrow Propagation Adders", 
 Department of Computer Science, University of Illinois, Urbana, 
 Illinois 61801, Report No. 226, June, 1967 (Ph.D. Thesis). 
 
V 
 
 ^