■ 
 
 
 
 w 
 

 ll B HAHY 
 
 OF THE 
 UN IVLR5ITY 
 Of ILLI NOIS 
 
 510.84 
 Iffcr 
 no.228>-236 
 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 
 
 MAY 3 
 JUN V 
 
 my 
 
 MAY 4 1938 
 
 L161 — O-1096 
 
ynadL 
 
 LA o i 
 
 C?A^ Report No. 235 
 
 2/ A DETERMINISTIC PROCEDURE FOR THE DESIGN OF 
 
 CARRY-SAVE ADDERS AND BORROW-SAVE SUBTRACTERS 
 
 f 
 
 Stf i.* \M 
 
 by 
 James E. Robertson 
 
 July 5, 1967 
 
Report No. 235 
 
 A DETERMINISTIC PROCEDURE FOR THE DESIGN OF 
 CARRY-SAVE ADDERS AND BORROW-SAVE SUBTRACTERS 
 
 by 
 James E. Robertson 
 
 July 5, 1967 
 
 Department of Computer Science 
 University of Illinois 
 Urbana, Illinois 6l801 
 
 * To be presented at the First Annual IEEE Computer Conference, 
 Chicago, Illinois, September 6-8, 19^7 . 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/deterministicpro235robe 
 
TABLE OF CONTENTS 
 
 Page 
 
 1. REVIEW. ............................ 1 
 
 2. THE DETERMINISTIC PROCEDURE . . . . ........ . . . . . . 3 
 
 3. CHOICE OF NORMALIZED DIGIT SETS ................ 5 
 
 k. EXTENSION TO SYMMETRIC DIGIT SETS ............... 7 
 
 5. CHOICE OF BINARY FORMATS FOR s* AND a*. ........... . 8 
 
 i i 
 
 6. DETAILED LOGICAL DESIGNS. ................... 9 
 
 7. FURTHER DESIGN CONSIDERATIONS ................. 11 
 
 8. SUMMARY AND CONCLUSIONS .................... 12 
 
 BIBLIOGRAPHY. ......................... 13 
 
A DETERMINISTIC PROCEDURE FOR THE DESIGN OF 
 CARRY-SAVE ADDERS AND BORROW-SAVE SUBTRACTERS 
 
 by 
 
 James E„ Robertson 
 
 Department of Computer Science 
 
 University of Illinois 
 
 Urbana, Illinois 
 
 ABSTRACT 
 
 A recently developed deterministic procedure will be described, 
 and employed to determine binary carry-save adder and borrow-save subtracter 
 designs. Designs believed to be new as well as those previously known will 
 be developed. A particular structure, expressed in terms of normalized digit 
 sets, leads to three practical algebraic structures,, Each of these in turn 
 leads to nine (not necessarily unique) logical designs. Examples will be 
 given and possible application to variable field length systems will be 
 discussed. 
 
REVIEW 
 
 Historically, the design of carry save adders and borrow save 
 subtracters has been conducted by modification of conventional adders with 
 propagating carry and of subtracters with propagating borrow. As an example, 
 the Boolean equations for the ith digital position of a binary subtracter with 
 propagating borrow are 
 
 s . = a. © m. © b 
 1 i 11 
 
 b. . = a.b. "v b.m. v m.a. , 
 l-l li li li 
 
 (1) 
 
 in which a. is a minuend digit, m, is a subtrahend digit, s. is a difference 
 digit, and b. and b. are respectively the incoming and outgoing propagating 
 borrow. Equations (l) are the Boolean equivalent of the algebraic expression; 
 
 -2b. _ + s. = a. - m. - b. (2) 
 
 l-l 1111 
 
 The direct modification to a borrow save subtracter is one of 
 associating with the a. stored borrow digits Q!., and associating with the s. 
 stored borrow digits a.. Equations (l) then become 
 
 s. = a. © m. ©a 
 1111 
 
 a. ., = a. en. ^ a.m. v m.a. 
 
 l-l li li li 
 
 (3) 
 
 in which, as before, m. is a subtrahend digit, but now the minuend is 
 
 represented by the appropriately weighted sum of the digits a. and 0L. } and 
 
 the difference is represented by the weighted sum of the digits s. and a. „ 
 
 If the digits s. and o. are associated to form a redundantly represented 
 
 digit s. in accordance with the formula s. = s. - a,, the possible values 
 * i ill 
 
 of s. are -1, 0, and 1. 
 
 i ' 7 
 
 A less obvious modification to a borrow save subtracter is 
 achieved by rewriting Equations (l) and substituting as follows: 
 
 ■1- 
 
