第四章 组合逻辑的分析与设计

1第四章组合逻辑的分析与设计计算机学院 余波Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU63数字逻辑电路按照功能可分为

组合逻辑电路简称组合电路，它由最根本的的逻辑门电路组合而成。 时序逻辑电路简称时序电路，它是由最根本的逻辑门电路加上反响逻辑回路〔输出到输入〕或器件组合而成的电路。组合电路n-inputsm-outputs(仅根据当前输入值决定)组合电路n-inputsm-outputs存储单元下一状态当前状态4 组合逻辑电路特点是：输出值只与当时的输入值有关，即输出唯一地由当时的输入值决定。电路没有记忆功能，输出状态随着输入状态的变化而变化，类似于电阻性电路，如加法器、译码器、编码器、数据选择器等都属于此类。时序逻辑电路特点：与组合电路最本质的区别在于时序电路具有记忆功能。时序电路的特点是：输出不仅取决于当时的输入值，而且还与电路过去的状态有关。它类似于含储能元件的电感或电容的电路，如触发器、锁存器、计数器、移位存放器、储存器等电路都是时序电路的典型器件。5组合电路构成组合电路....x1x2xnymy2y1y3Y1=f1(x1,x2,…,xn)Y2=f2(x1,x2,…,xn)Ym=fm(x1,x2,…,xn)...对一个具有n输入的组合逻辑电路，那么可能有2n种对输入变量的组合，对每一种变量组合，有可能会产生一个二进制输出。6逻辑表达式表达式化简构造真值表逻辑功能分析组合逻辑的分析start逻辑图start逻辑问题画出逻辑图表达式并化简构造真值表分析输入输出组合逻辑的设计7P1=(ABC)’P2=A·P1=A·(ABC)’P3=B·P1=B·(ABC)’P4=C·P1=C·(ABC)’Step1:例1：分析如下逻辑电路的逻辑功能F=(P2+P3+P4)’=(A·(ABC)’+B·(ABC)’+C·(ABC)’)’=((ABC)’(A+B+C))’=ABC+A’B’C’Step2:8Step3:列出真值表Step4:分析逻辑功能：当三个变量相同时输出1。9例2：设计一组合电路，采用2421BCD编码来驱动TIL-312七段显示块。2421BCD编码10ABCDEFGABCDEFG11输入变量对应的最小项数字多输出函数显示2421BCD码12A=∑(1,10)B=∑(11,12)C=∑(8)D=∑(1,10,13)E=∑(1,9,10,11,13,15)F=∑(1,8,9,13)G=∑(0,1,13)A=[(w’z)’(x’yz’)’]’B=[(xy’z’)’(x’yz)’]’C=(wx’y’z’)’D=[(xy’z)’(x’yz’)’(w’z)’]’E=[(x’y)’(z)’]’F=[(wx’y’)’(y’z)’]’G=[(w)(xy’z)’]’A=w’z+x’yz’B=xy’z’+x’yzC=wx’y’z’D=xy’z+x’yz’+w’zE=x’y+zF=wx’y’+y’zG=w’+xy’z13Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU615数字集成电路介绍数字集成电路系列(ICcategory)TTL

低功耗 Lowpower(L) 高速 Highspeed(H)

