第2章 数码系统

1、CS&T Information CourseBeyond Technology计算机组成原理计算机组成原理大连东软信息学院精品课程大连东软信息学院精品课程CS&T Information Course内容回顾内容回顾 1、冯诺依曼体系结构中，计算机的设计思想是什么？ 2、计算机有哪五大部分组成？ 3、CPU中包括哪两大部件？ 4、计算机经历了哪四代？CS&T Information Course第第2章章 数码系统数码系统教学内容教学内容 2.1数制及其转换数制及其转换 2.2数值数据描述数值数据描述 2.3文本数据描述文本数据描述 2.4其他信息形式其他信息形式的表

2、示的表示 2.5数据校验数据校验教学重点教学重点 进位计数制及其进位计数制及其转换转换 真值和机器数真值和机器数 有符号数的表示有符号数的表示 浮点数的表示浮点数的表示 BCD码码 文本数据的描述文本数据的描述 校验码校验码教学难点教学难点 有符号数的表示有符号数的表示（原、反、补码）（原、反、补码）CS&T Information Course本章线索本章线索数制及其转换数制及其转换数值数据描述数值数据描述文本数据描述文本数据描述其他信息形式的其他信息形式的表示表示数据校验数据校验CS&T Information Course2.1数制及其转换数制及其转换重要概念重要概念 R

3、进制中只允许出现0、1、2、R-1共R个数码，数码即可以是数也可以是码（如字母），则R就称为R进制的基数。基数基数 R进制中，不同位置的1所表示的值不同，位号为i的1表示Ri，Ri称为位权。位权位权 进位规则是指何种情况下向高位进位。R进制中，对位加法满R就应向高位进位，即逢R进一。进位规则进位规则CS&T Information Course2.1数制及其转换数制及其转换常见进制常见进制十进制（十进制（D）二进制（二进制（B）八进制（八进制（O）十六进制（十六进制（H）0123456789101112131415000000010010001101000101011001111000

4、10011010101111001101111011110123456710111213141516170123456789ABCDEFCS&T Information Course2.1数制及其转换数制及其转换数制的相互转换数制的相互转换十进制十进制二进制二进制八进制八进制十六十六进制进制CS&T Information Course2.1数制及其转换数制及其转换二进制常用表达二进制常用表达（1）（1000）2 = 2N：表示1后面有N个0的二进制整数。（2）（1111）2 = 2N-1：表示共有N个1的二进制整数。（3）（0.001）2 = 2-N：表示小数点后共有N-1个

5、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。CS&T Information Course2.2数值数据描述数值数据描述机器数

6、机器数无符号数无符号数有符号数有符号数定点数定点数定点整数定点整数定点小数定点小数浮点数浮点数CS&T Information Course2.2数值数据描述数值数据描述无符号数和有符号数无符号数和有符号数 无符号数（unsigned） 数据与数值相等，数据本身的N+1个二进制比特位全部用来表示其数值，没有符号位。 表示范围： 0，2N+1-1 通常用于表示地址，作为计数器等用途CS&T Information Course2.2数值数据描述数值数据描述无符号数和有符号数无符号数和有符号数 有符号数（signed） 有符号数的数据分为符号和数值两个部分，N+1位有符号数的二进制

7、比特位最左一位用于表示符号，其余N位用于表示数值。 真值和机器数：真值是带符号的数，即平时生活中数的表达方式。机器数是有符号数的符号数值化后在计算机存储中的数，是一个0、1序列。 三个问题 符号的数值化：“+”用“0”表示，“-”用“1”表示。 数值的编码：多种方案，如原码，反码，补码，移码等。 小数点的表示：隐藏，不表示出来，只要事先约定好即可。CS&T Information Course2.2数值数据描述数值数据描述定点数和浮点数定点数和浮点数 定点数 小数点固定在某一位置的数为定点数。 定点整数与定点小数定点小数格式 定点整数格式CS&T Information Cou