s . = a. © m. © b. 
 1 11 1 
 
 b. , = (a. © m. )b. ^ a.m. 
 l-l i li li 
 
 (M 
 
 Let 
 
 k. = (a. © m. )b. 
 
 l ill 
 
 b. _, - k. ^ a.m. 
 
 l-l i li 
 
 s. = (a. © m. ) © (k. n v-a. n m. _, ) 
 i i i i+I l+l l+l 
 
 k. = (a. © m. )°(k. ^ a . m. . ) 
 i l l i+I i+I i+I 
 
 (5) 
 
 If, in Equations (5), the input propagating borrow k is replaced by a 
 
 i+1 
 
 stored borrow Oi. in association with a. , and the output propagating 
 
 borrow k. is replaced with a stored borrow a in association with s , the 
 1 1 1' 
 
 Boolean equations for the stored borrow subtracter become 
 
 s. = (a. © m. ) © (a. . v a. _m. . ) 
 
 1 1 1 i+I i+I i+I 
 
 J . = ( a . © m . ) . (a . . v a . . m. _ ) 
 
 1 1 1 i+I i+I i+I 
 
 (6) 
 
 In Equations (6), the combination s. = 
 
 , a. = 1, cannot occur, hence a 
 1 ' 1 ' 
 
 redundantly represented digit s. = -2a. + s. may assume only the three 
 values -1, 0, and 1. 
 
 As is evident from the expression for b in Equations (h) } the 
 propagating borrow must necessarily pass through an AND circuit and an OR 
 circuit in each digital position. The stored borrow of the subtracter of 
 Equations (3) is the output of the OR circuit; the stored borrow of 
 Equations (6) is the output of the AND circuit; thus the subtracter 
 structures require equivalent hardware. The relationship a.s. =0 implied 
 by Equations (6) simplifies the circuitry for conversion of the difference, 
 represented by the s. and a., to conventional (non-redundant) form, and is 
 therefore preferable if separate circuitry is provided for conversion. 
 
 -2- 
 
2. THE DETERMINISTIC PROCEDURE 
 
 The purpose of the following sections is to describe a deterministic 
 procedure for the design of carry-save adders and borrow-save subtracters. 
 In the case of binary subtracters, which are chosen for specific examples, 
 the procedure is shown to result in not only the two designs described in 
 the previous section, but in new designs as well. The procedure involves 
 three stages of design, as follows: 
 
 1) Specification in terms of normalized digit sets, 
 
 2) Choice of specific algebraic values, and 
 
 3) Logical design with specific binary formats. 
 
 For the purposes of this paper, an n-valued digit set is defined as 
 a sequence of n successive integers m, m+1, ..., m+n-1, with m an integer 
 (positive, negative, or zero) and n an integer greater than 1. The digit 
 set is normalized if m=0. The digit set is symmetric if n is odd and 
 
 n^l 
 
 2 
 is also an element of the digit set. For a number in conventional form, 
 
 m = - ~^~o It follows that for any element x of a symmetric digit set, 
 
 the digit set associated with each digital position is normalized with n=r, 
 the radix. If n > r, the digit set is redundant. 
 
 A carry-save adder (or borrow-save subtracter) necessarily requires 
 that the digit set of the sum (or difference) be redundant; otherwise, the 
 representation of the sum (or difference) is unique, which implies that each 
 digit is in general a f "unction of all digits of lesser significance. Only 
 digit sets of minimum redundancy (n=r+l) for the binary case (r=2) are 
 discussed here. Under these restrictions the first stage of design,, 
 specified in terms of normalized digit sets, leads to only one possible 
 specification. 
 
 In the second stage of design, the choice of the symmetric digit 
 set for the sum (or difference) is considered as well, and leads to two 
 additional algebraic specifications, one being an adder and the other a 
 subtracter. Thus the second stage of design, requiring a choice of 
 specific algebraic values, leads to three algebraic structures, as 
 follows : 
 
 1) The normalized carry-save adder, 
 
 2) The symmetric carry-save adder, and 
 
 3) The symmetric borrow-save subtracter. 
 
