计算原理及系统结构ppt课件

1、计算机原理及系统结构 第六讲主讲教师：赵主讲教师：赵宏伟宏伟 学时：学时：64第第3 3章章数据表示、数据运算算法数据表示、数据运算算法和逻辑电路实现和逻辑电路实现本章主要内容本章主要内容w信息编码、码制转换与检错纠错码信息编码、码制转换与检错纠错码w数据表示数据表示常用的信息编码常用的信息编码w二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法数字化编码二要素数字化编码二要素数值数值 文字文字 符号符号 语音语音 图形图形 图像图像 等统称数据，等统称数据，在计算机内部，都必须用在计算机内部，都必须用数字化编码数字化编码的形式的形式被被 存储存储 加工加工 和和 传送传送 数字化编

2、码数字化编码二要素二要素: 少量简单的基本符号少量简单的基本符号 一定的组合规则一定的组合规则用以表示用以表示大量复杂多样大量复杂多样的信息的信息p62p62 基二码（二进制码）基二码（二进制码）只使用只使用两个两个基本点符号：基本点符号： 符号个数符号个数最少最少，物理上容易实现，物理上容易实现与与二值逻辑二值逻辑的的 真真 假假 两个值对应简单两个值对应简单用二进制码用二进制码表示表示数值数据数值数据运算规则简单运算规则简单p63p63进位记数法与进制转换进位记数法与进制转换进位记数法进位记数法n n=i=m-1d di* *ir-kn 代表一个数值代表一个数值r 是这个数制的基是这个数制

3、的基(radix)i表示这些符号排列的位号表示这些符号排列的位号di是位号为是位号为i i的位上的一个符号的位上的一个符号ri是位号为是位号为i i的位上的一个的位上的一个 1 1 代表的值代表的值irdi*是第是第i i位的所代表的实际值位的所代表的实际值表示表示m+km+k位的值求累加和位的值求累加和p64p64十进制转二进制十进制转二进制整数部分除整数部分除2 2取余取余 小数部分乘小数部分乘2 2取整取整2 1 1222521011010.625 * 210.25 * 200.5 * 21 0.0 除尽为止除尽为止 求得位数满足要求为止求得位数满足要求为止低低高高高高低低从二进制数求其

4、十进制的值，逐位码权累加求和从二进制数求其十进制的值，逐位码权累加求和p65p65二到八或十六进制转换二到八或十六进制转换二到八二到八 从小数点向左右从小数点向左右三位一分组三位一分组（10 011 100 . 01)10 011 100 . 01)2 2 = ( 234 . 2 ) = ( 234 . 2 )8 8 010 010 二到十六二到十六 从小数点向左右从小数点向左右四位一分组四位一分组（1001 1100 . 01)1001 1100 . 01)2 2 = ( 9c . 4 ) = ( 9c . 4 )1616 01000100 说明：说明：整数部分不足位数对转换无影响，整数部分

5、不足位数对转换无影响， 小数部分不足位数要补零凑足小数部分不足位数要补零凑足, ,否则出错。否则出错。p67p67计算机原理及系统结构 第七讲主讲教师：赵主讲教师：赵宏伟宏伟 学时：学时：64二进制数据算术运算规则二进制数据算术运算规则(1) 加法运算规则加法运算规则 0+0=0 例如：例如： 0101 0+1=1 +) 0001 1+0=1 0110 1+1=0 并产生进位并产生进位(2) 减法运算规则减法运算规则 0-0=0 例如：例如： 1011 0-1=1 并产生借位并产生借位 -) 0101 1-0=1 0110 1-1=0二进制数据算术运算规则二进制数据算术运算规则(3)乘法运算规

6、则乘法运算规则 例如：例如： 1101 0x x0=0 x x) 0101 0x x1=0 1101 1x x0=0 1101 1x x1=1 1000001(4)除法运算规则除法运算规则 1101 例如：例如： 1110101/1001 1001 1110101 1001 1011 1001 01001 1001 0 0000p68p68二进制数据逻辑运算规则二进制数据逻辑运算规则（5）逻辑或运算规则）逻辑或运算规则 （7）逻辑非运算规则）逻辑非运算规则 00=0 /0=1 01=1 /1=0 10=1 11=1（6）逻辑与运算规则）逻辑与运算规则 （8）逻辑异或运算规则）逻辑异或运算规则

