Arithmetic and Logic Unit Organisation


  • • To describe the different types of number systems, their numerical representations, and the relationships with each other.
  • • To enunciate in detail
  • • Representation of decimal fixed-point and floating-point numbers in the binary system;
  • • Floating-point representation with its normalized form, including IEEE standards;
  • • Floating-point arithmetic and implementation of the floating-point unit;
  • • Addition and subtraction of signed numbers with overflow consideration.
  • • To explain the basic structure of an ALU (arithmetic and logic unit) with the required hardware elements.
  • • To describe different types of basic adders and subtracters with the overflow design principle and practical high-speed adders, including carry-lookahead adder (CLA) and carry-save adder (CSA).
  • • To explain Booth's algorithm for multiplication of signed and unsigned numbers.
  • • To study the methods for division of signed and unsigned numbers using machine- based algorithms.

Every computer has machine-level instructions that perform numerous arithmetic and logic operations on data operands, both integer and real (floating-point) 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 Systems

The 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 System

The 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 positional-value 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 System

Unfortunately, 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 (base-2) 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 base-2 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 positional-value 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:

Hexadecimal and Octal System

The hexadecimal (in short hex) number system uses 16 possible digit symbols, digit 0-9 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 (= 24), and that of an octal system is 8 (= 23), 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 10-15.

All types of conversions from one to another of all these number systems, including their fractional representations, are given in the website:

Merits of Hex and Octal Systems

Hex 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 error-prone 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 (Binary-Coded Decimal) Code

When 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 binary-coded-decimal (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 10012). In other words, only the 10 combinations out of the 16 possible 4-bit 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 Code

When 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 3-bit 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 3-bit binary and corresponding Gray code values are shown in the website:

Number Representations: Binary Systems

Any arbitrary number can thus be represented with just the binary digits 0 and 1. Ingeneral, if an и-bit sequence of binary digits b„_A-2 ...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 non-negative integers, this representation is simple and straightforward. For example, with a 6-bit 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: • Sign-magnitude; • 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. Sign-magnitude representation, however, suffers from several critical drawbacks, including two different representations of 0 (e.g. + 010 = 000000, and - 010 = 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 Representation

This representation also makes use of the leftmost bit of the binary number to represent the sign. But it differs from the sign-magnitude 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 sign-magnitude, this representation also suffers from the same drawback: the digit 0 here also has two different representations (+ 010 = 000000, and - 010 = 111111).

’s (Two’s) Complement Representation

In order to alleviate the limitations and drawbacks of the above-mentioned 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, bn _ 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, bn _,, 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" ~ 1bll _, = (), and the above equation then reduces to the usual definition of a non-negative integer. For negative numbers, the sign bit bn _ г = 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 Versa

The 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 8-bit 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 carry-out 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 of-128) when are made 2's complemented, the same number (including the sign) is once again obtained, which is definitely an abnormality.


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 m-bits where m>n. The prescribed rule for converting 2's complement n-bit integers to m-bit 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.

  • [1] 2's (two's) complement.

    Sign-Magnitude Representation

    While positive values have identical representations in all systems, negative values havedifferent representations. However, all of them involve treating the most significant(leftmost) bit being reserved to represent the sign of the number (known as sign bit), andthe remaining (и - 1) bits in the и-bit number indicate their magnitude. If the sign bit is 0,the number is positive. Negative values are represented by changing the most significantbit from 0 to 1 in bit sequence of the corresponding positive value. The simplest form of representation that employs a sign bit is known as sign-magnitude representation in which the

< Prev   CONTENTS   Source   Next >