Home Computer Science



Arithmetic and Logic Unit OrganisationTable of Contents:
LEARNING OBJECTIVES
Every computer has machinelevel instructions that perform numerous arithmetic and logic operations on data operands, both integer and real (floatingpoint) numbers, as well as characters and character strings given in the program to accomplish various tasks. To understand how these operations are being carried out, one should first know how numbers and characters are represented in a computer, and how they are then manipulated by appropriate algorithms for basic arithmetic and logic operations. The most natural way to represent a number in a computer system is straightaway by a string of bits, called a binary number, and a text character similarly can also be represented by a distinct string of bits called a character code. Numerical Representations: Number SystemsThe numerical values of various quantities used in every sphere of life are basically represented in two ways, namely analog and digital. But we are, at present, concerned only with the issues related to digital number systems. However, number can also be expressed in many different ways using different numbering system: the most common ones are the decimal, binary, octal, and hexadecimal systems, yet the decimal system is the most familiar one because of its everyday use. Moreover, conversions between each of these number systems are most regular and are often carried out to accomplish various tasks. Decimal SystemThe decimal system is composed of ten different numerals or symbols or digits, such as 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, and as such, the base or radix(r) of this decimal system is 10. It is a positionalvalue system in which the value of a digit depends on its position. The various positions of the digits in the number relative to the decimal point carry different weights that can be expressed as powers (both positive and negative) of 10, the radix. The presence of decimal point, however, actually separates the positive power of 10 from its negative powers. However, the value of a number in decimal system is then calculated by summing up all multiplied values, individually of each digit with an integer power of 10 (the radix). In general, any number is simply the sum of the products of each digit value and its positional value. Binary SystemUnfortunately, the decimal number system seems to be not suitable to lend itself to convenient implementation in digital systems. Almost every digital system uses the binary (base2) number system as the basic number system for its operations. Other number systems, however, are often used to interpret or represent binary quantities for the convenience of the users who work with these digital systems. In the binary system, there are only two symbols or possible digit values, 0 and 1 (don't confuse this 0 and 1 with the decimal 0 and 1), and hence, the radix or the base of this system is 2, and the binary digit is often abbreviated to the term bit. Even with such a relatively small base, this base2 system can be used at ease to represent any quantity that can be represented in decimal or in other number systems. The binary system is also a positionalvalue system, wherein each binary digit has its own value or weight expressed as a power of 2 (the base or radix). All types of conversions from binary to decimal and decimal to binary, including their fractional representations, are given in the website: http://routledge.com/9780367255732. Hexadecimal and Octal SystemThe hexadecimal (in short hex) number system uses 16 possible digit symbols, digit 09 plus the letters А, В, C, D, E, and F, and hence, it has the base 16. The digit positions as usual are weighted as powers of 16. The octal system uses eight possible digits, namely 0, 1,2,3,4,5,6, and 7, and hence, it implies base 8. The digit positions here are thus weighted as powers of 8. Similar to the decimal system, here also the value of a number in both the systems is calculated by summing up all multiplied values, individually of each digit with an integer power of their respective base (radix, r). The relationship between hexadecimal, octal, decimal, and binary number systems is simple. Since the base of the hexadecimal system is 16 (= 2^{4}), and that of an octal system is 8 (= 2^{3}), each hexadecimal digit represents a group of four binary digits and each octal digit represents a group of three binary digits. It is important to note that hex digits A through F are equivalent to the decimal values 1015. All types of conversions from one to another of all these number systems, including their fractional representations, are given in the website: http://routledge.com/9780367255732. Merits of Hex and Octal SystemsHex and octal systems are often used in a digital system as one kind of a shorthand way to conveniently represent strings of longer sequence of binary digits (bits) in situations when human involvement is associated. Since, in today's computer environment, bit strings as long as 64 bits are not very uncommon, it is more convenient and less errorprone to write the binary numbers in hex or octal, and it is then relatively easy to convert back and forth between binary and either hex or octal. The conversion can be executed relatively quickly without going through any intermediate computations that make one to realize the effectiveness as well as the usefulness of this tool in digital systems. BCD (BinaryCoded Decimal) CodeWhen numbers, letters, or words are represented by a special group of symbols, it is said to be encoded, and the group of symbols is simply called a code. All digital systems use some form of binary numbers for their internal operation, but the external world is still decimal in nature. This requires frequent conversions between decimal and binary systems that become quite complicated and even long for large numbers. For this reason, a means of encoding decimal numbers that combines some features of both the decimal and the binary systems is used in certain situations. If each digit of a decimal number is represented straightaway by its binary equivalent, the result is a code, called binarycodeddecimal (hereafter abbreviated as BCD). Since a decimal digit can be as large as 9, four bits are required to code each decimal digit, and only the four bit numbers from 0000 through 1001 are used (the binary code of 9 is 1001_{2}). In other words, only the 10 combinations out of the 16 possible 4bit binary combinations are used here as code groups. As a result, BCD code always requires more bits than the straight equivalent binary code of a decimal number, and is therefore somewhat inefficient. To illustrate the BCD code, take a decimal number 235, in which each decimal digit is changed to its corresponding binary equivalent to express it in BCD code, and side by side, its straight binary equivalent is also shown. It is important to note that BCD is not another number system such as decimal, binary, octal, and hexadecimal. In fact, it is precisely the decimal system with each decimal digit converted to its binary equivalent, without considering the number as an entity; whereas, the binary representation of a decimal number takes the complete decimal number by value and represents it in binary. However, the distinct advantage of the BCD code lies in the relative ease of converting it to and from decimal, and is especially significant from a hardware point of view, because in a digital system, it is the logic circuits that perform the conversions to and from decimal. Gray CodeWhen multiple input conditions in digital circuit are continuously changing almost at the same time at very high speeds, the situation may be misinterpreted, leading to an erroneous outcome. For example, with a 3bit number, when the number 3 (binary Oil) changes to 4 (binary 100), all three bits individually must change their states at the same time. In order to reduce the likelihood of a digital circuit misinterpreting a changing input, and also to facilitate such changes faster, the Gray code has been evolved as a way to represent a sequence of numbers. The unique aspect of the Gray code is that only one bit ever changes between two successive numbers in the sequence. The mechanisms and its related circuits to convert a binary code to its corresponding Gray code, and vice versa, and also a table of 3bit binary and corresponding Gray code values are shown in the website: http://routledge.com/9780367255732. Number Representations: Binary SystemsAny arbitrary number can thus be represented with just the binary digits 0 and 1. Ingeneral, if an иbit sequence of binary digits b„_A2 ...fra>is given, where bk = 0 or 1 for0 < к < n  1, then this sequence can represent unsigned integer values V in the range 0 to2"_1, where For nonnegative integers, this representation is simple and straightforward. For example, with a 6bit sequence (n = 6), it is possible to represent the numbers from 0 to 26  1,i.e. from 0 to 63, as (0 = 000000,1 = 000001, ..., 63 = 111111). Similarly, the negative integersneed to be properly represented along with the positive integers. In fact, out of severalavailable conventions, the following three systems are of common interest to representsuch numbers: • Signmagnitude; • l's (one's) complement;}} ^{[1]} • most significant (leftmost) bit represents the sign of the number, and the rightmost (n  1) bits of an иbit word hold the magnitude of the integer. Signmagnitude representation, however, suffers from several critical drawbacks, including two different representations of 0 (e.g. + 0_{10} = 000000, and  0_{10} = 100000), and as such summarily being dropped from favour while integer arithmetic is implemented in the hardware (ALU) of the computer. ’s (One’s) Complement RepresentationThis representation also makes use of the leftmost bit of the binary number to represent the sign. But it differs from the signmagnitude representation in the way in which the other bits are interpreted. Here, the negative value of a number is obtained by simply complementing each bit of the corresponding positive number, including the sign bit. As a result, all positive integers in this representation have the leftmost bit always equal to 0, and all negative integers necessarily have the leftmost bit equal to 1. While this representation is more or less consistent for all types of integer arithmetic carried out by the hardware (ALU) of the computer, similar to signmagnitude, this representation also suffers from the same drawback: the digit 0 here also has two different representations (+ 0_{10} = 000000, and  0_{10} = 111111). ’s (Two’s) Complement RepresentationIn order to alleviate the limitations and drawbacks of the abovementioned two methods, the most common scheme to represent negative numbers is 2's (two's) complement representation in which the most significant (leftmost) bit is also used here as sign bit. But it differs from the other two methods in the way in which the other bits of the integer are interpreted here. The 2's complement of a positive number is obtained by taking the Boolean complement of each bit of the corresponding positive number (as is done in l's complement), and then adding 1 to the resulting bit pattern viewing it as an unsigned integer. Most important is that the number 0 is identified as positive, and therefore has a 0 sign bit and a magnitude of Os in all remaining bits. For a «bit positive number, the sign bit, b_{n} _ _{v} is always zero, and the remaining bits in the number represent the magnitude of the number in the same manner as usual. Therefore, the range of positive integers that can be represented is from 0 to 2""^{1}  1 (the largest integer is 2" ~^{1}  1, with the sign bit zero, and all of the magnitude bits here are 1). Any large number beyond this range would then require more bits to represent. For a иbit negative number, the sign bit, b_{n} _,, is 1, and the remaining «  1 bits together can take on any one of the 2” ~^{1} values. Therefore, the range of the negative integers that can be represented with « bits is from 1 to 2" ~ b It is always attempted to assign the weight to the bit of negative integer in such a way that arithmetic operation can be handled straightaway. In unsigned integer representation, to compute the value of an integer from the bit representation, the weight of the most significant bit is +2" ~ b For a representation with a sign bit, it turns out that the desired arithmetic properties can be achieved, if the weight of the most significant bit is made 2" ~ b This is the convention used in 2's (two's) complement representation, which finally gives the following expression to symbolize negative numbers:
This equation is ultimately able to define the 2's (two's) complement representation for both positive and negative «bit integers. For positive numbers, the sign bit b„ _, = 0, which makes the term 2" ~ ^{1}b_{ll} _, = (), and the above equation then reduces to the usual definition of a nonnegative integer. For negative numbers, the sign bit b_{n} _ _{г} = 1, which makes the first term to 2" ~^{1} which is to be then added with summation term: i.e. 2" ~^{1} is to be subtracted from the summation term to yield a negative integer. The 2's (two's) complement system is the most efficient method for performing important arithmetic operations, addition and subtraction, although it appears to be a somewhat unnatural representation from the human point of view. Still, it is almost universally accepted for use as the processor representation for all types of integers. Conversion: Decimal to 2’s Complement and Vice VersaThe nature of the 2's (two's) complement representation can be usefully exhibited with the help of a graphical device, like a value box, in which the value on the far right of the box is 1 (i.e. 2°), and each succeeding position to the left is double in value (i.e. the power of 2 is incremented by 1), until the leftmost position which is negated (Figure 7.1a). It is clear from Figure 7.1a that the highest negative 2'scomplement number that can be represented is 2"" b If any of the bits other than the sign bit is 1, it adds a positive amount to the number. Abnormality: Although the 2's complement operation is always valid to derive the negation of any signed integers, there are two unusual cases that should be taken into account. The first one is that the 2's complement (i.e. negation) of number 0 expressed in 8bit representation gives rise to a carry 1 in the ninth bit position. If it is ignored, the correct result is obtained, which means that the negation of 0 is 0 as it should be. Ignoring this carryout is, however, a natural approach in order to obtain the correct result. The second unusual case seems to be even more critical. If a number is taken having a bit pattern of 1 followed by n 1 zeros, the 2's complement operation of this number (i.e. negation) will revert back the same number (including the sign) which should not be. The number 10000000 (2's complement representation of128) when are made 2's complemented, the same number (including the sign) is once again obtained, which is definitely an abnormality. FIGURE 7.1 Value box representation for conversion between 2's complement binary and decimal, (a) An eight position 2's (two's) complement value box, (b) conversion of binary 2's complement value 10000101 to decimal, and (c) conversion of decimal 115 to binary 2's complement value. Conversion between different bit lengths: It is often necessary to represent a number of an яbit integer to another form of mbits where m>n. The prescribed rule for converting 2's complement nbit integers to mbit integers is to move the sign bit to the new leftmost position and fill all other extended bits with copies of the sign bit. For positive numbers, fill in extended bits with zeros, and for negative numbers, fill in those with ones. This action is usually called sign extension. A brief detail with explanation of all these topics is given in the website: http://routledge. com/9780367255732.

<<  CONTENTS  >> 

Related topics 