【我的计组生活5'b00000】P0课下作业简析

l14107cb

大众好，咱们又见面了~~

寄语：很幸运开启了【我的计组生活】系列重制计划，把这一学期经历的记录下来，或许对后人或正在看的你有所帮忙。之前发的推送因为时间等原由，有些分享给人误解，亦有些照片看不清等问题。重制版对这些进行了更加多的优化，期盼大众爱好~

咱们持有什么：2020 计组实验课设的个人项目开源，部分上机题目，以及若干支线技能。这里尤其提醒：部分项目你能够看别人的实现思路，但项目开源后会增多抄袭危害，倘若有幸被请去课程组喝茶，后果自负 哦 ~

*重视：如有错误或能够改进的地区请与笔者联系 ~

当当当当！快醒醒，都 2021 寒假了，难道还有人在看计组？

确实，不仅有人在学，某项目组即将开工，（因为 NDA 限制，不可透露更加多）

重回金秋，咱们将一切归 0，一块学习（回忆）计组课程~

本期运用的软件：Logisim、CircuitVerse（可在线运用）

（废话不多说， 直接上干货）

P0课下作业简析

CRC校验(P0.Q1)

提交需求

运用 Logisim 搭建一个除数为四位，原数据帧为 8 位的 CRC 校验码计算电路。详细模块端口定义如下：

信号名方向描述A[7:0]I8位原数据帧B[3:0]I4位除数C[10:0]O8位原数据帧+3位校验码

必须严格根据模块的端口定义

文件内模块名: CRC

咱们规定除数的最高位必定为1,不需要思虑最高位非1的状况

重视:因为信号原帧位数为8位，进行除法运算时被除数应为8+3=11位

测试电路：(CRC为你需要搭建的电路)

重视:请保准模块的appearance与下图完全一致，否则有可能导致评测错误(查看模块appearance办法:在Logisim中打开相应模块后点击左上角按钮)

题目分析

1. CRC校验码简介

CRC校验是数据通信行业中最常用的一种查错校验方式，它对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备亦执行类似的算法，以保准数据传输的正确性和完整性。

在认识这种校验码怎么计算之前，咱们需要先认识一种特殊的除法:“模二除法”。它与算术除法类似，但在做减法时既不向上借位，亦不比较除数和被除数相同位数值的体积；它的运算法则为1-1=0，0-1=1，1-0=1，0-0=0，例如1100-1001=0101。针对模二除法，咱们以被除数为1011，除数为10为例，运算过程如下：

倘若你细心的话，能够发掘，模二除法中的减法和异或的操作是完全相同的，因此模二除法能够用异或来完成。

晓得了模二除法的计算过程，CRC校验码的计算就很简单了。咱们只需要将原帧补上( 除数位数-1 )个0做为被除数，而后进行模二除法就可。举个例子，咱们要发送的帧A为10011，发送端和接收端一起选定的除数B为1110。由于B是4位二进制数，咱们需要在A的后面补上3个0，从而得到A’=10011000。咱们将A’作被除数，B作除数，进行”模二除法”。

最后得到的余数是一个三位数(重视倘若不是三位，亦要在前面补零来凑齐三位)，这便是需求的校验码。咱们将得到的校验码110拼接在原数据帧的后面，就得到了要发送的新帧A’’=10011110。这般就完成为了CRC校验码的生成。

2. 实现办法

校验码即原数据后补上除数位数个0，对除数做模二除法的余数，因此本题的 核心在于：做模二除法。模二除法即若当前位为1，则当前位商为1，余数为对应位数异或。

查看上面的案例，晓得可能需要循环。不外，在硬件其中实现位循环操作是一个比较难实现的任务。

logisim 实现1（Author : lyx）

lyx 朋友的模块分的很细致，比 lxl 习惯要好。计组后期的实验中触及 CPU 的模块设计，尽可能需求朋友们的设计符合高内聚低耦合 的特征，大众会在 P4 的单周期 CPU 中看到这个概念，这儿不太多透露了~

①Swap

②Divisor element

解析：当前的第1位为judge，若其为1则当前位的商为1，求出相应余数；若为0，则直接输出4bits 被除数。

③CRC

logisim 实现2（Author : lxl）

①CRC

②XOR

解析：规律实现和lyx朋友的类似，但 lxl 朋友更爱好把模块能够堆在一块的堆在一块。在模2除法其中，判断首位是不是是1，lxl 直接让被除数和 1000（十进制数字8）比较，算是更加粗暴的方式，但不是典型的范例。

Tips：布线时更加多的运用 Tunnel，简化布线，画自己能一眼看懂的电路图。

实现GRF(P0.Q2)

提交需求

运用 logisim 搭建一个GRF。

