数据的表示和运算

Wu Jun 2020-03-16 18:57:23
Categories: Tags:

1 数制与编码

1.1 进位计数制及其相互转换

1)进位计数制

进位计数法是一种计数的方法,生活中常用 10 进制数表示,计算机内常用 二进制、八进制、十六进制表示数据。

2)不同进制之间的相互转换

例:将十进制数 123.6875 换为二进制。

计算机整数是连续表示的,但是小数是离散的,所以并不是每个十进制小数都可以准确地用二进制表示,例如 0.3,但是任何一个二进制小数都可以用十进制小数表示

1.2 真值和机器数

1)真值

真值就是我们日常用到的用正负号表示正负数的数(正号可省略),比如 +4、-1 等。真值是机器数要表示的实际值。

2)机器数

机器数是真值在计算机中表示的表示形式,是符号数值化的带符号二进制数。

机器数的特点是:表示的数值范围受计算机字长限制;机器数的符号位必须被数值化为0和1;机器数的小数点是用规定的隐含方式来表达的。

1.3 BCD 码

BCD 码是 Binary-Coded Decimal(二进制编码的十进制数)的简称,通常用 4 位二进制数表示 1 位十进制数。

这种编码方式,使十进制和二进制之间转换得以快速进行。但 4 位二进制有 16 种组合,必然会有 6 个冗余。

1)8421 码
2)余 3 码
3)2421 码
4)格雷码
5)5211 码

1.4 字符与字符串

由于计算机只能处理二进制数据,所以所有字符都要编码成二进制来表示。

1)字符编码 ASCII 码

ASCII 码是用 7 位二进制数表示一个字符的系统。

其中编码值 0~31 是控制字符,编码值 127 是 DEL 码,编码值 32 是空格,编码值 32~126 共 95 个是可印刷字符。

为什么 0~9 对应 ASCII 码 48~57? 因为 48 二进制形式为 0110000 ,去掉高三位即 0,其他数字亦然

2)汉字的表示和编码

汉字的编码包括汉字的输入编码、汉字内码、汉字字形码三种,分别用于输入、内部处理和输出三种用途。

3)字符串的存放

字符串是指连续的一串字符,通常占用主存中连续的多个字节,每个字节存储一个字符。

需要区分“大端模式”和“小端模式”

例如 16 位值 0x2122

不同计算机可以选用任何一种,甚至同时采用

1.5 校验码

1)奇偶校验码

在原编码基础上添加一个校验位,码距为 2,可以检测出一位错误(或奇数位错误),但不能找到出错位置,也不能检测偶数位错误。增加的冗余位称为奇偶校验位。

2)海明(汉明)校验码

是一种多重奇偶校验码。原理是在有效信息中加入几个校验位形成海明码,并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验位的值发生变化,所以不但可以发现错位,还能纠正错位。

根据纠错理论得 L - 1 = D + C (D>=C),即编码最小码距 L 越大,其检错位 D 数就越大,纠正错误的位数 C 也越大,并且纠错能力恒小于或等于检错能力。

例,在 n = 4,k = 3 时,求 1010 的汉明码

  1. 确定海明码的位数
    • 设有 n 位有效信息的位数,k 为校验位的位数,则信息位 n 和校验位 k 应满足:n + k <= 22 - 1。海明码位数为 n + k = 7 <= 23 - 1 成立,则 n、k 有效。设信息位 D4D3D2D1(1010),共 4 位,校验码 P3P2P1,共三位,对应的海明码为 H7H6H5H4H3H2H1
  2. 确定校验位的分布
    • 规定校验位Pi在海明位号为2i-1的位置上,其余各位为信息位,因此:

      • P1的海明位号为2i-1 = 20 = 1,即H1为P1
      • P2的海明位号为2i-1 = 21 = 2,即H2为P2
      • P3的海明位号为2i-1 = 22 = 4,即H4为P3
    • 将信息位按原来的顺序插入,则海明码各位分布如下:

      H7 H6 H5 H4 H3 H2 H1
      D4 D3 D2 P3 D1 P2 P1
  3. 分组,以形成校验关系
    • 每个数据位用多个校验位进行校验,但要满足:被校验的数据位的海明码位于等于校验该数据位的各校验位海明位号之和。另外,校验位不需要再被校验。
      • D1 在 H3 的位置,所以由 P2P1 校验
      • D2 在 H5 的位置,所以由 P3P1 校验
      • D3 在 H6 的位置,所以由 P3P2 校验
      • D4 在 H7 的位置,所以由 P3P2P1 校验
  4. 校验位取值
    • 校验位 Pi 的值分为 i 组(由该校验位校验的数据位)所有位求异或。根据 3 的分组,有:
      • P1 = D1⊕D2⊕D4 = 0⊕1⊕1 = 0
      • P2 = D1⊕D3⊕D4 = 0⊕0⊕1 = 1
      • P3 = D2⊕D3⊕D4 = 1⊕0⊕1 = 0
    • 所以 1010 对应的海明码为 1010010
  5. 海明码校验的原理
    • 每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查,就构成了 k 个校验方程:
      • S1 = P1⊕D1⊕D2⊕D4
      • S2 = P2⊕D1⊕D3⊕D4
      • S3 = P3⊕D2⊕D3⊕D4
    • 若 S3S2S1 的值为“000”,则说明无错,否则说明出错,而这个数就是错误的位号。
