数字逻辑与处理器基础全册配套精品完整课件

1、数字逻辑与处理器基础数字逻辑与处理器基础全册配套精品完整课件全册配套精品完整课件数字逻辑与处理器基础数字逻辑与处理器基础绪论绪论3主要内容主要内容基本问题基本问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1背景背景4基本问题基本问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1课程要求课程要求5整个课程体系包括理论课与实验课两门课程理论课：数字逻辑与处理器基础，学时为理论课：数字逻辑

2、与处理器基础，学时为48，3学分学分实验课：数字逻辑与处理器基础实验，必须选实验课：数字逻辑与处理器基础实验，必须选成绩=平时作业+考试参考书：（1）现代逻辑设计（第二版）， 罗嵘等译，电子工业出版社 （2）计算机组成与设计硬件/软件接口（第三版），郑纬民等译，机械工业出版社应用场景数字电路、处理器是干什么的？我们要学习什么？67背景：课程定位背景：课程定位智能手机具有计算器、Siri、视频等丰富功能看到的电路内部信看到的电路内部信号波形号波形背景：课程定位联系电路与信息世界的重要桥梁电路门电路、触发器信息世界语言、声音、图像人如何处理信息？人如何处理信息？模仿背景v为什么要“数字化”？10背

3、景1：离散的角度v逻辑中最朴素的思想是非此即彼：对于任何事物在一定条件下的判断都要有明确的“是”或“非”，不存在中间状态v研究对象在有限集（可数集合）上，因此其函数、关系都可以用表格表示出来11背景背景12一、模拟信号与数字信号模拟信号：连续变化的信号 自然界中可测试的物理量一般都是模拟信号， 例如温度，压力，距离，时间等数字信号：离散的信号 将模拟信号经过采样、量化和编码后得到的背景背景131 12 23 34 45 57 76 68 89 91 10 0 1 11 1 1 12 21 12 23 34 45 56 67 78 89 91 10 0 1 11 1 1 12 21 18 82

4、20 02 22 22 24 42 26 62 28 83 30 03 32 23 34 43 36 6温温度度( ( C C) )时时间间（小小时时）A A. .M MP P. .M M温温度度和和时时间间关关系系图图( (用用模模拟拟量量表表示示) )背景背景141 12 23 34 45 57 76 68 89 91 10 0 1 11 1 1 12 21 12 23 34 45 56 67 78 89 91 10 0 1 11 1 1 12 21 18 82 20 02 22 22 24 42 26 62 28 83 30 03 32 23 34 43 36 6温温度度( ( C C)

5、 )时时间间（小小时时）A A. .M MP P. .M M温温度度和和时时间间关关系系图图( (用用采采样样值值表表示示) )量化曲线量化曲线背景背景151 12 23 34 45 57 76 68 89 91 10 0 1 11 1 1 12 21 12 23 34 45 56 67 78 89 91 10 0 1 11 1 1 12 2时时间间（小小时时）A A. .M MP P. .M M温温度度和和时时间间关关系系图图( (用用数数字字形形式式表表示示) )1 10 00 01 11 11 10 01 10 00 01 10 00 01 11 11 10 00 01 11 11 10

6、 00 01 10 01 10 00 01 10 01 10 00 01 10 01 10 00 01 11 11 10 01 10 01 11 10 01 11 11 11 11 10 00 01 11 11 10 01 11 11 11 11 10 00 01 11 11 10 01 11 11 11 10 01 11 11 11 10 01 11 11 11 10 00 01 11 10 01 11 11 11 10 01 10 01 11 10 00 01 11 10 01 11 11 11 10 01 11 10 01 10 01 10 00 01 10 00 01 11 11 10

7、 00 01 10 03030292928282727262625252424232322222121202019191818( (o oc)c)一个例子16系统的数字化演进系统的数字化演进171、纯模拟系统音频有线扩音系统音频有线扩音系统Audio public address system线线 性性 放放 大大 器器原原 始始 声声 波波( (O Or ri ig gi in na al l s so ou un nd d w wa av ve es s) )麦麦 克克 风风( (M Mi ic cr ro op ph ho on ne e) )音音 频频A Au ud di io os

8、si ig gn na al lL Li in ne ea ar ra am mp pl li if fi ie er r放放 大大 后后 的的音音 频频 信信 号号A Am mp pl li if fi ie ed da au ud di io o s si ig gn na al l扬扬 声声 器器S Sp pe ea ak ke er r再再 生生 声声 波波R Re ep pr ro od du uc ce ed ds so ou un nd d w wa av ve es s182、数模混合系统音音 频频 信信 号号 的的模模 拟拟 再再 生生A An na al lo og gr

