企业网站建设项目计划书相册网站怎么做的

当前位置： 首页 > news >正文

企业网站建设项目计划书,相册网站怎么做的,长春网站建设论坛,福步外贸论坛登录循环冗余校验码 CRC 码 循环冗余校验码 (cyclic redundancy Check, CRC) 十进制除法 从熟悉的十进制出发#xff0c;假设现在你要给另一个人传送882这样的一个10进制数据#xff0c;为了防止传送数据的过程中某一个数据发生错误你可以和你的另一个小伙伴约定一个除数…循环冗余校验码 CRC 码 循环冗余校验码 (cyclic redundancy Check, CRC) 十进制除法 从熟悉的十进制出发假设现在你要给另一个人传送882这样的一个10进制数据为了防止传送数据的过程中某一个数据发生错误你可以和你的另一个小伙伴约定一个除数比如7 882÷7刚好是除的尽的最后我们算得的余数是等于0当数据的接收方接收到数据的时候就可以用它接收到的这个数据和你们约定的这个除数进行一个除法操作检查余数是否为0如果余数不等于0那么是不是就可以确定数据传输的过程中肯定是发生了错误比如说对方收到的其实是883也就是最后一个数发生了错误那883÷7最后可以算的余数1不等于0那么这就说明肯定是发生了错误需要重新传送再比如第2个数据发生了错误, 由8变成5(即852)那么除以7得到的余数是等于5同样这种情况也可以确定我们的数据传输肯定出现了问题这是我们熟悉的十进制除法总结一下 我们通过约定一个除数然后在接收到数据之后与这个除数进行相除的操作检查余数是否发生了改变, 用这样的方式就可以检测出数据传送的错误
基本思想 其实CRC的思想和十进制除法的思想是类似的 就是数据的发送方和接收方会先约定一个除数当然了我们处理的是计算机里面的数据, 所以这个数肯定是一个二进制的数然后我们会想办法在K个原始的信息位后面加上R个校验位我们需要确保拼接上这R个校验位之后这一整串的数据和我们刚才约定的除数进行相除的操作余数要等于0接下来数据的接收方接收到这 KR 位的数据之后需要用二进制除法来检查余数是否等于0如果余数不等于0那么就说明有一些二进制位出现了错误那这种情况下我们就可以进行重传或者某些时候也可以进行单比特位的纠错这就是循环冗余校验码的一个思想 如何检错纠错 检错 构建循环冗余校验码需要有这样的两个关键的要素一个是除数一个是被除数一般来说试题中会用这种生成多项式的方式给出除数比如例题如下设生成多项式为 G(x)x3x21G(x)x^3x^21G(x)x3x21, 信息码为101001求对应的CRC码 其实这题可以描述为1∗x31∗x20∗x11∗x01 * x^3 1 * x^2 0 * x^1 1 * x^01∗x31∗x20∗x11∗x0可见在这个生成多项式中这些项的系数要么为1要么为0因此我们可以把这个生成多项式转换成对应的二进制数, 即1101这一题的核心在于确定K、R以及生成多项式对应的二进制码一般而言 K 信息码的长度R 生成多项式最高次幂在这里题目中是3 这样的话校验码位数 N K R 6 3 9由上面的换算可知我们的二进制码有4个比特也即是1101思路6位信息位3个校验位生成的9位校验码除以对应的二进制码所得余数要为0因此接下来我们需要确定的是添加的这三位校验位应该是多少才能保证余数为零做法是这样的 把信息码左移R位也即是3位即101001000接下来就是相除的操作101001000 / 1101, 这个除法会让我们得到R位的余数也就是3位余数不过这个地方我们需要进行的是模2除的运算和我们普通的除法是有一些区别的, 后续来说明
注意体会模2除和模2减 首先由于除数有4位所以我们会取被除数的高四位与他先商一次模2除里取商的方式比较特别我们只看当前我们划出来的最高位如果它是1那么我们就商 1那1×10011001我们把它填到下面接下来我们会对后三位进行模2减的运算其实模2减的效果和模2加是相同的模2加其实就是异或运算所以事实上我们就是对后边的三位进行了异或运算先看0和1异或等于11和0异或等于10和1异或同样等于1因此后边三位进行模2减或者说分别进行异或得到的结果是111接下来有点类似于十进制除法我们把被除数的后面一位补到刚才得到的这个余数的低位, 得到 1110然后我们要确定下一位的商和之前一样我们只看最高位如果最高位为1的话那我们就商1同样的 1 × 1101 1101, 接下来我们需要对后面的三位进行一次模2减的运算那1和1进行模二减就相当于它们俩进行了一次异或等于01和0异或等于10和1异或等于1所以这次模2减得到的是011接下来再补一位凑足四位现在由于这儿的高位为0所以接下来我们应该商0那么0 × 1100 0000所以我们在下边写上4个0接下来同样的我们需要把后三位进行模2减或者说异或的运算得到三个1现在由于高位是1所以下一个商我们应该商1得到1101后三位进行模2减得到011再补一个0现在由于高位是0所以我们需要商0因此接下来需要减0000后三位进行模2减得到110最后还剩一个0我们在把它补上去由于此时高位为1所以我们要上商1那么和1101的后三位进行模2减得到的结果是001那001就是我们刚才的这一串代码和1101进行模2除得到的一个余数用模2除的规则最终得到的余数位数应该只比这个除数少一位那我们用这些操作得到的余数就是我们的校验位所以最终我们得到的CRC校验码就应该是前6个信息位101001再拼上最后的校验位001即101001001这就是校验位的一个确定方式用这种方式确定的校验码和1101进行模2除得到的余数一定是000现在我们已经有了校验码那么我们就可以把一整串的信息进行传输发送接收方接收到数据之后就需要进行检错和纠错注意发送方和接收方提前已经约定好了生成多项式或者说约定好了除数当接收方接收到数据之后就可以用接收到的这一串信息和刚才约定好的这个除数进行模二除的运算如果最终得到的余数是000。那么就代表没有出错注意上图接收出错的地方最终得到的余数应该是010这里会发现一个巧合我们得到的这个余数如果把它翻译成十进制的话刚好就是2而出错的位置刚好也是C2C_2C2​这个位置但其实这语速和出错位置之间并没有这样必然的联系 把原始的这一串数据各个位置进行了一个改变如果出错位在第1位的话那么和这个生成多项式进行模2除得到的余数是001如果是第2位, 那得到余数是010, 如果出错的位置是第3位那得到的余数是100如果把100翻译成十进制的话是等于4所以这个余数的值和出错位置之间其实并不是二进制到十进制的转换这么简单但是余数和出错位置确实又有对应关系我们会发现这儿的余数只有三个bit的信息而3个bit的信息总共只能表示2的三次方也就是8种状态如果余数等于三个0那么表示这个数据的传输是正确的接下来出错位为1234567这7种状况分别会对应不同的余数那这7种余数再加上000, 已经把3个bit能够表示的信息都表示了所以我们再看如果第8位出错的话余数又会等于001然后如果是第9位出错的话余数又等于010也就相当于这个余数又从头来了一遍第1个是001第2个是010所以如果余数等于010就可以确定是第2位出错了吗这个结论显然是站不住脚的因为第9位出错也有可能会导致余数变为010因此刚才那句话我们划了一条横线表示他并不严谨并不正确 纠错 那既然如此是不是意味着循环冗余校验吗它只有检测的能力而没有纠错的能力也就是无法确定出错的位置在哪这种理解也不全对像刚才这个例子当中由于我们信息位加校验位总共有9位而校验码只有3位的信息3位的信息最多只能表示8种状态无法完全的标注出这9个位置, 到底是哪一个位置发生了错误所以并不是循环冗余校验码没有纠错的能力而是这个例子当中信息位太长了所以我们再看另一个例子, 如果信息位只有4位然后生成多项式和之前是一样的除数1101如下 信息位0100生成多项式G(x)x3x21(1101)G(x)x^3x^21 \quad (1101)G(x)x3x21(1101) 首先我们的信息为后面补三个0得到 0100000, 然后用这一整串对1101进行模2除运算得到余数011所以最终得到的CRC码就应该是这4个信息位再拼接上011这三个校验位即0100011接下来如果这串数据传输过程中没有任何一位发生错误, 那显然余数应该是等于零如果发生错误了如下表所示 如果第1位发生错误那余数是001如果是第2位发生错误余数是010第3位是100…同样余数和出错位置之间的这个对应关系与上一个例子当中并没有发生任何改变所以这也就意味着只要我们确定了一个生成多项式无论我们的信息位如何变化最终这个余数的值和出错位置之间肯定都是一种固定不变的对应关系而如果数据的位数并没有超过余数所能表示的这个范围那么余数和出错位之间就是一一对应的关系在这个例子当中如果余数等于010那我们就可以确定出错的一定是第2位于是我们只需要纠正第2位就可以了所以循环冗余校验码其实是有纠错功能的只不过信息位的位数不能太多那到底要多少个信息问才不算多呢这儿给出了一个不等式 2R≥KR12^R \ge K R 12R≥KR1 这个和海明码的不等式是很类似的我们有R个校验位就意味着最终我们会得到R位的余数而这么多位的余数可以表示2的R次方这么多种状态其中有一种状态也就是余数为000这种状态是对应正确的状态然后剩下的2R−12^R-12R−1这么多种状态需要分别对应上KR这么多位每一位出现错误的那种情况需要进行一一对应所以如果能够满足 2R≥KR12^R \ge K R 12R≥KR1 那么CRC校验码就拥有可以纠正一位错误的能力不过在实际应用当中CRC码这种方式通常用于计算机网络的数据传输通常会把几千个比特的信息位加上几个校验位所以在实际使用当中这种校验码通常只会用来检错而不会用于纠错我们需要知道的是它实际上是有纠错能力的理论上这种校验码它可以检测出所有的奇数个错误同时可以检测出所有的双比特错误另外它可以检测出小于等于校验位长度也就是小于等于R位的连续的错误 总结 循环冗余校验码 构造 由生成多项式确定除数,若生成多项式中x的最高次为R则除数有R1位K个信息位 R个0作为被除数被除数、除数进行模二除得R位余数K个信息位R位余数 CRC码 校验 收到KR位数据与生成多项式模2除计算R位余数余数为0说明无错误余数非0说明出错 检错、纠错能力 可检测出所有奇数个错误可检测出所有双比特的错误可检测出所有小于等于校验位长度的连续错误若选择合适的生成多项式且 2R≥KR12^R \ge K R 12R≥KR1则可纠正单比特错