2.2.4 CONVERSIONS AMONG RADICES
In the previous section, we saw an example of how a base 2 number can be converted into a base 10 number. A conversion in the reverse direction is more involved. The easiest way to convert fixed point numbers containing both integer and fractional parts is to convert each part separately. Consider converting (23.375)10 to base 2. We begin by separating the number into its integer and fractional parts:
(23.375)10 = (23)10 + (.375)10.
Converting the Integer Part of a Fixed Point Number—The Remainder Method
As suggested in the previous section, the general polynomial form for representing a binary integer is: ...
If we divide the integer by 2, then we will obtain:
with a remainder of b0. As a result of dividing the original integer by 2, we discover the value of the first binary coefficient b0. We can repeat this process on the remaining polynomial and determine the value of b1. We can continue iterating the process on the remaining polynomial and thus obtain all of the bi This process forms the basis of the remainder method of converting integers between bases.
We now apply the remainder method to convert (23)10 to base 2. As shown in Figure 2-1, the integer is initially divided by 2, which leaves a remainder of 0 or 1.
Figure 2-1 A conversion from a base 10 integer to a base 2 integer using the remainder method.
1. For this case, 23/2 produces a quotient of 11 and a remainder of 1. The first remainder is the least significant binary digit (bit) of the converted number (the rightmost bit). In the next step 11 is divided by 2, which creates a quotient of 5 and a remainder of 1. Next, 5 is divided by 2, which creates a quotient of 2 and a remainder of 1. The process continues until we are left with a quotient of 0. If we continue the process after obtaining a quotient of 0, we will only obtain 0’s for the quotient and remainder, which will not change the value of the converted number. The remainders are collected into a base 2 number in the order shown in Figure 2-1 to produce the result (23)10 = (10111)2. In general, we can convert any base 10 integer to any other base by simply dividing the integer by the base to which we are converting.
We can check the result by converting it from base 2 back to base 10 using the polynomial method:
(10111)2 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20
= 16 + 0 + 4 + 2 + 1
= (23)10
At this point, we have converted the integer portion of (23.375)10 into base 2.
Converting the Fractional Part of a Fixed Point Number—The Multiplication
Method
The conversion of the fractional portion can be accomplished by successively
multiplying the fraction by 2 as described below.
A binary fraction is represented in the general form:
If we multiply the fraction by 2, then we will obtain:
We thus discover the coefficient b−1. If we iterate this process on the remaining
fraction, then we will obtain successive bi
This process forms the basis of the
multiplication method of converting fractions between bases. For the example
used here (Figure 2-2), the initial fraction (.375)10 is less than 1. If we multiply it
by 2, then the resulting number will be less than 2. The digit to the left of the
radix point will then be 0 or 1. This is the first digit to the right of the radix point
in the converted base 2 number, as shown in the figure. We repeat the process on
the fractional portion until we are either left with a fraction of 0, at which point
only trailing 0’s are created by additional iterations, or we have reached the limit
of precision used in our representation. The digits are collected and the result is
obtained: (.375)10 = (.011)2.
For this process, the multiplier is the same as the target base. The multiplier is 2
here, but if we wanted to make a conversion to another base, such as 3, then we
would use a multiplier of 3
1
Figure 2-2 A conversion from a base 10 fraction to a base 2 fraction using the multiplication meth
od.
We again check the result of the conversion by converting from base 2 back to
base 10 using the polynomial method as shown below:
We now combine the integer and fractional portions of the number and obtain
the final result:
(23.375)10 = (10111.011)2.
Non Terminating Fractions
Although this method of conversion will work among all bases, some precision
can be lost in the process. For example, not all terminating base 10 fractions have
a terminating base 2 form. Consider converting (.2)10 to base 2 as shown in Fig
ure 2-3. In the last row of the conversion, the fraction .2 reappears, and the pro
cess repeats ad infinitum. As to why this can happen, consider that any
non-repeating base 2 fraction can be represented as i/2k
for some integers i and k.
(Repeating fractions in base 2 cannot be so represented.) Algebraically,
Figure 2-3 A terminating base 10 fraction that does not have a terminating base 2 form.
where j is the integer i×5k . The fraction is thus non-repeating in base 10. This hinges on the fact that only non-repeating fractions in base b can be represented as i/bk for some integers i and k. The condition that must be satisfied for a non-repeating base 10 fraction to have an equivalent non-repeating base 2 fraction is:
i/10k = i/(5k ×2k ) = j/2k
where j = i/5k , and 5k must be a factor of i. For one digit decimal fractions, only (.0)10 and (.5)10 are non-repeating in base 2 (20% of the possible fractions); for two digit decimal fractions, only (.00)10, (.25)10, 0,50)10, and (.75)10 are non-repeating (4% of the possible fractions); etc. There is a link between relatively prime numbers and repeating fractions, which is helpful in understanding why some terminating base 10 fractions do not have a terminating base 2 form. (Knuth, 1981) provides some insight in this area.
Binary versus Decimal Representations
While most computers use base 2 for internal representation and arithmetic, some calculators and business computers use an internal representation of base 10, and thus do not suffer from this representational problem. The motivation for using base 10 in business computers is not entirely to avoid the terminating fraction problem, however, but also to avoid the conversion process at the input and output units which historically have taken a significant amount of time.
Binary, Octal, and Hexadecimal Radix Representations
While binary numbers reflect the actual internal representation used in most machines, they suffer from the disadvantage that numbers represented in base 2 tend to need more digits than numbers in other bases, (why?) and it is easy to make errors when writing them because of the long strings of 1’s and 0’s. We mentioned earlier in the Chapter that base 8, octal radix, and base 16, hexadecimal radix, are related to base 2. This is due to the three radices all being divisible by 2, the smallest one. We show below that converting among the three bases 2, 8, and 16 is trivial, and there are significant practical advantages to representing numbers in these bases.
Binary numbers may be considerably wider than their base 10 equivalents. As a notational convenience, we sometimes use larger bases than 2 that are even multiples of 2. Converting among bases 2, 8, or 16 is easier than converting to and from base 10. The values used for the base 8 digits are familiar to us as base 10 digits, but for base 16 (hexadecimal) we need six more digits than are used in base 10. The letters A, B, C, D, E, F or their lower-case equivalents are commonly used to represent the corresponding values (10, 11, 12, 13, 14, 15) in hexadecimal. The digits commonly used for bases 2, 8, 10, and 16 are summarized in Figure 2-4. In comparing the base 2 column with the base 8 and base 16 columns, we need three bits to represent each base 8 digit in binary, and we need four bits to represent each base 16 digit in binary. In general, k bits are needed to
Figure 2-4 Values for digits in the binary, octal, decimal, and hexadecimal number systems.
represent each digit in base 2k , in which k is an integer, so base 23 = 8 uses three bits and base 24 = 16 uses four bits.
In order to convert a base 2 number into a base 8 number, we partition the base 2 number into groups of three starting from the radix point, and pad the outermost groups with 0’s as needed to form triples. Then, we convert each triple to the octal equivalent. For conversion from base 2 to base 16, we use groups of four. Consider converting (10110)2 to base 8:
(10110)2 = (010)2 (110)2 = (2)8 (6)8 = (26)8
Notice that the leftmost two bits are padded with a 0 on the left in order to create a full triplet.
Now consider converting (10110110)2 to base 16:
(10110110)2 = (1011)2 (0110)2 = (B)16 (6)16 = (B6)16
(Note that ‘B’ is a base 16 digit corresponding to 1110. B is not a variable.)
The conversion methods can be used to convert a number from any base to any other base, but it may not be very intuitive to convert something like (513.03)6 to base 7. As an aid in performing an unnatural conversion, we can convert to the more familiar base 10 form as an intermediate step, and then continue the conversion from base 10 to the target base. As a general rule, we use the polynomial method when converting into base 10, and we use the remainder and multiplication methods when converting out of base 10.
No comments:
Post a Comment