Chapter 3: Representation and Coding of Information PDF

CHAPTER 3. REPRESENTATION AND CODING OF INFORMATION IN THE MACHINE  The various information present in central memory Representation of negative numbers Representation of real numbers BCD and EXCESS3 encoding Representation of characters 1. Representation of integer nu...

CHAPTER 3. REPRESENTATION AND CODING OF INFORMATION IN THE MACHINE  The various information present in central memory Representation of negative numbers Representation of real numbers BCD and EXCESS3 encoding Representation of characters 1. Representation of integer numbers [Henoune, 2024] There are two types of integers: – unsigned integers (positive) – and signed integers (positive or negative) Problem: How do you tell the machine if a number is negative or positive? There are 3 methods to represent negative numbers: – Sign/absolute value – 1’s complement (restricted complement) – 2’s complement (true complement) 1.1. Sign/absolute value representation (S/VA) [Henoune, 2024] On n bits, the most significant bit is used for indicate the sign: 1: negative sign 0: positive sign The other bits ( n -1 ) designate the absolute value of the number. Example: If we work on 4 bits. 1,001 0 001 Absolute value Absolute value Sign Sign 1001 is the representation of -1 0001 is the representation of +1 On 3 bits [Henoune, 2024]: sign VA value Values are between -3 and +3 0 00 +0 0 01 +1 0 10 +2 - 3 ≤ N ≤ +3 0 11 +3 - ( 4-1 ) ≤ N ≤ + (4 -1 ) - (22-1 -1) ≤ N ≤ +(22 -1 ) 1 00 -0 1 01 -1 - (2(3-1) -1) ≤ N ≤ +(2 (3-1) -1 ) 1 10 -2 1 11 -3 On n bits, the range of values that can be represented in S/VA : - (2(n-1) -1) ≤ N ≤ +(2 (n-1) -1 )  Advantages and disadvantages of Sign/Absolute Value representation [Henoune, 2024] Simple representation. The value zero has two representations +0 and -0 which leads to difficulties in arithmetic operations. For arithmetic operations we need two circuits: one for addition and the second for subtraction. The ideal is to use a single circuit to do both operations, because : a- b =a + ( -b )  1.2. One's complement representation (restricted complement) [Henoune, 2024] We call the one's complement of a number N another number N' such as: N+N'=2n -1 n : is the number of bits in the representation of the number N. Example. Let N=1010 on 4 bits, therefore its one's complement of N: N'= (24 - 1)-N N'=(16-1)10-(1010)2= (15)10 - (1010)2 = (1111) 2 – (1010) 2 = (0101) 2 1 0 1 0 + 0 1 0 1 1 1 1 1 Note 1. [Henoune, 2024] To find the one's complement of a number, simply to invert all the bits of this number: if the bit is a 0 put a 1 in its place and if it is a 1 put a 0 in its place. Example. Sur 4 Bits Sur 5 Bits 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 Note 2. [Henoune, 2024]  The most significant bit indicates the sign (0: positive, 1: negative). 1’s C(1’s C(N))= N Example. What is the decimal value represented by the value 101010 in one’s complement on 6 bits ? The most significant bit indicates that it is a negative number. Value = - 1’s C(101010) = - (010101) 2 = - (21) 10 On 3 bits: [Henoune, 2024] Value in Value in Value 1’s C binary decimal 000 000 +0 001 001 +1 010 010 +2 011 011 +3 100 - 011 -3 101 - 010 -2 110 - 001 -1 111 - 000 -0  The most significant bit tells us the sign.  zero also has a double representation (+0 and –0).  [Henoune, 2024] On 3 bits, the values are between -3 and +3 -3 ≤ N ≤ +3 - ( 4-1 ) ≤ N ≤ + (4 -1 ) -(22 -1) ≤ N ≤ +(22-1 ) -(2 (3 -1) -1) ≤ N ≤ +(2 (3 -1) -1 ) On n bits, the range of values that can be represented in 1’s C : -(2 (n -1) -1) ≤ N ≤ +(2 (n -1) -1 ) 1.3. 2's Complement (true complement) [Henoune, 2024] If we assume that a is a number on n bits then: a + 2n = a modulo 2n and if we take the result on n bits we will obtain the same value as a. a + 2 n= a Example. Let a = (1001)2 on 4 bits (2n) 10=(24 ) 10= (16) 10 =(10000)2 1 0 0 1 + 1 0 0 0 0 1 1 0 0 1 If we take the result on 4 bits we find the same value of a = 1001  [Henoune, 2024] a and b two integers on n bits, the subtraction can be reduced to an addition: a – b = a + (-b)  To do this, we need to find a value equivalent to -b ? a – b = a + 2n – b = a + (2n – 1) – b + 1 We have b + 1’s C(b)= 2n – 1 therefore 1‘s C(b) = (2n – 1) – b If we replace in the first equation we get: a– b = a + 1‘s C(b) + 1  The value 1’s C(b)+1 is called the two's complement of b: 1‘s C(b)+1 = 2‘s C(b)  we will obtain: a - b = a+ 2’s C(b) transform the subtraction into an addition. Example.  [Henoune, 2024] Find the true complement of : 01000101 on 8 bits? 2‘sC (01000101)= 1‘sC(01000101)+ 1 1‘sC (01000101)= (10111010) 2’sC (01000101)=(10111010)+ 1 = (10111011) Note 1. [Henoune, 2024] To find the 2‘s Complement of a number: you must go through the bits of thisnumber starting from the least significant and keep all the bits before the first 1 and invert the other bits that come after. Note 2. [Henoune, 2024]  The most significant bit indicates the sign (0: positive, 1: negative). 2‘s C(2‘s C(N))= N Example. [Henoune, 2024] What is the decimal value represented by the value 101010 in two’s C on 6 bits ?  The most significant bit indicates that it is a negative number.  Value = - 2’s C (101010) = - (010101 + 1) = - (010110)2 = - ( 22) 10  On 3 bits: [Henoune, 2024] Value in Value in binary value 2‘s C 000 000 +0 001 001 +1 010 010 +2 011 011 +3 100 - 100 -4 101 - 011 -3 110 - 010 -2 111 - 001 -1  The most significant bit indicates the sign.  zero does not have a double representation.  [Henoune, 2024] On 3 bits we notice that the values are between - 4 and +3 - 4 ≤ N ≤ +3 - 4 ≤ N ≤ + (4 -1 ) - 22 ≤ N ≤ +(22-1 ) - 2 (3 -1) ≤ N ≤ (2 (3 -1) -1 ) On n bits, the range of values that can be represented in 2’s C : -(2 (n -1) ) ≤ N ≤ +(2 (n -1) -1 )  Two's complement representation (true complement) is the most commonly used representation for representing negative numbers in the machine.  Arithmetic operations in 2’sC [Henoune, 2024] Perform the following operations on 5 Bits, using the 2’s C representation 01001 01001 + + +9 +9 11100 00100 -4 +4 +5 + 13 1 00101 01101 The result is positive Report (01101) 2 = (13) 10 The result is positive (00101) 2 = ( 5) 10  10111 10111 -9 + -9 + 11100 01001 -4 +9 - 13 +0 1 10011 1 00000 Report Report The result is negative: Result = - 2‘s C (10011) = -( 01101) The result is positive = - 13 (00000) 2 = ( 0) 10  Carry and overflow [Henoune, 2024]  We say that there is a carry if an arithmetic operation generates a report  We say that there is an overflow if the operation result on n bit is false. – The number of bits used is insufficient to contain the result – The result exceeds the range of values on the n bits used.  Overflow case [Henoune, 2024] 0 1 1 0 0 1 0 0 1 1 0 1 1 1 +9 + + -9 0 1 0 0 0 1 1 0 0 0 +8 -8 + 17 1 0 0 0 1 - 17 0 1 1 1 1 Négatif Positif  If the sum of two positive numbers gives a negative number, we have an overflow  Or the sum of two negative numbers gives a positive number  There is never an overflow if the two numbers have different signs.  2. The representation of real numbers [Henoune, 2024]  A real number composed of two parts: the integer part and the fractional part (the two parts are separated by a comma). Problem: how to tell the machine the position of the comma ?  There are two methods for representing real numbers : – Fixed point: the position of the comma is fixed – Floating point: the position of the comma changes (dynamic)  2.1. Fixed point representation [Henoune, 2024]  In this representation the integer part is represented on n bits and the fractional part on p bits plus one bit is used for the sign.  Example: if n=3 and p=2 we will have the following values Sign IP FP value 0 000 00 + 0.0 In this representation the 0 000 01 + 0.25 values are limited and 0 000 10 + 0.5 we do not have great 0 000 11 + 0.75 precision 0 001 00 + 1.0........  2.2. Floating point representation  [Henoune, 2024] Each real number can be written as follows: , N= ± M * b e M :, mantissa, b : base, e : exponent Example. 15,6 = 0,156 * 10+2 - ( 110,101)2 = - (0,110101)2 * 2+3 (0,00101)2= ( 0,101)2 * 2-2 Notice. The mantissa is said to be normalized if the first digit after the comma is different from 0 and the first digit before the comma is equal to 0.  [Henoune, 2024] In this representation on n bit : – The mantissa is in the form Sign/Absolute Value 1 bit for the sign k bits for the value – The exponent (positive or negative) is represented on p bits. Sign Exponent Mantissa 1 bit p bits k bits  For the representation of the exponent we use: Two's Complement Shifted or biased exponent  Two's complement exponent representation [Henoune, 2024]  We want to represent the numbers (0.015) 8 and -(15.01) 8 in floating point on a machine having the following format: Mantissa sign Exponent in 2‘s C Normalized Mantissa 1 bit 4 bits 8 bits (0,015)8=(0,000001101)2= 0,1101 * 2-5 Mantissa sign : positive (0) Normalized mantissa : 0,1101 Exponent = -5  use two's Complement to represent the -5 On 4 bits 2’s C(0101)=1011 0 1011 11010000 1 bit 4 bits 8 bits  - (15,01)8 = - (001101,000001)2= - 0,1101000001 * 24 Mantissa sign : negative (1) Normalized mantissa : 0,1101000001 Exponent = 4, in two's complement it keeps the same value (0100) We note that the mantissa is on 10 bits (1101 0000 01), and on the machine only 8 bits are used for the mantissa. In this case we will take the first 8 bits of the mantissa 1 0100 11010000 1 bit 4 bits 8 bits Notice. [Henoune, 2024] if the mantissa is on k bits and if it is represented on the machine on k’ bits such that k> k', then the mantissa will be truncated: we will take only k' bits  lose in precision.  The Shifted Exponent (biased) [Henoune, 2024]  in 2's complement, the interval of values that can be represented on p bits: - 2 (p -1) ≤ N ≤ 2 (p -1) -1 If we add the value 2(p -1) to all the terms of this inequality: - 2 (p -1) + 2 (p -1) ≤ N + 2 (p -1) ≤ 2 (p -1) - 1 + 2 (p -1) 0 ≤ N + 2 (p -1) ≤ 2p -1 We set N’= N + 2 (p -1) therefore: 0 ≤ N’ ≤ 2p -1 In this case we obtain positive values. The value 2p-1 is called the bias or the shift  [Henoune, 2024] With the biased exponent we transformed the exponents negative to positive exponents by adding to the exponent the value 2p -1. Biased Exponent = True Exponent + Bias Example. [Henoune, 2024] We want to represent the numbers (0.015) 8 and -(15.01 ) 8 in floating point on a machine having the following format : Mantissa Sign Biased Exponent Normalised Mantissa 1 bit 4 bits 11 bits (0.015) 8=(0.000001101) 2= 0.1101* 2-5 Mantissa sign : positive (0) Normalized mantissa : 0,1101 True exponent = -5 Calculate the bias: b= 24-1 = 8 Biased Exponent = -5 + 8 = +3 = ( 0011) 2 0 0011 1 1 0 1 0 0 0 0 0 0 0 1 bit 4 bits 11 bits - (15,01)8=(001101,000001)2= 0,1101000001 * 24 Mantissa sign: negative (1) Normalized mantissa : 0.1101000001 True exponent = + 4 Calculate the bias: b= 24-1 = 8 Biased Exponent = 4 + 8 = +12 = (1100) 2 1 1100 11010000010 1 bit 4 bits 11 bits  Floating Point Arithmetic Operations [Henoune, 2024]  Let two real numbers N1 and N2 be such that N1 = M1*be1 N2 = M2*be2  We want to calculate N1+N2?  Two cases arise: If e1 = e2 then N3= (M1+M2) be1 If e1 e2 then raise to the largest exponent and add the mantissas and then normalize the mantissa of the result. Example Perform the following operation: (0.15) 8+ (1.5) 8=(?) (0,15)8= (0,001101) 2 = 0,1101 *2-2 (1,5)8= (001, 101) 2 = 0,1101 *21 (0,15)8+ (1,5)8 = 0,1101 *2-2 + 0,1101 *21 = 0,0001101 *21 + 0,1101 *21 = 0, 1110101 * 21 0 0001 111010 1 bit 4 bits 6 bits Exercise. [Henoune, 2024] Give the representation of the two numbers N1=(-0.014)8 and N2=(0.14)8 on the following machine : Sign Biased (shifted) Normalized mantissa mantissa exponent 1 bit 5 bits 10 bits Calculate N2-N1 ? Before representing the two numbers we must calculate the bias (shift) B = 2 5-1 = 24 = 16 N1 = (-0,014) 8 = (-0,000001100) 2= (-0,1100) 2 * 2 - 5 ExpB= -5 + 16 = 11 = (01011)2 N2 = (0,14)8 = (0,001100)2= (0,1100)2 * 2 -2 ExpB = -2 + 16 = 14 = (01110) 2 So we will have the following representation for N1 and N2: N1 1 01011 1100000000 1 010 1111 0000 0000 ( AF00)16 N2 0 01110 1100000000 0011 10 11 0000 0000 (3B00)16 1 bit 5 bits 10 bits  Calculate N2-N1 ? Solution.  The calculations without  The calculations with the the biased exponent : biased exponent : Biased exponent = 14 True Exponent = Biased Exponent – Bias True exponent = 14 – 16 = -2 So we find the same result as the first operation.  The IEEE 754 standard. The IEEE 754 standard defines a standardized format, unifying the representation of floating point numbers : - 32-bit simple-precision format - 64-bit double-precision format The mantissa is normalized in the form ± 1,M *2±c where M is called a pseudo-mantissa. The 1 preceding the comma is not coded in machine and is called a hidden bit. Bias= 2p -1 -1 Exemple. Let's represent the number –(10,125)10 according to IEEE 754 single precision format. (10,125)10 = (1010,001)2 = (1,010001)2 × 23 True Exponent = 3, Bias= 28 -1 -1 =27 -1 = 128-1=127. Biased Exponent = TExp+Bias = (130)10 = (10000010)2 The sign of the mantissa is negative = 1. The encoding therefore gives the binary string : (1 10000010 01000100000000000000000)2 = (C1220000)16 3. BCD coding (Binary Coded Decimal) [Henoune, 2024] , Décimal Binaire  To convert from decimal to binary, successive divisions must be performed. 0 0000 There is another simplified method for 1 0001 converting from decimal to binary. 2 0010 3 0011  The principle is to make splitting into 4 bits 4 0100 and replacing each decimal digit with its 5 0101 corresponding binary value. 6 0110 7 0111  Combinations greater than 9 are prohibited 8 1000 9 1001 Example 2 8 9 6 3 2 0010 1000 1001 0110 0011 0010 289 = ( 0010 1000 1001)2 632 = (0110 0011 0010)2 EXCESS3 (BCD+3) encoding [Henoune, 2024] Décimal BCD+3 Binaire 0 3 0011 1 4 0100 2 5 0101 1 2 9 3 6 0110 4 7 0111 5 8 1000 0100 0101 1100 6 9 1001 7 10 1010 8 11 1011 9 12 1100  Reflected binary code [Henoune, 2024] In this GRAY code, a single bit changes it‘s value between two successive encodings. The same combinations are copied below existing combinations, but by writing them in the opposite order. Example. Convert the following transformations : Rules. (11101,101)2=(?)gray (10011,111)gray=(?)2 Solution. 4. Character encoding [Henoune, 2024]  Characters include: alphabetic letters (A, a, B, b,..), and other symbols, the numbers, and other symbols ( > , ; / : …. ).  The most widely used encoding is ASCII (American Standard Code for Information Interchange)  In this encoding each character is represented on 8 bits.  With 8 bits we can have 28 = 256 combinations  Each combination represents a character - Example : Code 65 (01000001) 2 corresponds to the character A Code 97 (01100001) 2 corresponds to the character a Code 58 (00111010) 2 corresponds to the character :  There is another code in 16-bit, This code is called UNICODE.