3)循环冗余校验(CRC)码

例,设生成多项式为 G(x) = x3+x2+1,信息码为 101001 ,求对应的 CRC 码:

R = 生成多项式最高幂次 = 3,K = 信息码长度 = 6, N = K + R = 9

  1. 移位
    • 将原信息码左移R位,低位补 0,得 101001000
  2. 相除
    • 对移位后的信息码,用生成多项式进行模2除法,产生余数。得到余数为 001,则 101001 编码后的 CRC 码为 101001001
  3. 检错和纠错
    • 接收到 CRC 码,用生成多项式 G(x) 做模 2 的除法,若余数为 0,则码字无错。
    • 若接收端接收的 CRC 码为 101001011,将这个数据与 1101 进行模 2 除法,得到余数 010,则说明倒数第二位出粗,将其取反即可。

模2除法:

模 2 加法和减法的结果相同,都是做异或运算,模 2 除法和算术除法类似,但每一位除(减)的结果不影响其他位,也就是不进位,过程如下:

  1. 用除数对被除数最高几位做模 2 减(异或,不借位)
  2. 除数右移 1 位,若余数做高位为 1,商为 1,并对余数做模 2 减。若余数最高位为 0,商为 0,除数继续右移一位。
  3. 循环直到余数位数小于除数时,该余数为最终余数。

2 定点数的表示和运算

2.1 定点数的表示

1)无符号数和有符号数的表示
2)机器数的定点表示

根据小数点的位置是否固定,计算机中机器数分两种数据格式:定点表示和浮点表示。

定点表示法约定所有机器数的小数点位置固定不变,可以分为定点整数、定点小数两种。

3)原码、反码、补码、移码

如未特殊说明,各种转换都不带符号位,保证符号位不变

2.2 定点数的运算

1)定点数的移位运算
2)原码定点数的加/减运算

注意:运算时注仓机器字长,当左边位出现溢出时,将溢出位丢掉。

3)补码定点数的加/减运算

补码加减运算规则简单,易于实现,因此计算机系统中普遍采用补码加减运算。

  1. 参与运算的两个操作数均是补码形式
  2. 按 2 进制运算规则,逢二进一
  3. 符号位与数值位按同样规则参与运算,符号位运算产生的进位要丢掉,结果的符号位由运算得出。
  4. 补码的加减法运算依据下面公式进行。当参与运算的数是定点小数时,模 M=2;当参与运算的是定点整数时,模 M=2n+1
    • [A + B] = [A] + [B] (mod M)
    • [A - B] = [A] + [-B] (mod M)
  5. 补码运算结果仍为补码
4)符号扩展

在计算机算术运算中,有时必须将采用给定位数表示的数转换成具有不同位数的某种表示形式。

符号位不变

5)溢出概念和判别方法

仅当两个符号相同的数相加,或两个符号相异的数相减才可能产生溢出。

(1)一位符号位判溢出

由于减法在机器中是用加法器实现的,因此无论是加法还是减法,只要参与操作的两个数符号相同,结构与原操作数符号不同,则肯定发生了溢出。

(2)采用双符号位

双符号位法也称模 4 补码,额外增加一位符号位。运算结果的两个符号位 S1S2 相同,表示未溢出,不同,表示溢出,此时最高位代表真正的符号。

符号位 S1S2 的各种情况如下:

  1. S1S2 = 00:表示结果为正,无溢出
  2. S1S2 = 01:表示结果正溢出
  3. S1S2 = 10:表示结果负溢出
  4. S1S2 = 11:表示结果为负,无溢出

则溢出逻辑判断表达式为 V = S1⊕S2,若 V = 0,表示无溢出,V = 1,表示结果溢出。

(3)采用一位符号位根据数据位的进位情况判断

如果符号位的进位 Cs 与最高位的进位 C1 相同,则说明没有溢出,否则发生了溢出。则溢出的逻辑判断表达式为 V = Cs⊕C1,若 V = 0,表示无溢出;V = 1,表示有溢出。

6)定点数的乘法运算

在计算机中,乘法运算由累加和右移操作实现。根据机器数的不同,可分为原码一位乘法和补码一位乘法。原码一位乘法的规则比补码一位乘法简单。

