Digital Logic System PDF - COMP 20013

PART 2: DIGITAL LOGIC SYSTEM LEARNING OUTCOMES At the end of this module, the student is expected to: 1. Define what boolean algebra is 2. Identify the different logic gates 3. Illustrate the representation of the different logic gates 4. Convert boolean algebra expression into a logic circ...

PART 2: DIGITAL LOGIC SYSTEM LEARNING OUTCOMES At the end of this module, the student is expected to: 1. Define what boolean algebra is 2. Identify the different logic gates 3. Illustrate the representation of the different logic gates 4. Convert boolean algebra expression into a logic circuit 5. Create truth tables for the corresponding logic circuits and boolean expression 6. Explain basic theorems and postulates on digital logic system COURSE MATERIALS Introduction George Boole (1815 – 1864) - developed an algebraic system to treat the logic functions, which is now called Boolean algebra. Claude Shannon (1916-2001)- is said to be the founder of Digital Circuit Design; It was in 1938 when Shannon applied boolean algebra to telephone switching circuits. And it was then the engineers realized that boolean algebra could be used to analyze and design computer circuits. Boolean Algebra - A branch of mathematics developed by George Boole - Provides a system of logic and reasoning using true and false statements suitable for representing switching circuits - The basic operations are complementation, multiplication, and addition. In digital systems, these operations are performed by inverters, AND gates, and OR gates respectively Boolean algebra differs from ordinary algebra - Ordinary algebra deals with real numbers, which consist of an infinite set of elements. Boolean algebra deals with only two elements, 0 and 1. - Boolean algebra defines an operator called complement which is not available in ordinary algebra. - Boolean algebra does not have additive or multiplicative inverses, so there are no subtraction or division operations Logic Gates Computer circuits are often called logic circuits because they simulate mental processes. These logic circuits are called GATES. A GATE is a digital circuit having one or more input signals but only one output signal. The basic gates are NOT, AND, OR. Unit III: Hardware - 50 | P a g e COMP 20013 - Introduction to Computing Operation Symbol Inversion NOT ‘ or an over bar Multiplication AND Addition OR + Using 1s and 0s, the representation is as follows: Inversion 1 =0 Multiplication 0 0=0 0 1=0 1 0=0 1 1=1 Addition 0 0=0 0 1=1 1 0=1 1 1=1 The Basic Gates : NOT, AND, OR Gates NOT Gate - Inverter OR Gate – Addition Unit III: Hardware - 51 | P a g e COMP 20013 - Introduction to Computing AND Gate – Multiplication Example of a logic circuit using the basic AND and OR gates Boolean expression : Z = XY + W Universal Gates : NAND and NOR Gates A universal logic gate is a logic gate that can be used to construct all other logic gates. This will be discussed in further details in later topics. NAND Gate Unit III: Hardware - 52 | P a g e COMP 20013 - Introduction to Computing NAND can also be drawn as below, NOR Gate NOR can also be drawn as below, Exclusive OR (XOR) Gate Unit III: Hardware - 53 | P a g e COMP 20013 - Introduction to Computing Exclusive NOR (XNOR) Gate Circuits that can perform binary addition and subtraction are constructed by combining logic gates. These circuits are used in the design of the arithmetic logic unit (ALU). The electronic circuits are capable of very fast switching action, and thus an ALU can operate at high clock rates. Example of two inverters entering an AND gate, with the corresponding truth table Unit III: Hardware - 54 | P a g e COMP 20013 - Introduction to Computing Postulates and theorems useful for two valued Boolean algebra Examples applying Theorem 4 (Distributive) and Postulate 5. F=AB+BC+B′C = AB + C(B + B′) = AB+C F=A+A′B = (A+A′)(A+B) =A+B F = A′B′C + A′BC + AB′ = A′C (B′+B) + AB′ = A′C + AB′ DeMorgan's Theorems DeMorgan’s Theorems are two additional simplification techniques that can be used to simplify Boolean expressions. Theorem 1 : (X + Y)’ = X’Y’ -> A NOR gate is same as a bubbled AND gate Unit III: Hardware - 55 | P a g e COMP 20013 - Introduction to Computing Theorem 2 : (XY)’ = X’ + Y’ -> A NAND gate is same as a bubbled OR gate Equivalence among circuits Double inversion has no effect on the logic state. If you invert the signal twice, you get the original signal back. Double invert a low, and you still have a low. Double invert a high, and you still have a high. The following three circuits will generate the same output. Using De Morgan’s theorem, we convert an OR-AND circuit to an all NOR circuit. Unit III: Hardware - 56 | P a g e COMP 20013 - Introduction to Computing Figure 3.4 Figure 3.5 Double inversion in Figure 3.5. , which makes it the same as in Figure 3.4. Applying De Morgan’s Theorem # 1, where a bubbled AND gate is the same as NOR, we come up with a following all NOR gate circuit Figure 3.6 Universal Gates Unit III: Hardware - 57 | P a g e COMP 20013 - Introduction to Computing A universal logic gate is a logic gate that can be used to construct all other logic gates. NAND gates and NOR gates are called universal gates as any type of gates or logic functions can be implemented by these gates. Basic gates NOT, AND, OR, implemented using all NAND gates Basic gates NOT, AND, OR, implemented using all NOR gates Unit III: Hardware - 58 | P a g e COMP 20013 - Introduction to Computing Fabrication of Integrated Circuit that performs a logic operation becomes easier when gate of only one kind is used. The advantage of using universal gates for implementation of logic functions is that it reduces the number of varieties of gates. Read: Digital Principles and Logic Design by A. Saba & N. Manna Digital Principles and Applications, 7th ed. By Leach, Malvino, Saha https://www.csus.edu/indiv/p/pangj/class/cpe64/ademo/L1_Demo_Demorgan.pdf www.secs.oakland.edu/~polis/Lectures/EGR240%20D5.1%20BasicLogicGates.ppt