IE7ReleasedMachineStructuresLecture15组合逻辑电路的表示组合逻辑电路的表示www.microsoft.com/ieThisweek,aftermorethan3yearssincethelastmajorupdate,MicrosoftfinallyreleasesthenextgenerationoftheirInternetExplorerwebbrowser复习复习状态单元的作用状态单元的作用:构建存储（构建存储（Buildmemories）控制其他状态单元与组合逻辑间的信息流动控制其他状态单元与组合逻辑间的信息流动用用D型翻转器（型翻转器（D-flip-flops）构建寄存器）构建寄存器时钟定义时钟定义D型翻转器何时改变型翻转器何时改变建立和保持（建立和保持（SetupandHold）时间重要）时间重要为了构建更快的时钟，可将长延时的工作流水化为了构建更快的时钟，可将长延时的工作流水化有限状态机非常有用有限状态机非常有用表达状态和变化表达状态和变化组合逻辑组合逻辑FSMs有状态和变化有状态和变化如何从一个状态变化为另一状态如何从一个状态变化为另一状态?答案答案:组合逻辑组合逻辑真值表真值表:唯一定义组合逻辑函数唯一定义组合逻辑函数0关于组合逻辑，需要学些什么关于组合逻辑，需要学些什么?如何设计如何设计:给定定义给定定义将其分解为可管理的大小来实现将其分解为可管理的大小来实现如何分析如何分析:延时多少延时多少,价格多少价格多少,能耗多少能耗多少具体对我们具体对我们:用逻辑门电路来实现用逻辑门电路来实现（TT）真值表）真值表例例#1:1iffone(notboth)a,b=1a b y000011101110（TT）真值表例）真值表例#2:2位加法位加法多少行多少行?TT例例#3:32位无符号数加法位无符号数加法多少行多少行?TT真值表例真值表例#3:3-输入多数（输入多数（majority）电路）电路逻辑门逻辑门(1/2)Andvs.OrANDGate（与门）（与门）CAB符号符号定义定义AND逻辑门逻辑门(2/2)2输入门扩展为输入门扩展为n输入输入N输入输入XOR是唯一一个是唯一一个扩展方法不明显的扩展方法不明显的非常简单非常简单:XOR=1当当且仅当其输入中且仅当其输入中1的个的个数为奇数数为奇数真值表真值表门门(如多数电路如多数电路)真值表真值表门电路门电路(如如,有限状态机电路有限状态机电路)PSInputNSOutput000000001010010000011100100000101001或者等价地或者等价地布尔代数布尔代数BooleanAlgebraGeorgeBoole,19世纪数学家世纪数学家开发了涉及逻辑的数学系统开发了涉及逻辑的数学系统(代数代数)后来称为后来称为“布尔代数布尔代数”基本函数基本函数:AND,OR和和NOT布尔代数的重要意义在于：布尔代数的重要意义在于：由由AND,OR和和NOT构建的门电路和布尔代数的代数式间存构建的门电路和布尔代数的代数式间存在一一对应在一一对应+即即OR,即即AND,x即即NOT布尔代数布尔代数(例例,“多数多数”函数函数)y=ab+ac+bcy=ab+ac+bc布尔代数布尔代数(如如,有限状态机有限状态机)PSInputNSOutput000000001010010000011100100000101001或者等价地或者等价地y=PS1PS0INPUT布尔代数布尔代数:电路化简电路化简布尔代数也可用于布尔代数也可用于电路电路证明：证明：如电路如电路X=电路电路Y?可用布尔代数证明可用布尔代数证明!布尔代数运算法则布尔代数运算法则布尔代数化简实例布尔代数化简实例组合逻辑的三种表示组合逻辑的三种表示组合逻辑表示转换组合逻辑表示转换布尔表达式布尔表达式转真值表转真值表:对右边所有变量尝试可能的值，穷对右边所有变量尝试可能的值，穷举得到真值表举得到真值表转逻辑门转逻辑门:用与或非门（用与或非门（AND-gate/OR-gate/Inverter）替换布尔代数中的与或非）替换布尔代数中的与或非AND/OR/NOT运算运算门电路图门电路图转真值表转真值表:用所有可能的输入组合，来对电路用所有可能的输入组合，来对电路进行测试，得到输出值进行测试，得到输出值转布尔表达式转布尔表达式:逆变换逆变换真值表转布尔表达式真值表转布尔表达式?正则表示正则表示(1/2)乘积之和乘积之和(ORsofANDs)正则形式正则形式(2/2)课堂测验课堂测验A.(a+b)(a+b)=bB.N-inputgatescanbethoughtofcascaded2-inputgates.I.e.,(abcde)=a(bc(de)whereisoneofAND,OR,XOR,NANDC.YoucanuseNOR(s)withcleverwiringtosimulateAND,OR,&NOTABC1:FFF2:FFT3:FTF4:FTT5:TFF6:TFT7:TTF8:TTTA.(a+b)(a+b)=aa+ab+ba+bb=0+b(a+a)+b=b+b=bTRUEB.(nextslide)C.YoucanuseNOR(s)withcleverwiringtosimulateAND,OR,&NOT.NOR(a,a)=a+a=aa=aUsingthisNOT,canwemakeaNORanOR?AnAnd?TRUEPeerInstructionAnswerA.(a+b)(a+b)=bB.N-inputgatescanbethoughtofcascaded2-inputgates.I.e.,(abcde)=a(bc(de)whereisoneofAND,OR,XOR,NANDC.YoucanuseNOR(s)withcleverwiringtosimulateAND,OR,&NOTABC1:FFF2:FFT3:FTF4:FTT5:TFF6:TFT7:TTF8:TTTA.B.N-inputgatescanbethoughtofcascaded2-inputgates.I.e.,(abcde)=a(bc(de)whereisoneofAND,OR,XOR,NANDFALSELetsconfirm!CORRECT3-inputXYZ|AND|OR|XOR|NAND000|0|0|0|1001|0|1|1|1010|0|1|1|1011|0|1|0|1100|0|1|1|1101|0|1|0|1110|0|1|0|1111|1|1|1|0CORRECT2-inputYZ|AND|OR|XOR|NAND00|0|0|0|101|0|1|1|110|0|1|1|111|1|1|0|000010111011101010110010001001111PeerInstructionAnswer(B)“小结小结”有限状态机（有限状态机（FSM）非常有用非常有用后续课程还要学后续课程还要学Usethistableandtechniqueswelearnedtotransformfrom1toanother