9、re ep pr ro od du uc ct ti io on no of f a au ud di io o s si ig gn na al l扬扬 声声 器器S Sp pe ea ak ke er r声声 波波s so ou un nd d w wa av ve es sC CD D驱驱 动动 器器C CD D D Dr ri iv ve e1 1 0 0 1 1 1 11 1 1 1 1 10 00 0 1 1数数 字字 数数 据据D Di ig gi it ta al l d da at ta a线线 性性 放放 大大 器器L Li in ne ea ar r a am mp pl

10、 li if fi ie er r数数 模模 转转 换换 器器D D A A c co on nv vt te er rCD机原理图（单声道）机原理图（单声道）Basic principle of a CD player系统的数字化演进系统的数字化演进193、纯数字系统 带数字显示的数字钟计计时时电电路路秒个位秒个位秒十位秒十位分个位分个位三位计时器示意图三位计时器示意图系统的数字化演进系统的数字化演进背景背景20三、数字电路的优点1.集成化程度高2.抗噪声、抗工艺偏差的能力强3.既可实现数值运算，又可实现逻辑运算，功能强大4.数字信号的传输和处理比模拟信号更有效、更可靠5.数字信号便于存储基

11、本问题基本问题21基本问题基本问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1基本问题v用电路解决计算（处理）问题v电路（Electrical circuit）：由电气设备和元器件按一定方式连接起来，为电荷流通提供了路径的总体，如电阻、电容、MOS管等v计算：通过有限步骤从输入得到期望输出的过程22基本问题基本问题231、算法算法算法就是对求解某类问题的方法和步骤的描述如描述两个数相乘后与第三个数相加，可用表达式AB+C表示数字电路分析和设计的基本过程：抽象计算（算法）电路结构基础器件基

12、本问题基本问题24数字电路分析和设计的基本过程：抽象计算（算法）电路结构基础器件1. 数字电路的设计：高层次到低层次抽象计算（算法）电路结构基础器件2. 数字电路的分析：低层次到高层次抽象计算（算法）电路结构基础器件转换方式转换方式1：硬件：硬件252、电路结构电路结构将设计好的算法转化为相应的电路结构如将AB+C转化为等价的电路结构1、算法算法算法就是对求解某类问题的方法和步骤的描述如描述两个数相乘后与第三个数相加，可用表达式AB+C表示转换方式转换方式1：硬件：硬件263、基础器件基础器件将电路结构中复杂的运算单元映射到基础器件基础器件包括：与门，非门，与非门，反相器，异或门，触发器，比较

13、器等如将AB+C的电路结构中加法器映射到基础器件转换方式1：硬件v典型的（纯）硬件转换方式具有如下特征： 对于没有过程的函数计算，其实现电路中不存在状态，完全由无记忆器件和互连线组成（组合逻辑）； 对于有过程的计算，其实现由每一步函数计算的硬件实现+过程控制器组成（时序逻辑）27转换方式2：软件v由于算法（特别是复杂的算法，如人脸识别）千差万别，不可能每个算法采用一个独特的硬件实现，因此需要新的转换方式-软件软件v将函数计算看做过程，将其分解为多个基本步骤，每个步骤都是有限操作集的一种操作，从而可以硬件实现v过程的控制器可以采用计数器，具有顺序执行和跳转能力v通过存储单元记录过程中的状态28历

14、史发展历史发展29基本问题基本问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1历史发展：离散数学集合论v1874年德国数学家康托尔证明了不可数无穷的概念，逐步建立了朴素集合论，后来被更加仔细地构架为公理化集合论v离散数字研究有限集合或者可数集合30历史发展：离散数学代数系统：研究抽象化的结构v巴比伦尼亚在西元前1850年已有关于各方面初等算术的坚实知识v花剌子模（约780-850）提出了“算法”与“代数”的概念v函数这个数学名词是莱布尼兹在1694年开始使用的v1830年：伽罗瓦理论在埃

15、瓦里斯特伽罗瓦对抽象代数的工作中得到发展31历史发展：离散数学布尔代数：奠定数字电路理论基础v布尔代数是捕获了集合运算和逻辑运算二者的根本性质的一个代数结构v它处理集合运算交集、并集、补集，和逻辑运算与、或、非v乔治布尔在1847年出版逻辑的数学分析中，提出代数逻辑系统v1937年香农的硕士论文提出布尔代数与电路开关的关系，奠定数字电路基础 32历史发展：离散数学计算理论v可计算性理论：是研究计算的一般性质理论，是计算科学的基础理论之一。通过建立计算的数学模型，可确定哪些问题可以用计算机解决，哪些问题不可能用计算机解决v用图灵机可给出“可计算问题”的精确定义：能够在抽象计算机（图灵机）上编出程

