计算机中的编码

Dear 丶 2022-09-14 15:16 198阅读 0赞

### 文章目录 ###

*   *  一、ASCII码
     *  二、BCD码
     *   *  1. BCD加法运算
         *  2. BCD减法运算
     *  三、汉字的编码
     *   *  1. 国标码（GB2312）
         *  2. 区位码及汉字机内码
         *   *  （1）区位码
             *  （2）汉字机内码
     *  四、检验码编码和解码
     *   *  1. 奇偶校验码编码
         *  2. 海明码编码
         *   *  （1）海明码的结构形式
             *  （2）海明码的编码原理
             *  （3）海明码的纠错
         *  3. 循环冗余校验码
         *   *  （1）CRC的编码方法
             *  （2）模2运算
             *  （3）CRC的译码及纠错
             *  （4）关于生成多项式

在计算机中，由于机器只能识别二进制数，因此，键盘上所有数字、字母和符号也必须事先为它们进行二进制编码，以便机器对它们加以识别、存储、处理和传送。

下面我们来认识下计算机中的各种编码，我打算采用四个小节的方式，分别来介绍 **ASCII码、BCD码、汉字的编码、检验码编码和解码** 。

## 一、ASCII码 ##

`ASCII`码（美国信息交换标准码）是计算机键盘上输入字符的二进制编码。

通常，`ASCII`码由`7`位二进制数码构成，共可为`128`个字符编码，这`128`个字符共分为两类：

*  图形字符，共`96`个
    
     *  十进制数符`10`个
     *  大小写英文字母`52`个
     *  其他字符`34`个
 *  控制字符，共`32`个
    
     *  回车符
     *  换行符
     *  退格符
     *  设备控制符
     *  信息分隔符
     *  其他

字符`0-9`所对应的`ASCII`码是在其数字的基础上加`30H`，比如字符`9`对应的`ASCII`码为`30H + 09H = 39H`。

字符`A`对应的`ASCII`码，是在其对应的十六进制数的基础上加`37H`，`A`在十六进制里面代表数字`10`，则有`37H + 0AH = 41H`，由于字符`A~Z`的`ASCII`码是顺序排列的，所有任意一个大写字母的`ASCII`码都能通过字符`A`的`ASCII`码计算出来，比如字符`Z`的`ASCII`码比字符`A`的`ASCII`码大`25（19H）`，所以，字符`Z`所对应的`ASCII`码为`41H + 19H = 5AH`。

小写的字母所对应的`ASCII`码比其对应的大写字母的`ASCII`码大`32（20H）`，所以小写字母`a`所对应的`ASCII`码为`41H + 20H = 61H`，由于小写字母`a~z`所对应的`ASCII`码也是顺序排列的，所以任意一个小写字母的`ASCII`码也可以参照字符`a`的`ASCII`码计算出来。

在`8`位微型计算机中，信息通常是按字节存储和传送的，一个字节有`8`位。`ASCII`码有`7`位，作为一个字节还多出一位，多出的这一位是最高位，常常用作奇偶校验，也称为奇偶校验位。奇偶校验位可以用来校验信息传送过程中是否有错。

--------------------

## 二、BCD码 ##

`BCD`码是十进制数的二进制编码。

计算机对十进制数的处理过程：键盘上输入的十进制数字先被替换成一个个的`ASCII`码送入计算机，然后通过程序替换成`BCD`码，并对`BCD`码直接进行运算（也可以先把`BCD`码替换成二进制码进行运算，并把运算结果再变为`BCD`码），最后把`BCD`码形式的输出结果变换成`ASCII`码才能在屏幕上加以显示。

`BCD`码是一种具有十进制权的二进制编码。它的种类较多，常用的有`8421`码、`2421`码、余`3`码和格雷码。

以`8421`码为例：

`8421`码是`BCD`码的一种，因组成它的`4`位二进制数码的权为`8、4、2、1`而得名。

`8421`码是一种采用`4`位二进制数来代表十进制数码的代码系统，在这个代码系统中，`10`组`4`位二进制数分别代表了`0~9`中的`10`个数字符号，如下表所示：

**表2.1 8421 BCD编码表**

`4`位二进制数字共有`16`种组合，其中`0000B ~ 1001B`为`8421`的基本代码系统，`1010B ~ 1111B`未被使用，称为非法码或冗余码。

`10`以上的所有十进制数至少需要`2`位`8421`码字（即`8`位二进制数数字）来表示，而且不应出现非法码，否则就不是真正的`BCD`数。

### 1. BCD加法运算 ###