For the structures considered here, a first input is in conventional 
 form (n=r=2), the second input is in minimally redundant form (n=r+l=3), and 
 the output (sum or difference) is also in minimally redundant form. Before 
 the third stage (logical design) can proceed, it is necessary to specify 
 precisely how the minimally redundant digits are represented in terms of 
 two binary digits; that is, a binary format is chosen for the redundant 
 digit sets. It is also required that the same format be chosen for the 
 redundant output and the redundant input, since commonly the output of one 
 calculation becomes the input for the next, as in, for example, recursive 
 steps of a multiplication. 
 
 Under these conditions, seventy-two formats, or logical designs, 
 are possible for each of the three algebraic structures. Formats of the 
 same FN type, however, are considered equivalent, since permutation is 
 equivalent to interchanging names of the two binary digits employed, and 
 negation of a format digit is equivalent to replacing it by its complement 
 wherever it appears in the design equations. There are then only nine PN 
 types of logical designs for each of the three structures. For brevity, 
 the nine FN types of designs will be described here only for the third 
 algebraic structure, the symmetric borrow-save subtracter. 
 
3. CHOICE OF NORMALIZED DIGIT SETS 
 
 The usual procedure for normalized digit set design is one of 
 specifying the output and input digit sets, and then determining a structure 
 meeting these specifications. 
 
 r+1 
 
 Figure 1 shows a structure consisting 
 of two addition tables,, or levels, 
 (each shown by a box) which meets the 
 specifications of the minimally 
 redundant carry-save adder considered 
 here. It is possible to show, for 
 the given specifications, that two 
 levels are necessary and sufficient, 
 and that the digit sets must be 
 chosen with the number of values of 
 Figure 1. The following trivial 
 observations are necessary; 
 
 1) For any addition table, 
 the number of values of the sum 
 digit set is one less than the 
 sum of the numbers of values of the 
 addend and augend digit sets. 
 
 2) The transfer input set labelled b. has the two normalized values 0, 1; the 
 transfer output set rb . has the values obtained by multiplying those of 
 b. by the radix r; namely 0, r, 
 
 3) The composite digit set representative of the output (sum) of the lower 
 
 addition table is rb. , + d. 
 
 l-l 1 
 
 If this digit set is to consist of 
 
 successive integers, the digit set for d. must have at least r values. 
 h) The composite digit set rb. + d. will have a number of values which is 
 
 at most the product of the numbers of values of rb. , and of d. 
 
 l-l 1 
 
 The 
 
 maximum number of values is achieved only if the number of values of d. 
 
 is precisely r; if the digit set of d. is redundant, the composite set 
 
 will have fewer values than the product of those of rb. , and d , „ 
 
 l-l 1 
 
 -5- 
 
The first observation implies that the sum of the numbers of values 
 
 of the digit sets of d. and b. is r + 2. Since no digit set has less than two 
 D 1 1 
 
 values, b must have at least two values, The third observation indicates 
 
 ' i 
 
 that d must have at least r values, hence the choices shown for d and b are 
 i i l 
 
 the only ones possible. 
 
 Since the values of d. and b are not compatible with the 
 
 l l 
 
 specifications for the addend and augend of the carry-save adder^ another 
 addition table is necessary. From observation h, the number of values of the 
 output digit set is 2r, hence the two inputs will have a total number of 
 values equal to 2r + 1. This then permits one input of r values^ and a second 
 input of r + 1 values,, consistent with the desired specifications. 
 
 -6- 
 
