Digital Logic Design IFT 211 PDF

IFT 211 DIGITAL LOGIC DESIGN COURSE OUTLINE Introduction to information representation and number systems. Boolean algebra and switching theory. Manipulation and minimisation of completely and incompletely specified Boolean functions. Physical properties of gates: fan-in, fan-out, propaga...

IFT 211 DIGITAL LOGIC DESIGN COURSE OUTLINE Introduction to information representation and number systems. Boolean algebra and switching theory. Manipulation and minimisation of completely and incompletely specified Boolean functions. Physical properties of gates: fan-in, fan-out, propagation delay, timing diagrams and tri-state drivers. Combinational circuits design using multiplexers, decoders, comparators and adders. Sequential circuit analysis and design, basic flip-flops, clocking and timing diagrams. Registers, counters, RAMs, ROMs, PLAs, PLDs, and FPGAs. Number systems Computer uses binary (base 2) number system, as they are made from binary digital components (known as transistors) operating in two states - on and off. It also uses octal, hexadecimal as a compact form for representing binary numbers. Binary (Base 2) Number System 10110B = 10000B + 0000B + 100B + 10B + 0B = 1×2^4 + 0×2^3 + 1×2^2 + 1×2^1 + 0×2^0 Decimal (Base 10) Number System 735 = 700 + 30 + 5 = 7×10^2 + 3×10^1 + 5×10^0 Hexadecimal (Base 16) Number System A3EH = A00H + 30H + EH = 10×16^2 + 3×16^1 + 14×16^0  exadecimal Binary Decimal 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 A 1010 10 B 1011 11 C 1100 12 D 1101 13 E 1110 14 F 1111 15 Conversion of numbers: Decimal to binary example 21110 to binary 2. 34510. 3. 712610 2 211 2 105 r1 2 52 r1 2. 26 r0 3 13 r0 4 6r1 2 3 r0 5 1r1 2. 0 r 1 110100112 Decimal to hexadecimal 26110 16 261 16 16 r5 17 1 r0 16 0 r1. 105h 567810 39410 Binary to decimal 10110B = 1×2^4 + 0×2^3 + 1×2^2 + 1×2^1 + 0×2^0 16 + 0 + 4 = 2 +0 = 2210 110100112 Decimal to octal 48710 8. 487 8 60 r7 8 7 r4 0. 7 7478 89010 Binary to hexadecimal 1001001010B = 0010 0100 1010B = 24AH 10001011001011B = 0010 0010 1100 1011B = 22CBH Hexadecimal to binary A3C5H = 1010 0011 1100 0101B 102AH = 0001 0000 0010 1010B Hexadecimal to octal A72E A 7 2 E 1010 0111 0010 1110 1010011100101110 group in 3’s 001 010 011 100 101 110 1 2 3 4 5 6 = 1234568 4.BF8516 4. B F 8 5 0100. 1011 1111 1000 0101 Group in 3’s 0 100. 101 111 111 000 010 100 0 4. 5 7 7 0 2 4 = 4.5770248 Octal to 247 8 hexadecimal 2 4 7 010 100 1112 = 010100111 Group in 4’s 0000 1010 0111 0 A 7 = A716 36.5328 to hexadecimal 3 6. 5 3 2 011 110. 101 011 010 Group in 4’s 0001 1110. 1010 1101 1 E. A D = 1E.AD16  convert 18.6875D to binary Integral Part = 18D 2. 18 2. 9. r 0 2 4r1 2 2r0 2 1r0 2. 0 r 1 =10010 Fractional Part =.6875D.6875*2=1.375 => whole number is 1.375*2=0.75 => whole number is 0.75*2=1.5 => whole number is 1.5*2=1.0 => whole number is 1 Hence.6875D =.1011B Combine, 18.6875D = 10010.1011B 10’s compliment 1) 10’s compliment of 2345010 - N R =10, N =5 =10 =7655010 2) 10’s compliment of 0.2345 n =0, = 0.6755 3) 10’s comp of 23.234 = - 23.324 = 76.676  9’s compliment -1)- N 9’s compliment of 2345010 - 1)- N (100000 – 1) – 23450 99999 – 23450 = 7654910 8’S compliment 24508 ) – 2450 10 8 4096 – 2450 10 8 4096 – 1320 10 10 = 2776 = 5330 10 8 16’s compliments 4A3016 )16 )10 – (4A30)16 6553610 - 4A3016 6553610 – 1899210 4654410 = B5D016 R’s and R-1 Complements General formula R’s complement :[2n]10 – N (R-1) complement: [(2n)10 -1]-N Example 10110012 1’s complement (27)10 -1 – 10110012 12710 – 10110012 1111111 – 1011001 = 01001102 Alternative: invert all bits 2’s complement 2’s complement 1011001 27 10 – N 12810 - 10110012 100000002 – 10110012 = 01001112 Alternative: add 1 to 1’s complement 0100110 + 1 0100111 2’s complement of hexadecimal reverse all bits and add 1 subtract each digit from 15 and add 1 Example 6A3D = 95C2 + 1 = 95C3 95C3 = 6A3C + 1 = 6A3D 21F0 = DE0F + 1 = DE10 DE10 = 21EF + 1 = 21F0 Complements 4’s complement of 224 444 – 224 = 220 5’s complement = 220 + 1 =221 9‘s complement of 1000 9999 – 1000 = 8999 10’s complement = 8999 + 1 = 9000 9’s complement subtraction A=1234 B = 1000 Find the 9’s complement of B and add it to A 9’s complement of B = 8999 1234 8999 10233 Add the carry + 1 00234 = 234 9’s complement subtraction A=1234 B = 3000 9’s complement f B =6999, add it to A 1234 + 6999 = 8233 ans = -(9’s complement of 8233) -1766 10’s complement subtraction A = 1234 B = 1000 10’s complement of B = 9000 1234 9000 10234 Discard the carry 234 A= 1234 B = 3000 10’s complement of B = 7000, add it to A 1234 + 7000 = 8234 Ans= -(10’s complement of 8234) = -1766  Subtract (1FA)16 from (2DC)16 using the 16’s complement method. Also subtract using the direct method and compare. Solution. Direct Subtraction 16’s complement method 2 D C 2 D C (+) – 1 F A 16’s complement E06 E2 Carry 10E2 Discard Carry (E 2)16 Subtract (2DC)16 from (1FA)16 using the 16’s complement method. Solution. Direct Subtraction 16’s complement method 1FA 1 F A (+) –2 D 16’s complement D24 101E F 1E Discard carry 1 E 16’s complement E2 16’s complement E2 True result (–E2)16 True result (–E2)16 Exercise 1Find the two’s complement of the following: (i) 10010101 (ii) 3FD4C1 (iii) 11100001 (iv) DE1B50 2 Subtract i) 1234 form 5678 ii) 3456 from 7866 using 10‘s complement Signed integers Signed integers are positive or negative, the MSB indicates the sign 0 is positive and 1 is negative 0111111 positive 1011011 negative Converting signed binary to hexadecimal Example: 1111 0000 starting value 1111 0000 step1: reverse the bits 0000 1111 step2: add 1 + 1 step3: form 2’s compliment 0001 0000 step4: convert to decimal 1*24 =16 Because the original integer (11110000) was negative, it decimal value is -16. Converting signed decimal to binary Example: -43 Binary representation of 43 is 00101011 Two’s compliment 11010100 +1 = 11010101 -43 is 11010101 Converting signed decimal to hexadecimal Convert the absolute value of the decimal integer to hexadecimal If the original decimal integer was negative, form the two’s compliment of the hexadecimal number from the previous step Converting signed hexadecimal to decimal If the hexadecimal integer is negative, form its two’s compliment otherwise retain the integer Using the integer from the previous step, convert it to decimal. If its original value was negative, attach a minus sign to the beginning of the decimal integer BINARY CODES Binary code is any data, text, or computer instructions represented using a two-symbol system. These two numeral symbols are 0 and 1. Weighted Binary Codes If each position of a number represents a specific 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. Example: BCD code Excess-3 code BCD code Decimal Number Binary Number BCD 0 0000 0000 0000 1 0001 0000 0001 2 0010 0000 0010 3 0011 0000 0011 4 0100 0000 0100 5 0101 0000 0101 6 0110 00000 0110 7 0111 0000 0111 8 1000 0000 1000 9 1001 0000 1001 10 (1+0) 1010 0001 0000 11 (1+1) 1011 0001 0001 12 (1+2) 1100 0001 0010 13 (1+3) 1101 0001 0011 14 (1+4) 1110 0001 0100 Decimal to BCD conversion convert the following decimal numbers: 8510, 57210 and 857910 into their 8421 BCD equivalents. 8510 = 1000 0101 (BCD) 57210 = 0101 0111 0010 (BCD) 857910 = 1000 0101 0111 1001 (BCD) BCD to Decimal Convert the following binary numbers: 10012, 10102, 10001112 and 10100111000.1012 into their decimal equivalents. 10012 = 1001BCD = 910 10102 = error! decimal 1010 , not a valid BCD number 10001112 = 0100 0111BCD = 4710 10100111000.1012 = 0101 0011 1000.1010BCD = 538.62510 Excess-3 Code The excess – 3 code of a decimal number is achieved by adding the number 3 to the 8421 code. Example to convert 15 to an excess-3 code, first 3 to be added to each digit  Excess-3 Code Find the excess-3 code of (237.75)10 Add 3 to all the digits individually, 2 +3 = 10, 3+3 =6 and 7+3 =10 Binary equivalent is 010101101010. The excess-3 code for (.75)10 7+3 =10, 5+3 =8 The excess-3 code for (.75)10 is.10101000. The excess-3 code for (237.75)10 is 010101101010.10101000.  Excess-3 Code The excess-3 code is 110010100011.01110101 Group the bits in 4s 1100 1010 0011.0111 0101. Subtracting 0011 from each four-bit group, 1001 0111 0000.0100 0010. Therefore, the decimal equivalent is (970.42)10. Gray Code The Gray code is the code where one bit will differ to the preceding number. Decimal Binary Gray code 0 0000 0000 1 0001 0001 2 0010 0011 3 0011 0010 4 0100 0110 5 0101 0111 6 0110 0101 7 0111 0100 8 1000 1100 9 1001 1101 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 Binary to Gray Code Example Gray to Binary code Convert (110011100)g to binary Example BCD Addition Binary No 1010 through 1111 are illegal If Sum < 9, add 0000 If Sum > 9 add 0110 Sum results into a carry add 0110 BCD addition  Excess-3 Addition 0000 t0 0010 and 1101 t0 1111 are illegal If sum < 9, add 0011 (3) If sum >= 9, subtract 0011 Sum > 9 if there’s a carry to the next digit  The addition of 13.1 and 11.3 in excess-3 Ex-3 of 13.1 0100 0110. 0100 Ex-3 of 11.3 0100 0100. 0110 1000 1010. 1010 - 0011 0011. 0011 0101 0111. 0111 5 7. 7 (24.4)d Exercise: find the addition of 2710 and 3910 , 2310 and 3310 Digital electronics Digital is generally associated with a computer because the term Digital is derived from the way computers perform operation, by counting digits. other applications. Industrial process control Military system Television Communication system Medical equipment Radar Navigation SIGNAL physical quantity containing some information Analog Signal Disadvantages Less accuracy Less versatility More noise effect More distortion More effect of weather Digital Signal Advantages More accuracy More versatility Less distortion Easy communicate Possible storage of information Computer Circuits circuit is a path between two or more points along which an electrical current can be carried. Computer Circuits is a complete path or combination of interconnected paths for electron flow in a computer. Computer circuits are binary in concept, having only two possible states. Diodes Array A diode is an electrical device allowing current to move through it in one direction with far greater ease than in the other. The most common kind of diode in modern circuit design is the semiconductor diode The term “diode” is customarily reserved for small signal devices, I ≤ 1 A. The term rectifier is used for power devices, I > 1 A. Circuit diagram Diode Array Series of diodes connected in a circuit for specific functions, mainly to protect electronic circuits from surge voltages. Suppress surge pulse Dissipate the energy of surge pulse Divert the transient to the power-bus or ground and away from sensitive IC components. Attributes: low capacitance, low clamping voltage, good capacitive matching Varieties application Protect high speed data interfaces/ data lines / control lines operating on power supply Protect sensitive components connected to data transmission lines from voltage caused by electrostatic discharge (ESD), electrical fast transients (ETF) and lightning Low voltage digital logic ICS DC power lines / High frequency applications Diode Array Diode Array Diode Array Integrated circuits [Ics] Ics: complete electronic circuits where both the passive and active elements are fabricated n a single silicon chip. Active components: produce gain eg transistors, FETs passive components: no gain eg resistors, capacitors and inductors Merits and Demerits Merits: Extreme small physical size Very small weight Reduced cost Extremely high reliability Increased response time and speed Low power consumption Easy replacement Higher yield Drawbacks of IC Coils or inductor cannot be fabricated IC function at fairy low voltages They handle only limited amount of power They are quite delicate and cannot withstand rough handling or excessive heat  Scale of integration SSI < 12 circuits < 50 Components MSI 13 – 99 circuits 50 – 500 Components LSI 100 – 9,999 circuits 5000 – 100,000 Components VLSI 10,000 – 99,999 circiuts 10,000 – 1,000,000 Components ULSI 100,000 – 999,999 circits 1,000,000 – 10,000,000 Components GSI > 1,000,000 circuits > 100,000,000 Components Classification of ICs by structure Monolithic ICs : singe stone/solid structure, all circuits components are fabricated inseparably within a single continuous piece of silicon wafer Thick and thin film ICs: these are not formed within a silicon wafer but on the surface of an insulating substrate like glass or ceramic material, Hybrid or multichip ICs: are formed either by inter-connecting a number of individual chips or by a combination f film and monolithic techniques. IC Fabrication Integrated circuit: thousands, millions of components on a single chip, all of the components in the circuit (and their “wires”) are fabricated simultaneously onto a circuit during the manufacturing process Wafer Substrate/wafer: a thin slice of silicon Circular, 4 to 18 inches in diameter, 1mm thick Basic Fabrication Processes sequence or process of chemical and mechanical modifications is performed on certain areas of the wafer Implantation: Atoms or molecules are added to the silicon wafer, changing its electronic properties. Deposition: Materials such as metals, insulators, or semiconductors are added in thin layers (like painting) onto the wafer. Etching: Material is removed from the wafer through chemical reactions or mechanical motion. IC Fabrication Process Steps Lithography: Etching: Deposition: Chemical Mechanical Polishing: Oxidation: Ion Implantation: Diffusion: Representing Logic Functions There are several ways of representing logic functions: – Symbols to represent the gates – Truth tables – Boolean algebra Basic Gate The AND Gate OR gate NOT gate NAND and NOR gates EXOR and EXNOR gates Logic gates representation withTruth table Example If chimney is not blocked and the house is cold and the pilot light is lit, then open the main fuel valve to start boiler. b = chimney blocked c = house is cold p = pilot light lit v = open fuel valve Multi Input Gates Families of logic gates Diode Logic (DL) Resistor-Transistor Logic (RTL) Diode-Transistor Logic (DTL): Transistor-Transistor Logic (TTL) Emitter-Coupled Logic (ECL) CMOS Logic Assignment: write short notes on the above listed gates Boolean Algebra Binary logic deals with variables that have two discrete values—1 for TRUE and 0 for FALSE, Switching can be expresses using Boolean Algebra defined with a set of elements, a set of operators, and a number of assumptions and postulates tool to reduce logical expressions  1 Associative Law: (A*B)*C = A*(B*C) for all A,B,C ∈ S. 2. Commutative Law: A*B = B*A for all A,B ∈ S. 3. Identity Element: E*A = A*X = A. Example: A + 0 = 0 + A = A. A × 1 = 1 × A = A. 4. Inverse: the inverse of an element A is (-A) since A + (–A) = 0. 6. Distributive Law: A*(B.C) = (A*B).(A*C). Summary The binary operator + defi nes addition. The additive identity is 0. The additive inverse defi nes subtraction. The binary operator (.) defi nes multiplication. The multiplication identity is 1. The multiplication inverse of A is 1/A, defi nes division i.e., A. 1/A = 1. The only distributive law applicable is that of (.) over + A. (B + C) = (A. B) + (A. C)  list of postulates and theorems Postulate 2 (a) A + 0 = A (b) A.1 = A Postulate 5 (a) A + A′ = 1 (b) A.A′ = 0 Theorem 1 (a) A + A = A (b) A.A = A Theorem 2 (a) A + 1 = 1 (b) A.0 = 0 Theorem 3, Involution (A′)′ = A Theorem 3, Commutative (a) A + B = B + A (b) A.B = B.A Theorem 4, Associative (a) A + (B + C) = (A + B) + C (b) A.(B.C) = (A.B).C Theorem 4, Distributive (a) A(B + C) = A.B + A.C (b) A + B.C = (A + B).(A + C) Theorem 5, DeMorgan (a) (A + B)′ = A′.B′ (b) (A.B)′ = A′ + B′ Theorem 6, Absorption (a) A + A.B = A (b) A.(A + B) = A  Proof of Theorems Theorem 1 : (a) X+X=X x+x=(X+X).1 by postulate 2b =(x+x)(x+x′) 5a =x+xx′ 4b =x+0 5b =x 2a Prove Theorem 1 : (b) X.X=X xx=(X.X)+0 by postulate 2a =x.x+x.x′ 5b =x(x+x′) 4a =x.1 5a =x 2b  proof Theorem 2 : (a) X+1=X x+1=1.(X+1) by postulate 2b (x+x′)=(x+1) 5a =x+x′.1 4b =x+ x′ 2b =1 5a Prove Theorem 2 : (b) X.0=0 x.0=0+(X.0) by postulate 2a (x.x′)=(x.0) 5b =x.x′+0 4a =x.x′ 2a =0 5b proof Theorem 6 : (b) X(x+y)=X X(x+y)=(x+0).(x+y) by postulate 2a =x+0.y 4a =x +0 2a =x 2a  De Morgan’s Theorem Theorem1: states that the complement of a product is equal to the sum of the complements. That is, if the variables are A and B, then (A.B)′ = A′ + B′ Theorem2: states that the complement of a sum is equal to the product of the complements. In equation form, this can be expressed as (A + B)′ = A′. B′ The complements of Boolean logic function or a logic expression may be simplified or expanded by the following steps of DeMorgan’s theorem. (a) Replace the operator (+) with (.) and (.) with (+) given in the expression. (b) Complement each of the terms or variables in the expression. DeMorgan’s theorems are applicable to any number of variables. For three variables A, B, and C, the equations are (A.B.C)′ = A′ + B′ + C′ and (A + B + C)′ = A′.B′.C′ De Morgan’s Theorem Examples Simplify a.b` + a.(b + c)` + b.(b + c)` = a.b` + a.b`.c` + b.b`.c` (DeMorgan) = a.b` + a.b`.c` (b.b` = 0) = a.b` (absorbtion)  DeMorgan’s Simplify [a.b.(c + (b.d)` ) + (a.b)` ].c.d = (a.b.(c + b` + d` ) + a` + b` ).c.d (DeMorgan) = (a.b.c + a.b.b` + a.b.d` + a` + b` ).c.d (distribute) = (a.b.c + a.b.d` + a` + b` ).c.d (a.b.b` = 0) = a.b.c.d + a.b.d`.c.d + a`.c.d + b`.c.d (distribute) = a.b.c.d + a`.c.d + b`.c.d (a.b.d`.c.d = 0) = (a.b + a` + b` ).c.d (distribute) = (a.b + (a.b)`).c.d (DeMorgan) = c.d (a.b + (a.b)` =1)  DeMorgan’s in Gates f = a.b + c.d Simpification Simplify the function F=AB+ BC + B′C. Solution. F = AB + BC + B′C = AB + C(B + B′) = AB + C Simplify the function F= A′B′C + A′BC + AB′. Solution. F = A′B′C + A′BC + AB′ = A′C (B′+B) + AB′ = A′C + AB′  Simplify the function F = AB + (AC)′ + AB′C(AB + C). Solution. F = AB + (AC)′ + AB′C(AB + C) = AB + A′ + C′+ AB′C.AB + AB′C.C = AB + A′ + C′ + 0 + AB′C (B.B′ = 0 and C.C = C) = ABC + ABC′ + A′ + C′ + AB′C (AB = AB(C + C′) = ABC + ABC′) = AC(B + B′) + C′(AB + 1) + A′ = AC + C′+A′ (B + B′ = 1 and AB + 1 = 1) = AC + (AC)′ =1  Simplify the function F = ((XY′ + XYZ)′ + X(Y + XY′))′. Solution. F = ((XY′ + XYZ)′ + X(Y + XY′))′ = ((X(Y′ + YZ))′ + XY + XY′)′ = ((X(Y′Z + Y′ + YZ))′ + X(Y + Y′))′ (Y′ = Y′(Z + 1) = Y′Z + Y′) = (X(Y′ + Z))′ + X)′ = (X′ + (Y′ + Z)′ + X)′ = (1+ YZ′)′ = 1′ =0 Combinational Circuit outputs at any time is determined directly from the present combination of input without any regard to the previous input. Truth Table CANONICAL AND STANDARD FORMS (i) Sum of the Products (SOP) (ii) Product of the Sums (POS) Product Term. An AND function is a product term, the logical product of several variables on which a function depends eg. ABC, XYZ` Sum Term: An OR function is a sum term. The logical sum of several variables on which a function depends eg.. A+B+C Standard form: Boolean function expressed in sum of the products or product of the sums fashion Minterm and Maxterms Minterm: A product term containing all n variables of the function in either true or complemented form Possible combination is 2n where n is the number of variables 2 variables 4 combinations 3 variables 8 combinations etc Maxterm: A sum term containing all n variables of the function in either true or complemented forming variables: forming an OR term provide 2n possible combinations called maxterms or standard sum. Minterms  Obtain the canonical sum of product form of the following function: F (A, B) = A + B Solution F (A, B) = A + B = A.1 + B.1 = A (B + B′) + B (A + A′) = AB + AB′ + AB + A′B = AB + AB′ + A′B (as AB + AB = AB)  Obtain the canonical sum of product form of the following function: F (A, B, C) = A + BC Solution F (A, B, C) = A + BC = A (B + B′) (C + C′) + BC (A + A′) = (AB + AB′) (C + C′) + ABC + A′BC = ABC + AB′C + ABC′ + AB′C′ + ABC + A′BC = ABC + AB′C + ABC′ + AB′C′ + A′BC (as ABC + ABC = ABC)  Obtain the canonical sum of product form of the following function: F (A, B, C, D) = AB + ACD Solution. F (A, B, C, D) = AB + ACD = AB (C + C′) (D + D′) + ACD (B + B′) = (ABC + ABC′) (D + D′) + ABCD + AB′CD = ABCD + ABCD′ + ABC′D + ABC′D′ + ABCD +AB′CD = ABCD + ABCD′ + ABC′D + ABC′D′ + AB′CD  Obtain the canonical product of the sum form of the following function. F (A, B, C) = (A + B′) (B + C) (A + C′) Solution F (A, B, C) = (A + B′) (B + C) (A + C′) = (A + B′ + 0) (B + C + 0) (A + C′ + 0) = (A + B′ + CC′) (B + C + AA′) (A + C′ + BB′) = (A + B′ + C) (A + B′ + C′) (A + B + C) (A′ + B + C) (A + B + C′) (A + B′ + C′) [using the distributive property, as X + YZ = (X + Y)(X + Z)] = (A + B′ + C) (A + B′ + C′) (A + B + C) (A′ + B + C) (A + B + C′) [as (A + B′ + C′) (A + B′ + C′) = A + B′ + C′]  Obtain the canonical sum of product form of the following function. F (A, B, C, D) = AB + ACD Solution. F (A, B, C, D) = AB + ACD = AB (C + C′) (D + D′) + ACD (B + B′) = (ABC + ABC′) (D + D′) + ABCD + AB′CD = ABCD + ABCD′ + ABC′D + ABC′D′ + ABCD + AB′CD = ABCD + ABCD′ + ABC′D + ABC′D′ + AB′CD Deriving a Sum of Products (SOP) Expression from a Truth Table Procedure 1 Form a product term for each input combination in the table, containing an output value of 1. 2 Each product term consists of its input variables in either true form or complemented form. If the input variable is 0, it appears in complemented form and if the input variable is 1, it appears in true form. 3. To obtain the final SOP expression of the output, all the product terms are OR operated. Deriving a Product of Sums (POS) Expression from a Truth Table Procedure 1. Form a sum term for each input combination in the table, containing an output value of 0. 2. Each product term consists of its input variables in either true form or complemented form. If the input variable is 1, it appears in complemented form and if the input variable is 0, it appears in true form. 3. To obtain the final POS expression of the output, all the sum terms are AND operated. Maxterm  Karnaugh Map Karnaugh Maps (or K-maps) are a powerful visual tool for carrying out simplification and manipulation of logical expressions having up to 5 variables The K-map is a rectangular array of cells – Each possible state of the input variables corresponds uniquely to one of the cells – The corresponding output state is written in each cell K-maps example 4-variable 5 Variable 6 Variable Examples Simplify F = A′B′C + A′BC + A′BC′ + AB′C + ABC F = C′ + AB′. F = C′ + AB′. Simplify the expression F (A, B, C, D) = m1 + m5 + m10 + m11 + m12 + m13+ m15. F = A′C′D + ABC′ + ACD + AB′C. Simplify the expression F (A, B, C, D) = m1 + m5 + m10 + m11 + m12 + m13 + m15. Simplify the expression F (A, B, C, D) = m7 + m9 + m10 + m11 + m12 + m13 + m14 + m15. F = AB + AC + AD + BCD. Don’t-care Combination In certain digital systems, some input combinations never occur during the process of a normal operation because those input conditions are guaranteed never to occur, they are called Don’t-Care Combinations. The function output may be either 1 or 0 are called incompletely specified functions. can be plotted on the Karnaugh map for further simplifi cation of the function. The don’tcare combinations are represented by d or x or Φ. Example  Exercise Using a Karnaugh map, simplify the following functions and implement them with basic gates. 1) Obtain (a) the minimal sum of the products and (b) minimal product of the sums for the function F (W,X,Y,Z) = Σ (0, 1, 2, 5, 8, 9, 10). 2) F (A, B, C, D) = Σ (0, 2, 3, 5, 7, 8, 13) + d (1, 6, 12) 3) F (A, B, C, D) = Σ (1, 7, 9, 10, 12, 13, 14, 15) + d (4, 5, 8) 4) F (A, B, C, D) = π (0, 8, 10, 11, 14) + d (6) 5) F (A, B, C, D) = π (2, 8, 11, 15) + d (3, 12, 14)  THE TABULATION METHOD (Quine-McCluskey method) Determination of Prime Implicants 1 Each minterm of the function is expressed by its binary representation. 2 The minterms are arranged according to increasing index (index is defi ned as the number of 1s in a minterm). Each set of minterms possessing the same index are separated by lines. 3 Now each of the minterms is compared with the minterms of a higher index. For each pair of terms that can combine, the new terms are formed. If two minterms are differed by only one variable, that variable is replaced by a ‘-’ (dash) to form the new term with one less number of literals. A line is drawn in when all the minterms of one set is compared with all the minterms of a higher index. 4 The same process is repeated for all the groups of minterms. A new list of terms is  Prime Implicant Chart 1 After obtaining the prime implicants, a chart or table is prepared where rows are represented by the prime implicants and the columns are represented by the minterms of the function. 2Crosses are placed in each row to show the composition of the minterms that makes the prime implicants. 3A completed prime implicant table is to be inspected for the columns containing only a single cross. Prime implicants that cover the minterms with a single cross are called the essential prime implicants. F (A, B, C, D) = Σ (1, 4, 6, 7, 8, 9, 10, 11, 15). the simplified Boolean expression of the given function can be written as F = AB′ + B′C′D + A′BD′ + BCD.  Obtain the minimal sum of the products for the function using the Quine-McClusky method F (A,B,C,D) = Σ(1, 2, 3, 7, 8, 9, 10, 11, 14, 15)  Designing Combinatorial Circuits Steps: The problem is stated - Determine the number of available input variables and required output variables. - Assigned letter symbol to the input and output variable - Derive the truth table that defines the required relationship between the inputs and the outputs - obtain the simplified Boolean function for each output - Draw the logic diagram Half Adder Sequential Circuits Sequential Circuits Bistable is so called because its output can remain in one of two states indefinitely, even if the input changes. is the smallest possible memory cell and stores only a single bit of information. two classes, Synchronous systems use a master clock to update the state of all flip-flops periodically. Asynchronous system: a change in an input signal triggers a change in another circuit and the changes ripples through the system Latches Flip-flops Basic flip-flop circuit with NOR gates Basic flip-flop circuit with NAND gates Clocked SR flip-flop Clocked D flip-flop Clocked JK flip-flop T Flip-Flop