第3章数据表示与运算算法和逻辑电路实现

1、第第3 3章章数据表示、运算算法数据表示、运算算法和线路实现和线路实现本章主要内容本章主要内容 3.1 信息编码概念、码制转换信息编码概念、码制转换 3.2 数据表示数据表示常用的信息编码常用的信息编码 3.3 二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法数字化编码二要素数字化编码二要素数值、文字、符号、语音、图形、图像等统称数值、文字、符号、语音、图形、图像等统称数据数据，在计算机内部，都必须用在计算机内部，都必须用数字化编码数字化编码的形式被的形式被存储、加工存储、加工和和传送传送。数字化编码数字化编码二要素二要素:少量简单的基本符号少量简单的基本符号一定的组合规则一定的组

2、合规则用以表示用以表示大量复杂多样大量复杂多样的信息的信息 基二码（二进制码）基二码（二进制码）只使用只使用两个两个基本点符号：基本点符号：符号个数符号个数最少最少，物理上容易实现，物理上容易实现与与二值逻辑二值逻辑的的 真真假假 两个值对应简单两个值对应简单用二进制码用二进制码表示表示数值数据数值数据运算规则简单运算规则简单进位记数法与进制转换进位记数法与进制转换进位记数法：进位记数法：N =Dm-1Dm-2Dm-3D1D0D-1D-2D-k1mkiirDiN每个每个Di的单位值都赋以固定的权值的单位值都赋以固定的权值ri（r称为称为基），则上式可写成：基），则上式可写成：例如：十进制数例如

3、：十进制数1234，可写成：，可写成：1234=1*103 + 2*102 + 3*101 + 4*100十进制转二进制十进制转二进制整数部分除整数部分除2 2取余取余 小数部分乘小数部分乘2 2取整取整2 1 1222521011010.625 * 210.25 * 200.5 * 21 0.0 除尽为止除尽为止 求得位数满足要求为止求得位数满足要求为止低低高高高高低低从二进制数求其十进制的值，逐位码权累加求和从二进制数求其十进制的值，逐位码权累加求和二到八或十六进制转换二到八或十六进制转换二到八二到八 从小数点向左右从小数点向左右三位一分组三位一分组（10 011 100 . 01)2 =

4、 ( 234 . 2 )8 010 二到十六二到十六 从小数点向左右从小数点向左右四位一分组四位一分组（1001 1100 . 01)2 = ( 9C . 4 )16 0100 说明：说明：整数部分不足位数对转换无影响，整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足，小数部分不足位数要补零凑足，否则出错。否则出错。二进制数据算术运算规则二进制数据算术运算规则(1) 加法运算规则加法运算规则 0+0=0 例如：例如： 0101 0+1=1 +) 0001 1+0=1 0110 1+1=0 并产生进位并产生进位(2) 减法运算规则减法运算规则 0-0=0 例如：例如： 1011 0-1

5、=1 并产生借位并产生借位 -) 0101 1-0=1 0110 1-1=0二进制数据算术运算规则二进制数据算术运算规则乘法运算规则乘法运算规则 例如：例如： 1101 0X0=0 X) 0101 0X1=0 1101 1X0=0 + 110100 1X1=1 1000001除法运算规则除法运算规则 1101 例如：例如：1110101/1001 1001 1110101 1001 1011 1001 001001 1001 0 本章主要内容本章主要内容3.1 信息编码概念、码制转换信息编码概念、码制转换3.2 数据表示数据表示常用的信息编码常用的信息编码3.3 二进制数值数据的编码与运算算法

6、二进制数值数据的编码与运算算法数据表示数据表示逻辑型数据逻辑型数据字符型数据字符型数据 西文字符西文字符 汉字汉字 字符串字符串多媒体信息多媒体信息 图像图像/图形图形 声音声音 视频视频数值型数据数值型数据 定点小数定点小数 整数整数 浮点数浮点数 十进制数（十进制数（BCD码）码）检错纠错码检错纠错码 奇偶校验奇偶校验 海明校验海明校验 循环冗余校验循环冗余校验逻辑型逻辑型数据数据逻辑型数据只有两个值：逻辑型数据只有两个值：真真 和和 假假，正好可以用二进制码的两个符号分别表示。正好可以用二进制码的两个符号分别表示。例如例如 1 表示表示 真真 0 表示表示 假假对逻辑型数据可以执行逻辑的

7、对逻辑型数据可以执行逻辑的 与与 或或 非非等基本逻辑等基本逻辑运算。其规则如下：运算。其规则如下： 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 字符型字符型数据数据字符是最重要的数据类型之一，编码规则很多，字符是最重要的数据类型之一，编码规则很多， 一些常见一些常见编码或术语：编码或术语：ASCII编码编码扩展扩展ASCII码码EBCDIC码码ANSI编码（编码（MBCS 编码）编码）GB2312码、码、GBK码、码、BIG5码码Unicode编码编码UTF-8码码American Standard Code for

8、 Information Interchange，美国信息互换标准代码，主要用，美国信息互换标准代码，主要用于显示现代英语和其他西欧语言，是最通用的于显示现代英语和其他西欧语言，是最通用的单字节编码系统，包含控制字符（如回车键、单字节编码系统，包含控制字符（如回车键、退格、换行键等）和可显示字符（如英文大小退格、换行键等）和可显示字符（如英文大小写字符、阿拉伯数字和西文符号）用写字符、阿拉伯数字和西文符号）用7位表示一位表示一个字符，共个字符，共128字符。见字符。见P49表表3.4。为表示更多的欧洲常用字符，对为表示更多的欧洲常用字符，对ASCII进行了进行了扩展，使用扩展，使用8位表示一个

