数制与编码规则

计算机系统中的数制

进位计数法

我们在计算时都使用的是进位计数法，即数制相加到最大值时要进一位。这里我们最熟悉的就是十进制的进位了。但是在计算机系统中我们使用的是机器语言，所以是二进制的进位计数。如下：

思考：为什么要采用二进制，他有什么特点？

二进制只有0/1位，方便对应到物理器件的状态，如通电/断点，或者高电位/低电位。并且我们发现每个数的位可以对应一个可以使用的符号，比如二进制每一位只能用0或者1，而16进制每一位都有15中可能的符号，基数小的进制很长，比如在二进制中表示一个数时通常需要很多位，而十六进制基数很大，所以就很短。但是运算时，二进制只有与，非，或，异或四中运算情况，而对于更大的进制比如十进制都有100以上的运算情况，很明显二进制虽然长了一点，但是运算起来更加简便，计算性能也就更高，所以计算机采用的是二进制。

进制转换

其他进制转10进制

那么接下来我们来看一下如何实现进制转换，这里我们先来具体了解一下一个进制是如何表示一个数的，实际上符号位的数值是系数，他所在的位数表示的是位权，比如：

$$二进制：101.1=1*2^2+0*2^1+1*2^0+1*2^{-1}=5.5$$

$$四进制：11.2=1*4^1+1*4^0+2*4^{-1}=5.5$$

$$八进制：5.4=5*8^0+4*8^{-1}=5.5$$

$$十进制：5.5=5*10^0+5*10^{-1}=5.5$$

$$十六进制：5.8=5*16^0+8*16^{-1}=5.5$$

这里一定要注意小数点后面的位权分别是-1,-2,-3…，前面的位权是0,1,2,3…并且我们发现确实101.1中的’1’,‘0’,‘1’,'1’1’都是系数，他们所在的数值串的位置决定了他们的位权。那么我们现在会将各种进制转换成了10进制了，但是如果我们想要将10进制转换成其他进制怎么做呢？这里我们回忆一下初中学过的连除法。

10进制转其他进制

我们一定要注意连除法对于小数点前的数是除到商为0在停止，并且最后是倒序着将余数排列成串，小数点后的数是不断乘，直到小数点后面全零，然后顺序着将小数点前面的数排列成串在拼接。比如：

将23.25转换成二进制，那么转换方法如下：

同理如果要转换成4进制，那么就是不断除以4和不断乘4，如果是8进制就是不断除以8和不断乘8。

其他进制转其他进制

这个办法就比较麻烦啦，我比如四进制的11.2转换到二进制，那么就只能先将四进制的11.2转换成十进制的5.5，然后再转换成二进制的101.1了。即上面两种方法的总和使用，关键就是以10进制为跳板。并且无论是哪种进制转换，重点要掌握小数的转换方法。

或者使用如下方法：n进制就是位一组表示一个数，比如：

因为四进制一位等于二进制的两位，所以二进制串中从低位（靠近小数点）开始每两个组成一个数就是四进制的数，如果位数不足就补零。比如八进制和16进制，都是从靠近小数点的地方开始组合，到两边时位数不够了就要补零来凑。

真值和机器数

实际上数还有正负之分，所以一般要去一个符号位来表示正负，0表示正数，1表示负数：

所以15的机器数应该是01111也写成0,1111，这个都好只是用来隔开符号位的，实际上在机器中并不存在，-8就要写成11000。而对于一个二进制数到底是解码成一个纯正整数还是负数就要看变量是如何声明的了。比如11000如果看成是一个纯正整数unsign int 那么就是+24，如果是一个负数那么就是-8。

BCD码

我们发现实际上对于计算机一般的计算就是将我们输入的十进制的数转换成二进制计算然后在输出十进制的形式，所以大部分的计算都在二进制和十进制中发生，所以我们需要一种更好的二进制与10进制的转换表示方式，既能够快速方便计算机处理又可以方便于人类理解，所以产生了BCD码。如下：

BCD码规定了各位的权值不再是2^n-1，而是特定的4个位为一组表示一个十进制数，这个四个位权从高到低排列是8,4,2,1。什么意思呢？查看下表：

