计算机组成：数据表示与运算

正文索引 [隐藏]

一、字符表示

1. ASCII

  • 一个字符：7位
  • 字符集：128 种字符
  • 最高为处理方法
    • 恒 0 ：作为 ASCII 标志
    • 奇偶校验位
    • 扩展 ASCII（字符集 256 个字符）

2. 汉字

汉字输入码

  • 数字编码
  • 字音编码：拼音输入法
  • 字形编码：五笔、手写输入
  • 形音编码

汉字交换码

用于不同系统间的数据交换

  • 国标码
  • 国标区位码
    例如：汉字“红”在 26 区 76 位，对应区位码就是 2676，对应国标码是 3A6CH

汉字机内码

汉字在计算机中的编码

  • ASCII 最高位 0，用 2 个字节表示一个汉字
  • ASCII 最高位奇偶校验，用三个字节表示一个汉字

汉字字模码

用于显示汉字

  • 点阵描述

    image-20191117185135781

  • 轮廓描述

3、字符串表示

向量表示法

  • 存放方式：主存连续单元，每个字节一个 ASCII 码

  • 存放顺序：“if (A<B) READ(C)”

    • 大端：高字节 -> 低字节

    image-20191117183753337

    • 小端：低字节 -> 高字节

    image-20191117183815813

  • 特点

    • 简单、节省空间
    • 删除、插入不方便

二、数值表示

1. 十进制 BCD 码

  • 概念：BCD, Binary Coded Decimal, 4 位二进制数可以表示 16 个十进制数，从中选择十个表示 1 位十进制数

  • 分类

    • 有权码：4 位均有指定的权值

    image-20191117185937594

    • 无权码：各位没有权值

    image-20191117190008868

    • 自补码：按位取反可得相对 9 的补码，例如 2421 码

    • 循环码：相邻编码只有 1 位不同，例如格雷码

2. 十进制数串

  • 字符串形式：将十进制数串看成字符串
    • 前分隔：同书写顺序，+/- 号单独占一个字节
    • 后嵌入：+/- 号嵌入到最低一位 ASCII 中
    • 正数不变
    • 负数最低位嵌入，如：- 0011 -> 0111
  • 压缩十进制数串：每位十进制数用 8421 码表示，占半个字节
    • 符号位：选用 8421 冗余码表示，放在最低数位后
    • +：1100
    • -：1101
    • 补位：如果数字 + 符号位为奇数，出现半个字节，在最高位补 0000 凑齐一个字节

3. 数据校验码

I. 概念

  • 距离：两个码字间不同位的个数
  • 码距：所有码字间最小距离
    • 码距 = 1，无检错能力
    • 码距 = 2， 发现错误，如奇偶校验
    • 码距 > 2，纠错能力，如海明校验、CRC 校验

II. 奇偶校验

  • 特点：1 位校验位，检查单错

    • 奇校验：1 的个数为奇数，如果出错 1 位，1 的个数为偶数，发现错误
    • 偶校验：1 的个数为偶数

  • 举例

    image-20191117191719012

III. 海明校验

  • 特点

    • k 位数据，r 位校验，满足image-20191117192644561
    • 校验位放在 2 的幂次位上
    • 第 i 个校验位，每次校验连续 i 位、空 i 位、连续 i 位，校验采用奇偶校验
    • 只能检测 1 位错

  • 举例

    image-20191117194701042

IV. CRC 校验

  • 模 2 运算

    • +/-：按位加/减，最高位进/借位舍弃，其实就是按位异或

    image-20191117195456472

    • *：部分积按异或处理

    image-20191117195641598

    • /：求部分余数时按异或处理，部分余数位数少于除数位数时，该部分余数为最终余数

    image-20191117195655429

  • 编码方式

    image-20191117195945419

    image-20191117200040022

    • 生成多项式：k + 1 位
    • 校验：CRC 校验码可被对应生成多项式模 2 除尽
    • 纠错：不同出错位余数不一样，出错后得到不为 0 的余数，补 0 继续模 2 除，CRC 码循环左移，当余数位出错表最后一位时，出错位被移到 CRC 码的最高位，送入反向门纠错，继续移位，直到除尽

  • 举例

    image-20191117200222568

    image-20191117200605575

    假设 A3 出错变为 1，则除不尽，开始纠错：

    image-20191117201241893