`BCD`加法是指两个`BCD`数按“逢十进一”原则进行相加，其和也是一个`BCD`数。

在进行`BCD`加法过程中，计算机对二进制加法结果进行修正的原则是：

*  若和的低`4`位大于`9`或低`4`位向高`4`位发生了进位，则低`4`位加`6`修正；
 *  若高`4`位大于`9`或高`4`位的最高位发生进位，则高`4`位加`6`修正。

举例说明：`48 + 69`，则`BCD`的加法过程为：

![BCD加法过程][BCD]

### 2. BCD减法运算 ###

与`BCD`加法类似，`BCD`减法时也要修正。

在`BCD`减法过程中，若本位被减数大于减数（即低`4`位二进制数的最高位无借位），则减法是正确的；若本位被减数小于减数，则减法时就需要借位，由于`BCD`运算规则是借`1`当作`10`，二进制在两个`BCD`码间的运算规则是借`1`当作`16`，而机器是按二进制规则运算的，故必须进行减`6`修正。

在`BCD`减法过程中，计算机对二进制运算结果修正的原则：

*  若低`4`位大于`9`或低`4`位向高`4`位有借位，则低`4`位减`6`修正；
 *  若高`4`位大于`9`或高`4`位最高位有错位，则高`4`位减`6`修正。

举例说明：`53 - 27`，则`BCD`的减法过程为：

![BCD减法过程][BCD 1]

所以，`53 - 27 = 00100110B`。

**note：** 在计算机中，两个数的减法被转换成被减数的补码加上减数相反数的补码来完成，也就是说在计算机中不存在减法电路。

--------------------

## 三、汉字的编码 ##

在计算机中，每个汉字都是一个图形，因此，计算机若要对汉字进行处理，就必须对所有汉字进行二进制编码，建立一个庞大的汉字库，以便计算机进行查找。

**小知识：** 历史上使用过的汉字约有`60000`多个，常用的汉字约有`6000`多个，其中，使用频度达到`90%`的汉字约有`2400`个，其余汉字的使用频度只占`10%`。

### 1. 国标码（GB2312） ###

国标码是《信息交换用汉字编码字符集的基本集》的简称，是我国国家标准总局于`1981`年颁布的国家标准，编号为`GB2312-80`。

在国标码中，共收集汉字`6763`个，分为两级：

1.  第一级收集汉字`3755`个，按拼音排序；
2.  第二级收集汉字`3008`个，按部首排序。

还包括了一般字符`201`个（间隔符、标点符号、运算符号、单位符号和制表符等）、序号`60`个、数字`22`个、拉丁字母`66`个、汉语拼音符号`26`个、汉语注音字母`37`等。因此，连同汉字一共是`7445`个图形字符。

为了给`7445`个图形字符编码，国标码采用`14`位二进制来给这些图形字符编码。`14`位二进制中的高`7`位占一个字节（最高位不用），称为第一字节；低`7`位占另一个字节（最高位不用），称为第二字节。

国标码中的汉字和字符分为字符区和汉字区。

*  `21H ~ 2FH`（第一字节）和`21H ~ 7EH`（第二字节）为字符区，用于存放非汉字图形字符；
 *  `30H ~ 7EH`（第一字节）和`21H ~ 7EH`（第二字节）为汉字区。

因此，国标码采用`4`位十六进制数来表示一个汉字。例如，“啊”的国标码为`3021H`（`30H`为第一字节，`21H`为第二字节）。

### 2. 区位码及汉字机内码 ###

#### （1）区位码 ####

区位码与国标码的区别不大，它们共用一张编码表。国标码用`4`位十六进制数来表示一个汉字，区位码是用`4`位十进制区号和位号来表示一个汉字。

#### （2）汉字机内码 ####

由于国标码每个字节的最高位都是`0`，与国际通用的标准`ASCII`码无法区分，因此，我国将每个汉字所对应的国标码的两个字节的最高位分别设定为`1`，作为该字的机内码。

--------------------

## 四、检验码编码和解码 ##

在计算机中，信息存入磁盘、磁带或其他存储器中常常会由于某种干扰而发生错误，信息在传输过程中也会因为传输线路上的各种干扰而使接收端接收到的数据和发送端发送的数据不同。为了确保计算机可靠工作，人们希望计算机能对从存储器中读取的数据或从接收端接收到的数据自动做出判断，并加以纠错。由此，引出了计算机对校验码的编码和解码问题。

校验码编码发生在信息发送之前（或存储）之前，校验码解码则在信息被接收（或读出）后进行。也就是说：欲发送信息应首先按照某种约定规律编码成校验码，使得这些有用信息加载在校验码上进行传送；接收端对接收到的校验码按约定规律的逆规律进行解码和还原，并在解码过程中去发现和纠正因传输过程中的干扰所引起的错误码位。