16、序计算其值的问题v图灵论题：凡可计算的函数都可用图灵机来实现3334MemoryControl UnitArithmetic Logic UnitAccumulatorInput Output 历史发展：集成电路历史发展：集成电路35l1950年，结型晶体管诞生l1950年，R Ohl和肖特莱发明了离子注入工艺l1951年，场效应晶体管发明l1956年，C S Fuller发明了扩散工艺l1958年，仙童公司Robert Noyce与德仪公司基尔比间隔数月分别发明了集成电路，开创了世界微电子学的历史l1960年，H H Loor和E Castellani发明了光刻工艺l1962年，美国RCA公

17、司研制出MOS场效应晶体管l1963年，F.M.Wanlass和C.T.Sah首次提出CMOS技术，今天，95%以上的集成电路芯片都是基于CMOS工艺l1964年，Intel摩尔提出摩尔定律，预测晶体管集成度将会每18个月增加1倍l1966年，美国RCA公司研制出CMOS集成电路，并研制出第一块门阵列（50门）l1971年，Intel推出1kb动态随机存储器（DRAM），标志着大规模集成电路出现历史发展：集成电路历史发展：集成电路36l1971年，全球第一个微处理器4004由Intel公司推出，采用的是MOS工艺，这是一个里程碑式的发明l1974年，RCA公司推出第一个CMOS微处理器1802

18、l1976年，16kb DRAM和4kb SRAM问世l1978年，64kb动态随机存储器诞生，不足0.5平方厘米的硅片上集成了14万个晶体管，标志着超大规模集成电路（VLSI）时代的来临l1979年，Intel推出5MHz 8088微处理器，IBM基于8088推出全球第一台PCl1981年，256kb DRAM和64kb CMOS SRAM问世l1984年，日本宣布推出1Mb DRAM和256kb SRAMl1988年，16M DRAM问世，1平方厘米大小的硅片上集成有3500万个晶体管，标志着进入VLSI阶段l1989年，1Mb DRAM进入市场l1989年，486微处理器推出，25MHz

19、，1m工艺，后来50MHz芯片采用 0.8m工艺历史发展：集成电路历史发展：集成电路37l1992年，64M位随机存储器问世l1993年，66MHz奔腾处理器推出,采用0.6工艺l1995年，Pentium Pro, 133MHz，采用0.6-0.35工艺l1997年，300MHz奔腾问世,采用0.25工艺l1999年，奔腾问世，450MHz，采用0.25工艺，后采用0.18m工艺l2000年，1Gb RAM投放市场l2000年，奔腾4问世，1.5GHz，采用0.18工艺l2001年，Intel宣布2001年下半年采用0.13工艺l2003年，奔腾4 E系列推出，采用90nm工艺l2005年，

20、intel 酷睿2系列上市，采用65nm工艺l2007年，基于全新45nm工艺的intel酷睿2 E7/E8/E9上市l2009年，intel酷睿i系列全新推出，创纪录采用了领先的32nm工艺，并且下一代22nm工艺正在研发历史发展：集成电路历史发展：集成电路38l2012年4月，Intel推出了22nm工艺的第三代智能酷睿处理器Ivy Bridgel每台22nm光刻工艺设备最低为3000万美元lIntel骄傲地指出，22nm技术将继续延续摩尔定律之路l已进入14nm时代Intel总裁兼CEO Paul Otellini展示22nm晶圆历史发展：历史发展：CPU39以Intel公司的CPU为例

21、：1971年，Intel公司生产出世界上第一个微处理器4004l面积：4mm3mml集成度：共2300个晶体管l工作频率：108KHzl工艺制程：10uml总线宽度：4bitsl存储容量：640bytes意义重大：为以后“使用通用的硬件设计作为基础，用软件来实现不同的功能”这一设计思想开辟了道路4004微处理器的发明人Ted Hoff因此被英国经济学家杂志列为“第二次世界大战以来最有影响的七位科学家之一”历史发展：历史发展：CPU40l1972年和1974年，Intel公司研制出8080和8085处理器，它们是8位微处理器l1978年，Intel公司生产出16位的微处理器，并命名为8086l1

22、985年，Intel公司推出80386，这是一种32位微处理器芯片，内部包含了27.5万个晶体管，时钟频率为12.5MHz，后逐步提高到33MHzl1993年Intel推出了全新一代的高性能处理器奔腾l1996年推出了最新一代的第六代X86系列CPU奔腾Prol1997年5月，推出Pentium 处理器l1998年，为了占领低端市场，推出Celeron处理器l1998与1999年间，在高端的、基于RISC的工作站和服务器上，Intel公司推出了新一款Pentium Xeonl1999年初，推出了新一代处理器Pentium l2000年，Intel公司发布集成4200万个晶体管的Pentium

