数制与进位记数法

1、1数制与进位记数法数制与进位记数法基基 r 数制的概念数制的概念 只用只用 r 个基本符号个基本符号 ( 例如例如 0,1,2,r-1 ) 通过排通过排列起来的符号串表示数值，列起来的符号串表示数值，r 称为该数制的称为该数制的基基。数值数值 N 的表示的表示 N = Dm-1Dm-2 D1 D0D-1D-2 D-k有有 权权 的的基基 r 数制数制 每个每个Di（-kim-1）的单位值都赋以固定的值）的单位值都赋以固定的值Wi，则称，则称 Wi 为该位的为该位的 权权 。 N 代表的实际值可表示为代表的实际值可表示为： imkiiWDN12数制与进位记数法数制与进位记数法若逢若逢 r 进位，

2、有进位，有 Wi = ri ，则，则N 代表一个数值代表一个数值 r 是这个数制的基是这个数制的基 i 表示这些符号排列的位号表示这些符号排列的位号Di 是位序号为是位序号为 i 的位上的一个符号的位上的一个符号ri 是位序号为是位序号为 i 的位上的一个的位上的一个 1 代表的值代表的值Di ri 是第是第 i 位的符号所代表的实际值位的符号所代表的实际值 表示表示 对对 m+k 位的值求累加和位的值求累加和称此数制为称此数制为 r 进位数制，简称进位数制，简称 r 进制。最常用的有进制。最常用的有二进制二进制、八进制八进制、十六进制十六进制 和和 十进制十进制 这这4种。种。imkiirD

3、N1ri3数制与进位记数法数制与进位记数法计算机中常用的计算机中常用的 4 种进位数制种进位数制 二进制：二进制：r = 2， 基本符号：基本符号：0 1 八进制：八进制：r = 8， 基本符号：基本符号：0 1 2 3 4 5 6 7 十进制：十进制：r = 10，基本符号：，基本符号：0 1 2 3 4 5 6 7 8 9 十六进制：十六进制：r = 16，基本符号：，基本符号： 0 1 2 3 4 5 6 7 8 9 A B C D E F其中其中 AF 表示十进制数表示十进制数 1015 4 种进位数制之间的关系种进位数制之间的关系: 二进制二进制用于计算机内部用于计算机内部,八八和和

4、十六进制十六进制是二进制的缩写是二进制的缩写, 十进制十进制用于人员。用于人员。4二进制数二进制数八、十六八、十六和和十进制十进制 把把二进制数二进制数转换为转换为十进制数十进制数， 累加二进制数中累加二进制数中全部数值为全部数值为 1 的那些位的位权的那些位的位权 (1101.1100)2=(123+122+021+120)10 + (12-1+12-2+02-3+02-4)10 = (13.75)10 把把二进制数二进制数转换成转换成八八或或十六进制数十六进制数时，从小数点时，从小数点向左和向右把每向左和向右把每 3 或者或者 4 个二进制位分成一组，直接个二进制位分成一组，直接写出每一组

5、所代表的数值，写出每一组所代表的数值，小数点后不足位数补小数点后不足位数补0。 (1101.1001)2 = (D.9)16 = (15.44)8 ，而不是而不是(15.41)8 5数制与进位记数法数制与进位记数法二进位数和十进制数之间的转换方法二进位数和十进制数之间的转换方法 二进制：二进制：r = 2， 基本符号：基本符号：0 1 十进制：十进制：r = 10，基本符号：，基本符号：0 1 2 3 4 5 6 7 8 9 求二进制数所对应的十进制数值，可通过进位记求二进制数所对应的十进制数值，可通过进位记数公式来计算，即把取值为数公式来计算，即把取值为 1 的数位的位权累加。的数位的位权累

6、加。 把十进制数转换为二进制，把十进制数转换为二进制，对整数部分通过除对整数部分通过除 2取余数来完成取余数来完成，对小数部分通过乘对小数部分通过乘 2 取整数来完成取整数来完成。 2 13-1 低位低位 0.762 2 6-0 1 0.522 高位高位 2 3-1 1 0.042 2 1-1 高位高位 0 0.082 0 0 0.16 低位低位 (13)10 = (1101)2 (0.76)10 = (0.1100)26数值范围和数据精度数值范围和数据精度数值范围数值范围 数值范围是指一种类型的数据所能表示的最大值和最数值范围是指一种类型的数据所能表示的最大值和最小值；小值；数据精度数据精度