低功耗肖特基LowpowerSchottky(LS) 肖特基 Schottky(S) 先进低功耗肖特基AdvancedLowpowerSchottky(ALS) 先进肖特基AdvancedSchottky(AS)ECLCMOS16SN74LS00生产者CT:中国TTLSN：德州仪器HD：日立54---军用温度范围〔-55℃～125℃〕74---商用温度范围〔0℃～70℃〕Lowpower(L)Highspeed(H)LowpowerSchottky(LS)Schottky(S)AdvancedLowpowerSchottky(ALS)AdvancedSchottky(AS)集成电路命名规那么〔TTL〕1718SN74LS0019SN5410,SN54LS10,SN54S10SN7410,SN74LS10,SN74S1020SN5427,SN54LS27SN7427,SN74LS2721SN5404,SN54LS04,SN54S04SN7404,SN74LS04,SN74S0422Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU624译码器将N个输入转换成对应的M个输出的过程M≤2N类型全部译码和局部译码；二进制译码、代码译码器、数字显示译码器。Eg: N-2n译码器， eg:3线-8线译码器N-M译码器，M<2n,eg:4线-10线译码器2526Y0=(G’B’A’)’=G+B+AY1=(G’B’A)’=G+B+A’Y2=(G’BA’)’=G+B’+AY3=(G’BA)’=G+B’+A’使能信号2线-4线译码器2774XX139译码器逻辑电路图2874LS139引脚图29Y0’=(C’B’A’)’Y1’=(C’B’A)’Y2’=(C’BA’)’Y3’=(C’BA)’Y4’=(CB’A’)’Y5’=(CB’A)’Y6’=(CBA’)’Y7’=(CBA)’SN74LS138——真值表3线-8线译码器低电平为有效输出30SN74LS13831Y0’=(C’B’A’)’Y1’=(C’B’A)’Y2’=(C’BA’)’Y3’=(C’BA)’Y4’=(CB’A’)’Y5’=(CB’A)’Y6’=(CBA’)’Y7’=(CBA)’译码功能：根据输出引脚哪一条线有效，就可知道具体输入的二进制代码是哪一种组合。=m0’=m1’=m2’=m3’=m4’=m5’=m6’=m7’32由3-8译码器构成的逻辑电路如下图，写出逻辑函数F1，F2.33对二输入变量A0,A1，译码器将得到四个输出Y0,Y1,Y2,Y3，对三输入变量A0,A1,A2，译码器将得到八个输出Y0,Y1,…,Y7，每一个输出Yi对应该输入的最小项。对二输入变量，如：Yi’=0，即输入变量组合A1A0的M进制(M输出)形式为i。用数字形式表示即：Yi

mi可用译码器实现最小项

341)二进制译码器的输出端能提供输入变量的全部最小项；2)任何组合逻辑函数都可以变换为最小项之和的标准式；=>用二进制译码器和门电路可实现任何组合逻辑函数。当译码器输出低电平有效时，多项选择用与非门；译码器输出高电平有效时，多项选择用或门。优点:可减少集成电路的使用数量。35例：用3线-8线译码器74LS138实现下面的逻辑函数：Y1=A’B’+AC+A’C’Y2=A’C+AC’Y3=B’C+BC’36将逻辑函数化为最小项之和的形式：Y1=A’B’+AC+A’C’=A’B’C+A’B’C’+ABC+AB’C+A’BC’+A’B’C’=m1+m0+m7+m5+m2+m0=(m0’m1’m2’m5’m7’)’Y2=A’C+AC’=A’BC+A’B’C+ABC’+AB’C’=m3+m1+m6+m4

=(m1’m3’m4’m6’)’Y3=B’C+BC’=AB’C+A’B’C+ABC’+A’BC’=m5+m1+m6+m2=(m1’m2’m5’m6’)’37当译码器输出低电平有效时，多项选择用与非门；译码器输出高电平有效时，多项选择用或门。思考：其它连接方法？Y1=(m0’m1’m2’m5’m7’)’Y2=(m1’m3’m4’m6’)’Y3=(m1’m2’m5’m6’)’38Y1=A’B’+AC+A’C’=m0+m1+m2+m5+m7

=∑(0,1,2,5,7) =∏(3,4,6)=M3M4M6

=m3’m4’m6’Y2=A’C+AC’=m1+m3+m4+m6 =∑(1,3,4,6) =∏(0,2,5,7) =m0’m2’m5’m7’

Y3=B’C+BC’=m1+m2+m5+m6

=∑(1,2,5,6) =∏(0,3,4,7) =m0’m3’m4’m7’39Y1=m3’m4’m6’Y2=m0’m2’m5’m7’

Y3=m0’m3’m4’m7’40练习：分别用逻辑门和74LS138画出下面逻辑表达式X=f(a,b,c)=∑(0,3,5,6,7) =a’b’c’+ab+bc+ac41G=f(x,y,z)=∑(0,1,2,4,5,6,7) =∏(3)例：用逻辑门和74LS138画出下面逻辑表达式