23、4处理器l2006年，英特尔-酷睿2双核处理器，随后的四核以及八核历史发展：历史发展：CPU412012年4月，Intel发布了Ivy Bridge处理器Core ix-3000系列处理器：l面积：160mm2l集成度：共14亿个晶体管l工作频率：3.9GHzl工艺制程：22nml总线宽度：64bits历史发展：历史发展：EDA42l早期：没有EDA，集成电路是手工设计的。这时期最著名的公司是Calma，该公司提出了GDSII格式l20世纪70年代中期，开始有研究者开发设计自动化的工具。首先研发的是布局布线工具l1980年，Carver Mead和Lynn Conway出版Introducti

24、on to VLSI Systems，这本划时代的书提出用可编译到硅片上的可编程语言进行芯片设计l最早的EDA工具是由学校研发出来的。最著名的学院派EDA工具之一是“Berkeley VLSI Tools Tarball”l商业EDA工具的出现是在1981年。Daisy Systems、Mentor Graphics和Valid Logic Systems等著名EDA公司就是这个时期成立的l1986年，Gateway Design Automation公司开发了硬件描述语言Verilogl1987年，美国国防部创造了VHDL语言。仿真器可根据语言很快地完成芯片设计的直接仿真。随后，用于逻辑综合

25、的后端工具也被研发出来历史发展：历史发展：EDA43l使用EDA工具进行芯片设计基本原理基本原理44基本问题基本问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1基本原理基本原理451、摩尔定律集成电路的发展规律：摩尔定律（Moore Law）- Min. transistor feature size decreases by 0.7X every three years- True for at least 30 years! (first published in 1965)后人对摩

26、尔定律加以扩展： 集成电路的发展：工艺每三年升级一代，集成度每三年翻两番，特征线宽约缩小30%左右，逻辑电路（以CPU为代表）的工作频率提高约30%基本原理基本原理46nThe data - 37 Years of Moores Law, IEEE Spectrum基本原理基本原理472、Moore定律的极限由Moore定律可知：集成电路的集成度每三年翻两番，工作频率提高约30%。那么集成电路的集成度和工作速率能否一直无限地增长下去呢？答案是不能的，还要考虑集成电路的功耗等物理制约问题！基本原理基本原理48按香农理论：传输1bit数据所需的最小能量为：其中k是波尔兹曼常数，T是绝对温度，是信号

27、的信噪比由海森堡的测不准原理：该能量对应的最小开关时间t为0.04ps，最小门级尺寸是1.5nm，即最大集成度n为4.71013devices/cm2从而得到单位面积的功耗P：太阳表面的功率密度约为6000W/cm2b0002E = limN = 0.693N = 0.693kTlog (1+)xphEth（其中，h为普朗克常数）62bnEP = 3.7 10 W /cmt基本原理基本原理49横轴为特征尺寸，纵轴为每个开关动作所消耗的最小能量由图中可知：特征尺寸越小（即集成度越大），则每个开关动作所消耗的能量会急剧上升基本原理基本原理50此表是理论极限工艺情况下的集成电路与国际半导体技术发展蓝

28、图（ITRS）规定的22nm工艺下的集成电路的性能比较基本原理基本原理51结论：1、功耗问题制约着集成电路的进一步发展2、考虑到功耗问题，想要增大集成度就必须降低工作频率，想要增加工作频率就必须降低集成度，因此两者之间存在一个折中3、22nm技术以下，需要新的材料和制造工艺来降低栅极和沟道的电荷泄漏以及需要改变已有MOSFET的结构课程线索课程线索52科学问题科学问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1基本思路 侧重工作原理与基本设计掌握组合、时序电路的工作原理与调试会设计以CP

29、U为代表的基本数字电路模块 应用强调核心典型电路中小规模：选择器、编码器、JK触发器等，典型不求全大规模：CPU介绍侧重本身，不涵盖IO如何建立算法/处理到电路的桥梁？f: xy基本矛盾千变万化的算法 有限类型电路元件基本途径：离散化、数字化NMOS、PMOS、R、L、C滤波、识别声音、图像核心问题 FSMD：一个算法一种电路 CPU+程序：多种算法映射到一种电路CIO专用芯片不同算法不同电路结构通用CPU不同算法不同比特序列教学日历预期效果与要求预期效果与要求57科学问题科学问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与

30、要求6体会与感想体会与感想7背景背景1预期效果与要求预期效果与要求581. 掌握数字系统的基础理论2. 熟悉数字系统的基本电路结构3. 掌握数字电路与系统的基本分析和设计方法4. 了解集成电路器件的基本构成与核心指标5. 掌握处理器的基本原理6. 具备计算机应用系统设计与开发的初步能力体会与感想体会与感想59科学问题科学问题2Accomplishments4基本原理基本原理4历史发展历史发展 3课程线索课程线索5预期效果与要求预期效果与要求6体会与感想体会与感想7背景背景1背景：一个小故事60 一个人带着一只羊，一条狼和一一个人带着一只羊，一条狼和一棵棵白菜想过河，他每次只能带着一只羊，白菜想

