COA Lecture Notes Chapter 3: Number Systems & Codes PDF

COA Lecture Notes Chapter 03: Number Systems and Codes Chapter Three Number Systems and Codes 3.1. Introduction 3.1.1. Data Types In computer memory or processor registers either data or con...

COA Lecture Notes Chapter 03: Number Systems and Codes Chapter Three Number Systems and Codes 3.1. Introduction 3.1.1. Data Types In computer memory or processor registers either data or control information is stored. Control information is a bit or a group of bits used to specify the sequence of command signals needed for manipulation of the data in other registers. Data are numbers and other binary-coded information that are operated on to achieve required computational results. The data types found in the registers of digital computers can be classified as follows: - i) Numbers used in arithmetic computations. ii) Letters of the alphabet used in data processing, and iii) Other discrete symbols used for specific purposes. Except binary numbers, all of these data types are represented in computer registers in binary- coded format. 3.1.2. Number System A number system of base r (or radix r) is a system that uses r distinct symbols or digits. The decimal number systems that we use in our day-to-day life are radix 10 system and the 10 symbols are 0, 1, 2, 3, 4, 5, 6, 8 and 9.  The decimal number 724.5 is interpreted as: - 7 x 102 + 2 x 101 + 4 x 100 + 5 x 10-1 Binary number system is radix 2 and the two symbols are 0 and 1.  For example, the string of digits (101101)2 is interpreted to represent an equivalent decimal quantity 1 x 25 + 0 x 24 + 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = (61)10.  To distinguish between different radix numbers, the digits will be enclosed in parentheses, as shown in above examples, and the radix of the number inserted as a subscript. The octal number system (radix 8) and hexadecimal or HEX number system (radix 16) are another important representation used in digital computer.  The octal number system contains symbols 0, 1, 2, 3, 4, 5, 6, and 7 and the HEX contains symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. 3.1.3. Number System Conversions Conversions from Decimal Number System to Others A number system in radix r can be converted to the decimal system by forming the sum of the weighted digits. For example, process of conversions (736.4)8 and (F3)16 to radix 10 is: BireZman ([email protected]) UoG, Computer Science Department 1 COA Lecture Notes Chapter 03: Number Systems and Codes (736.4)8 = 7 x 82 + 3 x 81 + 6 x 80 + 4 x 8-1 = (478.5)10 (F3)16 = F x 161 + 3 x 160 = (243)10 Conversion from decimal to its equivalent representation in the radix r system is carried out by separating the number into its integer and fraction parts, then converting each part separately. The conversion of decimal integer into a base r representation is done by successive divisions by r and accumulation of the remainders. The conversion of a decimal fraction to radix r representation is accomplished by successive multiplication by r and accumulation of the integer digits so obtained. Examples convert the decimal number 41.6875 into its equivalent binary number. Conversions of Octal and Hexadecimal Numbers The conversion from binary to octal is easily accomplished by partitioning the binary number into groups of three bits each. Example 1: The binary number (1010111101100011)2 is equivalent with octal (44899)8. Example 2: Converting binary number (1010111101100011)2 to Octal and HEX, is: - Octal representation 001 010 111 101 100 011 1 2 7 5 4 3 HEX representation 1010 1111 0110 0011 A F 6 3 Since registers of digital computers contain many bits, specifying the contents of registers by their binary values requires a long string of binary digits. Thus, it is more convenient to specify contents of registers by their Octal or HEX equivalent. 3.2. Signed-Integer Representation and Binary Math When an integer variable is declared in a programming language, many programming languages automatically allocate a storage area that includes a sign as the first bit of the storage location. Most common convention is to use the high-order bit for indicating sign of an integer, for example a high-order bit “1” indicates a negative number and a high-order bit “0” indicates the integer is positive. Basically, there are three common methods to represent signed integers (set of positive and negative integers) in computers: - a) The Signed-Magnitude b) The (r-1)’s Complement c) The r’s Complement BireZman ([email protected]) UoG, Computer Science Department 2 COA Lecture Notes Chapter 03: Number Systems and Codes 3.2.1. The Signed-Magnitude Representations The set of positive and negative integers is referred to as the set of signed integers. As its name implies, a signed-magnitude number uses its left-most bit (high-order bit or most-significant bit) to represent sign of the integer and the remaining bits to represent its magnitude or the numeric value. For example, the negative integer -1 is represented in 8-bit memory word as 10000001 and the positive integer +1 represented as 00000001. Using N-bits this method represents range of integers – 2(N – 1) – 1 to 2(N – 1) – 1. Arithmetic in Signed-Magnitude The arithmetic is carried out essentially the same method as humans, which is with pencil and paper. So, you can follow the following rules while performing addition in signed-magnitude. (I) If the signs are the same, add the magnitudes and use the same sign for the result. (II) If the signs differ, you must determine which operand has the larger magnitude. The sign of the result is the same as the sign of the operand with the larger magnitude, and the magnitude must be obtained by subtracting (not adding) the smaller one from the larger one. (III) An Overflow (and thus an erroneous result) in signed numbers occur when the sign of the result is incorrect. Example 1: Addition with Correct Result Example 2: Addition with Erroneous Result Example 3: Subtraction with Correct Result BireZman ([email protected]) UoG, Computer Science Department 3 COA Lecture Notes Chapter 03: Number Systems and Codes 3.2.2. Complements Complements are used in digital computers for simplifying the subtraction operation and for logical manipulation. As stated above, there are two types of complements for a given number in radix r system - the r’s complement and the (r-1)’s complement. The r-1’s Complement Definition: - Given a number N in base r having n digits the (r-1)’s complement of N is (𝐫 𝐧 − 𝟏) − 𝐍 Example 1: Finding (r-1)’s Complement of Decimal Numbers Decimal means r is 10 and the (r-1)’ complement refers to the 9’s complement. Therefore, for a given number N the 9’s complement will be (10n – 1) – N. However, 10n represents a number that consists of a single 1 followed by n 0’s and the value of 10n – 1 is a number represented by n 9’s. Now, let’s compute the 9’s complement of (12389)10. N = 12389 and n = 5 105 = 100000 and 104 – 1 = 99999. The 9’s complement is obtained as: 99999 – 12389 = 87610. Example 2: Finding (r-1)’s Complement of Binary Numbers Here, the (r-1)’s complement means the 1’s complement and for a given n-bits binary number N it will be (2n -1) – N. Again, 2n represented by a binary number that consists of a 1 followed by n 0’s. 2n – 1 is a binary number represented by n 1’s. Using 8-bit the 1’s complement of (23)10 and (9)10 are: - (23)10 = (00010111)2  11111111 - 00010111 = (00010111)2 (9)10 = (00001001)2  11111111 - 00001001 = (11110110)2 The r’s Complement Definition: - Given a number N in base r having n digits the r’s complement of N is:- r n − N, if N ≠ 0 { 0, if N = 0 Comparing with the above (r–1)’s complement, we notice that the r’s complement is obtained by adding 1 to the (r–1)’s complement since rn – N = [(rn – 1) – N] + 1. Example 1: Finding 10’s Complement of Decimal Number 12389 The 9’s complement of decimal 12389 is 87610 Then its 10’s complement is obtained by adding 1 to the 9’s complement. It becomes 87610 + 1 = 87611 BireZman ([email protected]) UoG, Computer Science Department 4 COA Lecture Notes Chapter 03: Number Systems and Codes Example 2: Finding 2’s Complement of Binary Number 00101100 Now its 1’s complement is 11010011 And the 2’s complement becomes 11010011 + 1 = 11010100 FYI: Computing r’s complement to an r’s complement value will restore the number to its original value. In other words, r’s complement of N is rn – N and if we do r’s complement to this, it becomes rn – (rn – N) which gives back N, the original number. Overflow When two numbers of n digits each are added and the sum occupies n + 1 digits, we say that an overflow occurred. The reason is because of the finite number of registers in digital computer, a result that contains n + 1 bits cannot be accommodated in a register with a standard length of n bits. An overflow may occur if the two numbers added both are positive or negative. The detection of an overflow after the addition of two binary numbers depends on whether the numbers are considered to be signed or unsigned. We can notice overflows as follows: - If the carry into the sign bit equals the carry out of the bit, no overflow has occurred. If the carry into the sign bit is different from the carry out of the sign bit, overflow has occurred and thus an error occurred. Example: Addition of two binary numbers that creates an overflow result. 3.3. Floating-Point Binary Binary numbers can also have decimal points, as of decimal numbers, for example the table below demonstrates what the decimal value 6.5342 means. Exponent 3 2 1 0 -1 -2 -3 -4 Position Value 1000 100 10 1 0.1 0.01 0.001 0.0001 Sample Values 0 0 0 6 5 3 4 2 Therefore, the decimal value has 6*1 + 5*0.1 + 3*0.01 + 4*0.001 + 2*0.0001 = 6.5342. Binary representation of real numbers works the same way except that each position represents a power of two, not a power of ten. To convert (10.01101)2 to decimal for example, use descending negative powers of two to the right of the decimal point, as shown below. BireZman ([email protected]) UoG, Computer Science Department 5 COA Lecture Notes Chapter 03: Number Systems and Codes Exponent 2 1 0 -1 -2 -3 -4 -5 Position Value 4 2 1 0.5 0.25 0.125 0.0625 0.03125 Sample Values 0 1 0 0 1 1 0 1 Therefore, the example has the decimal value 0*4 + 1*2 + 0*1 +0*0.5 + 1*0.25 + 1*0.125 + 0*0.0625 + 1*0.03125 = 2.40625. This means that the method of conversion is the same for real numbers as it is for integer values; we've simply added positions representing negative powers of two. Computers, however, use a form of binary more like scientific notation to represent floating- point or real numbers. For example, with scientific notation we can represent the large value 342,370,000 as 3.4237 x 108. This representation consists of a decimal component or mantissa of 3.4237 with an exponent of 8. Both the mantissa and the exponent are signed values allowing for negative numbers and for negative exponents respectively. Binary works the same way using 1's and 0's for the digits of the mantissa and exponent and using 2 as the multiplier that moves the decimal point left or right. For example, the binary number 100101101.010110 would be represented as 1.00101101010110 * 28. The decimal point is moved left for negative exponents of two and right for positive exponents of two. 3.3.1. Floating-Point Representation Example: Simple Model In digital computers, floating-point numbers consist of three parts: a sign bit, an exponent part (representing the exponent on a power of 2) and a fractional part (significand or mantissa). For instance, here below is a simple model that consists 14-bits with a 5-bit exponent, an 8-bit significand and 1-bit to represent the sign. 1 bit 5 bits 8 bits Sign bit Exponent Significand Example: Store the decimal number 17 using this simple model. We know that 17 = 17.0 x 100 = 1.7 x 101 = 0.17 x 102. Analogously, in binary 17 = 10001 x 20 = 1000.1 x 21 = 100.01 x 22 or = 0.10001 x 25. If you take the last one, its binary equivalent in this model will have the following form. 0 00101 10001000 3.3.2. Floating-Point Representations: The IEEE 754 Standard The IEEE Standard 754 is used to represent real numbers on the majority of contemporary computer systems. It utilizes a 32-bit pattern to represent single-precision numbers and a 64- bit pattern to represent double-precision numbers. Each of these bit patterns is divided into BireZman ([email protected]) UoG, Computer Science Department 6 COA Lecture Notes Chapter 03: Number Systems and Codes three parts, each part representing a different component of the real number being stored (Figure 3.1 shows these partitioning of single-precision and double-precision numbers). Figure 3.1: IEEE Standard 754 Floating-Point Formats Both formats work the same differing only by the number of bits used to represent each component of the real number. In general, the components of the single-precision format are substituted into the equation given below, where the sign of the value is determined by the sign bit (0 positive value and 1 negative value). Note that E is in unsigned binary representation. () 𝟏. 𝐅 ∗ 𝟐(𝐄 − 𝟏𝟐𝟕) The following equation is used for the double-precision values. () 𝟏. 𝐅 ∗ 𝟐(𝐄 − 𝟏𝟎𝟐𝟑) In both cases, F is preceded with an implied “1” and a binary point. However, you have to consider the following special cases.  Positive, E=255 and F=0 represents positive infinite.  Negative, E=255 and F=0 represents negative infinite.  Positive or negative, E=0 and F=0 represents zero. Example 1:- Convert the following 32-bit single-precision IEEE Standard 754 number into its binary equivalent. 11010110101101101011000000000000 Solution First, break the 32-bit number into its components as follows:-. 1 10101101 01101101011000000000 Sign Bit Exponent, E Fraction, F A sign bit of 1 means that this will be a negative number. BireZman ([email protected]) UoG, Computer Science Department 7 COA Lecture Notes Chapter 03: Number Systems and Codes The exponent E used to determine the power of two by which our mantissa will be multiplied and to in order to use it, we must first convert it to a decimal integer using the unsigned method. Exponent, E = (10101101)2 = 27 + 25 + 23 + 22 + 20 = 128 + 32 + 8 + 4 + 1 = (173)10 Substituting these components into the above single-precision equation () 𝟏. 𝐅 ∗ 𝟐(𝐄 − 𝟏𝟐𝟕) it will give us the following: = –1.01101101011000000000000 x 2(173-127) = –1.01101101011 x 246 Example 2:- Create the 32-bit single-precision IEEE Standard 754 representation of the binary number 0.000000110110100101 Solution:- Begin by putting the binary number above into the binary form of scientific notation with a single 1 to the left of the decimal point. Note that this is done by moving the decimal point seven positions to the right giving us an exponent of –7. 0.000000110110100101 = 1.10110100101 x 2-7 The number is positive, so the sign bit will be 0. The fraction (value after the decimal point and not including the leading 1) is 10110100101 with 12 zeros added to the end to make it 23 bits. Lastly, the exponent must satisfy the equation: E – 127 = –7 E = –7 + 127 = 120 Converting (120)10 to binary gives us the 8-bit unsigned binary value (01111000)2. Substituting all of these components into the IEEE 754 format gives us: 0 01111000 10110100101000000000 Sign Bit Exponent, E Fraction, F Therefore, the answer is 00111100010110100101000000000000. 3.4. Other Binary Codes 3.4.1. Character Codes Besides the binary number system it is also possible for the computer to perform arithmetic operations directly with decimal numbers provided they are placed in registers in a coded form. Decimal numbers enter the computer usually as binary-coded alphanumeric characters. When BireZman ([email protected]) UoG, Computer Science Department 8 COA Lecture Notes Chapter 03: Number Systems and Codes decimal numbers are used for internal arithmetic computations they are converted to a binary code with four bits per digit. At least four bits are required to represent the 10 decimal numbers in binary but, six combinations remain unassigned. The bit assignment most commonly used for the decimal digits is the straight binary assignment called binary-coded decimal (BCD). Decimal Number BCD 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 --------------------------------------------------- 1111 Unsigned 1112 Positive 1113 Negative It is very important to understand the difference between the conversion of decimal numbers into binary and the binary coding of decimal numbers. For example 99 is represented as 1100011 in binary but in BCD it is 1001 1001. BireZman ([email protected]) UoG, Computer Science Department 9 COA Lecture Notes Chapter 03: Number Systems and Codes 3.4.2. Alphanumeric Representation Alphanumeric character set is a set of elements that includes the 10 decimal digits, the 26 letters of the alphabet and a number of special characters (such as $, +, =, etc.). The standard alphanumeric binary code is the ASCII (American Standard Code for Information Interchange) it uses seven bits to code the 128 characters, as shown in Figure 3.2 below. Figure 3.2: ASCII 7-bits Representation The EBCDIC (Extended Binary Coded Decimal Interchange Code), as the name indicates, it is an expansion of BCD that uses 8-bits. Both EBCDIC and ASCII were built around the Latin alphabet, as such they are not suitable to represent data for non-Latin alphabets. For this reason Unicode is designed, it is a 16-bit alphabet which has the capacity to encode the majority of characters used in every language of the world. The Unicode code space consists of five parts, as shown in Figure 3.3 below. Figure 3.3: Unicode Code Space. BireZman ([email protected]) UoG, Computer Science Department 10 COA Lecture Notes Chapter 03: Number Systems and Codes 3.4.3. Codes for Data Recording and Transmission ASCII, EBCDIC and Unicode are translated into other code before they are transmitted or recorded. This translation is carried out by control electronics within data recording and transmitting devices. Bytes are sent and received by telecommunication devices by using "high" and "low" pulses in the transmission media (copper wire, for example). Magnetic storage devices record data using changes in magnetic polarity called flux reversal. Certain coding methods are better suited for data communications than for data recording, some popular recording and transmission codes are the following:- Non-Return-to-Zero code Non-Return-to-Zero-Inver Encoding Phase Modulation (Manchester coding) Frequency Modulation Run-Length-Limited code. Here is an example that shows how the word "OK" is transmitted using Non-Return-to-Zero code. Figure 3.4: NRZ Encoding of OK as a) As transmission wave form b) As magnetic flux pattern (the direction of the arrow indicates the magnetic polarity). 3.4.4. Error Detection Binary information transmitted through some form of communication medium is subject to external noise that could change bits from 1 to 0, and vice versa. An error detection code is a binary code that detects digital errors during transmission. The detected errors cannot be corrected but their presence is indicated. The usual procedure is to observe the frequency of BireZman ([email protected]) UoG, Computer Science Department 11 COA Lecture Notes Chapter 03: Number Systems and Codes errors. If errors occur infrequently at random, the particular erroneous information is transmitted again. If the error occurs too often, the system is checked for mal function. The most common error detection code used is the parity bit. A parity bit is an extra bit included with a binary message to make the total number of 1’s either odd or even. A message of three bits and two possible parity bits is shown below. xyz P(odd) P(even) 000 1 0 001 0 1 010 0 1 011 1 0 100 0 1 101 1 0 110 1 0 111 0 1 The even-parity scheme has the disadvantage of having a bit combination of all 0’s. Note that the P (odd) is the complement of the P (even). During transfer of information from one location to another, the parity bit is handled as follows. At the sending end, the message (in this case three bits) is applied to a parity generator, where the required parity bit is generated. The message, including the parity bit, is transmitted to its destination. At the receiving end, all the incoming bits (in this case four) are applied to a parity checker that checks the proper parity adopted (odd or even). An error is detected if the checked parity does not conform to the adopted parity. The parity method detects the presence of any odd number of errors. An even number of errors is not detected. Parity generator and checker networks are logic circuits constructed with exclusive-OR functions. BireZman ([email protected]) UoG, Computer Science Department 12