8、rse2.2数值数据描述数值数据描述定点数和浮点数定点数和浮点数 浮点数 小数点的位置可以浮动的数。 将尾数最高位为1的浮点数称作规格化数。 左规与右规浮点数的表示形式CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方案定点数的编码方案 原码 求法：把数值的绝对值转换成二进制以后在最高位加上其符号的数值表示，原数值的符号位“+”和“-”分别用“0”和“1”表示。 定义定点整数时：定点小数时：X原 = X （X0） X原 = X （X0） = 2N-X （X0） = 1-X （X0） 0的编码 +0原=00000000 -0原=10000000 0

9、的原码不唯一！ 表示范围 定点整数：-（2N-1）， +（2N-1） 定点小数：-（1-2-N），+（1-2-N）CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方案定点数的编码方案 反码 求法：如果为正数则其编码与原码相同，如果为负数则除符号位外按位取反。 定义定点整数时：定点小数时：X原 = X （X0） X原 = X （X0） = 2N+1-1+X （X0） = 2-2-N+X （X0） 0的编码+0反=00000000 -0反=11111111 0的反码不唯一！ 表示范围 定点整数：-（2N-1）， +（2N-1） 定点小数：-（1-2-

10、N），+（1-2-N）CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方案定点数的编码方案 补码 求法：如果为正数则其编码与原码相同；如果为负数则在反码的基础上+1。 定义定点整数时：定点小数时：X原 = X （X0） X原 = X （X0） = 2N+1+X （X0） = 2+X （X0） 0的编码 +0补=00000000，-0补=00000000 0的补码唯一！ 表示范围 定点整数： -2N，+（2N-1） 定点小数： -1，+（1-2-N）CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方案

11、定点数的编码方案 补码的性质 已知X补，求X原、-X补、2X补、X/2补的方法。 X原= X补（正数），X原= X补补（负数） -X补= X补连同符号位一起按位取反，末尾加1 2X补= X补连同符号位一起左移一位，右边补0（符号位不能变） X/2补= X补连同符号位一起右移一位，左边补符号位（舍去） 练习：已知X补= 0.01001001，求X原、-X补、2X补、X/2补。 X原= 0.01001001 -X补= 1.10110111 2X补=0.10010010 X/2补= 0.00100100CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方

12、案定点数的编码方案 变形补码 求法：双符号位补码 用法：方便判断运算是否溢出！ 移码 求法：将一个数的补码的符号位取反 定义：X移 = 2N+X 表示范围：0，+（2N+1-1） 用法：表示浮点数的阶码CS&T Information Course2.2数值数据描述数值数据描述定点数的编码方案定点数的编码方案练习：4位二进制数表示的有符号的定点整数和小数的原、反、补码的表示范围分别是多少？4位二进制数表示的有符号整数 原码：1111B0111B（-7+7） 反码：1000B0111B（-7+7） 补码：1000B0111B（-8+7）4位二进制数表示的有符号小数 原码：1.111B0.

13、111B（-（1-2-3） 1-2-3 ） 反码：1.000B0.111B（ -（1-2-3） 1-2-3 ） 补码：1.000B0.111B（-1 1-2-3 ）总结 定点数表示范围中包括0 所有编码表示的最大数一致 原码和反码的表示范围一致，且相对于0点中心对称CS&T Information Course内容回顾内容回顾 数制及其转换 数值数据描述（分类） 定点数的编码方案 原码、反码、补码CS&T Information Course 二进制数的位数为N+1=8位时，求+5和-5的原码。 当N+1=8时，N=7，即数值用7位表示。所以： (5)D=(101)B=(000

14、0 101)B 前面的4个0是为了保证数据位为7位加上去的，再把“+”号变成“0”放在首位。 +5原=0 0000101 同理可得：-5原=1 0000101。CS&T Information Course二进制数的位数为二进制数的位数为N+1=8位时，求位时，求+0.625和和-0.625的原码。的原码。 当N+1=8时，N=7，即数值用7位表示。所以： (0.625)D=(0.101)B=(0.101 0000)BCS&T Information Course二进制数的位数为二进制数的位数为N+1=8位时，求位时，求+5和和-5的补码。的补码。 +5原=00000101，-

