Number Systems and Codes

Additional  Reference:

Number Systems 1

Number Systems 2

Number Systems 3

RADIX NUMBER SYSTEMS

Convert base-r system to Decimal system

Here, we will learn how to work with numbers having arbitrary bases, although we will focus on the bases most used in digital computers, such as base 2 (binary), and its close cousins base 8 (octal), and base 16 (hexadecimal.) The base, or radix of a number system defines the range of possible values that a digit may have. In the base 10 (decimal) number system, one of the 10 values: 0,1, 2, 3, 4, 5, 6, 7, 8, 9 is used for each digit of a number. The most natural system for representing numbers in a computer is base 2, in which data is represented as a collection of 1’s and 0’s.

The general form for determining the decimal value of a number in a radix k fixed point number system is shown below:

The value of the digit in position i is given by bi. There are n digits to the left of the radix point and there are m digits to the right of the radix point. This form of a number, in which each position has an assigned weight, is referred to as a weighted position code. Consider evaluating (541.25)10, in which the subscript 10 represents the base. We have n = 3, m = 2, and k = 10:

The above equation can be re-written as;

Consider another example, 27.35.This number is actually equal to 2 tens plus 7 units plus 3 tenths plus 5 hundredths, or 2 x 10 + 7 x 1 + 3 x 0.1  + 5 x 0.01. The decimal point is used to separate the integer and fractional parts of the number.

More rigorously, the various positions relative to the decimal point carry weights that can be expressed as powers of 10.This is illustrated in Figure below, where the number 2745.214 is represented. The decimal point separates the positive powers of 10 from the negative powers.The number 2745.214 is thus equal to

In general, any number is simply the sum of the products of each digit value and its positional value.

In general, any number expressed in a base-r system has coefficients multiplied by powers of r:

When we write decimal (base 10) numbers, we use a positional notation; each digit is multiplied by an appropriate power of 10 depending on its position in the number.  Similarly, for binary (base 2) numbers, each binary digit is multiplied by the appropriate power of 2:

In the BINARY SYSTEM there are only two symbols or possible digit values, 0 and 1.  Even so, this base-2 system can be used to represent any quantity that can be represented in decimal or other number systems. In general though, it will take a greater number of binary digits to express a given quantity.  All of the statements made earlier concerning the decimal system are equally applicable to the binary system.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. This is illustrated in Figure below.

Here, places to the left of the binary point (counterpart of the decimal point) are positive powers of 2, and places to the right are negative powers of 2.The number 1011.101 is shown represented in the figure. To find its equivalent in the decimal system, we simply take the sum of the products of each digit value (0 or 1) and its positional value:

Let us now consider the base 2 number (1010.01)2 in which n = 4, m = 2, and r = 2:

Note that the binary point separates the positive and negative powers of 2 just as the decimal point separates the positive and negative powers of 10 for decimal numbers.

This suggests how to convert a number from an arbitrary base into a base 10 number using the polynomial method. The idea is to multiply each digit by the weight assigned to its position (powers of two in this example) and then sum up the terms to obtain the converted number. Although conversions can be made among all of the bases in this way, some bases pose special problems, as we will see next.

The Table below shows a 4-bit Binary Number with its equivalent Decimal Value.  It also shows the Weighted Values of a Binary Digit.

Note: in these weighted number systems we define the bit that carries the most weight as the most significant bit (MSB), and the bit that carries the least weight as the least significant bit (LSB). Conventionally the MSB is the leftmost bit and the LSB the rightmost bit.

BINARY NUMBER SYSTEM is a positional system where each binary digit (bit) carries a certain weight based on its position relative to the LSB. Any binary number can be converted to its decimal equivalent simply by summing together the weights of the various positions in the binary number that contain a 1.To illustrate, let’s change an 8-bits Binary Number to its decimal equivalent.

USING A BASE 12 NUMBER SYSTEM.

SUMMARY

Any positive integer R (R >. 1) can be chosen as the radix or base of a number system.  If the base is R, then R digits (0, 1, . . . , R-.1) are used. For example, if R = 8, then the required digits are 0, 1, 2, 3, 4, 5, 6, and 7.  A number written in positional notation can be expanded in a power series in R, as shown above.  Where ai is the coefficient of Ri and 0 <= ai >= R.1.  If the arithmetic indicated in the power series expansion is done in base 10, then the result is the decimal equivalent of N.

CONVERSIONS AMONG RADICES

Background analysis:

The base R equivalent of a decimal integer N can be represented as 

