白中英计算机组成原理第2章-运算方法与运算器.ppt

第2章运算方法和运算器 2020年3月26日星期四 2 目录 2 0数据的类型2 1数据与文字的表示方法 掌握 2 2定点加法 减法运算 掌握 2 3定点乘法运算 理解 2 4定点除法运算 理解 2 5定点运算器的组成 了解 2 6浮点运算方法和浮点运算器 掌握 2020年3月26日星期四 3 学习要求 掌握定点和浮点数的表示方法 表示范围 掌握定点数的补码加减法 常用的乘除法运算方法 掌握浮点数的加减运算方法 掌握数据校验的方法 理解溢出判断方法 清楚运算器部件的组成结构及设计方法 2020年3月26日星期四 4 2 0数据的类型 1 2 按数制分 十进制 在微机中直接运算困难 二进制 占存储空间少 硬件上易于实现 易于运算 十六进制 方便观察和使用 二 十进制 4位二进制数表示1位十进制数 转换简单 按数据格式分 真值 没有经过编码的直观数据表示方式 其值可带正负号 任何数制均可 机器数 符号化编码后的数值 包括正负号的表示 一般位数固定 8 16 32 不能随便忽略任何位置上的0或1 2020年3月26日星期四 5 2 0数据的类型 2 2 按数据的表示范围分 定点数 小数点位置固定 数据表示范围小 浮点数 小数点位置不固定 数据表示范围较大 按能否表示负数分 无符号数 所有均为表示数值 直接用二进制数表示 有符号数 有正负之分 最高位为符号位 其余位表示数值 按编码不同又可分为原码 反码 补码 移码 2020年3月26日星期四 6 2 1数据与文字的表示方法 2 1 1数据格式2 1 2数的机器码表示2 1 1数据格式2 1 3字符与字符串的表示方法2 1 4汉字的表示方法2 1 5校验码 2020年3月26日星期四 7 定点数 小数点固定在某一位置的数据 纯小数 表示形式有符号数x xSx 1x 2 x n0 x 1 2 n xs为符号位无符号数x x 1x 2 x nx n 1 0 x 1 2 n 1 无符号位数据表示范围0 0 0 0 x 1 2 n 0 1 1纯整数 表示形式有符号数x xsxn 1 x1x0 x 2n 1 xs为符号位无符号数x xnxn 1 x1x00 x 2n 1 1 xn为数值位注意 小数点的位置是机器约定好的 并没有实际的保存 x0 x 1x 2x 3 x n xnxn 1xn 2 x1x0 2 1 1数据格式 定点数 设采用n 1位数据 2020年3月26日星期四 8 定点机的特点 所能表示的数据范围小使用不方便 运算精度较低存储单元利用率低 2020年3月26日星期四 9 2 1 2数的机器码表示 有符号数 计算机中是不会存储 号的 那么怎么表示符号位呢 怎么让符号位同数值位一道参加运算呢 这就是怎么样把真值转换成机器码 原 反 补 移码 重点 1 原码 补码 移码的表示形式2 补码的定义3 原码 补码 移码的表示范围 2020年3月26日星期四 10 1 原码表示法 定义 定义 定点小数 x 原 定点整数 x 原 举例 0 110 原 0 110 0 110 原 1 0 110 1 110 110 原 0110 110 原 23 110 1000 110 1110 x1 x 0 x表示真值 1 x 1 x 0 x 1 x2n x 0n表示数值位 2n x 2n x 0 x 2n 实际机器中保存时并不保存小数点 等到的就是机器码中的原码 xnxn 1xn 2 x1x0Xn是符号位 0表示正 1表示负 2020年3月26日星期四 11 1 原码表示法 特点 0有两种表示法 0 原 0000 0 原 1000数据表示范围定点小数 1 X 1定点整数 2n X 2n 若数值位n 3即 8 X 8 优点与真值对应关系简单 符号位 真值的绝对值缺点参与运算复杂 需要将数值位与符号位分开考虑 减法麻烦 2020年3月26日星期四 12 要将指向5点的时钟调整到3点整 应如何处理 5 2 3 5 10 3 12自动丢失 12就是模 补码表示法的引入 1 3 2020年3月26日星期四 13 继续推导 5 2 5 10 MOD12 5 2 5 10 MOD12 2 10 MOD12 结论 在模为12的情况下 2的补码就是10 一个负数用其补码代替 同样可以得到正确的运算结果 补码表示法的引入 2 3 2020年3月26日星期四 14 进一步结论 在计算机中 机器能表示的数据位数是固定的 其运算都是有模运算 若是n 1位整数 包含符号位 则其模为2n 1 若是小数 则其模为2 若运算结果超出了计算机所能表示的数值范围 则只保留它的小于模的低n位的数值 超过n位的高位部分就自动舍弃了 补码表示法的引入 3 3 2020年3月26日星期四 15 2 补码表示法 定义 定义 定点小数 x 补 定点整数 x 补 举例 0 110 补 0 110 0 110 补 10 0 110 1 010 110 补 0110 110 补 24 110 10000 110 1010 x1 x 0 2 x 2 x 0 x 1 x2n x 0 2n 1 x 2n 1 x 0 x 2n x为n 1位 mod2 模 真值 mod2n 1 实际机器中保存时并不保存小数点 xnxn 1xn 2 x1x0 2020年3月26日星期四 16 2 补码表示法 特点 0有唯一的表示法 0 补 24 0 mod24 0000 0 补数据表示范围定点小数 1 X 1定点整数 2n X 2n 若n 3 则 8 X 8 加减运算规则 X Y 补 X 补 Y 补 mod2 只要结果不溢出 可将补码符号位与数值位一起参与运算 x 补 补 x 原补码除2操作 可通过算术右移实现 0 0110 补 11010 则 0 0110 10 补 11101 真值为 0 0011 比原码多一个负的最小值表示 定点小数和定点整数 其编码为1000 2020年3月26日星期四 17 n位二进制数x 则取反后应该是2n 1 x 再加1就是y 2n 1 x 1 y取反后应该是2n 1 y 再加1就是z 2n 1 y 1 z 2n 1 2n 1 x 1 1 x 2020年3月26日星期四 18 0的补码唯一纯小数 0和 0的补码表示 0 补 0 补 2 0 00 0 0 00 0纯整数 0和 0的补码表示 0 补 0 补 2n 1 00 0 00 0 1和 2n的表示 1 补 2 1 10 00 0 1 00 0 1 00 0 2n 补 2n 1 2n 1000 0 100 0 100 0 2020年3月26日星期四 19 由原码求补码 由原码求补码的简便原则 负数 除符号位以外 其余各位按位取反 末位加1 从最低位开始 遇到的第一个1以前的各位保持不变 之后各位取反 例 X 原 110110100 X 补 101001 100 2020年3月26日星期四 20 由 X 补求 X 补连符号位一起各位求反 末位加1 例 X 补 1 1010101解 由 X 补求 X 补 此规则同样适用 求相反数的补码 X 补 11010101 00101010 1 X 补 00101011 2020年3月26日星期四 21 3 移码表示法 移码通常用于表示浮点数的阶码用定点整数形式的移码把真值平移2n个单位定义 x 移 2n x2n x 2n与 x 补的区别 符号位相反优点 可以比较直观地判断两个数据的大小 浮点数运算时 容易进行对阶操作 表示浮点数阶码时 容易判断是否下溢 当阶码为全0时 浮点数下溢 4位补码与移码 xnxn 1xn 2 x1x0 2020年3月26日星期四 22 原 补 移码的编码形式 正数 原 补码的编码完全相同 补码和移码的符号位相反 数值位相同 负数 原码 符号位为1数值部分与真值的绝对值相同补码 符号位为1数值部分与原码各位相反 且末位加1移码 符号位与补码相反 数值位与补码相同 2020年3月26日星期四 23 课本P22例6以定点整数为例 用数轴形式说明原码 反码 补码 移码表示范围和可能的数码组合情况 2020年3月26日星期四 24 2020年3月26日星期四 24 课本P22例7将十进制真值 127 1 0 1 127 列表表示成二进制数及原码 反码 补码 移码值 符号位 0 1 数值位各位取反 数值位末位加1 符号位 正负数 取反 负数时 2020年3月26日星期四 25 P22例8设机器字长16位 定点表示 尾数15位 数符1位 问 1 定点原码整数表示时 最大正数是多少 最小负数是多少 2 定点原码小数表示时 最大正数是多少 最小负数是多少 215 1 32767 215 1 32767 1 2 15 1 1 32768 1 2 15 1 1 32768 定点原码整数最大正数最小负数定点原码小数最大正数最小负数 2020年3月26日星期四 26 2 1 1数据格式 浮点数 浮点数 小数点位置可变 形如科学计数法中的数据表示 浮点数格式定义 N Re MM 尾数 mantissa 是一个纯小数 整数部分为0的小数 表示数据的全部有效数位 决定着数值的精度 R 基数 radix 可以取2 8 10 16 表示当前的数制 微机中 一般默认为2 隐含表示 e 阶码 exponent 是一个整数 用于指出小数点在该数中的位置 决定着数据数值的大小 机器数的一般表示形式 2020年3月26日星期四 27 科学计数法的表示 一个十进制数可以表示成不同的形式 同理 一个二进制数也可以有多种表示 2020年3月26日星期四 28 浮点数规格化 浮点数的表示1 11 20 0 111 21 11 1 2 1规格化的目的保证浮点数表示的唯一性 保留更多地有效数字 提高运算的精度 规格化要求1 R 尾数 1 R为基数 如2 即大于1 2规格化处理 尾数向左移n位 小数点右移 同时阶码减n 尾数向右移n位 小数点左移 同时阶码加n 右规 左规 2020年3月26日星期四 29 浮点数的规格化 尾数用原码表示时尾数数值最高数值位为1 尾数形如0 1 正 或1 1 负 例如 0 011 25要规格化则变为0 11 24 0 011 25要规格化则变为1 11 24 尾数用补码表示时尾数最高数值位和尾数符号位相反 尾数形如0 1 正 或1 0 负 例如 0 011 25要规格化 则变为0 11 24 0 011 25要规格化 则变为1 01 24 2020年3月26日星期四 30 浮点数的数据表示范围N Re M 0 最大负数 最小正数 最小负数 最大正数 下溢区 上溢区 上溢区 负数区 正数区 浮点数的溢出 阶码溢出上溢 阶码大于所能表示的最大值 无穷下溢 阶码小于所能表示的最小值 0机器零 尾数为0 或阶码小于所能表示的最小值 2e 0 2020年3月26日星期四 31 浮点数的最值N M Re 设浮点数格式为 移码表示 2m 2m 1 补码表示 1 1 2 n 1 2 2m 1 2 n 2 2m 2 n 2 2m 1 2 n 2 2m 1 1 1 11 1 00 00 0 0 00 1 11 11 0 0 00 0 00 01 1 1 11 0 11 11 同左 同左 00 00 101 11 2 1 2 n 2 2m 2 1 2 2m 同左 同左 00 00 010 00 2020年3月26日星期四 32 例1 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码采用补码表示 尾数采用原码表示 分析其浮点数表示范围 最大正数N M Re最大正数为0 11 1 2011 1即 1 2 9 231该浮点数即为规格化数形式 阶码补码 尾数原码 2020年3月26日星期四 33 例1 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码采用补码表示 尾数采用原码表示 分析其浮点数表示范围 最小正数N M Re非规格化数形式最小正数为0 0 01 210 0即2 9 2 25 2 9 2 32规格化数形式最小正数为0 1 210 02 1 2 25 2 33 阶码补码 尾数原码 2020年3月26日星期四 34 例1 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码采用补码表示 尾数采用原码表示 分析其浮点数表示范围 最小负数N M Re最小负数为 0 1 1 201 1即 1 2 9 2 25 1 1 2 9 231该浮点数即为规格化数形式 阶码补码 尾数原码 2020年3月26日星期四 35 例1 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码采用补码表示 尾数采用原码表示 分析其浮点数表示范围 最大负数非规格化数形式最大负数为 0 0 01 210 0即 2 9 2 25 2 9 2 32规格化数形式最大负数为 0 1 210 0即 2 1 2 25 2 1 2 32 阶码补码 尾数原码 2020年3月26日星期四 36 例2 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码和尾数均采用补码表示 分析其规格化浮点数表示范围 最大正数阶码最大 尾数最大最大正数为0 11 1 211 1 1 2 9 231最小正数 规格化后 最小正数为0 10 00 2 32即2 32 2 1 2 33注意 不是因为0 0 1 2 32不是规格化数 阶码补码 尾数补码 2020年3月26日星期四 37 例2 设浮点数的阶码6位 含符号位 尾数为10位 含符号位 阶码和尾数均采用补码表示 分析其规格化浮点数表示范围 最小的负数最小负数为 1 00 0 231即231 1 231最大的负数最大负数为 0 10 01 2 32即 2 9 2 1 2 32注意 因有规格化要求 不是 阶码补码 尾数补码 2020年3月26日星期四 38 浮点数的IEEE754标准表示 IEEE InstituteofElectricalandElectronicsEngineers 美国电气及电子工程师学会IEEE是一家总部在美国的工程技术和电子专家的组织 IEEE致力于电气 电子 计算机工程和与科学有关的领域的开发和研究 也是计算机网络标准的主要制定者 为便于软件移植 按照IEEE754标准 实际机器内32位浮点数和64位浮点数的标准格式如下 0 22 23 30 31 23位尾数 仅为数值部分 8位阶码 包括阶符 1位数符 32位浮点数 0 51 52 62 63 64位浮点数 11位阶码 包括阶符 52位尾数 仅为数值部分 1位数符 2020年3月26日星期四 39 32位浮点数的IEEE754标准表示 数符S 表示浮点数的符号 占1位 0 正数 1 负数 尾数M 23位 原码纯小数表示 小数点在尾数域的最前面 由于原码表示的规格化浮点数要求 最高数值位始终为1 因此该标准中隐藏最高数值位 1 尾数的实际值为1 M 阶码E 8位 采用有偏移值的移码表示 移127码 即E e 127 E的8位二进制数即为移127码的编码 浮点数的真值 N 1 S 1 M 2E 127 阶码移码 尾数原码 2020年3月26日星期四 40 IEEE754标准格式 64位格式 其真值表示为 x 1 S 1 M 2E 1023e E 1023 2020年3月26日星期四 41 IEEE754标准的数据表示 IEEE754标准中的阶码E正零 负零E与M均为零 正负之分由数据符号确定 正无穷 负无穷E为全1 M为全零 正负之分由数据符号确定 阶码E的其余值 00000001 11111110 为规格化数据 真正的指数e的范围为 126 127 E 00000000 M 0000 0000 E 11111111 M 0000 0000 00000000 11111111 2020年3月26日星期四 42 IEEE754标准对特殊数据的表示 2020年3月26日星期四 43 课本P18例1 例1 若浮点数 的754标准存储格式为 41360000 16 求其浮点数的十进制数值 解 41360000 16 01000001001101100000000000000000指数e E 127 10000010 01111111 00000011 3尾数1 M 1 01101100000000000000000 1 011011浮点数N 1 S 1 M 2e 1 0 1 011011 23已经是标准化 11 375 10 数符S 阶码E 尾数M 2020年3月26日星期四 44 课本P18例2 例2 将 20 59375 10转换成754标准的32位浮点数的二进制存储格式 解 20 59375 10 10100 10011 2将尾数规范为1 M的形式 10100 10011 1 010010011 24e 4可得 M 010010011S 0E 4 127 131 10000011故 32位浮点数的754标准格式为 01000001101001001100000000000000 41A4C000 16 2020年3月26日星期四 45 单精度浮点数与双精度浮点数 高级语言的float double使用的即是IEEE754规定的格式 float 32位浮点值 也叫单精度浮点数 4字节保存 double 64位浮点值 也叫双精度浮点数 8字节保存 单精度浮点数的例子 1位8位7位8位8位 1100 0 01 2020年3月26日星期四 46 单精度浮点数与双精度浮点数 除0之外 IEEE754标准中单精度浮点数所能表示的绝对值最小的规格化浮点数的格式为 S0000000100000000000000000000000V 1 S 2 126 1 M 1 S 2 126 1 0 00 0 除 之外 IEEE754标准中单精度浮点数所能表示的绝对值最大的规格化浮点数的格式为 S1111111011111111111111111111111V 1 S 2 127 1 M 1 S 2 126 1 1 11 1 2020年3月26日星期四 47 求解技巧 例如 将下列十进制数表示成IEEE754格式的32位浮点数二进制存储形式 27 3211 512求解 27 32 27 1 32 00011011 2 2 5尾数 1 1011 阶码 e 5 4 1 E e 127 126IEEE754数据 0011111101011000000000000000000011 512 00001011 2 2 9尾数 1 011 阶码 e 9 3 6 E e 127 121IEEE754数据 0011110010110000000000000000000 2020年3月26日星期四 48 例 将十进制数 54表示成二进制定点数 16位 和浮点数 16位 其中数值部分10位 阶码部分4位 阶符和数符各取1位 并写出它在定点机和浮点机中的机器数形式 令x 54 则x 11011016位定点数真值表示 x 000000000110110定点机器数形式 x 原 x 补 浮点数规格化表示 x 0 1101100000 2110浮点机器数形式 x 原 x 补 非IEEE754标准 1000000000110110 1111111111001010 00110 11101100000 00110 10010100000 2020年3月26日星期四 49 最大正数 x 1 1 2 23 2127最小正数 x 1 0 2 128最小负数 x 1 1 2 23 2127最大负数 x 1 0 2 128 课本P23例9假设一个32位非零规格化浮点数 真值表示为 问 它所表示的规格化的最大正数 最小正数 最大负数 最小负数是多少 尾数用原码表示 类似IEEE 但不是 0 11111111111111111111111 11111111 0 00000000000000000000000 00000000 1 11111111111111111111111 11111111 1 00000000000000000000000 00000000 2020年3月26日星期四 50 浙江大学考研试题 计算机储存程序的特点之一是把数据和指令都作为二进制信号看待 今有一计算机字长32bit 数符位是第31bit 单精度浮点数格式如图所示 对于二进制数10001111111011111100000000000000 表示一个补码整数 其十进制值是多少 表示一个无符号整数 其十进制值是多少 表示一个IEEE754标准的单精度浮点数 其值是多少 2020年3月26日星期四 51 二进制数10001111111011111100000000000000 表示一个补码整数 其十进制值是多少 作为补码整数 其对应的原码是11110000000100000100000000000000十进制值是 230 229 228 220 214 表示一个无符号整数 其十进制值是多少 作为无符号整数 其十进制值是231 227 226 225 224 223 222 221 219 218 217 216 215 214 2020年3月26日星期四 52 二进制数10001111111011111100000000000000 作为IEEE754标准的单精度浮点数阶码E是00011111指数e 阶码E 127 00011111 01111111 1100000B 96D尾数M 11011111100000000000000则1 M 1 11011111100000000000000 1 110111111 单精度浮点数值为 X 1 s 1 M 2e 1 110111111 2 96 0 1110111111 2 95 14 16 1 15 16 2 12 16 3 2 95 0 3115 2 95 2020年3月26日星期四 53 2009考研真题 12 一个C语言程序在一台32位机器上运行 程序中定义了三个变量x y和z 其中x和z是int型 y为short型 当x 127 y 9时 执行赋值语句z x y后 x y和z的值分别是 x 0000007FH y FFF9H z 00000076Hx 0000007FH y FFF9H z FFFF0076Hx 0000007FH y FFF7H z FFFF0076Hx 0000007FH y FFF7H z 00000076H 2020年3月26日星期四 54 2010考研真题 14 假定变量i f d数据类型分别为int float double int用补码表示 float和double用IEEE754单精度和双精度浮点数据格式表示 已知i 785 f 1 5678e3 d 1 5e100 若在32位机器中执行下列关系表达式 则结果为真的是 I i int float i II f float int f III f float double f IV d f d fA 仅I和IIB 仅I和IIIC 仅II和IIID 仅III和IV 关键是 两端的数据类型是否一致 2020年3月26日星期四 55 2 1 1数据格式 十进制数串的表示方法 字符串形式每个十进制数位占用一个字节 除保存各数位 还需要指明该数存放的起始地址和总位数 主要用于非数值计算的应用领域 压缩的十进制数串形式采用BCD 二 十编码 码表示 一个字节可存放两个十进制数位 4 1节省存储空间 便于直接完成十进制数的算术运算 用特殊的二进制编码表示数据正负 如1100 正 1101 负 2020年3月26日星期四 56 2 1 3字符与字符串的表示方法 ASCII码 美国国家信息交换标准字符码 包括128个字符 共需7位编码 ASCII码规定 最高位为0 余下7位作为128个字符的编码 最高位的作用 奇偶校验 扩展编码 字符串指连续的一串字符 每个字节存一个字符 当存储字长为2 或4个字节时 在同一个存储单元中 可按从低位字节向高位字节的顺序存放字符串的内容 或按从高位字节向低位字节的次序顺序存放字符串的内容 2020年3月26日星期四 57 2 1 4汉字的表示方法 汉字的输入编码目的 直接使用西文标准键盘把汉字输入到计算机 分类 主要有数字编码 拼音码 字形编码三类 汉字内码用于汉字信息的存储 交换 检索等操作的机内代码一般采用两个字节表示 为了和ASCII区别 最高位为1 汉字字模码用点阵表示的汉字字形代码 用于汉字的输出 2020年3月26日星期四 58 中文编码 字符代码化 输入 数字码拼音码字形码 2020年3月26日星期四 59 汉字字模码 2020年3月26日星期四 60 2 1 5校验码 数据校验 数据校验原因为减少和避免数据在计算机系统运行或传送过程中发生错误 在数据的编码上提供了检错和纠错的支持 数据校验码的定义能够发现某些错误或具有自动纠错能力的数据编码 也称检错码 数据校验的基本原理是扩大码距 码距 任意两个合法码之间不同的二进制位的最少位数 仅有一位不同时 称其码距为1 2020年3月26日星期四 61 码距及作用 设用四位二进制表示16种状态16种编码都用到了 此时码距为1 任何一种状态的四位码中的一位或几位出错 就变成另一个合法码 无查错能力 若用四位二进制表示8个状态只用其中的8种编码 而把另8种编码作为非法编码 可使码距扩大为2 注意 并不是任选8种编码都可扩大码距 2020年3月26日星期四 62 校验码的类型 奇偶校验码判断数据中1的个数设置1位校验位 分奇校验和偶校验两种 只能检错 无纠错能力 海明校验码在奇偶校验的基础上增加校验位而得 具有检错和纠错的能力 循环冗余校验码 CRC 通过模2的除法运算建立数据信息和校验位之间的约定关系 具有很强的检错纠错能力 2020年3月26日星期四 63 奇偶校验码 概念 奇偶校验原理在数据中增加1个冗余位 使码距由1增加到2 如果合法编码中有奇数个位发生了错误 就将成为非法代码 增加的冗余位称为奇偶校验位 校验的类型偶校验 每个码字 包括校验位 中1的数目为偶数 奇校验 每个码字 包括校验位 中1的数目为奇数 校验过程发送端 按照校验类型 在发送数据后添加校验位P 接收端 对接收到的数据 包括校验位 进行同样类型的校验 决定数据传输中是否存在错误 2020年3月26日星期四 64 奇偶校验码 校验原理 偶校验 在接收端求校验位P D7 D6 D5 D4 D3 D2 D1 D0 P若P 0 则无错 若P 1 则有错 奇校验 在接收端求校验位P D7 D6 D5 D4 D3 D2 D1 D0 P若P 1 则无错 若P 0 则有错 电路实现 一般采用异或电路得到校验位 10101011 求校验码 偶校验码101010111 奇校验码101010110 2020年3月26日星期四 65 接收端 字 校验位 校验码 例1 数据00100001 奇校验码 00100001 1 偶校验码 00100001 0 例2 数据 01110101 偶校验码 01110101 1 发送端 门电路 01100101 1 出错 奇偶校验码 例题 1 2 2020年3月26日星期四 66 例3 数据 01110101 奇校验码 01110101 0 发送端 门电路 01100111 0 接收端 正确 奇偶校验只能发现奇数个错误 且不能纠正错误 奇偶校验码 例题 1 2 2020年3月26日星期四 67 海明码 海明码是1950年提出的 只要增加少数的几位校验码 即可检测出多位出错 并能自动恢复一或几位出错信息 实现原理 在一个数据中加入几个校验位 每个校验位和某几个特定的信息位构成偶校验的关系 接收端对每个偶关系进行校验 产生校验因子 通过校正因子区分无错和码字中的n个不同位置的错误 不同代码位上的错误会得出不同的校验结果 2020年3月26日星期四 68 海明码 确定校验位的位数 设K为有效信息的位数 r为校验位的位数 则整个码字的位数N应满足不等式 N K r 2r 1通常称为 N K 海明码设某 7 4 海明码表示的码字长度为位 校验位数为位 例如 数据D3D2D1D0 1001K 4 r 5 2r 可知 需要校验位3位P3P2P1 7 3 2020年3月26日星期四 69 海明码 确定校验位的位置 数据表示数据位D DiDi 1 D1D0 校验位P PjPj 1 P2P1 海明码H 包括数据位和校验位 HmHm 1 H2H1 分组原则每个校验位Pi从低到高被分在海明码中位号2i 1的位置 例如 数据D3D2D1D0 1001 校验位P3P2P1海明码共7位H7H6 H2H1 各位分配如下 P1 P2 P3 D0 D1 D2 D3 2020年3月26日星期四 70 海明码 校验分组 校验原则海明码的每一位Hi有多个校验位校验 其关系是被校验的每一位位号等于校验它的各校验位的位号之和 每个信息位的位置写成用2的幂次之和的形式 例如H7参与H1 H2 H4的校验 H6参与H2 H4的校验 H5参与H1 H4的校验 H3参与H1 H2的校验 分组情况 P1 P2 P3 D0 D1 D2 D3 第一组P1 第二组P2 第三组P3 第一组 P1 D3 D1 D0 第二组 P2 D3 D2 D0 第三组 P3 D3 D2 D1 2020年3月26日星期四 71 海明码 校验位的形成 校验位形成公式P1 第一组中所有位 除P1 求异或 Pj 第j组中所有位 除Pj 求异或为了能检测两个错误 增加一位校验Pj 1 放在最高位 Pj 1 所有位 包括P1 P2 Pj 求异或例如 P1 D3 D1 D0 1 0 1 0P2 D3 D2 D0 1 0 1 0P3 D3 D2 D1 1 0 0 1P4 D3 D2 D1 D0 P3 P2 P1 1 0 0 1 0 0 1 1 第一组 P1 D3 D1 D0 第二组 P2 D3 D2 D0 第三组 P3 D3 D2 D1 但不能纠错 2020年3月26日星期四 72 海明码 接收端校验 1 2 接收端接收到数据后 分别求S1 S2 S3 SjS1 第一组中所有位 包括P1 求异或 Sj 第j组中所有位 包括Pj 求异或Sj 1 Pj 1 所有位 包括P1 P2 Pj 求异或当Sj 1 1时 有一位出错 由Sj S3S2S1的编码指出出错位号 将其取反 即可纠错 当Sj 1 0时 无错或有偶数个错 两个错的可能性比较大 当Sj S3S2S1 0 000时 接收的数无错 否则有两个错 2020年3月26日星期四 73 同上例 接收端接收的数据为接收端求SS1 0 1 0 1 0S2 0 1 0 1 0S3 1 1 0 0 0S4 1 1 0 0 1 1 0 0 0若接收端接收到错误的数据S1 0 1 0 1 0S2 0 1 1 1 1S3 1 1 1 0 1S4 1 1 1 0 1 1 0 0 1 海明码 接收端校验 2 2 第一组 P1 D3 D1 D0 第二组 P2 D3 D2 D0 第三组 P3 D3 D2 D1 无错误 1 S4 1 有错误 S3S2S1 110 H6位有错 应取反 2020年3月26日星期四 74 练习 设待校验的数据为D7 D0 10101011 写出其海明校验码 解 确定海明校验位的位数因为K 8 由N K r 2r 1 得9 r 2r 校验位的位数为r 4 确定校验位的位置i 121110987654321D7D6D5D4P4D3D2D1P3D0P2P1 分组 N位分r组 2020年3月26日星期四 75 练习 设待校验的数据为D7 D0 10101011 写出其海明校验码 校验位的形成P1 D6 D4 D3 D1 D0 1 P2 D6 D5 D3 D2 D0 1P3 D7 D3 D2 D1 1 P4 D7 D6 D5 D4 0所以 信息码10101011的海明校验码为 101001011111 2020年3月26日星期四 76 海明码的纠错与检错能力 一个系统能纠正一位差错时 码距最小是3 码距为3时 或能纠正一位错 或能检测二位错 但不能同时纠正一位错并检测二位错 码距为1至7时 海明码的纠错和检错能力如右表 码距越大 纠错能力越强 但数据冗余也越大 即编码效率低了 2020年3月26日星期四 77 CRC校验 CRC的工作方法在发送端产生一个循环冗余码 附加在信息位后面一起发送到接收端 接收端收到的信息按发送端形成循环冗余码同样的算法进行校验 若无错 则接收 若有错 需重发 CRC的特点可检测出所有奇数位错 可检测出所有双比特的错 可检测出所有小于 等于校验位长度的突发错 CRC码的信息字段和校验字段的长度可以任意选定 2020年3月26日星期四 78 2 2定点加法 减法运算 2 2 1补码加法2 2 2补码减法2 2 3溢出概念与检验方法2 2 4基本的二进制加法 减法器 2020年3月26日星期四 79 2 2 1补码加法 补码加法运算基本公式定点整数 x y 补 x 补 y 补 mod2n 1 定点小数 x y 补 x 补 y 补 mod2 证明 1 证明依据 补码的定义 以定点小数为例 2 证明思路 分三种情况 a x y均为正值 0 0 b x y一正一负 0 0或者 0 c x y均为负值 0 0 2020年3月26日星期四 80 补码加法公式证明 1 2 证明 a 0 0 补 补 补 mod2 b 0 0 x 补 2 x y 补 2 y x 补 y 补 2 x 2 y 2 2 x y 2 x y 补 mod2 x y 补 2020年3月26日星期四 81 补码加法公式证明 2 2 c 0 0 0的证明与此相同 x 补 x y 补 2 y x 补 y 补 x 2 y 2 x y 当x y 0时 2 x y 2 进位2必丢失 因 x y 0 故 x 补 y 补 x y x y 补 mod2 当x y 0时 2 x y 2因 x y 0 故 x 补 y 补 2 x y x y 补 mod2 2020年3月26日星期四 82 定点数补码加法举例 例11 1001 0101 求 解 补 01001 补 00101 补01001 补00101 补01110所以 1110 例12 x 1011 0101 求 解 补 01011 补 11011 补01011 补11011 补100110所以 0110 2020年3月26日星期四 83 2 2 2补码减法 补码减法运算基本公式定点整数 x y 补 x 补 y 补 x 补 y 补 mod2n 1 定点小数 x y 补 x 补 y 补 x 补 y 补 mod2 证明 只需要证明 补 补已证明 x y 补 x 补 y 补 故 y 补 x y 补 x 补又 x y 补 x 补 y 补 故 y 补 x y 补 x 补可得 y 补 y 补 x y 补 x y 补 x 补 x 补 x y x y 补 x 补 x 补 x x 补 x 补 x 补 0 补等于 补的各位取反 末位加1 2020年3月26日星期四 84 定点数补码减法举例 例13 已知 1 1110 2 1101 求 1 补 1 补 2 补 2 补 解 1 补 10010 1 补 1 补 1 01101 00001 01110 2 补 01101 2 补 2 补 1 10010 00001 10011 注意课本上的错误 注意课本上的错误 2020年3月26日星期四 85 定点数补码减法举例 例14 1101 0110 求 解 补 01101 补 00110 补 11010 补 补 补 01101 11010 100111 00111 0111 01101 11010 100111 2020年3月26日星期四 86 2020年3月26日星期四 86 定点数补码加减法运算 基本公式定点整数 x y 补 x 补 y 补 mod2n 1 定点小数 x y 补 x 补 y 补 mod2 定点数补码加减法运算符号位和数值位可同等处理 只要结果不溢出 将结果按2n 1或2取模 即为本次运算结果 2020年3月26日星期四 87 例设机器字长为8位 补 10100011 补 00101101 求x y 解 补 11010011 补 补 补 10100011 11010011 101110110 01110110 118 10100011 11010011 101110110 x 93 y 45计算过程中 产生了溢出 93 45 138 128 2020年3月26日星期四 88 2 2 3溢出概念与检测方法 溢出在定点数机器中 数的大小超出了定点数能表示的范围 上溢数据大于机器所能表示的最大正数 下溢数据小于机器所能表示的最小负数 例如 4位补码表示的定点整数 范围为 8 7 若x 5 y 4 则x y产生上溢若x 5 y 4 则x y产生下溢若x 5 y 4 则x y产生上溢 2020年3月26日星期四 88 2020年3月26日星期四 89 例题 例15 1011 1001 求 解 补 0 1011 补 0 1001 补0 1011 补0 1001 补1 0100 例16 1101 1111 求 解 补 1 0011 补 1 0001 补1 0011 补1 0001 补0 0101 正数 正数 负数 负数 负数 正数 溢出 2020年3月26日星期四 90 溢出判别方法 直接判别法 方法 同号补码相加 结果符号位与加数相反 异号补码相减 结果符号位与减数相同 特点 硬件实现较复杂 举例 若 x 补 0101 y 补 0100 则 x y 补 1001若 x 补 1011 y 补 1100 则 x y 补 0111若 x 补 0101 y 补 1100 则 x y 补 1001 上溢 下溢 上溢 2020年3月26日星期四 91 溢出判别方法 变形补码判别法 变形补码 也叫模4补码 采用双符号位表示补码判别方法 特点 硬件实现简单 只需对结果符号位进行异或举例 若 x 补 00101 y 补 00100 则 x y 补 01001若 x 补 11011 y 补 11100 则 x y 补 10111若 x 补 00101 y 补 11100 则 x y 补 01001 上溢 下溢 上溢 2020年3月26日星期四 92 2020年3月26日星期四 92 溢出判别方法 进位判别法 0101 0100 1001 1 0 0001 0100 0101 0 0 V 0 1 1 V 0 0 0 判别方法 最高数值位的进位与符号位的进位是否相同 判别公式溢出标志V Cf Cn 1其中Cf为符号位产生的进位 Cn 1为最高数值位产生的进位 举例 2020年3月26日星期四 93 回顾逻辑门图形符号 2020年3月26日星期四 94 2 2 4基本的二进制加法 减法器 一位二进制数据的半加器 加数 Ai Bi结果 Si 和 Ci 1 本位向高位的进位 一位半加器示意图 一位二进制数据的全加器 加数 Ai BiCi 低位向本位的进位 结果 Si 和 Ci 1 本位向高位的进位 一位全加器示意图 2020年3月26日星期四 95 一位二进制数据的全加器的逻辑结构 全加运算的真值表如右所示 两个输出端的逻辑表达式Si Ai Bi CiCi 1 AiBi BiCi CiAi全加器逻辑结构 3T 1T 1T 3T 3T 2020年3月26日星期四 96 多位二进制数据加法器 两个n位的数据A An 1An 2 A1A0 B Bn 1Bn 2 B1B0和S Sn 1Sn 2 S1S0采用进位判别法判断运算的溢出 V Cn Cn 1 2020年3月26日星期四 97 多位二进制数据加法 减法器 将减法转换成加法 A 补 B 补 A 补 B 补由 B 补求 B 补 B 补求各位取反 末位加1 将加减法电路合二为一使用异或运算 当M 0时 Bi Bi当M 1时 Bi Bi 2020年3月26日星期四 98 多位二进制数据加法 减法器 3T 5T 1 2T 6T 1 2T 6T 2T 2 2T 6T n 1 2T 6T n 2T 6T 3T 2nT 9T 动画演示 2 1 swf n 2T 6T 2020年3月26日星期四 99 多位二进制加法 减法器的输出延迟 假如每位均采用一位全加器并考虑溢出检测 n位行波进位加法器的延迟时间ta为 ta n 2T 9T 2n 9 T如果不考虑溢出 则延迟时间ta由Sn 1的输出延迟决定 ta n 1 2T 6T 3T 2 n 1 9 T延迟时间ta输入稳定后 在最坏情况下加法器得到稳定的输出所需的最长时间 显然这个时间越小越好 2020年3月26日星期四 100 2 3定点乘法运算 2 3 0串行乘法2 3 1原码并行乘法2 3 2直接补码并行乘法 2020年3月26日星期四 101 2 3 0串行乘法 1 分析笔算乘法 A 0 1101B 0 1011 A B 0 10001111 0 1101 0 1011 1101 1101 0000 1101 0 10001111 符号位单独处理 乘数的某一位决定是否加被乘数 4个位积一起相加 乘积的位数扩大一倍 乘积的符号心算求得 2020年3月26日星期四 102 A B A 0 1011 0 1A 0 00A 0 001A 0 0001A 0 1A 0 00A 0 001 A 0 1A 0 1A 0 01 0 A 0 1 A 0 1A 0 1 A 0 1 0 A 0 1 A 0 1A 2 1 A 2 1 0 A 2 1 A 2 1 A 0 第一步被乘数A 0 第二步部分积右移1位 得新的部分积 第八步部分积右移1位 得结果 第三步部分积 被乘数 2 笔算乘法改进 2020年3月26日星期四 103 0 0000 0 1101 0 1101 0 1101 0 0000 0 1101 初态 部分积 0 乘数为1 加被乘数 乘数为1 加被乘数 乘数为0 加0 乘数为1 加被乘数 3 改进后的笔算乘法过程 竖式 2020年3月26日星期四 104 小结 乘法运算 加法 移位 若乘数数值位n 4 则累加4次 移位4次 乘法过程由乘数的末位决定被乘数是否与原部分积相加 被乘数只与部分积的高位相加部分积右移一位形成新的部分积 同时乘数右移一位 末位移丢 空出高位存放部分积的低位 硬件构成3个具有移位功能的寄存器 一个全加器 2020年3月26日星期四 105 A X Q均n 1位 移位和加受末位乘数控制 串行乘法的硬件配置 运算前为 n 1位部分积初值为0运算后为 乘积高n 1位 被乘数乘运算时用到的加数 运算前为 n 1位乘数运算后为 乘积低n 1位 2020年3月26日星期四 106 常用的串行乘法运算 原码乘法 符号位和数值位必须分开计算 原码一位乘一次判断1位 需判断n次 乘数位数为n 原码两位乘一次判断2位 可提高乘法的运算速度 补码乘法 符号位和数值位可以等同处理 补码一位乘结果修正法 需区分乘数正负号 复杂Booth算法 比较法 符号位直接参与运算补码两位乘 2020年3月26日星期四 107 原码一位乘法 设X Xf X1X2 Xn Y Yf Y1Y2 Yn 乘积的符号位为Pf 则Pf Xf Yf P X Y 求 P 的运算规则如下被乘数和乘数均取绝对值参加运算 符号位单独考虑 被乘数取双符号位 部分积的长度同被乘