MIPS RAM设计实验
实验目的
理解主存地址基本概念,理解存储位扩展基本思想,并能利用相关原理构建能同时支持字节、半字、字访问的存储子系统。
主要任务
Logisim\text{Logisim}Logisim 中 RAM\text{RAM}RAM 组件只能提供固定的地址位宽,数据输出也只能提供固定的数据位宽,访问时无法同时支持字节/半字/字三种访问模式,实验要求利用 444 个 888 位的 RAM\text{RAM}RAM 组件进行扩展,设计完成既能按照 888 位、也能按 161616 位、也能按照 323232 位进行读写访问的 323232 位存储器。
AddrAddrAddr 为 121212 字节地址输入(字访问时忽略最低两位,半字访问时忽略最低位,倒数第二位片选,字节访问时,低两位进行片选)。DinDinDin 为 323232 位写入数据 (不同访问模式有效数据均存放在最低位,高位忽略)。ModeModeMode 为访问模式控制位(000000 表示字访问,010101 表示 111 字节访问,101010 表示 222 字节访问)。WEWEWE 是写使能,111 表示写入,000 表示读出 ...
洛谷 P2761 软件补丁问题
传送门 ↬\looparrowright↬
题目描述
T\text TT 公司发现其研制的一个软件中有 nnn 个错误,随即为该软件发放了一批共 mmm 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。
换句话说,对于每一个补丁 iii,都有 222 个与之相应的错误集合 b1b_1b1和 b2b_2b2,使得仅当软件包含 b1b_1b1 中的所有错误,而不包含 b2b_2b2 中的任何错误时,才可以使用补丁 iii。补丁 iii 将修复软件中的某些错误 f1f_1f1,而同时加入另一些错误 f2f_2f2。另外,每个补丁都耗费一定的时间。
试设计一个算法,利用 T\text TT 公司提供的 mmm 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。对于给定的 nnn 个错误和 mmm 个补丁程序,找到总耗时最少的软件修复方案。
输入格式
第 111 行有 222 个正整数 nnn 和 mmm,nnn 表示错误总数,mmm 表示 ...
洛谷 P4011 孤岛营救问题
传送门 ↬\looparrowright↬
题目描述
194419441944 年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 nnn 行,东西方向被划分为 mmm 列,于是整个迷宫被划分为 n×mn\times mn×m 个单元。每一个单元的位置可用一个有序数对(单元的行号,单元的列号)来表示。南北或东西方向相邻的 222 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 ppp 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角,即 (x,y)(x,y)(x,y) 单元里,并已经昏迷。迷宫只有一个入口,在西北角。也就是说,麦克可以直接进入 (1,1)(1,1)(1,1) 单元。另外,麦克从一个单元移动到另一个相邻单元的时间为 111,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法,帮助麦克以最快的方式到达瑞恩 ...
MIPS寄存器文件设计实验
实验目的
学生了解 MIPS\text{MIPS}MIPS 寄存器文件基本概念,进一步熟悉多路选择器、译码器、解复用器等 Logisim\text{Logisim}Logisim 组件的使用,并利用相关组件构建 MIPS\text{MIPS}MIPS 寄存器文件。
主要任务
利用 Logisim\text{Logisim}Logisim 平台构建一个简化的MIPS寄存器文件,内部包含 444 个 323232 位寄存器。$R_1\#$ 为第 111 个读寄存器的编号,$R_2\#$ 为第 222 个读寄存器的编号。$W\#$ 为写入寄存器编号,DinDinDin 为写入数据,WEWEWE 写使能信号,为 111 时在 CLKCLKCLK 上跳沿将 DinDinDin 数据写入 $W\#$ 寄存器。CLKCLKCLK 为时钟信号,上跳沿有效。RD1RD_1RD1 为 $R_1\#$ 寄存器的值,RD2RD_2RD2 为 $R_2\#$ 寄存器的值,MIPS\text{MIPS}MIPS 寄存器文件中 000 号寄存器的值恒零。
实验原理
$W\#$ 通过译码器后,可得到写入寄存器编号 ...
MIPS运算器设计实验
实验目的
理解 ALU\text{ALU}ALU 的基本构成,掌握 Logisim\text{Logisim}Logisim 中各种运算组件的使用方法,熟悉多路选择器的使用,能利用前述实验完成的 323232 位加法器、 Logisim\text{Logisim}Logisim 中的运算组件构造指定规格的 ALU\text{ALU}ALU 单元。
主要任务
利用前面实验封装好 323232 位加法器以及 Logisim\text{Logisim}Logisim 平台中现有运算部件,构建一个 323232 位算术逻辑运算单元(禁用 Logisim\text{Logisim}Logisim 系统自带的加法器,减法器),可支持算术加、减、乘、除,逻辑与、或、非、异或运算、逻辑左移、逻辑右移、算术右移运算,支持常用程序状态标志(有符号溢出 OFOFOF、无符号溢出 UOFUOFUOF,结果相等EqualEqualEqual),在主电路中详细测试自己封装的 ALU\text{ALU}ALU,并分析该运算器的优缺点。
实验原理
逻辑左移、逻辑右移、算数右移用移位器实现。
无符号乘法用乘法器实现,L ...
6位有符号补码阵列乘法器设计实验
实验目的
掌握补码阵列乘法器的实现原理。
主要任务
在 666 位补码阵列乘法器中利用 555 位阵列乘法器以及求补器等部件实现补码阵列乘法器。
实验原理
X5,Y5X_5,Y_5X5,Y5 为符号位,其余为 555 位为数值位。
由于补码乘法中的乘数、被乘数和成绩的结果都以补码方式给出,为能利用无符号阵列乘法器,需要在运算前将以补码方式出现的被乘数和乘数先变成无符号数,因此需要设计求补电路。此外,无符号的阵列乘法器的输出结果是无符号数,为将结果变成补码,还需再最后增加一个求补电路。结果的符号位由异或门 X5⊕Y5X_5\oplus Y_5X5⊕Y5 产生,作为结果求补的控制信号。
接下来说明求补电路的设计,当输入数字 KKK 的符号位为 111,进行求补操作,否则不作任何改动;可利用分线器得到 K5K_5K5 和 K0∼K4K_0\sim K_4K0∼K4,K5K_5K5 作为多路选择器的选择信号,K0∼K4K_0\sim K_4K0∼K4 送入求补器,输出补码。
若5位阵列乘法器结果的符号位为 111,则要对 555 位阵列乘法器输出结果求补,否则直接输出结果; ...
汉字字库存储芯片扩展实验
实验目的
理解存储系统进行位扩展、字扩展的基本原理,能利用相关原理解决实验中汉字字库的存储扩展问题,并能够使用正确的字库数据填充。
主要任务
现有如下 ROM\text{ROM}ROM 组件,444 片 4K×324K\times324K×32 位 ROM\text{ROM}ROM,777 片 16K×3216K\times3216K×32 位 ROM\text{ROM}ROM,请在 Logisim\text{Logisim}Logisim 平台构建 GB2312\text{GB2312}GB2312 汉字编码的 16×1616\times1616×16 点阵汉字字库,电路输入为汉字区号和位号,电路输出为 8×328\times328×32 位(16×16=25616\times16=25616×16=256 位点阵信息)。
实验原理
实际要求是要对 444 片 4K×324K\times324K×32 位 ROM\text{ROM}ROM 进行字扩展,组成一片16K×3216K\times3216K×32 位 ROM\text{ROM}ROM。
对于一个 141414 位的地址信号, ...
洛谷 P1251 餐巾计划问题
传送门 ↬\looparrowright↬
题目描述
一个餐厅在相继的 NNN 天里,每天需用的餐巾数不尽相同。假设第 iii 天需要 rir_iri 块餐巾($ i=1,2,\cdots,N$)。餐厅可以购买新的餐巾,每块餐巾的费用为 ppp 分;或者把旧餐巾送到快洗部,洗一块需 mmm 天,其费用为 fff 分;或者送到慢洗部,洗一块需 nnn 天(n>mn>mn>m),其费用为 sss 分(s<fs<fs<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NNN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 111 行有 111 个正整数 NNN,代表要安排餐巾使用计划的天数。
接下来的一行是餐厅在相继的 NNN 天里,每天需用的餐巾数。
最后一行包含 555 个正整数 p,m,f,n,sp,m,f,n,sp,m,f,n,s ...
5位无符号阵列乘法器设计实验
实验目的
掌握阵列乘法器的实现原理,能够分析阵列乘法器的性能,能在 Logisim\text{Logisim}Logisim 中绘制阵列乘法器电路。
主要任务
在 555 位阵列乘法器中实现斜向进位的阵列乘法器。其中 X,YX,YX,Y 为5位被乘数和乘数,PPP 为乘积输出,阵列乘法所需的 252525 按位与的乘积项已经通过辅助电路生成,所有乘积项均通过隧道标签给出,用户只需要在已给出的电路框架中进行简单连线即可完成 555 位阵列乘法器。
实验原理
原理来自手工计算乘法。当且仅当 Xi=Yi=1X_i=Y_i=1Xi=Yi=1 时相乘为 111,因此每一位的相乘通过一个与门实现。
每一列的累加用多个 FAFAFA 实现,除最后一行的加法器外,每个 FAFAFA 的进位输出到下一行相邻高位 FAFAFA 的进位输入端。第 000 行阵列加法器进位为常量 000,第 111 行阵列加法器接收第 000 行加法器的进位……第 444行加法器采用横向进位,接收第 333 行加法器的进位。
电路图
32位快速加法器设计实验
实验目的
帮助理解成组进位产生函数,成组进位传递函数的概念,熟悉 Logisim\text{Logisim}Logisim 平台子电路的概念,能利用前述实验封装好的 444 位先行进位子电路以及 444 位快速加法器子电路构建 323232 位快速加法器,并能利用相关知识分析对应电路的时间延迟,理解电路并行的概念。
主要任务
利用 161616 位快速加法器以及先行进位电路构建 323232 位快速加法器,并探讨其时间延迟。X,YX,YX,Y 为 323232 位被相加数,CinCinCin 为进位输入,SSS 为和数输出,CoutCoutCout 为进位输出,OverflowOverflowOverflow 为有符号加法运算溢出信号。
实验原理
222 个 161616 位加法器直接串联,C16C_{16}C16 进位输入采用上层的进位输出。
电路图