(1)原码一位乘法

两个原码数相乘,其乘积的符号为相乘两数符号的异或值,数值则为两数绝对值之积

设[X]=xs.x1x2…xn, [YJ=ys.y1y2…yn,则运算规则如下。

(2)补码一位乘法(Booth 算法)

它是一种带符号数的乘法,采用相加和相减的操作,计算补码数据的乘积。

设[X]=xs.x1x2…xn, [YJ=ys.y1y2…yn,则运算规则如下。

yn(高位) yn+1(低位) 操作
0 0 部分积右移一位
0 1 部分积加 [X],右移一位
1 0 部分积加 [-X]$,右移一位
1 1 部分积右移一位
7)定点数的除法运算

在计算机中,除法运算可转换成“累加——左移"(逻辑左移),根据机器数的不同,可分为原码除法和补码除法。

(1)原码除法运算(不恢复余数法)

同原码乘法,需要将符号位与数值部分分开计算

(2)补码除法运算

和补码乘法一样,不需要单独算符号位

2.3 强制类型转换

3 浮点数的表示和运算

3.1 浮点数的表示

1)浮点数的表示格式

浮点数由阶码和尾数两部分组成,表示为 N = rE * M。式中,r 是浮点数阶码的底(隐含),与尾数的基数相同, 通常 r=2。E 和 M 都是带符号的定点数,E 称为阶码,M 称为尾数。

2)规格化浮点数

为了提高运算的精度,需要充分地利用尾数的有效数位,通常采取浮点数规格化形式,即规定尾数的最高数位必须是一个有效值。

3)浮点数表示范围
4)IEEE 754 标准

类型 数符 阶码 尾数数值 总位数
短浮点数 1 8 23 32
长浮点数 1 11 52 64
临时浮点数 1 15 64 80
5)定点、浮点表示的区别

3.2 浮点数的加减运算

浮点数运算的特点是阶码运算和尾数运算分开进行。浮点数的加/减运算一律采用补码。浮点数加/减运算分为以下几步。

  1. 对阶
    • 小数点位置对齐,使得两个数的阶码相等。
    • 先求阶差,小阶向大阶看齐,将阶码小的尾数右移一位(基数为 2),阶加 1,直到两个数的阶码相等为止。
    • 尾数右移时,舍弃掉有效位会产生误差,影响精度。
  2. 尾数求和:将对阶后的尾数按定点数加(减)规则运算
  3. 规格化:左规或右规
  4. 舍入
    • 01 入法: 类似于十进制的四舍五入
    • 恒置 1
  5. 溢出判断
    • 上溢:中断处理
    • 下溢:按机器零处理
  6. 强制类型转换
    • char -> int -> long -> double 范围和精度都从小到大,可以放心转换,不会有损失(溢出或者精度损失)
    • 值得注意的是, int -> float 虽然不会发生溢出,但是是可能进行舍入的,因为 float 尾数部分(24bit)比 int 数值(32bit)少,所以最后几位可能会发生舍入

3.3 浮点数的乘除法运算

  1. 浮点数阶码运算(移码)
    • [X+Y]移=[X]移+[Y]补
    • [X–Y]移=[X]移+[–Y]补
  2. 按照一位乘或加减交替除运算
    • 先确定符号,在列式子计算

4 算术逻辑单元 ALU

在计算机中,运算器承担了执行各种算术和逻辑运算的工作,运算器由算术逻辑单元 ALU (Arithmetic Logic Unit)、累加器、状态寄存器和通用寄存器组等组成。

ALU 的基本功能包括加、减、乘、除四则运算,与、或、非、异或等逻辑运算,以及移位、求补等操作。

4.1 串行加法器和并行加法器

加法器是由全加器再配以其他必要的逻辑电路组成的,根据组成加法器的全加器个数是单个还是多个,加法器有串行和并行之分。

1)一位全加器

全加器(FA)是最基本的加法单元

2)串行加法器

只有一个全加器,数据逐位送入加法器中进行运算,所以运算慢

3)并行加法器

多个全加器组成,各位同时运算,但是仍有一个制约其速度的最大问题:虽然各位同时提供,但是进位必须在低位计算结束后才能得到

(1)串行进位

正如上面所述,高位仍然需要等待低位的进位,速度仍然受限

(2)并行进位

在高位的表达式中直接带入低位进位的结果,当然这样越高位表达式越复杂,对应的逻辑电路也就越复杂,但这确实解决了速度的问题

4.2 算术逻辑单元的功能和结构

ALU 是一种功能较强的组合逻辑电路。它能进行多种算术运算和逻辑运算。由于加、减、乘、除运算最终都能归结为加法运算。因此,ALU 的核心首先应当是一个并行加法器,同时也能执行 “与”、“或”、“非”等逻辑运算。