42解：①输出信号译码器的级联 例：试用两片3－8译码器74LS138组成4线－16线译码器，将输入的4位二进制代码w,x,y,z译成16个独立的低电平信号D0～D15。43②输入信号和级联问题111片2译码0001111片1译码0000D8～D15D0～D7xyzW0111000011111000片选信号=>使能选中片1：不选片1：利用w控制每片中的一个使能信号443-8译码器扩展成4-16译码器思考：用2-4译码器扩展成4-16译码器45利用一个2-4译码器及四个3-8译码器实现一个5-32译码器46例：利用两片74XX138译码器实现四变量多输出函数。P=f(w,x,y,z)=∑(1,4,8,13)Q=f(w,x,y,z)=∑(2,7,13,14)注：最高位w作为片选信号47练习：分别用3线-8线译码器和2线-4线译码器实现下面的多输出函数：48编码器与译码过程相反，将特定意义的信息编成相应的二进制代码的过程n个二进制代码〔n位二进制数〕对2n信号进行编码的电路普通编码器和优先编码器两类4950例:8线-3线二进制编码器(octal-to-binary)A0=D1+D3+D5+D7A1=D2+D3+D6+D7A2=D4+D5+D6+D7输入互斥信号5152问题：当多个信号同时输入，如何选择其优先级？优先编码器：当输入端同时有信号到来，编码器自动按优先权排队，先对优先权级别最高的输入信号进行编码。然后按优先权顺序分别对其它输入信号进行编码。优先权最高5374××148真值表5474××148引脚图IEEE符号5574××147真值表56例如：有一个网络家电产品，可以按优先权自动处理输入同时出现的险情。优先编码器电路火灾小偷煤气泄漏电视空调处理电路119110传呼业主其它其它优先编码器的应用57Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU659数字多路器〔数据选择器〕——MUX数字多路器是从多个输入数据中选择一个送往唯一通道输出，类似一个多掷开关。M〔=2N〕个输入数据需要N位二进制信号来选择输出通道，称为N位选择变量(地址信号)。数据选择器是一个多输入，单输出的组合逻辑电路。60612选1多路器〔如：74LS157〕真值表选择变量决定将某个输入端的数据送至输出端。输入数据（2路）01SelectD0D162ADADY10'+=2选1多路器01AD0D1输入数据选择变量63设计一个4选1数字多路器：在选择信号的控制下，从D0～D3中任选一个送到公共输出端Y。D2A1A0Y0000D01111D1D3Y=A1’A0’D0+A1’A0D1+A1A0’D2+A1A0D3=∑miDiD0D2D1D30101A1A0选择信号64四选一多路器74LS153：1023EN01MUXA0A1D0D1D2D3四选一多路器逻辑符号A0A101D20D21D22D23EN2Y20123D10D11D12D13EN1Y10123MUX74LS153逻辑符号65Y=C’B’A’D0+C’B’AD1+C’BA’D2+C’BAD3+CB’A’D4+CB’AD5+CBA’D6+CBAD7

=∑miDiCBA0001111001D0D1D2D3D6D7D4D5原码输出〔Y〕卡诺图八选一数字多路器66八选一多路器74LS151C、B、A三位地址输入，可以从8个输入数据D7~D0中选择一个需要数据到输出；D7~D0八个数据输入端；67数字多路器的扩展 例：用一片2-4译码器和四片8选1数字多路器构成32选1数字多路器。

解：25=32，32选1就需要5位选择信号 用A4A3A2A1A0来表示选择信号。

信号分配10110001片2片1000111D8～D15D0～D7

A2A1A0A4A3片4片3D24～D31D16～D2300011100011100011100000001110100001111100001011111000111112-4译码器实现产生片选信号68 A4A3作2-4译码器数据输入。译码器输出分别接四片8选1数据选择器的片选端G’。在A4A3作用下，四片8选1分别被选中，片选端为0的选择器工作，片选端为1的选择器不工作。