h. EXTENSION TO SYMMETRIC DIGIT SETS 
 
 Since each normalized digit set has zero as its least value, all 
 
 digit sets appearing on Figure 1 are normalized, and hence completely 
 
 specified as indicated in line 1 of Table 1. If the digit sets of s. and 
 
 M- 1 
 
 a. are symmetric, however, two solutions are possible, as shown in lines 2 
 
 and 3 of Table 1 (l represents -l). 
 
 s . 
 
 i 
 
 
 
 
 
 * 
 
 b 
 
 d. 
 
 rb. _ 
 
 m. 
 
 a . 
 
 l 
 
 i 
 
 l-l 
 
 l 
 
 i 
 
 normalized 
 
 adder 
 
 symmetric 
 adder 
 
 symmetric 
 subtracter 
 
 0,1,2 0,1 0,1 0,2 0,1 0,1,2 
 1,0,1 0,1 1,0 0,2 0,1 1,0,1 
 1,0,1 1,0 0,1 2,0 1,0 1,0,1 
 
 Table 1. Values of Digit Sets for Three Algebraic Structures, 
 
 In Table 1, values for the digit sets must be chosen so that the 
 
 equations s. = b. + d. and rb . _ + d. = m. + a. are always satisfied, A 
 iii l-l ill J 
 
 structure is called an adder if the transfer digit b. and the addend digit 
 m. are both positive; if both are negative the structure is called a 
 subtracter, with m. a digit of the subtrahend. 
 
 -7- 
 
5. CHOICE OF BINARY FORMATS FOR s* AND a* 
 
 1 1 
 
 The first step in logical design is the choice of binary state 
 assignments to be considered. This is a tedious but straightforward process, 
 which may proceed as follows: 
 
 1) List the 2k ways of assigning the four states of two binary digits to 
 four digital values, with the fourth value as yet unspecified,, 
 
 2) For each of three groups, list the eight state assignments equivalent 
 under permutation and negation „ Choose one assignment from each group, 
 
 3) For each of the three state assignments resulting from step 2, list four 
 sets of digital values by assigning to the previously unspecified fourth 
 digital value the values 1, 0, 1, and "don't care". 
 
 k) Among the twelve assignments resulting from step 3> identify the three 
 pairs equivalent under permutation and negation, and delete one of each 
 pair. The equivalence results from the fact that the same digital value 
 is assigned to two states during step 3° These two states can then be 
 interchanged and the assignment will then be equivalent to another of the 
 twelve assignments of step 3° 
 
 The procedure outlined above results in nine assignments, none of 
 which are equivalent under permutation and negation. One such set of nine 
 assignments for the digital values 1, 0, and 1 is given in Table 2, The 
 assignments are numbered in Table 2 for future reference. 
 
 State 
 
 
 D: 
 
 Lgital Values 
 
 
 
 
 
 
 
 
 0, 
 
 
 
 .< 1 
 
 . 
 
 D.C. 
 
 
 
 0. 
 
 1 .. 
 
 T 
 
 1 
 
 1 
 
 
 1 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 
 D.C. 
 
 1 
 
 
 
 1 
 
 1 
 
 
 
 
 
 1 1 
 
 
 
 
 T T 
 
 D.C 
 
 . 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 Design 
 Number 
 
 h 5 
 
 Table 2. Assignments of Digital Values to Four States. 
 
 For the logical designs to follow^ the two binary digits which 
 
 represent a. will be called 0C. and a.; those which represent', s. will be 
 1 i 1 * £ 1 
 
 called 0. and s.. For reasons given before, a. and s. are always 
 11 '11 
 
 consistently represented. 
 
 -ft- 
 
