Number Systems PDF

2 NUMBER SYSTEMS 2.1 THE DECIMAL NUMBER SYSTEM We begin our study of the number systems with the familiar decimal number system. The decimal system contains ten unique symbols, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Since counting in decimal involves ten symbols, we say that its...

2 NUMBER SYSTEMS 2.1 THE DECIMAL NUMBER SYSTEM We begin our study of the number systems with the familiar decimal number system. The decimal system contains ten unique symbols, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Since counting in decimal involves ten symbols, we say that its base or radix is ten. There is no symbol for its base, i.e. for ten. It is a positional weighted system. It means that the value attached to a symbol depends on its location with respect to the decimal point. In this system, any number (integer, fraction, or mixed) of any magnitude can be represented by the use of these ten symbols only. Each symbol in the number is called a digit. The leftmost digit in any number representation, which has the greatest positional weight out of all the digits present in that number, is called the most significant digit (MSD) and the rightmost digit, which has the least positional weight out of all the digits present in that number, is called the least significant digit (LSD). The digits on the left side of the decimal point form the integer part of a decimal number and those on the right side form the fractional part. The digits to the right of the decimal point have weights which are negative powers of 10 and the digits to the left of the decimal point have weights which are positive powers of 10. The value of a decimal number is the sum of the products of the digits of that number with their respective column weights. The weight of each column is 10 times greater than the weight of the column to its right. The first digit to the left of the decimal point has a weight of unity or 100, the second digit to the left of the decimal point has a weight of 10 or 101, the third has a weight of 100 or 102, and so on. The first digit to the right of the decimal point has a weight of 1/10 or 10–1, the second digit to the right has a weight of 1/100 or 10–2, the third has a weight of 1/1000 or 10–3, and so on. 28  NUMBER SYSTEMS 29 In general, the value of any mixed decimal number dn dn–1 dn–2... d1 d0. d–1 d–2 d–3... d–k is given by (dn ¥ 10n) + (dn–1 ¥ 10n–1) +... + (d1 ¥ 101) + (d0 ¥ 100) + (d–1 ¥ 10–1) + (d–2 ¥ 10–2) +... Consider the decimal number 9256.26 using digits 2, 5, 6, 9. This is a mixed number. Hence, 9256.26 = 9 ¥ 1000 + 2 ¥ 100 + 5 ¥ 10 + 6 ¥ 1 + 2 ¥ (1/10) + 6 ¥ (1/100) = 9 ¥ 103 + 2 ¥ 102 + 5 ¥ 101 + 6 ¥ 100 + 2 ¥ 10–1 + 6 ¥ 10–2 Consider another number 6592.69, using the same digits 2, 5, 6, 9. Here, 6592.69 = 6 ¥ 103 + 5 ¥ 102 + 9 ¥ 101 + 2 ¥ 100 + 6 ¥ 10–1 + 9 ¥ 10–2 Note the difference in position values of the same digits, when placed in different positions. 2.1.1 9’s and 10’s Complements Subtraction of decimal numbers can be accomplished by the 9’s and 10’s complement methods similar to the 1’s and 2’s complement methods of binary. The 9’s complement of a decimal number is obtained by subtracting each digit of that decimal number from 9. The 10’s complement of a decimal number is obtained by adding a 1 to its 9’s complement. EXAMPLE 2.1 Find the 9’s complement of the following decimal numbers. (a) 3465 (b) 782.54 (c) 4526.075 Solution (a) 9 9 9 9 (b) 9 9 9. 9 9 –3465 –782.54 6 5 3 4 (9’s complement of 3465) 2 1 7. 4 5 (9’s complement of 782.54) (c) 9999.999 –4526.075 5 4 7 3. 9 2 4 (9’s complement of 4526.075) EXAMPLE 2.2 Find the 10’s complement of the following decimal numbers. (a) 4069 (b) 1056.074 Solution (a) 9 9 9 9 –4069 5 9 3 0 (9’s complement of 4069) +1 Add 1 5 9 3 1 (10’s complement of 4069) (b) 9999.999 –1056.074 8 9 4 3. 9 2 5 (9’s complement of 1056.074) +1 Add 1 8 9 4 3. 9 2 6 (10’s complement of 1056.074) 30 FUNDAMENTALS OF DIGITAL CIRCUITS 2.1.2 9’s Complement Method of Subtraction To perform decimal subtraction using the 9’s complement method, obtain the 9’s complement of the subtrahend and add it to the minuend. Call this number the intermediate result. If there is a carry, it indicates that the answer is positive. Add the carry to the LSD of this result to get the answer. This is called end around carry. If there is no carry, it indicates that the answer is negative and the intermediate result is its 9’s complement. Take the 9’s complement of this result and place a negative sign in front to get the answer. EXAMPLE 2.3 Subtract the following numbers using the 9’s complement method. (a) 745.81 – 436.62 (b) 436.62 – 745.81 Solution (a) 745.81 745.81 –436.62 fi + 5 6 3. 3 7 (9’s complement of 436.62) 309.19  3 0 9. 1 8 (Intermediate result)  + 1 (End around carry) 3 0 9. 1 9 (Answer) The carry indicates that the answer is positive. So the answer is +309.19. (b) 436.62 436.62 –745.81 fi + 2 5 4. 1 8 (9’s complement of 745.81) –309.19 6 9 0. 8 0 (Intermediate result with no carry) There is no carry indicating that the answer is negative. So, take the 9’s complement of the intermediate result and put a minus sign. The 9’s complement of 690.80 is 309.19. Therefore, the answer is –309.19. 2.1.3 10’s Complement Method of Subtraction To perform decimal subtraction using the 10’s complement method, obtain the 10’s complement of the subtrahend and add it to the minuend. If there is a carry, ignore it. The presence of the carry indicates that the answer is positive; the result obtained is itself the answer. If there is no carry, it indicates that the answer is negative and the result obtained is its 10’s complement. Obtain the 10’s complement of the result and place a negative sign in front to get the answer. EXAMPLE 2.4 Subtract the following numbers using the 10’s complement method. (a) 2928.54 – 416.73 (b) 416.73 – 2928.54 Solution (a) 2 9 2 8. 5 4 2928.54 –0416.73 fi + 9 5 8 3. 2 7 (10’s complement of 416.73) 2511.81  2 5 1 1. 8 1 (Ignore the carry) There is a carry indicating that the answer is positive. Ignore the carry. The answer is 2511.81.  NUMBER SYSTEMS 31 (b) 0416.73 0416.73 –2928.54 fi + 7 0 7 1. 4 6 (10’s complement of 2928.54) –2511.81 7 4 8 8. 1 9 (No carry) There is no carry indicating that the answer is negative. So, take the 10’s complement of the intermediate result and put a minus sign. The 10’s complement of 7488.19 is 2511.81. Therefore, the answer is –2511.81. 2.2 THE BINARY NUMBER SYSTEM The binary number system is a positional weighted system. The base or radix of this number system is 2. Hence, it has two independent symbols. The base itself cannot be a symbol. The symbols used are 0 and 1. A binary digit is called a bit. A binary number consists of a sequence of bits, each of which is either a 0 or a 1. The binary point separates the integer and fraction parts. Each digit (bit) carries a weight based on its position relative to the binary point. The weight of each bit position is one power of 2 greater than the weight of the position to its immediate right. The first bit to the left of the binary point has a weight of 20 and that column is called the units column. The second bit to the left has a weight of 21 and it is in the 2’s column. The third bit to the left has a weight of 22 and it is in the 4’s column, and so on. The first bit to the right of the binary point has a weight of 2–1 and it is said to be in the 1/2’s column, the next right bit with a weight of 2–2 is in the 1/4’s column, and so on. The decimal value of the binary number is the sum of the products of all its bits multiplied by the weights of their respective positions. In general, a binary number with an integer part of (n + 1) bits and a fraction part of k bits can be written as dn dn–1 dn–2... d1 d0. d–1 d–2 d–3... d–k. Its decimal equivalent is (dn ¥ 2n) + (dn–1 ¥ 2n–1) +... + (d1 ¥ 21) + (d0 ¥ 20) + (d–1 ¥ 2–1) + (d–2 ¥ 2–2) +... In general, the decimal equivalent of the number dndn–1... d1d0. d–1d–2... in any number system with base b is given by (dn ¥ bn) + (dn–1 ¥ bn–1) +... + (d1 ¥ b1) + (d0 ¥ b0) + (d–1 ¥ b–1) + (d–2 ¥ b–2) +... The binary number system is used in digital computers because the switching circuits used in these computers use two-state devices such as transistors, diodes, etc. A transistor can be OFF or ON, a switch can be OPEN or CLOSED, a diode can be OFF or ON, etc. These devices have to exist in one of the two possible states. So, these two states can be represented by the symbols 0 and 1, respectively. 2.2.1 Counting in Binary Counting in binary is very much similar to decimal counting as shown in Table 2.1. Start counting with 0, the next count is 1. We have now exhausted all symbols; therefore we put a 1 in the column to the left and continue to get 10, 11. Thus, 11 is the maximum we can count using two bits. So, put a 1 in the next column to the left and continue counting; we can count 100, 101, 110, 111. The 32 FUNDAMENTALS OF DIGITAL CIRCUITS largest number we can count using three bits is 111. Put a 1 to the left and continue; we get, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. The maximum count we can get using four bits is 1111. Continue counting with 5, 6,... bits as shown in Table 2.1. Table 2.1 Counting in binary Decimal number Binary number Decimal number Binary number 0 0 20 10100 1 1 21 10101 2 10 22 10110 3 11 23 10111 4 100 24 11000 5 101 25 11001 6 110 26 11010 7 111 27 11011 8 1000 28 11100 9 1001 29 11101 10 1010 30 11110 11 1011 31 11111 12 1100 32 100000 13 1101 33 100001 14 1110 34 100010 15 1111 35 100011 16 10000 36 100100 17 10001 37 100101 18 10010 38 100110 19 10011 39 100111 An easy way to remember to write a binary sequence of n bits is: The rightmost column in the binary number begins with a 0 and alternates between 0 and 1. 1 The second column begins with 2(= 2 ) zeros and alternates between the groups of 2 zeros and 2 ones. 2 The third column begins with 4(= 2 ) zeros and alternates between the groups of 4 zeros and 4 ones. The nth column begins with 2 n–1 zeros and alternates between the groups of 2n–1 zeros and 2n–1 ones. 2.2.2 Binary to Decimal Conversion Binary numbers may be converted to their decimal equivalents by the positional weights method. In this method, each binary digit of the number is multiplied by its position weight and the product terms are added to obtain the decimal number. EXAMPLE 2.5 Convert 101012 to decimal. Solution (Positional weights) 24 23 22 21 20  NUMBER SYSTEMS 33 (Binary number) 1 0 1 0 1 = (1 ¥ 24) + (0 ¥ 23) + (1 ¥ 22) + (0 ¥ 21) + (1 ¥ 20) = 16 + 0 + 4 + 0 + 1 = 2110 EXAMPLE 2.6 Convert 11011.1012 to decimal. Solution 24 23 22 21 20 2–1 2–2 2–3 1 1 0 1 1 ◊ 1 0 1 = (1 ¥ 24) + (1 ¥ 23) + (0 ¥ 22) + (1 ¥ 21) + (1 ¥ 20) + (1 ¥ 2–1) + (0 ¥ 2–2) + (1 ¥ 2–3) = 16 + 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = 27.62510 EXAMPLE 2.7 Convert 10010112 to decimal. Solution An integer binary number can also be converted to an integer decimal number as follows. Starting with the extreme left bit, i.e. MSB, multiply this bit by 2 and add the product to the next bit to the right. Multiply the result obtained in the previous step by 2 and add the product to the next bit to the right. Continue this process as shown below till all the bits in the number are exhausted. 1 0 0 1 0 1 1 1¥2+0=2 2¥2+0=4 4¥2+1=9 9 ¥ 2 + 0 = 18 18 ¥ 2 + 1 = 37 37 ¥ 2 + 1 = 75 The above steps can be written down as follows: Copy down the extreme left bit, i.e. MSB = 1 Multiply by 2, add the next bit (1 ¥ 2) + 0 = 2 Multiply by 2, add the next bit (2 ¥ 2) + 0 = 4 Multiply by 2, add the next bit (4 ¥ 2) + 1 = 9 Multiply by 2, add the next bit (9 ¥ 2) + 0 = 18 Multiply by 2, add the next bit (18 ¥ 2) + 1 = 37 Multiply by 2, add the next bit (37 ¥ 2) + 1 = 75 The result is, 1 0 0 1 0 1 12 = 7510 2.2.3 Decimal to Binary Conversion There are two methods to convert a decimal number to a binary number. These are the reverse processes of the two methods used to convert a binary number to a decimal number. First method: In this method, which is normally used only for small numbers, the values of various powers of 2 need to be remembered. For conversion of large numbers, we should have a 34 FUNDAMENTALS OF DIGITAL CIRCUITS table of powers of 2. In this method, known as the sum-of-weights method, the set of binary weight values whose sum is equal to the decimal number is determined. To convert a given decimal integer number to binary, first obtain the largest decimal number which is a power of 2 not exceeding the given decimal number and record it. Subtract this number from the given number and obtain the remainder. Once again obtain the largest decimal number which is a power of 2 not exceeding this remainder and record it. Subtract this number from the remainder to obtain the next remainder. Repeat the above process on the successive remainders till you get a 0 remainder. The sum of these powers of 2 expressed in binary is the binary equivalent of the original decimal number. In a similar manner, this sum-of-weights method can also be applied to convert decimal fractions to binary. To convert a decimal mixed number to binary, convert the integer and fraction parts separately into binary. In general, the sum-of-weights method can be used to convert a decimal number to a number in any other base system. Second method: In this method, the decimal integer number is converted to the binary integer number by successive division by 2, and the decimal fraction is converted to binary fraction by successive multiplication by 2. This is also known as the double-dabble method. In the successive division-by-2 method, the given decimal integer number is successively divided by 2 till the quotient is zero. The last remainder is the MSB. The remainders read from bottom to top give the equivalent binary integer number. In the successive multiplication-by-2 method, the given decimal fraction and the subsequent decimal fractions are successively multiplied by 2, till the fraction part of the product is 0 or till the desired accuracy is obtained. The first integer obtained is the MSB. Thus, the integers read from top to bottom give the equivalent binary fraction. To convert a mixed number to binary, convert the integer and fraction parts separately to binary and then combine them. In general, these methods can be used for converting a decimal number to an equivalent number in any other base system by just replacing 2 by the base b of that number system. That is, any decimal number can be converted to an equivalent number in any other base system by the sum-of-weights method, or by the double-dabble method—repeated division-by-b for integers and repeated multiplication-by-b for fractions. EXAMPLE 2.8 Convert 163.87510 to binary. Solution The given decimal number is a mixed number. We, therefore, convert its integer and fraction parts separately. The integer part is 16310 The largest number, which is a power of 2, not exceeding 163 is 128. 128 = 27 = 100000002 The remainder is 163 – 128 = 35 The largest number, which a power of 2, not exceeding 35 is 32. 32 = 25 = 1000002 The remainder is 35 – 32 = 3  NUMBER SYSTEMS 35 The largest number, which is a power of 2, not exceeding 3 is 2. 2 = 21 = 102 The remainder is 3–2=1 1 = 20 = 12 Therefore, 16310 = 100000002 + 1000002 + 102 + 12 = 101000112 The fraction part is 0.87510 The largest fraction, which is a power of 2, not exceeding 0.875 is 0.5. 0.5 = 2–1 = 0.1002 The remainder is 0.875 – 0.5 = 0.375 The largest fraction, which is a power of 2, not exceeding 0.375 is 0.25. 0.25 = 2–2 = 0.012 The remainder is 0.375 – 0.25 = 0.125 The largest fraction, which a power of 2, not exceeding 0.125 is 0.125 itself. 0.125 = 2–3 = 0.0012 Therefore, 0.87510 = 0.1002 + 0.012 + 0.0012 = 0.1112 The final result is, 163.87510 = 10100011.1112. EXAMPLE 2.9 Convert 5210 to binary using the double-dabble method. Solution We divide the given decimal number successively by 2 and read the remainders upwards to get the equivalent binary number. Successive division Remainder 2 52 2 26 0 2 13 0 2 6 1 2 3 ≠ 0 2 1 Ω 1 0 Ω 1 Reading the remainders from bottom to top, the result is 5210 = 1101002. 36 FUNDAMENTALS OF DIGITAL CIRCUITS EXAMPLE 2.10 Convert 0.7510 to binary using the double-dabble method. Solution Multiply the given fraction by 2. Keep the integer in the product as it is and multiply the new fraction in the product by 2. Continue this process and read the integers in the products from top to bottom. Given fraction 0.75 Multiply 0.75 by 2 Ω 1.50 Multiply 0.50 by 2 Ø 1.00 Reading the integers from top to bottom, 0.7510 = 0.112. EXAMPLE 2.11 Convert 105.1510 to binary. Solution Conversion of integer 105 Successive division Remainder 2 105 2 52 1 2 26 0 2 13 0 2 6 1 2 3 ≠ 0 2 1 Ω 1 0 Ω 1 Reading the remainders from bottom to top, 10510 = 11010012. Conversion of fraction 0.1510 Given fraction 0.15 Multiply 0.15 by 2 Ω 0.30 Multiply 0.30 by 2 Ω 0.60 Multiply 0.60 by 2 Ω 1.20 Multiply 0.20 by 2 Ø 0.40 Multiply 0.40 by 2 0.80 Multiply 0.80 by 2 1.60 This particular fraction can never be expressed exactly in binary. This process may be terminated after a few steps. Reading the integers from top to bottom, 0.1510 = 0.0010012. Therefore, the final result is, 105.1510 = 1101001.0010012.  NUMBER SYSTEMS 37 2.2.4 Binary Addition The rules for binary addition are the following: 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 10, i.e. 0 with a carry of 1. EXAMPLE 2.12 Add the binary numbers 1101.101 and 111.011. Solution 8 4 2 1 2–1 2–2 2–3 (Column numbers) 1101◊ 1 0 1 + 111◊ 0 1 1 10101◊ 0 0 0 In the 2–3’s column 1 + 1 = 0, with a carry of 1 to the 2–2 column In the 2–2’s column 0 + 1 + 1 = 0, with a carry of 1 to the 2–1 column In the 2–1’s column 1 + 0 + 1 = 0, with a carry of 1 to the 1’s column In the 1’s column 1 + 1 + 1 = 1, with a carry of 1 to the 2’s column In the 2’s column 0 + 1 + 1 = 0, with a carry of 1 to the 4’s column In the 4’s column 1 + 1 + 1 = 1, with a carry of 1 to the 8’s column In the 8’s column 1 + 1 = 0, with a carry of 1 to the 16’s column 2.2.5 Binary Subtraction The binary subtraction is performed in a manner similar to that in decimal subtraction. The rules for binary subtraction are: 0 – 0 = 0; 1 – 1 = 0; 1 – 0 = 1; 0 – 1 = 1, with a borrow of 1. EXAMPLE 2.13 Subtract 111.1112 from 1010.012. Solution 8 4 2 1 2–1 2–2 2–3 (Column numbers) 1010. 0 1 0 111. 1 1 1 0010. 0 1 1 In the 2–3 column, a 1 cannot be subtracted from a 0. So, borrow a 1 from the 2–2 column making the 2–2 column 0. The 1 borrowed from the 2–2 column becomes 10 in the 2–3 column. Therefore, in the 2–3 column, 10 – 1 = 1. In the 2–2 column, a 1 cannot be subtracted from a 0. So, borrow a 1 from the 2–1 column, but it is also a 0. So, borrow a 1 from the 1’s column. That is also a 0, so borrow a 1 from the 2’s column making the 2’s column 0. This 1 borrowed from the 2’s column becomes 10 in the 1’s column. Keep one 1 in the 1’s column, bring the other 1 to the 2–1 column, which becomes 10 in this column. Keep one 1 in the 2–1 column and bring the other 1 to the 2–2 column, which becomes 10 in this column. Therefore, In the 2–2’s column 10 – 1 = 1 In the 2–1’s column 1–1=0 In the 1’s column 1–1=0 38 FUNDAMENTALS OF DIGITAL CIRCUITS Now, in the 2’s column, a 1 cannot be subtracted from a 0; so, borrow a 1 from the 4’s column. But the 4’s column has a 0. So, borrow a 1 from the 8’s column, making the 8’s column 0, and bring it to the 4’s column. It becomes 10 in the 4’s column. Keep one 1 in the 4’s column and bring the second 1 to the 2’s column making it 10 in the 2’s column. Therefore, In the 2’s column 10 – 1 = 1 In the 4’s column 1–1=0 In the 8’s column 0–0=0 Hence, the result is 0010.0112. 2.2.6 Binary Multiplication There are two methods of binary multiplication—the paper method and the computer method. Both the methods obey the following multiplication rules: 0 ¥ 0 = 0; 1 ¥ 1 = 1; 1 ¥ 0 = 0; 0 ¥ 1 = 0 The paper method is similar to the multiplication of decimal numbers on paper. Multiply the multiplicand with each bit of the multiplier, and add the partial products. The partial product is the same as the multiplicand if the multiplier bit is a 1 and is zero if the multiplier bit is a 0. EXAMPLE 2.14 Multiply 11012 by 1102. Solution The LSB of the multiplier is a 0. So, the first partial product is a 0. The next two bits of the multiplier are 1s. So, the next two partial products are equal to the multiplicand itself. The sum of the partial products gives the answer. 1101 ¥110 0000 1101 1101 1001110 EXAMPLE 2.15 Multiply 1011.1012 by 101.012. Solution 1011.101 ¥ 101.01 1 0 1 1101 0 0 0 0 000 10 1 1 1 01 000 0 0 0 0 1011 1 0 1 1 1 1 1 0 1.0 0 0 0 1  NUMBER SYSTEMS 39 2.2.7 Computer Method of Multiplication A computer can add only two numbers at a time with a carry. So, the paper method cannot be used by the digital computer. Besides, the computer has only a fixed number of bit positions available. A p-bit number multiplied by another p-bit number yields a 2p-bit number. To multiply a p-bit number by another p-bit number, a p-bit multiplicand register and a 2p-bit multiplier/result register are required. The multiplier is placed in the left p-bits of the multiplier/ quotient (MQ) register and the right p-bits are set to zero. This permits the MQ to be used as a dual register, which holds the multiplier and the partial (then final) results. The multiplicand is placed in the M register. The MQ register is then shifted one bit to the left. If a 1 is shifted out, M is added to the MQ register. If a 0 is shifted out, a 0 is added to the MQ register. The entire process is repeated p (the number of bits in the multiplier) times. The result appears in the MQ register. EXAMPLE 2.16 Multiply 11002 by 10012 using the computer method. Solution The computer method of multiplication is performed as shown below. MQ register 10010000 Shift MQ left 100100000 (A 1 is shifted out. So, add M to MQ) Add M 1100 Partial sum in MQ 00101100 Shift MQ left 001011000 (A 0 is shifted out. So, add 0 to MQ) Add 0 0000 Partial sum in MQ 01011000 Shift MQ left 010110000 (A 0 is shifted out. So, add 0 to MQ) Add 0 0000 Partial sum in MQ 10110000 Shift MQ left 101100000 (A 1 is shifted out. So, add M to MQ) Add M 1100 Final sum in MQ 01101100 2.2.8 Binary Division Like multiplication, division too can be performed by two methods—the paper method and the computer method. In the paper method, long-division procedures similar to those in decimal are used. EXAMPLE 2.17 Divide 1011012 by 1102. Solution Divisor 110 cannot go in the first three bits of the dividend, i.e. in 101. So, consider the first 4 bits 1011 of the dividend. 110 can go in 1011, one time with a remainder of 101. Next, 110 can go in 1010, one time with a remainder of 100. Next, 110 can go in 1001, one time with a remainder of 11. Finally, 110 can go in 110 with a remainder of 0. 40 FUNDAMENTALS OF DIGITAL CIRCUITS 110 )101101 (111.1 110 1010 110 1001 110 110 110 000 Therefore, 101101 ∏ 110 = 111.1 EXAMPLE 2.18 Divide 110101.112 by 1012. Solution 101 )110101.11 (1010.11 101 0110 101 111 101 101 101 000 Therefore, 110101.11 ∏ 101 = 1010.11 2.2.9 Computer Method of Division The computer method of division involves successive subtraction. Suppose we divide an eight-bit dividend by a four-bit divisor; the quotient will be formed in the right-half of the MQ register and the remainder in the left-half. The dividend is first placed in the MQ register, and the divisor in the D register. The divisor is then subtracted from the dividend. The result is considered negative if a borrow is required, and positive if no borrow is required. If this result is positive, the quotient will be greater than four bits; so, an error has occurred. We cannot complete the division with those registers. If the result is negative, then the quotient will be four or less bits, sufficiently small to be contained in the right-half of the MQ register. The MQ register is next shifted left one bit. The bit shifted out, a 0 or a 1 is not lost. It is stored in a carry flag, a single flip-flop, and is used for the subtraction following the left shift. If the result of subtraction is positive, a 1 is added to the LSB of the MQ register where the quotient is accumulated; if it is negative, the divisor is added to the MQ, and MQ is shifted left one bit. This effectively puts a 0 in this bit of the quotient. The process is continued until the MQ register has been shifted left four bits (the number of bits in the D register). The remainder is then in the left- half of the MQ register and the quotient in the right-half.  NUMBER SYSTEMS 41 EXAMPLE 2.19 Divide 32 by 5 in binary using the computer method. Solution Dividend = 32 = 100000 = 00100000 Divisor = 5 = 101 = 0101 Computer division MQ 0010 0000 Subtract D 0101 MQ 1101 0 0 0 0 (Borrow is required; the result is negative; division is valid) Add D 0101 MQ 0010 0 0 0 0 (Original number) Shift MQ left 00100 0000 Subtract D 0101 MQ 1111 0 0 0 0 (Result is negative) Add D 0101 MQ 0100 0000 Shift MQ left 01000 0000 Subtract D 0101 MQ 0011 0 0 0 0 (Result is positive) Add 1 1 MQ 0011 0001 Shift MQ left 00110 0010 Subtract D 0101 MQ 0001 0 0 1 0 (Result is positive) Add 1 1 MQ 0001 0011 Shift MQ left 00010 0110 Subtract D 0101 MQ 1101 0 1 1 0 (Result is negative) Add D 0101 MQ 0010 0 1 1 0 (Final answer) Result: Remainder = 0 0 1 0 Quotient = 0 1 1 0 2.3 REPRESENTATION OF SIGNED NUMBERS AND BINARY ARITHMETIC IN COMPUTERS So far, we have considered only positive numbers. The representation of negative numbers is also equally important. There are two ways of representing signed numbers—sign-magnitude form and complement form. There are two complement forms: 1’s complement form and 2’s complement form. 42 FUNDAMENTALS OF DIGITAL CIRCUITS Most digital computers do subtraction by the 2’s complement method, but some do it by the 1’s complement method. The advantage of performing subtraction by the complement method is reduction in the hardware. Instead of having separate digital circuits for addition and subtraction, only adding circuits are needed. That is, subtraction is also performed by adders only. Instead of subtracting one number from the other, the complement of the subtrahend is added to the minuend. In sign-magnitude form, an additional bit called the sign bit is placed in front of the number. If the sign bit is a 0, the number is positive. If it is a 1, the number is negative. For example, = + 41 Sign bit Magnitude = – 41 Sign bit Magnitude Under the sign-magnitude system, a great deal of manipulation is necessary to add a positive number to a negative number. Thus, though the sign-magnitude number system is possible, it is impractical. 2.3.1 Representation of Signed Numbers Using the 2’s (or 1’s) Complement Method The 2’s (or 1’s) complement system for representing signed numbers works like this: 1. If the number is positive, the magnitude is represented in its true binary form and a sign bit 0 is placed in front of the MSB. 2. If the number is negative, the magnitude is represented in its 2’s (or 1’s) complement form and a sign bit 1 is placed in front of the MSB. That is, to represent the numbers in sign 2’s (or 1’s) complement form, determine the 2’s (or 1’s) complement of the magnitude of the number and then attach the sign bit. The 2’s (or 1’s) complement operation on a signed number will change a positive number to a negative number and vice versa. The conversion of complement to true binary is the same as the process used to convert true binary to complement. The representation of + 51 and – 51 in both 2’s and 1’s complement forms is shown below: = + 51 (In sign magnitude form) Sign bit Magnitude (In sign 2’s complement form) (In sign 1’s complement form) = – 51 (In sign magnitude form) Sign bit Magnitude = – 51 (In sign 2’s complement form) Sign bit Magnitude = – 51 (In sign 1’s complement form) Sign bit Magnitude  NUMBER SYSTEMS 43 EXAMPLE 2.20 Each of the following numbers is a signed binary number. Determine the decimal value in each case, if they are in (i) sign-magnitude form, (ii) 2’s complement form, and (iii) 1’s complement form. (a) 01101 (b) 010111 (c) 10111 (d) 1101010 Solution Given number Sign-magnitude form 2’s complement form 1’s complement form 01101 + 13 + 13 + 13 010111 + 23 + 23 + 23 10111 –7 –9 –8 1101010 – 42 – 22 – 21 To subtract using the sign 2’s (or 1’s) complement method, represent both the subtrahend and the minuend by the same number of bits. Take the 2’s (or 1’s) complement of the subtrahend including the sign bit. Keep the minuend in its original form and add the 2’s (or 1’s) complement of the subtrahend to it. The choice of 0 for positive sign, and 1 for negative sign is not arbitrary. In fact, this choice makes it possible to add the sign bits in binary addition just as other bits are added. When the sign bit is a 0, the remaining bits represent magnitude, and when the sign bit is a 1, the remaining bits represent 2’s or 1’s complement of the number. The polarity of the signed number can be changed simply by performing the complement on the complete number. Table 2.2 lists all possible 4-bit singed binary numbers in the three representations. The equivalent decimal number is also shown for reference. Note that the positive numbers in all three representations are identical and have 0 in the leftmost position. The singed 2’s complement system has only one representation for 0, which is always positive. The other two systems have either a positive or a negative 0 which is something not encountered in ordinary arithmetic. Note that all negative numbers have a 1 in the leftmost bit position: This is the way we distinguish them from the positive numbers. With four bits, we can represent 16 binary numbers. In the signed magnitude and the 1’s complement representations, there are eight positive numbers and eight negative numbers including two zeros. In the 2’s complement representation, there are eight positive numbers including one zero and eight negative numbers. Special case in 2’s complement representation: Whenever a signed number has a 1 in the sign bit and all 0s for the magnitude bits, the decimal equivalent is –2n, where n is the number of bits in the magnitude. For example, 1000 = –8 and 10000 = –16. Characteristics of the 2’s complement numbers: The 2’s complement numbers have the following properties: 1. There is one unique zero. 2. The 2’s complement of 0 is 0. 3. The leftmost bit cannot be used to express a quantity. It is a sign bit. If it is a 1, the number is negative and if it is a 0, the number is positive. 44 FUNDAMENTALS OF DIGITAL CIRCUITS 4. For an n-bit word which includes the sign bit, there are (2n–1 – 1) positive integers, 2n–1 negative integers and one 0, for a total of 2n unique states. 5. Significant information is contained in the 1s of the positive numbers and 0s of the negative numbers. 6. A negative number may be converted into a positive number by finding its 2’s complement. Table 2.2 Signed binary numbers Decimal Sign 2’s Sign 1’s Sign complement form complement form magnitude form +7 0111 0111 0111 +6 0110 0110 0110 +5 0101 0101 0101 +4 0100 0100 0100 +3 0011 0011 0011 +2 0010 0010 0010 +1 0001 0001 0001 +0 0000 0000 0000 –0 — 1111 1000 –1 1111 1110 1001 –2 1110 1101 1010 –3 1101 1100 1011 –4 1100 1011 1100 –5 1011 1010 1101 –6 1010 1001 1110 –7 1001 1000 1111 –8 1000 — — Methods of obtaining the 2’s complement of a number: The 2’s complement of a number can be obtained in three ways as given below. 1. By obtaining the 1’s complement of the given number (by changing all 0s to 1s and 1s to 0s) and then adding 1. 2. By subtracting the given n-bit number N from 2n. 3. Starting at the LSB, copying down each bit up to and including the first 1 bit encountered, and complementing the remaining bits. EXAMPLE 2.21 Express – 45 in 8-bit 2’s complement form. Solution +45 in 8-bit form is 00101101.  NUMBER SYSTEMS 45 First method Obtain the 1’s complement of 00101101 and then add 1. Positive expression of the given number 00101101 1’s complement of it 11010010 Add 1 +1 Thus, the 2’s complement form of – 45 is 11010011 Second method Subtract the given number N from 2n 2n = 100000000 Subtract 45 = – 00101101 Thus, the 2’s complement form of – 45 is 11010011 Third method Copy down the bits starting from LSB up to and including the first 1, and then complement the remaining bits. Original number 00101101 Copy up to the first 1 bit 1 Complement the remaining bits 1101001 Thus, the 2’s complement form of – 45 is 11010011 EXAMPLE 2.22 Express –73.75 in 12-bit 2’s complement form. Solution + 73.75 = N = 01001001.1100 First method Positive expression of the given number 01001001.1100 1’s complement of it 10110110.0011 Add 1 +1 Thus, the 2’s complement of –73.75 is 10110110.0100 Second method 28 = 1 0 0 0 0 0 0 0 0. 0 0 0 0 Subtract 73.75 =– 01001001.1100 Thus, the 2’s complement of –73.75 is 10110110.0100 Third method Original number 01001001.1100 Copy up to the first 1 bit 100 Complement the remaining bits 10110110.0 Thus, –73.75 in 2’s complement form is 10110110.0100 2.3.2 2’s Complement Arithmetic The 2’s complement system is used to represent negative numbers using modulus arithmetic. The word length of a computer is fixed. That means, if a 4-bit number is added to another 4-bit number, 46 FUNDAMENTALS OF DIGITAL CIRCUITS the result will be only of 4 bits. Carry, if any, from the fourth bit will overflow. This is called the modulus arithmetic. For example: 1100 + 1111 = 1011. In the 2’s complement subtraction, add the 2’s complement of the subtrahend to the minuend. If there is a carry out, ignore it. Look at the sign bit, i.e. MSB of the sum term. If the MSB is a 0, the result is positive and is in true binary form. If the MSB is a 1 (whether there is a carry or no carry at all) the result is negative and is in its 2’s complement form. Take its 2’s complement to find its magnitude in binary. EXAMPLE 2.23 Subtract 14 from 46 using the 8-bit 2’s complement arithmetic. Solution +14 = 00001110 –14 = 11110010 (In 2’s complement form) +46 00101110 –14 fi +11110010 (2’s complement form of – 14) +32 00100000 (Ignore the carry) There is a carry, ignore it. The MSB is 0. So, the result is positive and is in normal binary form. Therefore, the result is + 00100000 = + 32. EXAMPLE 2.24 Add – 75 to + 26 using the 8-bit 2’s complement arithmetic. Solution +75 = 01001011 –75 = 10110101 (In 2’s complement form) +26 00011010 –75 fi +10110101 (2’s complement form of – 75) –49 11001111 (No carry) There is no carry, the MSB is a 1. So, the result is negative and is in 2’s complement form. The magnitude is 2’s complement of 11001111, that is, 00110001 = 49. Therefore, the result is – 49. EXAMPLE 2.25 Add – 45.75 to + 87.5 using the 12-bit 2’s complement arithmetic. Solution +87.5 01010111.1000 –45.75 fi + 1 1 0 1 0 0 1 0. 0 1 0 0 (– 45.75 in 2’s complement form) +41.75  0 0 1 0 1 0 0 1. 1 1 0 0 (Ignore the carry) There is a carry, ignore it. The MSB is 0. So, the result is positive and is in normal binary form. Therefore, the result is + 41.75 EXAMPLE 2.26 Add 27.125 to – 79.625 using the 12-bit 2’s complement arithmetic. Solution +27.125 00011011.0010 – 7 9. 6 2 5 fi + 1 0 1 1 0 0 0 0. 0 1 1 0 (– 79.625 in 2’s complement form) –52.500 1 1 0 0 1 0 1 1. 1 0 0 0 (No carry)  NUMBER SYSTEMS 47 There is no carry. The MSB is a 1 indicating that the result is negative and is in its 2’s complement form. The 2’s complement of 11001011.1000 is 00110100.1000. Therefore, the result is – 52.5. EXAMPLE 2.27 Add – 31.5 to – 93.125 using the 12-bit 2’s complement arithmetic. Solution –93.125 1 0 1 0 0 0 1 0. 1 1 1 0 (– 93.125 in 2’s complement form) – 3 1. 5 0 0 fi + 1 1 1 0 0 0 0 0. 1 0 0 0 (– 31.5 in 2’s complement form) –124.625  1 0 0 0 0 0 1 1. 0 1 1 0 (Ignore the carry) There is a carry, ignore it. The MSB is a 1. So, the result is negative and is in its 2’s complement form. The 2’s complement of 1000 0011.0110 is 0111 1100.1010. Therefore, the result is – 124.625. EXAMPLE 2.28 Add 47.25 to 55.75 using the 2’s complement method. Solution 47.25 00101111.0100 55.75 fi +00110111.1100 103.00 01100111.0000 (No carry) There is no carry. The MSB is a 0. Therefore, the result is positive and is in its true binary form. Hence, it is equal to + 103.0. EXAMPLE 2.29 Add + 40.75 to – 40.75 using the 12-bit 2’s complement arithmetic. Solution +40.75 00101000.1100 – 4 0. 7 5 fi + 1 1 0 1 0 1 1 1. 0 1 0 0 (– 40.75 in 2’s complement form) 00.00  0 0 0 0 0 0 0 0. 0 0 0 0 (Ignore the carry) There is a carry, ignore it. The result is 0. Method of obtaining the 1’s complement of a number: The 1’s complement of a number is obtained by simply complementing each bit of the number, that is, by changing all the 0s to 1s and all the 1s to 0s. We can also say that the 1’s complement of a number is obtained by subtracting each bit of the number from 1. This complemented value represents the negative of the original number. This system is very easy to implement in hardware by simply feeding all bits through inverters. One of the difficulties of using 1’s complement is its representation of zero. Both 00000000 and its 1’s complement 11111111 represent zero. The 00000000 is called positive zero and the 11111111 is called negative zero. EXAMPLE 2.30 Represent – 99 and – 77.25 in 8-bit 1’s complement form. Solution We first write the positive representation of the given number in binary form and then complement each of its bits to represent the negative of the number. (a) +99=01100011 –99=10011100 (In 1’s complement form) (b) +77.25=01001101.0100 – 7 7. 2 5 = 1 0 1 1 0 0 1 0. 1 0 1 1 (In 1’s complement form) 48 FUNDAMENTALS OF DIGITAL CIRCUITS 2.3.3 1’s Complement Arithmetic In 1’s complement subtraction, add the 1’s complement of the subtrahend to the minuend. If there is a carry out, bring the carry around and add it to the LSB. This is called the end around carry. Look at the sign bit (MSB). If this is a 0, the result is positive and is in true binary. If the MSB is a 1 (whether there is a carry or no carry at all), the result is negative and is in its 1’s complement form. Take its 1’s complement to get the magnitude in binary. EXAMPLE 2.31 Subtract 14 from 25 using the 8-bit 1’s complement arithmetic. Solution 25 00011001 –14 fi +11110001 (In 1’s complement form) +11 00001010  +1 (End around carry) 00001011 The MSB is a 0. So, the result is positive and is in pure binary. Therefore, the result is, 00001011 = +1110. EXAMPLE 2.32 Add – 25 to + 14 using the 8-bit 1’s complement method. Solution +14 00001110 –25 fi +11100110 (In 1’s complement form) –11 11110100 (No carry) There is no carry. The MSB is a 1. So, the result is negative and is in its 1’s complement form. The 1’s complement of 11110100 is 00001011. The result is, therefore, – 1110. EXAMPLE 2.33 Add – 25 to – 14 using the 8-bit 1’s complement method. Solution –25 11100110 (In 1’s complement form) –14 fi +11110001 (In 1’s complement form) –39 11010111  +1 (End around carry) 11011000 The MSB is a 1. So, the result is negative and is in its 1’s complement form. The 1’s complement of 11011000 is 00100111. Therefore, the result is – 39. EXAMPLE 2.34 Add + 25 to + 14 using the 8-bit 1’s complement arithmetic. Solution +25 0 0 0 1 1 0 0 1 (In 1’s complement form) +14 fi + 0 0 0 0 1 1 1 0 (In 1’s complement form) +39 00100111 There is no carry. The MSB is a 0. So, the result is positive and is in pure binary. Therefore, the result is, 00100111 = + 39.  NUMBER SYSTEMS 49 EXAMPLE 2.35 Add + 25 to – 25 using the 8-bit 1’s complement method. Solution +25 00011001 –25 fi +11100110 (In 1’s complement form) 00 11111111 There is no carry. The MSB is a 1. So, the result is negative and is in its 1’s complement form. The 1’s complement of 11111111 is 00000000. Therefore, the result is – 0. EXAMPLE 2.36 Subtract 27.50 from 68.75 using the 12 bit 1’s complement arithmetic. Solution +68.75 01000100.1100 –27.50 fi +11100100.0111 (In 1’s complement form) +41.25 00101001.0011  +1 (End around carry) 00101001.0100 The MSB is a 0. So, the result is positive and is in its normal binary form. Therefore, the result is + 41.25. EXAMPLE 2.37 Add – 89.75 to + 43.25 using the 12-bit 1’s complement method. Solution +43.25 00101011.0100 –89.75 fi +10100110.0011 (In 1’s complement form) –46.50 11010001.0111 There is no carry. The MSB is a 1. So, the result is negative and is in its 1’s complement form. The 1’s complement of 11010001.0111 is 00101110.1000. Therefore, the result is – 46.50. EXAMPLE 2.38 Write the following binary numbers in sign magnitude form, in sign 1’s complement form, and in sign 2’s complement form using 16-bit registers. (a) + 1 0 0 1 0 1 0 (b) – 1 1 1 1 0 0 0 0 (c) – 1 1 0 0 1 1 0 0. 1 (d) + 1 0 0 0 0 0 0 1 1. 1 1 1 Solution The representation of positive numbers in sign magnitude form, in sign 1’s complement form, and in sign 2’s complement form is exactly the same. The first bit 0 indicates the positive sign and the remaining bits indicate the magnitude. To write the negative number in 16-bit sign magnitude form, put a 1 in the MSB position and write the magnitude in 15-bit form. To write the negative number in sign 1’s complement form, put a 1 in the MSB position and write the 1’s complement of the 15-bit magnitude in the other 15-bit positions. 50 FUNDAMENTALS OF DIGITAL CIRCUITS To write the negative number in sign 2’s complement form, put a 1 in the MSB position and write the 15-bit 2’s complement form of the magnitude in the other 15-bit positions. (a) The given number + 1 0 0 1 0 1 0 in 15-bit form is + 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 In 16-bit sign magnitude form it is 0000000001001010 In 16-bit sign 1’s complement form it is 0000000001001010 In 16-bit sign 2’s complement form it is 0000000001001010 (b) The given number – 1 1 1 1 0 0 0 0 in 15-bit form is – 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 In 16-bit sign magnitude form it is 1000000011110000 In 16-bit sign 1’s complement form it is 1111111100001111 In 16-bit sign 2’s complement form it is 1111111100010000 (c) The given number – 1 1 0 0 1 1 0 0. 1 in 15-bit form is – 0 0 0 1 1 0 0 1 1 0 0. 1 0 0 0 In 16-bit sign magnitude form it is 1000 11001100.1000 In 16-bit sign 1’s complement form it is 1111 00110011.0111 In 16-bit sign 2’s complement form it is 1111 00110011.1000 (d) The given number + 1 0 0 0 0 0 0 1 1. 1 1 1 in 15-bit form is 0 0 1 0 0 0 0 0 0 1 1. 1 1 10 In 16-bit sign magnitude form it is 0001000 00 011.1110 In 16-bit sign 1’s complement form it is 0001000 00 011.1110 In 16-bit sign 2’s complement form it is 0001000 00 011.1110 EXAMPLE 2.39 Perform N1 + N2, N1 + (– N2) for the following 8-bit numbers expressed in 2’s complement representation. Verify your answers by using decimal addition and subtraction (a) N1 = 0 0 1 1 0 0 1 0, N2 = 1 1 1 1 1 1 0 1 (b) N1 = 1 0 0 0 1 1 1 0, N2 = 0 0 0 0 1 1 0 1 Solution Since the given 8-bit numbers are in 2’s complement form, if the MSB is a 0, the number is positive and the remaining bits give the magnitude of the positive number. If the MSB is a 1, the number is negative and 2’s complement of the remaining bits give the magnitude of the negative number. So, perform the addition and subtraction using 2’s complement method. The arithmetic operations and the verification of the answers using decimal addition and subtraction are performed as given below. (a) Given N1 = 0 0 1 1 0 0 1 02 = + 0 1 1 0 0 1 0 = + 5 010, and N2 = 1 1 1 1 1 1 0 12 = – 0 0 0 0 0 1 1 = – 310 N1 + N2 = 00110010 +50+ + 11111101 –3 00101111=+47 +47 There is a carry. Ignore it. The MSB is a 0. So, answer is positive and the remaining bits indicate the magnitude in normal binary. It is + 47. N1 + (– N2) = 0 0 1 1 0 0 1 0 +50+ +00000011 + 3 00110101 =+53 +53 There is no carry. The MSB is a 0. So, the answer is positive and is in true binary form. It is + 53.  NUMBER SYSTEMS 51 (b) Given N1 = 1 0 0 0 1 1 1 0 = – 1 1 1 0 0 1 0 = –11410 N2 = 0 0 0 0 1 1 0 1 = + 0 0 0 1 1 0 1 = + 1310 N1 + N2 = 1 0 0 0 1 1 1 0 –114+ +0 0 0 0 1 1 0 1 + 13 1 0 0 1 1 0 1 1 = –10110 –101 There is no carry. The MSB is a 1. So, the answer is negative. Take its 2’s complement and put minus sign. So it is – 1 1 0 0 1 0 12 = – 1 0 12. N1 + (– N2) = 10001110 –114+ +11110011 – 13  1 0 0 0 0 0 0 1 = –12710 –127 There is a carry. Ignore it. The MSB is a 1. So, the answer is negative. Take its 2’s complement and put a minus sign. It is – 0 1 1 1 1 1 1 12 = – 12710. EXAMPLE 2.40 (a) The binary numbers listed have a sign bit in the left most position and if negative, numbers are in 2’s complement form. Perform the arithmetic operations indicated and verify the answers. (b) Repeat if the numbers are in 1’s complement form. (i) 101011+111000 (ii) 001110+110010 (iii) 111001–001010 (iv) 101011–100110 Solution (a) Given that the binary numbers listed have a sign bit in the MSB position and if negative, numbers are in 2’s complement form. So, if MSB = 0, the number is positive and the remaining bits give its magnitude. If the MSB = 1, the number is negative and the remaining bits give the 2’s complement of the magnitude. Therefore, 1 0 1 0 1 1 =– 1 0 1 0 1 = –21 1 1 1 0 0 0=– 0 1 0 0 0=– 8 0 0 1 1 1 0 =+ 0 1 1 1 0 = +14 1 1 0 0 1 0=– 0 1 1 1 0 = –14 1 1 1 0 0 1 =– 0 0 1 1 1 = –7 0 0 1 0 1 0=+ 0 1 0 1 0 = +10 1 0 1 0 1 1 =– 1 0 1 0 1 = –21 1 0 0 1 1 0=– 1 1 0 1 0 = –26 The arithmetic operations in 2’s complement form and their verifications are given below. (i) 101011 = –10101 = –21 + +111000 = –01000 = –8 100011 = –29 –29 Both the augend and addend are negative and are in 2’s complement form. In the sum term there is a carry. Ignore it. The sign bit is a 1. So, the answer is negative. Take its 2’s complement and put a minus sign. Answer = – 0111012 = – 29. The decimal addition is shown above. (ii) 001110 = +01110 = +14 + +110010 = –01110 = –14 000000 = 0 0 52 FUNDAMENTALS OF DIGITAL CIRCUITS The augend is positive and the addend is negative and is in its 2’s complement form. In the sum term there is a carry. Ignore it. The answer is all 0s. It is 0. The decimal addition is shown above. (iii) 111001 fi 1 1 1 0 0 1 = – 0 0 1 1 1 = – 7+ –001010 + 1 1 0 1 1 0 = – 0 1 0 1 0 = –10 101111 = –17 –17 The minuend is negative and the subtrahend is positive. Take the 2’s complement of the subtrahend and add it to the minuend. In the sum term there is a carry. Ignore it. The sign bit is a 1. So, the answer is negative. Take its 2’s complement and put a minus sign. It is –17. The decimal subtraction is shown above. (iv) 101011 fi 101011 = –10101 = –21 – – –100110 +011010 = –11010 = –26 000101 = +5 +5 Both the minuend and the subtrahend are negative and are in 2’s complement form. Since the subtrahend is to be subtracted from the minuend, take the 2’s complement of the subtrahend and add it to the minuend. In the sum term there is a carry. Ignore it. The sign bit is a 0. So, the answer is positive and is in true binary form. It is + 5. The decimal subtraction is shown above. (b) Given that the binary numbers listed have a sign bit and if negative, numbers are in 1’s complement form. So, if MSB = 0, the number is positive and the remaining bits give its magnitude. If the MSB = 1, the number is negative and the remaining bits give the 1’s complement of the magnitude. Therefore, 1 0 1 0 1 1 =– 1 0 1 0 0 = –20 1 1 1 0 0 0=– 0 0 1 1 1=– 7 0 0 1 1 1 0 =+ 0 1 1 1 0 = +14 1 1 0 0 1 0=– 0 1 1 0 1 = –13 1 1 1 0 0 1 =– 0 0 1 1 0=–6 0 0 1 0 1 0=+ 0 1 0 1 0 = +10 1 0 1 0 1 1 =– 1 0 1 0 0 = –20 1 0 0 1 1 0=– 1 1 0 0 1 = –25 The arithmetic operations in 1’s complement form and their verifications are given below. (i) 101011 = –10100 = –20 + +111000 = –00111 = – 7 100011 –27  1 100100 = –27 Both the augend and addend are negative and are in 1’s complement form. In the sum term there is a carry. Add it to the LSB. The sign bit is a 1. So, the answer is negative. Take its 1’s complement and put a minus sign. Answer = –110112 = –27. The decimal addition is also shown above. (ii) 0 0 1 1 1 0 = + 0 1 1 1 0 = +14 + + 1 1 0 0 1 0 = – 0 1 1 0 1 = –13 000000 1  1 000001 = +1  NUMBER SYSTEMS 53 The augend is positive and the addend is negative and is in its 1’s complement form. In the sum term there is a carry. Add it to the LSB. The sign bit is a 0. So, the answer is positive and is in true binary form. It is +1. The decimal addition is also shown above. (iii) 1 1 1 0 0 1 fi 1 1 1 0 0 1 = – 0 0 1 1 0 = – 6+ –001010 + 1 1 0 1 0 1 = – 0 1 0 1 0 = –10 101110 –16  1 101111 = –16 The minuend is negative and is in 1’s complement form. The subtrahend is positive. Take the 1’s complement of the subtrahend and add it to the minuend. In the sum term there is a carry. Add it to the LSB. The sign bit is a 1. So, the answer is negative. Take its 1’s complement and put a minus sign. It is –16. The decimal subtraction is also shown above. (iv) 101011 fi 101011 = –10100 = –20 – –100110 +011001 = –11001 = –25 000100 + 5  1 000101 = +5 Both the minuend and the subtrahend are negative and are in 1’s complement form. Take the 1’s complement of the subtrahend and add it to the minuend. The sum term has a carry. Add it to the LSB. The sign bit is a 0. So, the answer is positive and is in normal binary form. It is +5. The decimal subtraction is also shown above. EXAMPLE 2.41 Perform the subtraction with the following unsigned binary numbers (a) by taking the 2’s complement of the subtrahend and (b) by taking the 1’s complement of the subtrahend. (i) 11010 – 10000 (ii) 11010 – 1101 (iii) 100 – 11000 (iv) 1010100 – 1010100 Solution (a) Subtraction of the given unsigned binary numbers using 2’s complement method (i) 11010 fi 11010 = 26 –10000 +10000 (2’s complement) = –16 01010 (Ignore the carry) +10 = + 0 1 0 1 0 = +10 (Result is positive = +10) There is a carry. Ignore it. The MSB is 0. Hence, the answer is positive and is in true binary form. So it is + 0 1 0 1 0 = + 10 54 FUNDAMENTALS OF DIGITAL CIRCUITS (ii) 11010 fi 11010 = 26 – 1101 + 1 0 0 1 1 (2’s complement) = –13  0 1 1 0 1 (Ignore the carry, result is positive = +13) +13 = + 0 1 1 0 1 = +13 There is a carry. Ignore it. The MSB is 0. Hence, the answer is positive and is in true binary form. So it is + 0 1 1 0 1 = +13 (iii) 100 fi 0000100 fi 0000100 = 4 –110000 0110000 + 1 0 1 0 0 0 0 (2’s complement) = – 48 1 0 1 0 1 0 0 (Result is negative) – 44 = – 0 1 0 1 1 0 0 = – 44 There is no carry. The MSB is 1. Hence, the answer is negative. Take its 2’s complement and put a minus sign. So, it is – 1 0 1 1 0 0 = – 44 (iv) 1010100 fi 1010100 = 84 –1010100 + 1 0 1 0 1 0 0 (2’s complement) = –84  0 0 0 0 0 0 0 (Ignore the carry) 0 = 0 (Result = 0) There is a carry. Ignore it. The MSB is 0. Hence, the answer is positive and is in true binary form. So it is + 0 0 0 0 0 0 = 0. (b) Subtraction of the given unsigned binary numbers using 1’s complement method (i) 11010 fi 11010 = 26 –10000 +01111 (1’s complement) = –16 01001 +10 +1 (End around carry) 0 1 0 1 0 = +10 (Result is positive = +10) There is a carry. Add it to the LSB. The MSB is 0. Hence the answer is positive and is in true binary form. So it is + 1 0 1 0 = +10 (ii) 11010 fi 11010 = 26 –1101 + 1 0 0 1 0 (1’s complement) = –13  0 1 1 0 0 (Add carry) +13 1 0 1 1 0 1 (Result is positive = +13) There is a carry. Add it to the LSB. The MSB is 0. Hence, the answer is positive and is in true binary form. So it is + 1 1 0 1 = +13  NUMBER SYSTEMS 55 (iii) 100 fi 0000100 = 4 –110000 + 1 0 0 1 1 1 1 (1’s complement) = – 48 1 0 1 0 0 1 1 (Result is negative) – 44 =– 1 0 1 1 0 0 (= – 44) There is no carry. The MSB is 1. Hence, the answer is negative.Take the 1’s complement of the remaining bits and put a minus sign. So, it is – 1 0 1 1 0 0 = – 44. (iv) 1010100 fi 1010100 = 84 –1010100 + 0 1 0 1 0 1 1 (1’s complement) = –84 1 1 1 1 1 1 1 (Result is negative = – 0) – 0 There is no carry. The MSB is 1. Hence, the answer is negative. Take the 1’s complement of the remaining bits and put a minus sign. So, it is – 0 0 0 0 0 0 = 0. 2.3.4 Double Precision Numbers For any computer the word length is fixed. In a 16-bit computer, that is, in a computer with a 16- bit word length, only numbers from +216–1 – 1 (+ 32,767) to –216 –1 (–32,768) can be expressed in each register. If numbers greater than this are to be expressed, two storage locations need to be used, that is, each such number has to be stored in two registers. This is called double precision. Leaving the MSB which is the sign bit, this allows a 31-bit number length with two 16-bit registers. If still larger numbers are to be expressed, three registers are used to store each number. This is called triple precision. 2.3.5 Floating Point Numbers In the decimal system, very large and very small numbers are expressed in scientific notation, by stating a number (mantissa) and an exponent of 10. Examples are 6.53 ¥ 10 –27 and 1.58 ¥ 1021. Binary numbers can also be expressed in the same notation by stating a number and an exponent of 2. However, the format for a computer may be as shown below. Mantissa   Exponent   0110000000 100101 In this machine, the 16-bit word consists of two parts, a 10-bit mantissa and a 6-bit exponent. The mantissa is in 2’s complement form. So, the MSB can be thought of as the sign bit. The binary point is assumed to be to the right of this sign bit. The 6 bits of the exponent could represent 0 through 63. However, to express negative exponents, the number 3210 (1000002) has been added to the desired exponent. The actual exponent of the number, therefore, is equal to the exponent given by the 6 bits minus 32. This is a common system used in floating point formats. It is called the excess-32 notation. According to these definitions, the floating-point number shown above is The mantissa portion =+0.110000000 The exponent portion = 100101 The actual exponent = 100101–100000=000101 The entire number = N = + 0.11002 ¥ 25 = 110002 = 2410 56 FUNDAMENTALS OF DIGITAL CIRCUITS There are many formats of floating point numbers, each computer having its own. Some use two words for the mantissa, and one for the exponent; others use one and half words for the mantissa, and a half word for the exponent. On some machines the programmer can select from several formats, depending on the accuracy desired. Some use excess-n notation for the exponent, some use 2’s complement, some even use sign-magnitude for both the mantissa and the exponent. 2.4 THE OCTAL NUMBER SYSTEM The octal number system was extensively used by early minicomputers. It is also a positional weighted system. Its base or radix is 8. It has 8 independent symbols 0, 1, 2, 3, 4, 5, 6, and 7. Since its base 8 = 23, every 3-bit group of binary can be represented by an octal digit. An octal number is, thus, 1/3rd the length of the corresponding binary number. 2.4.1 Usefulness of the Octal System The ease with which conversions can be made between octal and binary makes the octal system more attractive as a shorthand means of expressing large binary numbers. In computer work, binary numbers with up to 64-bits are not uncommon. These binary numbers do not always represent a numerical quantity; they often represent some type of code, which conveys non-numerical information. In computers, binary numbers might represent (a) the actual numerical data, (b) the numbers corresponding to a location (address) in memory, (c) an instruction code, (d) a code expressing alphabetic and other non-numerical characters, or (e) a group of bits representing the status of devices internal or external to the computer. When dealing with large binary numbers of many bits, it is convenient and more efficient for us to write the numbers in octal rather than binary. However, the digital circuits and systems work strictly in binary; we use octal only for the convenience of the operators of the system. Table 2.3 shows octal counting. Table 2.3 Octal counting Decimal Octal Decimal Octal Decimal Octal Decimal Octal number number number number number number number number 0 0 10 12 20 24 30 36 1 1 11 13 21 25 31 37 2 2 12 14 22 26 32 40 3 3 13 15 23 27 33 41 4 4 14 16 24 30 34 42 5 5 15 17 25 31 35 43 6 6 16 20 26 32 36 44 7 7 17 21 27 33 37 45 8 10 18 22 28 34 38 46 9 11 19 23 29 35 39 47 2.4.2 Octal to Binary Conversion To convert a given octal number to a binary, just replace each octal digit by its 3-bit binary equivalent.  NUMBER SYSTEMS 57 EXAMPLE 2.42 Convert 367.528 to binary. Solution Given octal number is 3 6 7. 5 2 Convert each octal digit to binary 011 110 111. 101 010 The result is 011110111. 1010102 2.4.3 Binary to Octal Conversion To convert a binary number to an octal number, starting from the binary point make groups of 3 bits each, on either side of the binary point, and replace each 3-bit binary group by the equivalent octal digit. EXAMPLE 2.43 Convert 110101.1010102 to octal. Solution Groups of three bits are 110 101. 101 010 Convert each group to octal 6 5. 5 2 The result is 65.528 EXAMPLE 2.44 Convert 10101111001.01112 to octal. Solution Groups of three bits are 10 101 111 001. 011 1 = 010 101 111 001. 011 100 Convert each group into octal 2 5 7 1. 3 4 The result is 2571.348 2.4.4 Octal to Decimal Conversion To convert an octal number to a decimal number, multiply each digit in the octal number by the weight of its position and add all the product terms. The decimal value of the octal number dndn–1dn–2... d1d0 ◊ d–1d–2... d–k is (dn ¥ 8n) + (dn–1 ¥ 8n–1) +... + (d1 ¥ 81) + (d0 ¥ 80) + (d–1 ¥ 8–1) + (d–2 ¥ 8–2) +... EXAMPLE 2.45 Convert 4057.068 to decimal. Solution 4057.068 = 4 ¥ 83 + 0 ¥ 82 + 5 ¥ 81 + 7 ¥ 80 + 0 ¥ 8–1 + 6 ¥ 8–2 = 2048 + 0 + 40 + 7 + 0 + 0.0937 = 2095.093710 2.4.5 Decimal to Octal Conversion To convert a mixed decimal number to a mixed octal number, convert the integer and fraction parts separately. To convert the given decimal integer number to octal, successively divide the given number by 8 till the quotient is 0. The last remainder is the MSD. The remainders read upwards give the equivalent octal integer number. 58 FUNDAMENTALS OF DIGITAL CIRCUITS To convert the given decimal fraction to octal, successively multiply the decimal fraction and the subsequent decimal fractions by 8 till the product is 0 or till the required accuracy is obtained. The first integer from the top is the MSD. The integers to the left of the octal point read downwards give the octal fraction. EXAMPLE 2.46 Convert 378.9310 to octal. Solution Conversion of 37810 to octal Successive division Remainders 8 378 8 47 ≠ 2 8 5 Ω 7 0 Ω 5 Read the remainders from bottom to top. Therefore, 37810 = 5728. Conversion of 0.9310 to octal 0.93 ¥ 8 Ω 7.44 0.44 ¥ 8 Ω 3.52 0.52 ¥ 8 Ø 4.16 0.16 ¥ 8 1.28 Read the integers to the left of the octal point downwards. Therefore, 0.9310 = 0.73418. Hence 378.9310 = 572.73418. Conversion of large decimal numbers to binary and large binary numbers to decimal can be conveniently and quickly performed via octal as shown below. EXAMPLE 2.47 Convert 549710 to binary. Solution Since the given decimal number is large, we first convert this number to octal and then convert the octal number to binary. Successive division Remainders 8 5497 8 687 ≠ 1 8 85 Ω 7 8 10 Ω 5 8 1 Ω 2 0 1 Therefore, 549710 = 125718 = 0010101011110012.  NUMBER SYSTEMS 59 EXAMPLE 2.48 Convert 1011110100012 to decimal. Solution Since the given binary number is large, we first convert this number to octal and then convert the octal number to decimal. 1011110100012 = 57218 = 5 ¥ 83 + 7 ¥ 82 + 2 ¥ 81 + 1 ¥ 80 = 2560 + 448 + 16 + 1 = 302510. 2.4.6 Octal Arithmetic Octal arithmetic rules are similar to the decimal or binary arithmetic. Normally we are not interested in performing octal arithmetic operations using octal representation of numbers. This number system is normally used to enter long strings of binary data in a digital system like a microcomputer. This makes the task of entering binary data in a microcomputer easier. Arithmetic operations can be performed by converting the octal numbers to binary numbers and then using the rules of binary arithmetic. Octal subtraction can be performed using 1’s complement method or 2’s complement method. However octal subtraction can also be performed directly by 7’s and 8’s complement methods similar to the 9’s and 10’s complement methods of decimal system. EXAMPLE 2.49 Add (27.5)8 and (74.4)8. Solution 27.58 = 010 1 1 1 ◊ 1 0 12 +74.48 = +111 1 0 0 ◊ 1 0 02 124.18 = 1010 100 ◊001 EXAMPLE 2.50 Subtract (a) 458 from 668 and (b) 738 from 258. Solution Using 8-bit representation and 2’s complement method (a) 668 = 00 110 1 1 02 – 458 = +11 011 0 1 12 (2’s complement of – 458) 218 0 0 010 0 0 12 (Ignore the carry. Answer is positive) (b) 258 = 00 0 10 1 0 12 – 738 = +11 000 1 0 12 (2’s complement of –738) – 488 11 011 0 1 02 (Answer is negative) 2’s complement of 1 1 0 1 1 0 1 02 = – 0 0 1 0 0 1 1 0 = – 488 Multiplication and division can also be performed using the binary representation of octal numbers and then making use of multiplication and division rules of binary numbers. 2.5 THE HEXADECIMAL NUMBER SYSTEM Binary numbers are long. These numbers are fine for machines but are too lengthy to be handled by human beings. So, there is a need to represent the binary numbers concisely. One number system developed with this objective is the hexadecimal number system (or Hex). Although it is 60 FUNDAMENTALS OF DIGITAL CIRCUITS somewhat more difficult to interpret than the octal number system, it has become the most popular means of direct data entry and retrieval in digital systems. The hexadecimal number system is a positional-weighted system. The base or radix of this number system is 16, that means, it has 16 independent symbols. The symbols used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. Since its base is 16 = 24, every 4 binary digit combination can be represented by one hexadecimal digit. So, a hexadecimal number is 1/4th the length of the corresponding binary number, yet it provides the same information as the binary number. A 4-bit group is called a nibble. Since computer words come in 8 bits, 16 bits, 32 bits and so on, that is, multiples of 4 bits, they can be easily represented in hexadecimal. The hexadecimal system is particularly useful for human communications with computers. By far, this is the most commonly used number system in computer literature. It is used both in large and small computers. 2.5.1 Hexadecimal Counting Sequence 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F................................ F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 100 101 102 103 104 105 106 107 108 109 10A 10B 10C 10D 10E 10F................................ 1F0 1F1 1F2 1F3 1F4 1F5 1F6 1F7 1F8 1F9 1FA 1FB 1FC 1FD 1FE 1FF 2.5.2 Binary to Hexadecimal Conversion To convert a binary number to a hexadecimal number, starting from the binary point, make groups of 4 bits each, on either side of the binary point and replace each 4-bit group by the equivalent hexadecimal digit as shown in Table 2.4. Table 2.4 Binary to hexadecimal conversion Hexadecimal Binary Hexadecimal Binary 0 0000 8 1000 1 0001 9 1001 2 0010 A 1010 3 0011 B 1011 4 0100 C 1100 5 0101 D 1101 6 0110 E 1110 7 0111 F 1111 EXAMPLE 2.51 Convert 10110110112 to hexadecimal. Solution Make groups of 4 bits, and replace each 4-bit group by a hex digit.  NUMBER SYSTEMS 61 Given binary number is 1011011011 Groups of four bits are 0010 1101 1011 Convert each group to hex 2 D B The result is 2DB16 EXAMPLE 2.52 Convert 01011111011.0111112 to hexadecimal. Solution Given binary number is 01011111011.011111 Groups of four bits are 0010 1111 1011. 0111 1100 Convert each group to hex 2 F B. 7 C The result is 2FB.7C16 2.5.3 Hexadecimal to Binary Conversion To convert a hexadecimal number to binary, replace each hex digit by its 4-bit binary group. EXAMPLE 2.53 Convert 4BAC16 to binary. Solution Given hex number is 4 B A C Convert each hex digit to 4-bit binary 0100 1011 1010 1100 The result is 01001011101011002 EXAMPLE 2.54 Convert 3A9E.B0D16 to binary. Solution Given hex number is 3 A 9 E. B 0 D Convert each hex digit to 4-bit binary 0011 1010 1001 1110. 1011 0000 1101 The result is 0011101010011110.1011000011012 2.5.4 Hexadecimal to Decimal Conversion To convert a hexadecimal number to decimal, multiply each digit in the hex number by its position weight and add all those product terms. If the hex number is dndn–1... d1d0. d–1d–2... d–k, its decimal equivalent is (d ¥ 16n) + (d ¥ 16n–1) +... + (d ¥ 161) + (d ¥ 160) + (d ¥ 16–1) + (d ¥ 16–2) +... n n–1 1 0 –1 –2 EXAMPLE 2.55 Convert 5C716 to decimal. Solution Multiply each digit of 5C7 by its position weight and add the product terms. 5C716 = (5 ¥ 162) + (12 ¥ 161) + (7 ¥ 160) = 1280 + 192 + 7 = 147910 EXAMPLE 2.56 Convert A0F9.0EB16 to decimal. Solution A0F9.0EB16 = (10 ¥ 163) + (0 ¥ 162) + (15 ¥ 161) + (9 ¥ 160) + (0 ¥ 16–1) + (14 ¥ 16–2) + (11 ¥ 16–3) 62 FUNDAMENTALS OF DIGITAL CIRCUITS = 40960 + 0 + 240 + 9 + 0 + 0.0546 + 0.0026 = 41209.057210 2.5.5 Decimal to Hexadecimal Conversion To convert a decimal integer number to hexadecimal, successively divide the given decimal number by 16 till the quotient is zero. The last remainder is the MSB. The remainders read from bottom to top give the equivalent hexadecimal integer. To convert a decimal fraction to hexadecimal, successively multiply the given decimal fraction and subsequent decimal fractions by 16, till the product is zero or till the required accuracy is obtained, and collect all the integers to the left of the decimal point. The first integer is the MSB and the integers read from top to bottom give the hexadecimal fraction. This is known as the hex dabble method. EXAMPLE 2.57 Convert 2598.67510 to hex. Solution The given decimal number is a mixed number. Convert the integer and the fraction parts separately to hex. Conversion of 259810 Successive division Remainder Decimal Hex 16 2598 16 162 6 ≠ 6 16 10 2 Ω 2 0 10 Ω A Reading the remainders upwards, 259810 = A2616. Conversion of 0.67510 Given fraction is 0.675 0.675 ¥ 16 Ω 10.8 0.800 ¥ 16 Ω 12.8 0.800 ¥ 16 Ω 12.8 0.800 ¥ 16 Ø 12.8 Reading the integers to the left of hexadecimal point downwards, 0.67510 = 0.ACCC16. Therefore, 2598.67510 = A26.ACCC16. Conversion of very large decimal numbers to binary and very large binary numbers to decimal is very much simplified if it is done via the hex route. EXAMPLE 2.58 Convert 4905610 to binary. Solution The given decimal number is very large. It is tedious to convert this number to binary directly. So, convert this to hex first, and then convert the hex to binary.  NUMBER SYSTEMS 63 Successive division Remainder Decimal Hex Binary group 16 49056 16 3066 0 ≠ 0 0000 16 191 10 Ω A 1010 16 11 15 Ω F 1111 0 11 Ω B 1011 Therefore, 4905610 = BFA016 = 1011,1111,1010,00002. EXAMPLE 2.59 Convert 10110111011011102 to decimal. Solution The given binary number is very large. So, perform the binary to decimal conversion via the hex route. 1011, 0111, 0110, 11102 = B 7 6 E16 B76E16 = (11 ¥ 163) + (7 ¥ 162) + (6 ¥ 161) + (14 ¥ 160) = 45056 + 1792 + 96 + 14 = 4695810 2.5.6 Octal to Hexadecimal Conversion To convert an octal number to hexadecimal, the simplest way is to first convert the given octal number to binary and then the binary number to hexadecimal. EXAMPLE 2.60 Convert 756.6038 to hex. Solution Given octal number is 7 5 6. 6 0 3 Convert each octal digit to binary 111 101 110. 110 000 011 Groups of four bits are 0001 1110 1110. 1100 0001 1000 Convert each four-bit group to hex 1 E E. C 1 8 The result is 1EE.C1816 2.5.7 Hexadecimal to Octal Conversion To convert a hexadecimal number to octal, the simplest way is to first convert the given hexadecimal number to binary and then the binary number to octal. EXAMPLE 2.61 Convert B9F.AE16 to octal. Solution Given hex number is B 9 F. A E Convert each hex digit to binary 1011 1001 1111. 1010 1110 Groups of three bits are 101 110 011 111. 101 011 100 Convert each three-bit group to octal 5 6 3 7. 5 3 4 The result is 5637.534 64 FUNDAMENTALS OF DIGITAL CIRCUITS 2.5.8 Hexadecimal Arithmetic The rules for arithmetic operations with hexadecimal numbers are similar to the rules for decimal, octal and binary systems. Arithmetic operations are not done directly in hex. The hex numbers are first converted into binary and arithmetic operations are done in binary. Hexadecimal subtraction can be performed using 1’s complement method or 2’s complement method. However, hexadecimal subtraction can also be performed directly by15’s and 16’s complement methods similar to the 9’s and 10’s complement methods of decimal system. EXAMPLE 2.62 (a) Add 6E16 and C516, (b) subtract 7B16 from C416 and (c) subtract 5D16 from 3A16. Solution (a) 6E16 = 0110 1 1 1 02 + C516 = +1100 0 1 0 12 13316 10011 0 0 1 12 (b) C416 = 1100 0 1 0 02 – 7B16 = +1000 0 1 0 12 (2’s complement form of –7B16) 4916 = 01 0 0 1 0 0 12 (Ignore the carry. Answer is positive) (c) 3A16 = 0011 1 0 1 02 –5D16 = +1010 0 0 1 12 (2’s complement of –5D16) –2316 1101 1 1 0 12 (No carry. Answer is negative) 2’s complement of 1 1 0 1 1 1 0 12 = – 0 0 1 0 0 0 1 1 = – 2316 Multiplication and division can also be performed using the binary representation of hexadecimal numbers and then making use of multiplication and division rules of binary numbers. EXAMPLE 2.63 Convert the following numbers with the given radix to decimal and then to binary. (a) 44335 (b) 119912 (c) 56547 (d) 12213 Solution To convert the given number in any number system into decimal use sum of weights method. The obtained decimal number can be converted into binary by sum of weights method or by successive division by 2 method. (a) 44335 = 4 ¥ 53 + 4 ¥ 52 + 3 ¥ 51 + 3 ¥ 50 = 4 ¥ 125 + 4 ¥ 25 + 3 ¥ 5 + 3 ¥ 1 = 61810 61810 = 512 + 0 + 0 + 64 + 32 + 0 + 8 + 0 + 2 + 0 = 1 0 01 1 0 1 0 1 02 (b) 119912 = 1 ¥ 123 + 1 ¥ 122 + 9 ¥ 121 + 9 ¥ 120 = 1 ¥ 1728 + 1 ¥ 144 + 9 ¥ 12 + 9 ¥ 1 = 198910 198910 = 1024 + 512 + 256 + 128 + 64 + 0 + 0 + 0 + 4 + 0 + 1 = 1 1 1 1 1 0 0 0 1 0 12  NUMBER SYSTEMS 65 (c) 56547 = 5 ¥ 73 + 6 ¥ 72 + 5 ¥ 71 + 4 ¥ 70 = 5 ¥ 343 + 6 ¥ 49 + 5 ¥ 7 + 4 ¥ 1 = 204810 204810 = 2048 + 0 + 0 + 0 + 0 + 0 + 0 + 0+ 0+ 0 + 0 + 0 = 1 0 0 0 0 0 0 0 0 0 0 02 (d) 12213 = 1 ¥ 33 + 2 ¥ 32 + 2 ¥ 31 + 1 ¥ 30 = 1 ¥ 27 + 2 ¥ 9 + 2 ¥ 3 + 1 ¥ 1 = 5210 5210 = 32 + 16 + 0 + 4 + 0 + 0 = 1 1 0 1 0 02 EXAMPLE 2.64 List the first 20 numbers in base 3, base 5, base 7 and base 12 systems. Solution The first 20 numbers in different bases are given in Table 2.5. Table 2.5 First 20 numbers in different bases Base Base Decimal 3 5 7 12 Decimal 3 5 7 12 0 0 0 0 0 10 101