在电子通信领域,会用到很多二进制和“模2”运算。什么是“模”?与“进制”有什么不同?为什么需要使用模运算?
1、什么是进制?
“进制”就是数数(数一下有几本书)和计算时的一种“进位制度”系统。这个系统是人为制定的。
我们日常生活中使用的是“十进制”,电子通信领域大量使用“二进制”。
一种“进制”需要有一些规则,这些规则综合构成“进位制度”系统:
① 从0递增,每次递增都按照加1计算;(这是四则运算的前提)
② 可以递增到无限大;
③ 递增过程中,数字的位数随着“进制”增加;(构成一个数字的位,叫做权)
④ 数字只有一位的时候,这些数字被称作“进制”的基数;
⑤ 每种进制都有自己独有的“按进制”计算规则,也就是“进位”规则。
这5条规则是构成一种计数系统的前提。通常,最引人关注的规则就是“进位”规则。其他规则较少被注意到。但是,实际上,这5条规则中的任何一种规则被改变,都能产生一种新的计数系统。
如果仅有“进位”规则发生变化,其他规则不变,就会产生很多种“进制”,比如二进制、3进制、7进制甚至371进制。一般用到的是二进制。
可以认为:所有的其他“进制”都是十进制演变出来的,计数习惯和运算习惯都沿用十进制。
常见的十进制和二进制计算
上图的计算方法众所周知。但是如果跟“模运算”相比较的话,会发现很大不同。
2、什么是“模”?“模”和“进制”有什么不同?
如果说十进制是一个计数世界的话,二进制是另一个规则类似的子计数世界。构成两者的5条规则中,只有具体的基数和逢基进位是不同的,其他都相同。如果将第②条规则“可以递增到无限大”,改变成“仅可以递增到某个有限大的值”就产生了另一种计数世界,这就是“模”。
“模”,是一个比较“令人感到陌生”的名词,但是在生活中却很早就普遍使用了。如钟表的表盘。时间的长度是无限的,如果想把无限的时间长度数值放进表盘有限的刻度上,有一个简单的办法,就是让表示时间长度的数值不停地归0。
这个表盘数字世界就是“模12”。数字从0开始加1递增,递增到12,不进位而是归零。这与进制的处理方法截然相反。也是“模”与“进制”的最突出的区别。
从0到11的数字是十进制数字,可以称为“模元”,而数字12可以称为“模值”。(如果有相关的著作对这些名词有更加合适的称谓,请自行转换。)
模元可以是十进制数字,也可以是二进制或者其他进制数字。
模元之间的递增方式也可以不是按照加1递增。如果是这样的话,按模运算会与常规的运算不同。
至此,关于“模”的概念应该有一个大致的总结:
① “模”是一种数学计数系统,或者说一种计数模型;
② 模值可以按照自己的需要自由指定;
③ 模元可以是任何进制数字,递增方式可以不是加1递增;
④ 模内,数字递增到模值,不会进位,而是归零,重新递增。
用语言来描述的话,“模”就是一个封闭的圆形计数系统。
模与进制的区别是:
模,满则归零;
进制,满则溢出。
如何把任何一个数字放进已经定义好的模中呢?
把十进制数字215放在模12内:
就说215在模12内等于11。这个方法可以是定义模的办法。但是这样建立的模有两个前提条件:从0开始计数,每次按照加1递增。
如果模元不是从0开始,模元不按照递增排序,或者按照加某个数值递增,除模取余方法可能需要做一些改变。这种情况出现在某些编码中。
3、模运算原理
先看模12运算。
在模12中,
5 4=9;
5-8=9。
可以说,4和8是互补的。这也是二进制中“补数”的含义。
7乘以8,可以理解为从0点开始,指针顺时针走8次,每次走7格,最后指针指向数字8点。所以模12的7×8=8。
按模除法一般用于把任意数字放入定义好的模中,实际的用途类似于钟表的用途。
最简单的是“模2”。用一个表盘来描述模运算。
模2加:
0 1=1;指针从0点顺时针走1格,指向1点。
1 0=1;指针从1点顺时针走0格,指向1点。
0 0=0;
1 1=0;指针从1点顺时针走1格,指向0点。
由此定义了一种逻辑运算:异或。异或的运算符号为
,比较形象,意味着在一个圆圈内进行的加法运算。
模2加法的特点可以描述为:
不同得1,相同得0。在编码中大量应用。
模2减:
0-1=1;指针从0点逆时针走1格,指向1点。
1-0=1;指针从1点逆时针走0格,指向1点。
0-0=0;
1-1=0;指针从1点逆时针走1格,指向0点。
可以看出,模2减和模2加,结果完全一样。所以在计算模运算的除法时,常常用加法直接代替减法。编码中我们只能看到模2加,看不到模2减,就是这个原因。
模2乘:
0×0=0;指针从0点顺时针走0次0格,指向0点。
0×1=0;指针从0点顺时针走1次0格,指向0点。
1×0=0;指针从0点顺时针走0次1格,指向0点。
1×1=1。指针从0点顺时针走1次1格,指向1点。
这就是逻辑“与”运算。和十进制的乘法思路一样。
模2除:
0÷1=0;
1÷1=1。
可以看出,以2为模,其实模元并不是二进制,而是在十进制基础上定义的一种模。只不过模2比较特殊。
一种比较特殊的按模除法,在二进制基础上定义的模。如二进制数字1100100除以1011定义的一种二进制模,模值为1011。应该称之为“模1011”。如果把1100100放进这个模内,对应的模元就是除法的余数:
可以看出,二进制的按模计算不同于十进制的按模计算。二进制的按模计算过程中,对每一位使用“模2运算”。那么为什么要使用“模2运算”呢?
前面说了,模是一种为了实现某种目的人为定义的计数系统,按模计算方法也是人为定义的。在编码的过程中,可以不使用模2加法进行按模计算,但是如果统一使用模2加法能够让按模运算具有某些特殊性质,还能够大幅度降低硬件或软件的难度,为什么不用呢?
伟大的科学家发现了按模运算的一种特殊性质:
如果一个二进制数字T(x)以xn 1为模,每次T(x)按照乘2递增,则模xn 1内的模元是一组循环码组。
xn 1是一种二进制数的多项式表示法。表示二进制数字有n 1位,最高位和最低位都是1,其他位都是0。
这条性质能够用来建立CRC编码。如以10001为模值,建立一个模。用10011做被除数进行模运算:
,