第2章-数码系统 1

,BeyondTechnology,计算机组成原理,大连东软信息学院精品课程,内容回顾,1、冯诺依曼体系结构中，计算机的设计思想是什么？2、计算机有哪五大部分组成？3、CPU中包括哪两大部件？4、计算机经历了哪四代？,第2章数码系统,本章线索,2.1数制及其转换重要概念,2.1数制及其转换常见进制,2.1数制及其转换数制的相互转换,2.1数制及其转换二进制常用表达,（1）（1000）2=2N：表示1后面有N个0的二进制整数。（2）（1111）2=2N-1：表示共有N个1的二进制整数。（3）（0.001）2=2-N：表示小数点后共有N-1个0的二进制纯小数。（4）（0.111）2=1-2-N：表示小数点后共有N个1的二进制纯小数。（5）（1111）2-（X1X2XN）2=（X1X2XN）2：表示共有N个1的二进制整数减去一个N位的二进制整数，结果是将减数按位取反。（6）（0.1111）2-（0.X1X2XN）2=（0.X1X2XN）2：表示共有N个1的二进制纯小数减去一个小数部分有N位的二进制纯小数，结果是将减数的小数部分按位取反。（7）二进制数左移K位，相当于这个数乘以2K。（8）二进制数右移K位，相当于这个数除以2K。,2.2数值数据描述,2.2数值数据描述无符号数和有符号数,无符号数（unsigned）数据与数值相等，数据本身的N+1个二进制比特位全部用来表示其数值，没有符号位。表示范围：0，2N+1-1通常用于表示地址，作为计数器等用途,2.2数值数据描述无符号数和有符号数,有符号数（signed）有符号数的数据分为符号和数值两个部分，N+1位有符号数的二进制比特位最左一位用于表示符号，其余N位用于表示数值。真值和机器数：真值是带符号的数，即平时生活中数的表达方式。机器数是有符号数的符号数值化后在计算机存储中的数，是一个0、1序列。三个问题符号的数值化：“+”用“0”表示，“-”用“1”表示。数值的编码：多种方案，如原码，反码，补码，移码等。小数点的表示：隐藏，不表示出来，只要事先约定好即可。,2.2数值数据描述定点数和浮点数,定点数小数点固定在某一位置的数为定点数。定点整数与定点小数,定点小数格式定点整数格式,2.2数值数据描述定点数和浮点数,浮点数小数点的位置可以浮动的数。将尾数最高位为1的浮点数称作规格化数。左规与右规,浮点数的表示形式,2.2数值数据描述定点数的编码方案,原码求法：把数值的绝对值转换成二进制以后在最高位加上其符号的数值表示，原数值的符号位“+”和“-”分别用“0”和“1”表示。定义定点整数时：定点小数时：X原=X（X0）X原=X（X0）=2N-X（X0）=1-X（X0）0的编码+0原=00000000-0原=100000000的原码不唯一！表示范围定点整数：-（2N-1），+（2N-1）定点小数：-（1-2-N），+（1-2-N）,2.2数值数据描述定点数的编码方案,反码求法：如果为正数则其编码与原码相同，如果为负数则除符号位外按位取反。定义定点整数时：定点小数时：X原=X（X0）X原=X（X0）=2N+1-1+X（X0）=2-2-N+X（X0）0的编码+0反=00000000-0反=111111110的反码不唯一！表示范围定点整数：-（2N-1），+（2N-1）定点小数：-（1-2-N），+（1-2-N）,2.2数值数据描述定点数的编码方案,补码求法：如果为正数则其编码与原码相同；如果为负数则在反码的基础上+1。定义定点整数时：定点小数时：X原=X（X0）X原=X（X0）=2N+1+X（X0）=2+X（X0）0的编码+0补=00000000，-0补=000000000的补码唯一！表示范围定点整数：-2N，+（2N-1）定点小数：-1，+（1-2-N）,2.2数值数据描述定点数的编码方案,补码的性质已知X补，求X原、-X补、2X补、X/2补的方法。X原=X补（正数），X原=X补补（负数）-X补=X补连同符号位一起按位取反，末尾加12X补=X补连同符号位一起左移一位，右边补0（符号位不能变）X/2补=X补连同符号位一起右移一位，左边补符号位（舍去）练习：已知X补=0.01001001，求X原、-X补、2X补、X/2补。X原=0.01001001-X补=1.101101112X补=0.10010010X/2补=0.00100100,2.2数值数据描述定点数的编码方案,变形补码求法：双符号位补码用法：方便判断运算是否溢出！移码求法：将一个数的补码的符号位取反定义：X移=2N+X表示范围：0，+（2N+1-1）用法：表示浮点数的阶码,2.2数值数据描述定点数的编码方案,练习：4位二进制数表示的有符号的定点整数和小数的原、反、补码的表示范围分别是多少？4位二进制数表示的有符号整数原码：1111B0111B（-7+7）反码：1000B0111B（-7+7）补码：1000B0111B（-8+7）4位二进制数表示的有符号小数原码：1.111B0.111B（-（1-2-3）1-2-3）反码：1.000B0.111B（-（1-2-3）1-2-3）补码：1.000B0.111B（-11-2-3）总结定点数表示范围中包括0所有编码表示的最大数一致原码和反码的表示范围一致，且相对于0点中心对称,内容回顾,数制及其转换数值数据描述（分类）定点数的编码方案原码、反码、补码,二进制数的位数为N+1=8位时，求+5和-5的原码。当N+1=8时，N=7，即数值用7位表示。所以：(5)D=(101)B=(0000101)B前面的4个0是为了保证数据位为7位加上去的，再把“+”号变成“0”放在首位。+5原=00000101同理可得：-5原=10000101。,二进制数的位数为N+1=8位时，求+0.625和-0.625的原码。,当N+1=8时，N=7，即数值用7位表示。所以：(0.625)D=(0.101)B=(0.1010000)B,二进制数的位数为N+1=8位时，求+5和-5的补码。,+5原=00000101，-5原=10000101因为+5是一个正数，其补码与原码相同，有+5补=00000101。负数的补码是在反码的最末位加上1，由例2.7可知-5反=11111010，而11111010+1=11111011，可以得到-5补=11111011。,二进制数的位数为N+1=8位时，求+0.625和-0.625的补码。,+0.625原=0.1010000，-0.625原=1.1010000因为+0.625是一个正数，其补码与原码相同，有+0.625补=0.1010000。负数的补码是在反码的最末位加上1，由例2.8可知-0.625反=1.0101111，而1.0101111+0.0000001=1.0110000，可以得到-0.625补=1.0110000。,二进制数的位数为N+1=8位时，求+5和-5的变形补码,+5原=00000101+5反=00000101+5补=00000101+5变补=000000101同理可得：-5原=10000101-5反=11111010-5补=11111011-5变补=111111011另外：+0.101变补=00.1010000，-0.101变补=11.0110000。,二进制数的位数为N+1=8位时，求+5和-5的移码。,+5补=00000101+5移=10000101同理可得：-5原=10000101-5反=11111010-5补=11111011，-5移=01111011。,2.2数值数据描述浮点数的编码方案,浮点数的表示：X=MxREx，其中Mx称为尾数，通常为带符号的小数，Ex称为阶码，通常为带符号的整数。几个重要概念浮点数上溢：阶码比所能表示的最大正数还要大。浮点数下溢：阶码比所能表示的最小负数还要小。浮点数溢出处理：上溢产生中断，停止处理；下溢强行置机器0，继续运算。机器0：尾数为0，阶码不管为任何值，或者阶码小于它所能表示的最小数，无论尾数为任何值。规格化数：在R进制中，要求尾数Mx满足1/R|Mx|1，即R进制中尾数的第一位为有效位（非零）。IEEE754标准,浮点数IEEE754标准,已知一单精度浮点数的机器码为：42C88000H，求其真值,解：42C88000H=（0100,0010,1100,1000,1000,0000,0000,0000）2=（0,10000101,10010001000000000000000）2尾符为0，尾数为0.10010001000000000000000，阶码为10000101真值=（-1）0（1+0.10010001000000000000000）2（100001011111111）=1.1001000126=（100.25）10。,2.2数值数据描述十进制数的编码,BCD码：十进制数的二进制编码。BCD码的编码方案有权码：8421码、5421码、2421码等无权码：余三码、格雷码等8421码,8421码的编码方式,BCD码实质都是利用四位二进制来表示一位十进制数码，方案有多种，按其编码是否根据特定的权值构成，分为有权码和无权码。有权码有8421码、2421码和5421码等编码方式，通常用得最多的是8421码，所以一般BCD码如不特殊说明就指8421码。如十进制的128，用8421码的1表示为0001，2表示为0010，8表示为1000，得(128)D=(000100101000)BCD。,其他有权码,2421码和5421码等编码方式自己设计一种有权码如：84-2-1？用84-2-1码表示1，如何表示？,练习,一种BCD码，其中09的编码为0000，0001，0010，0011，0100，0101，0110，0111，1110，1111，则各位的权值为_。A.8421B.5421C.4421D.2421,无权码,余3码的编码方式就是在8421码的编码上加上3，做数值计算得到的编码。格雷码的主要特点为任何两组相邻码字中只有一位二进制不同，它有多种编码方案。一种方案为8421码加一个前导0，然后相邻两位异或得到。求：数字9的格雷码,2.3文本数据描述ACSII码,键盘有多少个按键？101个AscII码用几位可以表示这些按键？,2.3文本数据描述ACSII码,基本的ASCII字符集：使用7位二进制数对字符进行编码，包括128个字符，其中有96个可打印字符，包括常用的字母、数字、标点符号等，另外还有32个控制字符。常用几个编码0：30H（48）A：41H（65）a：61H（97）一个字节的最高位为0，可用于奇偶校验。,练习,已知0和9的ASCII码分别为0110000和0111001，请分别写出3、5、7的ASCII码、8421码及余三码。,内容回顾,1、浮点数的编码方案2、浮点数真值计算公式浮点数真值=（-1）尾符（1+尾数）2（阶码偏移量）3、十进制数的编码4、ASCII码,本次课内容要点,1、汉字的编码2、数据校验,2.3文本数据描述汉字的编码,输入码：用来将汉字输入到计算机中的一组键盘符号。交换码：计算机内部处理的信息，都是用二进制代码表示的。国标码：GB2312-80区位码：94（区）94（位）机内码：每一个汉字确定的二进制代码，既把国标码的每一个字节的首位置1（为了解决和ASCII码的冲突）。字形码：汉字的输出码，输出汉字时都采用图形方式，无论汉字的笔画多少，每个汉字都可以写在同样大小的方块中。,2.3文本数据描述汉字的编码,区位码、国标码和汉字的内码的关系（国标码）H=（区位码）H+（2020）H（内码）H=（国标码）H+（8080）H（内码）H=（区位码）H+（A0A0）H例：“啊”字的国标码为3021H区位码=3021H2020H=1001H，即它在第16区，第01位。内码=3021H+8080H=B0A1H。,十进制,区位码-94个区可分为5组,01-15区：是各种图形符号、制表符和一些主要国家的语言字母，其中01-09区为标准符号区，共有682个常用符号。10-15区：为自定义符号区，可留作用户自己定义。16-55区：是一级汉字区，共有3755个常用汉字，以拼音为序排列。56-87区：是二级汉字区，共有3008个次常用汉字，以部首为序排列。88-94区：自定义汉字区，可留作用户自己定义。,2.4其他信息形式的表示图像的格式简介,BMP：位图格式GIF：图形交换格式JPEG：有损压缩格式,2.4其他信息形式的表示有关音频编码,采样率和采样大小采样的过程就是抽取某点的频率值。采样率：采样的频率采样大小：采样频率的能量值并量化有损与无损相对自然界的信号，任何数字音频编码方案都是有损的PCM约定俗成了无损编码PCM编码：音质好，体积大,2.4其他信息形式的表示视频格式,FLC：无声时代AVI：载歌载舞MPEG编码流媒体：MPEG-4，边下载边播放,2.5数据校验,2.5数据校验校验码的工作原理,码距：任意两个合法编码之间不相同的位数的最小值。,合法的数据,非法的编码,数据传输,合法的编码,非法的编码,传输数据正确,传输数据错误,校验码,差错编码,附加监督位：在数据块中加入一些冗余信息，使数据块中的各个比特建立起某种形式的关联，接收端通过验证这种关联关系是否存在，来判断数据在传输过程中有没有出错。差错编码：在数据块中加入冗余信息的过程。,术语,检错码码字只有检错的功能，接收方只能判断数据块有错，但不能确切知道错误的位置，从而也不能纠正错误。纠错码码字具有一定的纠错功能，接收方不仅能检出错，还知道错在什么地方，这时只需将数据位取反即能获得正确的数据。,2.5数据校验奇偶校验码,由n-1位信息元和1位校验元组成奇校验码：在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数个偶校验码：附加上一个校验元以后，码长为n的码字中“1”的个数为偶数个例：被校验的代码为1000001，则奇偶校验码分别为奇校验码：11000001（最左位为校验位）偶校验码：01000001（最左位为校验位）是一种检错码,2.奇偶校验的校验方程,设7位信息码组为C7C6C5C4C3C2C1,校验码为C0,则对偶校验,当满足C7C6C5C4C3C2C1C00（1）时,为合法码;对奇校验,当满足C7C6C5C4C3C2C1C01（2）时,为合法码。对于偶校验,合法码字应满足nCiC00（3）i-1对于奇校验,合法码字应满足nCiC01（4）i-1,注意:公式(1)(2)为奇偶校验位的生成方程;公式(3)(4)为校验方程。,发明纠错码的大数学家里查德.海明,RichardHamming于1915年生于美国芝加哥。1937年在芝加哥大学获得数学硕士学位,1939年在内布拉斯加大学获得硕士学位,又于1942年在伊利诺大学获得博士学位。他长期在贝尔实验室工作，担任计算机科学部的主任。他成功地解决了通信时发送方发出的信息在传输过程中的误码问题，并于1947年发明了一种能纠错的编码，称为纠错码或海明码。这种方法在计算机各部件间进行信息传输时以及在计算机网络的信息传输中同样有用。为此，他于1968年荣获图灵奖。Hamming作为数学家在数值方法、编码与信息论、统计学和数字滤波器等领域也有重大的贡献。Hamming是美国工程院院士，曾任ACM第七届主席，还获得了除图灵奖之外的多个重大奖项。,2.5数据校验海明码,设信息位为k位，增加r位冗余位，构成一个n=k+r位的码字。可以用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。满足关系式2r=n+1或2r=k+r+1。在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若它们全为“0”，则认为无错；若不全为“0”，在一位错的情况下，可查表判定是哪一位错，从而纠正之。是一种纠错码，但只能纠一位错。,海明码,设信息位为k位，增加r位冗余位，构成一个n=k+r位的码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错，则要求满足关系式2r=n+1或2r=k+r+1以k=4为例来说明，要满足上述不等式，必须r=3。假设取r=3，则n=k+r=7，即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，构成7位码字a6a5a4a3a2a1a0,信息位,冗余位,在校验时，a2、a1和a0就分别和这些位半加构成三个不同的监督关系式。在无错时，这三个关系式的值S2、S1和S0全为“0”。若a2错，则S2=1，而S1=S0=0；若a1错，则S1=1，而S2=S0=0；若a0错，则S0=1,S2、S1和S0这三个校正因子的其它4种编码值可用来区分a3、a4、a5、a6中的一位错,监督关系式,a2、a4、a5或a6的一位错都应使S2=1，由此可以得到监督关系式S2=a2a4a5a6，同理可得S1=a1a3a5a6，S0=a0a3a4a6。S2、S1和S0是偶校验码的校验元,监督关系式,冗余码的确定,在发送端编码时，信息位a6、a5、a4和a3的值取决于输入信号，它们在具体的应用中有确定的值。冗余位a2、a1和a0的值应根据信息位的取值按监督关系式来确定使监督关系式中的S2、S1和S0取值为零，即a2a4a5a6=0a1a3a5a6=0a0a3a4a6=0由此可求得：a2=a4a5a6a1=a3a5a6a0=a3a4a6,a2,a1,a0即为冗余码,已知信息位，即可确定冗余位,接收端纠错,在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若它们全为“0”，则认为无错；若不全为“0”，在一位错的情况下，可查表2.6来判定是哪一位错，从而纠正之。,海明码例发送,发送端想发送一个数字9，直接发送没法校验和纠错，怎么办？,给它加上校验码，数字9的BCD码是1001，加几位校验码合适？,根据海明码的构造方法，加3位冗余位，可校验一位错,查P45页表2.7，1001加冗余位100,把加了冗余位的码字一起发送过去,海明码例发送,组合成的码字按照a6,a5,a4,a3,a2,a1,a0的顺序排列，即为：1001100最后，把这串码字发送出去,海明码例接收,刚才我们发送了码字1001100，如果在通讯过程中收到干扰，到接收端变成了：1101100接收端则通过监督关系式判断是否有错，如何纠正根据监督关系式，S2=a2a4a5a6，则S2=1S1=a1a3a5a6，则S1=1S0=a0a3a4a6。则S0=0,S2,S1,S0的取值为110,A5位错了！,修正，把收到的码字1101100的a5位取反,正确的码字是：1001100，再去掉冗余位，则发送的正确信息是1001，即数字9,校验码工作过程总结差错编码,附加监督位：在数据块中加入一些冗余信息，使数据块中的各个比特建立起某种形式的关联，接收端通过验证这种关联关系是否存在，来判断数据在传输过程中有没有出错。差错编码：在数据块中加入冗余信息的过程。,练习1,发送数字5，要求接收端可以校验1位错。设计海明码校验码字发送。接收端接收正确的情形如何判断？如果接收端的信息错了1位，如何判断哪位错并纠正？,练习2,接收方接收到了一串用海明码进行校验的编码：0101110判断：接收到的编码是否有错？如果有错，错在哪一位？纠正该编码？,2.5数据校验循环冗余码,在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共（k+r）位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。是一种常用的纠错码。,计算机网络第4章数据链路层,68,循环冗余检验的原理,码字多项式：让数据码字的每一位对应于多项式中每一位的系数。,如：数据码字：1010101则：码字多项式：x6+x4+x2+1,（n+k,k）码：即：数据码为：n位，冗余码为k位，则：其合法编码有2k个。,例如：(7,3)码的合法编码有八个：00000001001110001110101110101110100110100110100110100111,计算机网络第4章数据链路层,69,循环冗余检验的原理,CRC编码方法,设：要发送的信息码字多项式为：F(x)双方协议规定的生成多项式为：G(x),编码步骤：(1)用生成多项式的最高位乘以M(x)：xkF(x)(2)用(1)的结果除以G(x)(3)所得余数R(x)即为CRC的冗余码。,计算机网络第4章数据链路层,70,xkF(x)=Q(x)G(x)+R(x),有：xkF(x)+R(x)=Q(x)G(x),CRC校验码：编码后的数据流,计算机网络第4章数据链路层,71,CRC译码方法,设：收到的信息码字多项式为：F(x)双方协议规定的生成多项式为：G(x)则：,F(x)G(x),能除尽，传输正确否则，传输错误,若传输正确，则F(x)=Q(x)G(x)Q(x)G(x)G(x),显然是可以除尽的，反之，除不尽,计算机网络第4章数据链路层,72,校验位的生成用一个例子来说明校验位的生成过程。假设要传送的数据信息为：