实验三 小规模组合逻辑电路的分析和设计
一、实验目的
1. 熟悉组合逻辑电路的特点和一般分析方法
2. 熟悉逻辑门电路的使用方法
二、实验预习
1. 组合逻辑电路的分析和设计方法
2. 逻辑门电路的使用
三、实验器材
1. 直流稳压电源
2. 数字逻辑实验箱
3. 74LS00,74LS10,74LS20,74LS86
四、实验内容和步骤
(一)全加器
已知全加器的输入端Ai 、Bi 、Ci-1,输出端Si 和Ci ,输入、输出之间的逻辑关系为:
1-⊕⊕=i i i i C B A S , 1)(-++=i i i i i i C B A B A C
1. 改变函数的形式,使用异或门和与非门将电路构建出来;
2. 改变输入变量的值,记录输出值,并于全加器的真值表进行对比。
(二)三变量不一致电路
设计一个“三变量不一致”电路,要求:
1. 当输入的三个变量不相同时,电路输出为1,否则为0;
2. 全部用与非门实现。
(三)裁判表决电路
举重比赛有三个裁判,一个主裁判A ,两个副裁判B 、C 。在杠铃是否完全举起的裁决中,每一个裁判通过按下自己面前的按钮来裁决。最终的裁决取决于至少两名裁判的裁决,其中必须要有主裁判。如果最终的裁决为杠铃举起成功,
则输出举重“有效”指示灯亮,否则“无效”指示灯亮。请设计此电路,要求全部使用与非门实现。
南通大学计算机科学与技术学院计算机数字逻辑设计 实验报告书 实验名组合逻辑电路数据选择器实验 班级_____计嵌151_______________ 姓名_____张耀_____________________ 指导教师顾晖 日期 2016-11-03
目录 实验一组合逻辑电路数据选择器实验 (1) 1.实验目的 (1) 2.实验用器件和仪表 (1) 3.实验内容 (1) 4.电路原理图 (1) 5.实验过程及数据记录 (2) 6.实验数据分析与小结 (9) 7.实验心得体会 (9)
实验三组合逻辑电路数据选择器实验 1 实验目的 1. 熟悉集成数据选择器的逻辑功能及测试方法。 2. 学会用集成数据选择器进行逻辑设计。 2 实验用器件和仪表 1、8 选 1 数据选择器 74HC251 1 片 3 实验内容 1、基本组合逻辑电路的搭建与测量 2、数据选择器的使用 3、利用两个 74HC251 芯片(或 74HC151 芯片)和其他辅助元件,设计搭建 16 路选 1 的电路。 4 电路原理图 1、基本组合逻辑电路的搭建与测量 2、数据选择器的使用
3、利用两个 74HC251 芯片(或 74HC151 芯片)和其他辅助元件,设计搭建 16 路选 1 的 电路。 5 实验过程及数据记录 1、基本组合逻辑电路的搭建与测量 用 2 片 74LS00 组成图 3.1 所示逻辑电路。为便于接线和检查,在图中要注明芯片编号及各引脚对应的编号。
图 3.1 组合逻辑电路 (2)先按图 3.1 写出 Y1、Y2 的逻辑表达式并化简。 Y1==A·B ·A =A + A·B=A + B Y2=B·C ·B·A = A · B+ B ·C (3)图中 A、B、C 接逻辑开关,Y1,Y2 接发光管或逻辑终端电平显示。(4)改变 A、B、C 输入的状态,观测并填表写出 Y1,Y2 的输出状态。 表 3.1 组合电路记录
实验二组合逻辑电路的设计 一、实验目的 1.掌握组合逻辑电路的设计方法及功能测试方法。 2.熟悉组合电路的特点。 二、实验仪器及材料 a) TDS-4数电实验箱、双踪示波器、数字万用表。 b) 参考元件:74LS86、74LS00。 三、预习要求及思考题 1.预习要求: 1)所用中规模集成组件的功能、外部引线排列及使用方法。 2) 组合逻辑电路的功能特点和结构特点. 3) 中规模集成组件一般分析及设计方法. 4)用multisim软件对实验进行仿真并分析实验是否成功。 2.思考题 在进行组合逻辑电路设计时,什么是最佳设计方案 四、实验原理 1.本实验所用到的集成电路的引脚功能图见附录 2.用集成电路进行组合逻辑电路设计的一般步骤是: 1)根据设计要求,定义输入逻辑变量和输出逻辑变量,然后列出真值表; 2)利用卡络图或公式法得出最简逻辑表达式,并根据设计要求所指定的门电路或选定的门电路,将最简逻辑表达式变换为与所指定门电路相应的形式; 3)画出逻辑图; 4)用逻辑门或组件构成实际电路,最后测试验证其逻辑功能。 五、实验内容 1.用四2输入异或门(74LS86)和四2输入与非门(74LS00)设计一个一位全加器。 1)列出真值表,如下表2-1。其中A i、B i、C i分别为一个加数、另一个加数、低位向本位的进位;S i、C i+1分别为本位和、本位向高位的进位。 A i B i C i S i C i+1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 10 1 1 1 00 1 1 1 1 1 1 2)由表2-1全加器真值表写出函数表达式。
H a r b i n I n s t i t u t e o f T e c h n o l o g y 组合逻辑电路实验设计 血型匹配情况判断电路 一、实验题目: 人的血型有A、B、AB、O四种。输血时输血者的血型与受血者血型必须符合图1中用箭头指示的授受关系。判断输血者与受血者的血型是否符合上述规定,要求用八选一数据选择器(74LS151)及与非门(74LS00)实现。(提示:用两个逻辑变量的4种取值表示输血者的血型,例如00代表A、01代表 B、10代表AB、11代表O。) 图1 二、电路设计: 方案一: 解: 1、题目分析
根据题意,确定有4个输入变量,设为X、Y、M、N;输出变量为P。 其中,用两个逻辑变量X、Y的四中取值表示输血者的血型:00代表A型、01代表B型、10代表AB型、11代表O型。 用另外两个逻辑变量M、N的四种取值表示受血者的血型:00代表A型、01代表B型、10代表AB型、11代表O型。 逻辑输出变量P代表输血者与受血者的血型符合情况:1代表血型符合,0代表血型不符合。 题目中要求用八选一数据选择器(74LS151)及与非门(74LS00)实现电路设计。 2、列写输入与输出变量真值表: 真值表如下图所示 3、逻辑表达式: 根据真值表画出卡诺图:
卡诺图如右图所示: 用八选一数据选择器(74LS151),所以输出逻辑表达式写成最小项和的形式:设X 、Y 、M 为选择变量,X 为高位。 逻辑函数P 的与或标注型表达式: P (X ,Y ,M ,N ) X Y M N X Y M N X Y M N X Y M N X Y M N =+++++ 4、比较表达式: 与标准表达式比较得:267P Nm N m(0,1,3,5)m m =+∑++ 所以,数据选择器中EN=0,0135D D D D N ==== D 2=N ,D 4=0, D 6=D 7=1, 5、逻辑电路图:
实验三分治算法(2) 一、实验目的与要求 1、熟悉合并排序算法(掌握分治算法) 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况,写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include
int target[N],head[N],tail[N]; int i=0,n,m; for(; i
本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号: 05 学生姓名:俞梦真 指导教师:郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求
1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 归式,就是如何将原问题划分成子问题。 2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。 3.界函数,问题规模变化的函数,它保证递归的规模向出口条件靠拢(2)递归与非递归之间如何实现程序的转换? (3)分析二分查找和快速排序中使用的分治思想。 答: 1.一般根据是否需要回朔可以把递归分成简单递归和复杂递归,简单递归一般就是根据递归式来找出递推公式(这也就引申出分治思想和动态规划)。 2.复杂递归一般就是模拟系统处理递归的机制,使用栈或队列等数据结构保存回朔点来求解。 (4)分析二次取中法和锦标赛算法中的分治思想。 二次取中法:使用快速排序法中所采用的分划方法,以主元为基准,将一个表划分为左右两个子表,左子表中的元素均小于主元,右子表中的元素均大于主元。主元的选择是将表划分为r
实验三组合逻辑电路的设计(一) 一、实验目的 1.掌握用SSI器件设计组合逻辑电路的方法; 2.熟悉各种常用MSI组合逻辑电路的功能与使用方法; 3.掌握多片MSI组合逻辑电路的级联、功能扩展; 4.学会使用MSI逻辑器件设计组合电路; 5.培养查找和排除数字电路常见故障的初步能力。 二、实验器件 1.74LS00 四二输入与非门74LS20 双四输入与非门 2.74LS138 三线—八线译码器74LS139 双二线—四线译码器 三、实验原理 组合逻辑电路是最常见的逻辑电路,其特点是在任何时刻电路的输出信号仅取决于该时刻的输入信号,而与信号作用前电路原来所处的状态无关。组合逻辑电路的设计,就是如何根据逻辑功能的要求及器件资源情况,设计出实现该功能的最佳电路。 在采用小规模器件(SSI)进行设计时,通常将函数化简成最简与—或表达式,使其包含的乘积项最少,且每个乘积项所包含的因子数也最少。最后根据所采用的器件的类型进行适当的函数表达式变换,如变换成与非—与非表达式﹑或非—或非表达式﹑与或非表达式及异或表达式等。 在数字系统中,常用的中规模集成器件(MSI)产品有编码器﹑译码器﹑全加器﹑数据选择/分配器﹑数值比较器等。用这些功能器件实现组合逻辑函数,基本采用逻辑函数对比方法。因为每一种中规模集成器件都具有某种确定的逻辑功能,都可以写出其输出和输入关系的逻辑函数表达式。在进行设计时,可以将要实现的逻辑函数表达式进行变换,尽可能变换成与某些中规模集成器件的逻辑函数表达式类似的形式。 下来我们介绍一下使用中小规模器件设计组合逻辑电路的一般方法。 四、组合电路设计原则及其步骤 组合电路的设计是由给定的的逻辑功能要求,设计出实现该功能的逻辑电路,设计过程大致按下列步骤进行: (1)分析设计要求,把用文字描述的形式的设计要求抽象成输入、输出变量的逻辑关系;(2)根据分析出的逻辑关系,通过真值表或其他方式列出逻辑函数表达式; (3)根据题目提供给你的芯片,将逻辑函数化简到所需要的函数式; (4)画出逻辑电路图或电路原理图; 对于MSI组合逻辑电路的设计是以所用MSI个数最少、品种最少,同时MSI间的连线也最少作为最基本的原则。 下面使用中小规模器件我们各举一个例子: 例:用与非门设计三位多数表决器。 步骤:(1)根据真值表写出逻辑表达式: F = AB + BC + AC = AB BC AC (2)画出逻辑图,如图3—1所示
实验三组合逻辑电路(常用门电路、译码器和数据选择器) 一、实验目的 1.掌握组合逻辑电路的设计方法 2.了解组合逻辑电路的冒险现象与消除方法 3.熟悉常用门电路逻辑器件的使用方法 4.熟悉用门电路、74LS138和74LS151进行综合性设计的方法 二、实验原理及实验资料 (一)组合电路的一般设计方法 1.设计步骤 根据给出的实际逻辑问题,求出实现这一逻辑功能的最简单逻辑电路,这就是设计组合逻辑电路时要完成的工作。组合逻辑电路的一般设计步骤如图3.1所示。 图3.1 组合逻辑电路的一般设计步骤 设计组合逻辑电路时,通常先将实际问题进行逻辑抽象,然后根据具体的设计任务要求列出真值表,再根据器件的类型将函数式进行化简或变换,最后画出逻辑电路图。 2. 组合电路的竞争与冒险(旧实验指导书P17~20) (二)常用组合逻辑器件 1.四二输入与非门74LS00 74LS00为双列直插14脚塑料封装,外部引脚排列和内部逻辑结构如图3.2所示。它共有四个独立的二输入“与非”门,每个门的构造和逻辑功能相同。 图3.2 74LS00引脚排列及内部逻辑结构 2.二四输入与非门74LS20
74LS20为双列直插14脚塑料封装,外部引脚排列和内部逻辑结构如图3.3所示。它共有两个独立的四输入“与非”门,每个门的构造和逻辑功能相同。 图3.3 74LS20引脚排列及内部逻辑结构 3.四二输入异或门74LS86 74LS86为双列直插14脚塑料封装,外部引脚排列和内部逻辑结构如图3.4所示。它共有四个独立的二输入“异或”门,每个门的构造和逻辑功能相同。 图3.4 74LS86引脚排列及内部逻辑结构 3.3线-8线译码器74LS138 74LS138是集成3线-8线译码器,其功能表见表3.1。它的输出表达式为 i A B i Y G G G m 122(i =0,1,…7;m i 是最小项),与基本门电路配合使用,它能够实现任何三变量的逻辑函数。74LS138为双列直插16脚塑料封装,外部引脚排列如图3.5所示。
实验一 组合逻辑电路的设计 一、实验目的: 1、 掌握组合逻辑电路的设计方法。 2、 掌握组合逻辑电路的静态测试方法。 3、 加深FPGA 设计的过程,并比较原理图输入和文本输入的优劣。 4、 理解“毛刺”产生的原因及如何消除其影响。 5、 理解组合逻辑电路的特点。 二、实验的硬件要求: 1、 EDA/SOPC 实验箱。 2、 计算机。 三、实验原理 1、组合逻辑电路的定义 数字逻辑电路可分为两类:组合逻辑电路和时序逻辑电路。组合逻辑电路中不包含记忆单元(触发器、锁存器等),主要由逻辑门电路构成,电路在任何时刻的输出只和当前时刻的输入有关,而与以前的输入无关。时序电路则是指包含了记忆单元的逻辑电路,其输出不仅跟当前电路的输入有关,还和输入信号作用前电路的状态有关。 通常组合逻辑电路可以用图1.1所示结构来描述。其中,X0、X1、…、Xn 为输入信号, L0、L1、…、Lm 为输出信号。输入和输出之间的逻辑函数关系可用式1.1表示: 2、组合逻辑电路的设计方法 组合逻辑电路的设计任务是根据给定的逻辑功能,求出可实现该逻辑功能的最合理组 合电路。理解组合逻辑电路的设计概念应该分两个层次:(1)设计的电路在功能上是完整的,能够满足所有设计要求;(2)考虑到成本和设计复杂度,设计的电路应该是最简单的,设计最优化是设计人员必须努力达到的目标。 在设计组合逻辑电路时,首先需要对实际问题进行逻辑抽象,列出真值表,建立起逻辑模型;然后利用代数法或卡诺图法简化逻辑函数,找到最简或最合理的函数表达式;根据简化的逻辑函数画出逻辑图,并验证电路的功能完整性。设计过程中还应该考虑到一些实际的工程问题,如被选门电路的驱动能力、扇出系数是否足够,信号传递延时是否合乎要求等。组合电路的基本设计步骤可用图1.2来表示。 3、组合逻辑电路的特点及设计时的注意事项 ①组合逻辑电路的输出具有立即性,即输入发生变化时,输出立即变化。(实际电路中 图 1.1 组合逻辑电路框图 L0=F0(X0,X1,···Xn) · · · Lm=F0(X0,X1,···Xn) (1.1) 图 1.2 组合电路设计步骤示意图图
学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日
实验一:递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习,旨在加深学生对该算法原理的理解,提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料; 2.学生独自完成实验指定内容; 3.实验结束后,用统一的实验报告模板编写实验报告。 4.提交说明: (1)电子版提交说明: a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验一_学号_姓名”, 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹, 其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 (2)打印版提交说明: a 不可随意更改模板样式。 b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号 字。 c 行间距:单倍行距。 (3)提交截止时间:2018年10月10日16:00。 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: 【必做题】 (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份?
算法递归典型例题 实验一:递归策略运用练习 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份? 源程序: (3)出售金鱼问题:第一次卖出全部金鱼的一半加二分之一条金鱼;第二次卖出乘余金鱼的三分之一加三分之一条金鱼;第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼;现在还剩下11条金鱼,在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼? (4)某路公共汽车,总共有八站,从一号站发轩时车上已有n位乘客,到了第二站先下一半乘客,再上来了六位乘客;到了第三站也先下一半乘客,再上来了五位乘客,以后每到一站都先下车上已有的一半乘客,再上来了乘客比前一站少一个……,到了终点站车上还有乘客六人,问发车时车上的乘客有多少? (5)猴子吃桃。有一群猴子摘来了一批桃子,猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只,以此类推),第九天正好吃完,问猴子们摘来了多少桃子? (6)小华读书。第一天读了全书的一半加二页,第二天读了剩下的一半加二页,以后天天如此……,第六天读完了最后的三页,问全书有多少页? (7)日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将2520个桔子分给六个儿子。分完后父亲说:“老大将分给你的桔子的1/8给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分1/6给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/4给老六;老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子? 四、实验过程 (一)题目一:…… 1.题目分析 由已知可得,运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数,且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天, If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
电子信息工程刘晓旭 2011117147 实验一组合逻辑电路设计(含门电路功能测试) 一.实验目的 1掌握常用门电路的逻辑功能。 2掌握用小规模集成电路设计组合逻辑电路的方法。 3掌握组合逻辑电路的功能测试方法。 二.实验设备与器材 数字电路实验箱一个 双踪示波器一部 稳压电源一部 数字多用表一个 74LS20 二4 输入与非门一片 74LS00 四2 输入与非门一片 74LS10 三3 输入与非门一片 三 .实验任务 1对74LS00,74LS20逻辑门进行功能测试。静态测试列出真值表,动态测试画出波形图,并说明测试的门电路功能是否正常。 2分析测试1.7中各个电路逻辑功能并根据测试结果写出它们的逻辑表达式。 3设计控制楼梯电灯的开关控制器。设楼上,楼下各装一个开关,要求两个开关均可以控制楼梯电灯。 4某公司设计一个邮件优先级区分器。该公司收到有A,B,C,三类邮件,A,类的优先级最高,B类次之,C类最低。邮件到达时,其对应的指示灯亮起,提醒工作人员及时处理。当不同类的邮件同时到达时,对优先级最高的邮件先做处理,其对应的指示灯亮,优先级低的暂不理会。按组合逻辑电路的一般设计步骤设计电路完成此功能,输入输
实验一: (1)74LS00的静态逻辑功能测试 实验器材:直流电压源,电阻,发光二极管,74LS00,与非门,开关,三极管 实验目的:静态逻辑功能测试用来检查门电路的真值表,确认门电路的逻辑功能正确与否 实验过程:将74LS00中的一个与非门的输入端A,B分别作为输入逻辑变量,加高低电平,观测输出电平是否符合真值表描述功能。 电路如图1: 图1 真值表1.1: 实验问题:与非门的引脚要连接正确,注意接地线及直流电源 实验结果:由二极管的发光情况可判断出74LS00 实现二输入与非门的功能 (2)71LS00的动态逻辑功能测试 实验器材:函数发生器,示波器,74LS00,与非门,开关,直流电压源 实验目的:测试74LS00与非门的逻辑功能 实验内容:动态测试适合用于数字系统中逻辑功能的检查,测试时,电路输入串行数
组合逻辑电路实验报告
图6-1:O型静态险象 如图6-1所示电路 其输出函数Z=A+A,在电路达到稳定时,即静态时,输出F 总是1。然而在输入A变化时(动态时)从图6-1(b)可见,在输出Z的某些瞬间会出现O,即当A经历1→0的变化时,Z出现窄脉冲,即电路存在静态O型险象。 进一步研究得知,对于任何复杂的按“与或”或“或与”函数式构成的组合电路中,只要能成为A+A或AA的形式,必然存在险象。为了消除此险象,可以增加校正项,前者的校正项为被赋值各变量的“乘积项”,后者的校正项为被赋值各变量的“和项”。 还可以用卡诺图的方法来判断组合电路是否存在静态险象,以及找出校正项来消除静态险象。 实验设备与器件 1.+5V直流电源 2.双踪示波器 3.连续脉冲源 4.逻辑电平开关 5.0-1指示器
(3)根据真值表画出逻辑函数Si、Ci的卡诺图 (4)按图6-5要求,选择与非门并接线,进行测试,将测试结果填入下表,并与上面真值表进行比较逻辑功能是否一致。 4.分析、测试用异或门、或非门和非门组成的全加器逻辑电路。 根据全加器的逻辑表达式
全加和Di =(Ai⊕Bi)⊕Di-1 进位Gi =(Ai⊕Bi)·Di-1+Ai·Bi 可知一位全加器可以用两个异或门和两个与门一个或门组成。(1)画出用上述门电路实现的全加器逻辑电路。 (2)按所画的原理图,选择器件,并在实验箱上接线。(3)进行逻辑功能测试,将结果填入自拟表格中,判断测试是否正确。 5.观察冒险现象 按图6-6接线,当B=1,C=1时,A输入矩形波(f=1MHZ 以上),用示波器观察Z输出波形。并用添加校正项方法消除险象。
算法设计与分析课程实验项目目录 学生:学号: *实验项目类型:演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。
本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日~6月30日温度24℃ 1.实验目的和要求: 熟悉蛮力法的设计思想。 2.实验原理和主要容: 实验原理:蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容:以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序,实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的: S END +MORE MONEY . 这里有两个前提假设: 第一,字母和十进制数字之间一一对应,也就是每个字母只代表一个数字,而且不同的字母代表不同的数字;第二,数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意,解可能并不是唯一的,不同人的解可能并不相同。3.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。)
该算法程序代码如下: #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数:\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 实验三组合逻辑电路 实验三 组合逻辑电路 一、实验目的 1. 通过简单的组合逻辑电路设计与调试,掌握采用小规模(SSI )集成电路设计组合逻辑电路的方法。 2. 用实验验证所设计电路的逻辑功能。 3. 熟悉、掌握各种逻辑门的应用。 二、实验原理 组合逻辑电路是最常见的逻辑电路之一,可以用一些常用的门电路来组合成具有其他功能的门电路。组合逻辑电路在逻辑功能上的特点是任意时刻的输出仅仅取决于该时刻的输入,而与电路过去的状态无关。在电路结构上的特点是只包含门电路,而没有存储(记忆)单元。在使用中、小规模集成电路来设计组合电路时,一般步骤如图3-1所示: 1. 进行逻辑抽象,首先根据设计任务的要求建立输入、输出变量,列出其真 设计要求 真值表 逻辑抽象逻辑表达式 卡诺图 最简逻辑表达式 逻辑电路图 代数法化减 卡诺图法化减 值表。 2. 用卡诺图或代数法化简,求出最简逻辑表达式。 3. 根据简化后的逻辑表达式,画出逻辑电路图。 若已知逻辑电路,欲分析组合电路的逻辑功能,则分析步骤为: 1. 由逻辑电路图写出各输出端的逻辑表达式。 2. 由逻辑表达式列出真值表。 3. 根据真值表进行分析,从而确定电路功能。 组合电路的设计过程是在理想情况下进行的, 即假设一切器件均没有延迟效应。图3-1 组合逻辑电路设计流程图 三、实验仪器及器件 1. EL-ELL-Ⅳ型数字电路实验系统 2. 集成电路芯片:74LS00 1 2 74LS04 74LS86等 四、实验内容及步骤 1. 测试用异或门和与非门组成的半加器的逻辑功能 如果不考虑来自低位的进位而能够实现将两个1位二进制数相加的电路,称为半加器,半加器的符号如图3-2所示。 半加器的逻辑表达式为: AB CO B A B A B A S =⊕=+= 根据半加器的逻辑表达式可知,半加和S 是输入A 、B 的异或,而进位CO 则为输入A 、B 相与,故半加器可用一个集成异或门和二个与非门组成,电路如图3-3所示。 &=1 1 CO S ΣCO A B S CO 图3-2 半加器符号 图3-3 异或门和与非门组成的半加器逻辑电路 在实验仪上用74LS00及74LS86按图3-3 接线,当输入端A 、B 为表3-1所列状态时,测 电子信息工程晓旭 2011117147 实验一组合逻辑电路设计(含门电路功能测试) 一.实验目的 1掌握常用门电路的逻辑功能。 2掌握用小规模集成电路设计组合逻辑电路的方法。 3掌握组合逻辑电路的功能测试方法。 二.实验设备与器材 数字电路实验箱一个 双踪示波器一部 稳压电源一部 数字多用表一个 74LS20 二4 输入与非门一片 74LS00 四2 输入与非门一片 74LS10 三3 输入与非门一片 三 .实验任务 1对74LS00,74LS20逻辑门进行功能测试。静态测试列出真值表,动态测试画出波形图,并说明测试的门电路功能是否正常。 2分析测试1.7中各个电路逻辑功能并根据测试结果写出它们的逻辑表达式。 3设计控制楼梯电灯的开关控制器。设楼上,楼下各装一个开关,要求两个开关均可以控制楼梯电灯。 4某公司设计一个优先级区分器。该公司收到有A,B,C,三类,A,类的优先级最高,B 类次之,C类最低。到达时,其对应的指示灯亮起,提醒工作人员及时处理。当不同类的同时到达时,对优先级最高的先做处理,其对应的指示灯亮,优先级低的暂不理会。按组合逻辑电路的一般设计步骤设计电路完成此功能,输入输出高低电平代表到 实验一: (1)74LS00的静态逻辑功能测试 实验器材:直流电压源,电阻,发光二极管,74LS00,与非门,开关,三极管 实验目的:静态逻辑功能测试用来检查门电路的真值表,确认门电路的逻辑功能正确与否 实验过程:将74LS00中的一个与非门的输入端A,B分别作为输入逻辑变量,加高低电平,观测输出电平是否符合真值表描述功能。 电路如图1: 图1 真值表1.1: 实验问题:与非门的引脚要连接正确,注意接地线及直流电源 实验结果:由二极管的发光情况可判断出74LS00 实现二输入与非门的功能 (2)71LS00的动态逻辑功能测试 实验器材:函数发生器,示波器,74LS00,与非门,开关,直流电压源 实验目的:测试74LS00与非门的逻辑功能 实验容:动态测试适合用于数字系统中逻辑功能的检查,测试时,电路输入串行数字 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4.实现具体的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2, (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0,1,2, (9) 三.程序算法 将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1—9作为个位数,余数代表有1—余数本身这么多个数作为剩余的个位数,此外,商还代表1—商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验报告 (2009/2010学年第一学期) 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的:加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题。 任务:用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较、文章比较等多个领域。 要求:掌握动态规划法的思想,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件:计算机 软件:Visual C++ 三、实验原理及内容(包括操作过程、结果分析等) 1、最长公共子序列(LCS)问题是:给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n},要求找出X和Y的一个最长公共子序列。 例如:X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列,检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法,求解时间为指数级别的,因此不可取。 2、分析LCS问题特征可知,如果Z={z1,z2,……,z k}为它们的最长公共子序列,则它们一定具有以下性质: (1)若x m=y n,则z k=x m=y n,且Z k-1是X m-1和Y n-1的最长公共子序列; (2)若x m≠y n且x m≠z k,则Z是X m-1和Y的最长公共子序列; (3)若x m≠y n且z k≠y n,则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题,分解为求解较小规模的问题: 若x m=y m,则进一步分解为求解两个(前缀)子字符序列X m-1和Y n-1的最长公共子序列问题; 如果x m≠y n,则原问题转化为求解两个子问题,即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列,取两者中较长者作为X和Y的最长公共子序列。 由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度,由上述分析可得如下递推式: 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见,最长公共子序列的求解具有重叠子问题性质,如果采用递归算法实现,会得到一个指数时间算法,因此需要采用动态规划法自底向上求解,并保存子问题的解,这样可以避免重复计算子问题,在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解(即最长公共子序列),还需要一个二维数组s[][],数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到,从而可以得到最优解的当前解分量(即最长公共子序列中的当前字符),最终构造出最长公共子序列自身。 实验三组合逻辑电路设计(含门电路功能测试) 一、实验目的 1.掌握常用门电路的逻辑功能 2.掌握小规模集成电路设计组合逻辑电路的方法 3.掌握组合逻辑电路的功能测试方法 二、实验设备与器材 Multisim 、74LS00 四输入2与非门、示波器、导线 三、实验原理 TTL集成逻辑电路种类繁多,使用时应对选用的器件做简单逻辑功能检查,保证实验的顺利进行。 测试门电路逻辑功能有静态测试和动态测试两种方法。静态测试时,门电路输入端加固定的高(H)、低电平,用示波器、万用表、或发光二极管(LED)测出门电路的输出响应。动 态测试时,门电路的输入端加脉冲信号,用示波器观测输入波形与输出波形的同步关系。 下面以74LS00为例,简述集成逻辑门功能测试的方法。74LS00为四输入2与非门,电路图如3-1所示。74LS00是将四个二输入与非门封装在一个集成电路芯片中,共有14条外引线。使用时必须保证在第14脚上加+5V电压,第7脚与底线接好。 整个测试过程包括静态、动态和主要参数测试三部分。 表3-1 74LS00与非门真值表 1.门电路的静态逻辑功能测试 静态逻辑功能测试用来检查门电路的真值表,确认门电路的逻辑功能正确与否。实验时,可将74LS00中的一个与非门的输入端A、B分别作为输入逻辑变量,加高、低电平,观测输出电平是否符合74LS00的真值表(表3-1)描述功能。 测试电路如图3-2所示。试验中A、B输入高、低电平,由数字电路实验箱中逻辑电平产生电路产生,输入F可直接插至逻辑电平只是电路的某一路进行显示。 仿真示意 2.门电路的动态逻辑功能测试 动态测试用于数字系统运行中逻辑功能的检查,测试时,电路输入串行数字信号,用示波器比较输入与输出信号波形,以此来确定电路的功能。实验时,与非门输入端A加一频率为 算法设计与分析实验报告 教师: 学号: 姓名: 实验一:串匹配问题 实验目的:(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求:( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 实验三 组合逻辑电路
实验一组合逻辑电路设计
算法设计与分析实验报告 统计数字问题
南京邮电大学算法设计实验报告——动态规划法
数字电路组合逻辑电路设计实验报告
算法设计与分析实验报告