北航计算机组成原理课程设计-2020秋 PreProject-Logisim-2^n mod 5问题

北航计算机学院-计算机组成原理课程设计-2020秋

PreProject-Logisim-2^n mod 5问题

本系列所有博客，知识讲解、习题以及答案均由北航计算机学院计算机组成原理课程组创作，解析部分由笔者创作，如有侵权联系删除。

2^n mod 5

提交要求

使用Logisim搭建电路，该电路串行输入一个二进制无符号数B(先从高位输入,每输入一个数字就相当于之前输入的数左移一位再加上当前输入的数字)，输出“2的B次幂”模5的余数的电路并提交。

输入： In（1bit 串行输入）
输出： S0，S1，S2，S3，S4（独热编码，当 S x S_x Sx 为1表示 2 I n ≡ x ( m o d 5 ) 2^{In}≡x(mod5) 2In≡x(mod5)）
文件内模块名: mod5
注意：切勿使用内置算术器件（如加法器、除法器等）！请搭建有限状态机！
输入输出样例：
输入输出样例中每一行表示相邻上升沿之间的开区间时间内的输入和期望输出。

解答

2⁰ % 5 = 1；2¹ % 5 = 2；2² % 5 = 4；2³ % 5 = 3；

2⁴ % 5 = 1；2⁵ % 5 = 2；2⁶ % 5 = 4；2⁷ % 5 = 3；

…

可以证明，2ⁿ % 5 = 2^n%4 % 5，具有周期性的规律，并且只可能出现四种情况，因此本题不需要真正计算2ⁿ，只需要通过上述规律建立状态机即可。

根据题目所述的输入模式，1比特串行输入，这是一个极好的例子帮助我们理解状态机：我们从输入输出样例入手，初始状态输入0，其输出应当为S1 = 1，其他等于0（这里简化称之为输出S1，后面的说法与之相对应），这代表着“2⁰ % 5 = 1”（2^In % 5 = S_x），而如果下一个时钟上升沿过后输入变为1，这代表着整体输入的数据为01（先输入高位，每输入一个数字就相当于之前输入的数左移一位再加上当前输入的数字），此时输出应当为S2，2¹ % 5 = 2，……

正如教程所述，状态机的核心就是设计出状态转移，具体在本题来说就是，设当前输入数据为i，当前输出状态o = 2ⁱ % 5，已知下一次输入数据为b（b只能是0或1），求下一个输出o’ = 2^2i+b % 5。由模除的性质，o’ = 2^2i+b % 5 = ((2ⁱ)² * 2^b) % 5 = (o² * 2^b) % 5，如此，下一个状态只与当前状态以及当前输入有关。

明确这一点就很容易穷举出所有的情况，但在此之前我们还要对状态进行编码，以及将状态对应到输出。上面的分析可以看出S0的输出是恒为0的，因此实际我们只需要使用2位二进制数编码4个状态即可，两个状态位分别记为C1、C0，得到如下的状态转移表（其中输出S_x表示五个输出中S_x为1，其它均为0）。

但需要注意的是：本题最后一句话点出了重要要求，“输入输出样例中每一行表示相邻上升沿之间的开区间时间内的输入和期望输出”，这意味着，题目要求即使在时钟上沿没有到来的时候，如果输入变化，输出也必须随其变化，也就是说题目要求我们搭建Mealy型状态机，输出由输入和当前状态共同决定。具体到题目中，例如如果当前状态为00，2^In % 5 = 1，而此时下一个输入已经到来，为1，输出必须相应地变化为S2，而当下一个时钟上沿来临时状态才改变为01。明确这一点之后，才能绘制出符合测评机要求的状态转移表和状态图，如下：

C1	C0	b	C1’	C0’	输出
0	0	0	0	0	S1
0	0	1	0	1	S2
0	1	0	1	1	S4
0	1	1	1	0	S3
1	0	0	1	1	S4
1	0	1	1	0	S3
1	1	0	0	0	S1
1	1	1	0	1	S2

直观表示为状态转移图如下：