《数据表示与运算算法和逻辑电路实现》由会员分享，可在线阅读，更多相关《数据表示与运算算法和逻辑电路实现（82页珍藏版）》请在金锄头文库上搜索。
1、第3章数据表示、数据运算算法 和逻辑电路实现本章主要内容w信息编码、码制转换与检错纠错码w数据表示常用的信息编码w二进制数值数据的编码与运算算法数字化编码二要素数值 文字 符号 语音 图形 图像 等统称数据， 在计算机内部，都必须用数字化编码的形式 被 存储 加工 和 传送 数字化编码二要素:少量简单的基本符号 一定的组合规则 用以表示大量复杂杂多样样的信息基二码（二进制码）只使用两个基本点符号： 符号个数最少，物理上容易实现 与二值逻辑的 真 假 两个值对应简单 用二进制码表示数值数据运算规则简 单进位记数法与进制转换进位记数法 N= i=m-1Di*ir-kN 代表一个数值 r 是这个数制
2、的基(Radix) i表示这些符号排列的位号 Di是位号为i的位上的一个符号ri是位号为i的位上的一个 1 代表的值irDi*是第i位的所代表的实际值 表示m+k位的值求累加和十进制转二进制整数部分除2取余 小数部分乘2取整2 1 122 252 1 011 0 10.625 * 210.25 * 200.5 * 2 10.0 除尽为止 求得位数满足要求为止低高高低从二进制数求其十进制的值，逐位码权累加求和二到八或十六进制转换二到八 从小数点向左右三位一分组 （10 011 100 . 01)2 = ( 234 . 2 )8010 二到十六 从小数点向左右四位一分组 （1001 1100 .
3、01)2 = ( 9C . 4 )160100 说明：整数部分不足位数对转换无影响 ， 小数部分不足位数要补零凑足,否则出错。二进制数据算术运算规则(1) 加法运算规则0+0=0 例如： 01010+1=1 +) 00011+0=1 01101+1=0 并产生进位 (2) 减法运算规则0-0=0 例如： 1011 0-1=1 并产生借位 -) 01011-0=1 01101-1=0二进制数据算术运算规则乘法运算规则 例如： 11010X0=0 X) 01010X1=0 11011X0=0 11011X1=1 1000001 除法运算规则1101 例如： 1110101/1001 1001 11
4、101011001101110010100110010 0000检错纠错码为了提高计算机的可靠性，除了采 取选用更高可靠性的器件，更好的生产工 艺等措施之外，还可以从数据编码上想一 些办法，即采用一点冗余的线路，在原有 数据位之外再增加一到几位校验位，使新 得到的码字带上某种特性，之后则通过检 查该码字是否仍保持有这一特性，来发现 是否出现了错误，甚至于定位错误后，自 动改正这一错误，这就是我们这里说的检 错纠错编码技术。非线性码线性码卷积码分组码非循环码循环码随机错误 突发错误纠错码校验位与信息位的形成关系信息位与校验位的约束条件码字本身的结构特点信息位与校验位排列位置关系系统码非系统码纠错
5、码分类几种常用的检错纠错码我们只介绍三种常用的检错纠错码： 奇偶检错码， 用于并行数据传送中 海明检错与纠错码，用于并行数据传送中 循环冗余码， 用于串行数据传送中编码过程译码过程传送原始数据码 字结果数据形成校验位的值 ，加进特征检查接送的码字， 发现 / 改正错误奇偶校验码偶校验奇校验校验位用于并行码检错 原理：在 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 原有数字位 两个新的码字 奇偶
6、校验码的实现电路+奇较验 偶校验 出错指示+同左侧电路编码电路译码电路P (校验位)八位数据位D7 D6 D5 D4 D3 D2 D1 D0p海明校验码用于多位并行数据检错纠错处理 实现：为 k 个数据位设立 r 个校验位， 使 k+r 位的码字同时具有如下两个特性：能发现并改正 k+r 位中任何一位出错， 能 发 现 k+r 位中任何二位同时出错，但 已无法改正。海明码的编码方法合理地用 k 位数据位形成 r 个校验位的值， 即保证用 k 个数据位中不同的数据位组合来 形成每个校验位的值，使任何一个数据位出 错时，将影响 r 个校验位中不同的校验位组 合起变化。换言之，通过检查是哪种校验位
7、组合起了变化，就能确定是哪个数据位错， 对该位求反则实现纠错。 有时两位错与某种情况的一位错对校验位组 合的影响相同，必须加以区分与解决。P1 = D2 + D1 P2 = D3 + D1 P3 = D3 + D2海明码的实现方案 例如： k =3, r =4D3 D2 D1 P4 P3 P2 P1 X X X P4 = P3 + P2 + P1 + D3 + D2 + D1S1 = P1 + D2 + D1 S2 = P2 + D3 + D1 S3 = P3 + D3 + D2 S4 = P4 + P3 + P2 + P1 + D3 + D2 + D1+ ：异或编码方案译码方案海明码的实现方
8、案 例如： k =3, r =4D3 D2 D1 P4 P3 P2 P11 1 1 1 0 0 0 S1 = P1 + D2 + D1 S2 = P2 + D3 + D1 S3 = P3 + D3 + D2 S4 = P4 + P3 + P2 + P1 + D3 + D2 + D1译码方案S4 S3 S2 S1 值0 0 0 0 01 1 1 0 61 1 0 1 51 0 1 1 31 0 0 0 01 1 0 0 41 0 1 0 21 0 0 1 10 1 1 1 0 0 01 0 1 1 0 0 01 1 0 1 0 0 01 1 1 0 0 0 01 1 1 1 1 0 01 1 1
9、 1 0 1 01 1 1 1 0 0 1D3 D2 P3 D1 P2 P1 P4海明校验码总结 校验码字没有出错，则4个S均为0。 任何单独一位数据位出错，4个S中会有3个 1，且S4一定为1。 若单独一位校验位出错， 4个S中会有1到2 个为1，且S4一定为1。 任何两位(包含数据位和校验位），S4一定 为0，另外3个S不全为0。 4在这里只是表示奇数位出错还是偶数位 出错，1为奇数位出错，0表示偶数位出错。检错纠错码小结(1) K位码有2K 个编码状态，全用于表示合法 码，则任何一位出错, 均会变成另一个合法码 ，不具有检错能力。 (2) 从一个合法码变成另一个合法码，只少要 改变几位码
10、的值，称为最小码距(码距)。 (3) K+1 位码，只用其 2K 个状态，可使码距 为 2 , 如果一个合法码中的一位错了，就成为 非法码，通过检查码字的合法性，就得到检错 能力，这就是奇偶校验码。检错纠错能力(4) 对 k 位数据位，当给出 r 位校验位时， 要发现并改正一位错， 须满足如下关系：2r = k + r +1 ；要发现并改正一位错，也能发现两位错,则应：2r-1 = k + r , 此时码距为 4 。(5) 若最小码距为 d (d=2), 能发现 d-1 位错，或改正 (d-2)/2 (取整) 位错, 要发现 l 位错,并改正 t 位错，应满足如下 条件:d = l + t +
11、 1 ( l = t )本章主要内容w信息编码、码制转换与检错纠错码w数据表示常用的信息编码w二进制数值数据的编码与运算算法基二码应用实例：数据表示逻辑型数据 字符型数据 ASCII 码 EBCDIC 码 字符串 汉字 检错纠错码 奇偶校验 海明校验 循环冗余校验 数值型数据 定点小数 整数 浮点数 二十进制数（BCD码） 逻辑型数据逻辑型数据只有两个值：真 和 假，正好可以用二进制码的两个符号分别表示 ， 例如 1 表示 真则 0 表示 假 不必使用另外的编码规则。 对逻辑型数据可以执行逻辑的 与 或 非等基 本逻辑运算。其规则如下：逻辑型数据基本运算规则X Y X与Y X或Y X的非0 0 0 0 10 1 0 1 11 0 0 1 01 1 1 1 0 字符型数据的表示字符作为人机联系的媒介，是最重 要的数据类型之一，当前的西文字符集由 128 个符号组成，通常用 8 位二进制编码,即用一 个字节来表示每一个符号，当前通用的两个标 准字符集是： ASCII 码： 即 American Standard Code forInformation Interchange EBCDIC码：即 Extended Binary CodedDecimal Interchage CodeASCII码字符集具体编码如下表所示： ASCII字符编码编码 集b6 b5 b4 000
