Analyze the 4-bit SN74181 ALU chip by completing the table shown below. Given th
ID: 3674644 • Letter: A
Question
Analyze the 4-bit SN74181 ALU chip by completing the table shown below. Given the operands supplied to A = 1001 and B = 0110 in two's complement (as arithmetic data) or unsigned binary (as logic data) representation, and C-1 equal to 0 or 1 in two different cases, analyze the ALU operations involved in this case by calculating manually the output produced by the ALU
If C-1 = 1 For F3 F2 F1 F0, If C-1 = 0 Cout For F3 F2 F1 F0
M S3 S2 S1 S0 F3 F2 F1 F0 F3 F2 F1 F0 C3 function Description
1 0 1 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 1 1
1 1 0 0 0
0 0 0 0 0
1 1 0 0 1
1 0 0 0 1
0 1 1 1 1
0 0 0 1 1
1 1 0 1 0
1 1 1 1 0
0 0 1 1 1
0 0 0 0 1
1 1 1 1 1
Please give an explanation how to ge the solution
Explanation / Answer
THE ESSENCE OF THE 6800 MICROPROCESSOR Decimal Natural binary Hexadecimal Binary 00 00000 00 0000 0000 01 00001 01 0000 0001 02 00010 02 0000 0010 03 00011 03 0000 0011 04 00100 04 0000 0100 05 00101 05 0000 0101 06 00110 06 0000 0110 07 00111 07 0000 0111 08 01000 08 0000 1000 09 01001 09 0000 1001 10 01010 0A 0001 0000 11 01011 0B 0001 0001 12 01100 0C 0001 0010 13 01101 0D 0001 0011 14 01110 0E 0001 0100 15 01111 0F 0001 0101 16 10000 10 0001 0110 17 10001 11 0001 0111 18 10010 12 0001 1000 19 10011 13 0001 1001 20 10100 14 0010 0000 Table 1.3 Different ways of representing the quantities decimal 0…20. 1s. As might be expected, arithmetic in such a hybrid system is difficult, and BCD is normally converted to natural binary at the system input and processing is done in natural binary before being converted back (see Program ?? on page ??). The rules of arithmetic are the same in natural binary6 as they are in the more familiar base 10 system, indeed any base-n radix scheme. The simplest of these is addition, which is a shorthand way of totalling quantities, as compared to the more primitive counting or incrementation process. Thus 2 + 4 = 6 is rather more efficient than 2 + 1 = 3; 3 + 1 = 4; 4 + 1 = 5; 5 + 1 = 6. However, it does involve memorizing the rules 6Sometimes called 8-4-2-1 code after the weightings of the first four lowest columns. DIGITAL REPRESENTATION 7 of addition.7 In decimal this involves 45 rules, assuming that order is irrelevant; from 0 + 0 = 0 to 9 + 9 = 18. Binary addition is much simpler as it is covered by only three rules: 0 + 0 = 0 0 + 1 1 + 0 = 1 1 + 1 = 10 (0 carry 1) Based on these rules, the least significant bit (LSB) is totalized first, passing a carry if necessary to the next left column. The process ends with the most significant bit (MSB) column, its carry being the new MSD of the sum. For example: 96 Augend + 37 Addend 133 Sum 1 Carries 1100000 Augend + 0100101 Addend 10000101 Sum 1 1 1 Carries 0 1 1 4 2 6 8 4 2 1 6 3 1 (a) Decimal (b) Binary 8 2 1 0 1 0 Just as addition implements an up count, subtraction corresponds to a down count, where units are removed from the total. Thus 8 5 = 3 is the equivalent of 8 1 = 7; 7 1 = 6; 6 1 = 5; 5 1 = 4; 4 1 = 3. The technique of decimal subtraction you are familiar with applies the subtraction rules commencing from LSB and working to the MSB. In any given column were a larger quantity is to be taken away from a smaller quantity, a unit digit is borrowed from the next higher column and given back after the subtraction is completed. Based on this borrow principle, the subtraction rules are given by: 0 0 = 0 10 1 = 1 Borrowing 1 from the higher column 1 0 = 1 1 1 = 0 For example: 7Which you had to do way back in the mists of time in primary/elementary school! 8 THE ESSENCE OF THE 6800 MICROPROCESSOR 96 Minuend 37 Subrahend 59 Difference 1 Borrows 1100000 Minuend 0100101 Subrahend 0111011 Difference 1 1 Borrows 0 1 1 4 2 6 8 4 2 1 6 3 1 (a) Decimal (b) Binary 1111 Although this familiar method works well, there are several problems implementing it in digital circuitry. • How can we deal with situations where the minuend is larger than the subtrahend? • How can we distinguish between positive and negative quantities? • Can a digital system’s adder circuits be coerced into subtracting? To illustrate these points, consider the following example: 37 Minuend 96 Subtrahend 41 Difference (59) 1 0100111 Minuend 1100000 Subtrahend 1000111 Difference (0111001) 1 (a) Decimal (b) Binary Normally when we know that the when Minuend is greater than the Subtrahend, the two operands are interchanged and a minus sign is appended to the outcome; that is (Subtrahend Minuend). If we do not swap, as in (a) above, then the outcome appears to be incorrect. In fact 41 is correct, in that this is the difference between 59 (the correct outcome) and 100. 41 is described as the 10’s complement of 59. Furthermore, the fact that a borrow digit was generated from the MSD indicates that the difference is negative, and therefore appears in this 10’s complement form. Converting from 10’s complement decimal numbers to the ‘normal’ magnitude form is simply a matter of inverting each digit and then adding one to the outcome. A decimal digit is inverted by computing its difference from 9. Thus the 10’s complement of 3941 is 6059: 3941 = 6058; +1 = 6059 DIGITAL REPRESENTATION 9 However, there is no reason why negative numbers should not remain in this complement form — just because we are not familiar with this type of notation. The complement method of negative quantity representation of course applies to binary numbers. Here the ease of inversion (0 1; 1 0) makes this technique particularly attractive. Thus in our example above: 1000111 = 0111000; +1 = 0111001 Again, negative numbers should remain in a 2’s complement form. This complement process is reversible. Thus: complement normal Signed decimal numeration has the luxury of using the symbols + and to denote positive and negative quantities. A 2-state system is stuck with 1s and 0s. However, looking at the last example gives us a clue on how to proceed. A negative outcome gives a borrow back out to the highest column. Thus we can use this MSD as a sign bit, with 0 for + and 1 for . This gives 1,1000111b for 59 and 0,01110011b for +59. Although for clarity the sign bit has been highlighted above using a comma delimiter, the advantage of this system is that it can be treated in all arithmetic processes in the same way as any other ordinary bit. Doing this, the outcome will give the correct sign: 0,1100000 (+96) 1,1011011 (37) 0,0111011 (+59) 1 0,0100101 (+37) 1,0100000 (96) 1,1000101 (59) (a) Minuend less than subtrahend (b) Minuend greater than subtrahend 1 From this example we see that if negative numbers are in a signed 2’s complement form, then we no longer have the requirement to implement hardware subtractors, as adding a negative number is equivalent to subtracting a positive number. Thus A B = A + (B). Furthermore, once numbers are in this form, the outcome of any subsequent processing will always remain 2’s complement signed throughout. 10 THE ESSENCE OF THE 6800 MICROPROCESSOR There are two difficulties associated with signed 2’s complement arithmetic. The first of these is overflow. It is possible that adding two positive or two negative numbers will cause overflow into the sign bit; for instance: 1 (a) Sum of two +ve numbers gives ve (b) Sum of two ve numbers gives +ve 1 1,0011 (13!!!) 0,1011 (+11) 0,1000 (+8) 0,1101 (+3!!!) 1,0101 (11) 1,1000 (8) In (a) the outcome of (+8) + (+11) is 13! The 24 numerical digit has overflowed into the sign position (actually, 10011b = 19 is the correct outcome). Example (b) shows a similar problem for the addition of two signed negative numbers. Overflow can only happen if both operands have the same sign bits. Detection is then a matter of determining this situation with an outcome that differs. See Fig. 1.5 for a logic circuit to implement this overflow condition. The final problem concerns arithmetic on signed operands with different sized fields. For instance: 0,0011001 (+25) 0,011 (+03) ???? 1 0,0011001 (+25) 1,101 (03) ???? (a) Extending a positive number (b) Extending a negative number 0,0011100 (+28) 1 1 0,0011001 (+25) 0,0000011 (+03) 0,0011001 (+25) 0,0010110 (+22) 1 1 111 1 1,1111101 (03) Both the examples involve adding an 8-bit to a 16-bit operand. Where the former is positive, the data may be increased to 16 bits by padding with 0s. The situation is slightly less intuitive where negative data requires extension. Here the prescription is to extend the data by padding out with 1s. In the general case the rule is simply to pad out data by propagating the sign bit left. This technique is known as sign extension. DIGITAL REPRESENTATION 11 Multiplication by the nth power of two is simply implemented by shifting the data left n places. Thus 00101(5) << 01010(10) << 10100(20) multiplies 5 by 22, where the << operator is used to denote shifting left. The process works for signed numbers as well: 0,00000011 ( 3) << 0,00000110 ( 6) << 0,00001100 (12) << 0,00011000 (24) (a) +3 × 8 = +24 (b) 3 × 8 = 24 1,11110100 (12) 1,11101000 (24) 1,11111010 ( 6) 1,11111101 ( 3) << << << 0,00000110 (3 x 2) + 0,00011000 (3 x 8) 0,00011110 (3 x 10 = 30) (c) +3 × 10 = 30 Should the sign bit change polarity, then a magnitude bit has overflowed. Some computers/microprocessors have a Arithmetic Shift Left process that signals this situation, as opposed to the standard Logic Shift Left used in unsigned number shifts. Multiplication by non-powers of 2 can be implemented by a combination of shifting and adding. Thus as shown in (c) above, 3 × 10 is implemented as (3 × 8) + (3 × 2) = (3 × 10) or (3 << 3) + (3 << 1) (see also Example ??.2. In a similar fashion, division by powers of 2 is implemented by shifting right n places. Thus 1100(12) >> 0110(6) >> 0011(3) >> 0001.1(1.5). This process also works for signed numbers: >> >> >> (a) +15/8 = 1.875 (b) 15/8 = 1.875 >> >> >> (c) 15/10 = 1.5 1010 1111.0 0001.1 1010 0101 101.0 000.0 1,11110.001 (1.875) 1,1100.010 (3.75) 1,1000.100 (7.5) 0,1111.000 (+15) 1,0001.000 (15) 0,0111.100 (+7.5) 0,0011.110 (+3.75) 0,0001.111 (+1.875) Notice that rather than always shifting in 0s, the sign bit should be propagated in from the left. Thus positive numbers shift in 0s and negative 12 THE ESSENCE OF THE 6800 MICROPROCESSOR numbers shift in 1s. This is known as Arithmetic Shift Right as opposed to Logic Shift Right which always shifts in 0s. Division by non powers of 2 is illustrated in (c) above. This shows the familiar long division process used in decimal division. This is an analagous process to the shift and add technique for multiplication, using a combination of shifting and subtracting. Arithmetic is not the only way to manipulate binary patterns. George Boole8 in the mid-19th century developed an algebra dealing with symbolic processing of logic propositions. This Boolean algebra deals with variables which can be true or false. In the 1930s it was realised that this mathematical system could equally well be used to analyze switching networks and thus binary logic systems. Here we will confine ourselves to looking at the fundamental logic operations of this switching algebra. A f 0 1 1 0 A f = A 1 A f = A (a) Truth table (b) Alternative logic symbols Figure 1.1 The NOT operation. The inversion or NOT operation is represented by overscoring. Thus f = A states that the variable f is the inverse of A; that is if A = 0 then f = 1 and if A = 1 then f = 0. In Fig. 1.1(a) this transfer characteristic is presented in the form of a truth table. By definition, inverting twice returns a variable to its original state; thus f = f. 9 8The first professor of mathematics at Queen’s College, Cork. 9In days of yore when logic circuits were built out of discrete devices, such as diodes, resistors and transistors, problems due to sneak current paths were rife. In one such laboratory experiment the output lamp was rather dim, and the lecturer in charge suggested that two NOTs in series in a suspect line would not disturb the logic but would block off the unwanted current leak. On returning sometime later, the students complained that the remedy had had no effect. On investigation the lecturer discovered two knots in the offending wire — obviously not tied tightly enough! DIGITAL REPRESENTATION 13 Logic function implementations are normally represented in an abstract manner rather than as a detailed circuit diagram. The NOT gate is symbolized as shown in Fig. 1.1(b). The circle always represents inversion in a logic diagram, and is often used in conjunction with other logic elements, such as in Fig. 1.2(c). B A f 0 0 0 0 1 0 A f = B A & A f = B A (a) Truth table (b) Alternative logic symbols 1 1 1 1 0 0 B B (c) NAND 1 1 0 0 0 1 0 1 1 1 0 1 B A f B f = B A A B A & f = B A Figure 1.2 The AND function. The AND operator gives an all or nothing function. The outcome will only be true when every one of the n inputs are true. In Fig. 1.2 two input variables are shown, and the output is symbolized as f = B · A, where · is the Boolean AND operator. The number of inputs is not limited to two, and in general f = A(0) · A(1) · A(2) ··· A(n). The AND operator is sometimes called a logic product, as ANDing (cf. multiplying) any bit with logic 0 always yields a 0 output. If we consider B as a control input and A as a stream of data, then consideration of the truth table shows that the output follows the data stream when B = 1 and is always 0 when B = 0. Thus the circuit can be considered to be acting as a valve, gating the data through on command. The term gate is generally applied to any logic circuit implementing a fundamental Boolean operator. Most practical AND gate implementations have an inverting output. The logic of such implementations is NOT AND, or NAND for short, and is symbolized as shown in Fig. 1.2(c). The OR operator gives an anything function. Here the outcome is true when any input or inputs are true (hence the 1 label in the logic symbol). In Fig. 1.3 two inputs are shown, but any number of variables may be ORed together. ORing is sometimes referred to as a logic sum, and the + used as the mathematical operator; thus f = B + A. In an analogous 14 THE ESSENCE OF THE 6800 MICROPROCESSOR B A f 0 0 0 0 1 1 A f = B + A >1 A f = B + A (a) Truth table (b) Alternative logic symbols 1 1 1 1 0 1 B B (c) NOR 1 1 0 0 0 1 0 1 0 1 0 0 B A f B f = B + A A B A >1 f = B + A Figure 1.3 The OR operation. manner to the AND gate detecting all ones, the OR gate can be used to detect all zeroes. This is illustrated in Fig. 2.16 on page 34 where an 8-bit zero outcome brings the output of the NOR gate to 1. Considering B as a control input and A as data (or vice versa), then from Fig. 1.3(a) we see that the data is gated through when B is 0 and inhibited (always 1) when B is 1. This is a little like the inverse of the AND function. In fact the OR function can be expressed in terms of AND using the duality relationship A + B = B · A. This states that the NOR function can be implemented by inverting all inputs into an AND gate. AND, OR and NOT are the three fundamental Boolean operators. There is one more operation commonly available as an electronic gate; the Exclusive-OR operator (EOR). The EOR function is true if only one input is true (hence the =1 label in the logic symbol). Unlike the inclusive-OR, the situation where both inputs are true gives a false outcome. B A f 0 0 0 0 1 1 A f = B + A =1 A f = B + A (a) Truth table (b) Alternative logic symbols 1 1 0 1 0 1 B B (c) ENOR B f = B + A A B A =1 f = B + A 1 0 0 1 1 1 0 1 0 0 0 1 B A f Figure 1.4 The EOR operation. If we consider B is a control input and A as data (they are fully inter- DIGITAL REPRESENTATION 15 changeable) then: • When B = 0 then f = A; that is the output follows the data input. • When B = 1 then f = A; that is the output is the inverse of the data input. Thus an EOR gate can be used as a programmable inverter. Another useful property considers the EOR function as a logic differentiator. The EOR truth table shows that the gate gives a true output if the two inputs differ. Alternatively, the ENOR truth table of Fig. 1.4(c) shows a true output when the two inputs are the same. Thus an ENOR gate can be considered to be a 1-bit equality detector. The equality of two n-bit words can be tested by ANDing an array of ENOR gates (see Fig. 2.6 on page 23), each generating the function Bk Ak; that is: fB=A = n X1 k=0 Bk Ak As a simple example of the use of the EOR/ENOR gates, consider the problem of detecting sign overflow (see page 10). This occurs if both the sign bits of word B and word A are the same (SB SA) AND the sign bit of the outcome word C is not the same as either of these sign bits, say SB SC. The logic diagram for this detector is shown in Fig. 1.5 and implements the Boolean function: (SB SA) · (SB SC) SA SB SC S = S A B S = S C B V is true if: (Sign A = Sign B) AND (Sign C = Sign B) V Figure 1.5 Detecting sign overflow. Finally, the EOR function can be considered as detecting when the number of true inputs are odd. By cascading n+1 EOR gates, the overall parity 16 THE ESSENCE OF THE 6800 MICROPROCESSOR function is true if the n-bit word has an odd number of ones. Some measure of error protection can be obtained by adding an additional bit to each word, so that overall the number of bits is odd. This oddness can be checked at the receiver and any deviation indicates corruption