31、过河，他每次只能带着一只羊，或者一条狼，或者一棵白菜过河，并或者一条狼，或者一棵白菜过河，并限定人不在场时，狼和羊，或羊和白限定人不在场时，狼和羊，或羊和白菜不能单独在一起菜不能单独在一起。 试试求出他带一只羊，一条狼和一颗求出他带一只羊，一条狼和一颗白菜过河的方法白菜过河的方法。故事的解读v将狼、羊、白菜运送到对岸是一个过程，与时间相关v过程：事物发展所经过的程序v过程在数学上可以表示为时间的函数v过程还可以通过状态及其转化关系描述v状态指物质系统所处的状况，由一组物理量来表征61故事的分析v过程的表示（狼，羊，白菜，人|） （狼，羊|白菜，人）v状态的表示（狼，羊，白菜，人|）=（WSCP

32、|）=（1111）0000,0001,1110,11116263WSCP|WSC|PWSP|CWS|CPWCP|SWC|SPWP|SCW|SCPSCP|WSC|WPSP|WCS|WCPCP|WSC|WSPP|WSC|WSCP问题的表示问题的解决64WSCP|WSC|PWSP|CWS|CPWCP|SWC|SPWP|SCW|SCPSCP|WSC|WPSP|WCS|WCPCP|WSC|WSPP|WSC|WSCP体会与感想体会与感想651、数量的离散化2、过程的同步化3、算法的结构化课前了解v二进制转换：271, 0.1, -3v二进制算术：-7+5v化简表达式:66CDCBA数字逻辑与处理器基础数字

33、逻辑与处理器基础清华大学电子工程系第二讲：数的表示与布尔代数Accomplishments4算术的布尔代数描述3逻辑与布尔代数2函数的布尔代数描述4布尔代数式的化简5数的编码与二进制表示168参考书ref.1:罗嵘等译,现代逻辑设计(第二版),电子工业出版社编码(ref.1/1.3.4)v编码从广义上讲是信息从一种形式或格式转换为另一种形式或格式的过程v狭义上可以将编码理解为将图像、语音、信号转换为具有特定格式字符序列的过程v抽象上看编码是各种集合的元素映射到字符串的过程准确的说，有限集合X上的串是由X中的元素组成的有限序列，其中，序列是一个定义域由连续整数集合组成的特殊函数v解码是编码的逆过

34、程69为什么用二元编码？v容易表示容易表示 二元编码数只有“0”和“1”两个基本符号，易于用两种对立的物理状态表示 用电灯开关的“闭合”状态表示“1”，用“断开”状态表示“0” 晶体管的导通表示“1”， 截止表示“0” 电容器的充电表示“1”，放电表示“0” 电脉冲的有表示“1”，无表示“0” 脉冲极性的正表示“1”，负表示“0” 电位的高表示“1”，低表示“0” 十进制数有10个基本符号( 0，1，2，.，9 )，需10种状态才能表示，要用电子器件实现起来是很困难的70常见的二元编码方式v有限集合S（原始集合）到有限集合C（编码集合）的映射BCD Code，二进制表示的十进制编码Gray C

35、ode，格雷码ASCII CodeAmerican Standard Code for Information Interchange“空格”对应的比特序列就是“0100000”请课后查找ASCII码的具体编码内容71数制(ref.1/附录A)v人一生都要和十进制打交道v数字硬件系统要用二进制，八进制和十六进制vB进制的表示法？v位权记数法一个数字在序列中所处位置决定了它的权重处在最右边位置的数字权重最低处在最左边位置的数字权重最高72为什么用二进制？v运算简单运算简单 算术运算和逻辑运算是计算机的基本运算，采用二进制可以简单方便地进行这两类运算 二进制数的算术运算特别简单，加法和乘法仅各有3

36、条运算规则( 000，011，111 0和000，010，111 )，运算时不易出错 二进制数的“1”和“0”正好可与逻辑值“真”和“假”相对应，便于计算机进行逻辑运算73二进制Binary System2iiDk 数字:0,11.0111MSBLSB二进制点2221202-12-2位权101.112=12202112012112274MSB(Most Significant Bit)：权重最高位LSB(Least Significant Bit)：权重最低位四比特二进制数23222120等价十进制000000001100102001130100401015011060111723222120

37、等价十进制100081001910101010111111001211011311101411111575高位MSB在左，低位LSB在右1110 1-bit right shift=0111 01421=71110 2-bit right shift=0011 101422=3 .5Left shift左移Right shift右移0110 1-bit left shift=0 1100621=12622=16+8=240110 2-bit left shift=01 100076BCD码vBinary-coded-decimalv编码方式不惟一v8421码有权码每个十进制数字都用其等价的二进