9、字符，共位表示一个字符，共256字符，扩字符，扩充出来的符号包括表格符号、计算符号、希腊充出来的符号包括表格符号、计算符号、希腊字母和特殊的拉丁符号。字母和特殊的拉丁符号。Extended Binary Coded Decimal Interchage Code，是，是IBM公司为大型操作系统开发的，根据公司为大型操作系统开发的，根据早期打孔机式的早期打孔机式的BCD排列而成，使用排列而成，使用8位表示一位表示一个字符，共个字符，共256个字符。但英文字母不连续。个字符。但英文字母不连续。为扩充为扩充ASCII码，以显示本国语言，各国家和地码，以显示本国语言，各国家和地区制定的标准，如区制定的

10、标准，如 GB2312, BIG5, JIS 等，称为等，称为 ANSI 编码，又称为编码，又称为MBCS（Muilti-Bytes Charecter Set，多字节字符集），多为，多字节字符集），多为2字节。字节。简体中文中简体中文中ANSI 编码代表编码代表 GB2312 编码，日文编码，日文中中ANSI 编码代表编码代表 JIS 编码。编码。GB 2312是一个简体中文字符集，由是一个简体中文字符集，由6763个常用个常用汉字和汉字和682个全角的非汉字字符组成，排列成个全角的非汉字字符组成，排列成94行行94列，用区位号表示一个字符编码列，用区位号表示一个字符编码.GBK是对是对GB

11、2312的扩充，增加了对人名、古汉的扩充，增加了对人名、古汉语等方面出现的罕用字。语等方面出现的罕用字。BIG5是一个繁体中文字符集，在台湾、香港与是一个繁体中文字符集，在台湾、香港与澳门地区及其他海外华人中普遍使用。澳门地区及其他海外华人中普遍使用。各种各种ANSI编码不兼容，易出现乱码，编码不兼容，易出现乱码，Unicode编编码将所有符号都纳入其中（现在可容纳码将所有符号都纳入其中（现在可容纳100多万多万个符号）。但编码效率不高，比如个符号）。但编码效率不高，比如UCS-4标准标准)规定用规定用4个字节存储一个符号，每个英文字母前个字节存储一个符号，每个英文字母前3个字节为个字节为0，

12、对存储和传输都很耗资源。，对存储和传输都很耗资源。 为提高为提高Unicode编码的效率，推出了编码的效率，推出了UTF-8码，码，它可以根据不同的符号自动选择编码的长度，它可以根据不同的符号自动选择编码的长度，如英文字母采用如英文字母采用1个字节就够了。个字节就够了。 字符串的表示与存储字符串的表示与存储u 字符串是指连续的一串字符，占据主存中连续字节，每字符串是指连续的一串字符，占据主存中连续字节，每个字节存放一个字符，表示字符串数据要给出串存放的主个字节存放一个字符，表示字符串数据要给出串存放的主存存起始地址起始地址和串的和串的长度长度。u 对一个主存字的多个字节，有按从低位到高位字节次

