简介

背景

为了应对现实中的通信链路在传输过程中可能会产生比特差错（误码率，BER——Bit Error Rate，比如误码率为10^-10表示平均没传送10¹⁰比特就会出现一个比特的差错，1可能变成0,0可能变成1；当然误码率与信噪比有很大关系，提高信噪比可降低误码率。然而实际的通信链路并非理想的，它不可能使误码率下降到0），为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。目前在数据链路层广泛使用了CRC的检错技术。

原理

CRC校验的原理是根据接收端与发送端共同约定的除数P，在要发送的数据末尾补上一定位数的CRC校验码，以使“要发送数据+校验码”能够被共同约定的除数P以异或^运算的方式整除，接收端以此作为数据在传输过程中是否发生比特差错的判断依据。这个【使得要发送数据可以被共同约定的除数P整除的】CRC校验码被称为帧检验序列FCS（Frame Check Sequence）。P通常用多项式表示，比如CRC-16的G(x)=x^16^ +x^15^+x^2^+1表示除数P为11000000000000101（共17位）。

异或运算就是教科书中提到的“二进制的模2运算”。

此处可以看到CRC与FCS不是同一个概念，CRC是一种检错方法，而FCS是添加在要发送数据后面、用来校验的冗余码。

计算过程

计算过程概述

在发送端，先把要发送的数据划分为组，假定每组k个比特。假定待发送的数据 M = 101001 （k = 6），CRC就是根据【发送方与接收方共同约定的】除数P（n+1位）生成【用来差错检测用的n位冗余码（FCS）】，并在待发送数据M后添加FCS，由此构成一个新的（k+n）位的帧，使其能够被除数P整除。发送端将新的（k+n）位帧发送出去，接收端在收到后，对每一个收到的（k+n）位帧进行CRC校验：把收到的每一个帧与共同约定的除数P进行异或运算¹，然后检查得到的余数R是否为0。若为0，则说明无差错；不为0，则说明有差错。

n位冗余码的具体计算过程

1. 根据G(x)得到约定的除数P，除数P是n+1位。比如G(x)=x⁸ +x⁶+x⁵+1 表示除数P是 101100001，请注意，根据G(x)得到除数P，是从0位开始算——即多项式最后的1，表示除数的0位是1而非0。
2. 根据待发送的数据M和第一步中【根据G(x)得到的除数P】，得出校验码。具体计算过程如下
   ①假设待发送的数据M的二进制位数为k位，除数P二进制位数为n+1位，则在待发送的数据M后面增添n位“0”——即二进制的模2运算——M*2ⁿ，形成新的k+n位数据M’。
   ②然后将k+n位的M’异或除以【发送和接收方共同约定的】除数P（n+1位），请注意，此处用代码实现时，不能直接简单地M'^P，详见此批注¹和下方给出的代码实现。将【所得到的余数R（二进制的形式，n位）添加到M’增添的后n位0上——比如余数为1，M’在第①步中预留的校验码（全0）位数是三位，则在M’预留的后三位校验码上应改为001，而非1——001称之为FCS（帧校验序列）】，即关注余数FCS添加到M’时的补0问题——将FCS填加到k+n位的M’的n位“0”上。但要注意的是，所得校验码全为0时（即整除）也都不能省略。
3. 此时，将 M’后n位已更新为FCS的新数据【2ⁿM+FCS】作为要发送数据发出，接收端收到后检查是否其能够被共同约定的除数P（二进制的模2运算）异或¹整除。若能够整除，则判定校验通过，数据无误；不能整除，则判定校验不通过，数据在传输过程中出现了差错。

代码实现

Java

import java.math.BigInteger;

public class CrcCheckCodeGenerator {
	
	 BigInteger Dividend;//CRC被除数（要加校验码的字串），为了防止位数过长使用的BigInteger
	 BigInteger CRC_Divisor;//CRC除数
	 
	 public CrcCheckCodeGenerator(String Dividend, String binaryDivisor) {
	  // TODO Auto-generated constructor stub
	  int fillingZeroNumber = binaryDivisor.length()-1;
	  for(int i = 0; i<fillingZeroNumber; i++) {
	   Dividend = Dividend+"0";
	  }
	  this.Dividend = new BigInteger(Dividend,2);
	  this.CRC_Divisor = new BigInteger(binaryDivisor,2);
	 }
	 
	 public String generateCrcCheckCode() {
		 
		 String CRC_DivisorString = CRC_Divisor.toString(2);
		 int binaryResultBit = CRC_DivisorString.length()-1;
		 String binaryResult = "";//CRC最终校验的结果
		 
		 if (Dividend!=null && CRC_Divisor!=null) {
			 String dividendString = Dividend.toString(2);
			 int cRC_Divisor = Integer.parseInt(CRC_DivisorString,2);
			 int i = 0;//代表从Dividend运算到了第几位
			 while (i<dividendString.length()||(binaryResult.length()==CRC_DivisorString.length())) {
				 if (binaryResult.length()<= binaryResultBit) {
					 binaryResult += dividendString.charAt(i)+"";
					 ++i;
				 }else {
					 int result = Integer.parseInt(binaryResult, 2);
					 result = result^cRC_Divisor;
					 if (result == 0) {//防止异或整除后，依然保留一位0
						 binaryResult = "";
					 }else {
						 binaryResult = Integer.toBinaryString(result);
					 }
				
				 }
			 }
			 //补齐最终结果的位数
			 while(binaryResult.length() < CRC_DivisorString.length()-1) {
				 binaryResult = "0"+binaryResult;
			 }
			 return binaryResult;
//			 resultCrcChekCode = Dividend.xor(CRC_Divisor);
	  }else if (Dividend == null) {
		System.out.println("要添加CRC校验码的待发送数据为空");
		binaryResult = "0".repeat(binaryResultBit);
		return binaryResult;
	  }else {
		System.out.println("CRC计算中要用到的除数为空");
		binaryResult = "0".repeat(binaryResultBit);
		return binaryResult;
	  }
	 }
}