4. 定点数表示

I. 正负号的表示

  • 无符号数：无 +/-
  • 带符号数：设置最高位为符号位，0 表 +，1 表 -

image-20191117202545608

II. 小数点的表示

  • MSB：Most Significant Bit，带符号数最高有效位（不包括符号位）
  • LSB：Last Significant Bit
  • 定点整数：小数点位置定在最低数值位之后
    image-20191117202942198
  • 定点小数：小数点定在符号位之后
    image-20191117203034326

III. 原码

  • 表示：符号位 + 真值
  • 小数举例
    image-20191117203425358
  • 整数举例
    image-20191117203446435
  • 0 的表示
    image-20191117203504901

IV. 补码

  • 模：M，运算上限，超出此值自动丢弃
  • 补：a + b = M，称为 a、b 互补
  • 同余：x = y (mod M)，最典型的例子是钟表中 3 点和 15 点指针位置一样，这就是 M = 12，3 = 15 (mod 12)，3、15 同余
  • 补码原理：x - b = x - (M - a) = x + a - M = x + a，所以补码中的减法均可使用加法代替
  • 原码 -> 补码
    • 正数：补码 = 原码
    • 负数：补码 = 按位取反 + 1
  • 小数补码
    image-20191117205214080
  • 整数补码
    image-20191117205233666
  • 变形补码：设置两个符号为，00 为 + ，11 为 -，模变成 4，方便进行溢出判断
    image-20191117205528582

V. 移码

定义：image-20191128085000061

  • 2k 被称为偏置常数/位移量

意义：相当于将真值在数轴上整体向右平移，这样负数部分全部移到正值，方便数值比较（不用管符号位了，直接按无符号数比较就可以）

image-20191128085101078

移码计算方法：补码符号位取反就是移码

image-20191128085446716
image-20191128104656838

VI. 反码

  • 正数反码：反码 = 原码
  • 负数补码：反码 = 原码按位取反

三、定点数运算

1. 加减运算

I. 原码加减

  • 加法：
    • 无溢出：正常正值
    • 有溢出：变为负值，输出的其实是补码，需要转换
  • 减法：
    • 够减：正常正值
    • 不够减：负值，需要求补变正

出现上下溢出的时候都存在补码差的问题，所以没有人直接强行用原码加减，大多采用减法转化为加补码的形式。

II. 补码加减

  • 核心公式：[X +/- Y]补 = [X]补 +/- [Y]补 (mod 2)

    • + ：直接加
    • -：减数求补后减

  • 举例

    image-20191119150835227

  • 溢出：结果的最高数位侵入符号位，应该是为出错，判别方法如下

    • 正 + 正 = 正，负 + 负 = 负

    • 最高数值位与符号位向更高位的进位不能同时产生

    • 双符号位的值位 01 or 10（变形补码）

    image-20191119151502687

2. 乘法运算

I. 原码一位乘法

定点小数

  • 计算思想：部分积叠加计算

    • 被乘数：image-20191119152308074
    • 乘数：image-20191119152541865
    • 乘积：image-20191119152727838

  • 算法

    1. 参加运算的两个数均为原码，两数符号位不参加运算，取其绝对值做无符号数乘法
    2. 设部分积初值为0。为防止运算过程中产生暂时性溢出，部分积采用单符号位参加运算。n位数相乘，部分积连同符号位应取n+1位；
    3. 运算前先检测0，只要两数有任意一个为0，则乘积为0，不再进行运算；
    4. 部分积运算：用乘数的最低位作为判断位，若为1，加被乘数；若为0，不加（相当于加0）；运算后部分积逻辑右移一位（将乘数符号位消去）

  • 举例

    image-20191119153843977

    运算结果：0.1000 1110

