2 信息表示与编码.ppt

1、三极管 组成计算机的基本元件二进制计算机中的信息表示逻辑代数 现代计算机的理论基础,第2章 计算机中的信息表示和编码,2.1 常用进位计数制 2.2数值数据的0、1编码 2.3字符数据的0、1编码 2.4图像的0、1编码 2.5声音的0、1编码 2.6指令的0、1编码 2.7数据传输中的差错检验,2.1 常用进位计数制,2.1.1从十进制到二进制 2.1.2八进制和十六进制 2.1.3数制的转换,2.1.1从十进制到二进制 1.进位计数制的4 个要素： 基数：进位计数制中数码的个数称为基数。10进制基数是10。 数码 ：十进制中有0、1、2、3、9 共十个数码。 位权值：在进位记数制中数码所处

2、的位置不同,代表的数值大 小也不同，位权的值等于基数的若干次幂。 进位规律：逢10进1，借1当10 。 例:十进制1234.5可以按权展开为多项式的和 由于10进制位权值是10的整数次冥，因此展开如下： 1234.5=110 3+2 10 2+3 10 1+4 10 0+5 10 -1,2.二进制的特点: 数码 ：二进制数只有0或1两个数码。 基数：为2。 位权值：各位的权值是以2为底的连续整数幂，从右向左递增。 进位规律：二进制的进位规则是由低位向高位“逢二进一” 。 按权展开： (N)2=(kn-1kn-2 k1k0 .k-1k-2 k-m)2 = ki2i (i=-m n-1）,3. 二

3、进制运算法则 加法规则：“逢2进1” 0 + 0 = 0 1 + 0 = 0 + 1 = 1 1 + 1 = 10 例： 101.01+110.11? 解：,减法规则：“借1当2” 0 0 = 0 ；1 0 = 1； 1 1 = 0 ； 10 1 = 1； 例： 1100.00-110.11? 解：,乘法规则 0 0 = 0 1 0 = 0 1 = 0 1 1 = 1 显然，二进制数乘法比十进制数乘法比简单多了。,2.1.2八进制和十六进制,由于二进制数书写太长，难认、难记，因此我们常使用八进制和十六进制作为二进制的助记形式。 1.特点 八进制记数符：0，1，2，3，4，5，6，7 十六进制记

4、数符：0，1，2，3，4，5，6，7，8，9，A(a)，B(b)，C(c)，D(d)，E(e)，F(f) 2.与二进制的关系 三位二进制数可用一位八进制数表示 四位二进制数可用一位十六进制数表示,3.二进制数转换为八进制或十六进制的方法 从小数点开始，两侧分别向左、右按每3位一组（最高位与最低位不足3位以0补）转换为八进制或按4位一组转换为十六进制，将每组以对应的等值八进制数或十六进制数代替。 具体举例如下： 例： 10110 1110.1111B ?H 解：补零 0001 0110 1110 . 1111 1 6 E F 所以 10110 1110.1111B16E.FH,二进制数：010

5、101111 000101101100 八进制数： 2 5 7 . 0 5 5 4 二进制数：1010 1111 0001 0110 1100 十六进制： A F . 1 6 C (0011 0110 1110.1101 0100) 2 = ( 36E.D4 ) 16 (001 101 101 110. 110 101 ) 2 = ( 1556.65 ) 8,4.八、十六进制数转换为二进制的方法： 每位八进制数直接转换为3位二进制数。 每位十六进制数直接转换为4位二进制数 例：N=（C1B）H=（？）B （C1B）H=1100/0001/1011=（110000011011）B,常用的进位计数

6、制的特点如下表：,不同的进位计数制计数规律（逢 R 进 一）,在计算机中常用数制的书写形式,在计算机中常用数制的书写形式, 数字后面加写相应的英文字母作标识,(567)10 (1011)2 (345)8 (5AD)16, 2.1.3数制的转换 ,二进制转换为十进制方法：按权展开 例 ：(11010.101)2=124+123+022+121+020 +12-1+02-2+12-3 =16+8+2+0.5+0.125 =(26.625)10,2. 其他进制转换为十进制,方法：按权展开 例：十六进制数N=（1FA3.B3）H 按权展开为： N=1*163+15*162+10*161+3*160+1

7、1*16-1+3*16-2 例： N=（10110.101）B=（？）D 按权展开： N=1*24+0*23+1*22+1*21+0*20+1*2-1+0*2- 2+1*2-3 =16+4+2+0.5+0.125 =（22.625）D,3. 十进制数转换成二进制数 方法：将待转换的数分成整数部分和小数部分，并分别加以转换。 整数部分转换 十进制数的整数部分采用“除2取余”法，直到商为0，反向书写。即最后所得余数为最高位。 例如，将十进制整数58转换为二进制整数，具体转化法如下：,纯小数转换,十进制数的小数部分采用“乘2取整”法进行转换， 直到小数部分为0或达到所要求的精度。正向书写。 如：将十

8、进制小数0.625转换为二进制小数,注意： 运算时，式中的整数不参加连乘。 有时，小数十二转换，会出现转换不完的情况。 这时可按“舍0取1”（相当于四舍五入）的原则，取到所需的位数,例：( 9.6875 ) 10 = ( ? ) 2,用除2取余法求出整数9对应的二进制（逆向书写）,0.68752=1.375 取出整数1 0.3752=0.75 取出整数0 0.752=1.50 取出整数1 0.52=1.00 取出整数1 （0.6875）1 0 =（0.1011）2,(9.6875)10=(1001.1011)2,用乘2取整法求出小数部分0.6875的二进制（正向书写）,数制与转换小结： 二进制

9、：0 1两个数码 八进制记数符：0，1，2，3，4，5，6，7 十六进制记数符：0，1，2，3，4，5，6，7，8，9，A(a)，B(b)，C(c)，D(d)，E(e)，F(f) 转换： 三位二进制数可用一位八进制数表示 四位二进制数可用一位十六进制数表示 二、八、十六进制与十进制间的转换：（按权展开） 十进制数转换成二进制数：将待转换的数分成整数部分和小数部分，并分别加以转换。整数部分转换采用“除2取余”法，直到商为0，反向书写。即最后所得余数为最高位。小数部分采用“乘2取整”法进行转换， 直到小数部分为0或达到所要求的精度。正向书写。,2.2数值数据的编码,2.2.1 机器数的原码、反码和

10、补码表示 2.2.2 机器数的浮点与定点表示 2.2.3 十进制数的二进制编码 BCD码,2.2.1 机器数的原码、反码和补码表示,1.计算机中信息的表示 冯诺伊曼计算机的特点之一：使用二进制。现代电子计算机中所需要的一切信息，都是用电路状态的组合表示的，数字计算机中电路状态只有两种用于表示“0”和“1”，所以计算机中的所有信息都要用“0”和“1”的组合表示，这就是信息的编码。,2.机器数和真值： 一个数在机器内的表示形式称为机器数。它将一个数连同它的符号在机器中被0，1编码化了。这个数本身的值称为该机器数的真值。 在计算机中不仅要用0，1编码的形式表示一个数的数值部分， 正、负号也要用0，1

11、编码来表示。一般用数的最高位（最左边一位）（MSB，Most Significant Bit）表示数的正负， 当：MSB0 表示正数，如+1011表示为01011； MSB1 表示负数，如-1011表示为11011。 这里“01011”和“11011”就是两个机器数。它们的真值分 别为+1011和-1011。,3.无符号数和带符号数： 不需要考虑正、负的数是称为无符号数。如内存单元的地址。无符号数不需要用一位来表示符号。所以用同样字长，无符号数的最大值比有符号数要大一倍。如字长为4位时，能表示的无符号数的最大值为1111，即15，而表示的无符号数的最大值为111，即7。,4.原码 机器数通常有

12、3种主要形式，分别是：原码、反码和补码。 编码规则： 最高1位表示符号位，对于正数，符号位记作0；对于负数，符号位记作1；其余各位表示数值部分。 例如N1和N2的真值形式为 N1=+100110 N2=-010101 则N1和N2的原码表示形式为 N1原= 0100110 N2原= 1010101,5.反码 编码规则： 左边第1位是符号位，符号位为0代表正数，符号位为1代表负数。对于负数，反码的数值是将原码数值按位求反，即原码的某位为1，反码的相应位就为0，或者原码的某位为0，反码的相应位就为1。而对于正数，反码和原码相同。 例如：N1 = +100110 N2 = - 010101 则N1和

13、N2的反码表示形式为： N1反 = 0100110 N2反= 1101010,6.补码 编码规则： 在补码表示中，正数的表示同原码和反码的表示是一样的，对于负数，其符号位为1，而数值位是将原码按位取反后，再在最低位加1。 例如：两个带符号的二进制数分别为N1和N2，其真值形式为： N1=+100110 N2= - 010101 则N1和N2的补码表示形式为： N1补= 0100110 N2补= 1101011,X X原 X反 X补 +1101 01101 01101 01101 -1101 11101 10010 10011 取反 补1 不论对正数，还是对负数，反码与补码具有下列相似的性质：

14、X反反X原 X补补X原,7.移码 移码是在补码的最高位加1，故又称增码。 例： 几个数的4位二进制补码和移码 真值 补码 移码 +3 0011 1011 0 0000 1000 -3 1101 0101 显然，补码和移码的数值部分相同，而符号位相反。,注意: 字长为8位时，原码、反码的表数范围为+127-127，而补码的表数范围为+127-128。这是因为负数的补码是在其反码上加1的缘故。 反码有+0与-0之分。 从+128到-128，数字是从大到小排列的。只有移码能直接反映出这一大小关系。因而移码能像无符号数一样直接进行大小比较。,2.2.2 机器数的浮点与定点表示 1.机器数的浮点表示法

15、一个十进制数可以表示为： N13.141590.3141591010.0314159102 同样，一个二进制数可以表示为： N20.011B0.110B2-10.0011B21 一般地说，一个任意二进制数N可以表示为： N2EM 式中： E数N的阶码； M数N的有效数字，称为尾数。,当E变化时，数N的尾数M中的小数点位置也随之向左或向右浮动。因此将这种表示法称为数的浮点表示法。 在计算机中浮点数用约定的4部分表示， Ef 阶码的符号位 S 尾数的符号位 E 阶码 M 尾数 不同的机器的字长不同，采用浮点表示法时，要预先对上述 4部分所占的二进制位数加以约定，机器才可以自动识别。 尾数的位数决定

16、数的精度,阶码的位数决定数的范围,2.尾数的规格化处理 浮点数的尾数一般为纯小数。在浮点机中常采用规格化表示的浮点数，按国际电子电气工程师协会规定的标准，浮点数的尾数要用原码表示，当尾数不为0时小数点右边第一位必须为1 即（.1000 ）才能满足浮点数规格化表示的要求；否则应修改阶码。使非规格化尾数变为规格化数的过程，称为尾数的规格化处理。 对二进制而言，小数点向左移一位，相当与尾数的数码向右移一位，（除以2），为保持数的大小不变，阶码加1（乘以2）。,3.机器数的定点表示法,2.2.3 十进制数的二进制编码 1.BCD码 （BCD）码也称为二进制编码形式的十进制数，用来解决二进制数表示十进制

17、数问题。即用4位二进制数来表示一位十进制数，这种编码形式可以有多种，有8421码, 5421码, 余3码等，其中最自然、最简单的一种方式为 8-4-2-1码，也称压缩的BCD码。即这4位二进制数的权，从左往右分别为8，4，2， 1。例如：,2.8421码BCD码的特点： 在这种编码方式中每一位二值代码的1都代表一个固定数值， 把每一位的1代表的十进制数加起来，得到的结果就是它所代表的十进制数。由于代码中从左到右每一位的1分别表示8、4、2、1，所以把这种代码叫做8421码。,例： 3579 D? BCD 解： 3 5 7 9 0011 0101 0111 1001 所以 3579D 0011

18、0101 0111 1001 BCD,3.压缩BCD码和非压缩BCD码 相对于压缩的BCD码，把用8位二进制数表示的一位十进制数的编码称为非压缩的BCD码，这时高4位无意义，低4位是一个BCD码。,4.格雷码(循环码) 下表列出了一种典型格雷码,它的主要特点是相邻的两个代码之间仅有一位的状态不同。,表： 几种常见的BCD代码,小结,机器数的原码、反码和补码表示 定点数和浮点数、规格化浮点数 BCD码,2.3 字符数据的0、1编码 2.3.1ASCII码 2.3.2汉字的编码,2.3.1 ASCII码,ASCII码是美国信息交换标准代码( American Standard Code for I

19、nformation Interchange ) 包括09十个数字，大小写英文字母及专用符号等95种可打印字符和33种控制符。它用8位来表示字符代码。其基本代码占7位，第8位用作奇偶校验位， 表中 ENQ（查询）、ACK（肯定回答）、NAK（否定回答）等，是专门用于串行通信的控制字符。,在码表中查找一个字符所对应的ASCII码的方法是：向上找b6b5b4向左找b3b2b1b0。例如，字母J的ASCII码中的b6b5b4为100B(5H)，b3b2b1b0为1010B(AH)。因此，J的 ASCII码为1001010B(5AH)。 COMPUTER的ASCII码,1.汉字信息的数字化,2.3.2

20、汉字的编码,2.汉字的编码类型: 汉字输入码 汉字交换码 汉字内码 汉字字形码,3.汉字的输入码汉字外码 为了能使用标准的西文键盘将汉字输入到计算机内，用字母数字代替汉字的编码方式。 数字编码（顺序码）如：按排列顺序形成的汉字编码区位码、电报码 字音编码（音 码）按读音规则形成的汉字编码（音码），如：拼音码、自然码 字形编码（形 码）按字形形成的汉字编码如：五笔字型码、表形码，郑码等； 音形编码 （按音、形结合形成的汉字编码（音形码），如 自然码、智能ABC，双拼码,4.汉字交换码,汉字交换码是汉字信息处理系统之间或通信系统之间传输信息时所使用的编码，即国标码。,国标码：国家标准信息交换用汉字

21、编码（GB2312-80）。国标码采用双字节的编码方式，每个字节的最高位为0。,国标码 收入6763个汉字，其中常用的一级汉字3755个，按汉语拼音字母顺序排列；二级汉字3008个，按偏旁部首顺序排列。另外还有682个西文字符、图符，共7445个字符，构成9494的矩阵，即排列成94行94列，形成汉字编码表。每一行为“区”，每一列为“位”，这就是国标区位码,5.汉字机内码 机内码：是设备和汉字信息处理系统内部存储、处理、传输汉字而使用的编码。机内码：最高位为1,6.汉字字形码 字形码：用于显示或打印汉字时产生字型，是通过点阵形式产生的。常用的字形点阵有： 1616、2424、3232、4848

22、,汉字字模的原理与西文字符的字模基本相同，只是由于汉字笔画复杂，为了表达清晰，要比西文字符须要更多的点阵。,图：一个2424点阵的汉字字模示例,6.汉字系统的工作过程, 用一种输入方法从键盘输入汉字。 键盘管理程序按照码表将外码变换成机内码。 机内码经字库模检索程序查对应的点阵信息在字模库的地址，从字库取出字模。 字模送显示驱动程序，产生显示控制信号。 显示器按照字模点阵将汉字字形在屏幕上显示出来。,2.4图像的0、1编码,2.4.1 图像类型 矢量图（vector graphice）法：用一些基本的几何元素（直线、弧线、圆、矩形等）以及填充色块等描述图像，并用一组指令表述。这种图像一般称为图

23、形或合成图像。 位图（bitmapped graphics）法：用点阵描述图像，并用一组0、1码数据描述。这种图像也称为位图。,2.4.2 图像处理过程,离散处理 采样 量化,1. 图像的离散化,离散化后的图像被看成一个由MN的像素（picture-elements，piel）点阵组成的图。每个像点都是一个单色的小方块，放大了就是马赛克。图像中像素点的密度称为图像分辨率（image resolution），单位为dpi（dots per inch，每英寸像点数）。,2. 采样与量化,采样（sampling）就是在每个小块中取它的颜色参数，将它的颜色进行分解，计算出红、黄、蓝（R、G、B）三种基

24、色分量的亮度值。将每个采样点的每个分量进行0、1编码，就称为量化。,3.颜色深度 表示一个像素点颜色的二进制位数叫颜色深度。 目前，像素深度有如下一些标准类型： 黑白图（Black 1111与0000的码距为4。 一个编码系统的码距就是整个编码系统中任意(所有)两个码字的最小距离。 例如：一个编码系统有四种编码分别为：0000，0011，1100， 1111，此编码系统中0000与1111的码距为4;0000与0011的码距为2，是此编码系统的最小码距。因此该编码系统的码距为2。,3.码距和检错纠错的关联 假如我们现在要对A，B两个字母进行编码。我们可以选用不同长度的编码，以产生不同码距的编码

25、，分析它们的检错纠错能力。 方案l ：用1位长度的二进制编码。A=1，B=0。这样A， B之间的最小码距为1。 合法码：0,1; 非法码： ; 此编码无检错纠错能力。因为这种编码无论由1错为0，或由0错为1，接收端都无法判断是否有错，因为1，0都是合法的编码。,方案2：用2位长度的二进制编码，可选用11，00作为合法编码，也可以选用01，10作为合法编码。若以A=11，B=00为例，A、B之间的最小码距为2。 合法码：11,00;非法码：01,10; 特点： 可以检测出1位错：因为无论A(11)或B(00)，如果发生一位错码，必将变成01或10，这都禁用码组(非法码)，故接收端可以判断为误码。

26、 无法纠错：因为无法判断误码(01或10)是A(00)错误还是B(11)错误造成，即无法判断原信息是A或B，或说A与B形成误码(01或10)的可能 性(概率)是相同的。 不能发现两位错误：如果产生二位错码，即00错为11，或11错为00，结果将从一个合法编变成另一个合法编码，接收端就无法判断其是否有错。 所以此种 编码的检错能力为1位，纠错能力为0位。,结论： 编码信息纠错和检错能力与编码系统的码距有关，增大码距纠错和检错能力提高，在原有数据信息中增加冗余信息可以增加码距。（编码由一位变成两位可以增加码距） 在编码理论中有如下结论： （1）在一个码组内为了检测e个误码，要求最小码距应该满足：

27、d=e+1 （2）在一个码组内为了纠正t个误码，要求最小码距应该满足： d=2t+1,下表概括了最小距离为1至7的码的纠错和检错能力。,2.7.3常用差错控制编码,1.奇偶校验码 每传送一个信息码组，都要传送一位附加的冗余校验位；该校验位可以作为码字的最高位，也可以作为码字的最低位，使得整个字符码组中1或0的数目为奇数或偶数。对于奇校验，1(或0)的数目为奇数为合法码；为偶数，便是非法码。对于偶校验，1(或0)的数目为偶数为合法码；为奇数，便是非法码。 由此，可以设计出校验逻辑： P= C7 C6 C5 C4 C3 C2 C1 C0P （ P为校验位值） P=0，无错；P=1，有错。 这种校验

28、方法能检测出传输中任意奇数个错误，但不能检测出偶数个错误。,2. 海明码 关于海明码的经典说法，即码距为3，可以发现2位，或者纠正1位错。 （1）基本思想：在k位信息位中为，增加r位冗余位，构成一个n=k+r位的码字，附加的r位冗余位被编在传输码字的特定位置上，将数据代码的码距均匀地拉大，每一个这种冗余位对码字中的若干位进行奇偶校验，并且数据的每一二进制位分配在几个奇偶校验组中，这样当某一位出错后，会引起几个校验位的值的变化。这样，不但能够检测出错误，而且能够为进一步纠错提供依据。,（2）编码规律： 若编成的海明码为HmHm-1H2H1，则海明码的编码规律为： （a)冗余位数：假设校验位的位数