7、 通常指实数所能给出的有效数字位数；对浮点数来说，通常指实数所能给出的有效数字位数；对浮点数来说，精度不够会造成误差，误差大量积累会出问题。精度不够会造成误差，误差大量积累会出问题。机内处理机内处理 数值范围与数据精度概念不同。在计算机中，它们的数值范围与数据精度概念不同。在计算机中，它们的值与用多少个二进制位表示某种类型的数据，以及怎值与用多少个二进制位表示某种类型的数据，以及怎么对这些位进行编码有关。么对这些位进行编码有关。7数值数据在计算机内的格式数值数据在计算机内的格式定点小数定点小数: N = N N N .Ns-1-n-2整整 数数: N = N N . N N01sn-1浮点数浮

8、点数: N = M E E .E E M M .M ssm-110-1-2-n符号位符号位 阶码位阶码位 尾数数码位尾数数码位 总位数总位数 短浮点数短浮点数: 1 8 23 32长浮点数长浮点数: 1 11 52 64 临时浮点数临时浮点数: 1 15 64 80IEEE 标准：标准： 阶码用移码阶码用移码 尾数用原码尾数用原码 基为基为 283、数值数据的编码和运算算法、数值数据的编码和运算算法二进制数值数据的类型二进制数值数据的类型 二进制表示的二进制表示的定点小数定点小数、整数整数和和浮点数浮点数数值数据编码目标数值数据编码目标 能方便统一地表示正数、零和负数，并且尽可能方便统一地表示

9、正数、零和负数，并且尽可能有利于简化对它们实现算术运算用到的规则；能有利于简化对它们实现算术运算用到的规则； 数据符号的正与负，可用一位二进制的数据符号的正与负，可用一位二进制的 0 和和 1两个状态加以表示，数据数值用多位二进制表示。两个状态加以表示，数据数值用多位二进制表示。常用的编码方案常用的编码方案 原码原码表示、表示、补码补码表示、表示、反码反码表示表示9+ 0.1011+ 1100 1100 0.1011带符号的数带符号的数 符号数字化的数符号数字化的数真值真值 机器数机器数机器数与真值机器数与真值 0 1011 1 1011 0 1100 1 1100小数点的位置小数点的位置 一

10、个数据的实际值被称为数的真值，机器数是一个数据的实际值被称为数的真值，机器数是指对数据符号位完成数字化处理后的机内表示。指对数据符号位完成数字化处理后的机内表示。10 X = X = X =定点小数表示定点小数表示: Ns N1 N2 Nn原原 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(纯小数纯小数) 原码，反码，补码的定义原码，反码，补码的定义11实例：实例： X1 = 0.1011 -0.1011 0.0000 X 补补 = 0 1011 1 0101 0

11、 0000说明：说明：补码补码最高一位是符号位，符号最高一位是符号位，符号 0 正正 1 负负 补码补码表示为：表示为：2符号位符号位 + 数的真值数的真值 补码补码零只有一个编码，故能表示零只有一个编码，故能表示 -1 补码补码能很好地用于加减（乘除）运算能很好地用于加减（乘除）运算定点小数表示定点小数表示: Ns N1 N2 Nn X 2 + X -1 X 00 X 1(纯小数纯小数) 补码的定义与说明补码的定义与说明定义：定义： X 补补 =MOD 212整数的编码表示整数的编码表示整数的整数的 原码原码 反码反码 补码补码 表示表示与小数的三种表示基本相同与小数的三种表示基本相同差别仅

12、表现在小数点的位置差别仅表现在小数点的位置可以认为整数的小数点在最低数值位的右侧可以认为整数的小数点在最低数值位的右侧因此整数的模与整数位数有关因此整数的模与整数位数有关讲课中不大用整数讲讲课中不大用整数讲 原原 反反 补补 码定义码定义 例如：整数六位编码例如：整数六位编码 ( 1 位符号位，位符号位，5 位数值位位数值位) X = +01110 X原原= 0 01110 X补补= 0 01110 X = - 01110 X原原= 1 01110 X补补= 1 1001013x 为真值为真值n 为整数的位数为整数的位数x原原 = x 2n x 02n x 0 x 2nx补补 = x 2n x