13、序对一个主存字的多个字节，有按从低位到高位字节次序存放的，也有按从高位到低位字节次序存放的。存放的，也有按从高位到低位字节次序存放的。u例如：例如：IF AB THEN READ(C) 存放方式有：存放方式有： I F A A F I B T T B 假定每个字假定每个字4 个字节个字节 H E N N E H R E A D D A E R ( C ) ) C (多媒体信息编码多媒体信息编码1 图图 图像图像 图形图形2 声音声音 语音：采集语音：采集AD转换转换编码编码 音乐：把乐谱、弹奏的乐器类型、击键力度等用音乐：把乐谱、弹奏的乐器类型、击键力度等用符号记录符号记录 效果声效果声3 视

14、频信息视频信息由像素点阵构成的位图 ，色彩丰富、过渡自然，图像像素点越多（分辨率高），图像越清晰，文件就越大。一般通过照相、扫描、摄像得到图形都是位图图像，如bmp、jpg等。由数学公式表达的轮廓线条构成矢量图；放大后图形不失真，占用空间较小。工程设计图、图表、插图经常以矢量图形曲线来表示，如photoshop中的PSD文件。把声音的波形进行编码-波形法把数字式电子乐器的弹奏过程记录下来-合成法数值数据在计算机内的格式数值数据在计算机内的格式定点小数定点小数: N = N N N .Ns-1-n-2整整 数数 : N = N N N . N N01snn-1浮点数浮点数: N = M E E

15、.E E M M .M ssm-110-1-2-n符号位符号位 阶码位阶码位 尾数数码位尾数数码位 总位数总位数 短浮点数短浮点数: 1 8 23 32长浮点数长浮点数: 1 11 52 64 临时浮点数临时浮点数: 1 15 64 80IEEE 标准：标准： 阶码用移码，阶码用移码，尾数用原码尾数用原码 基为基为 2 8421码码 余余3码码 循环码循环码 84-2-10 0000 0011 0000 00001 0001 0100 0001 01112 0010 0101 0011 01103 0011 0110 0010 01014 0100 0111 0110 01005 0101 1

16、000 1110 10116 0110 1001 1010 10107 0111 1010 1000 10018 1000 1011 1100 10009 1001 1100 0100 1111十进制数的编码（十进制数的编码（BCD编码）编码）用用4位位二进制表示二进制表示1位位十进制，从十进制，从16个编码中选个编码中选10个，个，有多种方案，例如：有多种方案，例如：8421码，余码，余 3 码，循环码码，循环码8421和和84-2-1为为有权码有权码，即每位，即每位上的上的 1 代表确定的值，如：代表确定的值，如：8421码中码中4个位分别表示个位分别表示8、4、2、1，故编码，故编码01

17、11=0*8+1*4+1*2+1*1=784-2-1码中码中4个位分别表示个位分别表示8、4、-2、-1，故编码，故编码0111=0*8+1*4+1*(-2)+1*(-1)=1余余3码和循环码为码和循环码为无权码无权码：无法：无法确定每位上的确定每位上的 1 代表的值代表的值检错纠错码检错纠错码 为了提高计算机的为了提高计算机的可靠性可靠性，除了采取选用更高，除了采取选用更高可靠性的器件、更好的生产工艺等措施之外，还可可靠性的器件、更好的生产工艺等措施之外，还可以从以从数据编码数据编码上想一些办法，即采用一点冗余的线上想一些办法，即采用一点冗余的线路，在原有数据位之外再路，在原有数据位之外再增

18、加一到几位校验位增加一到几位校验位，使使新得到的码字带上某种特性新得到的码字带上某种特性，之后通过，之后通过检查该码字检查该码字是否仍保持这种特性是否仍保持这种特性，来，来发现发现是否出现了错误，甚是否出现了错误，甚至至自动改正自动改正错误，这就是错误，这就是检错纠错编码技术检错纠错编码技术。三种常用的检错纠错码三种常用的检错纠错码奇偶检错码奇偶检错码， 用于用于并行并行数据传送中数据传送中海明检错与纠错码海明检错与纠错码， 用于用于并行并行数据传送中数据传送中循环冗余码循环冗余码， 用于用于串行串行数据传送中数据传送中编码编码译码译码传送传送原始数据原始数据码码 字字结果数据结果数据形成校验

19、位的值，形成校验位的值，加进特征加进特征检查接送的码字，检查接送的码字，发现发现 / 改正错误改正错误奇偶校验码奇偶校验码校验位校验位用于用于并行数据检错并行数据检错原理：原理：在在 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 原始信息原始信息 两个新的码字两个新的码字 偶校验偶校验奇校验奇校验奇偶校验码的实现电路奇偶校验码的实

20、现电路出错指示出错指示编码电路编码电路译码电路译码电路P (校验位校验位)0 D6 D5 D4 D3 D2 D1 D0p编码编码电路电路P奇奇= D6 D5 D4 D3 D2 D1P偶偶= D6 D5 D4 D3 D2 D1E奇奇=D6 D5 D4 D3 D2 D1 P奇奇当当E奇奇=1时为合法码时为合法码E偶偶=D6 D5 D4 D3 D2 D1 P偶偶当当E偶偶=0时为合法码时为合法码奇较验奇较验 偶校验偶校验7位数位数据位据位奇偶检验码练习奇偶检验码练习-教材教材P75：4解：解：数据数据01010111中有中有5个个1，故：，故：奇校验：奇校验：0 01010111 偶校验：偶校验：1

21、 01010111数据数据11010100中有中有4个个1，故：，故：奇校验：奇校验：1 11010100 偶校验：偶校验：0 11010100海明校验码海明校验码用于并行数据检错纠错，如用于并行数据检错纠错，如主存的主存的ECC(Error Correcting Code) 是海明校验码的一种典型应用。是海明校验码的一种典型应用。实现原理实现原理：在：在k个数据位中加入个数据位中加入r个校验位，个校验位， 将数据将数据代码的码距比较均匀地拉开，并把每数据位分配代码的码距比较均匀地拉开，并把每数据位分配在几个奇偶校验组中。当某位出错时，就会引起在几个奇偶校验组中。当某位出错时，就会引起相关的几

22、个校验位值发生变化，这不仅可发现错相关的几个校验位值发生变化，这不仅可发现错误，还能指出哪一位出错，为进一步自动纠借提误，还能指出哪一位出错，为进一步自动纠借提供了依据。供了依据。海明校验码构成海明校验码构成r个位可表示个位可表示2r个码，个码，用其中一个码表示是否出错，用其余用其中一个码表示是否出错，用其余2r-1个码指个码指示出错位置，则最多可指示示出错位置，则最多可指示2r-1个位，个位，数据位和检验位都有可能出错，故校验位数数据位和检验位都有可能出错，故校验位数r和和数据位数数据位数k应满足不等式：应满足不等式：2r - 1kr，也即，也即k2r - 1 - rk值值 最小最小r值值1

23、43511412265 27576 581197例如，校验位数例如，校验位数r=4，可表示，可表示16个码，可用于纠正被传送的个码，可用于纠正被传送的最多有效数据位最多有效数据位k=16-1-4=11。(1)校验位分布校验位分布若由若由k个数据码个数据码DkDk-1D1和和r个校验码个校验码PrPr-1P1构成的海构成的海明码格式为明码格式为HmHm-1H3H2H1, m=k+r，则：，则：PrPr-1P1依次分布在依次分布在H2r-1、H2r-2 、H4、H2、H1上，上，DkDk-1D1按序分布在剩余位置上。按序分布在剩余位置上。例如：例如：5位信息码位信息码D5D4D3D2D1，需，需4

24、位检验码位检验码P4P3P2P1 ，则，则9位海明码为：位海明码为：H9 H8 H7 H6 H5 H4 H3 H2 H1D5 P4 D4 D3 D2 P3 D1 P2 P1海明码编码规则海明码编码规则-1(2)校验关系校验关系指海明码中每个指海明码中每个Hi由哪些由哪些P?来校验，关系为：被校验位来校验，关系为：被校验位位号位号=校验位校验位位号之和位号之和。例如：。例如：H3对应对应H2、H1(3=2+1)，故，故H3处的处的D1由由P2、P1校验校验H5对应对应H4、H1(5=4+1)，故，故H5处的处的D2由由P3、P1校验校验H6对应对应H4、H2(6=4+2)，故，故H6处的处的D3

25、由由P3 、P2校验校验H7对应对应H4、H2、H1(7=4+2+1)，故，故D4由由P3、P2、P1校验校验H9对应对应H8、H1(9=8+1)，故，故D5在由在由P4、P1检验检验注意：由于注意：由于H1、H2、H4、H8、H16本身是检验位，因此本身是检验位，因此不再由其他检验位进行检验。不再由其他检验位进行检验。海明码编码规则海明码编码规则-2海明码编码规则海明码编码规则-3(3) 校验位的取值校验位的取值H9D5H8P4H7D4H6D3H5D2H4P3H3D1H2P2H1P1P4P3P2P1按行采用偶校验，各校验位计算公式如下：按行采用偶校验，各校验位计算公式如下：P4=D5P3=D

26、4 D3 D2P2=D4 D3 D1P1=D5 D4 D2 D1 海明码解码海明码解码在收到数据解码时，按奇偶校验码解码方式处理：在收到数据解码时，按奇偶校验码解码方式处理：S4=D5 P4S3=D4 D3 D2 P3S2=D4 D3 D1 P2S1=D5 D4 D2 D1 P1若若S4S3S2S1 = 0S4S3S2S1 = 0，说明传送无错，说明传送无错, , 接收到的代码无错接收到的代码无错; ;若若S4S3S2S1 0, S4S3S2S1 0, 说明传送有错说明传送有错, , 此时此时S4S3S2S1S4S3S2S1代表的十进代表的十进制数值就是出错的位号制数值就是出错的位号, , 故

27、将故将SS3S2S1SS3S2S1称为指误字称为指误字( Symptom )( Symptom )。海明码举例海明码举例-一位出错一位出错例：假设海明码数据在传送时第例：假设海明码数据在传送时第5位发生错误。位发生错误。 H9 H8 H7 H6 H5 H4 H3 H2 H1 D5 P4 D4 D3 D2 P3 D1 P2 P1发送海明码发送海明码 0 0 0 1 0 1 0 1 0(如数字如数字4, 00100)接收的海明码接收的海明码 0 0 0 1 1 1 0 1 0 出错出错则：则：S4=D5 P4 =0 S3=D4 D3 D2 P3= 0 1 1 1=1 S2=D4 D3 D1 P2=

28、 0 1 0 1=0 S1=D4 D2 D1 P1= 0 1 0 0=1从而得到指误字从而得到指误字S4S3S2S1 =0101，说明，说明H5(数据位数据位D2)出错出错, 将将D2取反即可。取反即可。海明码举例海明码举例-两位出错两位出错例：假设海明码数据在传送时第例：假设海明码数据在传送时第5、6位同时发生错误。位同时发生错误。 H9 H8 H7 H6 H5 H4 H3 H2 H1 D5 P4 D4 D3 D2 P3 D1 P2 P1发送海明码发送海明码 0 0 0 1 0 1 0 1 0(如数字如数字4, 00100)接收的海明码接收的海明码 0 0 0 0 1 1 0 1 0 出错出

29、错则：则：S4=D5 P4 =0 S3=D4 D3 D2 P3= 0 0 1 1=0 S2=D4 D3 D1 P2= 0 0 0 1=1 S1=D4 D2 D1 P1= 0 1 0 0=1从而得到指误字从而得到指误字S4S3S2S1 =0011，说明，说明H3(数据位数据位D1)出错，出错，与事实不符。与事实不符。结论结论: :海明码能海明码能查出查出2 2位以上的错误，但位以上的错误，但不能定位和纠错。不能定位和纠错。海明码改进海明码改进-纠一检两纠一检两增加一个检验位，用于区分是一位错还是两位错。增加一个检验位，用于区分是一位错还是两位错。仍以仍以5位数据为例，此时检验码需增加到位数据为例

30、，此时检验码需增加到5位，则位，则P4P3P2P1编解码同前面方案，而编解码同前面方案，而P5位于位于H10，海明码格式海明码格式如下：如下： H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 P5 D5 P4 D4 D3 D2 P3 D1 P2 P1且且P5的编码的编码为：为：P5=H1 H2 H9P5的解码的解码为：为：S5=H1 H2 H9 H10(即即P5)结论：结论：当当Si(i=15)全为全为0，表示接收无误；，表示接收无误；当当S5=1，S4S3S2S1 = 0000，表示，表示P5出错；出错；当当S5=1，S4S3S2S1 0000，表示一位错，其值为出错位置；，表

31、示一位错，其值为出错位置；当当S5=0，S4S3S2S1 0000，表示两位错，错误位置不确定。，表示两位错，错误位置不确定。检错纠错码小结检错纠错码小结(1) K位码有位码有2K 个编码状态，若全用于表示合法码，个编码状态，若全用于表示合法码，则任何一位出错，均会变成另一个合法码，不具则任何一位出错，均会变成另一个合法码，不具有检错能力。有检错能力。(2) 从一个合法码变成另一个合法码，至少要改变几从一个合法码变成另一个合法码，至少要改变几位码的值，称为位码的值，称为最小码距最小码距(码距码距)。(3) K+1 位码，只用其位码，只用其 2K 个状态，可使码距为个状态，可使码距为 2 , 如

32、果一个合法码中的一位错了，就成为如果一个合法码中的一位错了，就成为非法码非法码，通过检查通过检查码字的合法性码字的合法性，就，就得到检错能力得到检错能力，这就，这就是奇偶校验码。是奇偶校验码。检错纠错能力检错纠错能力(4) 对对 k 位数据位，当给出位数据位，当给出 r 位校验位时，位校验位时，要发现并要发现并改正一位错，改正一位错， 须满足如下关系：须满足如下关系： 2r = k + r +1 ； 要发现并改正一位错，也能发现两位错要发现并改正一位错，也能发现两位错,则应则应： 2r-1 = k + r , 此时码距为此时码距为 4。(5) 若最小码距为若最小码距为 d (d=2), 能发现

33、能发现 d-1 位错，位错，或或改正改正 (d-2)/2 (取整取整) 位错位错,要发现要发现 l 位错位错,并并改正改正 t 位错，应满足如下条件位错，应满足如下条件: d = l + t + 1 ( l = t )海明码练习海明码练习-教材教材P75：7对对8位数据进行检位数据进行检1纠纠1需需4位校验位，检位校验位，检2纠纠1则需则需5位。位。H12 D8H11 D7H10 D6H9 D5H8 P4H7 D4H6 D3H5 D2H4 P3H3 D1H2 P2H1 P1P4P3P2P1数据数据01010111的的5个校验位取值如下：个校验位取值如下：P1=D7D5 D4 D2 D1=1 1

34、 0 1 1 = 0P2=D7 D6 D4 D3 D1=1 0 0 1 1 = 1P3=D8 D4 D3 D2=0 0 1 1 = 0P4=D8 D7 D6 D5=0 1 0 1 = 0P5=Hi=0海明码为：海明码为：0 0101 0 011 0 1 1 0数据数据00000000，5个校验位取值如下：个校验位取值如下：P1=D7D5 D4 D2 D1= 0P2=D7 D6 D4 D3 D1=0P3=D8 D4 D3 D2=0P4=D8 D7 D6 D5=0P5= Hi=0海明码为：海明码为：0 0000 0 000 0 0数据数据 0 1 0 1 0 1 1 1海明码练习海明码练习-教材教

35、材P75：7若若01010111的最低数据位由的最低数据位由1变成变成0，即变成，即变成01010110，则：，则：原海明码原海明码0 0101 0 011 0 1 1 0变成变成 0 0101 0 011 0 1 1 0译码过程：译码过程：S1=D7D5 D4 D2 D1 P1=1 1 0 1 0 0 = 1S2=D7 D6 D4 D3 D1 P2=1 0 0 1 0 1 = 1S3=D8 D4 D3 D2 P3=0 0 1 1 0 = 0S4=D8 D7 D6 D5 P4=0 1 0 1 0 = 0S5= Hi=1根据译码结果知根据译码结果知S5=1，表示，表示1位错，错误位置在位错，错误

36、位置在0011，即，即H3，故，故D1位错。位错。海明码练习海明码练习-教材教材P75：7若若00000000的最低、最高数据位由的最低、最高数据位由0变成变成1，即变成，即变成 10000001，则原海明码，则原海明码0 0000 0 000 0 0 0 0 变成变成 0 1000 0 000 0 1 0 0译码过程：译码过程：S1=D7D5 D4 D2 D1 P1=0 0 0 0 1 0 = 1S2=D7 D6 D4 D3 D1 P2=0 0 0 0 1 0 = 1S3=D8 D4 D3 D2 P3= 1S4=D8 D7 D6 D5 P4= 1 0 0 0 0 = 1S5= Hi=0根据译

37、码结果知根据译码结果知S5=0，S4S3S2S100000000，故两位错，具体哪两位不知。，故两位错，具体哪两位不知。循环冗余校验循环冗余校验(Cyclic Redundancy Check ,CRC)码，简码，简称称CRC码，是一种检错、纠错能力很强的数据码，是一种检错、纠错能力很强的数据校验码，主要用于网络、同步通信及磁表面存储校验码，主要用于网络、同步通信及磁表面存储器等场合。器等场合。CRC码格式码格式CRC码的左边为信息位，右边为校验位。若信息码的左边为信息位，右边为校验位。若信息位为位为n位，校验位为位，校验位为r位，则该校验码被称为位，则该校验码被称为(n+r,r)循环码。循环

38、码。循环冗余校验码循环冗余校验码信息位信息位校验位校验位n位位r位位循环冗余校验码的格式循环冗余校验码的格式CRC编码步骤编码步骤如下：如下：(1)将待编码的将待编码的n位有效信息位表示为一个位有效信息位表示为一个n-1阶多项式阶多项式M(x)。(2)将将M(x)左移左移r位，得到位，得到M(x).xr（r由预选的由预选的r+1阶生成多项阶生成多项式式G(x)决定）。决定）。(3)用预选的用预选的r+1阶生成多项式阶生成多项式G(x)对对M(x).xr作作模模2除法除法。(4)把左移把左移r位后的的有效信息位与位后的的有效信息位与余数余数作作模模2加法加法，形成长度，形成长度为为n+r的的CR

39、C码。码。M(x).xr+R(x) Q(x).G(x) CRC编码方法编码方法M(x)xxr r G(x) Q(x) R(x)G(x)模模2运算运算模模2加减运算加减运算是指不考虑进是指不考虑进/借位，即：借位，即：000, 011, 101, 110 ，实际是实际是异或异或操作。操作。模模2除法除法的的上商原则上商原则是当部分余数首位是是当部分余数首位是1时，商取时，商取1，即使比除数小，反之商取，即使比除数小，反之商取0；然后按；然后按模模2减减求余求余数。当被除数除完时的余数就是校验位（比除数少数。当被除数除完时的余数就是校验位（比除数少一位）。一位）。 CRC编码举例编码举例例：使用生

40、成多项式为例：使用生成多项式为G(X)X3X1，把，把4位信息位信息1100编成编成CRC码。码。解：解：步骤步骤1：由于：由于G(X)为为3次多项式，故次多项式，故r取取3，将信息码，将信息码1100左移左移3位得位得11000000（ 相当于相当于M(X)=X3+X2，M(X)X3=X6+X5）步骤步骤2：由于：由于G(X)多项式系数对应多项式系数对应1011，计算，计算模模2除除法：法：1100000/1011，得商为，得商为1110，余数为，余数为010（相当于计算（相当于计算M(X)X3/G(X)=(X6+X5)/(X3+X+1)，得，得Q(X)=X3+X2+X1，R(X)=X）步骤

41、步骤3：将：将1100000与余数与余数010进行进行模模2加加， 即即1100000+010=1100010，1100010即为所求的即为所求的CRC码码（相当于计算（相当于计算M(X)X3+R(X)）CRC码的纠错原理码的纠错原理 由于由于M(X).XrQ(X).G(X)+R(X)，根据模，根据模2加的规则加的规则M(X).Xr+R(X)=Q(X).G(X)+R(X)+R(X)Q(X).G(X)上式表明上式表明, 合法的合法的CRC码应当能被生成多项式整除。码应当能被生成多项式整除。若若CRC码不能被生成多项式整除，说明出现差错。码不能被生成多项式整除，说明出现差错。当出现信息的传送差错时

42、，当出现信息的传送差错时，CRC码被生成多项式整除所码被生成多项式整除所得到的余数与出错位之间有唯一的对应关系得到的余数与出错位之间有唯一的对应关系, 根据这一根据这一关系便可立即确定出错位的位置关系便可立即确定出错位的位置。若某位出错，则余数不为若某位出错，则余数不为0，对此余数补，对此余数补0后继续作模后继续作模2除法除法, 此后余数将按一定顺序循环。此后余数将按一定顺序循环。对前例，形成对前例，形成010、100、011、110、111、101、001、010的循环，反复循环，这就是的循环，反复循环，这就是“循环码循环码”一词的来源。一词的来源。 CRC生成多项式的选择生成多项式的选择被

43、用来生成被用来生成CRC码的多项式一般码的多项式一般满足下列要求：满足下列要求：（1）任何一位出错都应使余数不为）任何一位出错都应使余数不为0。（2）不同位出错应使余数不同。）不同位出错应使余数不同。（3）对余数继续作模）对余数继续作模2除法，应使余数循环。除法，应使余数循环。（4）必须是）必须是r次多项式，且次多项式，且Xr和和X0的系数为的系数为1。生成多项式的选择主要靠经验，但已有生成多项式的选择主要靠经验，但已有几种多项几种多项式式具有极高的检错率，被广泛运用，分别是具有极高的检错率，被广泛运用，分别是:CRC12X12X11X3X2X1CRC16X16X15X21CRCCCITTX1

44、6X12X51本章主要内容本章主要内容3.1 信息编码、码制转换与检错纠错码信息编码、码制转换与检错纠错码3.2 数据表示数据表示常用的信息编码常用的信息编码3.3 二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法+ 0.1011+ 1100 1100 0.1011带符号的数带符号的数 符号数字化的数符号数字化的数真值真值 机器数机器数 0 1011 1 1011 0 1100 1 1100小数点的位置小数点的位置数据的实际值被称为数据的实际值被称为真值真值。数据在机器内要用规定的编码来表示，这种数据在机器内要用规定的编码来表示，这种表示被称为表示被称为机器数机器数。机器数与真值机

45、器数与真值定点小数原码定点小数原码定义：定义： X 原原 =实例：实例： X = 0.10110 -0.10110 0.0000 X原原 = 0 10110 1 10110 0 0000 1 0000 X 1 - X -1 X 0 0 X 1结论：原码为符号位加数的绝对值，结论：原码为符号位加数的绝对值，0正正 1负负 原码零有两个编码，原码零有两个编码，+0 和和 -0编码不同编码不同 原码难以用于加减运算，但乘除方便原码难以用于加减运算，但乘除方便(原因原因?)定点原码特点定点原码特点u 原码加减法困难：原码加减法困难：要比较参与加减运算的两个数的符号，还要比要比较参与加减运算的两个数的符

46、号，还要比较它们的绝对值的大小，才能确定运算结果的较它们的绝对值的大小，才能确定运算结果的数值和符号。数值和符号。u 原码乘除法方便：原码乘除法方便：两个数的符号异或，数值相乘除即可。两个数的符号异或，数值相乘除即可。定点小数反码定点小数反码定义：定义： X 反反 =实例：实例： X = 0.10110 -0.10110 0.0000 X反反 = 0 10110 1 01001 0 0000 1 1111 X (2-2-n) + X -1 X 0 MOD (2-2-n) 0 X 1结论：负数结论：负数反码反码为符号位跟每位数值位取反，为符号位跟每位数值位取反，0 正正1 负负 反码反码零有二个

47、编码，分零有二个编码，分+0 和和 -0 反码反码难以用于加减运算，有循环进位问题难以用于加减运算，有循环进位问题(举例举例?)定点反码循环进位问题定点反码循环进位问题如：如： X = +0.1011， Y = -0.0100， X反反 = 0 1011， Y反反= 1 1011X反反 + Y反反 = 0 1011 + 1 1011 = 1 0 0110有进位，结果再加有进位，结果再加1，即，即 0 0110+1 = 0 0111又如：又如： X = +0.1011， Y = 0.0100， X反反 = 0 1011 Y反反 = 0 0100X反反 + Y反反 = 0 1011 + 0 010

48、0 = 0 1111没有进位，没有进位，01111就是最后结果。就是最后结果。 定点小数模定点小数模2补码补码定义：定义： X 补补 =实例：实例： X = 0.10110 -0.10110 0.0000 X补补 = 0 10110 1 01010 0 0000 X 2 + X -1 X 0 MOD 2 0 X =0时，时，X0=0，X补补 = 0.X1X2Xn = X 有：有： 当当X0时，时， X0=1, X补补 = 1.X1X2Xn = 2 + X 所以：所以：X = 1.X1X2Xn 2 = -1 + 0.X1X2Xn = -X0 + 0.X1X2Xn 也有：也有：2/ )2XiX0(

49、X/2n1ii2/ )2XiX0(X/2n1ii结论：结论：X补补的负系数加数值部分，等于真值的负系数加数值部分，等于真值X例：例：X补补=1 0110，则：，则： X=-1 + 0.0110 = -(1-0.0110) =-0.1010 y补补 = 0 y1 y2 yny = 0. y1 y2 yny = 0. y1 y2 yn y补补 = 1 y1 y2 yn + 2-n y补补 = 1 y1 y2 yn y原原 = 1 y1 y2 yn + 2-n y = （0. y1 y2 yn + 2-n） y = 0. y1 y2 yn + 2-n y补补 = 0 y1 y2 yn + 2-n每位

50、取反，每位取反，即得即得 y补补y补补连同符号位在内，连同符号位在内，末位加末位加 1每位取反，每位取反，即得即得 y补补y补补连同符号位在内，连同符号位在内，末位加末位加 1已知已知 y补补如何简单求如何简单求-y补补整数的编码表示整数的编码表示整数的整数的 原码原码 反码反码 补码补码 表示表示与小数的三种表示与小数的三种表示基本相同基本相同，小数点在最低数值位的，小数点在最低数值位的右侧右侧2因此整数的取值范围与整数因此整数的取值范围与整数位数位数有关。有关。(定点小数的取值范围与位数无关，精度与位数有关定点小数的取值范围与位数无关，精度与位数有关)例如：整数六位编码例如：整数六位编码

51、X = +01110 X原原= 0 01110 X补补= 0 01110 X = - 01110 X原原= 1 01110 X补补= 1 10010原原 反反 补码表示小结补码表示小结正数的正数的 原码、反码、补码原码、反码、补码表示均相同表示均相同，符号位为符号位为 0，数值位同真值。，数值位同真值。零的零的原码和反码均有原码和反码均有 2个编码，补码只有个编码，补码只有 1个个负数的负数的原码，反码，补码表示均不同，原码，反码，补码表示均不同，符号位为符号位为 1，数值位：原码为数的绝对值，数值位：原码为数的绝对值 反码为每一位均取反反码为每一位均取反 补码为反码再加补码为反码再加1由由X

52、补补求求-X补补：每一位取反后：每一位取反后,再在最低位再在最低位+1 n由由 X补补 求求 X 的真值：的真值：X= -X0 + Xi * 2-ii=1补码加减法补码加减法X + + Y补补 = X补补 + + Y补补X - - Y补补 = X补补 - - Y补补X - - Y补补= X补补 + -Y补补l 说明减法可用加法实现说明减法可用加法实现l 如何求如何求-Y补补？l 对对Y补补逐位取反，末位逐位取反，末位再加再加1，得，得-Y补补例：例：X=+0.1011 y= -0.0101，求，求X+Y和和X-Y。解：解：X补补= 0 1011, Y补补=1 1011， -Y补补=0 0101

53、 0 1011+1 1011 0 0110则则X+Y补补=0 0110故故X+Y=0.0110 0 1011 + 0 0101 1 0000则则X-Y补补=1 0000故故X-Y=-1.0000结果竟为负结果竟为负数？数？ 溢出了溢出了! 0.1011-0.0101 0.0110 0.1011+0.0101 1.0000故故X+Y=+0.0110 X-Y=+1.0000人工算人工算补码加减法溢出判断补码加减法溢出判断(1) 正正 + 正正 得得负负 或或 负负 + 负负 得得正正(2) 数字位向符号位有进位，但符号位不产生向更高位的进位数字位向符号位有进位，但符号位不产生向更高位的进位(3)

54、双符号位双符号位的值为的值为 01 或或 10前例：前例：X=+0.1011，Y= -0.0101，采用双符号位（模，采用双符号位（模 4 补码）补码）X补补= 00 1011, Y补补= 11 1011 -Y补补= 00 0101 00 1011 + 00 0101 01 0000X-Y (溢出溢出) 00 1011+11 1011100 0110则则X+Y补补=00 0110故故X+Y=0.0110XX补补+Y+Y补补XX补补+-Y+-Y补补F X实现补码加减运算的逻辑电路实现补码加减运算的逻辑电路Fs F ALU 目的目的 寄存器寄存器源源 寄存器寄存器 选通门选通门二选通门二选通门选通

55、门选通门F 1XYF YX F010 1F /YFsOVRZC累加器累加器减法：减法：X X-Y /1加法：加法：X X+Y溢出判断电路溢出判断电路V= x0 y0 z0 + x0y0z0 判断电路 FA V z0 y0 x0 判断电路 单符号位判断：单符号位判断：正加正得负或负加负得正表明溢出正加正得负或负加负得正表明溢出补码表示中的符号位扩展补码表示中的符号位扩展由由X补补 求求X/2补补 ： 原符号位不变，且符号位与数值位均右移一位，原符号位不变，且符号位与数值位均右移一位， 例如，例如， X补补 =10010 则则 X/2补补 =110010不同位数的整数补码相加减时，不同位数的整数补

56、码相加减时， 位数少的补码数的符号位向左扩展，位数少的补码数的符号位向左扩展， 0101010111000011 0101010111000011 + 1111111110011100 + 0000000000011100 0101010101011111 0101010111011111补码计算练习补码计算练习原码一位乘法原码一位乘法 例如：例如： X = 0.1101 Y = - 0.1011 0. 1 1 0 1 问题：问题： * 0. 1 0 1 1 1. 加法器只有两个数据输入端加法器只有两个数据输入端 1 1 0 1 2. 加法器与乘运算数据位数相同加法器与乘运算数据位数相同 1

57、1 0 1 解决方案：解决方案： 0 0 0 0 1. 每次求出部分积，而不是一次总累加每次求出部分积，而不是一次总累加 + 1 1 0 1 变每次左移被乘数为右移部分积变每次左移被乘数为右移部分积 0 . 1 0 0 0 1 1 1 1 2. 判乘数每一位的值用固定的一位线路判乘数每一位的值用固定的一位线路 手工运算过程手工运算过程 例如：例如： X = 0 . 1 1 0 1 Y = - 0 . 1 0 1 1 0. 1 1 0 1 * 0. 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1 0 10 . 1 0 0 0 1 1 1 1 手工运算过程手工运算过程

58、原码一位乘运算原码一位乘运算 X*Y原原 =(X Y)(|X|*|X|) 累加器初值取零值累加器初值取零值+ 初值加被乘数初值加被乘数 部分积右移部分积右移+ 前次部分积加被乘数前次部分积加被乘数 部分积右移部分积右移+ 前次部分积加前次部分积加+ 部分积右移部分积右移前次部分积加前次部分积加 部分积右移部分积右移两数符号再异或求积两数符号再异或求积的符号，最终：的符号，最终：X*Y = -0.10001111实现原码一位乘法的逻辑线路图实现原码一位乘法的逻辑线路图 加加 法法 器器 部部 分分 积积 被被 乘乘 数数 乘乘 数数 F最低位最低位加运算加运算移位线路移位线路每位每位1套套 第第

59、 i 位位第第 i 位位第第 i +1位位第第 i -1位位F/2X FX F*2X移位电路移位电路把乘数放在一把乘数放在一个移位寄存器个移位寄存器中，该寄存起中，该寄存起又用来接受加又用来接受加法器的移位输法器的移位输出，则判乘数出，则判乘数的某一位也更的某一位也更方便方便原码一位乘法原码一位乘法0 0 0 0 0 0 1 0 1 1 加加 法法 器器 部部 分分 积积 被被 乘乘 数数 乘乘 数数 F最低位最低位加运算加运算移位线路移位线路每位每位1套套0 0 0 0 0 00 0 1 1 0 1 1 0 1 10 0 1 1 0 10 0 1 1 0 10 0 0 1 1 0 1 1 0

60、 1 1 0 1 10 1 0 0 1 10 1 0 0 1 11 1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 低位积低位积 已知：已知：X=0.1001，Y=0.1101，计算计算X*Y。原码一位乘法运算例原码一位乘法运算