15、5原=10000101 因为+5是一个正数，其补码与原码相同，有+5补=00000101。 负数的补码是在反码的最末位加上1，由例2.7可知-5反=11111010，而11111010+1=11111011，可以得到-5补=11111011。CS&T Information Course二进制数的位数为二进制数的位数为N+1=8位时，求位时，求+0.625和和-0.625的补码。的补码。 +0.625原=0.1010000，-0.625原=1.1010000 因为+0.625是一个正数，其补码与原码相同，有+0.625补=0.1010000。 负数的补码是在反码的最末位加上1，由例2.

16、8可知-0.625反=1.0101111，而1.0101111+0.0000001 = 1.0110000，可以得到-0.625补=1.0110000。CS&T Information Course二进制数的位数为二进制数的位数为N+1=8位时，求位时，求+5和和-5的变形补码的变形补码 +5原= 0 0000101 +5反= 0 0000101 +5补= 0 0000101 +5变补=00 0000101 同理可得： -5原= 1 0000101 -5反= 1 1111010 -5补= 1 1111011 -5变补=11 1111011 另外：+0.101变补=00 .1010000

17、，-0.101变补=11 .0110000。CS&T Information Course二进制数的位数为二进制数的位数为N+1=8位时，求位时，求+5和和-5的移码。的移码。 +5补=0 0000101 +5移=1 0000101 同理可得： -5原=1 0000101 -5反=1 1111010 -5补=1 1111011， -5移=0 1111011。CS&T Information Course2.2数值数据描述数值数据描述浮点数的编码方案浮点数的编码方案 浮点数的表示： X=Mx REx，其中Mx称为尾数，通常为带符号的小数，Ex称为阶码，通常为带符号的整数。 几个重

18、要概念 浮点数上溢：阶码比所能表示的最大正数还要大。 浮点数下溢：阶码比所能表示的最小负数还要小。 浮点数溢出处理：上溢产生中断，停止处理；下溢强行置机器0，继续运算。 机器0：尾数为0，阶码不管为任何值，或者阶码小于它所能表示的最小数，无论尾数为任何值。 规格化数：在R进制中，要求尾数Mx满足1/R |Mx| 1，即R进制中尾数的第一位为有效位（非零）。 IEEE754标准CS&T Information Course浮点数浮点数IEEE754标准标准IEEE754标准标准符号位符号位阶码阶码尾数尾数偏移量偏移量是否采用隐藏位技术是否采用隐藏位技术单精度单精度32位（短实数）位（短实

19、数）1823127采用双精度双精度64位（长实数）位（长实数）111521023采用临时实数临时实数80位位1156416383不采用CS&T Information Course已知一单精度浮点数的机器码为：已知一单精度浮点数的机器码为：42C88000H，求其真值，求其真值 解：解：42C88000H = （0100,0010,1100,1000,1000,0000,0000,0000）2 = （0,10000101,10010001000000000000000）2 尾符为0，尾数为0.10010001000000000000000，阶码为10000101 真值=（-1）0（1+

20、0.10010001000000000000000）2（100001011111111）=1.1001000126=（100.25）10。CS&T Information Course2.2数值数据描述数值数据描述十进制数的编码十进制数的编码 BCD码：十进制数的二进制编码。 BCD码的编码方案 有权码：8421码、5421码、2421码等 无权码：余三码、格雷码等 8421码CS&T Information Course8421码的编码方式码的编码方式 BCD码实质都是利用四位二进制来表示一位十进制数码，方案有多种，按其编码是否根据特定的权值构成，分为有权码和无权码。有权码有