38、制数表示最常用v余3码无权码Excess-3 code请课后查找余3码的具体编码内容，它与8421码的关系778421BCD码十进制数字8.4.2.1BCD00000100012001030011401005010160110701118100091001权重842178注意v8421BCD和二进制数不是等价的和二进制数不是等价的v(395)10=(0011 1001 0101)BCD=(110001011)2v(001110010101)2=(512+256+128+16+4+1)10=91710 39510v9510+9510(1001 0101)BCD+ (1001 0101)BCD每两

39、个4比特二进制数之和S大于1001时, 需要进行修正S-1010=S+(-1010)=S+0101+0001=S+011079格雷码0 0 00 0 10 1 10 1 01 1 01 1 11 0 11 0 0Gray0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1Binaryl二进制码的状态转换按照数值的大小不断改变l格雷码的状态转换按照仅有一位数字发生变化的原则改变80负数的表示法(ref.1/A.4)v加法和减法是最基本的运算，对于任意进制都是一样的v减法：用加法来实现，需要表示负数810 0 1 0 1 1 1 01 0 1 0 1 1 0 1-)1

40、44173+)2171110111100 0 1 0 1 1 0 01 0 1 0 1 1 0 1+)1 46173-)1270101111011101010110补（complements）的概念12347659812111010-5=510+7-12=57是5的12进制的补10-5 = 10+7 =5忽略进位82负数的表示方式基二进制数制系统v有符号数：原码 010101012=+8510 110101012=-8510 v1补码(通常简称反码) 一个1补码表示的负数可以通过它对应的正数N推导2n-1-N (n是N这个数中包括的比特数) 简单的计算方法：将该负数对应的正数N按位取反 对于n

41、比特的二进制数，其可表示的数的范围-(2n-1 -1)2n-1-1对于0，有两种表示法：000和111由于有两个0的表示法，不方便将减法运算变成加法运算83负数的表示方式基二进制数制系统v2补码 一个2补码表示的负数可以通过它对应的正数N推导2n-N (n是N这个数中包括的比特数)MSB是符号位，其权重: -2n-1 MSB=1, 负数; MSB=0, 正数 简单的计算方法：将该负数对应的正数N按位取反，再加1得到 对于n比特的二进制数，其可表示的数的范围-2n-1 2n-1-1对于0，只有一种表示法：000由于只有一个0的表示法，非常方便将减法运算变成加法运算84注意v补码仅针对负数有不同表

42、示v对于正数+8510有符号数 0101010121补码 0101010122补码 010101012v对于负数-8510有符号数 1101010121补码 1010101022补码 10101011285有符号数N-20的1补码21010100100642N 12011 10 1sN 2252101 ( 010111)011001128420sNN 1 s000002222(101100 )1010011 1010100ssNN 1 s-20的2补码222(100000010100)0110001sNN62举例86-20的2补码用加法来代替减法v8-208+(-20)v-20的补码v-12的

43、补码0 1 0 1 0 00 0 1 0 0 0-)1 0 1 1 0 00 0 1 0 0 0+)00101100101110110010100 按位取反101011 再加1101011+000001=101100001100110011 110011+000001= 11010087011101000011+)+4+3+)+7忽略1001111010110+) -3+6+)+3101101100101+)+6+5+)+11忽略11011010+)10111-3-6+)-9-5+7溢出？88处理溢出v增加位数010110011000101+)+6+5+)+11忽略1110111010+)11

44、0111-3-6+)-989位序的定义（endian，端）v简单的比特在通信中按照先后顺序传送即可，不会有什么歧义v当传送复杂的数据结构时，由于通信往往是串行的比特流，在传送中就出现了顺序问题v传递的顺序就是位序v从最常见的数据结构字节看，它由8比特构成 将这8比特传送，理论上有8!=40320种传送方法，例如可以按照32145678，也可以按照76432158等等顺序 可以预见如果这成为现实，那么双方通信将十分困难 幸运(不幸)的是人们的思维习惯决定了只有两种顺序是“合理”的，一个是高位序，另一个则是低位序90位序的含义v 位序必须有一个公认的含义才能再定义顺序。字节最常见的含义是代表一个0

45、-255的整数v 8个比特代表不同的权重v 把比特传送顺序按照从先往后标志为0到7v 当多字节组合成为字时，如2字节、4字节组合字，它们也有相同的字节位序问题v 从低权重字节到高权重就是低位序，而从高权重字节到低权重就是高位序01234567MSBLSB高位序01234567LSBMSB低位序时间顺序l一个和谐的系统或协议中，没有特殊原因下位序是统一的，比特位序和字节位序都会遵守同一顺序 91数的表示与布尔代数Accomplishments4算术的布尔代数描述3逻辑与布尔代数2函数的布尔代数描述4布尔代数式的化简5数的编码与二进制表示192逻辑与布尔代数(ref.1/2.2)v比特与逻辑，新生

