‘壹’ 计算机网络问题，急，，，
2017年12月13日星期三，
这里需要强调一点，生成多项式（generator polynomial）和多项式不是一个概念，这里需要注意。我个人的理解是你要进行几位的CRC校验，就需要几位的生成多项式（generator polynomial），但还收到生成多项式（generator polynomial）的第一位必须为1的限制，因此生成的多项式还需要注意这一点。原始信息所对应的多项式和生成多项式（generator polynomial）不是一个概念。
首先，我们要知道，任何一串二进制数都可以用一个多项式表示：且这串二进制数的各位对应多项式的各幂次，多项式中假如有此幂次项（比如多项式汇中有幂次项x^2对应二进制串码中从右至左的第三位二进制数一定为1.因为右数第一位的幂次项为x^0，右数第二位的幂次项为x^1），则对应二进制数串码中此位置的1，无此幂次项对应0。
举例：代码1010111对应的多项式为x^6+x^4+x^2+x+1，若我们将缺失的幂次项补全的话就有x^6+(x^5)+x^4+(X^3)+x^2+x+1，又因为x^5和X^3所对应的二进制位为0，不记入多项式中，因此有x^6+x^4+x^2+x+1，就是表示 1010111这个串码。
而多项式为x^5+x^3+x^2+x+1的完整多项式为x^5+（x^4）+x^3+x^2+x+1正好对应二进制串码101111,而x^4对应的二进制串码中右数第五位（左数第二位）为0，不记入多项式中，因此,101111可以使用多项式x^5+x^3+x^2+x+1来表示。
通过上述两个多项式的例子，可以看出，当多项式中的幂次项所对应的那一位二进制为1时，多项式中的那一个幂次项存在，而当二进制串码中的某位为0时，对应的多项式幂次项忽略不记录，例如，10111 1因为从左向右第二位是0，因此对应的多项式分子x^4就没有被记录到多项式中，
书面的说法是：
多项式和二进制数有直接对应关系：X的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：X的最高幂次为R，转换成对应的二进制数有R+1位，
我们现在来看题目中generator plynomial （生成多项式）is X^4+x^2+1,最高幂次是4，因此，其表示的二进制为（4+1=5）5位，
且通过crc的原理，我们知道，循环冗余校验码（CRC）是由两部分组拼接而成的，
第一部分是信息码，
第二部分是校验码，
可得公式：
CRC=信息码+校验码，
很明显校验码是跟在信息码之后的，所以，题目中1101011011中左数的那5位是真正传输的信息（信息码），即actual bit string transmitted（实际传输的信息位流）是11010，而后面的5位（11011）是校验码，
接下来我们结合上面的内容来理解对CRC的定义：
循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)*2^R），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)*2^R 除以生成多项式G(x)得到的余数就是校验码。
另一个定义：
利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。
再看另一个描述，在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为1·x^6+1·x^5+0·x^4+0·x^3+1·x^2+0·x^1+1，即 x^6+x^5+x^2+1。
设，编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k(这里的K就是整个原始信息的二进制编码的长度，以上例1100101为例，此串二进制编码的最高位对应的多项式幂次为6，根据定义得K=6+1=7，正好是此串二进制编码的长度，)；
设，生成多项式为G(x)，G(x)的最高幂次等于r，这个r可以随意指定，也就是r可以不等于K，但指定r时，必须满足生成多项式G（x）最高位必须为1的条件，
设，CRC多项式为R(x)。：将P(x)乘以x^r(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。
设，编码后的带CRC的信息多项式为T(x)。：用公式表示为T(x)=x^r*P(x)+R(x),翻译过来就是，编码后的带CRC校验的多项式由左移了r位的原始信息P(x)后接CRC的校验码R（x）组成，
而在接收端，是使用T(x ）去除G(x)，若无余数，则表示接收正确。就是接收端使用接收到的信息T(x ）去除和发送端约好的生成多项式G(x)，若除尽没有余数则表示信息正确接收。
我们再来看本题，
题中给出已传输的信息为：1101011011，即T(x ）=1101011011；
而generator polynomial 生成多项式是：x^4+x^2+1，即G(x)=10101；
那么，我们来使用T(x ）除以G(x)=110，根据上面的定义，我们知道，出现了没有除尽的情况，有余数，余数为110，则说明信息11010在传递过程出现了错误，而题目中给出，若将此信息串码的左数第三位进行翻转，则接收到的信息为：1111011011，那么，
T(x ）=1111011011，
则，再通过T(x ）除以G(x)进行校验运算后，得到余数1，没有除尽
即T(x ）除以G(x)=1，
所以没有通过CRC校验，此时，接收端能发现这个错误，
但是，如果我们将此串数据的左数第三位和最后一位同时翻转，得到1111011010，那么再经过T(x ）除以G(x)的接收端校验后，除尽了，余数为0，则，此时，因为T(x ）除以G(x)=0，通过了接收端的校验，因此，接收端并不能发现这个错误，以为是收到了正确的串码：11110，但实际上我们发送的串码是：11010，
最后，我们再来研究一下，T(x ）是怎么除G(x)的，实际上我们必须清楚，这里的除法实际上并不是我们传统意义上的十进制除法，而是两个二进制的“按位异或”（请注意每步运算都是先进行高位对齐的。）的算法，在二进制数运算中，这被称为模二除运算，
来看两个例子，
【例一】假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010，求编码后的报文。
解：
1、将生成多项式G(X)=X^3+X+1转换成对应的二进制除数1011。
R=3，R就是生成多项式的最高次幂，
2、此题生成多项式有4位（R+1）(注意：通过对生成多项式计算所得的校验码为3位，因为，生成多项式的R为生成多项式的最高次幂，所以校验码位数是3位)，要把原始报文C(X)【这里的C(X)就是1010】左移3（R）位变成1010 000
3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除（高位对齐），相当于按位异或：
1010000
1011
------------------
0001000， 请注意这里，通过第一次除法，也就是模2除（高位对齐）的运算，将两个二进制代码进行了高位对齐后的按位异或的操作后，得到0001000即1000，接下来，需要进行第二次除法，即使用第一步得到的二进制数1000去除1011【G（x）】，则有下面的式子，
1000
1011
------------------
0011，请注意，结果为0011，也可以写成11，但是我们由上面得知，由生成多项式G(X)=X^3+X+1，已经确定了校验位是3位，因此，
得到的余位011，所以最终编码为：1010 011。
例二：
信息字段代码为: 1011001；对应的原始多项式P(x)=x6+x4+x3+1
假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001，又因为g(x)最高次幂为4，因此可以确定校验位是4位，
根据CRC给生成多项式g(x)定义的规则，将原始代码整体左移4位，这样在原始数据后面多出4位校验位的位置，即x^4*P(x),得到：10110010000；
接下来使用10110010000去除以g(x)，得到最终的余数1010，并与原始信息组成二进制串码：1011001 1010发送出去，
接收方：使用相同的生成多项式进行校验:接收到的字段/生成码（二进制除法）
如果能够除尽，则正确，
给出余数（1010）的计算步骤：
除法没有数学上的含义，而是采用计算机的模二除法，即除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐，按位异或。
10110010000
^11001
--------------------------
01111010000 ，这里进行第一次按位异或，得到01111010000，即1111010000，将1111010000再去除以11001，如下步骤，
1111010000
^11001
-------------------------
0011110000，进行了第二次模2除后，得到0011110000，即11110000，将
11110000去除11001，
11110000
^11001
--------------------------
00111000，第三次摸2除，得到00111000，即111000，用
111000去除11001，
111000
^11001
-------------------
001010，进行第四次模2除后，得到最终的余数，001010，即1010，
则四位CRC校验码就为：1010。
‘贰’ 关于计算机网络的crc计算
我们知道，一台主机向另外一台主机发送报文的时候，需要一层层经过自己的协议栈进行数据封装，到达最后一层（四层协议的网络接口层）时需要在帧尾部添加FCS校验码（通过CRC算法得出）。当对端主机收到时，在接收端同样通过CRC算法进行验证，确认传输过程中是否出现错误。它只能确认一个帧是否存在比特差错，但没有提供解决措施。
循环冗余校验的原理
在发送端，先把数据划分为组（即：一帧）。假定每组 k 个比特。
在每组后面，添加供差错检测用的 n 位冗余码一起发送。即：实际发送长度为：k+n 比特。
发送前双方协商n+1位的除数P，方便接收方收到后校验。
给K比特的数据添加除数减一个0（P-1）作为被除数，与第三步确定的除数做“模2除法”。得出的余数即FCS校验序列，它的位数也必须是（P-1）。
将FCS校验序列添加至K个比特位的后面发送出去。
接收方对接收到的每一帧进行校验，若得出的余数 R = 0，则判定这个帧没有差错，就接受(accept)。若余数 R ≠ 0，则判定这个帧有差错，就丢弃。
对“模2除法”进行说明：
“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。
计算示例
那么接收方拿到的就是：101001001。再以它为被除数，1101为除数进行“模2除法”。
‘叁’ 计算机网络：数据链路层
互联网是指很多异构的网络由路由器联系起来的一个大网络。在研究这个大网络之前，我们要庖丁解牛，先研究其局部和单元。最小的网络单元就是局域网，局域网是一个单位所拥有，且地理范围和站点数量都很有限。
局域网内的计算机通信不需要路由器，所以不会用到网络层的协议，而是依赖数据链路层。
上图说明了数据链路层在整个互联网体系中的位置。数据链路层的信道分为两种：
在点到点信道的数据链路层协议上，可以采用简化的三层模型。无论是主机和主机，主机和路由器，或者两个路由器之间，我们都可以看成结点和结点之间的通信。
数据链路层不必考虑物理层是如何实现比特传输的细节，我们甚至可以简单设想，节点A沿着数据链路层的水平方向把帧输出给结点B。
数据链路层的协议有多个，但有三个共性问题。
从上图可以得出以下结论：
利用转义字符（ESC，十六进制编码0x1B）来解决帧的数据部分包含控制字符的问题
信道往往不是理想的，所以通信会带来误差。常用误码率来衡量传输误差。误码率BER（bit error rate）等于错误的比特占全部比特的百分比。
那么我们怎么知道所接受到的帧有没有错误比特呢？这就需要校验机制，目前数据链路层广泛采用循环冗余校验CRC（(Cyclic Rendancy Check）。其原理是在帧的数据部分后面加上冗余码（FCS），接受方利用冗余码校验数据部分。具体细节请参考《计算机网络》。
综上，封装成帧和透明传输保证收到完整的帧，差错检验保证收到正确的帧。这三种机制能保证帧的无差错传输，但不能保证可靠传输（发送什么就接收到什么）。造成不可靠传输的原因有两类：
1. 帧中的比特错误
2. 帧重复，帧丢失，帧失序
数据链路层的帧的三种机制只能消除第一种错误，至于第二种则需要确认和重传机制。在早期互联网中，数据链路层曾经保证可靠传输，但随着光纤技术的发展，误码率大大下降，数据链路层就采用了简单的不可靠传输协议，把可靠运输的实现放在了运输层中。实践证明，这样可以提高通信效率。
最后，我们可以看到，计算机网络本质是通信问题，里面包含了很多通信元素：完整，误差，校验，重复，丢失，失序，可靠传输等。
‘肆’ crc是什么意思 怎么理解crc是什么意思
1、循环冗余校验（Cyclic Rendancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。
2、在数据传输过程中，无论传输系统的设计再怎么完美，差错总会存在，这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错，0变为1，或者1变为0)，从而接受方接收到错误的数据。为尽量提高接受方收到数据的正确率，在接收方接收数据之前需要对数据进行差错检测，当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种，常见的有奇偶校验、因特网校验和循环冗余校验等。循环冗余校验是一种用于校验通信链路上数字传输准确性的计算方法（通过某种数学运算来建立数据位和校验位的约定关系的）。发送方计算机使用某公式计算出被传送数据所含信息的一个值，并将此值 附在被传送数据后，接收方计算机则对同一数据进行 相同的计算，应该得到相同的结果。如果这两个 CRC结果不一致，则说明发送中出现了差错，接收方计算机可要求发送方计算机重新发送该数据。
‘伍’ crc是什么意思
CRC是循环冗余校验（CyclicRendancyCheck）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。
简介
在数据传输过程中，无论传输系统的设计再怎么完美，差错总会存在，这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错，0变为1，或者1变为0)，从而接受方接收到错误的数据。为尽量提高接受方收到数据的正确率，在接收方接收数据之前需要对数据进行差错检测，当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种，常见的有奇偶校验、因特网校验和循环冗余校验等。循环冗余校验是一种用于校验通信链路上数字传输准确性的计算方法（通过某种数学运算来建立数据位和校验位的约定关系的）。发送方计算机使用某公式计算出被传送数据所含信息的一个值，并将此值附在被传送数据后，接收方计算机则对同一数据进行相同的计算，应该得到相同的结果。如果这两个CRC结果不一致，则说明发送中出现了差错，接收方计算机可要求发送方计算机重新发送该数据。
工作原理
循环冗余校验同其他差错检测方式一样，通过在要传输的k比特数据D后添加(n-k)比特冗余位(又称帧检验序列，FrameCheckSequence，FCS)F形成n比特的传输帧T，再将其发送出去。
‘陆’ 计算冗余码
FJNU.1240Description
计算机网络中采用循环冗余码来校验数据的正确性。其原理是:发送方计算出待发送的二进制数据的循环冗余码，并随同原数据一起发送到接收方；接收方通过重新计算接收到的数据的循环冗余码，并和收到的循环冗余码进行比较，如果两者相同则可判定所收到的数据是正确的，否则说明数据是错误的。其中计算二进制数据的循环冗余码的计算过程如下：
>>协议事先约定一个二进制生成表达式，本题设为10011；
>>将待发送的二进制数据串的末尾加4个0；
>>将补上0的数据串按模2除法除于生成表达式，取余数；
>>该余数就是该二进制数据串的循环冗余码。
例如:
数据串为：1101011011
生成表达式为：10011
循环冗余码为1110
计算过程如下：
根据上述的计算方法，请编写一个循环冗余码计算程序，假设二进制数据串的长度不超过20位，生成表达式固定为10011。
Input
输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数。后面紧接着k行，每行对应一个测试例，含一个N位二进制串（1<=N<=20），代表数据。
Output
每个测试例对应一行输出，含一个5位二进制串，表示循环冗余码。
Sample Input
2
1101011011
10101010
Sample Output
01110
01001
Source
福建师范大学第三届程序设计比赛网上预赛
My Program
┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄它是华丽的分隔线
【题意简述】
对于输入的二进制数，在末尾加上4个0后用10011对其进行模2除法。并输出最后的结果（5位二进制码）。
【粗略分析】
由于C++中没有二进制的数据类型，因此采用字符串记录。
观察运算图可知，每次都取前5位对它进行模2除法。我们可以设定一个i = 0 to n-5，用来计算每一步。
我们还可以观察出，每次只有第i位为1时才会进行运算。所以我们加一个判定m[j]=='1'时才计算。
因为固定除数都为10011，我们直接将它列为数组，i=1 to 5 进行模2并存储回字符数组即可。
【C++源代码】
简单地模拟一下计算过程就可以了。