21、8421码、2421码和5421码等编码方式，通常用得最多的是8421码，所以一般BCD码如不特殊说明就指8421码。 如十进制的128，用8421码的1表示为0001，2表示为0010，8表示为1000，得(128)D=(0001 0010 1000)BCD。CS&T Information Course其他有权码其他有权码 2421码和5421码等编码方式 自己设计一种有权码 如：84-2-1？ 用84-2-1码表示1，如何表示？CS&T Information Course练习练习 一种BCD码，其中09的编码为0000，0001，0010，0011，0100，0101，

22、0110，0111，1110，1111，则各位的权值为_。 A. 8421 B. 5421 C. 4421 D. 2421CS&T Information Course无权码无权码 余3码的编码方式就是在8421码的编码上加上3，做数值计算得到的编码。 格雷码的主要特点为任何两组相邻码字中只有一位二进制不同，它有多种编码方案。一种方案为8421码加一个前导0，然后相邻两位异或得到。 求：数字9的格雷码CS&T Information Course2.3文本数据描述文本数据描述ACSII码码 键盘有多少个按键？ 101个 AscII码用几位可以表示这些按键？CS&T In

23、formation Course2.3文本数据描述文本数据描述ACSII码码 基本的ASCII字符集：使用7位二进制数对字符进行编码，包括128个字符，其中有96个可打印字符，包括常用的字母、数字、标点符号等，另外还有32个控制字符。 常用几个编码 0：30H（48） A：41H（65） a：61H（97） 一个字节的最高位为0，可用于奇偶校验。CS&T Information Course练习练习 已知0和9的ASCII码分别为0110000和0111001，请分别写出3、5、7的ASCII码、8421码及余三码。CS&T Information Course内容回顾内容回顾

24、 1、浮点数的编码方案 2、浮点数真值计算公式 浮点数真值 =（-1）尾符（1+尾数）2（阶码偏移量） 3、十进制数的编码 4、ASCII码CS&T Information Course本次课内容要点本次课内容要点 1、汉字的编码 2、数据校验CS&T Information Course2.3文本数据描述文本数据描述汉字的编码汉字的编码 输入码：用来将汉字输入到计算机中的一组键盘符号。 交换码：计算机内部处理的信息，都是用二进制代码表示的。 国标码：GB2312-80 区位码： 94（区）94（位） 机内码：每一个汉字确定的二进制代码，既把国标码的每一个字节的首位置1（为了解

25、决和ASCII码的冲突）。 字形码：汉字的输出码，输出汉字时都采用图形方式，无论汉字的笔画多少，每个汉字都可以写在同样大小的方块中。CS&T Information Course2.3文本数据描述文本数据描述汉字的编码汉字的编码 区位码、国标码和汉字的内码的关系 （国标码） H =（区位码）H +（2020）H （内码）H = （国标码）H+ （8080）H （内码）H = （区位码）H+ （A0A0）H 例：“啊”字的国标码为3021H 区位码=3021H 2020H = 1001H，即它在第16区，第01位。 内码=3021H + 8080H = B0A1H。十进制十进制CS&am

26、p;T Information Course区位码区位码-94个区可分为个区可分为5组组 01-15区：是各种图形符号、制表符和一些主要国家的语言字母，其中01-09区为标准符号区，共有682个常用符号。 10-15区：为自定义符号区，可留作用户自己定义。 16-55区：是一级汉字区，共有3755个常用汉字，以拼音为序排列。 56-87区：是二级汉字区，共有3008个次常用汉字，以部首为序排列。 88-94区：自定义汉字区，可留作用户自己定义。CS&T Information Course2.4其他信息形式的表示其他信息形式的表示图像的格式简介图像的格式简介 BMP：位图格式 GIF：