7、00=0 0 0=0 01=0 0 1=1 10=0 1 0=1 11=1 1 1=0 0000计算机原理及系统结构 第八讲主讲教师：赵主讲教师：赵宏伟宏伟 学时：学时：64检错纠错码检错纠错码 为了提高计算机的为了提高计算机的可靠性可靠性，除了采，除了采取选用更高可靠性的器件，更好的生产取选用更高可靠性的器件，更好的生产工艺等措施之外，还可以从数据编码上工艺等措施之外，还可以从数据编码上想一些办法，即采用一点冗余的线路，想一些办法，即采用一点冗余的线路，在原有数据位之外再在原有数据位之外再增加一到几位校验增加一到几位校验位位，使新得到的码字带上某种特性使新得到的码字带上某种特性，之，之后则通

8、过后则通过检查该码字是否仍保持有这一检查该码字是否仍保持有这一特性特性，来，来发现发现是否出现了错误，甚至于是否出现了错误，甚至于定位错误后，定位错误后，自动改正自动改正这一错误，这就这一错误，这就是我们这里说的是我们这里说的检错纠错编码技术检错纠错编码技术。p70p70非线性码非线性码线性码线性码卷积码卷积码分组码分组码非循环码非循环码循环码循环码随机随机 错误错误 突发突发 错误错误纠错码纠错码校验位与信息位校验位与信息位 的形成关系的形成关系信息位与校验位信息位与校验位 的约束条件的约束条件码字本身的码字本身的 结构特点结构特点信息位与校验位排列位置关系信息位与校验位排列位置关系系统码系

9、统码非系统码非系统码纠错码分类纠错码分类p70p70几种常用的检错纠错码几种常用的检错纠错码我们只介绍三种常用的检错纠错码：我们只介绍三种常用的检错纠错码：奇偶检错码奇偶检错码， 用于用于并行并行数据传送中数据传送中海明检错与纠错码海明检错与纠错码，用于，用于并行并行数据传送中数据传送中循环冗余码循环冗余码， 用于用于串行串行数据传送中数据传送中编码过程编码过程译码过程译码过程传送传送原始数据原始数据码码 字字结果数据结果数据形成校验位的值，形成校验位的值，加进特征加进特征检查接送的码字，检查接送的码字，发现发现 / 改正错误改正错误奇偶校验码奇偶校验码用于并行码用于并行码检错检错原理：在原理

10、：在 k 位数据码之外增加位数据码之外增加 1 位校验位，位校验位，使使 k+1 位码字中取值为位码字中取值为 1 的位数的位数总保持总保持为为 偶数偶数（偶校验偶校验）或）或 奇数奇数（奇校验奇校验）。）。例如：例如：0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 原有数字位原有数字位 两个新的码字两个新的码字 偶校验偶校验奇校验奇校验校验位校验位p71p71奇偶校验码的实现电路+ 奇较验奇较验 偶校验偶校验 出错指示出错指示+同左侧电同左侧电路路编码电路编码电路译码电路译码电路p (校验位校验位)八位数据八位数据位位d7 d6

11、 d5 d4 d3 d2 d1 d0p海明校验码海明校验码用于多位并行数据用于多位并行数据检错纠错检错纠错处理处理实现：为实现：为 k 个数据位设立个数据位设立 r 个校验位，个校验位，使使 k+r 位的码字同时具有这样两个特性：位的码字同时具有这样两个特性： 能发现并改正能发现并改正 k+r 位中任何一位出错，位中任何一位出错， 能能 发发 现现 k+r 位中任何二位同时出错，但已位中任何二位同时出错，但已无法改正。无法改正。海明码的编码方法海明码的编码方法合理地用合理地用 k 位数据位形成位数据位形成 r 个校验位的值，个校验位的值，即保证用即保证用 k 个数据位中不同的数据位组合个数据位

12、中不同的数据位组合来形成每个校验位的值，使任何一个数据来形成每个校验位的值，使任何一个数据位出错时，将影响位出错时，将影响 r 个校验位中不同的校个校验位中不同的校验位组合起变化。换言之，通过检查是哪验位组合起变化。换言之，通过检查是哪种校验位组合起了变化，就能确定是哪个种校验位组合起了变化，就能确定是哪个数据位错，对该位求反则实现纠错。数据位错，对该位求反则实现纠错。有时两位错与某种情况的一位错对校验位组有时两位错与某种情况的一位错对校验位组合的影响相同，必须加以区分与解决。合的影响相同，必须加以区分与解决。p1 = d2 + d1p2 = d3 + d1p3 = d3 + d2海明码的实现

13、方案海明码的实现方案 例如：例如： k =3, r =4d3 d2 d1 p4 p3 p2 p1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 p4 = p3 + p2 + p1 + d3 + d2 + d1s1 = p1 + d2 + d1s2 = p2 + d3 + d1s3 = p3 + d3 + d2s4 = p4 + p3 + p2 + p1 + d3 + d2 + d1+ ：异或：异或编码方案编码方案译码方案译码方案p72p72检错纠错码小结检错纠错码小结(1) k位码有位码有2k 个编码状态，全用于表示合法个编码状