A2A1A0作8选1选择输入。在A2A1A0作用下，多路器8个输出端分别被选中并输出。6901234567012ENYMUX(1)D0D1D2D3D4D5D6D701234567012ENYMUX(2)D8D15D16D2301234567012ENYMUX(3)01234567012ENYMUX(4)D24D31A0A1A2A3A4012301ENBIN/OCT≥1YA4A300011011A2A1A0Y000D0001D1010D2011D3100D4101D5110D6111D7片选信号：各片的选择信号：例：A4A3A2A1A0=11101选中第四片选择器的D5输出。Y=D29111011110D5D29思考：如何用一片4选1数字多路器和四片8选1数字多路器构成32选1数字多路器？70用两片74S150〔16选1多路器〕，构成1个32选1的数字多路器最高位选择信号输入为片选信号71问题：如何选择多位数据？需要多个数字多路器。 例：构造逻辑电路实现对两组4位数据的选择。利用四片2选1数字多路器、选择信号、使能信号在四线数据Ai’s和Bi’s中选择一组送至输出端Yi’s。 这里,s=0时将Ai’s送至输出端Yi’s； s=1时将Bi’s送至输出端。72利用两片74S153构成四线数字多路器1、每个数字多路器逻辑电路仅实现一位输入数据的选择。选择四位数据，需要四线数字多路器。2、多个多路器使用同一选择信号输入。例：A=0,B=0,输出源数据：SD73数字多路器的应用 用数字多路器实现逻辑函数

a)选择信号位数=逻辑函数中变量个数

b)选择信号位数<逻辑函数中变量个数

解决1：多路器级联 解决2：利用降维卡诺图74例：用8选1数字多路器实现逻辑函数F=f(x,y,z)=∑(1,2,4,5,7)解：8选1数字多路器的逻辑函数为Y=C’B’A’D0+C’B’AD1+C’BA’D2+C’BAD3+CB’A’D4+CB’AD5+CBA’D6+CBAD7其中，A,B,C为选择信号，Di为数据信号。F=x’y’z+x’yz’+xy’z’+xy’z+xyzC=x,B=y,A=zD0=D3=D6=0D1=D2=D4=D5=D7=1CBA0001111001D0D1D2D3D6D7D4D5Y卡诺图xyz00011110010Y卡诺图111110075C=x,B=y,A=zD0=D3=D6=0D1=D2=D4=D5=D7=176卡诺图的降维卡诺图的维数：卡诺图的变量数如果把某些变量也作为卡诺图小方格内的值，将减小卡诺图的维数，这种卡诺图称为降维卡诺图。作为降维图小方格中值的那些变量称为记图变量。方法： 设记图变量为x，对于原卡诺图中，当x=0时，原图单元值为F，x=1时，原图单元值为G，那么在新的降维图中对应的降维图单元中填入子函数x’F+xG。其中F和G可以是0、1、某一变量，也可以是某一函数。77例：实现对下面四变量卡诺图的降维AB00011110CD00011110ABC0001111001四变量三变量二变量DC+D0101ABCDC+D781变量降维图通过降维以后，相当于减少了逻辑函数的变量数目。当降维卡诺图的维数与数据选择器的选择输入端数目相等时，即可按照用具有n个选择输入端的数据选择器实现n变量逻辑函数的方法来实现m变量的逻辑函数。01ADC+D0101ABCDC+D79例：用4选1多路器实现布尔函数F=f(x,y,z)=∑(1,2,4,5,7)解：F=f(x,y,z)=∑(1,2,4,5,7)=x’y’z+x’yz’+xy’z’+xy’z+xyz函数输入变量组合为23=8>4解决方法：对布尔函数进行降维80方法一：令z为记图变量1111XYZ00011110011z’XY0101z1zD0=zD1=z’D2=1D3=zF=X’Y’D0+X’YD1+XY’D2+XYD3

=X’Y’Z+X’YZ’+XY’+XYZXYzz’1zD3D2D1D04-1MUXA1A0EN81方法二：令y为记图变量1111XYZ00011110011Y’XZ0101YY’1D0=yD1=y’D2=y’D3=1F=X’Z’D0+X’ZD1+XZ’D2+XZD3