27、图形交换格式 JPEG：有损压缩格式CS&T Information Course2.4其他信息形式的表示其他信息形式的表示有关音频编码有关音频编码 采样率和采样大小 采样的过程就是抽取某点的频率值。 采样率：采样的频率 采样大小：采样频率的能量值并量化 有损与无损 相对自然界的信号，任何数字音频编码方案都是有损的 PCM约定俗成了无损编码 PCM编码：音质好，体积大CS&T Information Course2.4其他信息形式的表示其他信息形式的表示视频格式视频格式 FLC：无声时代 AVI：载歌载舞 MPEG编码 流媒体：MPEG-4，边下载边播放CS&T Inf

28、ormation Course2.5数据校验数据校验 即检查代码是否出错，但不能确定何处出错，不能修改。检错码 即不仅能检查出错误，还能定位错误并纠正。纠错码CS&T Information Course2.5数据校验数据校验校验码的工作原理校验码的工作原理码距：任意两个合法编码之间不相同的位数的最小值。合法的数据非法的编码数据传输合法的编码非法的编码传输数据正确传输数据错误校验码CS&T Information Course差错编码差错编码q 附加监督位：在数据块中加入一些冗余信息，使数据块中的各个比特建立起某种形式的关联，接收端通过验证这种关联关系是否存在，来判断数据在传输

29、过程中有没有出错。q 差错编码：在数据块中加入冗余信息的过程。CS&T Information Course 术术 语语 码字只有检错的功能，接收方只能判断数据块有错，但不能确切知道错误的位置，从而也不能纠正错误。 码字具有一定的纠错功能，接收方不仅能检出错，还知道错在什么地方，这时只需将数据位取反即能获得正确的数据。CS&T Information Course2.5数据校验数据校验奇偶校验码奇偶校验码 由n-1位信息元和1位校验元组成 奇校验码：在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数个 偶校验码：附加上一个校验元以后，码长为n的码字中“1”的个数为偶数个

30、 例：被校验的代码为1000001，则奇偶校验码分别为 奇校验码：11000001 （最左位为校验位） 偶校验码：01000001 （最左位为校验位） 是一种检错码CS&T Information Course2. 2.奇偶校验的校验方程奇偶校验的校验方程 设设7 7位信息码组为位信息码组为C C7 7C C6 6C C5 5C C4 4C C3 3C C2 2C C1 1, , 校验码为校验码为C C0 0 , ,则对偶则对偶校验校验, , 当满足当满足 C C7 7CC6 6CC5 5CC4 4CC3 3CC2 2CC1 1CC0 00 0 （1 1） 时时, , 为合法码为合法码

31、; ; 对奇校验对奇校验, , 当满足当满足 C C7 7CC6 6CC5 5CC4 4CC3 3CC2 2CC1 1CC0 0 1 1 （2 2） 时时, , 为合法码。为合法码。 对于偶校验对于偶校验, , 合法码字应满足合法码字应满足n n C Ci iCC0 00 0 （3 3）i-1i-1 对于奇校验对于奇校验, , 合法码字应满足合法码字应满足n n C Ci iCC0 01 1 （4 4）i-1i-1注意注意: :公式公式(1)(2)(1)(2)为奇偶校验位为奇偶校验位的生成方程的生成方程; ;公式公式(3)(4)(3)(4)为校验方程。为校验方程。CS&T Inform

32、ation Course发明纠错码的大数学家发明纠错码的大数学家里查德里查德. .海明海明 Richard HammingRichard Hamming于于19151915年生于美国芝加哥。年生于美国芝加哥。 19371937年在芝加哥大学获得数学硕士学位年在芝加哥大学获得数学硕士学位, 1939, 1939年在年在内布拉斯加大学获得硕士学位内布拉斯加大学获得硕士学位, , 又于又于19421942年在伊利诺大年在伊利诺大学获得博士学位。他长期在贝尔实验室工作，担任计学获得博士学位。他长期在贝尔实验室工作，担任计算机科学部的主任。他成功地解决了通信时发送方发算机科学部的主任。他成功地解决了通信

