在电子通信领域,会用到很多二进制和“模2”运算。什么是“模”?与“进制”有什么不同?为什么需要使用模运算?

进制数讲解(通俗理解进制与)(1)

1、什么是进制?


“进制”就是数数(数一下有几本书)和计算时的一种“进位制度”系统。这个系统是人为制定的。

我们日常生活中使用的是“十进制”,电子通信领域大量使用“二进制”。

一种“进制”需要有一些规则,这些规则综合构成“进位制度”系统:

① 从0递增,每次递增都按照加1计算;(这是四则运算的前提)

② 可以递增到无限大;

③ 递增过程中,数字的位数随着“进制”增加;(构成一个数字的位,叫做权)

④ 数字只有一位的时候,这些数字被称作“进制”的基数;

⑤ 每种进制都有自己独有的“按进制”计算规则,也就是“进位”规则。

这5条规则是构成一种计数系统的前提。通常,最引人关注的规则就是“进位”规则。其他规则较少被注意到。但是,实际上,这5条规则中的任何一种规则被改变,都能产生一种新的计数系统。

如果仅有“进位”规则发生变化,其他规则不变,就会产生很多种“进制”,比如二进制、3进制、7进制甚至371进制。一般用到的是二进制。

可以认为:所有的其他“进制”都是十进制演变出来的,计数习惯和运算习惯都沿用十进制。

进制数讲解(通俗理解进制与)(2)

常见的十进制和二进制计算

上图的计算方法众所周知。但是如果跟“模运算”相比较的话,会发现很大不同。

2、什么是“模”?“模”和“进制”有什么不同?


如果说十进制是一个计数世界的话,二进制是另一个规则类似的子计数世界。构成两者的5条规则中,只有具体的基数和逢基进位是不同的,其他都相同。如果将第②条规则“可以递增到无限大”,改变成“仅可以递增到某个有限大的值”就产生了另一种计数世界,这就是“模”。

“模”,是一个比较“令人感到陌生”的名词,但是在生活中却很早就普遍使用了。如钟表的表盘。时间的长度是无限的,如果想把无限的时间长度数值放进表盘有限的刻度上,有一个简单的办法,就是让表示时间长度的数值不停地归0。

进制数讲解(通俗理解进制与)(3)

进制数讲解(通俗理解进制与)(4)

这个表盘数字世界就是“模12”。数字从0开始加1递增,递增到12,不进位而是归零。这与进制的处理方法截然相反。也是“模”与“进制”的最突出的区别。

从0到11的数字是十进制数字,可以称为“模元”,而数字12可以称为“模值”。(如果有相关的著作对这些名词有更加合适的称谓,请自行转换。)

模元可以是十进制数字,也可以是二进制或者其他进制数字。

模元之间的递增方式也可以不是按照加1递增。如果是这样的话,按模运算会与常规的运算不同。

至此,关于“模”的概念应该有一个大致的总结:

① “模”是一种数学计数系统,或者说一种计数模型;

② 模值可以按照自己的需要自由指定;

③ 模元可以是任何进制数字,递增方式可以不是加1递增;

④ 模内,数字递增到模值,不会进位,而是归零,重新递增。

用语言来描述的话,“模”就是一个封闭的圆形计数系统。

模与进制的区别是:

模,满则归零;

进制,满则溢出。

如何把任何一个数字放进已经定义好的模中呢?

把十进制数字215放在模12内:

进制数讲解(通俗理解进制与)(5)

就说215在模12内等于11。这个方法可以是定义模的办法。但是这样建立的模有两个前提条件:从0开始计数,每次按照加1递增。

如果模元不是从0开始,模元不按照递增排序,或者按照加某个数值递增,除模取余方法可能需要做一些改变。这种情况出现在某些编码中。

3、模运算原理


先看模12运算。

进制数讲解(通俗理解进制与)(6)

在模12中,

5 4=9;

5-8=9。

可以说,4和8是互补的。这也是二进制中“补数”的含义。

7乘以8,可以理解为从0点开始,指针顺时针走8次,每次走7格,最后指针指向数字8点。所以模12的7×8=8。

按模除法一般用于把任意数字放入定义好的模中,实际的用途类似于钟表的用途。

最简单的是“模2”。用一个表盘来描述模运算。

进制数讲解(通俗理解进制与)(7)

模2加:

0 1=1;指针从0点顺时针走1格,指向1点。

1 0=1;指针从1点顺时针走0格,指向1点。

0 0=0;

1 1=0;指针从1点顺时针走1格,指向0点。

由此定义了一种逻辑运算:异或。异或的运算符号为

进制数讲解(通俗理解进制与)(8)

,比较形象,意味着在一个圆圈内进行的加法运算。

模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放进这个模内,对应的模元就是除法的余数:

进制数讲解(通俗理解进制与)(9)

可以看出,二进制的按模计算不同于十进制的按模计算。二进制的按模计算过程中,对每一位使用“模2运算”。那么为什么要使用“模2运算”呢?

前面说了,模是一种为了实现某种目的人为定义的计数系统,按模计算方法也是人为定义的。在编码的过程中,可以不使用模2加法进行按模计算,但是如果统一使用模2加法能够让按模运算具有某些特殊性质,还能够大幅度降低硬件或软件的难度,为什么不用呢?

伟大的科学家发现了按模运算的一种特殊性质:

如果一个二进制数字T(x)以xn 1为模,每次T(x)按照乘2递增,则模xn 1内的模元是一组循环码组。

xn 1是一种二进制数的多项式表示法。表示二进制数字有n 1位,最高位和最低位都是1,其他位都是0。

这条性质能够用来建立CRC编码。如以10001为模值,建立一个模。用10011做被除数进行模运算:

进制数讲解(通俗理解进制与)(10)

进制数讲解(通俗理解进制与)(11)

,