作者：whisper

链接：http://proprogrammar.com:443/article/252

声明：请尊重原作者的劳动，如需转载请注明出处

---

    （一）数制与编码

• 1、进位计数制及其相互转化
• 2、真值和机器数
• 3、BCD码
• 4、字符与字符串
• 校验码

     2.1 数制及其转换

    2.1.1 进位计数制机器相互转化

    1）R进制转化为十进制的方法

    按权展开法：先写成多项式，后计算十进制结果

    N = dₙ₋₁dₙ₋₂....d₁d₀d₋₁d₋₂....d₋ₘ

    = dₙ₋₁ x Rⁿ⁻¹ + dₙ₋₂ x Rⁿ⁻² + .... + d₁ x R + d₀

    + d₋₁ x R⁻¹ + d₋₂ x R⁻² + .... + d₋ₘ x R⁻ᵐ

    2）十进制转化为二进制的方法

    一般分为两个步骤：

    整数部分的转换

    除2取余法（基数除法）

    减权定位法

    小数部分的转换

    乘2取整法（基数乘法）

    除基2取余法（整数部分）

    除基取余法：把给定的十进制数除以基数，取余数作为最低位的系数，然后继续将商部分除以基数，余数作为次低位系数，重复操作直至商为0

    例如：用基数除法将(327)₁₀转换成二进制数

    减权定位法（整数部分）

    将十进制数依次从二进制的最高位权值进行比较，若够减则对应位置1，减去该权值后再往下比较，若不够减则对应位为0，重复操作直至差数为0

    例如：将(327)₁₀转换成二进制数

    乘基取整法（小数部分的转换）

    把给定的十进制小数数乘以2，取其整数作为二进制小数的第一位，然后取小数部分继续乘以2，将所得整数部分作为第二位小数，重复操作直至得到所需要的二进制小数

    例如：将(0.8125)₁₀转换成二进制小数

    可得(0.8125)₁₀=(0.1101)₂

    3）二进制、八进制和十六进制之间的转换

    以小数点为界，对小数点前后的数分别分组处理，不足的位数补0

    整数部分将0补在数的左侧，对小数部分将0补在数的右侧

    二进制转换成十六进制

    十六进制转换成二进制

    2.1.2 真值和机器数

    （1）真值：正、负号加某进制数绝对值的形式称为真值。

    X=+1011B    y=-1011B

    （2）机器数：符号数码化的数称为机器数如：

    X = 01011    Y=11011

    一般用"0"表示"+"，    "1"表示"-"

                    正                     负

    2.1.3 BCD码-十进制数的编码与运算

    BCD码

    8421码为有权代码，数值为N=8d₃+4d₂+2d₁+1d₀

    十进制数63.29的BCD码为

    0110 0011. 0010 1001

    十进制编码的加法运算

    BCD码运算应将每4位二进制数为一组，组与组之间直接运算，逢十进一。

    但计算机中无法区分BCD码，一概作为二进制数处理，计算机做此运算后须进行调整。

    调整方法：

    和≤9  (1001)₂，不调整

    和>9  (1001)₂，加6(0110)₂修正

    2.1.4 字符与字符串

    （1）字符：ASCII码，用7位表示，外加一位校验位，共128个，10个数字及26个大小写英文字母的ASCII码

    （2）字符串占用主存中连续的多个字节，每个字节存储一个字符

    高字节地址：高位字符或

    高字节地址：低位字符

    （1）汉字的输入

• 输入码：为使输入设备能将汉字输入到计算机而专门编制的一种代码。

    - 国标码、区位码、拼音码和五笔字型等

    （2）汉字在机内的表示

• 机内码：是指机器内部处理和存储汉字的一种代码

    - 用2个字节表示一个汉字的

    （3）汉字的输出与汉字字库

• 显示器是采用图形方式（即汉字是由点阵组成）显示汉字的

    2.1.5 校验码

    （1）奇偶校验码

    （2）海明（汉明）校验码

    （3）循环冗余校验码（CRC码）

• 数据校验码是一种常用的带有发现某些错误或自动改错能力的数据编码方法
• 基本原理：加进一些冗余码，使合法数据编码出现某些错误时，就成为非法编码。
• 码距：是根据任意两个合法码之间至少有几个进制位不相同而确定的，若仅有一位不同，称码距为1。

    （1）奇偶校验码

    原理：是使原来合法编码码距由1增加到2

    方法：通常是为一个字节补充一个二进制位，称为校验位，通过设置校验位的值为0或1的方式，使字节自身的8位和该校验位含有1值的位数一定为奇数或偶数

    在使用奇数个1的方案进行校验时，称为奇校验，反之称为偶校验

    只能发现一位错或奇数个位错，但不能确定是哪一位错

