CRC 检验
2019-09-07
现实的通信链路都不会是理想的。这就是说，比特在传输过程中可能会产生差错； 1 可能会变成 0，而 0 也可能变成 1。这就叫做比特差错。比特差错是传输差错中的一种。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER（Bit Error Rate）。误码率与信噪比有很大的关系。如果设法提高信噪比，就可以使误码率减小。实际的通信链路并非是理想的，它不可能使误码率下降到零。因此，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。目前在数据链路层广泛使用了循环冗余检验 CRC（Cyclic Redundancy Check）的检测技术。
下面通过一个简单的例子来说明循环冗余检验的原理。
在发送端，先把数据划分为组，假定每组 k 个比特。先假定待传送的数据 M = 101001（k = 6）。CRC 运算就是在数据 M 的后面添加供差错检测用 n 位冗余码，然后构成一个帧发送出去，一共发送 （k + n） 位。在所要发送的数据的后面增加 n 位的冗余码，虽然增大了数据传输的开销，但却可以进行差错检测。当传输可能出现差错时，付出这种代价往往是很值得的。
这 n 位冗余码可用以下方法得出。用二进制的 模 2 运算 （用模 2 运算进行加法时不进位）进行 乘 M 的运算，这相当于在 M 的后面添加 n 个 0 。得到的 （k + n）位的数除以收发双方事先商定的长度为 （n + 1）位的除数 P ，得出的商是 Q 而余数是R（n位，比P少一位）。关于除数 P 下面还要介绍。在下图所示的例子中，M = 101001（即k = 6）。假定除数 P = 1101（即n = 3）。经模 2 除法运算后的结果是：商 Q = 110101（这个商并没有什么用处），而余数 R = 001。这个余数 R 就作为冗余码拼接在数据 M 的后面发送出去。这种为了进行检错而添加的冗余码常称为帧检验序列 FCS（Frame Check Sequence）。因此加上 FCS 后发送的帧是 101001001（即 ），共有 （k + n）位。
注意，循环冗余检验 CRC 和帧检验序列 FCS 并不是同一个概念。 CRC 是一种检错方法，而 FCS 是添加在数据后面的冗余码，在检错方法上可以选用 CRC ，但也可不选用 CRC。
在接收端把接收到的数据以帧为单位进行 CRC 检验：把收到的每一个帧都除以同样的除数 P （模 2 运算），然后检错得到的余数 R。
如果在传输过程中无差错，那么经过 CRC 检验后得出的余数 R 肯定是 0 （被除数现在是101001001，而除数是P = 1101，看余数 R 是否为 0）。
总之，在接收端对收到的每一帧经过 CRC 检验后，有以下两种情况：
- 若得出的余数 ，则判定这个帧没有差错，就接受（accept）。
- 若余数 ，则判定这个帧有差错（但无法确定究竟是哪一位或哪几位出现了差错），就丢弃。