13、 02n+1 + x 0 x 2n（mod 2n+1）x反反 = x 2n x 0( 2n+1 1) + x 0 x 2n（mod 2n+1 1）整数的编码表示整数的编码表示14原原 反反 补码表示小结补码表示小结正数的正数的 原码原码、反码反码、补码补码表示均相同表示均相同，符号位为符号位为 0，数值位同数的真值。，数值位同数的真值。零的零的原码原码和和反码反码均有均有 2个编码，个编码，补码补码只只 1个码个码负数的负数的 原码原码、反码反码、补码补码表示均不同表示均不同，符号位为符号位为 1，数值位：原码为数的绝对值，数值位：原码为数的绝对值 反码为每一位均取反码反码为每一位均取反码 补

14、码为反码再在最低位补码为反码再在最低位+1由由 X补补 求求 -X补补：每一位取反后再在最低位：每一位取反后再在最低位+115补码表示中的符号位扩展补码表示中的符号位扩展由由 X补补 求求 X / 2补补 的方法的方法 原符号位不变，且符号位与数值位均右移一位原符号位不变，且符号位与数值位均右移一位例如，例如， X补补 =10010 则则 X/2补补 =11001不同位数的整数补码相加减时，不同位数的整数补码相加减时， 位数少的补码数的符号位向左扩展，位数少的补码数的符号位向左扩展， 一直扩展到与另一数的符号位对齐。一直扩展到与另一数的符号位对齐。 0101010111000011 01010

15、10111000011 + 10011100 + 00011100 0101010101011111 0101010111011111 000000001111111116补码的一些补充说明补码的一些补充说明由由X补补（X0 X1X2Xn）求真值）求真值 XX补补 = 2X0 + X X = X补补 - 2X0 = X0 X1X2Xn - 2X0 = -X0 + (-X0+ X0 X-1X-2X-n) = -X0 + 0.X1X2Xn由由 X补补 求求 X/2补补的关系的关系 X补补 = X0 X1X2XnX/2补补 = X0 X0X1X2Xn174、检错纠错码、检错纠错码 要提高计算机的要提

16、高计算机的可靠性可靠性，除了采取选用更高可，除了采取选用更高可靠性的器件，更好的生产工艺等措施之外，还可以靠性的器件，更好的生产工艺等措施之外，还可以针对薄弱环节，从数据编码上想一些办法，即采用针对薄弱环节，从数据编码上想一些办法，即采用少量冗余的线路，在原有数据位之外再少量冗余的线路，在原有数据位之外再增加一到几增加一到几个校验位个校验位，使新得到的使新得到的由数据位和校验位构成的码由数据位和校验位构成的码字字带上某种特性带上某种特性，在经过薄弱环节之后，则通过，在经过薄弱环节之后，则通过检检查该码字是否仍保持有这一特性查该码字是否仍保持有这一特性，来，来判断判断码字中的码字中的某一、二位的

17、值是否发生了变化某一、二位的值是否发生了变化，即是否出现了错，即是否出现了错误，甚至于定位错误后，误，甚至于定位错误后，自动改正自动改正这一错误，这就这一错误，这就是我们这里说的是我们这里说的检错纠错编码技术检错纠错编码技术。18检错纠错码检错纠错码 码距（最小码距）的概念码距（最小码距）的概念：是指任意两个合法码：是指任意两个合法码之间至少有几个二进制位不相同之间至少有几个二进制位不相同。例如：。例如： 仅有一位不同，称最小码距为仅有一位不同，称最小码距为 1，例如用，例如用 4 位二进制表示位二进制表示16 种状态，则种状态，则 16 种编码都用到了，此时种编码都用到了，此时码距为码距为

18、1，就是说，就是说，任何一个编码状态的四位码中的一位或几位出错，都会变成另任何一个编码状态的四位码中的一位或几位出错，都会变成另一个合法码，此时一个合法码，此时无检错能力无检错能力。 若用若用 4 个二进制位表示个二进制位表示 8 种合法状态，就可以只用其中的种合法状态，就可以只用其中的 8 个编码来表示之，而把另个编码来表示之，而把另 8 种编码作为非法编码，此时可以种编码作为非法编码，此时可以使合法码的使合法码的码距为码距为 2。如果如果一个码字中的任何一位出错后都会一个码字中的任何一位出错后都会成为非法码，则它就成为非法码，则它就有了发现一位出错的能力有了发现一位出错的能力。 合理增大码

