计算机组成原理P0-Q1——CRC校验

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

题目描述

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

计算机组成原理P0-Q1——CRC校验

必须严格按照模块的端口定义
文件内模块名:CRC
我们规定除数的最高位一定为1,不需要考虑最高位非1的情况
注意:由于信号原帧位数为8位，进行除法运算时被除数应为8+3=11位**
测试电路：(CRC为你需要搭建的电路)
注意:请保证模块的appearance与下图完全一致，否则有可能造成评测错误

假装是分割线

本题助教团队给出了非常明确的知识点讲解&思路分析，摘录如下：

特殊的模2除法

它与算术除法类似，但在做减法时既不向上借位，也不比较除数和被除数相同位数值的大小；它的运算法则为1-1=0，0-1=1，1-0=1，0-0=0，例如1100-1001=0101。对于模二除法，我们以被除数为1011,除数为10为例，运算过程如下：

计算机组成原理P0-Q1——CRC校验

CRC校验电路

我们只需要将原帧补上( 除数位数-1 )个0作为被除数，然后进行模二除法即可。举个例子，我们要发送的帧A为10011，发送端和接收端共同选定的除数B为1110。因为B是4位二进制数，我们需要在A的后面补上3个0，从而得到A’=10011000。我们将A’作被除数，B作除数，进行”模二除法”。如下图：

计算机组成原理P0-Q1——CRC校验

最后得到的余数是一个三位数(注意如果不是三位，也要在前面补零来凑齐三位)，这就是要求的校验码。我们将得到的校验码110拼接在原数据帧的后面，就得到了要发送的新帧A’’=10011110。这样就完成了CRC校验码的生成。

端口定义（8位）

Dividend[7:0]	I	输入数据，即被除数
Divisor[3:0]	I	输入数据，除数
Output	O	输出数据，CRC校验码（包括原数据+校验码）

目标分析及层次化

因为需要得到生成三位校验码，所以考虑每次对四位数据进行Mod2运算并输出余数。

两个板块：

设计四位模二除法器
使用四位模二除法器搭建8位CRC校验码计算电路

模二除法和异或运算是等价的，所以对于一个四位除四位的模二除法器：

如果被除数的最高位是1,则商１,余数使用异或门来将四位被除数和四位除数异或即可。
如果被除数的最高位是0,则商为0,余数直接等于被除数了。

搭建完四位的除法器，我们再来看看怎么使用这个简单的电路来搭建我们所需要的复杂电路。类似于普通除法的过程，我们计算模二除法时也是每次从被除数中取出一定的位数(对于该问题来说是四位)来和除数相除，除得的余数再补上一位被除数后继续与除数相除。如此，计算过程就相当于进行多次四位的模二除法了。我们要做的就是将上一个四位模二除法器的余数输出，拼接一位被除数作为下一个四位模二除法器的被除数输入(除数始终是同一个数),如此反复直到被除数所有的位都被使用。

具体搭建

输入：输入被除数和除数
被除数进位模块：将原本的被除数补上（除数位数-1）位0作为新的被除数。（splitter虽然丑了点但是真的很实用）
四位模二除法器：
按照前述，搭建一个除法器得到余数，便于后续计算。搭建规则前述很清晰，不过多赘述。
得到前四位余数作为“循环初始值”
-得到的三位余数和被除数现在的最高位组合作为初值，进行第二次的计算。之后得到的每三位余数同样加上被除数的最高位作为四位初值，逐步相除，除到被除数的最后一位即得到最终的三位校验码。（注：此处我重新搭建了一个（3+1）mod4的模块，原理和4mod4一模一样，只是输入变成了3位＋1位，便于搭建）
最后将得到的三位校验码和被除数结合，得到最终的输出。