定点整数

  • 计算思想：同小数

  • 举例（其中 ->1 表示右移 1 位）

    image-20191119154913510

II. 补码一位乘法

  • 核心公式：image-20191119194500113

    证明：image-20191119194523802

  • 算法

    1. 设部分积初值为0，部分积采用双符号位运算，但乘数只需要一位符号位参加运算
    2. 乘数最低位之后增加一位附加位Yn+1 ，且初始令Yn+1=0；
    3. 运算前检测0，只要X、Y有任意一个为0，则乘积为0，不再运算；
    4. 用乘数的最低两位YnYn+1作为判断位，其比较值 (Yn+1-Yn) 始终决定了每次应执行的操作（算数右移）
    5. 重复n+1次比较和运算，但只右移n次，最后一次只运算不移位。
    6. 运算完成后，为避免误差，乘数的最低两位YnYn+1清0。

  • 小数举例

    image-20191119162759700

  • 整数举例

    image-20191119163115268

III. 补码两位乘法

  • 核心公式：image-20191119195006510

    其中，Z 表示部分积，上述公式由补码一位乘法简单推得

  • 算法

    1. 部分积采用三位符号位运算，初值为0
    2. 乘数最低位之后增加一位附加位Yn+1 ，初始令Yn+1=0；
    3. 运算前检测0：只要X、Y有任意一个为0，则乘积为0，不再进行运算；
    4. 设乘数数值部分为n位（移位是算数右移）
      • 当n为奇数时：乘数设1位符号位，做(n+1)/2次运算和移位，最后一步右移1位；
      • 当n为偶数时，乘数设2位符号位，做(n/2)+1次运算，n/2次移位，最后一步不移位。
    5. 运算完成后，为避免误差，乘数的最低三位Yn-1YnYn+1清0。

3. 除法运算

I. 原码恢复余数除法

  • 核心公式：image-20191120104001367

  • 举例

    image-20191120104056468

II. 原码加减交替除法

  • 核心公式

    image-20191120104354818

    当某步试减操作不够减时，并不需要立即恢复余数，只要下一步试减直接做加法即可

  • 算法

    1. 参加运算的数均为原码，两数符号位不参加运算，取其绝对值做无符号数除法；

    2. 符号位：由两数符号“异或”产生；

    3. 运算前检测：

      • 若 X* 为 0，则商为0；
      • 若 Y* 为0，按非法除数处理；
      • 应满足 X* < Y*，否则按溢出处理；

    4. 商的储之初值

      1. 0（被除数单倍字长）
      2. 被除数低位部分（被除数双倍字长）；

    5. 部分余数

      • 初值：

        1. 被除数（被除数单倍字长）
        2. 被除数高位部分（被除数双倍字长）。

      • 符号位：单符号位，且符号位初值为0（取X*）；

    6. 部分余数的运算
      逻辑移位

      image-20191120105329159

    7. 运算结束

      image-20191120105540371

  • 举例

    image-20191120150024299

    原码加减交替除法同样适用于整数，但被除数应采用双倍字长运算，否则当单字长被除数的绝对值小于除数时，得不到整数商

4. 十进制运算

BCD 码运算

计算思路

  1. 将BCD码看成二进制数，进行二进制加法
  2. 对二进制和进行修正，转换成BCD码

一位8421码加法

image-20191120162147248

一位余 3 码加法

image-20191120162224733

n 位十进制加法器

image-20191120162305769

例题

image-20191120162415009

image-20191120162358787

四、定点运算器件

1. 加法器原理

I. 行波进位加法器