那么根据BCD码的计算规则，我们可以得到以上的表中数值对应的BCD码是这样产生的

$$1=0*8+0*4+0*2+0*1=1$$

$$8=1*8+0*4+0*2+0*1=8$$

并且当1+8时上面的BCD码也可以正确表示

$$1+8=0001+1000=1001=8*1+0*4+0*2+1*1=9$$

这样的方法既能够方便计算机计算，同时我们也可以轻松的通过二进制串读出具体的数值。但是我们知道BCD码规定是4位组合成一个十进制数，但是我们知道在二进制的4位组合下可以有16中组合，即还有6中冗余无效的二进制串：

上面这六个是非法无意义的BCD码，规定当相加后的串落入以下区间时，就要加上0110产生的新BCD码为结果，既保证了不能一次性用四位二进制串表示10以上的数，这样BCD码中的四位二进制位总是对应着一个十进制0~9的数，就符合人类思维了。所以：

我们发现当5+8用BCD计算后结果为1101落入了非法映射中（即虽然确实此时读还是能读出13，但是表示是非法的，因为我们规定一个四位组合只能表示0~9）所以，加上一个0110，这样1101+0110=10011，我们在从地位划分四个四个组合就是0001和0011也就是13。这就是BCD码的表示方法，这种方法比较常见，需要牢记。同时还有余3码和2421码等，可以了解即可。

计算机系统中的编码

字符与字符串的ASCII码

最常见的就是表示字符和字符串的ASCII码了，他将每一个键盘上的字符都对应着一个可以用7位二进制编码表示的数。如下:

其中我们可以将128个字符划分一下区域：

• 可印刷字符 32~126

• 数字 48（011 0000）~57（011 1001）

  注意：这里去掉高三位后面四位其实就是0~9的二进制表示

• 大写字母 65（100 0001）~90（101 1010）

• 小写字母 97（110 0001）~122（111 1010）

我们这里熟背0对应的ASCII码是48，A对应的是65，a对应的是97。我们要回推算不同字母或者数字的ASCII码，比如我们已知A的ASCII码是65，那么字符‘H’存放在了某存储单元M中，那么M中存放的内容是什么？

我们可以确定M中存放的是H的ASCII码，而我们又知道了A的ASCII码是65，H是第八个字母，所以H的ASCII码为65+(8-1)=72=1001000所以M中存放的内容是0100 1000。这里一定注意存储单元的内容都是按字节存储，所以必须是Byte的整数倍，也就是必须是8位的整数倍表示，所以这里应该用八位表示。

大端模式和小端模式

我们这里在讨论一下字符串的字符存储模式，大端模式就是存储单元内先存储高位字节，后存储低位字节的顺序，即我们正常的理解的顺序存储，比如假设我们现在有一个存储区，他的每个存储单元可以放4B，那么IF_A>B_THEN_READ©_这句话存储后就是这样：

就是从左往右，高位存高位字节，低位存低位字节。对应的ASCII码就是：

但是如果是小端模式，那么就是存储单元内先存储低位字节，后存储高位字节的顺序，即每个存储单元（4个格，这一行）都是倒着存的，如下：

每一行都是从右往左，从存储单元低位到高位分别存储字符的高位到低位。

奇偶校验码

就是将校验码分为有效信息位和奇偶校验位，奇校验码就是要保证校验码中1的个数为奇数，而偶校验码就是要保证校验码中1的个数为偶数：

比如上图中的1001101的奇校验就是奇偶校验位上要加上一个1使得整体的1的个数是奇数，而偶校验就是要在1001101前面加上一个0这样保证了整体1的个数是偶数个。这种方法有两种可供选择的校验规律，一般是用来检验信息位的奇数位是否出错，但是无法纠正错误，因为只是知道1的个数不对，具体哪里错了无从得知，常用于检验存储器数据的检查和传输数据的检查。但是局限性较强，所以一般使用更好的方法。重点掌握奇校验码和偶校验码的求解。

海明校验码

