NUMBER SYSTEMS AND CODES - fu-berlin.de

1 1 NUMBER SYSTEMSAND CODESA rithmetic operations using decimal numbers are quite common. However, in logicaldesign it is necessary to perform manipulations in the so-called binary system of num-bers because of the on-off nature of the physical devices used. The present chapter isintended to acquaint the reader with the fundamental concepts involved in dealing withnumber SYSTEMS other than decimal. In particular, the binary system is covered in con-siderable POSITIONAL NOTATIONAn ordinary decimal NUMBER can be regarded as a polynomial in powers of 10. For ex-ample, can be regarded as 4 102 + 2 101 + 3 100 + 1 10 1 + 2 10 numbers like this are said to be expressed in a NUMBER system with base, orradix, 10 because there are 10 basic digits (0, 1, 2.)

2 , 9) from which the numbersystem is formulated. In a similar fashion we can express any NUMBER N in a systemusing any base b. We shall write such a NUMBER as (N)b . Whenever (N)b is written,the convention of always expressing b in base 10 will be followed. Thus (N)b = (pnpn 1 .. p1p0 . p 1p 2 .. p m )b where b is an integer greater than 1 and 0 < pi < b 1. The value of a NUMBER represented in this fashion, which is called positionalnotation, is given by(N)b = pn bn + pn-1 bn-1 + .. + p0 b0 + p-1 b-1 ( )+ p-2 b-2+ .. + p m b mn(N)b = pi bi( )i = -m1 For decimal numbers, the symbol . is called the decimal point; for more gen-eral base-b numbers, it is called the radix point.

3 That portion of the NUMBER to theright of the radix point (p-1p-2 .. p m ) is called the fractional part, and the portion tothe left of the radix point (pnpn 1 .. p0 ) is called the integral expressed in base 2 are called binary numbers. They are often usedin computers since they require only two coefficient values. The integers from 0 to 15are given in Table for several bases. Since there are no coefficient values for therange 10 to b 1 when b > 10, the letters A, B, C, .. are used. Base-8 numbers arecalled octal numbers, and base-16 numbers are called hexadecimal and hexadecimal numbers are often used as a shorthand for binary numbers.

4 Anoctal NUMBER can be converted into a binary NUMBER by converting each of the octal co-efficients individually into its binary equivalent. The same is true for hexadecimalnumbers. This property is true because 8 and 16 are both powers of 2. For numberswith bases that are not a power of 2, the conversion to binary is more Conversion of BaseTo make use of nondecimal NUMBER SYSTEMS , it is necessary to be able to convert anumber expressed in one base into the correct representation of the NUMBER in anotherbase. One way of doing this makes direct use of the polynomial expression ( ).For example, consider the binary NUMBER ( )2.

5 The corresponding polynomialexpression is1 23 + 0 22 + 1 21 + 1 20 + 1 2 1 + 0 2 2 + 1 2 3or8 +2 +1 +1/2 +1/8or11 + 5/8 = Integers in various 160001001 0101010101011001000202020202020220011010 0303030303033010001110040404040440101012 111005050505501100201211060606066(N)b 0111 0211312070707077100002220131008080881001 10021141109090991010101222012100A0AA1011 10223211311100BB1100110302214121110C1101 111312315131211D1110112322416141312E1111 120333017151413F2 NUMBER SYSTEMS and CODES Chap. 1 This technique of directly evaluating the polynomial expression for a NUMBER is ageneral method for converting from an arbitrary base b1 to another arbitrary base convenience, it will be called the polynomial method.

6 This method the NUMBER (N)b1 as a polynomial, with base-b2 numbers used in the polynomial, base-b2 arithmetic being polynomial method is most often used by human beings whenever a numberis to be converted to base 10, since it is then possible to use decimal method for converting numbers from one base to another is the first exampleof one of the major goals of this book: the development of algorithms. In generalterms, an algorithm is a list of instructions specifying a sequence of operations whichwill give the answer to any problem of a given type. The important characteristics ofan algorithm are: (1) that it is fully specified and does not rely on any skill or intuitionon the part of the person applying it and (2) that it always works, ( , that a correctanswer is always obtained.)

7 The notion of an algorithm is discussed in more detail inSection of [Knuth 68].It is not always convenient to use base-b2 arithmetic in converting from base-b1to base-b2 . An algorithm for carrying out this conversion by using base-b1 arithmeticwill be discussed next. This discussion is specifically for the situation in which b1 =10, but it can be extended easily to the more general case. This will be called the it-erative method, since it involves iterated multiplication or converting (N)10 to (N)b the fraction and integer parts are converted , consider the integer part (portion to the left of the decimal point). The generalconversion procedure is to divide (N)10 by b, giving (N)10/b and a remainder.

8 Theremainder, call it p0, is the least significant (rightmost) digit of (N)b. The next leastsignificant digit, p1, is the remainder of (N)10/b divided by b, and succeeding digits areobtained by continuing this process. A convenient form for carrying out thisconversion is illustrated in the following (a)(23)10=(10111)2223(Remainder)21112512 2121001(b)(23)10=(27)8823(Remainder)8270 2 Sec. Positional Notation3(c)(410)10=(3120)55410(Remainde r)5820516253103 Now consider the portion of the NUMBER to the right of the decimal point, , thefractional part. The procedure for converting this is to multiply (N)10 (fractional) by the resulting product is less than 1, then the most significant (leftmost) digit of thefractional part is 0.

9 If the resulting product is greater than 1, the most significant digitof the fractional part is the integral part of the product. The next most significant digitis formed by multiplying the fractional part of this product by b and taking the integralpart. The remaining digits are formed by repeating this process. The process may ormay not terminate. A convenient form for carrying out this conversion is illustrated (a) ( )10 = ( ) x 8 = (b) ( )10 = ( .. ) x 2 = x 2 = x 2 = x 2 = x 2 = x 2 = ..(c) ( )10 = ( .. )2 = ( .. ) x 2 = x 2 = x 2 = x 2 = x 2 = x 2 = .. x 8 = x 8 = ..03 This example illustrates the simple relationship between the base-2 (binary) sys-tem and the base-8 (octal) system.

10 The binary digits, called bits, are taken three at atime in each direction from the binary point and are expressed as decimal digits to givethe corresponding octal NUMBER . For example, 101 in binary is equivalent to 5 indecimal; so the octal NUMBER in part (c) above has a 5 for the most significant digit of thefractional part. The conversion between octal and binary is so simple that the octalexpression is sometimes used as a convenient shorthand for the corresponding NUMBER SYSTEMS and CODES Chap. 1 When a fraction is converted from one base to another, the conversion may notterminate, since it may not be possible to represent the fraction exactly in the new basewith a finite NUMBER of digits.