GRF中包括32个32位寄存器，分别对应0~31号寄存器，其中0号寄存器读取的结果恒为0。详细模块端口定义如下：

模块功能定义如下：

必须严格根据模块的端口定义

0号寄存器读出的数据在任何时刻都为0

请运用寄存器部件来实现GRF中的32个寄存器

文件内模块名: grf

测试电路：(grf 为你需要搭建的电路)

重视:请保准模块的appearance与下图完全一致，否则有可能导致评测错误

题目分析

根据需要搭建电路就可，重视尽可能运用 Tunnel 的运用来优化可读性。另一，亦能够在VS Code中对文件 XML 代码进行更改，读者们能够自己尝试一波。

logisim 实现1（Author : lyx）

grf

setZero

single

part4

part5

wholePart

解析：分层制作模块，即四个 single 形成 part4、四个 part4 形成 part5、最后构成wholePart，再加入最后模块。写入和读取均用独热编码的方式操作。

logisim 实现2（Author : lxl）

grf

32bits register (like robots huh?)

In/out

Whole Part

解析：一样为分层制作模块，同第1题同样，lxl 朋友更爱好把模块堆在一个照片里，因为是用代码改的模块，因此呢在操作上不至于很繁杂。每一个寄存器对应一个位置，写入和读取操作只需要寻址正确就可。

logisim 实现3（Author : lxl）

解析：这个是 lxl 在 P3 logisim单周期CPU时重构的 GRF，较为符合设想的实现规则。实质上怎样实现不重要，真正重要的是当遇到 bug 的时候自己能否快速找到，在实现的时候能够多瞧瞧讨论区，比如 DMX 运用的时候别忘记三态。