• 字母"A"的ASCII码为0100 0001，有偶数个"1"，因此：

    -使用偶校验时，校验位记为0，即：

    0 0100 0001

    -使用奇校验时，校验位记为1，这样1的位数为奇数个，即：

    1 0100 0001

    （2）汉明/海明校验码

    只要增加少数几个校验位，并把数据的每一个二进制位分配在几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验组的值发生变化，这不但可以发现错误，还能指出哪一位出错，为自动纠错提供了依据。

    假设校验位的个数为r，则校验位能表示2ʳ个状态，可用其中的一个状态指出“没有发生错误”，用其余的2ʳ-1个状态指出有错误发生在某一位，然而错误也可能发生在校验位，因此只有k=2ʳ-1-r个信息能用于纠正被传送数据的位数，要满足关系：

    2ʳ ≥ k + r + 1

    如果要能检出与自动校正一位错，并能同时发现两位错，此时校验位的位数r和数据位的位数k应满足下述关系：

    2ʳ⁻¹ ≥ k + r

    组成汉明码的三要素

    汉明码的组成需增添?位检测位

    2ʳ ≥ k + r + 1

    检测位的位置

    2ⁱ（i = 0, 1, 2, 3....)

    检测位的取值？

    检测位的取值与该位所在的检测“小组”中承担的奇偶校验任务有关

    （注：检测“小组”的确定：对于第i个校验位，它的检测“小组”是校验位与原数据组成的数据的顺序的第i位为1位置）

    例如：第二个校验位的校验小组是下面红色的四个，他们的顺序位的第2位为1

    各检测位Cᵢ所承担的检测小组为

    C₁检测的g₁小组包含第1,3,5,7,9,11...

    C₂检测的g₂小组包含第2,3,6,7,10,11...

    C₄检测的g₃小组包含第4,5,6,7,12,13...

    C₈检测的g₄小组包含第8，9，10，11，12，13，14，15，24...

    gᵢ小组独占第2ⁱ⁻¹位

    gᵢ和gⱼ小组共同占第2ⁱ⁻¹+2ʲ⁻¹位

    gᵢ、gⱼ和gₗ小组共同占第2ⁱ⁻¹ + 2ʲ⁻¹ + 2ˡ⁻¹位

    按配偶原则配置0011的汉明码

    ∵ k=4  根据2ʳ ≥ k + r + 1，取r=3

    二进制序号    1    2    3    4    5    6    7

    名称             C₁  C₂   0   C₄   0    1    1

    C₁ = 3⊕5⊕7 = 1

    C₂ = 3⊕6⊕7 = 0

    C₄ = 5⊕6⊕7 = 0

    ∴ 0011的汉明码为 1000011

    汉明码的纠错过程

    形成新的检测位Pᵢ，其位数与增添的检测有关，如增添3位(r=3)，新的检测位为P₄P₂P₁，

    以r=3为例，Pᵢ的取值为

    对于按“偶校验”配置的汉明码

    不出错时P₁=0，P₂=0，P₄=0

    已知接收到的汉明码为010 01111（按配偶原则配置），试问要求传送的信息是什么？

    纠错过程如下

    P₁ = 1⊕3⊕5⊕7 = 0 无错

    P₂ = 2⊕3⊕6⊕7 = 1 有错

    P₄ = 4⊕5⊕6⊕7 = 1 有错

    ∴ P₄P₂P₁ = 110

    第6位出错，可纠正为010 0101，故要求传送的信息为0101

    （3）循环冗余校验(CRC)码

    CRC(Cyclic Redundancy check)码可以发现并纠正信息串行读写、存储或传送过程中出现的一位、多位错误，因此在磁介质存储器读写和计算机之间通信方面得到广泛应用

    CRC码一般是指k位信息码之后拼接r位校验码，使用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码）的值，以及如何从k+r位信息码知道有没有错

    CRC码的编码方法

    模2运算是指以按位模2相加为基础的四则运算，运算时不考虑进位和借位。

    模2加减：即按位加，可用异或逻辑实现

    模2加与模2减的结果相同，即

    0±0=0  0±1=1  1±0=1  1±1=0

    两个相同的数据的模2和为0

    如下：01即为冗余码

    CRC码的编码方法

    1、可将待编码的k位有效信息位表达为多项式M(x)形式：

    M(x) = Cₖ₋₁xᵏ⁻¹ + Cₖ₋₂xᵏ⁻² + ... + Cᵢxⁱ + ... + C₁x¹ + C₀ 式中Cᵢ为0或1

    若将信息位组左移r位，则可表示为多项式M(x) * xʳ，这样就可以空出r位，以便拼接r个校验位

    CRC码是用多项式M(x) * xʳ除以称为生成多项式G(x)（特定的一个多项式）所得到的余式。为了得到r位余数（校验位），G(x)必须是r+1位的，即为r次的多项式

    设所得余数表达式为R(x)，商为Q(x)，将余数拼接在信息位组左移r位空出的r位上，就构成这个有效信息位的CRC码。

    CRC码的译码与纠错

    将收到的循环校验码用约定的生成多项式G(x)去除，如果码字无误则余数应为0，如有某一位出错，则余数不为0，且不同数位出错余数会不同。

    更换不同的待测码字可以证明：余数与出错位的对应关系是不变的，只与码制和生成多项式有关。对于其他码制或选用其他生成多项式出错模式将发生变化。   

---

亲爱的读者：有时间可以点赞评论一下