=X’YZ’+X’Y’Z+XY’Z’+XZFXZYY’1Y’D3D2D1D04-1MUXA1A0EN82方法三：令x为记图变量1Z0101xx’x1111XYZ00011110011YD0=xD1=1D2=x’D3=xF=Y’Z’D0+Y’ZD1+YZ’D2+YZD3

=XY’Z’+Y’Z+X’YZ’+XYZYzx1x’xD3D2D1D04-1MUXA1A0EN83练习：用1个4-to-1MUX实现下面的布尔函数F(X,Y,Z)=Σm(1,2,6,7)

F(A,B,C)=

m(1,3,5,6). 函数输入变量组合为23=8>4

需对输入函数用卡诺图降维法得到记图变量84F(X,Y,Z)=X’Y’Z+X’YZ’+XYZ’+XYZ=Σm(1,2,6,7)111XYZ00011110011z’XY0101z01D0=zD1=z’D2=0D3=1F=X’Y’D0+X’YD1+XY’D2+XYD3

=X’Y’Z+X’YZ’+XYXYzz’01D3D2D1D04-1MUXA1A0EN85F(A,B,C)=Σm(1,3,5,6)111ABC00011110011CAB0101CCC’D0=CD1=CD2=CD3=C’F=A’B’D0+A’BD1+AB’D2+ABD3

=A’B’C+A’BC+AB’C+ABC’8687例：用一个2选1多路器实现下面的布尔函数：F(x1,x2,x3)=x1’x2’+x1x2’+x1x3 函数输入变量组合为23=8>2 需对输入函数用卡诺图降维法〔降为1维卡诺图〕得到记图变量88F(x1,x2,x3)=x1’x2’+x1x2’+x1x3=x1’x2’x3’+x1’x2’x3+x1x2’x3’+x1x2’x3+x1x2x3=∑(0,1,4,5,7)0X1X2010111X3111X1X2000111100111X3890X1X2010111X3X2’X101X2’+X3D0=X2’D1=X2’+X3D1D02-1MUXAX1FX2’≥1X390思考：用数字多路器作为通用逻辑门？1、用2选1多路器实现逻辑与z=x1x0以一个变量作为选择信号，一个变量作为输入信号=x1x0+0x0’以x0作为选择信号，x1作为输入信号D0=0,D1=X1912、用2选1多路器实现逻辑或z=x1+x0=x1x0’+x0

以x0作为选择信号，x1作为输入信号 D0=X1,D1=1922、用2选1多路器实现逻辑非逻辑非运算是单输入变量z=x’=0·x+1·x’以x作为选择信号D0=1,D1=0Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU694二进制加法器 加法器是构成算术运算器的根本单元。半加器不考虑低位来的进位加法叫半加；能完成半加功能的电路叫半加器。全加器考虑低位来的进位加法叫全加；能完成全加功能的电路叫全加器。95一位加法器〔1-bitadder〕能够实现两个1位二进制数相加的运算输出和与进位。961位半加器 组合逻辑设计流程step1：分析输入与输出，写出变量： 输入：两个加数A,B 输出：两个加数的和：S，进位：Co 输入与输出的关系〔1位二输入加法的可能〕：0+0=00+1=11+0=11+1=10黄色数字为和，红色数字为进位。半加器A加数B被加数CO进位输出S半加和97step2：列出真值表ABSCO0000011010101101step3：写出逻辑函数step4：画出逻辑图981位全加器〔考虑低位来的进位〕 组合逻辑设计流程step1：分析输入与输出，写出变量： 输入：两个加数Ai,Bi 来自低位的进位：Ci-1 输出：两个加数的和：S，向高位的进位：CiAiBiCi-1SCi0000000110010100110110010101011100111111step2：列出真值表99Ci=AiBi+AiCi-1+BiCi-1

Si=AiBi’Ci-1’+Ai’Bi’Ci-1+Ai’BiCi-1’+AiBiCi-1

=Ai

Bi

Ci-1step3:逻辑函数100step4:101Ci =AiBi+AiBi’Ci-1+Ai’BiCi-1 =AiBi+(AiBi’+Ai’Bi)Ci-1

=AiBi+(Ai

Bi)Ci-1Si=Ai

Bi

