1、 3.Designing combinational circuits 3.1 Combinational circuits 3.2 Implementing Boolean expressions 3.3 Simplifying logic circuits3.4 MSI combinational logic devices1 3.1 Combinational circuitsA combinational function can be defined by Boolean expression,truth table and circuit diagram.F=AB+CTruth t
2、ableABCFCircuit diagramFor example:2 3.2 Implementing Boolean expressions1.Sum-of-product expressions（1）Product termA term consisting of variables connected with AND operators is a product term.（2）Sum-of-product expressionAn expression with product terms connected by OR operators is a sum-of-product
3、(SOP)expression.For example:F(A,B,C)=AB+AC3 3.2 Implementing Boolean expressions2.Canonical expressions（1）MintermThe product term which contains all the variables(or their complements)is called a minterm.Each minterm can be described by a binary number such that each digit in the number is a 1 if th
4、e variable in the minterm is true,and a 0 if the variable is complemented.The binary number for each minterm is unique.4 3.2 Implementing Boolean expressionsThree-variable Minterm numbering5 3.2 Implementing Boolean expressions（2）Canonical sum-of-product expressionThe expression with minterms connec
5、ted by OR operators is a canonical sum-of-product expression.（3）Conversion into canonical formA canonical sum-of-product expression can be obtained from a non-canonical sum-of-product expression by multiplying each term by(A+A)(B+B)(),where A,B,etc.are variables not in the product term.6 3.2 Impleme
6、nting Boolean expressionsExp1:Expand the expression F(A,B,C)=AB+AC+ABC to the canonical sum-of-product expression.F(A,B,C)=AB+AC+ABC=AB(C+C)+A(B+B)C+ABC=ABC+ABC+ABC+ABC+ABC=ABC+ABC+ABC+ABC 7 3.2 Implementing Boolean expressions2.Product-of-sum expressions（1）Sum termA term consisting of variables(or
7、their complements)connected with OR operators is a sum term.（2）Product-of-sum expressionAn expression with sum terms connected by AND operators is a product-of-sum(POS)expression.For example:F(A,B,C)=(A+B)(A+C)8 3.2 Implementing Boolean expressions（3）MaxtermThe sum term which contains all the variab
8、les(or their complements)is called a maxterm.Each maxterm can be described by a binary number such that each digit in the number is a 0 if the variable in the maxterm is true,and a 1 if the variable is complemented.（4）Canonical product-of-sum expressionThe expression with maxterms connected by OR op
9、erators is a canonical sum-of-product expression.9 3.2 Implementing Boolean expressionsThree-variable Maxterm numbering10 3.3 Simplifying logic circuitsSimplifying an expression usually means reducing the number of variables in each term and reducing the number of terms.1.Simplification2.Algebraic m
10、inimization methodExp2:F(A,B,C)=A+AC+ABC=A(1+C+BC)=AAlgebraic minimization applies Boolean identities and laws to simplify expressions.11 3.3 Simplifying logic circuitsAlgebraic minimization is capable of reducing any expression to its simplest form,however,it relies on the skill of the individual i
11、n applying the appropriate rules.Limitations for algebraic method 12 3.3 Simplifying logic circuits3.Karnaugh map minimization method（1）Karnaugh mapKarnaugh map consists of two-dimensional array squares.Each square corresponds to a minterm.The minterms of adjacent squares,either horizontally or vert
12、ically,have the same variables except only one variable different.Karnaugh map method is a visual minimization method,by which we can identify the terms that can be combined.13 3.3 Simplifying logic circuits3,4 variable Karnaugh map14 3.3 Simplifying logic circuits（2）Mapping functions onto the Karna
13、ugh mapSquares should be marked with 1s for those minterms appear in the function to be minimized.Exp3:Mapping the function expression F(A,B,C)=ABC+ABC+ABC onto a Karnaugh map.15 3.3 Simplifying logic circuits（3）Karnaugh map minimization methodTo the sum-of-product expressions,the basic minimization
14、 steps are:)Mark those squares with a 1 that correspond to the terms in the expression.)Form the 1s into the largest valid groups of 1s.)Read the terms from the map which correspond to the groups(cover the 1s).16 3.3 Simplifying logic circuitsExp4:Minimize the function expression by Karnaugh map:F(A
15、,B,C)=A B C+A B C+A B C F(A,B,C)=A B+A B C Adjacent 1s can be combined into a group corresponding to a single product term,eliminating the different variable.17 3.3 Simplifying logic circuitsExp5:Minimize the function expression by Karnaugh map:F(A,B,C)=A B C+A B C F(A,B,C)=A C Squares on one edge a
16、re also adjacent to those on the opposite edge(top and bottom or left and right).18 3.3 Simplifying logic circuitsLarger groupsThe final minimization term is given by those variables which are common to all the squares in the group.19 3.3 Simplifying logic circuitsTruth table description and the Kar
17、naugh map There is a direct relationship between the squares on a Karnaugh map and the truth table description of the function as both have one entry for each minterm.20 3.3 Simplifying logic circuits4.Incompletely specified functions（1）dont care termThe combinations of input values that cannot occu
18、r or can occur but the output values for them are irrelevant are treated as dont care terms,and marked by X.（2）Incompletely specified functionThe function with dont care term is called incompletely specified function.21 3.3 Simplifying logic circuits（3）Minimizing incompletely specified functionsWe c
19、an take advantage of the dont care terms in minimization.Each X can be considered as 0 or 1 whichever leads to the simplest solution.Exp6:Suppose a logic circuit is designed to generate a 1 when the BCD digit 8 appears.What will the function be?F=A D22 3.4 MSI combinational logic devices1.DecoderA d
20、ecoder is designed to recognize the different patterns that can occur on a set of inputs.One output of the decoder is activated for each of the possible binary patterns that occur on the inputs.Lets take a 3-line-to-8-line decoder 74LS138 as an example:three inputs:A2,A1,A0eight outputs:Y0 Y7enable
21、inputs:S3,S2,S1（1）Function 23 3.4 MSI combinational logic devicesTruth table of a 3-line-to-8-line decoder24 3.4 MSI combinational logic devicesThe enable inputs enable the device and allow its outputs to change with the inputs:)When S11、S2S30，the decoder is enabled，Y0 Y7are determined by A0 A2；)Whe
22、n S10 or S21 or S31，the decoder is disabled，Y0 Y7 will be limited to 1；The outputs of the decoder are active-low,which means that they are normally at a logic 1 and become a logic 0 to indicate activation.An output becomes a 0 when the corresponding input pattern has been applied.25 3.4 MSI combinat
23、ional logic devices（2）Applications Address decoderDecoder can be used in computer interface design to identify addresses of memory modules.Suppose the memory module address to be recognized is 010,then output Y2 is chosen to activate the memory module.Exp6:26 3.4 MSI combinational logic devicesLogic
24、 function generatorAs each output of a decoder implements one minterm,therefore,the decoder can be used to implement a combinational logic function.Exp7:Implement the function F=ABC+ABC+ABC by using a 3-line-to-8-line decoder.Three outputs need to be selected,Y5,Y6 and Y7 which are connected to the
25、inputs of a three-input NAND gate.27 3.4 MSI combinational logic devicesCircuit diagram 28 3.4 MSI combinational logic devices2.Multiplexer(Selector)（1）Function Multiplexer is a logic circuit which allows one of a set of data inputs to be selected and fed into a single output.Lets take a 8-line-to-1
26、-line selector or multiplexer as an example:Model of a multiplexer3 data select inputs:A2,A1,A01 data output:Y8 data inputs:D0 D729 3.4 MSI combinational logic devicesMSI devices 74LS151:8-line-to-1-line multiplexer 74LS153:dual 4-line-to-1-line multiplexer 74LS157:quad 2-line-to-1-line multiplexer
27、30 3.4 MSI combinational logic devices（2）Applications Address decoderExp8:Suppose the memory module address to be recognized is 010.D0 D1 D2 D3 D4 D5D6D7SA2A1A00Y MultiplexerY 0100101To memory Then output Y is 0,which can be used to activate the memory module.Multiplexer can be used as an address de
28、coder.31 3.4 MSI combinational logic devicesLogic function generatorApart from its principle function for selecting one data input to feed to a single output,the multiplexer can be used to implement a sum-of-product expression.If a data input is set to a 1 and the data input is selected by the combi
29、nation of select input values,the Y output will be a 1.Hence by connecting each data input to either a 0 or a 1,depending upon whether the associated minterm is a part of the required function that Y output will implement.32 3.4 MSI combinational logic devicesExp9:Implement the function F=ABC+ABC+AB
30、C by using a 8-line-to-1-line multiplexer.D0 D1 D2 D3 D4 D5D6D7SA2A1A00Y MultiplexerY 01ABCFThree data inputs D2,D4 and D7 are set to a 1,the remaining inputs are set to a 0.33 3.4 MSI combinational logic devices3.Arithmetic circuits（1）AdditionHalf adderThe circuit which can add together two binary
31、digits is called a half adder.It has two inputs A,B and two outputs Sum,Carry.Half adder truth table34 3.4 MSI combinational logic devicesFull adderThe circuit which can add two binary digits together with a carry from a previous addition is called a full adder.Full adder has three inputs A,B Cin an
32、d two outputs Sum,Cout.Full adder truth table35 3.4 MSI combinational logic devicesParallel adderWhen the carry output of each adder is connected to the carry input of the next higher-order adder,we can get a parallel adder.Lets take a 4-bit parallel adder as an example:Circuit arrangement of a 4-bit parallel adder36