Then conversion of a decimal integer to any base R can be carried out using the division method.

This process is continued until we finally obtain an. Note that the remainder  obtained at each division step is one of the desired digits and the least significant digit is obtained first.

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

I.  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 the above equation, 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.

If We now apply the remainder method to convert (23)10 to base 2. As shown in Figure below, the integer is initially divided by 2, which leaves a remainder of 0 or 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 above to produce the result (23)10 = (10111)2.  

Flowchart for Decimal-to-Binary Conversion using Remainder Method.

In general, we can convert any Decimal number or base 10 integer to any other RADIX by simply dividing the integer by the RADIX 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 x 24 + 0 x 23 + 1 x 22 + 1 x 21 + 1 x 20

At this point, we have converted the integer portion of (23.375)10 into base 2.

II.   Converting the Fractional Part of a Fixed Point Number—The Multiplication Method

Background analysis:

This process is continued until we have obtained a sufficient number of digits. Note that the integer part obtained at each step is one of the desired digits and the most significant digit is obtained first.

For the BINARY conversion of the fractional portion of the DECIMAL number, can be accomplished by successively multiplying the fraction by 2 as described below.

A binary fraction is represented in the general form:

                    b–1 x 2 –1  +  b–2  x 2–2  +   b–3 x 2–3  + ...

If we multiply the fraction by 2, then we will obtain the from equation above  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 below), 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.