6. DETAILED LOGICAL DESIGNS 
 
 Simplified Boolean equations for the detailed logical designs for 
 each of the nine assignments are given below. 
 
 Design 
 Number 
 
 Lower Addition Table 
 
 Upper Addition Table 
 
 1 
 
 b , = a.m. ^ a Q; ^ a m, 
 
 l-l 11 li 11 
 
 d. = a. © a. © m. 
 
 i i w i ^ i 
 
 a. = b 
 
 or 
 
 ; O = d 
 
 ) 1 J 
 
 is - b 
 
 I i i 
 
 i-1 
 
 OL ^ a m 
 
 i i i 
 
 o . = 
 
 b d. 
 
 i l 
 
 a. = 
 i 
 
 a. ff m. 
 
 i i 
 
 s . 
 l 
 
 b © d 
 
 i-1 
 
 = OL. a . n/ a m. 
 
 li li 
 
 a. = b 
 
 or a = d 
 
 1 2 
 
 d. = 
 
 i 
 
 a. © m. 
 
 s . = 
 
 b. v + d. 
 l i 
 
 Vl 
 
 d. = 
 
 l 
 
 i-1 
 
 = OL ^ a m 
 i i i 
 
 m (+ (ol ^ a ) 
 I i i 
 
 - a (a v m. ) 
 li i 
 
 a. = 
 
 b d 
 i i 
 
 b d 
 
 i i 
 
 b v d 
 
 i i 
 
 a m 
 
 i i 
 
 s . = 
 
 b. <4 d 
 
 l i 
 
 b i-i 
 
 = OL a . ^ OL a m 
 
 li i i i 
 
 i-1 
 
 m . <9 (OL. v a . ) 
 
 ii l 
 
 = OC v a m 
 
 i i i 
 
 d. = 
 
 i 
 
 b. . 
 
 1 - X 
 
 m. 
 
 © (a, ^ a J 
 
 = a. (a. ^ m ) 
 
 o . = 
 
 s . 
 
 i 
 
 o. = 
 
 S . =3 
 
 1 1 
 
 b d 
 l i 
 
 b. fl 1 
 
 i v l 
 
 b.d 
 
 i l 
 
 b.d 
 i i 
 
 b ^ d. 
 
 or 
 
 o . - b . © d . 
 
 D d 
 l i 
 
 i^i i 
 
 i-1 
 
 Qa N/am vQ a 
 
 l i i i i i 
 
 b d 
 i l 
 
 o = b 
 
 b. © d. 
 
 i i 
 
 m. © (a. ^ a . ) 
 
 ii i 
 
 s. 
 
 l 
 
 b . © d , 
 l i 
 
 s. - b d. 
 i ii 
 
 Table 3. Boolean Equations for Symmetric Borrow-Save Subtracters 
 
The combined equations for design 1 can be written as 
 
 s. = a. © a. © m. 
 1 1 w l w i 
 
 a. q = a . m. v a. a. v a.m 
 
 l-l 11 11 11 
 
 Design 1 is therefore identical with the long-known stored borrow subtracter 
 of Equations (3). The state assignment for design 1 is equivalent to giving 
 a. a weight of -1 and a. a weight of +1 (Table 2). Correspondingly o. has 
 weight -2 and s. has weight +1, so that 
 
 -2a. . + s = a -m - Oi , 
 
 l-l l l l i 
 
 which is equivalent to Equation (2) interpreted for the stored-borrow 
 modification. 
 
 The combined equations for design 2 can be written as 
 
 s. = a . © m. © (oi. . v a. . m. , ) 
 
 l i^i l+l i+I i+I 
 
 a. = (a. © m. )(a. . v e m ) 
 
 i i i i+I i+I i+I 
 
 indicating that design 2 is identical with the long-known stored-borrow 
 
 subtracter of Equations (6). The state assignment for design 2 is equivalent 
 
 to giving GC. and a. weights of -2, and a. and s weights of +1, with the value 
 11 11 
 
 -2 excluded (corresponding to o. f 1, s. = 0), 
 
 Designs k and 7 , which are identical, are minor variations of design 
 
 2. In these designs, b. ©d. = a. ^ s., whereas in design 2, b. ©d. = s.. In 
 
 ^11 i i' ' l l i 
 
 effect the OR operation needed to complete the EXCLUSIVE OR in the upper 
 addition table is supplied in the formation of d. in the lower addition table. 
 Design 8, if a. and s . . are complemented, becomes the Boolean dual of designs.^ 
 and 7. Design 5 is equivalent, under negation' of a., to the Boolean dual of . 
 design 2. 
 
 Designs 6 and 9 appear too complicated to warrant further discussion. 
 
 Design 3 is believed to be new. The state assignment for design 3 
 is equivalent to Oi. and a. being, respectively, the sign and magnitude of a . 
 This design is therefore referred to as the stored sign subtracter. 
 
 -10- 
 
7. FURTHER DESIGN CONSIDERATIONS 
 
 Frequently when stored-borrow subtracters are employed, 
 separate circuitry is provided for conversion, or assimilation, of the 
 redundantly represented digits to conventional form. In Figure 1 for a 
 binary subtracter, the lower addition table can be used for assimilation 
 with a. the digit to be assimilated, m. the incoming propagating borrow, 
 rb. the outgoing propagating borrow, and d. the assimilated digit. Thus, 
 the complexity of the assimilation circuitry is indicated by the design 
 equations for the lower addition table in Table 3° The relative difficulty 
 of assimilation for design 1, discussed earlier, is clearly apparent. 
 Designs 2 and 5 are the simplest, with designs 3j ^> 1> and 8 only slightly 
 more complex. 
 
 Although conversion of a subtracter into an adder is usually 
 performed by complementation of each digit m. , with borrow insertion in 
 the least significant digit, an alternative approach is advantageous in 
 
 some circumstances. Let s, a, and m be the numbers represented by all 
 
 ■* -* * * 
 
 digits s„, a . and m , respectively. If the values of s and a are 
 
 1 i' 1 * l * i * 
 
 symmetric, then -s and -a can be formed by replacing s. by -s. and a. by 
 
 * ill 
 
 -a. in each digital position. Since s - a - m, the result of these 
 
 negations is -s = -(-a - m) = a + m, that is, an addition is performed. 
 This approach has potential advantages in some variable field length 
 operations, since it does not require any special operations on the least 
 significant digit. The stored sign subtracter of design 3 is simplest for 
 this operation, since negation of each digit requires only the complementation 
 of its sign digit. 
 
 An advantage of the deterministic procedure described is that 
 statistical calculations can be made at the first stage of design, and, if 
 interpreted properly, apply to all descendents of that design. For example, 
 the probability of the center digit (l for the normalized digit set; for 
 
 v * 1 
 
 the symmetric digit set) of the sum digit set s. is always — if the two 
 
 values of m. are equally likely, independent of the probabilities of the values 
 
 of a. 
 
 i 
 
 tt - l 
 
 ■11- 
 
8. SUMMARY AND CONCLUSIONS 
 
 A deterministic procedure has been described which begins with 
 a single normalized digit set structure for a carry-save adder which 
 leads to three algebraic structures. Each of these three result in nine 
 logical designs, one group of which has been described. Of the nine, two 
 have been known for many years, four are minor variations of these, two 
 are new but appear impractical, and one is new and appears to be of 
 potential value for some variable field length systems. 
 
 The digit set approach has been employed for the study of more 
 complicated binary structures, including three level adders in which both 
 addend and augend are three-valued, and for the study of higher radix 
 structures. The carry-save adder described here is simple and unusually 
 tractable in comparison. 
 
 •12- 
 
BIBLIOGRAPHY 
 
 1. Rohatsch, Fredrich A., "A Study of Transformations Applicable to the 
 Development of Limited Carry-Borrow Propagation Adders", Ph.D. Thesis, 
 University of Illinois, Urbana, Illinois, June 1967. 
 
 2. Atkins, Daniel E., "The Theory and Implementation of SRT Division," 
 M.S. Thesis, University of Illinois, Urbana, Illinois, June, 19^7 > 
 PP. ^9-53. 
 
 ■13- 
 
ACKNOWLEDGMENTS 
 
 The use of transformations from normalized digit sets and 
 the development of systematic procedures for finding limited carry 
 propagation adders subject to specified operand and sum digit sets is 
 based on the work of Dr. Fred Rohatsch. The author is grateful to 
 Dr. Rohatsch for many productive discussions on the subject matter of 
 this paper. 
 
 The inspiration for the research on which this paper was based 
 was provided by the discovery in July, 19^5 > of a stored sign symmetric 
 adder (Table 1, line 2 with the format of design 3? Table 2) while the 
 author was a summer employee of Bell Telephone Laboratories, Whippany, 
 New Jersey. The author is grateful to his associates during that period 
 for many stimulating conversations relevant to this paper. 
 
 The stored sign subtracter (Design 3 of Table 3) is being used 
 in the arithmetic unit of Illiac III at the University of Illinois. The 
 author is grateful that this design is encountering the practical tests 
 of a physical realization in hardware. The onerous tasks of conversion 
 
 from a logical design into a physical realization have been performed by 
 
 2 
 Mr. Daniel E. Atkins. 
 
 ■Ik