ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 1 DIGITAL ELECTRONICS AND MICROPROCESSORS ELM3111 Digital Electronics and Microprocessors Some of the contents are adopted from M. Morris Mano, Michael D Ciletti.Digital Design, 4nd edition, Pearson & Prentice Hall, 2007. ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Contents 2-3 Canonical vs Standard Forms of the Boolean Expressions › Sum of Minterms and product of Maxterms examples › Canonical vs Standard representations 2-4 Other Commonly used gates 2-5 Special Notes on Gates 3- Gate level Minimization › Karnaugh Diagrams 2 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 3 2-3 Canonical Vs Standard Forms Of The Boolean Expressions ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 4 Conversion Between Canonical Forms Example: Consider the function F(A, B, C)=Σ (1, 2, 3, 7). Express the function using product of maxterms. Solution: F’(A, B, C)=Σ (0, 4, 5, 6)= m0 + m4 + m5 +m6 Now use De-Morgan’s Law F(A,B,C)=(F’(A, B, C))’= (m0 + m4 + m5 +m6)’=M0M4M5M6 Where Mj=mj’ 5 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Conversion Between Canonical Forms A B C F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 m0 (A’B’C’) M0 (A+B+C) m4 (AB’C’) M4 (A’+B+C) m5 (AB’C) M5 (A’+B+C’) m6 (ABC’) M6 (A’+B’+C) Mj=mj’ ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Conversion Between Canonical Forms A B C A’B’C xy canonical A’BC’ A’BC A’BC F(A,B,C)=Σ (1, 2, 3, 7). 6 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Conversion Between Canonical Forms A B C A+B+C A’+B+C A’+B+C’ A’+B’+C canonical F(A,B,C)= ΠM0M4M5M6 7 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Standard Forms F1=y’+xy+x’yz’ F2=x(y’+z)(x’+y+z’) 8 These are standard form Boolean expressions - Two level representation - Sum of products or product of sums with reduced number of variables in the terms (not canonical) ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 2-4 Other Commonly Used Gates 9 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Logic functions of N variables • • So far, we have defined 3 gates Why consider new gates? • Cheaper hardware, more flexibility. 10 11 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek The NAND Gate x y • • • z This is a NAND gate. It is a combination of an AND gate followed by an inverter. NAND gates have several interesting properties. NAND(a,a)=(aa)’ = a’ = NOT(a) (NAND(a,b))’=(ab)’’ = ab = AND(a,b) NAND(a’,b’)=(a’b’)’ = a+b = OR(a,b) x y z 0 0 1 0 1 1 1 0 1 1 1 0 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 12 The NAND Gate • These three properties show that a NAND gate with both of its inputs driven by the same signal is equivalent to a NOT gate • A NAND gate whose output is complemented is equivalent to an AND gate, and a NAND gate with complemented inputs acts as an OR gate. • Therefore, we can use a NAND gate to implement all three of the elementary operators (AND,OR,NOT). • Therefore, ANY switching function can be constructed using only NAND gates. Such a gate is said to be primitive or functionally complete. ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 13 NAND Gates into Other Gates what are these circuits? x x’ NOT Gate x y xy AND Gate x x+y y OR Gate 14 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek The NOR Gate • • x y z This is a NOR gate. It is a combination of an OR gate followed by an inverter. NOR gates also have several interesting properties NOR(a,a)=(a+a)’ = a’ = NOT(a) NOR’(a,b)=(a+b)’’ = a+b = OR(a,b) NOR(a’,b’)=(a’+b’)’ = ab = AND(a,b) x 0 0 1 1 y 0 1 0 1 z 1 0 0 0 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 15 The NOR Gate • • • • • Like the NAND gate, the NOR gate is functionally complete. Any logic function can be implemented using just NOR gates. Both NAND and NOR gates are very valuable as any design can be realized using either one. It is easier to build an IC chip using all NAND or NOR gates than to combine AND,OR, and NOT gates. NAND/NOR gates are typically faster at switching and cheaper to produce. 16 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek The NOR Gate into other Gates x x’ x y x+y NOT Gate OR Gate x xy y AND Gate 17 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek The XOR Gate (Exclusive-OR) x y z • XOR gates assert their output when exactly one of the inputs is asserted, hence the name. • The switching algebra symbol for this operation is , i.e. 1 1 = 0 and 1 0 = 1. x 0 0 1 1 y 0 1 0 1 z 0 1 1 0 18 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek The XNOR Gate x y z • • This is a XNOR gate. This functions as an exclusive-NOR gate, or simply the complement of the XOR gate. • The switching algebra symbol for this operation is , i.e. 1 1 = 1 and 1 0 = 0. 0 x y z 0 0 1 1 0 1 0 0 1 1 1 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Example 19 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 20 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 2-4 Special Notes On Gates 21 22 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Integrated Circuits- Digital Logic Families • IC’s in a semiconductor chip is called a chip, • It contains the electronic components for constructing gates CMOS NOT gate TTL NOT gate Digital Logic Families TTL transistor–transistor logic; ECL emitter‐coupled logic; MOS metal‐oxide semiconductor; CMOS complementary metal‐oxide semiconductor. ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 23 Integrated Circuits- Integration Level • Digital ICs are often categorized according to the complexity of their circuits, • Small‐scale integration (SSI) devices contain several independent gates in a single package. The inputs and outputs of the gates are connected directly to the pins in the package. The number of gates is usually fewer than 10 and is limited by the number of pins available in the IC. • Medium‐scale integration (MSI) devices have a complexity of approximately 10 to 1,000 gates in a single package. decoders, adders, and multiplexers registers and counters. • Large‐scale integration (LSI) devices contain thousands of gates in a single package. Processors, memory chips, and programmable logic devices. • Very large‐scale integration (VLSI) devices now contain millions of gates within a single package. large memory arrays and complex microcomputer chips. • Because of their small size and low cost, VLSI devices have revolutionized the computer system design technology, giving the designer the capability to create structures that were previously uneconomical to build. ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Integrated Circuits 24 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Integrated Circuits 25 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 3 Gate Level Minimization 26 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Gate Level Minimization Problem Example: using the canonical form of the function F(A, B, C)=Σ (0, 4, 5, 6) simplify it • m0 =(A’B’C’) • m4 =(AB’C’) • m5 =(AB’C) • m6 =(ABC’) F= A’B’C’+ AB’C’+ AB’C+ AB’C’+ ABC’+ AB’C’ F= B’C’+ AB’+ AC’ 27 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 28 Efficient Gate Level Minimization • Gate-level minimization is the design task of finding an optimal gate-level implementation of the Boolean functions describing a digital circuit. • This task is well understood, but is difficult to execute by manual methods when the logic has more than a few inputs. • Fortunately, computer-based logic synthesis tools can minimize a large set of Boolean equations efficiently and quickly. • Nevertheless, it is important that a designer understand the underlying mathematical description and solution of the problem. ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 29 Efficient Gate Level Minimization • The complexity of the digital logic gates that implement a Boolean function is directly related to the complexity of the algebraic expression from which the function is implemented. • Although the truth table representation of a function is unique, when it is expressed algebraically it can appear in many different, but equivalent, forms. Boolean expressions may be simplified by algebraic means minimization is awkward because it lacks specific rules to predict each succeeding step in the manipulative process. THE MAP METHOD • The map method presented here provides a simple, straightforward procedure for minimizing Boolean functions. • This method may be regarded as a pictorial form of a truth table. The map method is also known as the Karnaugh map or K-map . ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 30 Efficient Gate Level Minimization • A K-map is a diagram made up of squares, with each square representing one minterm of the function that is to be minimized. • Any Boolean function can be expressed as a sum of minterms, it follows that a Boolean function is recognized graphically in the map from the area enclosed by those squares whose minterms are included in the function. • In fact, the map presents a visual diagram of all possible ways a function may be expressed in standard form. • By recognizing various patterns, the user can derive alternative algebraic expressions for the same function, from which the simplest can be selected. • The simplified expressions produced by the map are always in one of the two standard • forms: sum of products or product of sums. • It will be assumed that the simplest algebraic expression is an algebraic expression with a minimum number of terms and with the smallest possible number of literals in each term. • This expression produces a circuit diagram with a minimum number of gates and the minimum number of inputs to each gate. • We will see subsequently that the simplest expression is not unique: It is sometimes possible to find two or more expressions that satisfy the minimization criteria. In that case, either solution is satisfactory 31 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Karnaugh Map for sum of products F = Σ(m0,m1) = A’B + A’B’ B 0 1 0 A’B’ A’B 1 AB’ AB A If A’B=1 for A=0, B=1 put 1 here A B F 0 0 1 0 1 1 1 0 0 1 1 0 B 0 1 0 1 1 1 0 0 A 32 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Karnaugh Map for sum of products A B C F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 BC 00 01 11 10 0 0 1 0 1 1 1 1 1 1 A F=AB’C’ +AB’C +ABC +ABC’ + A’B’C + A’BC’ ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek 33 Rules for K-Maps We can reduce functions by circling 1’s in the K-map Each circle represents minterm reduction Following circling, we can deduce minimized and-or form. Rules to consider Every cell containing a 1 must be included at least once. The largest possible “power of 2 rectangle” must be enclosed. The 1’s must be enclosed in the smallest possible number of rectangles. 34 ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek Rules for K-Maps • A Karnaugh map is a graphical tool for assisting in the general simplification procedure A 0 1 B 0 1 0 1 1 0 1 0 0 1 1 1 1 A F=A’ B 0 F=A’B + A’B’ F=B+A F=AB+A’B + AB’ BC 00 01 11 10 0 0 1 0 1 1 1 1 1 1 A F=A+B’C +BC’ F=AB’C’ +AB’C +ABC +ABC’ + A’B’C + A’BC’

Download
# Lecture notes 4