Below show the entire process of converting the Fractional part from Decimal (Base-10) to Binary (Base-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 8, then we would use a multiplier of 8.

                                                                                                                                                                            METHOD.

We again check the result of the conversion by converting from base 2 back to base 10 using the polynomial method as shown below:

          (.011)2 = 0 x 2-1 + 1 x 2-2 + 1 x 2-3 = 0 + 1/4 + 1/8 = (.375)10.

We now combine the integer and fractional portions of the number and obtain the final result:

                           (23.375)10 = (10111.011)2

SUMMARY.

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 below.

In comparing the base 2 (binary) column with the base 8 (octal) and base 16 (hexa) 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.

SUMMARY.

Representation of Negative Numbers

Up to this point we have been working with unsigned positive numbers. In most computers, in order to represent both positive and negative numbers the first bit in a word is used as a sign bit, with 0 used for plus and 1 used for minus. Several representations of negative binary numbers are possible. The sign and magnitude system is similar to that which people commonly use. For an n-bit word, the first bit is the sign and the remaining n - 1 bits represent the magnitude of the number.Thus an n-bit word can represent any one of 2n-.1 positive integers or 2n-.1 negative integers. Table below, illustrates this for n =. 4.  For example, 0011 represents .+3 and 1011 represents -.3. Note that 1000 represents minus zero in the sign and magnitude system and .-8 in the 2’s complement system. 

The design of logic circuits to do arithmetic with sign and magnitude binary numbers is awkward; therefore, other representations are often used. The 2’s complement and 1’s complement are commonly used because arithmetic units are easy to design using these systems. For the 2’s complement number system, a positive number, N, is represented by a 0 followed by the magnitude as in the sign and magnitude system; however, a negative number, -N, is represented by its 2’s complement, N* and  If the word length is n bits, the 2’s complement of a positive integer N is defined as  for a word length of n bits.

N* = 2n - N

For n = 4,  -N is represented in 2's complement by 16 - N as shown in Table below. For example,  -.3 is represented by 16 - 3 = 1310=11012. As is the case for sign and magnitude numbers, all negative 2’s complement numbers have a 1 in the position furthest to the left (sign bit).

For the 1’s complement system a negative number, -N, is represented by its 1’s complement, ~N. The 1’s complement of a positive integer N is defined as

~N = (2n - 1) - N

We can also say that the  1’s complement (~N) is 1 less its 2’s complement (N*) or its  2’s complement (N*) is 1 more than its  1’s complement (~N).

  ~N  = (2n - 1) - N = N* - 1

                                                        N*  =  2n - N  = ~N + 1

so the 2’s complement can be formed by complementing N bit-by-bit and then adding 1.  An easier way to form the 2’s complement of N is to start at the right and complement all bits to the left of the first 1. For example, if  N = 0101100, then N* = 1010100

Signed Magnitude

The signed magnitude (also referred to as sign and magnitude) representation is most familiar to us as the base 10 number system. A plus or minus sign to the left of a number indicates whether the number is positive or negative as in +1210 or -1210. In the binary signed magnitude representation, the leftmost bit (MSB) is used for the sign, which takes on a value of 0 or 1 for ‘+’ or ‘-’, respectively. The remaining bits contain the absolute magnitude. Consider representing +1210 and -1210 in an eight-bit format:

+1210 = 000011002

-1210 =  100011002

The negative number is formed by simply changing the sign bit in the positive number from 0 to 1. Notice that there are both positive and negative representations for zero: 00000000 and 10000000.

There are eight bits in this example format, and all bit patterns represent valid numbers, so there are 28 = 256 possible patterns. Only 28 - 1 = 255 different numbers can be represented, however, since +0 and -0 represent the same number.

Excess Representation 

In the excess or biased representation, the number is treated as unsigned, but is “shifted” in value by subtracting the bias from it. The concept is to assign the smallest numerical bit pattern, all zeros, to the negative of the bias, and assign the remaining numbers in sequence as the bit patterns increase in magnitude. A convenient way to think of an excess representation is that a number is represented as the sum of its two’s complement form and another number, which is known as the “excess,” or “bias.” Refer to Table below at the rightmost column, for Excess-4 examples .

Consider representing (+3)10 and (-3)10 in an three-bit format, using an excess 4 representation. An excess 4 number is formed by adding 4 to the original number, and then creating the unsigned binary version.  For (+3)10, we compute (4 + 3 = 7)10 and produce the bit pattern (111)2. For (-3)10, we compute (4 + -3 = 1)10 and produce the bit pattern (001)2:

Note that there is no numerical significance to the excess value: it simply has the effect of shifting the representation of the two’s complement numbers.

There is only one excess representation for 0, since the excess representation is simply a shifted version of the two’s complement representation. For the previous case, the excess value is chosen to have the same bit pattern as the largest negative number, which has the effect of making the numbers appear in numerically sorted order if the numbers are viewed in an unsigned binary representation.

Thus, the most negative number is (-4)10 = (000)2 and the most positive number is (+3)10 = (111)2. This representation simplifies making comparisons between numbers, since the bit patterns for negative numbers have numerically smaller values than the bit patterns for positive numbers. This is important for representing the exponents of floating point numbers, in which exponents of two numbers are compared in order to make them equal for addition and subtraction.

Binary Codes

Although most large computers work internally with binary numbers, the input/output equipment generally uses decimal numbers. Because most logic circuits only accept two-valued signals, the decimal numbers must be coded in terms of binary signals. In the simplest form of binary code, each decimal digit is replaced by its binary equivalent. 

For example, 937.25 is represented by

This representation is referred to as binary-coded-decimal (BCD) or more explicitly as 8-4-2-1 BCD. Note that four bits are always used for each digit and that the result is quite different than that obtained by converting the number as a whole into binary.  The BCD code, then, represents each digit of the decimal number by a four-bit binary number. Clearly only the four-bit binary numbers from 0000 through 1001 are used. The BCD code does not use the numbers 1010, 1011, 1100, 1101, 1110, and 1111. In other words, only 10 of the 16 possible four-bit binary code groups are used and 1010 through 1111 are not valid BCD codes.

Convert  this BCD 0110100000111001 to its decimal equivalent.

Group the BCD number into four-bit  and convert each to decimal.

0110  1000  0011 1001

  6        8       3        9

Comparison of BCD and Binary

It is important to realize that BCD is not another number system like binary, decimal, and hexadecimal. In fact, it is the decimal system with

each digit encoded in its binary equivalent. It is also important to understand that a BCD number is not the same as a straight binary number. A straight binary number takes the complete decimal number and represents it in binary; the BCD code converts each decimal digit to binary individually.

To illustrate, take the number 137 and compare its straight binary and BCD codes:

13710 . --> 10001001           (binary)

13710  .-->  0001 0011 0111 (BCD)

The BCD code requires 12 bits, while the straight binary code requires only eight bits to represent 137. BCD requires more bits than straight binary to represent decimal numbers of more than one digit because BCD does not use all possible four-bit groups, as pointed out earlier, and is therefore somewhat inefficient.

The main advantage of the BCD code is the relative ease of converting to and from decimal. Only the four-bit code groups for the decimal digits 0 through 9 need to be remembered. This ease of conversion is especially important from a hardware standpoint because in a digital system, it is the logic circuits that perform the conversions to and from decimal.

Table below shows several possible sets of binary codes for the ten decimal digits.

Many other possibilities exist because the only requirement for a  valid code is that each decimal digit be represented by a distinct combination of binary digits. To translate a decimal number to coded form, each decimal digit is replaced by its corresponding code. Thus 937 expressed in excess-3 code is 1100 0110 1010. The 8-4-2-1 (BCD) code and the 6-3-1-1 code are examples of weighted codes. A 4-bit weighted code has the property that if the weights are w3, w2, w1, and w0, the code a3a2a1a0 represents a decimal number N, where

                        N = a3w3 + a2w2 + a1w1 + a0w0

For example, the weights for the 6-3-1-1 code are w3=6, w2=3, w1=1, and w0=1.  The binary code 1011 thus represents the decimal number N, where               

                      N = a3w3 + a2w2 + a1w1 + a0w0

                            = 1*6 + 0*3 + 1*1 + 1*1

                            = 8

The excess-3 code is obtained from the 8-4-2-1 code (BCD Code) by adding 3 (0011) to each of the codes.

The 2-out-of-5 code has the property that exactly 2 out of the 5 bits are 1 for every valid code combination. This code has useful error-checking properties because if any one of the bits in a code combination is changed due to a malfunction of the logic circuitry, the number of 1 bits is no longer exactly two. 

Gray code has the property that the codes for successive decimal digits differ in exactly one bit. For example, the codes for 6 and 7 differ only in the fourth bit, and the codes for 9 and 0 differ only in the first bit. A Gray code is often used when translating an analog quantity, such as a shaft position, into digital form. In this case, a small change in the analog quantity will change only one bit in the code, which gives more reliable operation than if two or more bits changed at a time.

The Gray and 2-out-of-5 codes are not weighted codes. In general, the decimal value of a coded digit cannot be computed by a simple formula when a non-weighted code is used.

Digital systems operate at very fast speeds and respond to changes that occur in the digital inputs. Just as in life, when multiple input conditions are changing at the same time, the situation can be misinterpreted and cause an erroneous reaction.

In order to reduce the likelihood of a digital circuit misinterpreting a changing input, the Gray code has been developed 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. Table below shows the translation between three-bit binary and Gray code values. 

To convert binary to Gray, simply start on the most significant bit and use it as the Gray MSB as shown in Figure below. Now compare the MSB binary with the next binary bit (B1). If they are the same, then G1=0. If they are different, then G1=1. G0 can be found by comparing B1 with B0.

Conversion from Gray code back into binary is shown in above Figure (b).  Note that the MSB in Gray is always the same as the MSB in binary. The next binary bit is found by comparing the binary bit to the left with the corresponding Gray code bit. Similar bits produce a 0 and differing bits produce a 1.

PUTTING THEM ALL TOGETHER (Decimal, Binary, Hex, BCD, GRAY) 

Table below gives the representation of the decimal numbers 1 through 15 in the binary and hex number systems and also in the BCD and Gray codes.  Examine it carefully and make sure you understand how it was obtained.  Especially note how the BCD representation always uses four bits for each decimal digit.

Homework-02 (1 week Deadline)

1) Express the following Decimal Numbers (Base-10) to its equivalent Binary, Octal and Hex Values.

     a) 757.25

     b) 123.17

     c) 356.89

     d) 1063.5