海明校验码更加科学，他实际上就是一种特殊地组合方式使得可以组成多组奇偶校验码组，从而可以既能发现错误，同时还可以根据海明码得知是第几位出错从而完成检验以及纠正的功能，具体为什么这样做，我现在还没想明白，但是不影响我们解题。这里就介绍以下方法。

首先回忆之前的奇偶校验我们知道一般设置一位（1bit）的校验位即可，但是这里我们需要要求信息为和校验位满足一个要求：

确定海明码的位数

实际上就是确定信息为何校验位是否满足一个可以组成海明码的条件关系，假设现在这个海明码有n个信息为，k个校验位，那么必须满足下面的条件才可以形成用来校验的海明码：

$$n+k<=2^k-1或者也可以表示为2^k>=n+k+1$$

我们来简单理解一下这个式子以便加深印象，2^k表示的是加上了k个校验码后最多可以检验出多少种错误情况，而n+k+1表示的是在一个n+k位的组合海明码会可以形成n+k+1中形式，那么也就是说n+k位的海明码可能有n+k个错误情况以及1中正确情况，而我们的校验码可以检验的最多情况是2^k，所以当且仅当2^k>=n+k+1时这个n+k位的海明码可以利用这k各校验位查找出自己的所有错误情况并表示出来。

满足了上面这个式子以后说明我们现在可以进行组装海明码了。那么接下来我们进行组装

确定校验位的位置分布

接下来我们需要组装校验位和信息位了，我们需要确定校验位要放在哪里。我们这里假设信息位D4D3D2D1是1010，然后校验位是P3P2P1，我们需要将P3,P2,P1插入到信息位D4D3D2D1中来组成一个海明码H7H6H5H4H3H2H1。那么对于Pi位的校验位，他要放在海明码中的第2^i-1处。即

$$H_i=P_{2^{i-1}}$$

所以对于上面的n=4,k=3，且信息位是1010，我们组成海明码时，P3要放到H4，P2要放到H2，P1要放到H1处，所以其他的剩余Hi处放信息位，所以最终组成的海明码应该如下：

接下来我们还需要确定校验位应该填写什么值。

分组以形成校验关系（确定个校验位的数值）

这里的分组很简单，我们要保证一个数据为Di要由多个校验位P1,P2,P3的几个组合形式来校验，其中到底每一个Di选那几个校验组合检验我们只需要满足被校验的信息位的海明位号等于校验该信息位的各校验位的海明位之和。比如对于1010我们已经确定的海明位：

我们可以看出对于D1他的海明位是H3所以选择了P2（海明位是H2)和P1（海明位是H1）的组合，因为H3=H2+H1。D2的校验组合就是P3P1等等。然后我们将这些组合竖着分组，分成1,2,3组（这里的组数一定>=校验位数的）

那么检验位P1就是需要第一组的数据位进行异或取值，异或就是相同取0，不同取1，所以

$$P_1=D_1⊕D_2⊕D_4=0⊕1⊕1=0$$

$$P_2=D_1⊕D_3⊕D_4=0⊕0⊕1=1$$

$$P_3=D_2⊕D_3⊕D_4=1⊕0⊕1=0$$

所以各个校验位的值就都填写出来了，这样我们就写出了1010的海明码是

海明码的校验原理

那么我们是如何进行对海明码的检验的呢？怎样通过海明码来检验信息位是否正确？如果不正确又是如何知道第几位出错了呢？

我们知道此时1010正确的海明码就应该是1010010，即如果信息位正确恰好有

$$S_1=P_1⊕D_1⊕D_2⊕D_4=0$$

$$S_2=P_2⊕D_1⊕D_3⊕D_4=0$$

$$S_3=P_3⊕D_2⊕D_3⊕D_4=0$$