46、导引课v主要内容及参考文献 布尔代数的定义 布尔函数=逻辑函数 基本定律/定理 德摩根定律/反演律的应用93布尔代数的定义v布尔代数是数字系统的数学基础v用逻辑运算符表示输入逻辑变量与输出逻辑变量之间的关系 运算: NOT（非）, AND（与）, OR（或） 优先权：非最高，与次之，或最低 运算符: + (或/逻辑加), (与/逻辑乘), or (非/反)94布尔函数v将一组在集合0,1上取值的输入惟一映射到输出变量的取值集合 0,1上v对于布尔函数，都有一个布尔表达式与之对应布尔函数可以表示成与、或、非运算的形式布尔表达式是包含布尔变量和运算符的代数表述真值表布尔函数的表格形式(ref.1/

47、1.4)物理实现：逻辑门95基本定律 (1)vCommutative Law 交换律X+Y=Y+X XY=YXvAssociative Law 结合律(X+Y)+Z=X+(Y+Z)=X+Y+Z(XY)Z=X(YZ)=XYZvDistributive Law 分配律X+(YZ)=(X+Y)(X+Z)X(Y+Z)=XY+XZvComplement 互补律X+X=1 XX=096基本定律(2)vDeMorgans Law 德摩根定律/反演律(X+Y+Z+)=XYZ (XYZ )=X +Y+Z+ v与0 & 1的运算A+0=A, A+1=1A1=A, A0=0 (A+1=1的对偶)vIdempoten

48、t 重叠X+X=X; XX=X (X+X=X的对偶)vInvolution 对合(X)=X97基本定理(1)vDuality 对偶 对偶是布尔代数的一个非常有用的性质 一个布尔表达式的对偶可以通过将与和或互换与和或互换，逻辑0和1互换，同时保持布尔变量不变得到 如果一个布尔代数定理成立，其对偶亦成立 X+0=X(X+0) D=(X)D即X1=Xv对偶函数的一般形式f(X1, X2, , Xn, 0, 1, +, )D=f(X1, X2, , Xn, 1, 0, , +)v如果两个布尔表达式的对偶函数是相同的，则这两个表达式是相同的98基本定理(2)vConsensus theorem 多数定理

49、(X+Y)(Y+Z)(X+Z)=(X+Y)(X+Z)XY+YZ+XZ=XY+XZ用于化简逻辑表达式（代数化简法用到）用于消除组合电路的竞争冒险（下一次课用到）99德摩根定律的应用v德摩根定律给出了复杂函数求反函数的一种方法与和或互换与和或互换逻辑逻辑0和和1互换互换布尔变量求反布尔变量求反100反函数的一般形式：f(X1, X2, , Xn, 0, 1, +, )=f(X1, X2, , Xn, 1, 0, , +)用真值表验证德摩根定律X Y X Y X+Y XY (X+Y) XY (XY) X+Y0 0 110011110 1 101000111 0 011000111 1 0011000

50、0101用德摩根定律求反函数Y=A(B+C)+CDY=A(B+C)+CD= A(B+C)(CD)= A+(B+C) (C+D)= (A+BC)(C+D)102 注意！l反函数l对偶函数()DYABC CD()()YABC CD ()YA BCCD()ABC CDACD()0ABC CDACDBCCDACDACD103用德摩根定律变换逻辑门电路的形式A BAB104与非门等价于对输入取反的或门用德摩根定律变换逻辑门电路的形式ABA B105或门等价于对输入取反的与非门ABA B106或非门等价于对输入取反的与门用德摩根定律变换逻辑门电路的形式A BAB107与门等价于对输入取反的或非门用德摩根定

51、律变换逻辑门电路的形式将与或表达式变换成仅用与非门实现Y=ABC+AC+BCY=(ABC)(AC)(BC)108思考v仅用或非门实现？v仅用与门实现？v是否可以仅用异或门实现？109数的表示与布尔代数Accomplishments4算术的布尔代数描述3逻辑与布尔代数2函数的布尔代数描述4布尔代数式的化简5数的编码与二进制表示1110111算术的布尔代数描述v 与00=001=010=011=1v 或00=001=110=111=1v 非0=11=0 乘法ab=f00=001=010=011=1 加法a+b=cs0+0=000+1=011+0=011+1=10与=乘异或=和异或：ab=(ab)(

52、ab)与=进位 f=ab c=ab s=ab+ab=ab数的表示与布尔代数Accomplishments4算术的布尔代数描述3逻辑与布尔代数2函数的布尔代数描述4布尔代数式的化简5数的编码与二进制表示1112113函数的布尔代数描述ref.1/1.4v二元域上函数的表示方法：真值表表达式其他方式（程序、Binary decision diagram树）v任意功能的函数都可以用布尔代数表示v日历子系统根据月份和是否闰年的标志，给出这个月份的天数日历子系统的C程序v Integer number_of_days (month, leap_flag) switch (month) case janu

