DCF-Module 2 PDF - Boolean Algebra, Logic Gates, and Combinational Circuits

MODULE 2 BOOLEAN ALGEBRA , LOGIC GATES AND COMBINATIONAL CIRCUITS Important topics 1. Basic Theorems and Definitions. 2. SOP ,POS and canonical forms. 3.Basic gates and universal gates with figure and truth table. 4.Implement NOT,AND,OR using NOR, NAND gates. 5.Solve K map with examples 6.Design...

MODULE 2 BOOLEAN ALGEBRA , LOGIC GATES AND COMBINATIONAL CIRCUITS Important topics 1. Basic Theorems and Definitions. 2. SOP ,POS and canonical forms. 3.Basic gates and universal gates with figure and truth table. 4.Implement NOT,AND,OR using NOR, NAND gates. 5.Solve K map with examples 6.Design logic diagrams. 1.Axiomatic definitions of Boolean Algebra In 1854, George Boole developed an algebraic system now called Boolean algebra. For the formal definition of Boolean algebra, we shall employ the postulates formulated by E. V. Huntington in 1904. Definition Boolean Algebra is used to analyse and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. It is an algebraic structure defined on a set of at least two elements B = {0, 1}, together with three binary operators denoted by ( “+”, “.”, “-” ) that satisfies the following basic identities. OR AND operator operator →NOT operator In addition to above we have Absorption law OR of a variable with the AND of that variable and another variable is equal to that variable itself A+(A.B)=A AND of a variable with the OR of that variable and another variable is equal to that variable itself A.(A+B)=A Idempotence law AND of a variable itself is equal to that variable only A.A=A OR of a variable itself is equal to that variable only A +A=A Redundant Literal Rule (RLR) A+A’B=A+B →( OR of a variable with the AND of the compliment of that variable with another variable , is equal to OR of two variables) A(A’+B) =AB→ (AND of a variable with the OR of the compliment of that variable with another variable , is equal to AND of two variables) Consensus Theorem AB + A’C + BC = AB + A’C (A + B) + (A’ + C) + (B + C) = (A + B) + (A’ + C) 2.Two-valued Boolean Algebra A two‐valued Boolean algebra is defined on a set of two elements, B = {0, 1}, with rules for binary operators + ,. , - (OR,AND &NOT), with truth table as below. 3.Basic Theorems and Definitions 4.Boolean Functions, Simplifications of Boolean functions using axioms and theorems. Every Boolean expression must be simplified to a simple form as possible in order to reduce hardware cost and complexity Techniques for these reductions are Multiply all variables necessary to remove brackets Look for identical terms Look for a variable and its negation in the same term, this term can be dropped. Boolean algebra Simplification Table Examples: 1. Expression f(A,B)=A.(A+B) reduced to A  2.Expression f(A,B,C)=(A+B)(A+C) reduced to A+B.C 3.Expression f(A,B,C)=AB(B’C+AC) reduced to ABC 5.Standard forms-POS, SOP and Canonical Form of Boolean Functions. To implement a Boolean function with lesser number of gates we have to minimize literals(variables)and the number of terms. Boolean variables are either in complimented form or in uncomplimented form and the terms are arranged in one of the two standard forms of Boolean functions 1. Sum of Product form (SOP) 2. Product of Sum form (POS) Sum of Product (SOP) Form In this SOP form of Boolean function representation, the variables are operated by AND (product) to form a product term and all these product terms are ORed (summed or added) together to get the final function. A sum-of-products form can be formed by adding (or summing) two or more product terms using a Boolean addition operation. Here the product terms are defined by using the AND operation and the sum term is defined by using OR operation SOP form can be obtained by Writing an AND term for each input combination, which produces HIGH output. Writing the input variables if the value is 1 , and write the complement of the variable if its value is 0. OR the AND terms to obtain the output function. Ex: Boolean expression f(A,B,C)= A’BC + AB’C + ABC ‘ + ABC By taking binary values expression can be written as →011+101+110+111 In truth table mark 1 corresponding to the terms in the expression. Truth Table A B C Y / OUTPUT 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 F=A’BC+AB'C+ABC’+ABC Canonical SOP If each term in SOP contains all the literals then these are known as canonical(standard) SOP expression Eg. 1:AB’ + A’B→ Canonical form Eg 2:AB’+ABC→ Non Canonical since the literal C is missing in the first term.  To convert an expression from non canonical SOP to Canonical SOP Multiply each SOP by ( X + X’) where X is the missing variable & expand Repeat above steps until all resulting product terms contains all the variable in either complimented or normal form Above Eg.2 Expression can be covert to canonical form by multiplying (C+C’) to first term ie. AB’.(C+C’)+ABC → AB’C+AB’C’+ABC Product of Sums (POS) Form In this POS form, all the variables are ORed, i.e. written as sums to form sum terms.All these sum terms are ANDed (multiplied) together to get the product-of-sum form. This form is exactly opposite to the SOP form. So this can also be said as “Dual of SOP form”.POS form can be obtained by Writing an OR term for each input combination, which produces LOW output. Writing the input variables if the value is 0, and write the complement of the variable if its value is 1. AND the OR terms to obtain the output function. Ex: Boolean expression for function F = (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C) By taking binary values expression can be written as → (0+0+0)(0+0+1)(0+1+0)(1+0+0) In truth table mark 1 corresponding to the terms in the expression. Truth Table A B C Y / OUTPUT 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 F= (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C) Converting POS to canonical POS form ADD by ( X X’) where X is the missing variable Apply rule → A + BC = ( A + B) ( A + C) Repeat above steps until all resulting sum terms contains all the variable in either complimented or normal form Eg. 1:(A+B’).(A’+B)→ Canonical form Eg 2:(A+B’).(A+B+C)→ Non Canonical since the literal C is missing in the first term. Above Eg.2 Expression can be covert to canonical form by multiplying (CC’) to first term ie. :(A+B’)+(C.C’).(A+B+C)→ (A+B’+C)(A+B’+C’)(A+B+C) Example 2: Max term and Min Term Min term(m) or( ∑ ) MAXTERM( M ) or ( П ) Each individual product term in SOP Each individual sum term in POS is is called minterm( m0,m1,m2..) called maxterm(M1,M2,M3….) 0→A’ 0→A 1→A 1→A’ A binary variable may appear in its These are the sum terms which normal form and compliment form contains all the variables in either Consider 2 binary variables , A & B normal form or compliment form combined with an AND operation 2^n different maxterm can be Since each variable may appear in obtained by writing the binary either form, there are four possible equivalent of numbers combinations; A’B’ , A’B , AB’ & AB Each of these four AND terms is called a minterm or standard product 2^n different minterm can be obtained by writing the binary equivalent of numbers KARNAUGH MAP (K MAP) A Karnaugh map or a K-map refers to a pictorial method that is utilized to minimize various Boolean expressions without using the Boolean algebra theorems along with the equation manipulations. A Karnaugh map can be a special version of the truth table. We can easily minimize various expressions that have 2 to 4 variables using a K-map. K-map can easily take two forms, namely, Sum of Product or SOP and Product of Sum or POS In K-map, if the number of variables is three, the number of cells is 23=8, and if the number of variables is four, the number of cells is 24=16. The K-map takes the SOP and POS forms. The K-map grid is filled using 0's(for POS) and 1's(SOP). The K-map is solved by making group. CELL: Smallest unit of a K map. Input variables are cell coordinates and the output variable is cell content PAIR : A group of two adjacent cells in K map. A pair cancel 1 variable in a K map simplification QUAD :A group of four adjacent cells in K map. A quad cancel 2 variables in a K map simplification OCTET: A group of eight adjacent cells in K map. A quad cancel 3 variable in a K map simplification Solving an Expression Using K-Map 1. Select a K-map according to the total number of variables. 2. Identify maxterms or minterms as given in the problem. 3. For SOP, put the 1’s in the blocks of the K-map with respect to the minterms (elsewhere 0’s). 4. For POS, putting 0’s in the blocks of the K-map with respect to the maxterms (elsewhere 1’s) 5. Making rectangular groups that contain the total terms in the power of two, such as 2,4,8.. and trying to cover as many numbers of elements as we can in a single group. 6. From the groups that have been created in step 5, find the product terms and then sum them up for the SOP form. Or find the sum terms and multiply them for POS form 2-Variable K MAP  Number of variables n is 2 and hence 22=4 cells are needed to form 2 variable K map Coordinates of each cell corresponds to a unique combination of two input variables A, B 3Variable K MAP Number of variables n is 3 and hence 23=8 cells are needed to form 3 variable K map Coordinates of each cell corresponds to a unique combination of three input variables A, B Simplification rules through K map Group 0’s with 0’s and 1’s with 1’s Group can overlap each other Group can contains 2n number of cells Group can have only be horizontal or vertical Each group should be as large as possible Opposite grouping or corner grouping is allowed There should be a few groups as possible F(A,B)= Σ 1,2,3 or π 0)  Example 3: F(P,Q,R,S)= Σ 0,2,5,7,8,10,13,15 Ans: SOP→QS+Q’S’ Example 4: F(A,B,C)=π(0,3,6,7) Reduced to (A' + B’) (B’ + C’) (A + B + C) Example 5: 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’)  Don’t Care Conditions The “Don’t Care” conditions allow us to replace the empty cell of a K map to form a grouping of the variables which is larger than that of forming groups without don’t care. While forming groups of cells, we can consider a “Don’t Care” cell as 1 or 0 or we can also ignore that cell. Therefore, the “Don’t Care” condition can help us to form a larger group of cells. A Don’t Care cell can be represented by a cross(X) SOP including don’t care POS including don’t care f = m(1, 5, 6, 11, 12, 13, 14) + d(4) F(A, B, C, D) = M(6, 7, 8, 9) + d(12, 13, 14, 15) Reduced to f = BC' + BD' + A'C'D + AB'CD Reduced to F = (A'+ C)(B' + C')  Refer more examples done in classroom. Basic and universal gates-Representation, truth table, Logic Gates Logic gate is an electronic circuit which makes logic decisions It have only one output and two or more inputs except for the not gate, which has only one input Output signals appears only for certain combinations of input signals Gates do the manipulation of binary information 3 basic logic gates: are OR gate , NOT gate, AND gate Logic gates are the building blocks and are available in the form of various IC families Input and output relationship can be represented in a tabular form in a truth table BASIC GATES NOT GATE / UNIVERSAL GATES,EX-OR, and EX-NOR NAND and NOR gates are called UNIVERSAL GATES, because all other gates can be realised using the NAND and NOR gates. 3 INPUT NOR &NAND NOT GATE AND GATE Output of an AND gate attains state 1 if and only if all the NOT gate has only one input and one inputs are in state 1. output The Boolean expression of AND gate is Y = A.B It performs inversion or complementation It performs logical multiplication HIGH input produce LOW output When any of the inputs are LOW, the output is LOW LOW input produce HIGH output AND gate is composed of two or more inputs and only one Hence output is the compliment of its input output OR GATE ExOR-GATE Output of an OR gate attains state 1 if one or more XOR or Ex-OR gate is a special type of gate. inputs attain state 1. The Boolean expression of the OR gate is Y = A + B, It can be used in the half adder, full adder and read as Y equals A ‘OR’ B. subtractor. It performs logical addition OR gate has two or ,more inputs and one output The exclusive-OR gate is abbreviated as EX-OR HIGH on the output is produced when any of the gate or sometime as X-OR gate. inputs are HIGH Boolean Expression X=A’B+AB’  Ex-NOR GATE XNOR gate is a special type of gate. It can be used in the half adder, full adder and subtractor. The exclusive-NOR gate is abbreviated as EX-NOR gate or sometime as X-NOR gate NAND GATE NOR GATE NAND gate is actually a combination of two NOR gate is actually a combination of two logic logic gates: AND gate followed by NOT gate. gates: OR gate followed by NOT gate. So its output is complement of the output of an So its output is complement of the output of an AND gate. OR gate. This gate can have minimum two inputs, output This gate can have minimum two inputs, output is always one. is always one. By using only NAND gates, we can realize all By using only NOR gates, we can realize all logic logic functions: AND, OR, NOT, X-OR, X- functions: AND, OR, NOT, X-OR, X-NOR, NAND. NOR, NOR. So this gate is also called universal So this gate is also called universal gate. gate  Implement NOT,AND,OR ,Ex-OR, Ex-NOR NAND gates NOT USING NAND OR USING NAND AND USING NAND Ex-OR USING NAND Ex-NOR USING NAND Implement NOT,AND,OR ,Ex-OR, Ex-NOR NOR gates NOT USING NOR OR USING NOR AND USING NOR Design logic diagrams Logic gates are used for implementing any Boolean expression Boolean expressions indicates the types of gate networks, which can be systematically progressing from input to output on the gates Example: Design a circuit for (A+B).C’ Example :2 A’+B.(C+D) Example 3:AB+BCD Example:4 AB’C+DE’FG Questions: Reduce Boolean expression using K map and prepare circuit. 1.F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15) 2.F(A, B, C, D) = Σm(1, 3, 4, 6, 8, 9, 11, 13, 15) + Σd(0, 2, 14) 3. F(A,B,C,D) = ∏(0,1,2,4,5,7,10,15) +d(3,8,9) 4. F(A,B,C,D)=π(3,5,7,8,10,11,12,13)