### 1. 奇偶校验码编码 ###

奇偶校验码编码和解码又称为奇偶校验，是一种只有一位冗余位的校验码编码方法，常用于主存校验和信息传送。

奇偶校验分为奇校验和偶校验两种：

*  奇校验的约定编码规律：要求编码后的校验码中`1`的个数（包括有效信息位和奇校验位）为奇数；
 *  偶校验的编码规律：要求编码后的校验码中`1`的个数（包括有效信息位和偶校验位）为偶数。

一个`8`位奇偶校验码，有效信息位通常位于奇偶校验码中的低`7`位，一位奇偶校验位处于校验码中的最高位。

对于奇偶校验码来说，需要知道以下几点：

*  奇偶校验位状态常由发送端的奇偶校验电路自动根据发送字节低`7`位中“`1`”的个数来确定。
 *  奇偶检验电路通常采用异或电路实现，如果采用偶检验，发送端将所有信息位经过异或后所得的结果就是偶校验位；若采用奇校验，所有信息位异或后取反就是奇校验位。
 *  接收端将接收到的全部信息（包括校验信息位）进行异或运算，若采用的是偶校验，异或运算的结果为`0`，则认为接收到的信息正确；若采用奇校验，全部信息位异或后结果为`1`，则认为传输正确，否则传输错误。
 *  对于采用奇偶校验的信息传输线路，奇偶校验位的状态取决于其余`7`位信息中“`1`”的奇偶性，对于偶校验，若其他`7`位中“`1`”的个数为偶数，则奇偶校验电路自动在校验位上补`0`；若“`1`”的个数为奇数，则校验位上为`1`，以保证所传信息字节中“`1`”的个数为偶数。

例如，字符`C`的`ASCII`码为`01000011B`，采用偶校验，校验位形成过程为：

校验位
    = D₆ ⊕ D₅ ⊕ D₄ ⊕ D₃ ⊕ D₂ ⊕ D₁ ⊕ D₀ 
    = 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 
    = 1

校验位占`D₇`位，最后形成含有偶检验位的信息编码为`11000011`。  
这样，接收端奇偶校验电路只要判断每个字节中是否有偶数个“`1`”（包括奇偶校验位）就可以知道信息在传输中是否出错。

奇偶校验的缺点：

*  无法检验每个字节中同时发生偶数个错码的通信错误；
 *  当检验出错误时，无法确定到底是哪一位出错。

### 2. 海明码编码 ###

海明码是一种既能发现错误，又能纠正错误的校验码。

海明码的码位有（`n+k`）位，`n`为有效信息的位数，`k`为奇偶校验位位数。`k`个奇偶校验位有`2^k`种组合，除采用一种组合指示信息在传送或读出过程中有无错误外，尚有（`2^k - 1`）种组合可以用来指示出错的码位。因此，若要能指示海明码中任意一位是否有错，则校验码的位数`k`必须满足如下关系：`2^k >= n+k+1`，由此，可以计算出`n`与`k`的关系如下表所示：

**表4.2.1 有效信息位与所需校验位的关系**

在确定了`n`与`k`的值后，还要进一步确定哪些位为有效信息位及哪些位作为奇偶校验位。

**海明码规定：位号恰好等于2的权值的那些位（即：第1（ 2^0 ） 位、第2（ 2^1 ）位、第4（ 2^2 ）位、第8（ 2^3 ）位）均可用作奇偶校验位，并命名为P₀，P₁，P₂，P₃，…，余下各位则是有效信息位。**

接下来，通过一个例子来说明对`ASCII`码进行海明码编码和解码的原理。

在对海明码的编码、解码原理介绍前，先对海明码的结构形式简单叙述下。

#### （1）海明码的结构形式 ####

我们知道`ASCII`码有`7`位有效信息位（`n = 7`），由上表可知，`k = 4`，故海明码的码长为`(n + k) = 11`位。根据海明码对奇偶校验位位号的上述规定，第`1、2、4、8`位应为奇偶校验位，其余各位为有效信息位。其分配关系如下：

*note：其中，`P₀、P₁、P₂、P₃`为奇偶校验位；`D₆、D₅、D₄、D₃、D₂、D₁、D₀`为有效数据位；最上面一排为海明码的位号。*

在海明码中，奇偶校验位`P₀、P₁、P₂、P₃`（海明码位号为`1、2、4、8`）负责对各有效信息位的校验。