即此时S3S2S1刚刚好是000（想想也知道P1,P2,P3都是由正确的D1,D2,D3,D4组合异或出来的，所以如果反过来D1,D2,D3,D4没有错误，那么刚好此时校验位和信息位异或出来的结果相同即S1就是P1⊕P1=0，所以只有正确时才能为0）。那么如果海明码不正确，比如检测出来的S3S2S1=001,那么就说明1010的海明码有错误并且海明码的第001=1位有错误，取反就可以纠正错误了，再比如S3S2S1=101，那么就说明H5错误，需要取反纠正即可。为了验证表示的位置确实是错误的，我们假设对应的1010的海明码我们接受的是1010000，那么此时S2就会报错为1，即此时S3S2S1=010说明H2错误，我们发现此时确实是H2错误了。

最后我们再来思考一下k和n需要满足的关系，我们就不难发现了此时如果满足2^k>=n+k+1,那么刚好任何一个有错误的位都可以由k位二进制串标志出错误的位置。即如上面k=3时最多可以表示8个位置，而海明码刚好就是有0~7八个位置，所以任何一个错误都可以由k位二进制串S3S2S1表示出来，并且由于海明码也是二进制码，所以只有0/1两种可能的值，所以一旦某个位置出错误了说明只要取反就一定是正确的数值了。这种海明码校验明显更加科学高效，是一种较为广泛的校验方法。

循环冗余检验码（CRC)

循环冗余检验码最终实现的目的和海明检验码是一样的，需要技能查找到错误，并且同时还能得知错误的位置进行修正。其思路如下：

首先它不同于海明码，不是将校验位插入到信息位当中，而是将所有的校验位放到信息位的后面组成CRC码。

确定CRC位数

实际上就是确定在K个信息位后面插入的校验位数R是多少，这个R与接收端和发送端约定好的一个多项式G(x)的最高位有关，如对于

$$G(x)=x^3+x^2+1$$

那么R就是最高项的次数值，这里R就是3，最终的CRC码应该是一个长度为N=K+R的码，所以CRC码又称为（N,K）码。那么接下来我们需要求解校验位的值

确定校验位的数值

由于校验位都是拼接在信息位后面如下：

所以也就没有确定校验位一说了，直接求解各个校验位的数值即可了，这里我们以信息码为101001为例讲解，我们约定生产多项式G(x)=x^3+x^2+1，那么R=3，接下来我们需要求解3个校验位的数值，我们先假设校验码是000，然后拼接到信息码后面，所以组成了一个长度为K+3的码就是101001000，我们将这码称之为被除数，这个步骤叫做移位（实际上就是将信息码左移了R位），同时根据G(x)我们取每一个x的系数，所以取出来的码就是1101因为

$$1101=1*x^3+1*x^2+0*x1+1*x^0=G(x)=x^3+x^2+1$$

我们将1101称之为除数，那么接下来求解校验码就是将被除数不断地进行对除数的模2除法。

思考：什么是模2除法？

我们规定：模2加法和模2减法的结果是相同的，都是做异或运算。模2除法和算术除法类似，但是对于每一次的减法都要使用模2减法，并且结果不影响其他2位，也不允许借位，步骤如下：

1. 用除数对被除数进行最高位做模2减，不借位
2. 除数右移一位，如果余数最高位是1，那么就商1，即对余数做除数的模2减法。如果余数最高位是0，那么就商0，除数继续右移一位。
3. 循环直到余数位数小于除数时，该余数就是最终的余数，也就是校验码了。

比如我们现在求解101001的校验码，所以就是除数1101对被除数101001000进行模2除法如下图：

我们来就提分析一下这个模2除的过程：

这样我们就得到了校验码是001，所以101001的CRC码就是101001001。

CRC的检验原理

检验原理实际上就是对接收到的CRC码进行模2除，如果刚好可以整除即余数为0说明CRC码正确，否则得到的余数就是错误的位置的二进制表示。比如对于101001的一个CRC码是101001011，那么通过不断的进行1101（这个是G(x)约定的除数）的模2除法最终会得到余数是010，即第010=2位错误，一定要注意无论是海明码还是CRC码，他们的排列都是从右往左数错误的位置，即CRC码的排列方式也是C9C8C7C6C5C4C3C2C1,所以错误的位置是C2，即从右往左数的第二位，查看确实是这个错误了，取反即可纠正错误。

CRC码和海明码两种码效果相同无优劣之分，都是对于接收到的数据进行检验。

总结