29、为r位，则它共有2r个状态，用其中一个状态指出“有无错”，其余的2r-1个状态便可用于错误定位（指出是哪一位错） 。设有效信息码组为k位，并考虑到错误也可能发生在校验位，则须定位状态共有k+r个。也就是说，要能充分地进行错误定位，应有关系： 2r-1k+r 例如：一个字节的数据需要4个校验位,(b) 校验位分布位置： 在m位的海明码中，各校验位分布在位号为2i-1的位置，即校验位的位置分别为1,2,4,8,，其余为数据位。数据位按原来的顺序关系排列。如有效信息码为D5D4D3D2D1，则编成的海明码为D5P4D4D3D2P3D1P2P1，其中Pi为第 i个校验位。,(c) 校验关系： 海明码的

30、每一位Hi要被多个校验位校验。关系如下：被校验位的位号为校验位的位号之和。如D1(位号为3)要由P2与P1两个校验位校验，D2(位号为5)要由P3(位号为4)与P1两个校验位校验，D3(位号为6)要由P2与P3两个校验位校验，D4(位号为7)要由P1、P2、P3三个校验位校验，。 也就是说：每个校验位对海明码中的部分数据位（包括校验位本身）进行奇偶校验。校验位所在位置决定了它要校验和跳过的比特位顺序。具体关系如下：,位置1：校验1位，跳过1位，校验1位，跳过1位 (需要校验1,3,5,7,9,11,13,15,位) 位置2：校验2位，跳过2位，校验2位，跳过2位 (2,3,6,7,10,11,

31、14,15,) 位置4：校验4位，跳过4位，校验4位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,) 位置8：校验8位，跳过8位，校验8位，跳过8位 (8-15,24-31,40-47,) ,（d）校验位的取值： 如进行偶校验则如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.,例：一个字节的数据：10011010 构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 计算每个校验位的奇偶性 ( ?代表要设置的比特位): 位置1检查1,3,5,7,9,11: ?

32、 _ 1 _ 0 0 1 _ 1 0 1 0. 偶数个1，因此位置1设为0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0 位置2检查2,3,6,7,10,11: 0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1，因此位置2设为1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0 位置4检查4,5,6,7,12: 0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1，因此位置4设为1，即: 0 1 1 1 0 0 1 _ 1 0 1 0 位置8检查8,9,10,11,12: 0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1，因此位置8设为0，即: 0 1 1 1 0 0 1 0 1 0 1 0 因此码字为: 011100101010.,3. 循环冗余校验码（CRC） （1）循 环冗余校验的基本原理： 发送方 在N位信息码后再拼接K位的校验码（CRC） 。接受方将受到的信息码用同一个生成多项是去除，合法的循环冗余校验码应当能被生成多项式