[MUSIC] This lesson deals with a particular type of circuits, the arithmetic components. Arithmetic components are an important part of practically any digital circuit, and so deserve a particular treatment. In this lesson, we will present an implementation of every basic operation, that is to say, addition, subtraction, multiplication and division. Actually, n-bit binary adders have already been described several times in preceding lessons, so that we will just recall that a possible implementation is this one: an interative circuit, made up of n 1-bit adders. 1-bit adders are generally called "full adders". The circuit computes X plus Y plus an initial CARRY, and the result, S is an (n+1)-bit number, whose most significant bit is the output CARRY of the last cell of the last full adder. Second basic operation, subtraction. Given to number X and Y, n-bit numbers, and an initial BORROW, we want to compute the difference X minus Y minus BORROW. In this case, the result is smaller than or equal to 2**n - 1, which is the case, when X has its maximum value 2**n - 1 and when both Y and the BORROW and are equal to 0. But in this case, the result could also be negative. And the minimum value of the difference is -2**n, the value that we get when X is equal to 0, Y is equal to the maximum value 2**n - 1 and when the BORROW is equal to 1. Then, how can we represent D? If D is non-negative, it's an n-bit number that can be representated in binary, and if D is negative but greater than or equal to -2**n then it can be represented with an additional bit whose weight is negative, that is to say that Dn has a weight equal to -2**n. Then, how works the classical pencil and paper method to compute the difference between two numbers: at each step, we are going to compute two bits, a difference bit and a borrow, an output borrow bit. Actually, the real value of the difference can be equal to 1, 0, -1 or -2. Then, we define the borrow, an output borrow, and a bit d of the difference. If the result, the real result, is 1 no problem: there is no borrow, and d =1. If the result is 0, the same: dout = 0 and d = 0. Then, if the result is negative, first case: the result is -1; then you could write or say that -1 = -2 + 1. So, we will choose a bit of the difference equals 1, but then transmit the borrow to the next step, with a weight equal to the present weight multiplied by 2, so that in this case the borrow - the output borrow - will be equal to 1. You must think that this borrow actually has a negative weight. This is 1 and this is -1 with the weight equal to 2. It's the same as -2. In the same way, in the case where the real result is -2, we will say that -2 is -2 + 0. So, here the bit of the difference is 0, and the borrow is equal to 1, actually it is a negative weight. Observe now that d is equal to the real difference computed modulo 2, because when the real result is odd, the corresponding bit is 1 and when the real result is even, the corresponding bit is 0. And the output borrow bit is equal to 0, when the real result is non-negative, and equal to 1 when the real result is negative. Another comment: the value of x - y - bin modulo 2 is exactly the same as the value of x + y + bin modulo 2, because modulo 2, -1 is the same as 1. Both numbers are odd numbers. Let us see an example: First we compute 12 (decimal 12) minus 9; then we compute in a step by step way: 0 minus 1 is equal to -1. Then the difference bit is 1 and the borrow bit is also 1; 0 minus 0 minus 1 once again is equal to minus 1. Then, here the difference bit is 1 and the borrow bit is 1, with a negative weight; next step: 1 - 1 = 0; next step: 1 - 1 = 0, so that the result is this one (in decimal 3). Now, let us compute, 9 minus 12: 1 - 0 = 1; 0 - 0 = 0; 0 - 1 is -1; then here, the difference bit is 1 and there is a borrow to the next step; 1 - 1 - 1 = -1; once again, difference bit equal to 1 and borrow equal to -1, so that the result is this one, but now the first 1 has a negative weight, and this number is equal to minus 16 plus 8 plus 4 plus 1 and this is minus 3. This type of representation is called 2's complement representation of the negative number. This is the algorithm: it's an iteration (a loop) where at each step, we compute a difference bit, the modulo 2 sum of the three incoming bits, two bits of the operands and one borrow input, and we compute the sign of the difference x(i) minus y(i) minus b(i). Here is the algorithm that we can modify. We can replace this modular 2 sum by the exclusive or sum of x(i), y(i) and b(i), exactly in the same way as in the adders that we have seen before and, as regards the borrow, the computation of the output borrow, we see that it is equal to 1 when (three cases): the bit of x is 0 and the bit of y is 1, or when the bit of x is 0 and the input borrow is 1, or when both the bit of y and the input borrow are equal to 1. In all of those cases, the result of this operation is negative so that the borrow must be equal to 1. The corresponding circuit is this one: an iterative one made up on n identical components, 1-bit subtractors, that are also called full subtractors, and every component, every full subtractor implements those Boolean functions. Now, an exercise: define a circuit that generate the difference, x minus y, without initial borrow in this case, under the classical form with sign and magnitude, that is to say the result D (the difference) is equal to + or - some absolute value (the magnitude of the difference). Then, the proposed method is quite simple. Compute, at the same time, the difference x - y and y - x. If x - y is non-negative, then the sign in equal to 0 and the result is this one. In the contrary case, if x - y is negative, then y - x will be non-negative, and the sign bit will be equal to 1. Here is a possible solution: we use two subtractors, that work in parallel; one computes x - y and the other one computes y - x. If the sign of x - y is 0, then the sign of D is equal to 0, and we select as a magnitude the value D' of the first substractor. In the contrary case, then we will get here a 1, the sign of x minus y is equal to 1. The sign of the result D is equal to 1 also, and we select, as absolute value (as magnitude of the difference) the output of the other subtractor that computes y minus x. Third operation: the multiplication. Given an n-bit number X and an m-bit number Y, we want to compute P equal to X time Y. Then the maximum value of P is smaller than 2**(n+m) so that the result P is a binary number that can be expressed with, at most, n + m bits. Assume now that Y is expressed in binary under this form; then P can be written under this form, and this suggests a very simple algorithm: we compute a set of partial products; P(0) is equal to X·Y(0); P(1) is equal to X·Y(1)·2, and so on, up to P(m-1) equal to X·Y(m-1)·2**(m-1), and once we have computed all those partial products, it remains to add up all the partial product. Actually, the computation of the partial products is very easy: the multiplication of X by bit (for example) Y(2) along can be done with a set of AND gates. Here you have the bits of X, here is the bit Y(i), Y(2) for example. and then we get, at the output of the AND gates, all the bits of X multiplied by Y(2) (for example). And the multiplication by the power of 2 amounts to adding some number of 0's to the right of the corresponding number. To multiply by 2 in binary is as multiplying by 10 in decimal; it is just a matter of adding a 0 on the right side of the number. Let us see an example: assume that we define X = 101101 and Y = to 1011. Then, first partial product: 1 multiplied by X is equal to X. Second partial product: 1 multiplied by X is also equal to X, but with 0 on the right side, that corresponds to multiplying by 2. Third partial product: 0 times 101101 is equal to 0, with two 0's and, finally, 1 multiplied by X is 101101 with three 0's. So, it's very easy to compute all those artial products, and then, it's necessary to compute the sum of all those products, and we get finally the result of the multiplication. Thus, the algorithm is this one: at each step (it's an iteration once again) at each step we must compute the sum of some value ACC plus the product of X by a bit of the second operator Y, and multiply this product by some power of 2, and we already know that this amounts to shifting or to adding 0's to the right of the number. And the result of this computation, is the new value of the variable ACC. Then the corresponding circuit is an iterative one, and at each step we compute (and so on)) this sum, that is to say, adding ACC_IN to X, to some X, multiplied by a bit y of the second operand, and this gives us the new value of variable ACC_OUT. The second operand of every cell is (first time) X, (second time) X·2, X·4, and so on, up to X·2**(m-1). Last operation: division. First, we must define what we call "quotient", "remainder" and "accuracy" of the division. Consider two naturals X and Y, such that X is smaller than Y. Then we must compute the quotient Q and the remainder R, such that X is equal to Q time Y plus the remainder. Furthermore, Q must be a multiple of 2**(-p), where p is the accuracy of the division, accuracy expressed in number of fractional bits of the result, and the remainder R must be smaller than Y multiplied by the same value 2**(-p). A previous operand alignment may be necessary, in order that this condition is satisfied. Assume that X is greater than Y. Thus, what we must do is to substitute Y by Y multiplied by some power of 2, so that the condition (this one) holds true; then we compute X divided by Y multiplied by 2**k, obtain some result and finally we multiply the result by 2**k. In order that the result is obtained with an accuracy of p fractionary bits, this computation must be realized with a precision of p + k fractionary bits. This definition is equivalent to this one: if we divided here by Y, we get that X divided by Y is equal to Q (the quotient) plus R divided by Y, where the quotient is a multiple of 2**(-p), and where the error (the error is the difference between the real value of the division of X by Y and the quotient) this difference is R divided by Y and, according to this condition, is smaller than 2**(-p)). Here is an algorithm that allows to compute the quotient and the remainder. An initial remainder r(0) is equal to X (to the dividend). Then, it's an iteration. At each step, we compute the difference between two times the preceding remainder and the divisor. If the difference is negative, then the corresponding quotient bit is 0 and the new remainder is 2 times the preceding one, but if d is non-negative, then the quotient is 1, and the new remainder is the difference. Then we get the result under this form: Q is equal to the number, expressed in binary with the set of quotient bits that have been computed, multiplied by 2**(-p). In other words, in binary Q is 0.q(1) q(2) ··· q(p) and R is the last obtained remainder when i is equal to p, also multiplied by this negative power. Let us see an example. Assume that X is equal to 21, Y equal 35, and we want an accuracy of 6 factional units. Then we compute, 2 times the remainder: 2 times 21 is equal to 42, is greater than Y. So I can write that 42 is equal to 35 plus 7. First quotient bit 1 and the new remainder is 7. Next step: 2 times the preceding remainder, 2 times 7, 14, is smaller than the divisor; so I can write that 14 is 0 times 35, plus the difference 14, and we follow up: 2 times 14, 28, is smaller than 35, so I write that 2 times 14 is equal to 0 times 35 plus 28 and so on. The result is that Q is the number (in binary) equal to 100110 (that) multiplied by 2 to the power -6 or, in other words, divided (in decimal) by 64, so that the quotient is 38 divided by 64, and in binary it's written under this form, that is to say 100110, but with 0. here on the left side. The remainder is 14 multiply by 2 to the power -6. In other words, 14 divided by 64. In binary: this number, and you can check that, actually, Q times the divisor, 35, plus the remainder divided by 64 is equal to 21 and that the remainder satisfies this condition. Corresponding circuit: once again is an iterative circuit; at each step we must compute a bit of the quotient and a new remainder. It's very easy: we must multiply the preceding remainder by 2; that means to add a 0 on the right side of this number, and then to compute the difference between 2R and Y; if the sign is equal to 0, that means that 2R is greater than or equal (that the result is non-negative) in which case the quotient bit is equal to 1, and the new value of the remainder is the difference. In the other case, if the sign bit of this difference is equal to 1, it means that the difference is negative, then the quotient bit is equal to 0 and the new value of the remainder is the preceeding value multiply by 2. And that's all. Summary of this lesson: We have described circuits that execute the basic arithmetic operations, that means addition, subtraction, multiplication and division, with natural operands (non-negative integers), and we have given some information about 2's complement representation of negative numbers. [BLANK_AUDIO]
