Digital Logic Design PDF

Boolean Algebra & Logic Gates By : MCs.Shahad Ali  Digital Logic Gates There are three fundamental logical operations, from which all other functions, no matter how complex, can be derived. These Basic functions are named: –AND –OR –NOT (INVERTER)  A...

Boolean Algebra & Logic Gates By : MCs.Shahad Ali  Digital Logic Gates There are three fundamental logical operations, from which all other functions, no matter how complex, can be derived. These Basic functions are named: –AND –OR –NOT (INVERTER)  AND Gate Represented by any of the following notations: – X AND Y –X.Y –XY Function definition: Z = 1 only if X=Y=1 0 otherwise  OR Gate Represented by any of the following notations: – X OR Y –X+Y Function definition: Z = 1 if X=1 or Y =1 or both X=Y=1 0 if X=Y=0  NOT (Inverter) Gate Represented by a bar over the variable Function definition:  It is also called complement operation , as it changes 1’s to 0’s and 0’s to 1’s. Logic gates timing Diagram Timing diagrams illustrate the response of any gate to all possible input signal combinations. The horizontal axis of the timing diagram represents time and the vertical axis represents the signal as it changes between the two possible voltage levels 1 or 0 Other Gates Others Gates  Digital Logic How to describe Digital logic system? We have two methods: Truth Table Boolean Expression  TRUTH TABLE A Truth Table is a table of combinations of the binary variables showing the relationship between the different values that the input variables take and the result of the operation (output). The number of rows in the Truth Table is where n = number of input variables in the function. The binary combinations are obtained from the binary number by counting from 0 to Example: AND gate with 2 inputs – n=2 – The truth table has 2 rows = 4 – The binary combinations is from 0 to (22-1=(3)) [00,01,10,11]  BOOLEAN EXPRESSIONS We can use these basic operations to form more complex expressions: Some terminology and notation: – f is the name of the function. –(x,y,z) are the input variables, each representing 1 or 0. Listing the inputs is optional, but sometimes helpful. – A literalis any occurrence of an input variable or its complement. The function above has four literals: x, y’, z, and x’.  How to get the Boolean Expression from the truth table? Boolean Expressions From Truth Tables Each 1 in the output of a truth table specifies one term in the corresponding boolean expression.  Example Find boolean expression? Example Solution  Basic Logic gates We have defined three basic logic gates and operators Also, we could build any digital circuit from those basic logic gates. In digital Logic, we are not using normal mathematics we are using Boolean algebra So, we need to know the laws & rules of Boolean Algebra  Boolean Algebra What’s the difference between the Boolean Algebra and arithmetic algebra? The First obvious difference that in Boolean algebra we have only (+) and (.) operators we don’t have subtraction(-) or division(/) like math.  Binary Logic You should distinguish between binary logic and binary arithmetic. – Arithmetic variables are numbers that consist of many digits. Arithmetic A binary logic variable is always either 1 or 0.  Binary Laws & Rules of Boolean Algebra The basic laws of Boolean algebra: –The commutative law –The associative law –The distributive law  Commutative Law The commutative law of addition for two variables is written as: A+B = B+A The commutative law of multiplication for two variables is written as: AB = BA  Associative Law The associative law of addition for 3 variables is written as: A+(B+C) = (A+B)+C The associative law of multiplication for 3 variables is written as: A(BC) = (AB)C  Distributive Law The distributive law for multiplication as follows: A(B+C) = AB + AC The distributive law for addition is as follows A+(B.C) = (A+B)(A+C) Basic Theorems of Boolean Algebra Basic Theorems of Boolean Algebra OR Laws AND Laws Inversion Law  Theorem 1(a) Proof X+X=X Solution X+X = (X + X ). 1 X.1=1 =(X + X)(X + X’) X + X’=1 =X + XX’ Dist X + YZ= (X+Y)(X+Z) =X + 0 X.X’=0 =X  Theorem 1(b) Prove X.X = X Solution: X.X = XX + 0 X + 0 =X =XX + XX’ XX’= 0 =X(X + X’) =X(1) X + X’ =1 =X  Duality Principle A Boolean equation remains valid if we take the dual of the expressions on both sides of the equals sign Dual of expression it means, – Interchange 1’s with 0’s (and Vice-versa) – Interchange AND (.) with OR (+) (and Vice-versa)  DeMorgan’s Law Theorem 1: NAND = Bubbled OR Complement of product is equal to addition of the compliments. Theorem 2: NOR = Bubbled AND Complement of sum is equal to product of the compliments.  Truth Tables for DeMorgan’s Example Get the logic function from the following truth table and implement it using basic logic gates (AND, OR, NOT) Simplification of the logic function A´B´ + A´B + AB´  Solution: A´(B´ + B) + AB´ A’(1) + AB´ (A’ + A)(A’ + B’) Hint A+AB Dist 1 (A’ + B’) (AB)’ DeMorganLaw (1 NAND Gate only) From 7 gates using simplification rule can be optimized to 1 gate  Home Task: Simplify the following Expressions Find the dual of the following expression 1. A + AB = A 2. A + A’B = A + B 3. A + A’ = 1 4. (A + B)(A + C) = A + BC Home Task: Simplify the following Expressions Prove the following binary expressions ( Using Postulates) 1. A + AB = A 2. (A + B)(A + C) = A + BC 3. AB + ABC + AB’ = A Gate Level Minimization  Introduction – The Map Method K map provides a pictorial method of grouping together expressions with common factors and therefore eliminating a truth table. unwanted variables. The K map can also be described as a special arrangement of  Choice of Blocks We can simplify function by using larger blocks –Do we really need all blocks? –Can we leave some out to further simplify expression? Function needs to contain special type of blocks –They are called Essential Prime Implicants Need to define new terms –Implicant –Prime implicant –Essential prime implicant Terminology Procedure for Simplifying Boolean Functions 1.Generate all PIs of the function. 2.Include all essential PIs. 4.The resulting simplified function is the logical OR of the product terms selected above. Examples to illustrate terms  2 variable map example F = m3 F = m1 + m2 + m3  Two Variable Map Consider the following map. The function plotted is: Z = f(A,B) = A + AB 3-variable K Map Example : 3-variable K Map (Cont..) Example : 3-variable K Map Another Example : 3-variable K Map F = yz + xz’ 3-variable K Map Combinational Logic  Arithmetic circuits An arithmetic circuit is a combinational circuit that performs arithmetic operations such as addition, subtraction, multiplication and division with binary numbers or with decimal numbers in a binary code. A combinational circuit that performs the addition of two bits is called a “Half Adder”.  Half adder It is required to design a combinational circuit that adds two binary numbers and produce the output in the form of two bits sum and carry Solution 1- We need to determine the inputs and output of the system and give letters for all of them our system has two inputs (X, Y) and two outputs (S, C)  Half adder 2-Derive the truth table according to the given relation between outputs and inputs – In the half adder block the output equals the sum of two binary inputs  Half adder (cont.) Obtain the simplified Boolean functions for each output as a function of the input variables using K- map Draw the logic diagram  Full Adder It is required to add three binary numbers Solution 1. From the specifications of the circuit, determine the required number of inputs and outputs and assign a letter (symbol) to each.  Full Adder (cont.) 2.Derive the truth table according to the given relation between outputs and inputs  Full Adder (cont.) 3- Draw the logic diagram Half ubtractor unc on Table Half ubtractor Circuit  Multiplexer Also called Data selector A digital circuit which selects one of the n data inputs and route it to the single output. Select lines (n) and Input lines are (2n) 4: 1 Multiplexer Data inputs are 4 (I0 - I3) Select input are 2