第3章组合逻辑电路设计精选文档.ppt

第3章组合逻辑电路设计本讲稿第一页，共六十九页2023/4/112习题习题完成下列练习完成下列练习,其中标为红色的要用其中标为红色的要用Multisim完成完成:52,54,55,56,58,62.（第（第5章）章）3,4,5,28,29,30.第第3 3章章 组合逻辑电路设计（续）组合逻辑电路设计（续）本讲稿第二页，共六十九页Chapter 3-Part 1 3OverviewPart 1 Design ProcedureStepsSpecificationFormulationOptimizationTechnology MappingBeginning Hierarchical DesignTechnology Mapping-AND,OR,and NOT to NAND or NORVerificationManualSimulation本讲稿第三页，共六十九页Chapter 3-Part 1 4Overview(continued)Part 2 Combinational LogicFunctions and functional blocksRudimentary logic functionsDecoding using DecodersImplementing Combinational Functions with DecodersEncoding using EncodersSelecting using MultiplexersImplementing Combinational Functions with Multiplexers本讲稿第四页，共六十九页Chapter 3-Part 1 5Combinational CircuitsA combinational logic circuit has:A set of m Boolean inputs,A set of n Boolean outputs,andn switching functions,each mapping the 2m input combinations to an output such that the current output depends only on the current input valuesA block diagram:m Boolean Inputsn Boolean OutputsCombinatorialLogic Circuit本讲稿第五页，共六十九页Chapter 3-Part 1 6Design Procedure1.SpecificationWrite a specification for the circuit if one is not already available2.FormulationDerive a truth table or initial Boolean equations that define the required relationships between the inputs and outputs,if not in the specificationApply hierarchical design if appropriate3.OptimizationApply 2-level and multiple-level optimizationDraw a logic diagram or provide a netlist for the resulting circuit using ANDs,ORs,and inverters本讲稿第六页，共六十九页Chapter 3-Part 1 7Design Procedure4.Technology MappingMap the logic diagram or netlist to the implementation technology selected5.VerificationVerify the correctness of the final design manually or using simulation 本讲稿第七页，共六十九页Chapter 3-Part 1 8Design Example1.Specification BCD to Excess-3 code converterTransforms BCD code for the decimal digits to Excess-3 code for the decimal digitsBCD code words for digits 0 through 9:4-bit patterns 0000 to 1001,respectivelyExcess-3 code words for digits 0 through 9:4-bit patterns consisting of 3(binary 0011)added to each BCD code wordImplementation:multiple-level circuitNAND gates(including inverters)本讲稿第八页，共六十九页Chapter 3-Part 1 9Design Example(continued)2.FormulationConversion of 4-bit codes can be most easily formulated by a truth tableVariables-BCD:A,B,C,DVariables-Excess-3 W,X,Y,ZDont Cares-BCD 1010 to 1111本讲稿第九页，共六十九页Chapter 3-Part 1 10Design Example(continued)3.Optimizationa.2-level usingK-mapsW=A+BC+BDX=C+D+BY=CD+Z=BCDA01324576121315148911101111XXXXXX1BCDA01324576121315148911101111XXXXXX1BCDA01324576121315148911101111XXXXXX1BCDA0132457612131514891110111XXXXXX11wzyxBCDBCDD本讲稿第十页，共六十九页Chapter 3-Part 1 11Design Example(continued)3.Optimization(continued)b.Multiple-level using transformationsW=A+BC+BDX=C+D+BY=CD+Z=G=7+10+6+0=23Perform extraction,finding factor:T1=C+DW=A+BT1 X=T1+BY=CD+Z=G=2+1+4+7+6+0=19BCDBCDDBCDCDD本讲稿第十一页，共六十九页Chapter 3-Part 1 12Design Example(continued)3.Optimization(continued)b.Multiple-level using transformationsT1=C+DW=A+BT1 X =T1+BY =CD+Z =G=19An additional extraction not shown in the text since it uses a Boolean transformation:(=C+D=):W=A+BT1X=T1+B Y=CD+Z=G=2+1+4+6+4+0=16!BCDCDDBT1DT1CDT1本讲稿第十二页，共六十九页Chapter 3-Part 1 13Design Example(continued)4.Technology Mapping Mapping with a library containing inverters and 2-input NAND,2-input NOR,and 2-2 AOI gates ABCDWXYZ本讲稿第十三页，共六十九页Chapter 3-Part 1 14Beginning Hierarchical DesignTo control the complexity of the function mapping inputs to outputs:Decompose the function into smaller pieces called blocksDecompose each blocks function into smaller blocks,repeating as necessary until all blocks are small enoughAny block not decomposed is called a primitive blockThe collection of all blocks including the decomposed ones is a hierarchyExample:9-input parity tree(see next slide)Top Level:9 inputs,one output2nd Level:Four 3-bit odd parity trees in two levels3rd Level:Two 2-bit exclusive-OR functionsPrimitives:Four 2-input NAND gatesDesign requires 4 X 2 X 4=32 2-input NAND gates本讲稿第十四页，共六十九页Chapter 3-Part 1 15Hierarchy for Parity Tree ExampleBOX0X1X2X3X4X5X6X7X8ZO9-Inputoddfunction(a)Symbol for circuit3-InputoddfunctionA0A1A2BO3-InputoddfunctionA0A1A2BO3-InputoddfunctionA0A1A2BO3-InputoddfunctionA0A1A2X0X1X2X3X4X5X6X7X8ZO(b)Circuit as interconnected 3-input odd function blocksBOA0A1A2(c)3-input odd function circuit as interconnected exclusive-OR blocks(d)Exclusive-OR block as interconnected NANDs本讲稿第十五页，共六十九页Chapter 3-Part 1 16Reusable FunctionsWhenever possible,we try to decompose a complex design into common,reusable function blocksThese blocks areverified and well-documentedplaced in libraries for future use本讲稿第十六页，共六十九页Chapter 3-Part 1 17Top-Down versus Bottom-UpA top-down design proceeds from an abstract,high-level specification to a more and more detailed design by decomposition and successive refinement A bottom-up design starts with detailed primitive blocks and combines them into larger and more complex functional blocksDesign usually proceeds top-down to known building blocks ranging from complete CPUs to primitive logic gates or electronic components.Much of the material in this chapter is devoted to learning about combinational blocks used in top-down design.本讲稿第十七页，共六十九页Chapter 3-Part 1 18Technology MappingMapping ProceduresTo NAND gatesTo NOR gatesMapping to multiple types of logic blocks in covered in the reading supplement:Advanced Technology Mapping.本讲稿第十八页，共六十九页Chapter 3-Part 1 19Mapping to NAND gatesAssumptions:Gate loading and delay are ignoredCell library contains an inverter and n-input NAND gates,n=2,3,An AND,OR,inverter schematic for the circuit is availableThe mapping is accomplished by:Replacing AND and OR symbols,Pushing inverters through circuit fan-out points,andCanceling inverter pairs本讲稿第十九页，共六十九页Chapter 3-Part 1 20NAND Mapping Algorithm1.Replace ANDs and ORs:2.Repeat the following pair of actions until there is at most one inverter between:a.A circuit input or driving NAND gate output,andb.The attached NAND gate inputs.本讲稿第二十页，共六十九页Chapter 3-Part 1 21NAND Mapping Example本讲稿第二十一页，共六十九页Chapter 3-Part 1 22Mapping to NOR gatesAssumptions:Gate loading and delay are ignoredCell library contains an inverter and n-input NOR gates,n=2,3,An AND,OR,inverter schematic for the circuit is availableThe mapping is accomplished by:Replacing AND and OR symbols,Pushing inverters through circuit fan-out points,andCanceling inverter pairs本讲稿第二十二页，共六十九页Chapter 3-Part 1 23NOR Mapping Algorithm1.Replace ANDs and ORs:2.Repeat the following pair of actions until there is at most one inverter between:a.A circuit input or driving NAND gate output,andb.The attached NAND gate inputs.本讲稿第二十三页，共六十九页Chapter 3-Part 1 24NOR Mapping ExampleABCDEF(c)FABXCDE(b)ABCDEF(a)231本讲稿第二十四页，共六十九页Chapter 3-Part 1 25Verification-show that the final circuit designed implements the original specificationSimple specifications are:truth tablesBoolean equationsHDL codeIf the above result from formulation and are not the original specification,it is critical that the formulation process be flawless for the verification to be valid!Verification本讲稿第二十五页，共六十九页Chapter 3-Part 1 26Basic Verification MethodsManual Logic AnalysisFind the truth table or Boolean equations for the final circuitCompare the final circuit truth table with the specified truth table,orShow that the Boolean equations for the final circuit are equal to the specified Boolean equationsSimulationSimulate the final circuit(or its netlist,possibly written as an HDL)and the specified truth table,equations,or HDL description using test input values that fully validate correctness.The obvious test for a combinational circuit is application of all possible“care”input combinations from the specification本讲稿第二十六页，共六十九页Chapter 3-Part 1 27 Verification Example:Manual AnalysisBCD-to-Excess 3 Code ConverterFind the SOP Boolean equations from the final circuit.Find the truth table from these equationsCompare to the formulation truth tableFinding the Boolean Equations:T1=C+D=C+DW=A(T1 B)=A+B T1X =(T1 B)(B )=T1+B Y =C +D=CD+DCDCBCDCD本讲稿第二十七页，共六十九页Chapter 3-Part 1 28Input BCD A B C D Output Excess-3 WXYZ 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 Verification Example:Manual AnalysisFind the circuit truth table from the equations and compare to specification truth table:The tables match!Input BCD A B C D Output Excess-3 WXYZ 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 本讲稿第二十八页，共六十九页Chapter 3-Part 1 29Verification Example:SimulationSimulation procedure:Use a schematic editor or text editor to enter a gate level representation of the final circuitUse a waveform editor or text editor to enter a test consisting of a sequence of input combinations to be applied to the circuitThis test should guarantee the correctness of the circuit if the simulated responses to it are correctShort of applying all possible“care”input combinations,generation of such a test can be difficult本讲稿第二十九页，共六十九页Chapter 3-Part 1 30Verification Example:SimulationEnter BCD-to-Excess-3 Code Converter Circuit SchematicAOI symbolnot available本讲稿第三十页，共六十九页Chapter 3-Part 1 31Verification Example:SimulationEnter waveform that applies all possible input combinations:Are all BCD input combinations present?(Low is a 0 and high is a one)本讲稿第三十一页，共六十九页Chapter 3-Part 1 32Verification Example:SimulationRun the simulation of the circuit for 120 nsDo the simulation output combinations match the original truth table?本讲稿第三十二页，共六十九页Chapter 3-Part 1 33Terms of UseAll(or portions)of this material 2008 by Pearson Education,Inc.Permission is given to incorporate this material or adaptations thereof into classroom presentations and handouts to instructors in courses adopting the latest edition of Logic and Computer Design Fundamentals as the course textbook.These materials or adaptations thereof are not to be sold or otherwise offered for consideration.This Terms of Use slide or page is to be included within the original materials or any adaptations thereof.本讲稿第三十三页，共六十九页Chapter 3-Part 1 34Design Example1.Specification BCD to Excess-3 code converterTransforms BCD code for the decimal digits to Excess-3 code for the decimal digitsBCD code words for digits 0 through 9:4-bit patterns 0000 to 1001,respectivelyExcess-3 code words for digits 0 through 9:4-bit patterns consisting of 3(binary 0011)added to each BCD code wordImplementation:multiple-level circuitNAND gates(including inverters)本讲稿第三十四页，共六十九页2023/4/11351.功能描述功能描述(specification)：如果没有现成的描述，则先要分析：如果没有现成的描述，则先要分析问题，得到一个符合要求的电路功能描述。问题，得到一个符合要求的电路功能描述。2.形式化形式化(formulation)：根据功能描述推导出真值表或初始的：根据功能描述推导出真值表或初始的布尔表达式，从而获得输入端与输出端的逻辑关系。布尔表达式，从而获得输入端与输出端的逻辑关系。3.优化优化(opimization)：采用两级或多级优化。画出逻辑图或提：采用两级或多级优化。画出逻辑图或提供一个目标电路的网表，目标电路由与门、或门和反相器组成。供一个目标电路的网表，目标电路由与门、或门和反相器组成。4.工艺映射工艺映射(technology mapping)：把逻辑图或网表转化成：把逻辑图或网表转化成可以用工艺实现的新逻辑图或网表。可以用工艺实现的新逻辑图或网表。5.验证验证(verification)：验证最后设计的正确性。：验证最后设计的正确性。3.1 3.1 设计流程设计流程本讲稿第三十五页，共六十九页2023/4/1136例例3-1 3-1 设计一个将设计一个将BCDBCD码转换成余码转换成余3 3码的转换器码的转换器 3.1 3.1 设计流程（续）设计流程（续）功能描述功能描述：一个十进制数的余3码是在此十进制数加3的二进制组合。例如，十进制数5的余3码，是5+3=8的二进制组合：1000。每个BCD码都有四位，从最高位到最低位，分别标记为A、B、C、D。每个余3码也有四位，按最高位到最低位标记，分别是W、X、Y、Z。形式化形式化：将一个BCD码加上0011（3）即可很容易地得到相应的余3码。非有效BCD码，可以假设不存在。所以，我们不用关心这些输入组合的余3码的二进制编码，将它们看做无关项。本讲稿第三十六页，共六十九页2023/4/1137初步优化：初步优化：3.1 3.1 设计流程（续）设计流程（续）本讲稿第三十七页，共六十九页2023/4/1138第二步优化：第二步优化：考虑到这四个输出表达式之间的共同子项考虑到这四个输出表达式之间的共同子项 3.1 3.1 设计流程（续）设计流程（续）本讲稿第三十八页，共六十九页2023/4/1139例例3-2 3-2 设计一个将设计一个将BCDBCD码转换成七段码的译码器码转换成七段码的译码器3.1 3.1 设计流程（续）设计流程（续）形式化：形式化：本电路的真值表本电路的真值表功能描述：功能描述：BCDBCD码码-七段码译码器（七段码译码器（BCD-to-seven-segmentBCD-to-seven-segment）是一个输入为十进制数的）是一个输入为十进制数的BCDBCD码，输出编码可以驱动数码管显示此十进制数字的组合电路。译码器的七个输出码，输出编码可以驱动数码管显示此十进制数字的组合电路。译码器的七个输出端（端（a a，b b，c c，d d，e e，f f，g g）选择需要显示的数码管的相关段）选择需要显示的数码管的相关段 本讲稿第三十九页，共六十九页2023/4/1140优化：优化：单独实现这七个函数需要单独实现这七个函数需要2727个与门和个与门和7 7个或门。然而，通过共用个或门。然而，通过共用表达式中存在的六个乘积项，可将与门的数量减少到表达式中存在的六个乘积项，可将与门的数量减少到1414。3.1 3.1 设计流程（续）设计流程（续）本讲稿第四十页，共六十九页2023/4/11413.2 3.2 开始分层设计开始分层设计分层设计：分层设计：一种一种“分而治之分而治之”的方法的方法例例3-3 3-3 设计一个设计一个4 4位比较器位比较器功能描述功能描述：比较器是一个比较两个二进制码以判定两者是否相等的电路。这种特殊的电路输入端包括两：比较器是一个比较两个二进制码以判定两者是否相等的电路。这种特殊的电路输入端包括两个矢量：个矢量：A A（3:03:0）和）和B(3:0)B(3:0)。矢量。矢量A A有四位，有四位，A A（3 3）、）、A A（2 2）、）、A A（1 1）和）和A A（0 0），其中），其中A A（3 3）是最高）是最高级，向量级，向量B B和向量和向量A A一样有相同的特性。电路的输出是一个一样有相同的特性。电路的输出是一个1 1位的变量位的变量E E，如果向量，如果向量A A和向量和向量B B相等则输出相等则输出E E等于等于1 1；如果向量；如果向量A A和向量和向量B B不相等则输出不相等则输出E E等于等于0 0。形式化形式化：由于本电路的规模较大，不宜采用真值表来形式化。：由于本电路的规模较大，不宜采用真值表来形式化。本讲稿第四十一页，共六十九页2023/4/1142优化优化：MX电路可以用下面的等式描述。输出输出E E的等式的等式：3.2 3.2 开始分层设计（续）开始分层设计（续）本讲稿第四十二页，共六十九页2023/4/11433.2 3.2 开始分层设计（续）开始分层设计（续）分层设计可以使复杂电路的表示变得简单分层设计可以使复杂电路的表示变得简单一些更复杂的结构也可被预定义为基本模块，用符号而不是电路图来表示一些更复杂的结构也可被预定义为基本模块，用符号而不是电路图来表示在分层设计是中，模块可重复使用在分层设计是中，模块可重复使用 本讲稿第四十三页，共六十九页2023/4/11443.3 3.3 工艺映射工艺映射实现技术实现技术本讲稿第四十四页，共六十九页2023/4/1145例例3-4 3-4 与非门的实现与非门的实现3.3 3.3 工艺映射（续）工艺映射（续）1 1、用与非门（或非门）和反相器替换原电路中的与门和或门，形成新的等效电路、用与非门（或非门）和反相器替换原电路中的与门和或门，形成新的等效电路 本讲稿第四十五页，共六十九页2023/4/11462 2、消除反相器对、消除反相器对 3.3.不改变逻辑函数，将所有在电不改变逻辑函数，将所有在电路的输入端或者驱动与非门电路的路的输入端或者驱动与非门电路的输出端和驱动与非门电路的输入端输出端和驱动与非门电路的输入端之间的反相器之间的反相器“推推”向驱动与非门向驱动与非门电路的每个输入端。在这个步骤中，电路的每个输入端。在这个步骤中，尽可能地消除反相器对。尽可能地消除反相器对。3.3 3.3 工艺映射（续）工艺映射（续）本讲稿第四十六页，共六十九页2023/4/1147例例3-5 3-5 或非门的实现或非门的实现3.3 3.3 工艺映射（续）工艺映射（续）本讲稿第四十七页，共六十九页2023/4/1148门个数：门个数：在例在例3-43-4中最终电路的门输入个数为中最终电路的门输入个数为1212，而在例，而在例3-53-5中门输入个个数为中门输入个个数为1414，所，所以与非门的开销较少。以与非门的开销较少。级数：级数：与非门的实现电路中门的最大连接级数为与非门的实现电路中门的最大连接级数为3 3，而或非门实现电路中的最大连接级数，而或非门实现电路中的最大连接级数为为5 5。假设门电路的延迟是一样的，信号从输入到输出，门级数较少的与非门电路的最大延。假设门电路的延迟是一样的，信号从输入到输出，门级数较少的与非门电路的最大延迟是或非门的迟是或非门的0.60.6倍。倍。所以，对于本例，所以，对于本例，与非门电路无论在门输入开销还是信号延迟上都要比或非门电路要更与非门电路无论在门输入开销还是信号延迟上都要比或非门电路要更好。好。实现对比实现对比3.3 3.3 工艺映射（续）工艺映射（续）本讲稿第四十八页，共六十九页Chapter 3 493.5 3.5 组合函数模块组合函数模块l在数字设计中，我们考虑有用的功能；l每个功能对应的组合电路实现被称为功能模块；l过去，功能模块制造成小规模（SSI）、中规模（MSI）和大规模集成（LSI）电路；l现在，功能模块经常集成在超大规模集成（VLSI）电路中；l采用分层设计方法，我们通常可以重复使用这些功能模块构造电路。本讲稿第四十九页，共六十九页Chapter 3 503.6 3.6 基本逻辑函数基本逻辑函数l定值、传递、取反及使能是最基本的组合函数3.6.1 3.6.1 定值、传输和取反定值、传输和取反l单变量X存在四个不同的1位函数XF=0F=XF=F=10100011011X本讲稿第五十页，共六十九页Chapter 3 513.6.2 3.6.2 多位函数多位函数l多位函数往往是单位函数的向量，如下例:l加粗线用来表示总线；l在图(b)中，F=(F3,F2,F1,F0)是一条总线；l总线可以拆分成单条线，每条线表示一位，如图(b)；l位的子集可以从总线中分离开来，如图(c)；l位的子集如果不连续时，可以如图(d)所示标注。F(d)0F31F2F1AF0(a)01A1234F0(b)42:1F(2:1)2F(c)43,1:0F(3),F(1:0)3AA本讲稿第五十一页，共六十九页Chapter 3 523.6.3 3.6.3 使能使能l使能允许信号从输入传递至输出。l当模块不使能时，输入不能传递到输出，输出固定为一个值。这个值可以是高阻态（Hi-Z）、0或1。本讲稿第五十二页，共六十九页2023/4/11533.7 3.7 译码器译码器l 译码器（decoder）是一种多输入、多输出电路，它将输入编码转换为输出编码。l 输入码字到输出码字之间存在一对一的映射关系。l 最常用的输入编码是n位二进制编码，最常用的输出编码是m中取1码。通常有mn。l 译码器电路的一般结构如右图。使能输入（如果有的话）必须有效，才能允许译码器实现正常的映射功能；否则，译码器将所有的输入码字都映射为单一的无效的输出码字（全0或全1）。本讲稿第五十三页，共六十九页2023/4/11543.7 3.7 译码器译码器l 输入为n位二进制编码，输出为2n中取1码，是最常用的一种译码器。l n位输入编码不一定代表0到2n-1个整数，可表示任意信息。l 有效的输入编码数不一定有2n个，如十进制译码器。本讲稿第五十四页，共六十九页2023/4/1155 3-8 3-8译码器译码器74x13874x138l 74x138是商用MSI 3-8译码器，输出为低电平有效。欲使选择的输出有效，必须令所有的使能信号（G1、G2A_L、G2B_