检验位和被校验的信息位之间的关系为：海明码的位号可看作是`2^i`累加（`i`从`0`开始），例如信息位`D₆`的海明码位号为`3 = (2^0 + 2^1)`，信息位`D₂`的海明码位号为`9 = (2^0 + 2^3)`。由此可以看成，如果信息位的海明码位号对应的二进制累加求和中含有`2^i`，则该位信息位就被对应的`Pi`校验，所以，海明码位号为`3`的`D₆`信息位应该被`P₀`和`P₁`位校验；海明码码号为`9`的`D₂`信息位应被`P₀`和`P₃`所校验。

按此关系可推出：

*  `P₀`负责对第`3、5、7、9、11`位的校验；
 *  `P₁`负责对第`3、6、7、10、11`位的校验；
 *  `P₂`负责对第`5、6、7`位的校验；
 *  `P₃`负责对第`9、10、11`位的校验。

转化成表，展示如下：

**表4.2.2 奇偶校验位表**

<table> 
 <thead> 
  <tr> 
   <th align="center">奇偶校验位</th> 
   <th align="center">被校验位</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">P₀(1)</td> 
   <td align="center">3，5，7，9，11</td> 
  </tr> 
  <tr> 
   <td align="center">P₁(2)</td> 
   <td align="center">3，6，7，10，11</td> 
  </tr> 
  <tr> 
   <td align="center">P₂(4)</td> 
   <td align="center">5，6，7</td> 
  </tr> 
  <tr> 
   <td align="center">P₃(8)</td> 
   <td align="center">9，10，11</td> 
  </tr> 
 </tbody> 
</table>

#### （2）海明码的编码原理 ####

海明码编码过程在发送端一侧进行，其主要任务是根据有效信息位确定`P₀、P₁、P₂、P₃`的值，并填入相应海明码的码位上。

以字符`A`的`ASCII`码（`41H（1000001B）`）为例，填入海明码的相应位号上变为：

确定奇偶校验位`P₀、P₁、P₂、P₃`的值必须按`表4.2.2 奇偶校验位表`进行。

**编码方法：按偶校验或奇校验规则统计相应被校海明码位号中“1”的个数。对于偶校验编码的方法是：若被校位号中“1”的个数为奇数，则相应奇偶校验位为“1”；若被校验位号中“1”的个数为偶数，则相应偶校验位为“0”。**

#### （3）海明码的纠错 ####

海明码的纠错是在海明码解码过程中完成的，纠错很简单，只要把错位取反就行了。而问题的关键是要弄清海明码中究竟错在哪一位上。

海明码的出错指示码`E₃、E₂、E₁、E₀`又称为指误字。指误字不仅可以指出数据在读出或传送过程中有无错误，而且可以指示究竟错在哪一位上。

例如，若`E₃E₂E₁E₀ = 0000B`，则表明数据在读出或传送过程中没有发生错误；若`E₃E₂E₁E₀ = 0001B`，则表明海明码的第`1`位（奇偶校验位`P₀`）有错；若`E₃E₂E₁E₀ = 0011B`，则表明海明码的第`3`位有错。

因此，海明码解码的主要问题可以归结为如何求取出错标志位`E₃、E₂、E₁及E₀`。

出错标志位的求取规则是按下表进行的。

**表4.2.3 出错标志位和所检测的位号表**

<table> 
 <thead> 
  <tr> 
   <th align="center">出错标志位</th> 
   <th align="center">被检海明码的位号</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">E₀</td> 
   <td align="center">1,3,5,7,9,11</td> 
  </tr> 
  <tr> 
   <td align="center">E₁</td> 
   <td align="center">2,3,6,7,10,11</td> 
  </tr> 
  <tr> 
   <td align="center">E₂</td> 
   <td align="center">4,5,6,7</td> 
  </tr> 
  <tr> 
   <td align="center">E₃</td> 
   <td align="center">8,9,10,11</td> 
  </tr> 
 </tbody> 
</table>

偶校验解码的方法是，若被检测所有海明码位号中“1”的个数为奇数，则相应出错标志位的值为`1`；若被检测所有海明码位号中`1`的个数为偶数，则相应出错标志位的值为`0`。

例如：若接收端接收到的字符`A`的海明码中第`11`位错成`0`，变成如下形式：

则有：

（1）（3）（5）（7）（9）（11）
    E₀ = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1 
    --------------------------------------------------
       （2）（3）（6）（7）（10）（11）
    E₁ = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1
    --------------------------------------------------
       （4）（5）（6）（7）
    E₂ = 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
    --------------------------------------------------
       （8）（9）（10）（11）
    E₃ = 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1

