本次的三道题目主要考查了组合逻辑、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个输入中是否至少有一个input
和n
相等。同时为了方便后续的操作,对输出进行了取反操作。
最后的效果为:若5个输入没有一个和n相等,则输出1,否则输出0
优先编码器+MUX
回顾一下专门输出,可以发现这符合一个优先队列:
- 若1没出现,输出1;
- 若1出现了,2没出现,输出2;
- ……
可以看出这是一个优先问题,小的数字具有更高的优先级,可以利用优先编码器实现此功能。但是优先编码器是输出最高位的1的位置,故此处需要将对1-5的判断反序。
随后,为了输出没出现的最小的正整数,可以利用MUX:优先编码器输出了位置,MUX接受此位置,按照该位置对应的情况输出对应的正整数,用常量作为MUX的输入即可。
此外,还有一个注意事项:一组可能的输入是1,2,3,4,5
,这时候需要输出6,这个需要特殊考虑
状态转移问题
这道题是一道基本的状态机转移问题,从原状态(位置),接受行进方向(输入),进行状态转移(移动到新位置),输出就是当前状态(位置)。状态数很明确就是1-8,输入操作码进行状态转移。
可以看作是P0课下hit
那道题的翻版,个人觉得还降低了难度。利用logisim
的组合逻辑分析可以很容易得到状态转移电路。
最后的电路也很符合melay状态机的标准形式:
输入序列匹配
这道题题目要求是moore状态机,但是总感觉怪怪的,不太像心中的传统的状态机,但细细一想,确实也符合输入,状态转移的范式,只不过处于状态转移不是那么明显。
匹配前三个周期的输入,可以用串联的寄存器依次将输入存下来:
对三个寄存器的储存值和题目给出的进行比较,对于数的比较,可以直接利用comparator进行比较,如果相等则输出
基于独热编码的MUX输出
总共有三种可能情况需要输出非0值,我的方案是设计电路一次进行了比较,如果满足EEE
,0A0
,A0E
中的一个则对应输出1,其他两个输出0,可以看出这符合独热编码的形式。如果一个都不符合则输出0。
设计电路部分如下:
一个大坑点
logisim
中的寄存器在默认状态下是0,也就是说对于0A0
,如果第一周期(或reset
之后的第一个周期)输入A,第二周期输入0,此时三个寄存器值分别是0、A、0(默认值,并不是输入值),这种情况可能非造成误认为是符合要求的输入。
但这种情况只看出现在第二个周期,笔者的应对方法是加上了一个counter
,如果当前周期数(reset
后置0)小于3,则强制输出0
同学你好,你的T3做法给我很大的启发。当时我在机房的时候,用了一个四位+四位的状态转移电路,将所有情况的状态全部都列了出来,这样导致我在组合逻辑分析时30分钟手搓了640个状态。虽然最后一遍点对了,但是这样的工作量还是难以承受的,你的做法就能很好地起到简化作用。说到串联寄存器,我还有一个想法,就是只用单个寄存器存24位状态,最后通过左移8位弹出最高位,再将输入记入最低8位,这样可能可以进一步简化。
总结得很好,逻辑清晰,表述严谨。
对于第三题,避免误识别 0A0
除了可以使用 counter
实现外,也可以通过在寄存器的输入输出端口分别加上非门来实现。如此,寄存器中初始化的
0
就会变成
f
,而正常的输入输出不受影响,就不会出现误识别的情况了。