image-20191120150822557

  • 进位逻辑：image-20191120150911907

    • 进位生成函数：image-20191120150945994，该项为 1 表示进位可由“本级运算单元” 产生，所以叫做“生成”
    • 进位传递函数：image-20191120151026152，该项为 1 表示“低一级运算单元”的进位可以“传递”到“高一级运算单元”

  • 四位行波进位加法器

    image-20191120151244013

  • 特点：进位延迟时间长

II. 先行进位加法器

进位信号直接由进位函数和最低位进位输入产生，而进位函数是直接由加数生成的，与低一位进位信号无关。

image-20191120151807507
image-20191120151818771

  • 四位先行进位加法器

    image-20191120151455814

  • 特点：受门电路扇入系数的影响，最多 8 位

III. 成组先行-级联进位加法器

组内采用先行进位方式，组间采用串行进位

image-20191120152439552

  • 十六位加法器

    • 组内：先行进位

    image-20191120152357353

    • 组间：串行进位

  • 特点：位数越多，加速效果越差

IV. 多级先行进位加法器

组内采用先行进位，组间也采用先行进位

image-20191120153329812

  • 十六位加法器（4 * 4 划分）

    • 组内：先行进位

    • 组间：先行进位
      分析一下组件的进位信号，可以得出：

      image-20191120152913593

    image-20191120152932328

  • BLCA，Block Carry Look Ahead，成组先行进位部件：输出组间进位函数 P、G

    image-20191120153306344

2. 算数逻辑单元 ALU

ALU，Arithmetic Logic Unit，是同时具有算数、逻辑运算功能并具备简单选择控制能力的运算电路

image-20191120160106180

成组先行-级联进位

image-20191120160310378

二级先行进位

image-20191120160342113

三级全先行进位

image-20191120160418561

3. 定点运算器

image-20191120160529168

  • 需要设置2个暂存器协调ALU输入/输出端同时传送问题；
  • 完成一次加法运算需要3个CPU时钟周期的时间；
  • 结构简单、规整，运算速度慢

image-20191120160649971

  • ALU的输入/输出端只需要设一个暂存器
  • 运算器完成一次加法运算需要2个CPU时钟周期的时间
  • 两条总线之间的传输可通过ALU进行，或通过设置专用的总线连接器实现

image-20191120160733378

  • 运算器完成一次加法运算只需要1个CPU时钟周期的时间，运算速度不再受总线分时使用的限制，在此总线已不是影响运算器性能的主要因素

4. 阵列乘除法器

利用全加器阵列，完全由硬件直接计算乘法结果

image-20191120161159318
image-20191120161232006

  • 保留进位加法
    • 本位的两个数相加，产生的进位信号不马上传递到本级加法器的高一位来参加本级的加法过程，而是暂时予以保留，以便参加下一级加法器高一位相加的加法。
    • 保留进位加法是一种特殊的快速加法，可以减少加法的进位传递时间，阵列乘法器中经常用到。
    • 相应的加法器则称为保留进位加法器（Carry Save Adder，CSA）。CSA与普通加法器的区别仅在于全加器进位输入输出端的连接方法上。
    • 普通的串行进位加法器则缩写为CPA（ carry propagate Adder ）

五、浮点数运算

I. 浮点数表示法

牺牲精度换取数据表示范围（同等长度下浮点数精度小于定点数）

image-20191128084540321

浮点数 = 数值 * 指数，即 image-20191128084634775

  • M：尾数（常用补码表示，方便计算）
  • R：基数（一般取 2 的整数幂，基越大，范围越大，但是精度越小）
  • E：阶码（常用移码表示，方便比较大小）

书写：image-20191128084815814

规格化浮点数：类似于科学计数法对尾数的要求，规定尾数最高位必须是一个有效数值，比如尾数用原码表示的话，0.0001 不是规格化浮点数的尾数，0.1 才是规格化浮点数的尾数

  • 右规：尾数值溢出到符号位时，将尾数右移一位，阶码 + 1
  • 左规：尾数小于规格化尾数值，将尾数左移 n 位，解码 - n

