P0做题记录

pigKiller

本次的三道题目主要考查了组合逻辑、melay状态机、和奇奇怪怪的moore状态机。

分享一下自己的做法,欢迎大家批评指正。

最小正整数

这道题乍一看可能会觉得比较复杂,但是仔细思考一下,输入总共只有5个,考虑的输出只有1,2,3,4,5,6,找到最小的没出现的正整数只需要一次次比较即可,故一种质朴的思路是将1,2,3,4,5依次和输入相比较,如果1没出现那就输出1,2没出现就输出2…

如果有猛士设计了基于排序的方案,将5个输入进行了排序,在利用最小值得到答案,我向你致以崇高的敬意,比如我的室友。

比较

比较的部分十分简单,可以直接利用comparator进行数据间的比较。

我的思路是设计了一个6输入1输出模块,6个输入分别是iuput1-5,和常数n,用于检测6个输入中是否至少有一个inputn相等。同时为了方便后续的操作,对输出进行了取反操作。

最后的效果为:若5个输入没有一个和n相等,则输出1,否则输出0

image-20231009223052163

优先编码器+MUX

回顾一下专门输出,可以发现这符合一个优先队列:

  • 若1没出现,输出1;
  • 若1出现了,2没出现,输出2;
  • ……

可以看出这是一个优先问题,小的数字具有更高的优先级,可以利用优先编码器实现此功能。但是优先编码器是输出最高位的1的位置,故此处需要将对1-5的判断反序。

随后,为了输出没出现的最小的正整数,可以利用MUX:优先编码器输出了位置,MUX接受此位置,按照该位置对应的情况输出对应的正整数,用常量作为MUX的输入即可。

此外,还有一个注意事项:一组可能的输入是1,2,3,4,5,这时候需要输出6,这个需要特殊考虑

image-20231009222902013

状态转移问题

这道题是一道基本的状态机转移问题,从原状态(位置),接受行进方向(输入),进行状态转移(移动到新位置),输出就是当前状态(位置)。状态数很明确就是1-8,输入操作码进行状态转移。

可以看作是P0课下hit那道题的翻版,个人觉得还降低了难度。利用logisim的组合逻辑分析可以很容易得到状态转移电路。

最后的电路也很符合melay状态机的标准形式:

image-20231009223731958

输入序列匹配

这道题题目要求是moore状态机,但是总感觉怪怪的,不太像心中的传统的状态机,但细细一想,确实也符合输入,状态转移的范式,只不过处于状态转移不是那么明显。

匹配前三个周期的输入,可以用串联的寄存器依次将输入存下来:

image-20231009224119420

对三个寄存器的储存值和题目给出的进行比较,对于数的比较,可以直接利用comparator进行比较,如果相等则输出

image-20231009225019828

基于独热编码的MUX输出

总共有三种可能情况需要输出非0值,我的方案是设计电路一次进行了比较,如果满足EEE,0A0,A0E中的一个则对应输出1,其他两个输出0,可以看出这符合独热编码的形式。如果一个都不符合则输出0。

设计电路部分如下:

image-20231009224456484

一个大坑点

logisim中的寄存器在默认状态下是0,也就是说对于0A0,如果第一周期(或reset之后的第一个周期)输入A,第二周期输入0,此时三个寄存器值分别是0、A、0(默认值,并不是输入值),这种情况可能非造成误认为是符合要求的输入。

但这种情况只看出现在第二个周期,笔者的应对方法是加上了一个counter,如果当前周期数(reset后置0)小于3,则强制输出0


廖鹏飞 回复 pigKiller

同学你好,你的T3做法给我很大的启发。当时我在机房的时候,用了一个四位+四位的状态转移电路,将所有情况的状态全部都列了出来,这样导致我在组合逻辑分析时30分钟手搓了640个状态。虽然最后一遍点对了,但是这样的工作量还是难以承受的,你的做法就能很好地起到简化作用。说到串联寄存器,我还有一个想法,就是只用单个寄存器存24位状态,最后通过左移8位弹出最高位,再将输入记入最低8位,这样可能可以进一步简化。


Coooookie(助教) 回复 pigKiller
助教认证

总结得很好,逻辑清晰,表述严谨。
对于第三题,避免误识别 0A0除了可以使用 counter 实现外,也可以通过在寄存器的输入输出端口分别加上非门来实现。如此,寄存器中初始化的 0 就会变成 f,而正常的输入输出不受影响,就不会出现误识别的情况了。
98fbda373adc1cb1883ddfca8bcf55b.png

0%