2) Express the following Hex Numbers (Base-16) to its equivalent Binary, Octal and Decimal Values.

     a) EB1.6

     b) 59D.C

     c) DEC.A

3) Express this Base-14 Number (3BA.25)14  to its equivalent Decimal and Base-6 Number Values.

4) Express this Decimal Number 1457.11 to   (A) its equivalent Binary, Octal and Hex Values. 

                                                                                   (B) its equivalent Base-4 Number

5) Express the following Decimal Numbers (Base-10) to its equivalent Binary and Hex Values.

a)  1305.375

b)  11.33

c)  301.12

d)  1644.875

6) Express the following Binary Numbers to its equivalent  Octal, Hex and Decimal Values.

a) 101 111 010 100.101

b) 100 001 101 111.010

7)   Convert this   (a) Base-11 Number (A52.A4)11   to its equivalent Base-9 Value.

                                 (b)  Base-9 Number (544.1)9   to its equivalent Hex and Binary Values.

                                 (c)  Decimal Number 97.7     to its equivalent  Binary , Base-3 and Base-5 Number Values.

                                   (d)  Base-3 Number (1110212.20211)3   to its equivalent  Base-9 Number Value.

8) Using Decimal Number from 0 to 15,  give the corresponding 4-bits BINARY codes and Gray Codes using the conversion Algorithm.

      Then create a Program using any Language that will convert 4 bits Binary code to its equivalent Gray Code and Vise-versa.