33、时发送方发出的信息在传输过程中的误码问题，并于出的信息在传输过程中的误码问题，并于19471947年发明年发明了一种能纠错的编码，称为纠错码或海明码。这种方了一种能纠错的编码，称为纠错码或海明码。这种方法在计算机各部件间进行信息传输时以及在计算机网法在计算机各部件间进行信息传输时以及在计算机网络的信息传输中同样有用。为此，他于络的信息传输中同样有用。为此，他于19681968年荣获图年荣获图灵奖。灵奖。HammingHamming作为数学家在数值方法、编码与信息作为数学家在数值方法、编码与信息论、统计学和数字滤波器等领域也有重大的贡献。论、统计学和数字滤波器等领域也有重大的贡献。Hamming

34、Hamming是美国工程院院士，曾任是美国工程院院士，曾任ACMACM第七届主席，第七届主席，还获得了除图灵奖之外的多个重大奖项。还获得了除图灵奖之外的多个重大奖项。CS&T Information Course2.5数据校验数据校验海明码海明码 设信息位为k位，增加r位冗余位，构成一个n=k+r位的码字。可以用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。 满足关系式2r=n+1或2r=k+r+1。 在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若它们全为“0”，则认为无错；若不全为“0”，在一位错的情况下，可查表判定是哪一位错，从而纠正之。

35、 是一种纠错码，但只能纠一位错。CS&T Information Course海明码海明码 设信息位为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信息位冗余位CS&T Information Course 在校验时，a2、a1和a0就分别和这些位半加构成三个不同

36、的监督关系式。在无错时，这三个关系式的值S2、S1和S0全为“0”。若a2错，则S2=1，而S1=S0=0；若a1错，则S1=1，而S2=S0=0；若a0错，则S0=1S2 S1 S0000001010100011101110111错码错码位置位置无错a0a1a2a3a4a5a6S2、S1和S0这三个校正因子的其它4种编码值可用来区分a3、a4、a5、a6中的一位错CS&T Information Course监督关系式监督关系式S2 S1 S0000001010100011101110111错码位置错码位置无错无错a0a1a2a3a4a5a6a2、a4、a5或a6的一位错都应使S2=

37、1，由此可以得到监督关系式S2=a2a4a5a6， 同理可得S1=a1a3a5a6， S0=a0a3a4a6。S2、S1和S0是偶校验码的校验元监督关系式CS&T Information Course冗余码的确定冗余码的确定 在发送端编码时，信息位a6、a5、a4和a3的值取决于输入信号，它们在具体的应用中有确定的值。冗余位a2、a1和a0的值应根据信息位的取值按监督关系式来确定 使监督关系式中的S2、S1和S0取值为零，即 a2 a4 a5 a6=0 a1 a3 a5 a6=0 a0 a3 a4 a6=0 由此可求得：a2=a4 a5 a6 a1=a3 a5 a6 a0=a3 a4

38、a6a2,a1,a0a2,a1,a0即为冗余码即为冗余码CS&T Information Course已知信息位，即可确定冗余位已知信息位，即可确定冗余位信息位信息位a3冗余位冗余位a0信息位信息位a3冗余位冗余位a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111CS&T Information Course接收端纠错接收端纠错 在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若它们全为“0”

39、，则认为无错；若不全为“0”，在一位错的情况下，可查表2.6来判定是哪一位错，从而纠正之。CS&T Information Course海明码海明码例例发送发送发送端想发送一个数字9，直接发送没法校验和纠错，怎么办？给它加上校验码，数字9的BCD码是1001，加几位校验码合适？根据海明码的构造方法，加3位冗余位，可校验一位错查P45页表2.7，1001加冗余位100把加了冗余位的码字一起发送过去CS&T Information Course海明码海明码例例发送发送 组合成的码字按照a6,a5,a4,a3,a2,a1,a0的顺序排列，即为：1001100 最后，把这串码字发送出去

