计算机组成与体系结构第3章数据表示与运算算法和逻辑电路实现.ppt

第3章 数据表示 数据运算算法和逻辑电路实现 2 本章主要内容 信息编码 码制转换与检错纠错码数据表示 常用的信息编码二进制数值数据的编码与运算算法 3 数字化编码二要素 数值文字符号语音图形图像等统称数据 在计算机内部 都必须用数字化编码的形式被存储加工和传送数字化编码二要素 少量简单的基本符号一定的组合规则用以表示大量复杂多样的信息 4 基二码 二进制码 只使用两个基本点符号 符号个数最少 物理上容易实现与二值逻辑的真假两个值对应简单用二进制码表示数值数据运算规则简单 5 进位记数法与进制转换 进位记数法 N i m 1 D i i r k N代表一个数值 r是这个数制的基 Radix i表示这些符号排列的位号 D i 是位号为i的位上的一个符号 r i 是位号为i的位上的一个1代表的值 i r D i 是第i位的所代表的实际值 表示m k位的值求累加和 6 十进制转二进制 整数部分除2取余小数部分乘2取整 2 11 2 2 2 5 2 1 0 1 1 0 1 0 625 2 1 0 25 2 0 0 5 2 1 0 0 除尽为止求得位数满足要求为止 低 高 高 低 从二进制数求其十进制的值 逐位码权累加求和 7 二到八或十六进制转换 二到八从小数点向左右三位一分组 10011100 01 2 234 2 8010二到十六从小数点向左右四位一分组 10011100 01 2 9C 4 160100说明 整数部分不足位数对转换无影响 小数部分不足位数要补零凑足 否则出错 8 二进制数据算术运算规则 1 加法运算规则0 0 0例如 01010 1 1 00011 0 101101 1 0并产生进位 2 减法运算规则0 0 0例如 10110 1 1并产生借位 01011 0 101101 1 0 9 二进制数据算术运算规则 乘法运算规则例如 11010X0 0X 01010X1 011011X0 011011X1 11000001除法运算规则1101例如 1110101 1001100111101011001101110010100110010 0000 10 检错纠错码 为了提高计算机的可靠性 除了采取选用更高可靠性的器件 更好的生产工艺等措施之外 还可以从数据编码上想一些办法 即采用一点冗余的线路 在原有数据位之外再增加一到几位校验位 使新得到的码字带上某种特性 之后则通过检查该码字是否仍保持有这一特性 来发现是否出现了错误 甚至于定位错误后 自动改正这一错误 这就是我们这里说的检错纠错编码技术 11 非线性码 线性码 卷积码 分组码 非循环码 循环码 随机错误 突发错误 纠错码 校验位与信息位的形成关系 信息位与校验位的约束条件 码字本身的结构特点 信息位与校验位排列位置关系 系统码 非系统码 纠错码分类 12 几种常用的检错纠错码 我们只介绍三种常用的检错纠错码 奇偶检错码 用于并行数据传送中海明检错与纠错码 用于并行数据传送中循环冗余码 用于串行数据传送中 编码过程 译码过程 传送 原始数据 码字 结果数据 形成校验位的值 加进特征 检查接送的码字 发现 改正错误 13 奇偶校验码 用于并行码检错原理 在k位数据码之外增加1位校验位 使K 1位码字中取值为1的位数总保持为偶数 偶校验 或奇数 奇校验 例如 0001100010000101010010110101原有数字位两个新的码字 偶校验 奇校验 校验位 14 奇偶校验码的实现电路 奇较验偶校验出错指示 15 海明校验码 用于多位并行数据检错纠错处理实现 为k个数据位设立r个校验位 使k r位的码字同时具有这样两个特性 能发现并改正k r位中任何一位出错 能发现k r位中任何二位同时出错 但已无法改正 16 海明码的编码方法 合理地用k位数据位形成r个校验位的值 即保证用k个数据位中不同的数据位组合来形成每个校验位的值 使任何一个数据位出错时 将影响r个校验位中不同的校验位组合起变化 换言之 通过检查是哪种校验位组合起了变化 就能确定是哪个数据位错 对该位求反则实现纠错 有时两位错与某种情况的一位错对校验位组合的影响相同 必须加以区分与解决 17 P1 D2 D1P2 D3 D1P3 D3 D2 海明码的实现方案例如 k 3 r 4 D3D2D1P4P3P2P11111111110010010100100110001 P4 P3 P2 P1 D3 D2 D1 编码方案 译码方案 18 P1 D2 D1P2 D3 D1P3 D3 D2 海明码的实现原理例如 k 3 r 4 D3D2D1P4P3P2P11111111110010010100100110001 P4 P3 P2 P1 D3 D2 D1 S1 P1 D2 D1S2 P2 D3 D1S3 P3 D3 D2S4 P4 P3 P2 P1 D3 D2 D1 6530421 19 检错纠错码小结 1 K位码有2K个编码状态 全用于表示合法码 则任何一位出错 均会变成另一个合法码 不具有检错能力 2 从一个合法码变成另一个合法码 只少要改变几位码的值 称为最小码距 码距 3 K 1位码 只用其2K个状态 可使码距为2 如果一个合法码中的一位错了 就成为非法码 通过检查码字的合法性 就得到检错能力 这就是奇偶校验码 20 检错纠错能力 4 对k位数据位 当给出r位校验位时 要发现并改正一位错 须满足如下关系 2r k r 1 要发现并改正一位错 也能发现两位错 则应 2r 1 k r 此时码距为4 5 若最小码距为d d 2 能发现d 1位错 或改正 d 2 2 取整 位错 要发现l位错 并改正t位错 应满足如下条件 d l t 1 l t 21 本章主要内容 信息编码 码制转换与检错纠错码数据表示 常用的信息编码二进制数值数据的编码与运算算法 22 基二码应用实例 数据表示 逻辑型数据字符型数据ASCII码EBCDIC码字符串汉字检错纠错码奇偶校验海明校验循环冗余校验数值型数据定点小数整数浮点数二 十进制数 BCD码 23 逻辑型数据 逻辑型数据只有两个值 真和假 正好可以用二进制码的两个符号分别表示 例如1表示真则0表示假不必使用另外的编码规则 对逻辑型数据可以执行逻辑的与或非等基本逻辑运算 其规则如下 24 逻辑型数据基本运算规则 XYX与YX或YX的非00001010111001011110 25 字符型数据的表示 字符作为人 机联系的媒介 是最重要的数据类型之一 当前的西文字符集由128个符号组成 通常用8位二进制编码 即用一个字节来表示每一个符号 当前通用的两个标准字符集是 ASCII码 即AmericanStandardCodeforInformationInterchangeEBCDIC码 即ExtendedBinaryCodedDecimalInterchageCodeASCII码字符集具体编码如下表所示 26 ASCII字符编码集 b6b5b4000001010011100101110111b3b2b1b00000NULDLESP0 P p0001SOHDC1 1AQaq0010STXDC2 2BRbr0011ETXDC3 3CScs0100EOTDC4 4DTdt0101ENQNAK 5EUeu0110ACKSYNK k 1100FFFS N n 1111SIUS O o 27 字符串的表示与存储 字符串是指连续的一串字符 它们占据主存中连续的多个字节 每个字节存放一个字符 对一个主存字的多个字节 有按从低位到高位字节次序存放的 也有按从高位到低位字节次序存放的 表示字符串数据要给出串存放的主存起始地址和串的长度 例如 IFA BTHENREAD C 就可以有如下不同的存放方式 IFAAFI BTTB 假定每个字HENNEH由4个字节READDAER组成 C C 28 汉字的表示 通常用两个字节表示一个汉字为了与西文字符编码相区别 西文的ASCII码的最高一位编码值为0 表示一个汉字时 把两个字节的最高一位的编码值设定为1 则该编码集的最多编码数量为128X128 这种编码方案与西文传送中的把ASCII码的最高一位用作奇偶校验位有矛盾 29 数值数据在计算机内的格式 定点小数 N NNN N s 1 n 2 整数 N NNN NN 0 1 s n n 1 浮点数 N MEE EEMM M s s m 1 1 0 1 2 n 符号位阶码位尾数数码位总位数 短浮点数 182332 长浮点数 1115264 临时浮点数 1156480 IEEE标准 阶码用移码 尾数用原码 基为2 30 二十进制编码 BCD编码 用四位二进制表示一位十进制 16个编码状态选用其中的10个编码有多种方案 例如 8421码 余3码 循环码又可区分为 有权码 每位上的1代表确定的值无权码 无法确定每位上的1代表的值 31 00000001100000000100010100000101112001001010011011030011011000100101401000111011001005010110001110101160110100110101010701111010100010018100010111100100091001110001001111 有权码无权码 8421 余3码 循环码 84 2 1 32 如何判定码权 00000101114 2 1 201104 2 验证每个码的值301014 1 401004从一编码求码权510118 2 1 61010 2结论71001 1证明此编码系统为有权码810008911118 4 2 1 33 如何判定码权 000112 1 0验证各码的值101001从一编码求码权201011301102401115100061001结论71010证明此编码系统为无权码8101191100 34 本章主要内容 信息编码 码制转换与检错纠错码数据表示 常用的信息编码二进制数值数据的编码与运算算法 35 定点小数表示 NsN1N2 Nn X X X 原 X 1 X 1 X 0 反 X 2 2 X n 0 X 1 1 X 0 补 X 2 X Mod 2 2 0 X 1 1 X 0 Mod2 0 X 1 n 纯小数 原码 反码 补码的定义 36 定点小数表示 NsN1N2 Nn 原码定义 X 原 实例 X1 0 10110 0 101100 0000 X 原 0101101101100000010000结论 原码为符号位加数的绝对值 0正1负原码零有两个编码 0和 0编码不同原码难以用于加减运算 但乘除方便 X 1 X 1 X 0 0 X 1 37 定点小数表示 NsN1N2 Nn 反码定义 X 反 实例 X1 0 10110 0 101100 0000 X 反 0101101010010000011111结论 反码负数为符号位跟每位的反 0正1负反码零有二个编码 分 0和 0反码难以用于加减运算 有循环进位问题 X 2 2 n X 1 X 0MOD 2 2 n 0 X 1 38 定点小数表示 NsN1N2 Nn 模2补码定义 X 补 实例 X1 0 10110 0 101100 0000 X 补 01011010101000000结论 补码最高一位是符号位 0正1负补码表示为 2 符号位 数的真值补码零只有一个编码 故能表示 1补码能很好地用于加减 乘除 运算 X 2 X 1 X 0MOD2 0 X 1 39 整数的编码表示 整数的原码反码补码表示与小数的三种表示基本相同 差别仅表现在小数点的位置 可以认为整数的小数点在最低数值位的右侧因此整数的模与整数位数有关 讲课中不大用整数讲原反补码定义例如 整数六位编码 X 01110 X 原 001110 X 补 001110X 01110 X 原 101110 X 补 110010 40 原反补码表示小结 正数的原码 反码 补码表示均相同 符号位为0 数值位同数的真值 零的原码和反码均有2个编码 补码只1个码负数的原码 反码 补码表示均不同 符号位为1 数值位 原码为数的绝对值反码为每一位均取反码补码为反码再在最低位 1由 X 补求 X 补 每一位取反后 再在最低位 1n由 X 补求X的真值 X 1 Xi 2 i i 1 41 数据的算术运算 补码加减法运算原码一位乘法运算原码一位除法运算补码一位乘法运算补码一位乘法运算原码二位乘法运算补码二位乘法运算其它快速乘除法运算方法简介 42 补码加减法的实现 X Y X Y X Y X Y Y 对 Y 逐位取反 再在最低位加1溢出判断 正 正得负或负 负得正数字位有向符号位的进位 但符号位不产生向更高位的进位双符号位的值为01或10 补 补 补 补 补 补 补 补 43 FX 实现补码加减运算的逻辑电路 FsFALU 目的寄存器 源寄存器 选通门 二选通门 选通门 F1 X Y FY XF 0 1 01 F Y FsOVRZC 累加器 XX YXX Y 加 减 44 补码加减法运算实例 X 0 1011y 0 0101模4补码 X 001011 Y 111011 Y 000101001011001011 111011 0001011000110010000X YX Y 溢出 补 补 补 45 补码表示中的符号位扩展 由 X 补求 X 2 补的方法原符号位不变 且符号位与数值位均右移一位 例如 X 补 10010则 X 2 补 110010不同位数的整数补码相加减时 位数少的补码数的符号位向左扩展 一直扩展到与另一数的符号位对齐 01010101110000110101010111000011 1111111110011100 000000000001110001010101010111110101010111011111 46 原码一位乘运算 X Y 原 X Y X Y 例如 X 0 1101Y 0 10110 11010000001011 0 10110001101101110100100111101101000100111100000010001111 1101X和Y符号异或为负0 10001111最终乘积原码表示为 110001111手工运算过程计算机内运算的实现方法 部分积乘数 47 原码一位乘运算 例如 X 0 1101Y 0 10110 1101问题 0 10111 加法器只有两个数据输入端11012 加法器与乘运算数据位数相同1101解决方案 0000每次求出部分积 而不是一次总累加 1101变每次左移被乘数为右移部分积0 10001111判乘数每一位的值用固定的一位线路手工运算过程 48 实现原码一位乘法的逻辑线路图 第i位 第i位 第i 1位 第i 1位 F 2 XF XF 2 X 移位电路 49 原码一位乘法 000000 1011 000000 001101 1011 001101 001101 000110 1011 010011 010011 1101 001000 001001 000110 001001 001001 001001 000100 000100 010001 010001 001000 低位积 50 原码一位乘运算 例如 X 0 1101Y 0 10110 1101 累加器初值取零值 0 1011 1101 初值 加被乘数1101 部分积右移0000将移出的一位保存起来 1101求第一次部分积0 10001111手工运算过程 51 原码一位乘运算 例如 X 0 1101Y 0 10110 1101 0 1011 1101 前次部分积加被乘数1101 部分积右移0000将移出的一位保存起来 1101求第二次部分积0 10001111手工运算过程 52 原码一位乘运算 例如 X 0 1101Y 0 10110 1101 0 1011 1101 前次部分积加 1101 部分积右移0000将移出的一位保存起来 1101求第三次部分积0 10001111手工运算过程 53 原码一位乘运算 例如 X 0 1101Y 0 10110 1101 0 1011 1101 前次部分积加被乘数1101 部分积右移0000将移出的一位保存起来 1101求第四次部分积0 10001111手工运算过程 最后一步 数符号异或求积的符号 54 原码一位乘运算 例如 X 0 1101Y 0 10110 1101 0 1011 1101 1101 0000 1101求第四次部分积0 10001111手工运算过程 若把乘数放在一个移位寄存器中 该寄存起又用来接受加法器的移位输出 则判乘数的某一位也更方便 55 原码一位乘运算 X Y 原 X Y X Y 例如 X 0 1101Y 0 10110 11010000001011 0 10110001101101110100100111101101000100111100000010001111 1101X和Y符号异或为负0 10001111最终乘积原码表示为 110001111手工运算过程计算机内运算的实现方法 56 除法运算 在计算机内实现除运算时 存在与乘法运算类似的几个问题 加法器与寄存器的配合 被除数位数更长 商要一位一位地计算出来等 这可以用左移余数得到解决 且被除数的低位部分可以与最终的商合用同一个寄存器 余数与上商同时左移 57 原码一位除运算 Y X 原 X Y YX 原码一位除是指用原码表示的数相除 求出原码表示的商 除操作的过程中 每次求出一位商 从理解原理考虑 用恢复余数除法讲解计算机内的实现方法更直观方便 即确定上商