14、态，全用于表示合法码，则任何一位出错码，则任何一位出错, 均会变成另一个合法均会变成另一个合法码，不具有检错能力。码，不具有检错能力。(2) 从一个合法码变成另一个合法码，只少要从一个合法码变成另一个合法码，只少要改变几位码的值，称为改变几位码的值，称为最小码距最小码距(码距码距)。(3) k+1 位码，只用其位码，只用其 2k 个状态，可使码距个状态，可使码距 为为 2 , 如果一个合法码中的一位错了，就成如果一个合法码中的一位错了，就成为为非法码非法码，通过检查，通过检查码字的合法性码字的合法性，就，就得到得到检错能力检错能力，这就是奇偶校验码。，这就是奇偶校验码。检错纠错能力检错纠错能力

15、(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

16、 )计算机原理及系统结构 第九讲主讲教师：赵主讲教师：赵宏伟宏伟 学时：学时：64本章主要内容本章主要内容w信息编码、码制转换与检错纠错码信息编码、码制转换与检错纠错码w数据表示数据表示常用的信息编码常用的信息编码w二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法基二码应用实例：数据表示基二码应用实例：数据表示逻辑型数据逻辑型数据字符型数据字符型数据ascii 码码 ebcdic 码码字符串字符串 汉字汉字检错纠错码检错纠错码奇偶校验奇偶校验海明校验海明校验 循环冗余校验循环冗余校验数值型数据数值型数据定点小数定点小数 整数整数 浮点数浮点数 二二十进制数（十进制数（bcd码）码）

17、 逻辑型逻辑型数据数据逻辑型数据只有两个值：逻辑型数据只有两个值：真真 和和 假假，正好可以用二进制码的两个符号分别表示，正好可以用二进制码的两个符号分别表示，例如例如 1 表示表示 真真 则则 0 表示表示 假假不必使用另外的编码规则。不必使用另外的编码规则。对逻辑型数据可以执行逻辑的对逻辑型数据可以执行逻辑的 与与 或或 非非等基等基本逻辑运算。其规则如下：本逻辑运算。其规则如下：逻辑型数据逻辑型数据基本运算规则基本运算规则 x y x与y x或y x的非 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 字符型字符型数据的表示数据的表示 字符作为人字符作为人

18、机联系的媒介，是最重机联系的媒介，是最重要的数据类型之一，当前的西文字符集由要的数据类型之一，当前的西文字符集由 128 个符号组成，通常用个符号组成，通常用 8 位二进制编码位二进制编码,即即用一个字节来表示每一个符号用一个字节来表示每一个符号，当前通用，当前通用的两个标准字符集是：的两个标准字符集是：ascii 码码： 即即 american standard code for information interchangeebcdic码码：即：即 extended binary coded decimal interchage code ascii码字符集具体编码如下表所示：码字符集具体

19、编码如下表所示： ascii字符编码集字符编码集 b6 b5 b4 000 001 010 011 100 101 110 111 b3 b2 b1 b0 0000 nul dle sp 0 p , p 0001 soh dc1 ! 1 a q a q 0010 stx dc2 “ 2 b r b r 0011 etx dc3 # 3 c s c s 0100 eot dc4 $ 4 d t d t 0101 enq nak % 5 e u e u 0110 ack syn & 6 f v f v 0111 bel etb 7 g w g w 1000 bs can ( 8 h x h

20、 x 1001 ht em ) 9 i y i y 1010 lf sub * : j z j z 1011 vt esc + ; k k 1100 ff fs , n n 1111 si us / ? o _ o p75p75字符串的表示与存储字符串的表示与存储 字符串是指连续的一串字符，它们占据主存中连续的字符串是指连续的一串字符，它们占据主存中连续的多个字节，每个字节存放一个字符，对一个主存字的多个字节，每个字节存放一个字符，对一个主存字的多个字节，有按从低位到高位字节次序存放的，也有多个字节，有按从低位到高位字节次序存放的，也有按从高位到低位字节次序存放的。表示字符串数据要按从高位到低