40、CS&T Information Course海明码海明码例例接收接收 刚才我们发送了码字1001100，如果在通讯过程中收到干扰，到接收端变成了：1101100 接收端则通过监督关系式判断是否有错，如何纠正 根据监督关系式， S2=a2 a4 a5 a6，则S2=1 S1=a1 a3 a5 a6，则S1=1 S0=a0 a3 a4 a6。则S0=0CS&T Information CourseS2,S1,S0的取值为的取值为110S2 S1 S0000001010100011101110111错码位置错码位置无无错错a0a1a2a3a4a5a6A5位错了！修正，把收到的码字1

41、101100的a5位取反正确的码字是：1001100，再去掉冗余位，则发送的正确信息是1001，即数字9CS&T Information Course校验码工作过程总结校验码工作过程总结差错编码差错编码q 附加监督位：在数据块中加入一些冗余信息，使数据块中的各个比特建立起某种形式的关联，接收端通过验证这种关联关系是否存在，来判断数据在传输过程中有没有出错。q 差错编码：在数据块中加入冗余信息的过程。CS&T Information Course练习练习1发送数字5，要求接收端可以校验1位错。设计海明码校验码字发送。接收端接收正确的情形如何判断？如果接收端的信息错了1位，如何判断

42、哪位错并纠正？CS&T Information Course练习练习2 接收方接收到了一串用海明码进行校验的编码： 0101110 判断：接收到的编码是否有错？ 如果有错，错在哪一位？ 纠正该编码？CS&T Information Course2.5数据校验数据校验循环冗余码循环冗余码 在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共（k+r）位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 是一种常用的纠错码。CS&T Inform

43、ation Course计算机网络第4章 数据链路层68 循环冗余检验的原理 码字多项式： 让数据码字的每一位对应于多项式中每一位的系数。如：数据码字： 1010101则：码字多项式：x6 + x4 + x2 + 1（n+k,k）码：即：数据码为：n位，冗余码为k位， 则：其合法编码有2k个。 例如：(7,3)码的合法编码有八个： 000 0000 100 1110 001 1101 011 1010 111 0100 110 1001 101 0011 010 0111CS&T Information Course计算机网络第4章 数据链路层69 循环冗余检验的原理 CRC编码方法设

44、：要发送的信息码字多项式为：F(x) 双方协议规定的生成多项式为：G(x)编码步骤： (1)用生成多项式的最高位乘以M(x)：xkF(x) (2)用(1)的结果除以G(x) (3)所得余数R(x)即为CRC的冗余码。CS&T Information Course计算机网络第4章 数据链路层70即有： xkF(x) G(x)xkF(x)= Q(x)G(x)+R(x)有：xkF(x)+R(x) = Q(x)G(x)CS&T Information Course计算机网络第4章 数据链路层71CRC译码方法设：收到的信息码字多项式为：F(x) 双方协议规定的生成多项式为：G(x)则：

45、能除尽，传输正确否 则，传输错误若传输正确，则F(x) = Q(x)G(x)Q(x)G(x) G(x)显然是可以除尽的，反之，除不尽CS&T Information Course计算机网络第4章 数据链路层72校验位的生成 用一个例子来说明校验位的生成过程。 假设要传送的数据信息为：100011，即报文多项式为：F(x)= x5 + x + 1。 若约定的生成多项式为：G(x)= x3+ 1，则数据信息位数n=6，生成多项式位数为4位，所以校验位位数k=3。 生成校验位时，用x3.F(x)去除以G(x)，相除时采用“模运算”的多项式除法。 CS&T Information Course计算机网络第4章 数据链路层7373 100011000100111100100110000011100001110100111101001111010011111001X3.F(x)G(x)(x8+ x4 + x3)(x3 + 1) 校验位为111，CRC码为100011 111。如果要校验CRC码，则可将CRC码用同一个多项式相除，若余数为，则说明无错；否则说明有错。例如，若在接收方的CRC码也为100011 111时，用同一个多项式相