19、距，能提高发现错误的能力，但表示合理增大码距，能提高发现错误的能力，但表示一定数量的合法码所使用的二进制位数要变多，增加一定数量的合法码所使用的二进制位数要变多，增加了电子线路的复杂性和数据存储、数据传送的数量。了电子线路的复杂性和数据存储、数据传送的数量。19非线性码非线性码线性码线性码卷积码卷积码分组码分组码非循环码非循环码循环码循环码随机随机 错误错误 突发突发 错误错误纠错码纠错码校验位与信息位校验位与信息位 的形成关系的形成关系信息位与校验位信息位与校验位 的约束条件的约束条件码字本身的码字本身的 结构特点结构特点信息位与校验位排列位置关系信息位与校验位排列位置关系系统码系统码非系统

20、码非系统码纠错码分类纠错码分类20几种常用的检错纠错码几种常用的检错纠错码我们只介绍三种常用的检错纠错码：我们只介绍三种常用的检错纠错码：奇偶校验码奇偶校验码：用于：用于并行并行数据传送中数据传送中海明校验码海明校验码：用于：用于并行并行数据传送中数据传送中循环冗余校验码循环冗余校验码：用于：用于串行串行数据传送中数据传送中编码过程编码过程原始数据原始数据形成校验位的值形成校验位的值加进特征加进特征译码过程译码过程结果数据结果数据检查收到的码字检查收到的码字发现发现 / / 改正错误改正错误运行过程运行过程的的 3 步曲：步曲：传送传送码码 字字薄弱环节薄弱环节21用于并行码用于并行码检错检错

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

22、 D6 D5 D4 D3 D2 D1 D0+编码电路编码电路八位数据位八位数据位p23海明校验码海明校验码用于多位并行数据用于多位并行数据检错纠错检错纠错处理处理实现：为实现：为 k 个数据位设立个数据位设立 r 个校验位，使个校验位，使 k+r 位位 的码字同时具有这样两个特性：的码字同时具有这样两个特性：能发现并改正能发现并改正 k+r 位中任何一位出错；位中任何一位出错；能发现能发现 k+r 位中任何二位同时出错，位中任何二位同时出错， 但已无法改正但已无法改正。 k k 与与 r r 之间应该满足之间应该满足什么样的关系什么样的关系 ？24海明码的编码方法海明码的编码方法 合理地用合理

23、地用 k 位数据位形成位数据位形成 r 个校验位的值，即保个校验位的值，即保证用证用 k 个数据位中个数据位中不同的数据位组合不同的数据位组合来形成每个校验来形成每个校验位的值，使位的值，使任何一个数据位出错任何一个数据位出错时，将影响时，将影响 r 个校验个校验位中位中不同的校验位组合不同的校验位组合起变化。这样一来，就可以通起变化。这样一来，就可以通过检查是过检查是哪种校验位组合起了变化哪种校验位组合起了变化，来推断是哪个数，来推断是哪个数据位错造成的，据位错造成的，对该位求反则实现纠错对该位求反则实现纠错。 有时两位出错与某种情况的一位出错对校验位组有时两位出错与某种情况的一位出错对校验

24、位组合的影响相同，合的影响相同，必须加以区分与解决必须加以区分与解决。 位数位数 r 和和 k 的关系：的关系： 2r k+r+1, 即用即用 2r 个编码个编码分别表示分别表示 k个数据位、个数据位、r个校验位中哪一位错，个校验位中哪一位错，都不错都不错 2r-1 k+r ，用，用 r-1 位校验码为出错位编码，再单位校验码为出错位编码，再单独设一位用于区分独设一位用于区分 1 位还是位还是 2 位位同时出错，同时出错，更实用更实用25P1 = D2 D1P2 = D3 D1P3 = D3 D2海明码的实现方案海明码的实现方案 例如例如: k =3, r =4D3 D2 D1 P4 P3 P