0 的表示

  • 真值为 0
  • 尾数为 0
  • 阶码达到最小值，尾数仍为非规格化的
  • 阶码小于最小值（下溢）

规格化浮点数表示范围

以下假设基为 2，阶码数值位 k 位，尾数数值位 n 位

  • 阶码用移码表示，尾数用原码表示

    image-20191128092408969

  • 阶码用移码表示，尾数用补码表示

    image-20191128093349667

隐藏位表示：由于规格化的要求，最高位一定是有效位，所以有很多设计为了省空间，将尾数的第一位隐藏掉，不过考试中为了避免二义性不会出现隐藏位表示法

例题

image-20191128094205302

II. IEEE754 浮点标准

这个标准将尾数的符号位提到最前边，是为了方便浮点数大小比较

image-20191128094612055

注意这里移码偏置常量取image-20191128101003147

image-20191128101103594

注意 M 使用了隐藏位，实际能表示 23 ~ 0，移码偏置常量127

舍入规则

  • 就近舍入：标准默认，类似 0 舍 1 入
  • 朝 0 舍入：多余位直接丢弃
  • 朝 +∞ 舍入：多余位直接丢弃，若为正数最低有效位 +1
  • 朝 -∞ 舍入：多余位直接丢弃，若为负数最低有效位 -1

例题

image-20191128101202295
image-20191128101213696

III. 浮点数加减

核心步骤：对阶、尾数加减、规格化、舍入、溢出判断

注意：为了避免精度损失，要对尾数右移时溢出的保护位进行舍入

image-20191128101641549

  • 写出机器码

    image-20191128101742120

  • 对阶（小阶向大阶对齐）

    image-20191128101813586

    大数右移过程中的移出位要保护起来，不参与后续运算，但要在最终进行舍入操作

  • 尾数加减

    image-20191128101840442

  • 规格化

    image-20191128101920265

  • 舍入（注意所谓 0 舍 1 入都是针对 原码的）

    image-20191128102044893

  • 溢出判断：阶码无溢出

  • 结果

    image-20191128102141175

IV. 浮点数乘除

核心步骤：阶码加减、尾数乘除、规格化、舍入、溢出判断

乘法示例

image-20191128104128882

  • 写出机器码

    image-20191128104204938

  • 阶码加减

    image-20191128104736102

  • 尾数相乘（本例使用补码两位乘法）

    image-20191128105016979

  • 规格化：结果本身就是规格化的

  • 舍入为 4 位：[Mz]补 = 1.0111（舍）

  • 溢出检查：移码最高符号位为 0，不溢出

  • 结果

    image-20191128105801202

除法示例

image-20191128110352918

  • 机器数表示

    image-20191128110413532

  • 阶码相减

    image-20191128110441882

  • 尾数相除（采用原码加减交替除法）

    image-20191128110623253

  • 结果规格化：已经是规格化的

  • 舍入：不用舍入

  • 溢出检查：不溢出

  • 结果

    image-20191128110821272

六、浮点运算器件

基本配置：阶码加减部件 + 尾数四则运算部件

image-20191128111405177

浮点协处理器

image-20191128111524803

  • 可与 80X86 异步并行工作
  • IEEE754 浮点标准
  • 提供二进制浮点数、二进制整数、十进制数串等三大类 7 中数据类型的计算

提高运算器整体性能的措施

  • 时间重叠：多个处理过程轮流重叠使用同一套硬件的不同部分

  • 资源重复：多个硬件资源同时工作，比如浮点加法流水线

    image-20191128112100766

  • 资源共享：多个任务轮流使用同一套硬件

提高单个运算器性能的措施

  • 提高 ALU 运算速度
  • 缩短源操作数送 ALU 和写结果的时间
  • 采用阵列乘除法器等高速乘除法技术
  • 设置冗余的加法线路专门支持指令寻址