模2运算是一种二进制算法,不考虑进位和借位,即模2加法是不带进位的二进制加法运算,模2减法是不带借位的二进制减法运算。一、模2加法两个序列模二相加,即两个序列中对应位相加,不进位,相同为0,不同为1。
1+1=0 0+0=0 1+0=1 0+1=1(相同即为0,否则为1)例如:
0 1 0 1+ 0 0 1 1──────
0 1 1 0
二、模二减法减法和加法一样,按加法规则运算。0-0=0 1-1=0 0-1=1 1-0=1(相同即为0,否则为1)例如:
0 1 1 0
-0 0 1 1
──────
0 1 0 1
三、模二乘法多位二进制模2乘法类似于普通意义上的多位二进制乘法,或者是十进制乘法。不同之处在于后者累加中间结果(或称部分积)时采用带进位的加法,而模2乘法对中间结果的处理方式采用的是模2加法。0×0=0 0×1=0 1×0=0 1×1=1(除11为1外,其余都为0)例如: 1 0 1 1
× 1 0 1
——————
1 0 1 1
0 0 0 0 1 0 1 1—————— 1 0 0 1 1 1
四、模二除法多位二进制模2除法也类似于普通意义上的多位二进制除法,但是在如何确定商的问题上两者采用不同的规则。后者按带借位的二进制除法,根 据余数减除数够减与否确定商1还是商0,若够减则商1,否则商0。多位模2除法采用模2减法,不带借位的二进制减法,因此考虑余数够减除数与否是没有意义 的。实际上,在CRC运算中,总能保证除数的首位为1,则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定。因为除数首位总是1,按照模2 除法运算法则,那么余数首位是1就商1,是0就商0。在下面的示例中,当余数位数与除数位数相同时,才进行异或运算,余数首位是1,商就是1,余数首位是0,商就是0。当已经除了几位后,余数位数小于除数,商0,余数往右补一位,位数仍比除数少,则继续商0,当余数位数和除数位数一样时,商1,进行异或运算,得新的余数,以此至被除数最后一位。例如:1111000 除以1101,模2除法的商为1011,余数为111.
#第一步 1111000 1101 0010000 ----余数,商为1,只要第一位非0商就是1 #第二步,每步移一位,当起始位为0时,除以0;为1时除以除数。 010000 0000 010000 ----余数,商为0,只要第一位是0商就是0 #第三步 10000 1101 01010 -----余数,商为1,这里的余数你猜出,其实就是对应位异或 #第四步 1010 1101 0111 ------余数,商为1,如果位数比除数还小,不再继续运算 #最终余数为111,商为1011