Chapter_1_Digital_Systems_and_Binary_Numbers _Final.pdf

Subject Name Computer Organization and Architecture Subject Code: BTCO13302 Course Outcomes CO-1 Understand the structure of various number systems and their application in digital system design CO-2 Design and analyze combinational and sequential logic circui...

Subject Name Computer Organization and Architecture Subject Code: BTCO13302 Course Outcomes CO-1 Understand the structure of various number systems and their application in digital system design CO-2 Design and analyze combinational and sequential logic circuits CO-3 Identify and explain various instructions and their corresponding microoperations. CO-4 Design processing unit using the concepts of ALU and control logic CO-5 Solve various arithmetic algorithms for several data representations CO-6 Describe fundamentals concepts of pipeline and memory mapping techniques Digital Systems and Binary Numbers  Outline  1.1 Digital Systems  1.2 Binary Numbers  1.3 Number-base Conversions  1.4 Octal and Hexadecimal Numbers  1.5 Complements  1.6 Signed Binary Numbers  1.7 Binary Codes  Digital Systems and Binary Numbers  Digital age and information age  Digital computers ◆ General purposes ◆ Many scientific, industrial and commercial applications  Digital systems ◆ Telephone switching exchanges ◆ Digital camera ◆ Electronic calculators, PDA's ◆ Digital TV  Discrete information-processing systems ◆ Manipulate discrete elements of information ◆ For example, {1, 2, 3, …} and {A, B, C, …}…  Binary Digital Signal  An information variable represented by physical quantity.  For digital systems, the variable takes on discrete values. ◆ Two level, or binary values are the most prevalent values.  Binary values are represented abstractly by: ◆ Digits 0 and 1 ◆ Words (symbols) False (F) and True (T) V(t) ◆ Words (symbols) Low (L) and High (H) ◆ And words On and Off Logic 1  Binary values are represented by values or ranges of values of physical quantities. undefine Logic 0 t Binary digital signal  Decimal Number System  Base (also called radix) = 10 ◆ 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }  Digit Position ◆ Integer & fraction 2 1 0 -1 -2  Digit Weight 5 1 2 7 4 ◆ Weight = (Base) Position  Magnitude 100 10 1 0.1 0.01 ◆ Sum of “Digit x Weight”  Formal Notation 500 10 2 0.7 0.04 d2*B2+d1*B1+d0*B0+d-1*B-1+d-2*B-2 (512.74)10  Octal Number System  Base = 8 ◆ 8 digits { 0, 1, 2, 3, 4, 5, 6, 7 }  Weights ◆ Weight = (Base) Position 64 8 1 1/8 1/64  Magnitude 5 1 2 7 4 ◆ Sum of “Digit x Weight” 2 1 0 -1 -2  Formal Notation 2 1 0 -1 - 5 2 *8 +1 *8 +2 *8 +7 *8 +4 *8 =(330.9375)10 (512.74)8  Binary Number System  Base = 2 ◆ 2 digits { 0, 1 }, called binary digits or “bits”  Weights ◆ Weight = (Base) Position 4 2 1 1/2 1/4  Magnitude 1 0 1 0 1 ◆ Sum of “Bit x Weight” 2 1 0 -1 -2  Formal Notation 1 *2 2 +0 *2 1 +1 *2 0 +0 *2 -1 +1 *2 - 2  Groups of bits 4 bits = Nibble 8 bits = Byte =(5.25)10 (101.01)2 1011 11000101  Hexadecimal Number System  Base = 16 ◆ 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }  Weights ◆ Weight = (Base) Position 256 16 1 1/16 1/256  Magnitude 1 E 5 7 A ◆ Sum of “Digit x Weight” 2 1 0 -1 -2  Formal Notation 1 *162+14 *161+5 *160+7 *16-1+10 *16-2 =(485.4765625)10 (1E5.7A)16  The Power of 2 n 2n n 2n 0 20=1 8 28=256 1 21=2 9 29=512 2 22=4 10 210=1024 Kilo 3 23=8 11 211=2048 4 24=16 12 212=4096 5 25=32 20 220=1M Mega 6 26=64 30 230=1G Giga 7 27=128 40 240=1T Tera  Binary Multiplication  Bit by bit 1 0 1 1 1 x 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 Number Base Conversions Evaluate Magnitude Octal (Base 8) Evaluate Magnitude Decimal Binary (Base 10) (Base 2) Hexadecimal (Base 16) Evaluate Magnitude  Decimal (Integer) to Binary Conversion  Divide the number by the ‘Base’ (=2)  Take the remainder (either 0 or 1) as a coefficient  Take the quotient and repeat the division Example: (13)10 Quotient Remainder Coefficient 13/ 2 = 6 1 a0 = 1 6 /2= 3 0 a1 = 0 3 /2= 1 1 a2 = 1 1 /2= 0 1 a3 = 1 Answer: (13)10 = (a3 a2 a1 a0)2 = (1101)2 MSB LSB  Decimal (Fraction) to Binary Conversion  Multiply the number by the ‘Base’ (=2)  Take the integer (either 0 or 1) as a coefficient  Take the resultant fraction and repeat the multipication Example: (0.625)10 Integer Fraction Coefficient 0.625 * 2 = 1. 25 a-1 = 1 0.25 * 2 = 0. 5 a-2 = 0 0.5 *2= 1. 0 a-3 = 1 Answer: (0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2 MSB LSB  Decimal to Octal Conversion Example: (175)10 Quotient Remainder Coefficient 175 / 8 = 21 7 a0 = 7 21 / 8 = 2 5 a1 = 5 2 /8= 0 2 a2 = 2 Answer: (175)10 = (a2 a1 a0)8 = (257)8 Example: (0.3125)10 Integer Fraction Coefficient 0.3125 * 8 = 2. 5 a-1 = 2 0.5 *8= 4. 0 a-2 = 4 Answer: (0.3125)10 = (0.a-1 a-2 a-3)8 = (0.24)8  Binary to Decimal Decimal Octal Binary Hexadecimal  Binary to Decimal Technique Multiply each bit by 2n, where n is the “weight” of the bit The weight is the position of the bit, starting from 0 on the right Add the results  Example Bit “0” 1010112 => 1 x 20 = 1 1 x 21 = 2 0 x 22 = 0 1 x 23 = 8 0 x 24 = 0 1 x 25 = 32 4310  Fractions Binary to decimal 10.1011 => 1 x 2-4 = 0.0625 1 x 2-3 = 0.125 0 x 2-2 = 0.0 1 x 2-1 = 0.5 0 x 20 = 0.0 1 x 21 = 2.0 2.6875  Fractions Decimal to binary E.g (13.0625)10 (1.0252)10  Fractions Accuracy of binary conversion of Non- integer E.g (0.252)10 With error less than 1% Eallow =% error * Number 0.01 *0.252= 0.00252 2-n < 0.00252 n=? Invert both side 2n > 397 N= log 397/ log2 = 8.63 == 9  Fractions Decimal to binary 1) (0.84) 2) (33.45)10 3) (11.378154)10 result should be accurate within 1% ,2% and 10% respectively  Octal to Decimal Decimal Octal Binary Hexadecimal  Octal to Decimal Technique n Multiply each bit by 8 , where n is the “weight” of the bit The weight is the position of the bit, starting from 0 on the right Add the results 7248 => 4 x 80 = 4+ 2 x 81 = 16+ 7 x 82 = 448+ 46810  Octal to Decimal Technique n Multiply each bit by 8 , where n is the “weight” of the bit The weight is the position of the bit, starting from 0 on the right Add the results Example: (572.7)8 572.7 => 5 x 82 = 7 x 81 = 2 x 80 = 7 x 8-1 = Hexadecimal to Decimal Decimal Octal Binary Hexadecimal  Hexadecimal to Decimal Technique Multiply each bit by 16n, where n is the “weight” of the bit The weight is the position of the bit, starting from 0 on the right Add the results ABC16 => C x 160 = 12 x 1 = 12 B x 161 = 11 x 16 = 176 A x 162 = 10 x 256 = 2560 274810  Hexadecimal to Decimal Technique Multiply each bit by 16n, where n is the “weight” of the bit The weight is the position of the bit, starting from 0 on the right Add the results (1E5.7A)16 256 16 1 1/16 1/256 1 E 5 7 A 2 1 0 -1 -2 1 *162+14 *161+5 *160+7 *16-1+10 *16-2 =(485.4765625)10  Binary − Octal Conversion Octal Binary 8= 23 0 000  Each group of 3 bits represents an octal digit 1 001 2 010 Assume Zeros Example: 3 011 ( 1 0 1 1 0. 0 1 )2 4 100 5 101 6 110 ( 2 6. 2 )8 7 111 Works both ways (Binary to Octal & Octal to Binary)  Binary − Hexadecimal Conversion Hex Binary  16 = 24 0 0000 1 0001  Each group of 4 bits represents a 2 0010 hexadecimal digit 3 0011 4 0100 5 0101 Assume Zeros 6 0110 Example: 7 0111 8 1000 ( 1 0 1 1 0. 0 1 )2 9 1001 A 1010 B 1011 C 1100 D 1101 (1 6. 4 )16 E 1110 F 1111 Works both ways (Binary to Hex & Hex to Binary)  Octal − Hexadecimal Conversion  Convert to Binary as an intermediate step Example: ( 2 6. 2 )8 Assume Zeros Assume Zeros ( 0 1 0 1 1 0. 0 1 0 )2 (1 6. 4 )16 Works both ways (Octal to Hex & Hex to Octal)  Octal to Binary Decimal Octal Binary Hexadecimal  Example Technique Convert each octal digit to a 3-bit equivalent binary representation 7058 = ?2 7 0 5 111 000 101 7058 = 1110001012  Octal to Hexadecimal Decimal Octal Binary Hexadecimal  Example Technique Use binary as an intermediary 1 0 7 6 10768 = ?16 001 000 111 110 2 3 E 10768 = 23E16  Hexadecimal to Octal Decimal Octal Binary Hexadecimal  Example Technique Use binary as an intermediary 1 F 0 C 1F0C16 = ?8 0001 1111 0000 1100 1 7 4 1 4 1F0C16 = 174148  Exercise – Convert... Hexa- Decimal Binary Octal decimal 29.8 101.1101 3.07 C.82 Don’t use a calculator! Answer Skip answer Answer  Exercise – Convert … Answer Hexa- Decimal Binary Octal decimal 29.8 11101.110011… 35.63… 1D.CC… 5.8125 101.1101 5.64 5.D 3.109375 11.000111 3.07 3.1C 12.5078125 1100.10000010 14.404 C.82 Decimal, Binary, Octal and Hexadecimal Decimal Binary Octal Hex 00 0000 00 0 01 0001 01 1 02 0010 02 2 03 0011 03 3 04 0100 04 4 05 0101 05 5 06 0110 06 6 07 0111 07 7 08 1000 10 8 09 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F  Addition  Decimal Addition 1 1 Carry 5 5 + 5 5 1 1 0 = Ten ≥ Base ➔ Subtract a Base  Binary Addition  Column Addition 1 1 1 1 1 1 1 1 1 1 0 1 = 61 + 1 0 1 1 1 = 23 1 0 1 0 1 0 0 = 84 ≥ (2)10  Binary Subtraction  Borrow a “Base” when needed 1 2 = (10)2 0 2 2 0 0 2 1 0 0 1 1 0 1 = 77 − 1 0 1 1 1 = 23 0 1 1 0 1 1 0 = 54  1.5 Signed Binary Numbers  To represent negative integers, we need a notation for negative values.  It is customary to represent the sign with a bit placed in the leftmost position of the number since binary digits.  The convention is to make the sign bit 0 for positive and 1 for negative.  Example:  Table 1.3 lists all possible four-bit signed binary numbers in the three representations.  Complements  There are two types of complements for each base-r system: the radix complement and diminished radix complement.  Diminished Radix Complement - (r-1)’s Complement ◆ Given a number N in base r having n digits, the (r–1)’s complement of N is defined as: (rn –1) – N  Example for 6-digit decimal numbers: ◆ 9’s complement is (rn – 1)–N = (106–1)–N = 999999–N ◆ 9’s complement of 546700 is 999999–546700 = 453299  Example for 7-digit binary numbers: ◆ 1’s complement is (rn – 1) – N = (27–1)–N = 1111111–N ◆ 1’s complement of 1011000 is 1111111–1011000 = 0100111  Observation: ◆ Subtraction from (rn – 1) will never require a borrow ◆ Diminished radix complement can be computed digit-by-digit ◆ For binary: 1 – 0 = 1 and 1 – 1 = 0  Complements  Radix Complement The r's complement of an n-digit number N in base r is defined as rn – N for N ≠ 0 and as 0 for N = 0. Comparing with the (r − 1) 's complement, we note that the r's complement is obtained by adding 1 to the (r − 1) 's complement, since rn – N = [(rn − 1) – N] + 1.  Example: Base-10 The 9's complement of 12398 is (99999-12398)= 87061 The 10's complement of 12398 is (9's complement +1)= 87061+1= 87062  Example: Base-2 The 1's complement of 1101100 is 0010100 (Inverter) The 2's complement of 1101100 is 0010101 (1's complement +1)  Complements  Radix Complement The r's complement of an n-digit number N in base r is defined as rn – N for N ≠ 0 and as 0 for N = 0. Comparing with the (r − 1) 's complement, we note that the r's complement is obtained by adding 1 to the (r − 1) 's complement, since rn – N = [(rn − 1) – N] + 1.  Example: Base-8 The 7's complement of 1234 is (7777-1234)= 6543 The 8's complement of 1234 is (7's complement +1) =6543+1=6544  Complements  1’s Complement (Diminished Radix Complement) ◆ All ‘0’s become ‘1’s ◆ All ‘1’s become ‘0’s Example (10110000)2  (01001111)2 If you add a number and its 1’s complement … 10110000 + 01001111 11111111  Complements  2’s Complement (Radix Complement) ◆ Take 1’s complement then add 1 OR ◆ Toggle all bits to the left of the first ‘1’ from the right Example: Number: 1’s Comp.: 10110000 10110000 01001111 + 1 01010000 01010000  Complements  2’s Complement (Radix Complement)  Complements  2’s Complement (Radix Complement)  Complements  2’s Complement (Radix Complement) Signed Binary Numbers  Complements  2’s Complement (Radix Complement)  Complements  Subtraction with Complements ◆ The subtraction of two n-digit unsigned numbers M – N in base r can be done as follows:  Complements  Example 1.5 ◆ Using 10's complement, subtract 72532 – 3250.  Example 1.6 ◆ Using 10's complement, subtract 3250 – 72532. There is no end carry. Therefore, the answer is – (10's complement of 30718) = − 69282.  Signed Binary Numbers  Arithmetic addition ◆ The addition of two numbers in the signed-magnitude system follows the rules of ordinary arithmetic. If the signs are the same, we add the two magnitudes and give the sum the common sign. If the signs are different, we subtract the smaller magnitude from the larger and give the difference the sign if the larger magnitude. ◆ The addition of two signed binary numbers with negative numbers represented in signed-2's-complement form is obtained from the addition of the two numbers, including their sign bits. ◆ A carry out of the sign-bit position is discarded.  Example:  Signed Binary Numbers  Arithmetic Subtraction ◆ In 2’s-complement form: 1. Take the 2’s complement of the subtrahend (including the sign bit) and add it to the minuend (including sign bit). 2. A carry out of sign-bit position is discarded. 3. Check MSB bit if 0 result is +ve and it is in true binary ,if 1 result is in –ve and it is in complement form (  A) − ( + B) = (  A) + ( − B)  Example: (  A) − ( − B) = (  A) + ( + B) (− 6) − (− 13) (11111010 − 11110011) (11111010 + 00001101) 00000111 (+ 7)  62 7/29/2024 2’s Complements Arithmetic 🞇 Subtractions Process: 🞇 Add 2’s Complement of the subtrahend to the minuend 🞇 If there is carry out ignore it 🞇 If MSB is 0, result is +ve 🞇 If MSB is 1, result is –ve so take 2’s complement of the result to generate the final answer and apply the (-)sign (Whether there is a carry out or not) Code Conversion  63 7/29/2024 Example: Subtract 46 – 14 using 2’s complement using 8-bit + 14 → 0 0 0 0 1 1 1 0 - 14 → 1 1 1 1 0 0 1 0 (2’s Complement Form) 46 00101110 - 14 +11110010 --------------------- 100100000 Code Conversion  1’s Complements Arithmetic 🞇 Subtractions Process: 🞇 Add 1’s Complement of the subtrahend to the minuend 🞇 If there is carry out add it to the LSB 🞇 If MSB is 0, result is +ve 🞇 If MSB is 1, result is –ve so take 1’s complement of the result to generate the final answer  65 7/29/2024 Example 25 → 00011001 - 14 + 1 1 1 1 0 0 0 1 (1’s complement Form) --------- ---------------------- 100001010 + 1 ------------------------ 00001010 Code Conversion  66 7/29/2024 Example 14 → 0 0 0 0 1 1 1 0 (1’s complement Form) - 25 + 1 1 1 0 0 1 1 0 (1’s complement Form) --------- ---------------------- 11110100 🞇 There is no carry. MSB is 1. 🞇 Result is complemented binary. 🞇 00000111 Code Conversion  67 7/29/2024 Assignment : 1. Perform 1’s Complement arithmetic on following numbers 14 68.75 - 25 - 27. 50 ----- --------- -11 + 41.25 🞇 Answer 1 : 1 1 1 1 0 1 0 0 (00001011) (- 11) 🞇 Answer 2 : 0 0 1 0 1 0 0 1.0 1 0 0 (+41.25) Code Conversion  68 7/29/2024 Cont… 1. Perform 2’s Complement arithmetic on following numbers 26 27.125 - 75 - 79. 625 ----- --------- - 49 - 52.500 🞇 Answer 1 : 1 1 0 0 1 1 1 1 (00110001) (-49) 🞇 Answer 2 : 1 1 0 0 1 0 1 1.1 0 0 0 (00110100.1000) (-52.500) Code Conversion Code Conversion 7/29/2024 69 Overflow / Underflow Problem 🞇 Addition and bit-size restriction allow for possible overflow / underflow 🞇 Overflow – when the addition of two binary numbers yields a result that is greater than the maximum possible value 🞇 Underflow – when the addition/subtraction of two binary numbers yields a result that is less than the minimum possible value Code Conversion 7/29/2024 70 Overflow / Underflow Problem 🞇 If 2 Two's Complement numbers are added and they both have the same sign, either positive or negative, then an overflow occurs if and only if the result (MSB) has the opposite sign. Code Conversion 7/29/2024 71 Overflow Example 🞇 Assume 4-bit restriction and 2’s complement 🞇 Maximum possible value: 24-1 – 1 = 7 610 + 310 = 910 01102 610 +00112 +310 10012 -710 not good! Code Conversion 7/29/2024 72 Underflow Example 🞇 Assume 4-bit restriction and 2’s complement 🞇 Minimum possible value: -(24-1) = -8 -510 + -510 = -1010 10112 -510 +10112 +-510 01102 610 not good!  Complements  Example ◆ Given the two unsigned binary numbers X = 1010100 and Y = 1000011, perform the subtraction (a) X – Y ; and (b) Y − X, by using 2's complement. There is no end carry. Therefore, the answer is Y – X = − (2's complement of 1101111) = − 0010001.  Complements  Subtraction of unsigned numbers can also be done by means of the (r − 1)'s complement. Remember that the (r − 1) 's complement is one less then the r's complement.  Example 1.8 ◆ Repeat Example 1.7, but this time using 1's complement. There is no end carry, Therefore, the answer is Y – X = − (1's complement of 1101110) = − 0010001.  Codes Codes Alphanumeric Numeric ASCII , EBCDIC Self – Non- Error detecting and Weighted complemen Sequential Reflective Cyclic weighted correcting ting Gray, 8421, Gray Xs-3 Xs-3 Binary, 2421, Gray BCD, 84-2-1 Xs-3  Binary Codes  Weighted Code ◆ If each position of a number represents a specific c weight then the coding scheme is called weighted binary code. ◆ In such coding the bits are multiplied by their corresponding individual weight, and then the sum of these weighted bits gives the equivalent decimal digit. ◆ E.g. BCD ,84-2-1 64 8 1 1/8 1/64 5 1 2 7 4 2 1 0 -1 -2  Binary Codes  BCD Code ◆ A number with k decimal digits will require 4k bits in BCD. ◆ Decimal 396 is represented in BCD with 12bits as 0011 1001 0110, with each group of 4 bits representing one decimal digit. ◆ A decimal number in BCD is the same as its equivalent binary number only when the number is between 0 and 9. ◆ The binary combinations 1010 through 1111 are not used and have no meaning in BCD.  Complements  Radix Complement The r's complement of an n-digit number N in base r is defined as (r − 1) 's complement : rn – N for N ≠ 0 and as 0 for N = 0. r's complement : obtained by adding 1 to the (r − 1) 's complement, since r n – N = [(rn − 1) – N] + 1.  Example: Base-10 The 9's complement of 12398 is (99999-12398)= 87061 The 10's complement of 12398 is (9's complement +1)= 87061+1= 87062  Binary Codes  84-2-1 Code ◆ It is also possible to assign negative weights to decimal code, as shown by the 84-2-1 code. ◆ In this case the bit combination 0101 is interpreted as the decimal digit 3, ◆ As obtained from 0 × 8 + 1 × 4 + 0 × (–2) + 1 × (–1) = 3. ◆ It is a self-complementary code: ◆ that is, the 9’s complement of the decimal number is obtained just by changing the 1s to 0s and 0s to 1s, or in effect by getting the 1’s complement of the corresponding number. ◆ For example, if we change the 1s to 0s and 0s to 1s in the previous example we have 1010 which is interpreted as decimal 6, as obtained from 1 × 8 + 0 × 4 + 1 × (–2) + 0 × (–1) = 6. ◆ 6 is the 9’s complement of 3. This property is useful when arithmetic operations are done internally with decimal numbers (in a binary code) and subtraction is calculated by means of 9’s complement.  Binary Codes  Non-Weighted Code ◆ These codes are not positional weighted. ◆ Each position of the binary number is not assigned a fixed value. ◆ E.g. : Excess-3(Xs-3) ,Gray  Binary Codes  Xs-3 Code ◆ It self complementing code ◆ obtained by adding 3 to each decimal digit then it can be represented by using 4 bit binary number for each digit. ◆ the maximum value may be (1100)2. Since the maximum decimal digit is 9 we have to add 3 to 9 and then get the BCD equivalent ◆ The binary combinations 1101 through 1111 are not used and have no meaning in Xs-3  Binary Codes Example-1 −Convert decimal number 23 to Excess-3 code. So, according to excess-3 code we need to add 3 to both digit in the decimal number then convert into 4-bit binary number for result of each digit. Therefore, = 23+33=56 =0101 0110 which is required excess-3 code for given decimal number 23.  Binary Codes  Other Decimal Codes  Gray Code ◆ It is non- weighted code , Cyclic code , Reflected code ◆ This code belongs to a class of code known as minimum change code, in which a number changes by only one bit as it proceeds from one number to the next. ◆ This code is not useful for arithmetic operations. ◆ Application » shaft encoders » Error detection. » Representation of analog data. » Low power design.  Binary Codes)  Gray Code ◆ Cyclic code : each successive code word differs from the preceding one in only one bit position, also called unit distance code ◆ It Reflected code 000 001 010 011 100 101 110 111 1-1 and onto!!  BCD addition  BCD addition Step 1: Convert decimal number into BCD (8421) code. Add the two BCD numbers using the rules for binary addition. Step 2: If a 4-bit sum is equal to or less than 9, it is a valid BCD number. Step 3: If a 4-bit sum is greater than 9 or if a carry-out of the 4-bit group is generated, it is an invalid result. Add 6 (0110) to the 4-bit sum in order to skip the six invalid BCD code words and return the code to 8421. If a carry results when 6 is added, simply add the carry to the next 4-bit group.  BCD addition  BCD addition 1) 25+13 2) 679.6+536.8  BCD addition  BCD addition  BCD Subtraction  BCD Subtraction  Xs-3 addition Step 1: Convert decimal number into Excess-3 code. Step 2: Add the two Xs-3 numbers using the rules for binary addition. Step 3: in a 4-bit group sum If carry generated then add 3 otherwise subtract 3  Xs-3 addition  Example:  1) 37+ 28  2) 247.6 +359.4  Xs-3 addition  Example:  Xs-3 Subtraction Step 1: Convert decimal number into Excess-3 code. Step 2: Add the two Xs-3 numbers using the rules for binary addition. Step 3: in a 4-bit group sum If no borrow then add 3 otherwise subtract 3  Xs-3 Subtraction  Example:  Xs-3 Subtraction  Example: Perform Xs-3 Subtraction 246-592 Using 9‘s Complement  Boolean Algebra Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. It is also called as Binary Algebra or logical Algebra. Boolean algebra was invented by George Boole in 1854.  Boolean Algebra Commutative law Any binary operation which satisfies the following expression is referred to as commutative operation. Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit. Associative law This law states that the order in which the logic operations are performed is irrelevant as their effect is the same. Distributive law Distributive law states the following condition. AND law These laws use the AND operation. Therefore they are called as AND laws. OR law These laws use the OR operation. Therefore they are called as OR laws.  Boolean Algebra INVERSION law This law uses the NOT operation. The inversion law states that double inversion of a variable results in the original variable itself. Idempotent :An input that is AND‘ed or OR ´ed with itself is equal to that input i) A + A = A ii) A. A = A Negation Law : i) A + A = 1 ii) A. A = 0 De Morgan’s Theorem – There are two “de Morgan’s” rules or theorems,  Boolean Algebra Laws of Boolean Algebra Example No1 Using the above laws, simplify the following expression: (A + B)(A + C)  Boolean Algebra Laws of Boolean Algebra Example No1 Using the above laws, simplify the following expression: (A + B)(A + C) Q= (A + B).(A + C) A.A + A.C + A.B + B.C – Distributive law A + A.C + A.B + B.C – Idempotent AND law (A.A = A) A(1 + C) + A.B + B.C – Distributive law A.1 + A.B + B.C – Identity OR law (1 + C = 1) A(1 + B) + B.C – Distributive law A.1 + B.C – Identity OR law (1 + B = 1) Q= A + (B.C) – Identity AND law (A.1 = A)  Boolean Algebra More Examples: Show that; (a) ab + ab'c = ab + ac (b) (a + b)(a + b' + c) = a + bc  Boolean Algebra More Examples: Show that; (a) ab + ab'c = ab + ac (b) (a + b)(a + b' + c) = a + bc (a) ab + ab'c = a(b + b'c) = a((b+b').(b+c))=a(b+c)=ab+ac (b) (a + b)(a + b' + c) = (a.a + a.b' + a.c + ab +b.b' +bc) =…  Boolean Algebra More Examples: Show that: (a(b + z(x + a')))' =a' + b' (z' + x') (a(b + z(x + a')))' = a' + (b + z(x + a'))' = a' + b' (z(x + a'))' = a' + b' (z' + (x + a')') = a' + b' (z' + x'(a')') = a' + b' (z' + x'a) =a‘+b' z' + b'x'a =(a‘+ b'x'a) + b' z' =(a‘+ b'x‘)(a +a‘) + b' z' = a‘+ b'x‘+ b' z‘ = a' + b' (z' + x')  Boolean Algebra More Examples: A + B [AC + (B+C’) D ] =A+BD  Boolean Algebra More Examples: (A + (BC) ’ ) ’ (Ab’ +ABC ) =0  Boolean Algebra More Examples: Show that AB’C +B +BD’ +ABD’_A’C=B +C  Boolean Algebra Absorption Law Absorption law involves in linking of a pair of binary operations. i) A+AB = A ii) A(A+B) = A iii) A+ĀB = A+B iv) A.(Ā+B) = AB 3rd and 4th laws are also called as Redundancy laws. A + ĀB = (A + Ā) (A + B ) → since A+BC = (A+B)(A+C) using distributive law = 1 * (A + B) → since A + Ā = 1 =A + B A. (Ā+B) = AB = A. Ā + AB = AB → since A Ā = 0  Boolean Algebra Consensus Theorem. We can also prove it like this:  Boolean Algebra Consensus Theorem. Example-1. F = AB + BC' + AC F = BC' + AC Example-2. F = (A + B).(A' + C).(B + C).'. F = (A + B).(A' + C)  Boolean Algebra Transposition Theorem.  Boolean Algebra Example : Find the complement of (a) A B + C D , (b) AB +CD = 0 Solution:  Boolean Algebra Example : Find the complement of (a) A B + C D , (b) AB +CD = 0 Solution:  Boolean Algebra Example : Simplify: (A + C)(AD + AD) + AC + C: Simplify: A(A + B) + (B + AA)(A + B):  Boolean Algebra Example : Simplify: (A + C)(AD + AD) + AC + C: Simplify: A(A + B) + (B + AA)(A + B):  Boolean Algebra Example : Minimize the following expression by use of Boolean rules. Boolean Function and their Representation Sum of Product (Mintern)/Disjunctive Normal Form (DNF): The Sum of Product means that the products of the variables that are separated by a plus sign. The variables can be complemented or uncomplemented, For-example, F(A,B,C) = AB + AB’ + A’ B +A’B’ + AB’C + A’B C + A’B C Product of sum (Maxterm)/Conjunctive Normal Form (CNF): The Product of Sum means that the sum of variables that are separated by a multiplication sign. For example, F(A,B,C) = (A + B) (A’ + B) (A +B’ ) (A’ +B’ ), F(A,B,C) = (A + B’ + C)(A +B’ + C’ )(A’ +B’ + C) Boolean Function and their Representation Canonical Form / Standard Standard SOP A function is given as; f(A, B, C)=∑m(3,5,6,7) Y=m3+m5+m6+m7 Y=A’BC+AB’C+ABC’+ABC Standard POS If a function is given as; f(A, B, C)=ΠM(0,1,2,4) Y=M0. M1. M2. M4 Y=(A+B+C)(A+B+C’)(A+B’+C)(A’+B+C) Boolean Function and their Representation Boolean Function and their Representation Find the sum-of-products and product of sums equations from the given truth Boolean Function and their Representation Expansion of a Boolean Expression in SOP to Standard SOP Boolean Function and their Representation Expansion of a Boolean Expression in SOP to Standard SOP Example: Expand A’ +B’ Boolean Function and their Representation Expansion of a Boolean Expression in SOP to Standard SOP Example: Expand A’ +B’ Boolean Function and their Representation Expansion of a Boolean Expression in SOP to Standard SOP Example: Express the Boolean function F = x + y z as a minterms and maxterm Boolean Function and their Representation Expansion of a Boolean Expression in SOP to Standard SOP Boolean Function and their Representation Expansion of a Boolean Expression in POS to Standard POS Boolean Function and their Representation Expansion of a Boolean Expression in POS to Standard POS Boolean Function and their Representation K-Map A K- map provides a systematic method for simplifying Boolean expressions The K-map is an array of cells in which each cell represents a binary value of the input variables. The cells are arranged in a way so that simplification of a given expression is simply a matter of properly grouping the cells. The K-maps can be used for expressions with two, three,four, and five variables The number of cells in a K-map, as well as the number of rows in a truth table. Boolean Function and their Representation K-Map Steps to solve expression using the K-map Select K-map according to the number of variables. Identify minterms or maxterms as given in the problem. For SOP put 1’ s in blocks of K -map respective to the minterms (0’ s elsewhere). For POS put 0’s in blocks of K -map respective to the maxterms(1’ s elsewhere). Make rectangular groups containing total terms in power of two like 2, 4,8..(except 1) and try to cover as many elements as you can in one group. From the groups made in step 5 find the product terms and sum them up for SOP form. Boolean Function and their Representation K-Map Grouping Rules by grouping together adjacent cells containing ones 1. No zeros allowed. 2. No diagonals. 3. Only power of 2 number of cells in each group. 4. Groups should be as large as possible. 5. Everyone must be in at least one group. 6. Overlapping allowed. Boolean Function and their Representation K-Map Boolean Function and their Representation K-Map Example1: Boolean Function and their Representation K-Map Example2: Boolean Function and their Representation K-Map Example3: Boolean Function and their Representation K-Map Example4: Boolean Function and their Representation K-Map Example5: Boolean Function and their Representation K-Map Example6: Minimize the following boolean function- F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15) F(A, B, C, D) = BD + C’D + B’D’ Boolean Function and their Representation K-Map Minimize the following Boolean function- Example7: F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15) F(A, B, C, D) = B’C’ + D Boolean Function and their Representation K-Map Minimize the following Boolean function- Example8: F(A, B, C, D) = Σm(3, 4, 5, 7, 9, 13, 14, 15) F(A, B, C, D) = A’BC’ + A’CD + AC’D + ABC Boolean Function and their Representation K-Map Minimize the following Boolean function- Example9: F(W, X, Y, Z) = Σm(1, 3, 4, 6, 9, 11, 12, 14) F(W, X, Y, Z) = X ⊕ Z Boolean Function and their Representation K-Map –Don’t Care: for a function is an input- sequence (a series of bits) for which the function output does not matter An input that is known never to occur is a can't-happen term Also known as redundancies irrelevancies optional entries invalid combinations vacuous combinations forbidden combinations unused states or logical remainders Boolean Function and their Representation K-Map –Don’t Care Example10: Minimize the following Boolean function- F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 5) F(A, B, C) = AB + A’B’ Boolean Function and their Representation K-Map Example11 : Minimize the following Boolean function- F(A, B, C) = Σm(1, 2, 5, 7) + Σd(0, 4, 6) F(A, B, C) = A + B’ + C’ Boolean Function and their Representation K-Map Example12: Minimize the following Boolean function- F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 4, 5) F(A, B, C) = A + B’ Boolean Function and their Representation K-Map Example13: Minimize the following Boolean function- F(A, B, C, D) = Σm(1, 3, 4, 6, 8, 9, 11, 13, 15) + Σd(0, 2, 14) F(A, B, C, D) = AD + B’D + B’C’ + A’D’ Boolean Function and their Representation K-Map Example13: Minimize the following Boolean function- F(A, B, C, D) = m(1, 2, 6, 7, 8, 13, 14, 15) + d(3, 5, 12) Boolean Function and their Representation K-Map -POS Example1: F(A,B,C,D)=π(3,5,7,8,10,11,12,13) (C+D’+B’).(C’+D’+A).(A’+C+D).(A’+B+C’) Boolean Function and their Representation K-Map -POS Example1: F(A,B,C,D) = ∏(0,1,2,4,5,7,10,15) (C+D’+B’).(C’+D’+A).(A’+C+D).(A’+B+C’) Boolean Function and their Representation K-Map -POS Example1: Boolean Function and their Representation K-Map Solving 5 variable SOP and POS expressions using K map: To solve Boolean expression with 5 variables, 25 cells are required. So we need 32 cells. It can be split into two K map and can be solved. The numbering of the cells is given below. Boolean Function and their Representation K-Map Example 1: Minimize the following 5 variable SOP function using K map: F(A,B,C,D,E)= ∑m(0,5,6,8,9,10,11,16,20,24,25,26,27) F(A,B,C,D,E)= B'C'D'E'+ A'B’CD’E+ A'B’CDE’+ AB'D'E' +BC' Boolean Function and their Representation K-Map Example 2: Minimize the following 5 variable SOP function using K map: Boolean Function and their Representation K-Map Example 2: Minimize the following 5 variable SOP function using K map: Boolean Function and their Representation K-Map Example Boolean Function and their Representation K-Map -5 variable Example2: Topic covered from syllabus