Ci-1102全加器的逻辑符号进位输入加数全加和全加器进位输出被加数103练习：用一片3-8译码器实现1位全加器S(A,B,Ci-1)=Σm(1,2,4,7)C(A,B,Ci-1)=Σm(3,5,6,7)104多位二进制加法器多位数相加时，要考虑进位进位的方式串行进位超前进位例：设计一个n(n=4)位二进制加法器，完成两个n位二进制的加法，输出1个n位的和，以及进位输出

CoutC3C2C1C011010

A3A2A1A01101+B3B2B1B0+1101

-------------------------------

S3S2S1S01010

105串行进位全加器由四个一位二进制全加器通过串行级连组成四位二进制全加器每一位全加器的进位输出，送给下一级的进位输入端。高位的加法运算必须等到低位的加法运算完成后，才能正确进行。106跟笔算相似,用全加器构成串行进位加法器.优点：结构简单。在一些中、低速数字设备中仍有应用。缺点：速度慢。四位二进制全加器，需要经过四级门的延迟时间。107进位生成项传递条件进位表达式和表达式考虑全加器逻辑函数根本思想:根据进位数Ci-1的表达式,先计算出各高位的进位数。当Pi=1,把低位来的进位Ci-1传给Ci当Gi=1,那么Ci=1超前进位加法器108解决滞后的问题了？=>没有。怎样解决？Ci仅由Ai,Bi和C0-1决定。

109递推式110减少了门电路的延迟，但增加了电路的复杂度111集成全加器74LS83是一种典型的集成加法器。一片74LS83只能进行4位二进制数的加法运算，将多片进行级联，就可扩展加法运算的位数。级联方法：将低位片的进位输出与高位片的进位输入相连112用加法器实现减法运算 方法：求减数的以二为基的补码〔补数〕对数N，其补数为rn-N,n为数的长度

113回忆：求任意进制以二为基的补码〔补数〕的运算方法：算法1：1.对r进制数N，从最低有效位向最高有效位进行转换2.遇到的第一个不为0的位转换为r-ai3.将剩余为转换为r-ai-1，直到最高有效位。算法2： 1.对r进制数N，从最低有效位向最高有效位进行转换2.将每一位转换为r-ai-13.将由步骤2得到的结果+1。114115BCD加法器 输入：两个n〔例：n=4〕位二进制数 输出：一个n位二进制数，进位标志1161、相加之和小于等于9相加结果正确。0111〔8421BCD〕=7,正确。2、相加之和大于9相加结果错误，需加6修正。1101〔8421BCD〕是非法码。需加6修正。产生进位，本位和正确。3、相加之和产生进位，且结果错误，需加6修正。0001〔8421BCD〕=17,错误。正确。错误产生原因：两者进位关系不同117结论：两个BCD码相加，当和大于9或进位为1，将结果加6进行修正；当和小于9那么不修正。修正信号应在有进位信号Cout产生、或两个8421BCD码相加之和为10~15的情况下产生。118119&&1ΣΣΣΣ&加6修正Content组合逻辑设计方法1数字集成电路介绍2译码器与编码器3数字多路器4加法器与减法器5二进制比较器与ALU6121二进制比较器功能：实现对两个数进行比较的电路。两个数A和B相比较，有A＞B、A＜B、A＝B三种情况。一位二进制比较器输入输出ABFA>B

FA<B

FA=B00011011001010100001真值表1221位二进制比较器〔多输出函数〕123多位二进制数的比较对于多位数值比较，先比较最高位，在高位相等的条件下，取决于低位的比较结果。例：四位二进制比较器真值表

A3

B3A2

B2A1B1

A0B0

FA＞BFA＜BFA＝B

A3＞B3

×

×

×A3＜B3

×

×

×A3＝B3A2＞B2

×

×A3＝B3

A2＜B2

×

×A3＝B3

A2＝B2

A1＞B1

×A3＝B3

A2＝B2

A1＜B1

×A3＝B3

A2＝B2

A1＝B1A0＞B0A3＝B3

A2＝B2

A1＝B1A0＜B0

A3＝B3

A2＝B2

A1＝B1A0＝B0

100

010

100

0