Created it, 06/09/09
Update it, 06/09/21
N° Visitors
7. - OPERATIONS IN THE NUMERICAL MACHINES
7. 1. - ADDITION IN THE NUMERICAL MACHINES
In chapter 5.2. , we saw the principle of the binary addition. In the numerical systems, there is no difference and it constitutes the basic operation.
It is carried out starting from simple cells (logical operators) which constitute the circuits of combinatory logic.
The table of the binary addition (figure 14) corresponds to the truth table of the operator OR EXCLUSIVE.
Into binary, if the following sum is carried out: 1 + 1 = 10
The least significant digit (C.L.M.S.) is one 0 (result corresponding to the part in cyan of figure 14). The most significant digit (C.L.P.S.), which constitutes the carryforward is 1.
The C.L.M.S. is given by the exit of the exclusive-OR gate, while the carryforward, or C.L.P.S., is provided by the exit of the circuit AND.
The diagram of this adder is given on figure 31 like its truth table. It relates to the addition of two numbers of a bit.
This representation supposes that this adder cannot receive any external carryforward, resulting from a former calculation.
It is seldom the case and to standardize the circuits, one considers an additional entry corresponding to this carryforward.
The circuit becomes that of figure 32 with its truth table.
The operation carries on two numbers of a bit each one.
The numbers comprising more bits are added with the same manner. Each adder will see on its entries of the identical bits of weight.
Figure 33 gives the diagram of a bearing adder on two numbers of four bits into normal binary or natural. The first number being formed of the bits a0, a1, a2, a3 and the second number of b0, b1, b2, b3. It is not here question of signed numbers, multiple precision or floating point.
The adders requiring a great speed of operation are designed a little differently. They take the name of adders with carryforward anticipated in opposition to that which we have just described where the carryforward is with propagation series.
On these adders with anticipated carryforward, this one is recomputed for each stage according to the preceding binary characters.
7. 2. - THE SUBTRACTION
We wrote at the beginning of this chapter that it would be interesting to use a universal procedure which would be used for all the operations. It is a wish which would facilitate the things well. Since we have just described the addition, let us see whether these circuits cannot be useful for the subtraction.
We know that the complement with 2 (that one represents by C2) is used to represent the negative numbers.
To carry out a subtraction amounts carrying out an addition whose second term is negative.
Moreover, it should be known that in the numerical systems, the words have all the same format. This format corresponds to the length of the registers.
Example :
In a system working on words of eight bits, the decimal number (+ 4) is in the form: 0000 0100.
The decimal number (- 9), in the representation of the negative numbers by C2, is in the form : 1111 0111.
, By same format, the fact is heard that these numbers use for their representation eight bits. Let us see what occurs with an example.
That is to say to withdraw (+ 4) (+ 9).
(+ 9) Þ 0000 1001
- (+ 4) becomes (- 4) Þ 1111 1100
Figure 34 represents this operation.
The overflow or going beyond is ignored because it falls apart from the storage capacity from the register which comprises only eight cells (thus eight binary characters: eight bits).
The most significant bit is one 0, as it indicates the sign of the absolute value, this number is positive and, consequently, the found numerical value corresponds to that of the result.
What does it occur when the second term is, in absolute value, larger than the first ?
That is to say to withdraw (+ 9) (+ 4), figure 35 shows this operation.
The result gives a number having one 1 to the B.L.P.S. (the most significant bit), therefore a negative value.
Since we chose the representation of the numbers by the complement with 2, if the sign is negative, the numerical value which follows can be only the complement with 2 of the required number.
Let us transform into decimal :
11111011 Þ C2 Þ 00000101 Þ (- 5) 10
If this result must be used for other calculations, it will remain in the machine in the form of complement with 2.
If this result constitutes the end of a calculation, before sending it on a bill-poster in order to visualize it (case of a calculator), it will be necessary to carry out the complement with 2 of the result then switching this one and signs it with the corresponding bill-posters.
The complement with 2 and the negative sign (-) are related one to the other.
For example, if we enter, always in the case of a calculator, a first number, it will be stored in binary format.
Before introducing the second number, we indicate the sign of the operation. If it is about an addition, the second term will be stored in a second register in the same form as the first.
If it is about a subtraction, the fact of introducing the sign -, using the keyboard, starts the procedure of complementation.
Once the operation carried out (after having pressed on the key “=”), if the B.L.P.S. is one 1, the procedure of complementation is committed before the sending of the result towards posting.
Put aside the procedure of complementation on the second term or the result, we use for the subtraction the same circuit summer as that described figure 32.
The complementation with 2 is obtained starting from the information contained in the register and on which one must proceed to this complementation.
In general, these registers have two exits, one is the recopy of the number previously entered, the other corresponds to the complement with 1 of this number (these circuits will be described to you in a lesson which is devoted to them).
This second exit is directed, if necessary, towards an adder. In this one, to the complement with 1, is added 1 in order to obtain the complement with 2.
Figure 36 illustrates this method.
For the moment, it is question only principles used in the numerical systems to carry out the operations.
These principles are somewhat different from the basic arithmetic operations, this is why it precise details should be brought there, but it is not yet time to approach the practical realization and the detailed description of the diagrams.
The exit complement to 1 of the register is sent in an adder. In this last, one adds 1 to the complement with 1 to obtain the complement with 2.
7. 3. - MULTIPLICATION
The two operations which will follow, multiplication and division, are given as example, because the practical procedure is sometimes rather complex and several methods are used. However, they are connected with those described below.
We know, since chapter 5.6. that the binary multiplication is a succession of additions whose terms are recopies of the multiplicand successively shifted.
There still, we note a common point with the two preceding operations : addition.
In the subtraction, it is necessary to carry out, in addition to the addition, the complement with 2.
In the multiplication, the additional operation consists of a shift of the partial results before the addition.
Example: That is to say to multiply (+ 25) by (+ 5). We consider that the numbers are represented in the machine by words of eight bits and the negative values by the complement with 2.
_par_(+5)_en_binaire.gif)
Figure 37 shows the course of this multiplication.
.gif)
The B.L.P.S. is 0, therefore the number is positive and the numerical value represented by the seven following bits corresponds to the absolute value of the result :
1111101 Þ |125|
Since the number is positive, the result is: (+ 125).
The part corresponding to the overflow is ignored since the register of storage comprises only eight basic cells.
Let us see what occurs if one of the two numbers is negative :
That is to say to multiply (+ 25) by (- 5). Figure 38 represents this new multiplication.
.gif)
Here, the operation was voluntarily continued in the overflow part. In practice, this part of the operation cannot be carried out (because the length of the registers).
The B.L.P.S. is to 1, consequently, it is about a negative number and such a number is represented by its complement with 2.
To find the value absolute of the result, it is necessary to carry out the complementation with 2 (C2).
That is to say : 10000011 Þ C2 Þ 01111101
The absolute value is |125|, the sign being negative, we find for result : (- 125).
With two examples, one realizes that the notation in floating point and multiple precision is a need because one is quickly limited in calculations when one works only on words of eight bits or bytes.
In short, for the multiplication, while starting with the B.L.M.S. of the multiplier, with each time one meets one 1, one recopies the multiplicand and one shifts it of as many rows towards the strong weights (towards the left) that the weight of the multiplying bit.
In practice, one does not carry out the multiplication by 0. One thus gains a cycle in the procedure, which results in a light saving of time.
The shift towards the strong weights is also carried out in the registers. In fact, instead of a white, as in the example, each partial result is stored in a register and one pushes the contents of this one towards the strong weights by introducing with the B.L.M.S. one 0.
The registers are circuits very important in electronics. They belong to the circuits known as : sequential.
In addition, the shift towards the strong weights is used, as into decimal, for the multiplication by a power of the base.
Example :
into decimal :
.gif)
into binary : That is to say to multiply 0110 by 010.
0102 is a whole power of base 2 (into decimal 0102 = + 2101).
Figure 39 shows this multiplication.
.gif)
In this example, we carried out the product by the 0 of the B.L.M.S. On the other hand, one did not do it for the 0 of the B.L.P.S. or bit of sign.
Moreover, the shift is here of a row towards the strong weights since 102 Þ 2101. The exhibitor of the power of 2 indicates the shift.
We could have taken in the place of 102, 10002, that is to say 2103. The result is, in this case :
0110 x 01000 = 0110000
The shift is here of three rows towards the higher powers.
7. 4. - DIVISION
Since it constitutes the arithmetic operation most delicate, the procedure used in the machine does not simplify it therefore.
It is wise to know the mechanism of it. However, if this last is not very quite comparable, that does not involve annoying consequences for the continuation of the program. It will be always time to reconsider this subject when good seems to you.
We use for this operation, the adder, the complement with 2 (addition and complement with 2 = subtraction), the shift, the research of the row occupied by the bit with 1 of the highest weight of the divider, the test of the bit of sign, the comparison of numerical size and, of course, memorizing or storage.
We will carry our example on following division :
010101 / 011
These numbers, once stored in the registers with eight bits arise in the following form :
00010101 - dividend
00000011 - divider
The sign of the operation, or operator, is also stored in a register, especially intended to this end, in the form of a binary word.
For this operation, there is a preliminary procedure which one starts by the introduction of this operator and who consists in recognizing the row occupied by the bit with 1 of the highest weight of the absolute value of the divider.
This operation can be carried out according to the illustrated principle figure 40 and which we will describe.
One recognizes there the register of storage which familiar, is followed to us of a multiplexer ordered by a discounting machine and an operator AND that you know.
The multiplexer and the discounting machine will be described in detail in the following theories. Will know, for the moment that the multiplexer is a circuit in which each entry is joined together at the common exit by a switch (bipolar transistor or MOS).
The closing of each one of these switches is obtained by binary data, present at the entry of the multiplexer.
This information can order one switch at the same time.
The binary data are obtained, in our case, by a discounting machine.
The rate/rhythm of countdown is obtained by a signal of clocking applied to an entry of the discounting machine.
This circuit has one second entry, connected at the exit of the operator AND, who stops the countdown as soon as this one passes at the logical level 1.
Information at exit of the discounting machine is appeared as a number at n bits ; in this case, three bits are enough because we deduct 7th rank with the 1st rank (of 1112 to 0012). This number is coded in binary format naturalness such as figure 41 shows it.
As soon as the entry “stop countdown” passes to 1, the calculation is stopped, and the reading of the binary data, present at exit of the discounting machine indicates the row of the bit to 1 of the highest weight of the absolute value of the divider. The eighth rank, which corresponds to the sign of the absolute value, is not taken into account for the moment.
This information is put in memory and the operation of complementation can be carried out, because the sign memorized in the register of the operator (here division ; /) the research of the complement with 2 of the divider implies.
Are from now on present in the machine :
The dividend Þ 0001 0101
The divider Þ 0000 0011
The row of the bit with 1 of the highest weight Þ 010
The complement with 2 of the divider Þ 1111 1101
In decimal division, we seek to know how much time the divider is contained entirely in the number formed per as many figures of the most raised weights, that the divider contains.
In other words, one withdraws the divider of the highest weights of the dividend. We carry out this operation mentally, but the digital circuits cannot proceed thus.
It is the reason of this research concerning the bit with 1 of the highest weight of the divider. We carry out the subtraction by an addition of the complement with 2 and if the bit of sign is one 1, the result is negative, that wants to say that the subtracter term has an absolute value larger than that of the withdrawn term. One deduces from it that the subtracter, in this case, is not contained in the formed number of the strongest weights of the dividend.
We, consequently, are obliged in this operation to take into account the bit of sign.
The preceding operation which enabled us to know the row of the bit with 1 of weight more raised, does not take account of the bit of sign.
For this purpose, to the binary data present at exit of the discounting machine, we must add a row.
Information present in the machine is :
The dividend Þ 0001 0101
The divider Þ 0000 0011
The row of the bit with 1 of weight more raised, increased of a row for the sign Þ 011
The complement with 2 of the divider Þ 1111 1101
Of course, the sign of the operation also remains present him, in the register operator.
From now on, we can begin the operation.
The provision of the operation requires an explanation. We sought the row containing the most significant digit of the divider, plus a row for the sign, in order to be able to withdraw the divider (in our case, to add its complement with 2), of the figures of the highest weights of the dividend, to know if it is contained entirely in this last. This procedure enables us to shift the complement with 2, towards the left, in order to align it under the same number of rows, of the highest weights of the dividend, that it contains itself of it.
Let us return to the operation.
The figure 42-a shows the first phase of the operation.
a) 1st phase :
It is necessary to test the bit of sign to know the result of the operation. This is relatively easy to obtain, it is enough, as in figure 40, to use a logical operator AND on which one sends the bit of sign on one of his entries and one 1 on the other.
As soon as the bit of sign passes to 1, the exit of the operator AND takes state 1.
When this exit is with state 1, that means that the divider is not contained in the number formed by the figures of the highest weights of the dividend.
In this case, as for decimal division, we will constitute a new number with an additional figure of row to the dividend.
That amounts shifting, towards the left, the dividend.
The divider not being contained in the first terms of strong weights of the dividend, the first figure, of the highest weight, the partial quotient is : 0.
After this first phase, the partial quotient arises in the form :
0 …….
b) 2nd phase :
The dividend is shifted once towards the left (figure 42-b).
The bit of sign of the remainder is to 1, therefore the result is negative, the divider is still not contained in the terms of strong weights.
The partial quotient becomes : 0 0….
New shift of the dividend.
c) 3rd phase :
The figure 42-c shows the operation after two shifts on the left dividend.
Result identical to the first two phases. The bit of sign of the remainder is still to 1.
The new partial quotient is thus : 0 0 0….
d) 4th phase :
After a new shift on the left, the operation arises as shown in the figure 42-d.
There, the bit of sign is 0, which means that the divider is contained in the terms of the highest weights of the dividend.
The partial quotient becomes : 0 0 0 1….
The successive additions will not relate any more to the dividend but on the remainder (as into decimal), the operation of shift continues on the absolute value of the remainder.
Before continuing, it should be made sure that the absolute value of the remainder is higher than the absolute value of the complement with 2 of the divider. This circuit of comparison is described to you a little further.
Thus if the absolute numerical value of the remainder is larger than that of C2 of the divider, the operation continues.
e) 5th phase :
The operation thus continues with, like new dividend, the preceding remainder shifted once on the left (figure 42-e).
The bit of sign is to 0, from where the new partial quotient : 0 0 0 1 1.
Shift towards the left, of the absolute value of the remainder.
Comparison of the numerical sizes.
The remainder is larger than C2 of the divider, the operation continues.
f) 6th phase :
The operation continues with the remainder shifted twice towards the left (figure 42-f).
The bit of sign is to 0, the new quotient has as a value: 0 0 0 1 1 1.
Shift towards the left, of the absolute value of the remainder and comparison of the numerical sizes. The absolute value of the shifted remainder is lower than that of the complement with 2 of the divider, the operation stops. Here, the absolute value of the remainder is equal to 0, the quotient is exact and the last bit obtained with the partial quotient constitutes the B.L.M.S. of the quotient (the weakest weight).
In the register of storage of the quotient, the result arises in the following form : 0000 0111.
At the time of the last comparison between the absolute values of the remainder and C2 of the divider, we had a result lower for the remainder and equal to 0.
This result could have been lower, but nonequal to 0, and, in this case, division stops, but comprises a remainder. The quotient is then an approximate quotient.
Division relating to fractional numbers is also possible, but the notation in floating point is preferable and facilitates the procedure with regard to the position of the comma.
Division is then carried out on the mantissas and the value of the exhibitor is found by withdrawing that of the divider of that of the dividend.
Into decimal, that returns to the following example :
That is to say to divide 0,125 by 3 :
0,125 = 0,125 x 100
3 = 0,3 x 101
Division carried out on the mantissas :
(+ 125) / (+ 3) = (+ 42)
Difference of the exhibitors:
(0) - (+ 1) = (- 1)
Result in notation floating point :
(+ 42) (- 1)
Transformation into decimal:
(+ 42) (- 1) = 0,42 x 10-1 = 0,042
The principle which one has just described recalls the broad outline of the division carried out in a numerical system, sometimes because the smallest details, consigned in writing or carried out mentally, are the subject of a complex assembly of circuits for their development.
Moreover, the manufacturers of calculating machine and, generally, those who are brought to carry out such circuits, which it acts of cabled or microprogramed logic, use processes which are clean for them, but that they seldom reveal.
In any case, the core operator remains the adder.
The procedures necessary, with the good control of the result, for the described operations are :
memorizing
addition
complementation with 2
the research of the row occupied by the bit with 1 of the highest weight of a number
the test of the bit of sign
the comparison of numerical sizes.
The test of the bit of sign, using the operator AND allows us, while reversing (i.e. by taking the complement with 1), the result available at exit of the operator, to extract the absolute value from the quotient. It is thus the reversed exit of the operator AND who will be used to charge the absolute value of the quotient in the register intended for this use.
We, during these descriptions, spoke about ignored overflow. In fact, this overflow is not always ignored, it is even sometimes stored in a register and is used, amongst other things, to indicate a capacity overshooting. In the microprocessors, a special register called register of state, gathers a certain number of indications of this kind which one can test constantly in order to give a different orientation to the following procedures where necessary.
Figure 43 represents the switching functions necessary to the realization of a comparator of numerical sizes. This is summarized in figure 44 which schematize a comparator of numerical sizes relating to two binary numbers a and b of a bit each one.
At the beginning of this chapter, we had wished only one procedure for all the operations. Now that we know the problem better, in the case of see whether one can obtain this procedure, a very simplified computer, which could carry out only additions and subtractions on relative entireties.
Let us draw up the list of the various operations which this machine will have to carry out.
Position of waiting of information or examination of the keyboard of entry.
Entry of the absolute value of a decimal number using the keyboard :
Transformation of this value into binary and put in memory.
Entry of the affected sign to this absolute value :
Sign +, to put the bit of sign at 0
Sign -, to carry out the complement with
2.
To memorize the signed number obtained in
and .
Entry of a sign operator by the keyboard. To memorize this sign.
Entry of the sign “=”. Departure of
the operation.
The recognized sign
is that of the addition :
To add the terms memorized in.
The recognized sign
is that of the subtraction :
To carry out the complement with 2 of
the last entered number and to add this complement with the first
entered term.
To memorize this result.
To carry out the test of the bit of sign :
If it is equal to 0, the result is
positive, no modification on the result memorized in .
If it is equal to 1, the result is
negative, to replace the term memorized in
by its complement with 2.
To post the result memorized in .
The chronology of the operations is thus that represented figure 45.
It appears more clearly than only,
the operations
and
are somewhat different between the addition and the subtraction. It is about an
addition but for
one of the two terms is complémenté to 2.
If one wanted to extend the possibilities of this machine to the multiplication and division, it would be necessary to introduce the shift, the numerical test of size and to seek the row of the bit with 1 of the highest weight.
The list of the operations would be a little longer, but the speed with which they are carried out would differ only from very little time obtaining result.
This theory is now finished. We remind to you that if you did not assimilate the part concerning calculations perfectly, this is not of fundamental importance for the comprehension of the following lessons. Besides we will have the occasion to return there in the theories concerning the microprocessors.
The next lesson will treat registers with shift whose we already evoked the role in this theory.
Click
here for the following lesson or in the synopsis envisaged to this end. |
High
of page |
 Preceding
page |
Following
page |