代码生成： [ 来自ROIFEs BLOG：https://roife.github.io/ ]

Logisim 的文件实质上是 XML 代码，由3 种标签构成:

<circuit> 是电路或子电路的标签, 用于标记全部电路。

<wire> 标签用于连线，经过 x-y 属性定位。

<comp> 标签持有 loc 和 name 属性, 用于调用库元件。

能够经过代码生成 XML 来实现构造重复性电路，例如本例需求的 32 个寄存器。

Logisim导航(P0.Q3)

提交需求

计小组要去机房上机考试，需要去B机房，然则日前他在A机房。他此刻的时间很充裕，就决定生成一串随机序列，告诉他下一步行走的方向，直到步行到B机房。他期盼用 logisim 搭建一个能够导航的 Moore 型有限状态机，来经过序列告诉他是不是到达B机房。

题目需求：

计小组只能往东南西北四个方向行走，且若能行走，则每次 只能行走一格。若下一步不存在机房让计小组行走，那样计小组会撞到墙壁并且 hit置高1星期期，此时计小组仍保持原地 不会移动，等待下1星期期再进行运动。（倘若下一步依旧撞墙， 则hit仍然置高；若下一步不会撞墙，则计小组将会继续行进，hit这里周期置 0）

计小组步行到B机房后，“到达”信号需要置位，并保持1星期期。到达B机房后计小组将会在下1星期期回到原点，（下1星期期的输入将被忽略掉）等待下下周期的输入，继续测试他的序列。

计小组遵循上北下南左西右东的方向完成操作。

计小组在时钟提升沿的时候就已然晓得自己下一步的方向并且瞬移过去，并且立即做出判断。

端口定义：

信号名方向描述dir[1:0]I暗示行走的方向：00：向北走 01：向东走 10：向南走 11：向西走clkI时钟信号resetI异步复位信号arriveO是不是到达hitO是不是撞上墙壁

模块名：navigation

必须严格根据模块的端口定义

测试电路：

重视：请保准模块的appearance与下图完全一致，否则有可能导致评测错误

题目分析

从这儿起始咱们要接触状态机的题目了，状态机大众都晓得分 Moore 或 Mealy 型状态机。本题的描述感觉很不清楚，说是 Moore型 的状态机，却含有瞬移、立刻转换的词语，会让人误解为Mealy型状态机。这个题目在评测的时候还开启了数据重测。不外记住，不管怎样，多看评论区总是好的。

这儿给出 lyx 朋友的编码方式，lyx采用了 5 种状态编码，而 lxl 只采用了 2 位的编码方式。不论是怎样编码，都应该进行状态构建。首要对不同的位置进行编码，对应计小组每一个位置均为一个状态题中5种状态（采用3位编码）。如下图构建五个状态：

则对应二进制编码即为状态的码，对应状态转换表为：

状态\方向00/北01/东10/南11/西000/0/arrive = 0001/hit = 0000/hit = 1000/hit = 1000/hit = 1001/1/arrive = 0011/hit = 0010/hit = 0000/hit = 0001/hit = 1010/2/arrive = 0100/hit = 0010/hit = 1010/hit = 1001/hit = 0011/3/arrive = 0011/hit = 1100/hit = 0001/hit = 0011/hit = 1100/4/arrive = 1000000000000

其余的便是要经过打表等操作完成上面这些状态转换了，Logisim 有很好的 Combinational Analysis功能，能够帮忙咱们更好的打表。这个在过程在上机的时候亦要火速，并且保准不出错。

logisim 实现1（Author : lyx）

stateChang

arriveCheck

navigation

解析：lyx 无把 Hit 一块存在状态寄存器中，引起整体看上去规律混乱，在最后模块中未标明的两个模块分别为 stateChange 和 arriveCheck 模块。

logisim 实现2（Author : lxl）

解析：倘若运用 2bit 组合时序电路，因为仅有两个状态，lxl 费尽心思尝试了怎样才可把返回原点的那个周期的输入忽略，最后最终搭配规律门成功实现，lxl 还是忘不了把所有模块放在一块的习惯，虽然这个习惯显出个人的图很简洁，但实质工程化是极欠好的。

Logisim中的FSM(P0.Q4)

正则表达式匹配

正则表达式是对字符串操作的一种规律公式，它一般被用来检索、替换符合某个模式的文本。它的规则比较繁杂，咱们此刻只讲解其中比较简单的几种规则。

[...]指的是要匹配中括号中的字符(重视是字符不是字符串),例如[xyz]便是要匹配x y z这三个字符中的任意一个。

{...}指的是需求匹配”{“前的那个字符几次，例如a{2}指的是要匹配a两次，a{2,4}指的是要匹配a 2至4次,a{,4}指要匹配a 0至4次，a{2,}指要匹配a 2至无穷次。因此[cd]{1,2}便是需求匹配(c或d)一次或两次,即cc、dd、cd、dc、c、d都是能匹配的。

(...)指的是将()内的字符串视为一个整体，例如(ab){1,2}对应的便是ab或abab。

咱们亦能够将多条表达式组合起来，如a{2}b{2}便是指匹配a两次后再匹配b两次,即匹配aabb。

提交需求

运用Logisim搭建一个Mealy型有限状态机 检测串行输入字符串中的能匹配正则表达式b{1,2}[ac]{2}的子串并输出。详细模块端口定义如下：

模块功能定义如下：

必须严格根据模块的端口定义

文件内模块名: fsm

重视: 每当匹配到一个子串时，需要输出一次1。例如对字符串bacbacac,模块应当在第1个c输入和第2个c输入时输出1,而在其他时刻保持输出为0。

重视：有限状态机的设计是Mealy型有限状态机。

测试电路如下：(code部分是你需要搭建的电路)

重视:请保准模块的appearance与下图完全一致，否则有可能导致评测错误

题目分析

已知目的为构建 Mealy 型 有限状态机，模块核心还是在于状态和状态转换的构建。首要识别正则表达式：目的字符串为b{a或c}{a或c}或bb{a或c}{a或c}。下面 构建状态 如下：

状态编号S0S1S2S3S4/true实质道理初始状态输入第1个b输入第2个b输入a或c第2次输入a或c对应二进制码000001010011100

状态转化表如下：

状态\输入a/00b/01c/10others/11S0S0S1S0S0S1S3S2S3S0S2S3S2S3S0S3S4S1S4S0S4/trueS0S1S0S0logisim 实现1（Author : lyx）

logisim 实现2（Author : lxl）

lxl 这个版本依然是 2 位的状态暗示，看起来简洁，并不符合工程方式。当然了，倘若你对自己模块化能力特别有把握，亦能够尝试这种做法。

思考

这道题本身的状态转换没啥问题，只是针对 clr 信号的处理非常的不舒服，但亦是合情恰当。

同步复位需求：时钟提升沿到来时 倘若 clr 信号是 1，才进行复位。

区别于异步复位，清零需要时钟提升沿和 clr 信号一起功效，而不是只看 clr 信号；又或是构成的电路不是时钟提升沿亦能够触发清零。

因此呢不可运用内置于寄存器内的 reset，而是需要自己搭建，于是出现了以下的故事。（《数字设计和计算机体系结构》上有）

好啦，这是 重制版的第 1 期【我的计组生活】，同期身份亦转换成为了经历过计组课设的学生了（虽然我的计组分甚是惨淡，或许做为一个过来人能够供给的更加多吧~~

老规矩，有错误必定要联系作者更改，能够在后台直接进行留言~

期盼能有帮忙到你哦！！不介意的童鞋能够来一波赞和在看，乃至是不是还能够来一波打赏~

PS宣传：各位看见了没，非常多照片引用自大番薯的石头屋，大番薯很强，剧烈举荐给大众 ~~

【我的祭祖生活0X00】From 大番薯的石头屋