53、ary: return (31); case february: if (leap_flag =1) then return (29) else return (28); case march: return (31); case april: return (30); case may: return (31); case june: return (30); case july: return (31); case august: return (31); case september: return (30); case october: return (31); case novemb

54、er: return (30); case december: return (31); default: return (0); v 114日历子系统的逻辑实现v组合逻辑逻辑抽象输入: month(m8,m4,m2,m1), leap_flag输出: d28, d29, d30, d31真值表化简逻辑函数逻辑电路115真值表输出与输入之间的逻辑关系monthleapd28d29d30d310000-0001-00010010010000010101000011-00010100-00100101-00010110-00100111-00011000-00011001-00101010-000

55、11011-00101100-00011101-111-m8,m4,m2,m1无关项Dont care116逻辑函数vd28=m8andm4andm2andm1andleapvd29=m8andm4andm2andm1andleap117d28的逻辑电路d28m8m4m2m1leap118d29的逻辑电路d29m8m4m2m1leap119d30和d31怎么办考虑电路，如何表示它们对应的布尔代数式？120数的表示与布尔代数Accomplishments4算术的布尔代数描述3逻辑与布尔代数2函数的布尔代数描述4布尔代数式的化简5数的编码与二进制表示1121布尔代数式的化简v两级逻辑规范形式(re

56、f.1/2.4)卡诺图(ref.1/2.5)v两级逻辑的化简(ref.1/3.1)Q-M 法(ref.1/3.2)122两级逻辑vSOP和POSSum of Products 与或表达式Product of Sums 或与表达式v规范形式Minterm 最小项Maxterm 最大项( , , , )f A B C DAB AC CD( , , , )()()f A B C DA B C C D 123最小项和最大项的定义v最小项：在n变量逻辑函数中，包含全部n个变量的与项，其中每个变量必须而且只能以原变量或反变量的形式出现一次，这样的与项称为最小项v最大项：在n变量逻辑函数中，包含全部n个变量

57、的或项，其中每个变量必须而且只能以原变量或反变量的形式出现一次，这样的或项称为最大项v组合逻辑标准式：任意逻辑函数可由最小项的或，或者最大项的与得到124三变量逻辑函数的最小项最小项使最小项取值为1的输入变量值最小项下标imiABCABC0000m0ABC0011m1ABC0102m2ABC0113m3ABC1004m4ABC1015m5ABC1106m6ABC1117m7权重222120125用最小项表示逻辑函数CBABCAACCBA)()(CBABCAABCCBABCA43723mmmmm)7 , 4 , 3 , 2(m( ,)Yf A B CABBCABC0112=3100102=210

58、1112=7101002=410MSBLSB126三变量逻辑函数的最大项最大项使最大项取值为0的输入变量值最大项下标iMiABCA+B+C0000M0A+B+C0011M1A+B+C0102M2A+B+C0113M3A+B+C1004M4A+B+C1015M5A+B+C1106M6A+B+C1117M7权重222120127用最大项表示逻辑函数) 4 , 1 , 0 ()()()()()()(410MMMMCBACBACBACBACCBACBABAY128mi & Mi(2,3, 4,7)Ym66MCBACABCABm23470156Ymmmmmmmm7432MMMM)7,4,3,2(7432

59、MMMMM(0,1,5,6)YM7432MMMM129两变量的卡诺图 BA0101 BA010m0(AB) m1(AB)1m2(AB) m3(AB)f (A, B)130三变量的卡诺图 BCA0001 111001 BCA000111100m0(ABC) m1(ABC) m3(ABC) m2(ABC)1m4(ABC) m5(ABC) m7(ABC) m6(ABC)f (A, B, C)131四变量的卡诺图 CDAB0001111000m0(ABCD) m1(ABCD) m3(ABCD) m2(ABCD)01m4(ABCD) m5(ABCD) m7(ABCD) m6(ABCD)11m12(ABC

60、D) m13(ABCD) m15(ABCD) m14(ABCD)10m8(ABCD) m9(ABCD) m11(ABCD) m10(ABCD)f (A, B, C, D)132四变量的卡诺图的另一种形式 ABCD0001111000m0(ABCD) m4(ABCD) m12(ABCD) m8(ABCD)01m1(ABCD) m5(ABCD) m13(ABCD)m9(ABCD)11m3(ABCD)m7(ABCD)m15(ABCD)m11(ABCD)10m2(ABCD) m6(ABCD) m14(ABCD)m10(ABCD)f (A, B, C, D)133f (E, A, B, C, D)五变量