精华内容
下载资源
问答
  • 二进制模2除法(CRC校验)

    万次阅读 多人点赞 2018-11-12 11:48:57
    二进制模2除法与二进制除法不同。 模2运算:加法不进位,减法不借位。 二进制除法: ... 带借位的二进制除法,根据...实际上,在CRC运算中,总能保证除数的首位为1,则模2除法运算的商是由余数首位与除数首位的...

    二进制模2除法与二进制除法不同。

    模2运算:加法不进位,减法不借位。

    二进制除法:

           带借位的二进制除法,根据余数减除数够减与否,确定商1还是商0,若够减则商1,否则商0。

    二进制模2除法:

          采用模2减法不带借位的二进制减法,因此考虑余数够减除数与否是没有意义 的。实际上,在CRC运算中,总能保证除数的首位为1,则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定。因为除数首位总是1,按照模2 除法运算法则,那么余数首位是1就商1,是0就商0

    (1)一步步的计算方法:

        模2除法与长除法类似,但有个特点:不借位。说白了就是按位异或,相同为0,不同为1。 
    它有三个原则: 
       1、除数与被除数最高几位(与除数位数相同)做异或,商1。(除数首位必须为1) 
       2、余数先去掉首位,若此时余数最高位为1,商1,并对以它为除数继续模2除。 
             若最高位为0,则商0,重复步骤2。 
       3、直到余数位数小于除数位数时,运算结束。 

    (2)熟悉规则之后,比较简洁的方法

          1、当余数位数与除数位数相同时,才进行异或运算,余数首位是1,商就是1,余数首位是0,商就是0。

          2、当已经除了几位后,余数位数小于除数,商0,余数往右补一位,位数仍比除数少,则继续商0,当余数位数和除数位数一样时,商1,进行异或运算,得新的余数,以此至被除数最后一位。

     

     

     

    展开全文
  • 主要就是CRC中用到的2运算二进制/十进制除法有别,前者是特殊的除法,甚至根本不是除法,就是异或。 CRC循环冗余检验:余数为0就没出错;不能确定哪几个比特出错了 看来必然是要增加开销的,没有白吃的午餐,...


    复习网络,不小心碰到差错控制的CRC冗余码计算,随便算了一下,发现自己算的不对,于是发现了一串知识,总结如下。主要就是CRC中用到的模2运算和二进制/十进制除法有别,前者是特殊的除法,甚至根本不是除法,就是异或。

    CRC循环冗余检验:余数为0就没出错;不能确定哪几个比特出错了

    在这里插入图片描述
    看来必然是要增加开销的,没有白吃的午餐,难怪名字叫做“冗余”呢
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    就是发送方先把冗余码的位置放n个0,然后把整个数据(k+n)位作为一个数字,除以(用的是模2除法,很重要!!不是常规除法)一个事先准备好的除数p(n+1位),除下来的余数R就是n位的,这n位余数就作为发送方的CRC循环冗余码。

    到了收方,就拿收到的数字除以相同的除数P(大概是协议规定好的P),余数为0就代表没出错

    对每一帧都要校验一下

    也不是100%会检测正确,也有概率检测的结果不对,冗余码的位数越大,结果才能越准确,检测错误的概率才会小

    二进制除法(和十进制除法其实一样!)

    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    模2除法(不同于二进制除法!本质就是异或而已)

    这篇博客点醒了我
    一直看不明白CRC冗余码的计算过程,,花了一个多小时研究,之前以为上面的描述是说十进制除法,自己的例子和ppt的例子都推不通,看了很多网页,以为是二进制除法,结果发现二进制除法本质和十进制除法是一样的,得到的结果也是一样的。。。

    后来终于明白了,CRC计算中说的除法,根本不是十进制或者二进制除法,而是模2除法,这是一种特殊的除法,基本也只在CRC冗余码的计算中才会用到,别的地方不用。

    模2除法的重点是(只要掌握了这几个点,就可以打通模2除法的经脉了,不再彷徨疑惑):

    • 不考虑进位
    • 等同于按位异或,虽然名字是除法,实际上根本和常规除法不是一回事,本质就是异或而已。比如商的判定不是根据余数和除数的大小来判定,而是根据余数的首位是0还是1,如果余数首位是0那就商1,如果余数首位是1那就商0。

    为何余数首位是1,则商为是0呢?
    因为其实商是余数首位和除数首位的异或,但是除数一直都不变且其首位一定是1啊,所以自然就是余数首位为1,商就是0咯

    • 商的第一位由被除数决定:被除数的首位如果是1,则商的最高位就是1,否则是0。
    • 计算过程中,如果余数的首位不是0,则不可以右移,即不能从被除数中再取一位下来,且这一位的商也就为0;只有余数首位是0,才可以再取一位下来,且这一位的商就是1。所以也可以说是根据是否可以右移来判断商是0还是1的,可以右移则商1。

    可以看到异或运算在IT领域是多么重要

    在这里插入图片描述在这里插入图片描述

    可以看到:

    • 模2除法的每一位的计算是完全独立的,就是异或,根本没有什么进位借位的事儿
    • 如果余数首位为1,则商为0,且再和除数异或一次,第二次的余数首位一定为0了,但是这一次只右移,并不得到商。所以上面的例子中做了8次异或运算,但是只有6位商,因为其中有两次的余数是1.
    • 模2运算中除数和余数用的是异或;二进制和十进制除法中除数和余数用的是减法

    收方收到数据后:
    在这里插入图片描述

    余数是0,所以没出错,接收。

    展开全文
  • 二进制模2除法(CRC循环冗余检验)

    千次阅读 多人点赞 2019-05-20 00:08:03
    一、二进制模2除法运算规则 被除数为1则商为1,被除数为0则商为0; 余数去掉首位为新的被除数; 新的被除数以0开头,则除数变为全0,以1开头则除数不变; 二、举例 101001000 / 1101 ...

    一、二进制模2除法运算规则

    • 被除数为1则商为1,被除数为0则商为0;
    • 余数去掉首位为新的被除数;
    • 新的被除数以0开头,则除数变为全0,以1开头则除数不变;

    二、举例

    101001000 / 1101

    三、CRC循环冗余检验

    1、 符号

    符号 解释
    k 要发送的数据的比特位数
    M 要发送的原始数据
    冗余码位数
    P 除数
    Q
    R 余数

    2、过程

    • 假设待传送的一组数据 M = 101001(现在 k = 6)。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送,即发送的数据长度为k+n位。

    • 用二进制的模 2 运算进行 2n 乘 M 的运算,这相当于在 M 后面添加 n 个 0

    • 得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P,得出商是 Q 而余数是 R,余数 R 比除数 P 少1 位,即 R 是 n 位。

    3、举例

    k=6	 M=101001  n=3  P=1101
    

    那么得到被除数( M 后面添加 n 个 0)为101001000,除数为1101,进行二进制模2除法运算,结果为商 Q=110101余数 R=001(过程参考上面的二、

    把余数 R 作为冗余码添加在数据 M 的后面发送出去。
    因此发送的数据为101001001,共(k+n = 9)位。

    展开全文
  • 2除法二进制除法

    2021-05-08 14:04:58
    2除法二进制除法 二进制加减乘除与十进制的如出一辙,“2和”、“2减”,名称、算法虽然不一样,但是,结果是相同的,实际上都是两个二进制数字相“异或”。 异或运算: 如果两个二进制数字相同,“异或”的...

    模2除法与二进制除法

    二进制加减乘除与十进制的如出一辙,“模2和”、“模2减”,名称、算法虽然不一样,但是,结果是相同的,实际上都是两个二进制数字相“异或”。

    异或运算:
    如果两个二进制数字相同,“异或”的结果就是0;
    如果两个二进制数字不同,“异或”的结果就是1。

    “模2除”在“循环冗余校验(CRC)”中,有广泛的应用。
    在这里插入图片描述

    展开全文
  • 文章目录知道两个概念2和2减两种不同的二进制除法除法模2除法CRC 循环冗余校验编码过程差错检测能力 谈CRC循环冗余校验的之前,先把二进制除法说一下,先回忆一下十进制之间的除法是如何运算的, 这个式子在做...
  • 在讲模二除法之前,我们先看看按位异或运算。如下即二进制1101b异或1010b的结果为0111b。 按位异或是一种二进制运算,只影响当前位,因此我们可以得出两个简单的定律:交换律和结合律。 A⊕B⊕C=A⊕(B⊕C) 例如...
  • 与四则运算相同,2运算也包括2加、2减、2乘、2四种二进制运算。而且,2运算也使用与四则运算相同的运算符,即“+”表示2加,“-”表示2减,“×”或“·”表示2乘,“÷”或“/”表示2。...
  • 包含测试代码原理就是:枚举二进制余数中1的位置 +二分搜索。O(32*32)不过此算法可以加上两重的二分搜索。时间复杂度会更优。#include<stdio.h>#include<stdlib.h>#include<iostream>#include<...
  • 编辑:原则上,不同数量系统之间的转换是重复的“除法,余数,乘法,加法”运算.我们来看一个例子:我们想将123从十进制转换为基数为3的数字.我们做什么?>取余数3 – 将这个数字加到结果前面.>除以3.>如果数...
  • 前一篇我们介绍了模2运算的加减乘除运算 ,虽然,我们了解了模二运算的基本法则,但是,如果每次都要计算,那就未免觉得太繁琐,所以,这里我总结了一套自己的运算心得供大家学习。接下来,我们就要讲解一下如何基础...
  • 与四则运算相同,2运算也包括2加、2减、2乘、2四种二进制运算。而且,2运算也使用与四则运算相同的运算符,即“+”表示2加,“-”表示2减,“×”或“·”表示2乘,“÷”或“/”表示2。...
  • 2除法

    2021-04-22 14:40:36
    异或 运算法则相当于不带进位的二进制加法 同1异0 问题引出 CRC循环冗余检测中需要使用2除法
  • 2运算得到这个数二进制序列中的最低位,2去掉这个数二进制序列中的最低位。当这个数进行2运算的结果为1时,那么它的最低位就是1,然后再进行2运算,将倒数第二位的数置为最末位,如此循环,当这个数为0时,...
  • 一个二进制序列通过2运算,可以求得它的最末位数字,通过2运算,可以去掉最末位的数,如此循环,如果2的结果是1,那么给计数器加1,最后输出计数器的值,即出现1的个数。但这种方法只能求一个正数二进制序列...
  • 题目:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。...首先除法的效率比移位运算要低得多,在实际编程中应尽可能地用移位运算符代替乘除法。下面主要写一下剑指Offer的拓展题 相关题目:
  • 昨天看到一个有意思的题目,不用除法和求模运算,判断一个数能否被3整除。这个问题,网上有人给了一个答案,但是该答案并不正确(读者可以自己去网上搜一下这个题目,可以看到该答案)。本文提出一个思路,与...
  • 注意:求冗余码所用的二进制除法2除法2除法需要用到2减法,而2减法跟2加法类似,是不带进/借位的运算2减法规则: 0-0=0; 1-1=0; 0-1=1;//无需考虑借位 1-0=1;//同上 课后例题 3-07 要发送的数据...
  • 解法一:利用除法和求模运算。计算机中的求模运算比较耗时。 template int Count(T v) { int num = 0; while (v) { if (v % 2 == 1) { ++num; } v /= 2; } return num; } 解法:利用位...
  • 2运算百度百科

    2020-10-30 14:13:24
    与四则运算相同,2运算也包括2加法、2减法、2乘法、2除法四种二进制运算。与四则运算不同的是2运算不考虑进位和借位,2算术是编码理论中多项式运算的基础。2算术在其他数字领域中的应用也是很广泛的...
  • 2运算的加减乘除运算

    千次阅读 2020-05-05 12:30:43
    与四则运算相同,模二运算也包括模二加法、模二减法、模二乘法、模二除法四种二进制运算。与四则运算不同的是模二运算不考虑进位和借位,模二算术是编码理论中多项式运算的基础。模二算术在其他数字领域中的应用也是...
  • 编程之美——求二进制数中1的个数

    千次阅读 2012-10-17 10:34:07
    1. 循环利用除法模运算。该方法最容易想到。可谓没有技术含量的。 2. 循环利用位移和按位与。用位操作代替算术运算,提高效率。 3. 只考虑数字中的1。有经验规律知:对于2的方幂N与N-1取与为0.因而,可以利用该...
  • CRC(循环冗余校验码)中的2除运算

    千次阅读 2012-05-21 15:28:24
    CRC里的除法不是简单的二进制除法,不信用附件里的计算器算出的结果与它的结果不一样。 CRC的二进制除法是这样的: 1111000 被除数 1101 除数 ———— 够除数的位数,商1 0010 余(除数与被除数前4位求异或得到的)...
  • 2运算是一种二进制运算,与普通的四则运算相同,2运算也包括2加法、2减法、2乘法、2除法。但是与普通四则运算不同的是,2运算不考虑进位和借位,两个二进制位相运算的时候,这两个值就能确定出结果,...
  • 2运算

    2012-03-10 20:17:25
    2运算的原理 2加法,2减法,2乘法,2除法 ...2运算是一种二进制算法,CRC校验技术中的核心部分,因此,我们在分析CRC算法之前,必须掌握2运算的规则。与四则运算相同,2运算也包括2加、...
  • 2运算的原理

    千次阅读 2015-08-02 14:24:22
    2运算的原理 2加法,2减法,2乘法,2除法 2运算是一种二进制算法,CRC校验技术中的核心部分,因此,我们在分析CRC算法之前,必须掌握2运算的规则。与四则运算相同,2运算也包括2加、2减、2...
  • CRC校验码之模二算法

    2020-02-28 20:37:01
    最近复习计算机网络相关的知识,学到CRC校验码时用到了模二除法,于是在回过头去重新温习了一下模二算法 百度百科对模二算法的解释是 模2运算是一种二进制算法,CRC校验技术中的核心部分。与四则运算相同,模2运算...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 171
精华内容 68
热门标签
关键字:

二进制模二除法运算