故，指误字为`E₃E₂E₁E₀ = 1011B`，指示第`11`位出错，将它取反，则错误码得到纠正。

### 3. 循环冗余校验码 ###

循环冗余校验码（`CRC码`）可以发现并纠正信息存储或传输过程中连续出现的多位错误，这在辅助存储器和计算机通信方面得到了广泛的应用。

`CRC码`是一种基于模`2`运算（即以按位模`2`相加为基础的四则运算，运算时不考虑进位和借位）建立编码规律的校验码，可以通过模`2`运算来建立有效信息位和校验位之间的约定关系。

这种约定关系为：假设`n`是有效数据信息位位数，`r`是校验位位数。则`n`位有效信息位与`r`位校验位所拼接的数（`k = n + r`位长），能被某一约定的数除尽。

#### （1）CRC的编码方法 ####

待编码的有效信息以多项式`M(x)`表示，将`M(x)`左移`r`位得到多项式`M(x) × x^r`，使低`r`位二进制位全为零，以便与随后得到的`r`位校验位相拼接。

使用多项式`M(x) × x^r`除以生成多项式`G(x)`，求得的余数即为校验位。为了得到`r`位余数（校验位），`G(x)`必须是`r + 1`位的。

将`r`位余数`R(x)`与左移`r`位的`M(x) × x^r`相加，就得到`n + r`位的`CRC码`。

#### （2）模2运算 ####

模`2`运算：不考虑借位和进位的运算。

*  模`2`加减  
    可用异或门实习，即：

0 + 0 = 0;
    0 + 1 = 1;
    1 + 0 = 1;
    1 + 1 = 0;
    0 - 0 = 0;
    0 - 1 = 1;
    1 - 0 = 1;
    1 - 1 = 0;

*  模`2`乘法  
    用模`2`加求部分积之和。
 *  模`2`除法  
    用模`2`减求部分余数，每上一位商，部分余数要减少一位，上商规则是：余数最高位为`1`，就商`1`，否则商`0`。当部分余数的位数小于除数时，该余数为最后余数。

举例说明：设四位有效信息位是`1100`，选用生成多项式`G(x) = 1011`，求有效信息位`1100`的`CRC`编码。

（1）将有效信息位1100表示为多项式M(x)
    
    M(x) = x³ + x² = 1100
    
    （2）M(x)左移3位，得M(x) × x³ 
    
    M(x) × x³ = x⁶ + x⁵ = 1100000
    
    （3）用r + 1位的生成多项式G(x)，对M(x) × x³作模2除
    
    M(x) × x³      1100000                    010
    ----------- = --------------- = 1110 + --------------
    G(x)             1011                     1011
    
    （4）M(x) × x³与r位余数R(x)做模2加，即可求得它的CRC码
    
    M(x) × x³ + R(x) = 1100000 + 010 = 1100010

#### （3）CRC的译码及纠错 ####

`CRC`码传输到目标部件时，用约定的多项式`G(x)`对收到的`CRC`码进行“模`2`除”，若余数为`0`，则表明该`CRC`校验码正确，否则表明有错，不同的出错位，其余数是不同的，由余数指出是哪一位出了错然后加以纠正。

**表4.3.1 G(x) = 1011时，CRC码出错模式表**

由上表可知，若`CRC`码有一位出错，用`G(x)`作“模`2`除”运算，则得到一个不为零的余数，若对余数补零，继续作“模`2`除”运算，会得到一个结果：各次余数会按上表中的顺序循环。

例如，第一位`N₁`出错，余数将为`1`，补零后再除，得到余数为`010`，以后依次为`100`、`011`、……，反复循环。这就是循环码的由来，利用这个特性正好可以来纠错。

当余数不为零时，一边对余数补零继续作“模`2`除”运算，一边将被检测的`CRC`码循环左移。由上表可知，当出现余数为`101`时，出错位也移到了`N₇`位，可通过“异或门”将它们纠正后，再在下次移位时送回`N₇`，然后继续移位，直至移满一个循环，就得到一个纠正后的码字。

#### （4）关于生成多项式 ####

不是任何一个（`r + 1`）位多项式都能作为生成多项式，从检错、纠错的要求来看，生成多项式应满足下列要求：

*  任何一位发生错误，都应使余数不为零；
 *  不同位发生错误，都应使余数不同；
 *  对余数补零，继续作“模2除”，应使余数循环。

--------------------

[BCD]: /images/20220828/591b7d69e56c425fb53e9a7724e2b82d.png
[BCD 1]: /images/20220828/6b87d4122b9c468bbe9bcd85043b0718.png