21、位字节次序存放的。表示字符串数据要给出串存放的主存起始地址和串的长度。例如：给出串存放的主存起始地址和串的长度。例如：if ab then read(c)就可以有如下不同的存放方式：就可以有如下不同的存放方式： i f a a f i b t t b 假定每个字假定每个字 h e n n e h 由由 4 个字节个字节 r e a d d a e r 组成组成 ( c ) ) c (汉字的表示汉字的表示 通常用两个字节表示一个汉字通常用两个字节表示一个汉字 为了与西文字符编码相区别（西文的为了与西文字符编码相区别（西文的ascii码的最高一位编码值为码的最高一位编码值为0），表示一），表示一个

22、汉字时，把两个字节的最高一位的编码个汉字时，把两个字节的最高一位的编码值设定为值设定为 1，则该编码集的最多编码数量，则该编码集的最多编码数量为为 128 x x 128。 这种编码方案与西文传送中的把这种编码方案与西文传送中的把ascii码的最高一位用作奇偶校验位有矛码的最高一位用作奇偶校验位有矛盾。盾。数值数据在计算机内的格式数值数据在计算机内的格式定点小数定点小数: n = n n n .ns-1-n-2整整 数数 : n = n n n . n n01snn-1浮点数浮点数: n = m e e .e e m m .m ssm-110-1-2-n符号位符号位 阶码位阶码位 尾数数码位尾

23、数数码位 总位数总位数 短浮点数短浮点数: 1 8 23 32长浮点数长浮点数: 1 11 52 64 临时浮点数临时浮点数: 1 15 64 80ieee 标准：标准： 阶码用移码，阶码用移码，尾数用原码尾数用原码 基为基为 2p76p76二二 十进制编码（十进制编码（bcd编码）编码）用四位二进制表示一位十进制，用四位二进制表示一位十进制， 16个编码状态选用其中的个编码状态选用其中的10个编码个编码有多种方案，例如：有多种方案，例如：8421码，余码，余 3 码，循环码码，循环码又可区分为：又可区分为：有权码：每位上的有权码：每位上的 1 代表确定的值代表确定的值无权码：无法确定每位上的

24、无权码：无法确定每位上的 1 代表的值代表的值0 0000 0011 0000 00001 0001 0100 0001 01112 0010 0101 0011 01103 0011 0110 0010 01014 0100 0111 0110 01005 0101 1000 1110 10116 0110 1001 1010 10107 0111 1010 1000 10018 1000 1011 1100 10009 1001 1100 0100 1111有权码有权码 无权码无权码8421余余3码码 循环码循环码 84-2-1p79p79计算机原理及系统结构 第十讲主讲教师：赵主讲教师：

25、赵宏伟宏伟 学时：学时：64本章主要内容本章主要内容w信息编码、码制转换与检错纠错码信息编码、码制转换与检错纠错码w数据表示数据表示常用的信息编码常用的信息编码w二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法定点小数表示定点小数表示: ns n1 n2 nn x = x = x =原原 x 1 - x -1 x 0反反 x(2 - 2 )+ x-n0 x 1-1 x 0补补 x 2 + xmod ( 2 - 2 )0 x 1-1 x 0mod 20 x 1-n（纯小数）原码，反码，补码的定义（纯小数）原码，反码，补码的定义p82p82定点小数表示定点小数表示: ns n1 n2

26、nn 原原 码码定义：定义： x 原原 =实例：实例： x1 = 0.10110 -0.10110 0.0000 x 原原 = 010110 110110 00000 10000 结论：结论：原码原码为符号位加数的绝对值，为符号位加数的绝对值，0正正 1负负 原码原码零有两个编码，零有两个编码，+0 和和 -0编码不同编码不同 原码原码难以用于加减运算，但乘除方便难以用于加减运算，但乘除方便 x 1 - x -1 x 0 0 x 1p83p83定点小数表示定点小数表示: ns n1 n2 nn模模 2 补码补码 定义：定义： x 补补 =实例：实例： x1 = 0.10110 -0.10110

27、 0.0000 x 补补 = 010110 101010 00000结论：结论：补码补码最高一位是符号位，最高一位是符号位，0 正正 1 负负 补码补码表示为：表示为：2*符号位符号位 + 数的真值数的真值 补码补码零只有一个编码，故能表示零只有一个编码，故能表示 -1 补码补码能很好地用于加减（乘除）运算能很好地用于加减（乘除）运算 x 2 + x -1 x 0 mod 2 0 x 1p83p83定点小数表示定点小数表示: ns n1 n2 nn 反反 码码定义：定义： x 反反 =实例：实例： x1 = 0.10110 -0.10110 0.0000 x 反反 = 010110 101001 00000 11111 结论：结论：反码反码负数为符号位跟每位的反负数为符号位跟每位的反, 0 正正 1 负负 反码反码零有二个编码，分零有二个编码，分+0 和和 -0 反码反码难以用于加