25、2 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 表示异或表示异或编码方案编码方案译码方案译码方案26（一）准备工作：（一）准备工作： (1) (1) 按次序排列数据位、校验位，按次序排列数据位、校验位， (2) (2) 分别在不同横行中的分别在不同横行中的P1P1、P2P2、P3P3、P4P4各列写各列写 1, 1, (3) (3) 在在 P1 P2

26、 P3 P1 P2 P3 各列低各列低 3 3 横行中的其他位置填写横行中的其他位置填写 0, 0, (4) (4) 在最顶横行其他各列填写在最顶横行其他各列填写 1 1；海明码的实现方案海明码的实现方案 例如：例如： k =3, r =4如何通过一张表分配不同的数据位组合来形成每个校验位的值如何通过一张表分配不同的数据位组合来形成每个校验位的值D3 D2 D1 P4 P3 P2 P1 编码方案编码方案D3 D2 D1 P4 P3 P2 P1 1 0 1 0 0 0 0 1 0 0 0 0 11 1 1 1D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0

27、 0 1 0 0 0 0 127（二）为各校验位分配数据位组合：（二）为各校验位分配数据位组合： (1) (1) 看表的低看表的低 3 3 横行右侧横行右侧 4 4 列各列的编码值分别为：列各列的编码值分别为： 1 1 (00 (001 1) )、2 2 ( 0( 01 10) 0) 、4 4 ( (1 100) 00) 、0 0 (000)(000) (2) (2) 为为低低 3 3 横行左侧横行左侧 3 3 列各列填写合理的编码值，其列各列填写合理的编码值，其 规则是，使用没出现在右侧规则是，使用没出现在右侧 4 4 列的最小正整数值列的最小正整数值 即即 3 (011)3 (011)、5

28、 (101)5 (101)、6 (110)6 (110)。海明码的实现方案海明码的实现方案 例如：例如： k =3, r =4如何通过一张表分配不同的数据位组合来形成每个校验位的值如何通过一张表分配不同的数据位组合来形成每个校验位的值编码方案编码方案011D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 10111100 4 2 16 5 3 28（三）写出各校验位的编码逻辑表达式：（三）写出各校验位的编码逻辑表达式： (1) (1) 用用 P1P1、P2P2、P3 P3 取值为取值为 1 1 的横行中那些取值为的横行中那些取值为

29、 1 1 的的 数据位进行数据位进行异或运算异或运算求得每个校验位的值求得每个校验位的值; ; 结果是结果是: : P1 = D2 P1 = D2 D1D1； P2 = D3 P2 = D3 D1D1； P3 = D3 P3 = D3 D2D2 (2) (2) 用其他各校验位及各数据位用其他各校验位及各数据位进行进行异或运算异或运算求校验求校验位位 P4 P4 的值，的值，用于区分无错、奇数位错、偶数位错用于区分无错、奇数位错、偶数位错 3 3 种情况种情况 总校验位总校验位 P4 = P3 P4 = P3 P2 P2 P1 P1 D3 D3 D2 D2 D1 D1 海明码的实现方案海明码的实

30、现方案 例如：例如： k =3, r =4如何通过一张表分配不同的数据位组合来形成每个校验位的值如何通过一张表分配不同的数据位组合来形成每个校验位的值编码方案编码方案011D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 101111029P1 = D2 D1P2 = D3 D1P3 = D3 D2海明码的实现方案海明码的实现方案 例如：例如： k =3, r =4 设计结果为：设计结果为：D3 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

31、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 ：异或：异或编码方案编码方案译码方案译码方案 译码方案是：译码方案是： 对接收到数据位再次编码，用得对接收到数据位再次编码，用得到的结果和到的结果和传送过来的校验位传送过来的校验位的值相的值相比较，结果分别用比较，结果分别用 S4S1 表示，二者表示，二者相同表明无错，不同是有相同表明无错，不同是有 1 位错了。位错了。 排查是哪一位错了，看排查是哪一位错了，看 S4S1 这这4 位的编码值。位的编码值。30海明码的应用实例海明码的应用实例若无错，则若无错，则S4 S3 S2 S1=0000 4 位位 S 全为全为 0如已有数据为如已有数据为 110110，则有：，则有： P1=1P1=1，P2=1 P3=0P2=1