Machine Structure - Abdelhamid Mehri University PDF

Module : MS1 2024-2025 Abdelhamid Mehri University - Constantine 2 2024-2025. Term 1 Machine Structure Chapitre 01 - part-1 Codification an...

Module : MS1 2024-2025 Abdelhamid Mehri University - Constantine 2 2024-2025. Term 1 Machine Structure Chapitre 01 - part-1 Codification and representation of numbers - part-2 α-Numeric coding - part-3 Boolean Algebra Teaching staff Name Grade Faculty/Institute E-mail address Bahri Mohamed redha MCB New Technologies [email protected] Boussebough Imen MCB New Technologies Students concerned Faculty/Institute Département Year Speciality New Technologies ING ING1 ING Course objectives The first objective of this chapter is to provide a comprehensive introduction to the architecture of computers and initiate the student to the coding and representation of numbers. The second objective is to familiarise the student with the notion of binary and machine code. The third objective is to introduce the student to a mathematical support for the mastery of binary (Boolean algebra). 1 Module : MS1 2024-2025 Chapter 1: Part-1 Codification and representation of numbers 2 Module : MS1 2024-2025 1.1. Introduction : Nowadays, information technology is part of every human activity. The computer is the most widely used tool in the world. To understand how a computer works, we first need to understand how it represents and processes information in general. In this chapter we will focus on the codification and representation of numbers. The machine only manipulates two binary values (0 and 1) to represent and process information, and in particular numbers, which is why we will be focusing on binary codification and representation in this chapter. 1.2. Positive integers : The computer calculates in binary, and only the symbols 0 and 1 are used to represent and manipulate numbers. In addition, the size of the numbers manipulated is limited, so storage space is limited in size, which limits the computer's ability to express numbers. 1.2.1. Representation of positive integers in a base B Just as in decimal we use ten digits to represent numbers, in base B (B is an integer and B ≥ 2) we use B digits to represent numbers: Let be a base B whose set of digits is: E={𝑋0 , 𝑋1 , 𝑋3 , … … … … …. 𝑋𝑛−1 } Each number X expressed in base B will be represented by a concatenation of the symbols 𝑋𝑖 in set E. Examples : In base 10: X = 19372 , E={0,1,2,3,4,5,6,7,8,9}; The number X is represented by the digits 1,9,3,7 and 2 in base 10. In base 2: X = 10111, E={0,1}; The number X is represented by the digits 1 and 0. Note: To avoid ambiguity in the representation of numbers, always specify the base used to represent the number, except for base 10. Example : X = 101 in base 2 is different from X = 101 in base 10. Therefore, X = 101 in base 2 will be expressed as X=(101)2 1.2.1.1. Representation of a positive integer in a base Let X be a positive integer and let B be a base (Bϵ N and B ≥ 2). To obtain the representation of X in the base B we apply the principle of Euclidean division : X = q.B + r. Each time, q is divided by B and the rest is noted. 3 Module : MS1 2024-2025 The division is repeated until q is less than B. The rest obtained in the division operation as well as the last value of q are noted from right to left in the expression of the number. Example Let the integer X= 44 be expressed in base 10. To express X in base 3, divide successively by 3 : 44 = 14*3 + 2 14 = 4*3 + 2 4 = 1*3 + 1 The last rest is 1, 1 is less than 3, so we stop the division process. Thus the decimal number 44 expressed in base 10 will be expressed (1122) in base 3. 1.2.1.1. Decimal value of a number expressed in base B The decimal value of a number X expressed in base B is obtained by multiplying each digit of base B, from right to left in the representation of X, by an increasing integer power (starting with zero) of the base. The values obtained in the calculation are added together. Examples 1) Consider the number X expressed in base 7, X = (3425)7 The decimal value of X is: 𝑿 = 𝟓. 𝟕𝟎 + 𝟐. 𝟕𝟏 + 𝟒. 𝟕𝟐 + 𝟑. 𝟕𝟑 , therefore X=1244 in base 10 2) Consider the number X expressed in base 2, X = (1101)2 The decimal value of X is: 𝑿 = 𝟏. 𝟐𝟎 + 𝟎. 𝟐𝟏 + 𝟏. 𝟐𝟐 + 𝟏. 𝟐𝟑 , therefore X=13 in base 10 1.2.2 The classical bases : Whole numbers are generally coded using a number of traditional bases: base 2 (binary), base 8 (octal), base 10 (decimal) and base 16 (hexadecimal). In this section we present the conversion of binary numbers to octal and hexadecimal, as this plays a key role in digital systems. Knowing that each binary symbol requires one bit (0 or 1), a binary number is therefore a collection of bits. Knowing also that the number 8 is a puissance 3 of 2 and that the number 16 is a puissance 4 of 2, each octal digit corresponds to 3 bits and each hexadecimal digit to 4 bits. 1.2.2.1. Binary conversion Octal The conversion from binary to octal is done by grouping 3 bits from right to left in the binary representation of the number, each grouping being replaced by the equivalent digit in octal base. 4 Module : MS1 2024-2025 Binary 000 001 010 011 100 101 110 111 Octal 0 1 2 3 4 5 6 7 Examples : Let the integer X be expressed in binary form X = (1101001)2 X is converted to octal by grouping three bits from right to left, as follows: X = 001 101 001 thus X =(151)8 1 5 1 Note: The missing bits on the left are filled with zeros. 1.2.2.2. Binary hexadecimal conversion The conversion from binary to hexadecimal is done by grouping 4 bits from right to left, each collection being replaced by the equivalent digit in hexadecimal base. Binary 0000 0001 0010 0011 0100 0101 0110 0111 Hexadécimal 0 1 2 3 4 5 6 7 Binary 1000 1001 1010 1011 1100 1101 1110 1111 Hexadécimal 8 9 A B C D E F Note : The base 16 digits are:{0,1,2,3,4,5,6,7,8,9, 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹} Example : Let the integer X be expressed in binary: X=(1101111011)2 X is converted to hexadecimal by grouping four bits from right to left, as follows: X=0011 0111 1011 thus X= (37B) 16 3 7 B The missing bits on the left are filled with zeros. 5 Module : MS1 2024-2025 Note: Direct conversion from a Base B to a Base K is possible if one of the two bases is an integer power of the other (e.g. B=3, K=9) and vice versa. 1.2.3. Arithmetic Classical arithmetic operations for other bases are performed in the same way as in decimal. In the following, we will present binary arithmetic operations as illustrative examples. The details will be explained in the course work. 1.2.3.1. Binary addition : Two binary bits are added according to the following specification: Bit1 Bit2 Carry Sum 0 + 0 = 0 0 0 + 1 = 0 1 1 + 0 = 0 1 1 + 1 = 1 0 The binary addition of two numbers is processed bit by bit from right to left, carrying forward the carry over. Example : Let be the two numbers X = (1101101)2 and Y = (10101011)2 The addition operation is performed in the same way as in base 10 10111101111101 + X+Y = (100011000)2 1 01 0 1 0 11 10 00 1 1 0 00 1.2.3.2. binary subtraction : The subtraction of two binary bits is carried out according to the following specification : Bit1 Bit2 Carry Diff 0 - 0 = 0 0 0 - 1 = 1 1 1 - 0 = 0 1 1 - 1 = 0 0 The binary subtraction of two numbers is carried out bit by bit from right to left, carrying forward the carries 6 Module : MS1 2024-2025 Note: more details will be provided in the coursework. 1.2.3.3. Binary multiplication : The multiplication of two binary bits is realised according to the following specification : Bit1 Bit2 Result 0 X 0 = 0 0 X 1 = 0 1 X 0 = 0 1 X 1 = 1 Example : Let be the two numbers X= (110 10)2 et Y= (1010)2 The X * Y multiplication operation is performed in the same way as in base 10 11010 x 1010 = 00000 + 11010. + 00000.. +11010... = 100000100 Note : The product of two positive numbers is always greater than the multiplied numbers, which poses a problem for the internal representation of numbers (size and capacity) Binary division is a fairly complex operation, generally using the same principle as decimal division (division by subtraction). The development of arithmetic in the different bases will be explained in the supervised work sessions.. 7 Module : MS1 2024-2025 1.3. The negative integers In binary calculation, positive integers are represented only as 0 and 1. The negative sign preceding integer values poses a problem for their machine representation. Several methods are used to represent negative numbers in a computer, including: sign and absolute value representation (SAV), complement to 1 (CP1) and complement to 2 (CP2). 1.3.1. Representation of negative integers in SAV (Sign and absolute value) 1.3.1.1. Principle Integers in SAV are coded in binary by ± absolute value, with the highest bit of the number represented reserved for the sign (1 for the '-' sign and 0 for the '+' sign). An integer coded on n bits will have an absolute value V : 𝟎 ≤ 𝑽 ≤ 𝟐𝒏 − 𝟏 1.3.1.2. Property Given an integer X coded in n-bit SAV, the range of the representation of X is: – (𝟐𝒏−𝟏 − 𝟏) ≤ 𝒏−𝟏 𝑿 ≤ +(𝟐 − 𝟏). Knowing that for n bits we have 2n representations, and from 0 to 2n-1-1 we have 2n-1 numbers. Thus, zero counts 2 times (+0) and (-0). The zero then has two representations: (-(2n-1-1),……-1,-0,+0,1,2,…,(2n-1-1)). Example1 : On 4 bits we will have 16 integers: (-7,-6,-5,-4,-3,-2,-1,-0,+1,+1,+2,+3,+4,+5,+6,+7). Note : for a number encoded on an n-bit word, we will actually have 2n-1 different numbers (zero has two codes) Example2 : The integer X=-20 will be coded in SAV on at least 6 bits as follows: 20 =(10100)2 X will be coded by: 110100. Example3 : The integer number X=+ 20 will be coded in 6 bits SAV as follows: 20 = (10100)2 X will be coded as: 010100. Example4 : The integer number X=-20 will be coded in 8 bits SAV as follows: 20 =(10100)2 X will be coded as: 10010100. Note: In SAV, addition and subtraction operations are complicated because the sign bit has to be handled separately. This method is not used by computer manufacturers for addition and subtraction operations. SAV arithmetic applications will be covered in more detail in the supervised classes. 8 Module : MS1 2024-2025 1.3.2. Representation of negative integers in 1's complement (CP1) 1.3.2.1. Principle: A negative integer is obtained in 1's complement (logical complement) by replacing each 0 bit by 1 and vice versa, in the binary code of the positive number. The highest bit in the number code is reserved for the sign (1 for the '-' sign and 0 for the '+' sign). Example: Consider the integer X = - 5 coded on 4 bits; We have: +5 = (0101)2 in binary (the highest bit is a sign bit, 0 for a positive sign). The CP1 (+5) = - 5, so X = 1010 inCP1. 1.3.2.1. Properties: In 1's complement,CP1(X) is the symmetric of (X). The integers coded on n bits in CP1 will be numbers of 2n-1 positive number and 2n-1 negative number. The range of representation of an integer X coded on n bits is: – (𝟐𝒏−𝟏 − 𝟏) ≤ 𝑿 ≤ +(𝟐𝒏−𝟏 − 𝟏). Knowing that on n bits we have 2n representations, and from 0 to 2n-1-1 we have 2n-1 numbers. So zero counts 2 times (+0) and (-0). Note: CP1 representation is easy to be produced electronically. 1.3.2.1. ARITHMETICS Addition in CP1: Principle : In addition, a carry generated by the sign bit must be added to the result obtained because the complements are added together, including the sign bit (carry). A necessary condition for adding the carry is that a carry must also be generated by the bit just before the sign one. If a carry is generated exclusively by the sign bits or by the bit just before the sign, addition cannot be performed. An overflow error is declared. Example1: Consider the two integers X = 7 and Y = 6, We want to perform the X-Y operation on 4 bits in CP1 )6-( + )7( = 6-7 thus, 7- 6 = 7 + CP1(6). 7= (0111)2 and 6= (0110)2 with CP1(6) = 1001 1 So, 01 11 1 1 + 1 0 0 1 = 10 0 0 0 a carry is generated by the bit and the pre-sign bit +1 = 0 0 0 1 the result is correct 7 – 6 = 1 9 Module : MS1 2024-2025 Example2 : Let be the two integers X= 7 and Y = 6, We want to perform the X+Y operation on 4 bits in CP1 7= (0111)2 et 6= (0110)2 1 So , 0 11 1 1 + 0 110 = 1 1 0 1 Wrong result A carry is generated only by the bit before the sign. The addition is incorrect (7 + 6 = 13, the signed number +13 requires 5 bits for coding. An overflow must be signalled in this case.). Note: In CP1, subtracting a number is reduced to adding its complement to 1 (the subtraction circuit is useless). In addition, CP1 does not handle the sign bit separately. 1.3.2. 2's complement representation (CP2) 1.3.2.1. Principle : The 2's complement (arithmetic complement) of a negative integer is obtained by adding +1 to its CP1 representation. This representation gives an additional configuration because the zero will have a single representation. Example: Let the integer X = - 5 be coded on 4bits; We have : X = 1010 in CP1. The CP2(+5)= CP1(+5) +1, thus X = 1011 in CP2. 1.3.2.2. Properties The range of representation of an integer X coded on n bits in CP2 is : – (𝟐𝒏−𝟏 ) ≤ 𝑿 ≤ +(𝟐𝒏−𝟏 − 𝟏) On n bits we have : X+CP2(X)=2n (hence the name 2's complement) The value of a number represented in CP2 is the same as reading a binary number Xn-1Xn-2…X0 as follows: 𝑿 = 𝟐𝒏−𝟐 𝑿𝒏−𝟐 + ⋯ + 𝟐𝟏 𝑿𝟏 + 𝟐° 𝑿𝟎 − 𝟐𝒏−𝟏 𝑿𝒏−𝟏 Thus, 𝑿 = (∑𝒏−𝟐 𝒊 𝒊=𝟎 𝑿𝒊 𝟐 ) - 𝑿𝒏−𝟏 𝟐 𝒏−𝟏 The CP2 (CP2(X)) = X for any integer value X. 11 Module : MS1 2024-2025 1.3.2.2. ARITHMETICS Addition in CP2 Principle : In CP2 addition, a carry generated by the sign bit will be ignored. A necessary condition for accepting the result thus obtained is that a carry must also be generated by the bit just before sign. If a carry is generated exclusively by the sign bits or by the bit just before the sign, addition cannot be performed. Example1 : Let the two integers X= 7 and Y = 6 We want to perform the operation X-Y on 4 bits in CP2 7- 6 = (7)+(-6) thus, 7- 6 = 7 + CP2(6). 7= (0111)2 et 6= (0110)2 with CP1(6) = 1001 thus, CP2(6) = 1010 1 So, 0 11 1 1 + 1 010 = 10 001 A carry is generated by the sign bit and the bit before the sign one. It will be ignored and the result is correct (7 – 6 = 1). Example2 : Given the two integers X= 7 and Y = 6, We want to perform the operation X+Y on 4 bits in CP2 7= (0111)2 and 6= (0110)2 1 So, 0 11 1 1 + 0 1 1 0 = 1 1 0 1 Incorrect result A carry is generated only by the bit before the sign. The addition is incorrect (7 + 6 = 13, the signed number +13 requires 5 bits for coding and representation. An overflow must be signalled in this case). 11 Module : MS1 2024-2025 Note : Subtracting a number is the same as adding its opposite, i.e. its 2's complement. Multiplying two numbers involves multiplying the absolute values of the 2 numbers and taking the opposite of the result if the numbers have different signs. To divide, go through the division of absolute values and reposition the signs of the quotient and rest if necessary. 1.4. The real numbers Computers only manipulate bits, so we need to define a representation of decimal numbers that is suitable for calculations. In addition, the space available for storing a number on a machine is limited, which limits the precision of calculations. The basic idea for the representation of decimal numbers is to define the location of a comma separating the integer part from the decimal part and to consider that the digits to the right of the comma correspond to the negative powers of the base (as for decimals). 1.4.1. Fixed-point representation of real numbers : The aim of fractional calculation is to achieve maximum precision in writing fractional numbers. The position of the decimal point in the number determines this precision. Unfortunately, in a computer the size of the representation is limited, so managing the position of the decimal point poses a real problem. 1.4.1.1. B base to decimal base conversion In the representation of a number or fixed point, a position is chosen in the digits of the number to separate the fractional part to the right of the chosen position, and the integer part from the chosen position to the left. The fractional part is converted by successive multiplications by negative and decreasing powers of the base B used, starting with (-1).The integer part is obtained using the principle of integers. So, to code a real number in n positions, we can, for example, define a comma after the K least significant digits, For X= (an-K-1…a1a0,a-1 …a1-k a-k)B 𝑛−𝑘−1 The decimal value of X is given by the formula: X = ∑𝑖=−𝑘 𝑎𝑘 2𝑘 Example : Let the real number x be coded in fixed-point binary: X = (1101 , 01)2 The decimal value of x is obtained as follows: X= (1* 2-2 ) + (0* 2-1 ) + (1* 20 ) + (0* 21 ) + (1* 22 ) + (1* 23) Thus, X= 0.25 + 0 + 1 + 4 + 8. Hence X = 13.25. 12 Module : MS1 2024-2025 1.4.1.2. Decimal to base B conversion To transform a fractional decimal number into base B, the integer part is transformed using the same principle as for whole numbers. The fractional part is obtained by successive multiplication of the fractional part by the base B. The integer part resulting from the multiplication is noted in each operation. The multiplication process is repeated until the fractional part disappears or a period of digits appears. Example : X=7,125 we want to express X in binary base: Conversion of the integer part of X to base 2: 7=(111)2 Converting the fractional part of X to base 2: 0,125 x 2 = 0,25 = 0 + 0,25 0.25 x 2 = 0,5 = 0 + 0,5 0,5 x 2 = 1,0 = 1 + 0,0 0,125 =(0,001)2 Thus : 7,125 =(111,001)2 1.4.1.3. Arithmetic Fixed-point arithmetic operations in base B are performed in the same way as in base 10. Note : More details will be given in the supervised classes.. 1.4.2. Floating point representation of real numbers : Since it is difficult to manage the position of the fixed point, floating point representation is generally adopted. 1.4.2.1. Principle : Floating point representation consists of representing real numbers in the following form: X =± M.BE , with: B : Base (2, 8, 10, 16, …) M : Mantissa (a purely fractional number) E : Exponent (an integer number) The mantissa is standardized (it has the maximum number of significant digits), so: (𝟎, 𝟏)𝟐 ≤ |𝑴| < (𝟏)𝟐 thus, (𝟎, 𝟓)𝟏𝟎 ≤ |𝑴| < (𝟏)𝟏𝟎 13 Module : MS1 2024-2025 Exponent and mantissa must be able to represent positive and negative numbers. They could be coded as SAV, CP1 or CP2, often M is coded in SAV form, E is sign less but shifted (Biased). The internal representation of a real number normalized to n bits will have the following form: SM E M Mantissa sign Exponent Mantissa 1.4.2.2.Case study: representation of floating-point real numbers according to the IEEE-754 standard in single precision. In order to standardize the representation of numbers in floating-point format, several standards have been proposed. In the following, we will look at the IEEE-754 standard established by the IEEE (Institute of Electrical and Electronics Engineers) committee, in single precision on 32 bits. Principle: In this standard, a floating-point number X is written in the form 𝑿 = ∓𝟏, 𝑴. 𝟐𝑬 , where : M : represents the pseudo mantises because the integer 1 is not represented. The mantises is coded on 23 bits (corresponding to the negative powers from 2-1 to 2-23). E : is an exponent coded on 8 bits, the exponent is shifted by +127 because it will be represented without a sign on the 8 bits (Ed = E + 127) A sign bit. According to the following diagram: S Ed M Sign Exponent shifted Mantissa One (1) sign bit, 8 bits for the exponent and 23 bits for the pseudo mantissa Description: 1) The highest bit is a sign bit, representing the sign of the mantissa (1 for a negative sign and 0 for a positive sign). 2) The 8-bit exponent is shifted by +127 to represent positive and negative powers. The exponent range is :– (𝟐𝟖−𝟏 ) ≤ 𝑬 ≤ +(𝟐𝟖−𝟏 − 𝟏) with , – 𝟏𝟐𝟕 ≤ 𝑬 ≤ +𝟏𝟐𝟕 The shifted exponent will be represented on 8 unsigned bits and will be in the range: 0 ≤ 𝑬𝒅 ≤ 𝟐𝟓𝟓. The accepted values for Ed are the interval𝟏 ≤ 𝑬𝒅 ≤ 𝟐𝟓𝟒. The values zero and 255 will be reserved for other purposes. 14 Module : MS1 2024-2025 Similarly, the accepted values for E are : −𝟏𝟐𝟔 ≤ 𝑬𝒅 ≤ +𝟏𝟐𝟕. Values -127 and +128 will be reserved for other purposes. The pseudo-mantissa is the fractional part, occupying the lowest 23 bits in the internal representation. Example : Representation of the number X= 25.127 in IEEE-754 floating point in single precision: 1) Set X in the Form 𝑿 = ∓𝟏, 𝑴. 𝟐𝑬 25 = (11001)2 , 0.125 =(0,001)2 25,125 = +1,1001001. 24 2) The pseudo-mantisse : M=(0,1001001)2 3) The biased exponent : Ed = 4+127= 131 ; 131 =(10000011)2 4) le bit de signe = 0 So on 32 bit in IEEE-754 standar, the number X=25,125 will be represented internally by : 0 10000011 10010010000000000000000 S Ed M Note : The internal representation of the real number can be expressed in hexadecimal, octal, etc... In the previous example, if we proceed by grouping 4 bits from right to left, then replace the groupings by their hexadecimal equivalents, we obtain the internal hexadecimal representation of the real number: X= 41C90000 Remark: Floating-point real arithmetic and more detailed applications of the IEEE-754 standard will be covered in supervised classes. The table below summarises the ranges of real number values represented in IEEE-754 single precision standards. 15 Module : MS1 2024-2025 Shifted Signe Exponent Mantisse Value Exponent 0 0 -127 0 Zéro 1 0 -127 0 Zéro Denormalized number 0 0 -127 ≠ 0 𝑿 = +𝟎, 𝑴. 𝟐−𝟏𝟐𝟕 Denormalized number 1 0 -127 ≠ 0 𝑿 = −𝟎, 𝑴. 𝟐−𝟏𝟐𝟕 Normalized number 0 1 ≤ Ed ≤ 254 -126 ≤ Ed ≤ +127 Any 𝑿 = +𝟏, 𝑴. 𝟐−𝑬 Normalized number 1 1 ≤ Ed ≤ 254 -126 ≤ Ed ≤ +127 Any 𝑿 = −𝟏, 𝑴. 𝟐−𝑬 0 255 128 0 +∞ 1 255 128 0 -∞ 0 255 128 ≠ 0 NaN 1 255 128 ≠ 0 NaN 16 Module : MS1 2024-2025 Part-2 α-Numeric coding 17 Module : MS1 2024-2025 1.2 The ASCII code: 2.1.1. The ASCII code (07 bits): The ASCII code is an abbreviation of the American Standard Code for Information Interchange. The code is universally adopted to encode and represent α-digital information. In the ASCII table, the coding is done on 7 bits and the internal representation is done on 8 bits. The 8th bit (the strongest bit) is reserved for the system. The ASCII table is organized into rows and columns where: Each line represents a state of the four lowest bits of the byte, called least significant bits (LSB). Each column represents a state of the three highest bits in the byte, known as the most significant bits (MSBs). Each cell of the table represents an α-numeric character encoded on seven bits. ASCII table -7 bits Note : The number of α-numeric characters encoded in the table is 128 ( 27). 18 Module : MS1 2024-2025 Examples: The ASCII code for the character "A" is: 1000001 or 41 in hexadecimal. The ASCII code for the character "?" is: 0111111 or 3F in hexadecimal. The ASCII code 4E represents the character "N". 2.1.2. The extended ASCII code (08 bits): The ASCII code was originally developed for the English language. Later, computer technology invaded the world, requiring the introduction of coding for several other languages and special characters. The 7-bit ASCII code table proved insufficient to cover the new codes. The ASCII code has been extended to 8 bits in order to be able to code more characters. The ISO/IEC 8859 standard provides extensions for coding by including the 8th strongest bit. The ASCII table is organized into rows and columns where: Each column represents a state of the four lowest bits of the byte, known as the least significant bits (LSB). Each row represents a state of the four highest bits of the byte, called MSBs. Each box in the table represents an α-numeric character encoded on eight bits. The number of α-numeric characters encoded in the table is 256 (28). Below is an example of the ISO-8859-15 ASCII table. 19 Module : MS1 2024-2025 Table ASCII ISO-8859-15. Examples: The ASCII code for the character "A" is: 01000001 or 41 in hexadecimal. The ASCII code for the character "?" is: 00111111 or 3F in hexadecimal. The ASCII code 4E represents the character "N". Notes : The extended ASCII code does not support characters that are not in the Latin alphabet (Chinese or Arabic). Unicode is intended to replace the ASCII code. This standard encodes each character on 16 bits, offering 65536(216) possibilities. This makes it possible to code different languages and many other symbols. 21 Module : MS1 2024-2025 2.2. Gray code (reflected binary) : Gray code, also known as reflected binary code, is obtained by modifying a single bit at a time in the binary code of a number when it is increased by one unit. The following table shows the construction of the Gray code for numbers from 0 to 15: Decimal Binary code Gray code number r 2.2.1. Generalization : X is a positive integer coded in binary on n+1 bits by: X = Bn Bn-1…………..B1B0 and coded in Gray code on n+1 bits by: X = Gn Gn-1…………..G1G0 a- The conversion Binary-Gray : The Gray code is calculated from a pure binary code using the following procedure: Gn= Bn and Gi=Bi+1 ⊕ Bi for i=n-1 to i=0. b- The Conversion Gray-Binary: The binary code is calculated from a Gray code using the following procedure: B n = Gn Bi=Gi ⊕ Gi+1 ⊕……. ⊕Gn for i=n-1 to i=0. 21 Module : MS1 2024-2025 Note : Gray code is used in digital sensors (angular or linear) and in the design of logic circuits, particularly in karnaugh tables, etc... 2.3. The BCD code The BCD code, which stands for Binary Coded Decimal, maps the base 10 digits (0 to 9) to their four- bit binary equivalents, so that each number expressed in base 10 is coded in BCD by replacing each decimal digit with its four-bit binary equivalent. In this way, each number expressed in base 10 is coded in BCD by replacing each decimal digit with its four-bit binary equivalent. Exemple : Let the number X be X = 759, 7 = (0111)2 5 = (0111)2 9 = (0111)2 The BCD code for X is : 011101011001 Note: Details of the exercises relating to this part of the chapter will be given in the tutorial session. 22 Module : MS1 2024-2025 Part-3 Boolean algebra 23 Module : MS1 2024-2025 1.Introduction : In this part of the course we focus on the work of the English mathematician George Boole, published in 1854, relating to binary logic applied to the logic circuits. 1.1 Terminologies and basic operations 1.1.2. Boolean variables : A Boolean variable takes its value from the set {0 , 1}, and is often represented by the symbols of the alphabet (x, y, z, etc...). The values 0 and 1 are logical values: "0" equals the logical value "false" and "1" equals the logical value "true". 1.1.3 Basic operators: The basic logical operators are AND, OR and Negation. The logical operator AND is denoted by (*) or (.) or () : Example: X and y will be noted: x*y or x.y or xy. Principle: The result of the operation of x and y is true if and only if x and y are true. The logical operator or is denoted by (+) : Example: X or y will be noted: x+y. Principle: The result of the operation of x and y is false if and only if x and y are false. The logical negation operator or is denoted ( ) : Example: the negation of X is denoted by X. Principle: The result of the operation of the negation of X is the inverse Boolean value of X. 1.1.4 Boolean expression A Boolean expression is formed from Boolean variables connected by Boolean operators. The Boolean expression returns a Boolean value when evaluated. Example: (X+Y).(X+Z) is a Boolean expression. Evaluating a Boolean expression The evaluation of a Boolean expression respects the order of precedence of Boolean operators.The order of precedence of Boolean operators is defined from the lowest to the highest as follows: OR AND NOT () Lowest Highest 24 Module : MS1 2024-2025 Example : Given the following Boolean expression: (X + Y).( X + Z + Y). The evaluation of this expression for the respective values 0, 0 and 1 of X, Y and Z is as follows: (X + Y). ( X + Z + Y). 1 2 3 4 5 The result of the assessment is: 0 Note: When two operators with the same priority follow each other, priority is given to the operator on the left. 1.1.5 The truth table The truth table is a mathematical tool for representing Boolean expressions, using the different combinations of variables that make up the expression. The truth table is a set of columns, with each variable in the expression occupying a column and the expression itself occupying a column. Each row of the table assigns the value of the Boolean expression to the values entered for its variables. The number of rows in the truth table is equal to 2n, where n represents the number of variables in the table. Example : given the Boolean expression x.y+z, the truth table associated with this expression is given in the figure below: X Y Z X.Y+Z 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Truth table 25 Module : MS1 2024-2025 1.2 Boolean functionsDéfinition : A Boolean function consists of a name for the function, the equality symbol and a Boolean expression formed by the variables in the function. Example : F(X,Y,Z) = X.Y+Z is a function with three variables X, Y and Z. Note : A Boolean function is evaluated in the same way as a Boolean expression. Boolean functions take Boolean values when they are evaluated 1.2.1 Boolean function representations : A Boolean function can be represented by a truth table such as a Boolean expression, or by an algebraic expression in two standard forms. a. Representation of Boolean functions as SOP (Sum of Products) Example : Consider the Boolean function F(X, Y, Z) = X Y + X Y Z. The Boolean function contains two terms (X Y) and (X Y Z), in each term the variables are connected by the operator (AND) (product). The two terms of the function are connected by the (OR) operator (sum). The terms of the function are then sums of products (SOP). b. Representation of Boolean functions as POS (Product of sums) Example: Consider the Boolean function F(X, Y, Z) = (X+ Y). (X +Y+ Z). The Boolean function contains two terms (X+Y) and (X+ Y+ Z), in each term the variables are connected by the operator (OR) (sum). The two terms of the function are connected by the (AND) operator (product). The terms of the function are then product of sums (POS). c. Representation of Boolean functions in canonical form Example: Consider the Boolean function F(X, Y, Z) = XY+ XYZ. The Boolean function contains two terms XY et XYZ. The term XY does not contain the variable Z, it is therefore said to be non-canonical. Definition: a function is said to be in Sop or Pos canonical form if and only if each term of the function contains all the variables of the function. Example : Consider the Boolean function (𝑋, 𝑌) = 𝑋𝑌 + 𝑋𝑌̅ , F is in canonical Sop form. 26 Module : MS1 2024-2025 1.2.2 Procedures for extracting the Sop and Pos forms of a Boolean function using a truth table a- Principle : In a truth table, each line groups together a binary code for the viables of the function represented, as well as the binary code of the function itself. For each value of 1 for the function in a line of the truth table, a term is constructed in conjunction with the function's variables such that each variable appears uncomplemented if its value is 1 and complemented if its value is 0. The term constructed is called the "min-term". The disjunction of the min-terms represent the Sop’s forme of the boolean function. For the 0 value of the function in a line of the truth table, we construct a term by disjunction of the variables of the function such that each variable appears uncomplemented if its value is 0 and complemented if its value is 1. This term is called the "Max-term". The conjunction of the Max-terms represent the Pos’s forme of the boolean function. b- The Sop form procedure. To obtain the canonical Sop form of a Boolean function, we construct a disjunction of all the min-terms of the function extracted from the truth table. Example: Given the Boolean function F defined by the following truth table: X Y Z X.Y+Z 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 The function includes five min-terms. For line 2 of the truth table F(0,0,1)=1 , the associated min-term is: (𝑋̅ 𝑌̅𝑍) F in Sop form: 𝐹(𝑋, 𝑌, 𝑍) = 𝑋̅𝑌̅𝑍 + 𝑋̅𝑌𝑍 + 𝑋𝑌̅𝑍 + 𝑋𝑌𝑍̅ + 𝑋𝑌𝑍 27 Module : MS1 2024-2025 Note : To simplify the use of the Sop canonical form, we use a compact format called Numeric Sop The numeric Sop format is obtained by replacing each min term with the decimal value of the binary code of the variables in the function that generates this min term. ̅𝒀 In the example above, The term: 𝑿 ̅ 𝒁 will be replaced by the value 1 (001 in base 2 = 1 in base10), The term 𝑿𝒀𝒁̅ will be replaced by the value 6 (110 in base 2 = 6 in base10), Thus : 𝑭(𝒙, 𝒚, 𝒛) = ∑𝒎𝒊𝒏(𝟏, 𝟑, 𝟓, 𝟔, 𝟕) c- The Pos form procedure. To obtain the canonical Pos form of a Boolean function, we construct a conjunction of all the min-terms of the function extracted from the truth table. Example : Given the Boolean function F defined by the following truth table: X Y Z X.Y+Z 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 The function includes tree Max–termes. In line 3 of the truth table F(0,1,0)=0, the Max-terme associated is :( X + Y+ Z ) F in Pos form : 𝑭(𝑿, 𝒀, 𝒁) = (𝒙 + 𝒚 + 𝒛)(𝒙 + 𝒚 ̅ + 𝒛)(𝒙 ̅ + 𝒚 + 𝒛) 28 Module : MS1 2024-2025 Note: To simplify the use of the Pos canonical form, we use a compact format called Numeric Pos The numeric Pos format is obtained by replacing each Max-term with the decimal value of the binary code of the variables in the function that generates this Max- term. In the example above, The term, (𝒙̅ + 𝒚 + 𝒛) will be replaced by the value 4 (100 in base 2 = 4 in base10), Thus : 𝑭(𝒙, 𝒚, 𝒛) = ∏𝑴𝒂𝒙(𝟎, 𝟐, 𝟒) 1.2.3 Non-completely defined function : The functions seen above are completely defined functions, i.e. each combination of variables in the function corresponds to a value (0 or 1) for the function. A function is said to be not completely defined if there is at least one combination of variables in the function for which the value of the Boolean function is indeterminate. Example : We want to sort objects by weight P as follows: 𝑥 = 0 𝑖𝑓 𝑃 < 400𝑔 𝑎𝑛𝑑 𝑥 = 1 𝑖𝑓 𝑃 ≥ 400𝑔 𝑦 = 0 𝑖𝑓 𝑃 ≤ 500𝑔 𝑎𝑛𝑑 𝑦 = 1 𝑖𝑓 𝑃 > 500𝑔 The objects that will be accepted must have a weight of 400g ≤ P ≤ 500g. Let F be the function that accepts or rejects the object. X Y F(x,y) 0 0 0 F(x,y) =1 if 400g ≤ P ≤ 500g 0 1 ? F(0,1) is not defined because 𝑃 < 400𝑔 et P≥500g at the same 1 0 1 time. 1 1 0 Note: The undefined value of a Boolean function is represented either by "d" or by "X". 1.2.3 1.3 Boolean algebra: Theorems and postulates Définition : A Boolean algebra is a closed algebraic system containing a set K of two or more elements and two binary operators "+" (or) and "." (and) such that : ∀ 𝑥, 𝑦 𝜖 𝐾, 𝑥 + 𝑦 𝜖 𝐾 𝑒𝑡 𝑥. 𝑦 𝜖 𝐾 In addition, the following postulates must be satisfied: 29 Module : MS1 2024-2025 a- postulates P1 : Existence of 1 and 0 : P4 : Distributivity : 𝑎) 𝑥 + 0 = 𝑥 𝑎) 𝑥 + (𝑦. 𝑧) = (𝑥 + 𝑦). (𝑥 + 𝑧) 𝑏) 𝑥. 1 = 𝑥 𝑏) 𝑥. (𝑦 + 𝑧) = 𝑥. 𝑦 + 𝑥. 𝑧 P2 : Commutativity : P5 : Complementation : 𝑎) 𝑥 + 𝑦 = 𝑦 + 𝑥 𝑎) 𝑥 + 𝑥̅ = 1 𝑏) 𝑥. 𝑦 = 𝑦. 𝑥 𝑏) 𝑥. 𝑥̅ = 0 𝑥̅ is the complement of x. P3 : Associativity: Note: Two expressions are equivalent if one 𝑎) 𝑥 + (𝑦 + 𝑧) = (𝑥 + 𝑦) + 𝑧 can replace the other. 𝑏) 𝑥. (𝑦. 𝑧) = (𝑥. 𝑦). 𝑧 b- Duality : The dual of an expression is obtained by replacing every "+" in the expression with ".", every "." with "+", every 1 with 0 and every 0 with 1. Example: 𝑥 + 𝑦. 𝑧 = (𝑥 + 𝑦). (𝑥 + 𝑧) The Dual is: 𝑥. (𝑦 + 𝑧) = (𝑥. 𝑦) + (𝑥. 𝑧) Note: In the definition of Boolean algebra (postulates), for each postulate P_i (i=1...5), (b) is always the dual of (a). c- Theorems : T1 : Idempotence : T5 : Demorgan Law: 𝑎) 𝑥 + 𝑥 = 𝑥 𝑎) ̅̅̅̅̅̅̅ 𝑥 + 𝑦 = 𝑥̅. 𝑦̅ 𝑏) 𝑥. 𝑥 = 𝑥 𝑏) ̅̅̅̅̅̅ 𝑥. 𝑦 = 𝑥̅ + 𝑦̅ T2 : Property of 1 and 0: T6 : Consensus : 𝑎) 𝑥 + 1 = 1 𝑎) 𝑥 𝑦 + 𝑥̅ 𝑧 + 𝑦 𝑧 = 𝑥 𝑦 + 𝑥̅ 𝑧 𝑏) 𝑥. 0 = 0 𝑏) (𝑥 + 𝑦)(𝑥̅ + 𝑧)(𝑦 + 𝑧) = (𝑥 + 𝑦)(𝑥̅ + 𝑧) T3 : Absorption : 𝑎) 𝑥 + 𝑥 𝑦 = 𝑥 𝑏) 𝑥. (𝑥 + 𝑦) = 𝑥 T4 : Half-absorption: 𝑎) 𝑥 + 𝑥̅ 𝑦 = 𝑥 + 𝑦 𝑏) 𝑥. (𝑥̅ + 𝑦) = 𝑥 𝑦 31  Module : MS1 2024-2025 1.3 Simplification of Boolean functions Why simplification? In classical algebra, simplification means finding a form of writing a function that is dense enough and easily evaluated. Example : 𝑎2 − 𝑏 2 𝐹(𝑎, 𝑏) = → 𝐹(𝑎, 𝑏) = 𝑎 − 𝑏 𝑎 + 𝑏 𝑎+𝑏≠0 In Boolean algebra, simplification also means finding a way of writing a function that is dense enough and requires a reduced number of logical operators (and, or, not, etc.), so that the hardware implementation (circuit) does not require a large number of components. 2.3.2 Algebraic simplification Algebraic simplification of a Boolean function requires the application of theorems from Boolean algebra. Example : 𝐹(𝑎, 𝑏) = 𝑎̅ 𝑏 + 𝑎 𝑏 = (𝑎̅ + 𝑎) 𝑏 (Factorisation) = 1.𝑏 (Complementation) =𝑏 (Existence of 1) 1.3.2 Simplification by Karnaugh's method The Karnaugh method offers a simple procedure for minimising Boolean functions. It is known as the Karnaugh Table or VEITCH diagram. a. Description of the Karnaugh table The table is a diagram of cells. Each cell represents a min term marked with a "1" (the "0s" in the table represent max terms) of the Boolean function. To index the table, each variable fills a set of adjacent cells. A product of two variables results in the intersection of the cells assigned to each variable. The N Karnaugh cells correspond to theExample 1 : Two-variable Karnaugh table © Bahri Mohamed Redha Page 31 sur 34 Module : MS1 2024-2025 Truth table: A B F 0 0 0 0 1 1 1 0 1 1 1 1 𝐹(𝑎, 𝑏) = 𝑎̅𝑏 + 𝑎𝑏̅ + 𝑎𝑏 Karnaugh table : b a 0 (𝑏̅) 1 (𝑏) 0 (𝑎̅) 1 1 (𝑎) 1 1 𝐹(𝑎, 𝑏) = 𝑎̅𝑏 + 𝑎𝑏̅ + 𝑎𝑏 Note : Two cells in the Karnaugh table are said to be adjacent if and only if the two min-terms of the two cells differ by a single variable (as in the gray code). Example 2 : Three-variable Karnaugh table bc 00 01 10 11 bc 00 01 11 10 a a 0 0 1 1 All cells are adjacentc Two non-adjacent cells Note : The Karnaugh table is considered to be a cylinder closed both horizontally and vertically. © Bahri Mohamed Redha Page 32 sur 34 Module : MS1 2024-2025 a. Simplification procedure : Step 1: Using the truth table or directly the expression of the function in Sop form, we place 1's in the cells corresponding to the min-terms of the function. Step 2: Group all the ADJACENT cells containing 1s in the maximum way, i.e. form groupings of ADJACENT cells of maximum size equal to a decreasing power of two.2N , 2N−1 , … , 21 , 20 Step 3: Form a minimum number of groupings of 1 in order to obtain a simplified function with no redundant terms, called the minimum non-redundant base for the Boolean function, where each grouping is called a "prime monomial". Examples: Consider the Boolean function F: 𝐹(𝑎, 𝑏, 𝑐) = 𝑎̅𝑏̅𝑐̅ + 𝑎𝑏̅𝑐 + 𝑎𝑏̅𝑐̅ + 𝑎𝑏𝑐 = ∑𝑚𝑖𝑛(0,4,5,7) bc 𝑏̅ 𝑐̅ 𝑏̅ 𝑐 𝑏𝑐 𝑏𝑐̅ a 00 01 11 10 𝑎̅ 0 1 3 2 0 1 𝑎 4 5 7 6 1 1 1 1 𝐹(𝑎, 𝑏, 𝑐) = 𝑏̅𝑐̅ + 𝑎𝑐 (Minimum complete non-redundant base for F) cd 00 01 11 10 ab 00 0 1 3 2 1 1 4 5 7 6 01 1 1 1 1 12 13 15 14 11 1 1 1 1 8 9 11 10 10 1 𝐹(𝑎, 𝑏, 𝑐, 𝑑) = 𝑏 + 𝑎̅𝑑̅ + 𝑎𝑐̅𝑑 (Minimum non-redundant complete base for F) Note : The Karnaugh table is useful for simplifying Boolean functions where the number of logical variables is ≤ 6. © Bahri Mohamed Redha Page 33 sur 34 Module : MS1 2024-2025 Conclusion Boolean simplification methods are used to rewrite functions in a more compact format with the aim of creating the associated combinatorial circuits at lower cost. This chapter presents two simplification methods (algebraic simplification and the Karnaugh method). © Bahri Mohamed Redha Page 34 sur 34