《计算机组成原理 第7讲_校验码教材》由会员分享，可在线阅读，更多相关《计算机组成原理 第7讲_校验码教材（31页珍藏版）》请在金锄头文库上搜索。
1、计算机组成原理计算机组成原理 Principles of Computer Organization 广义双语教学课程 http:/211.64.192.109/skyclass25/ 青岛理工大学 校级精品课程 1jlsheng 第3章 运算方法和运算部件 Error detection is the ability to detect the presence of errors caused by noise or other impairments during transmission from the transmitter to the receiver: Error corre
2、ction is the additional ability to reconstruct the original, error-free data. ( 6 ) 3.7 数据校验码 2jlsheng 海明校验码 Hamming Code 海明校验码是1种能检测1位或几位错误，又能自动纠正1位错误的 线性分组码。在数据中加入若干个校验位，把各个数据位分在几 个奇偶校验组中，把数据代码的码距比较均匀地拉大。任一位出 错都会引起有关的几个校验位的值发生变化，从而发现错误。 设m位校验码中数据为k位，校验位为r位。把校验码分成r组 作奇偶校验。 所产生的r位检错信息构成一个指误字，可指出2r种状
3、态。 指误字全0表示无错，其余2r1种状态能指明k+r位中的某一 位出错。即指误字应能表示k位数据哪一位出错，r个校验位哪一 位出错和无错这k+r+1种情况。 A Hamming code is a linear error-correcting code named after its inventor, Richard Hamming. Hamming codes can detect up to two simultaneous bit errors, and correct single-bit errors; 3jlsheng 若要求海明码能指出并纠正一位错，则数据位的位数k和校验
4、位的位数r应满足如下关系（海明不等式）： 2 rkr+1 此时码距为3 ，海明码中的每一信息位至少要参加两组奇 偶校验并至少影响两个校验位。 若要求海明码能检测发现2位错并能自动纠正一位错，则数据 位的位数k和校验位的位数r应满足如下关系： 2 r-1kr 满足这个不等式的海明码称为：扩展海明码 / 推广海明码 此时码距为4 ，推广海明码中的每一信息位至少要参加3组 奇偶校验并至少影响3个校验位。 (1) 校验位的位数 海明校验码 Hamming Code 4 (2) 分组原则（编码规则） 设：海明码Hm Hm-1H2 H1的最高位号为m ，最低位号 为1。 m= kr 每个校验位Pi在海明码
5、中被分配在位号2i1的位置，其余各 位为数据位，并按从低向高逐位依次排列的关系分配。 海明码的每一位码Hi由多个校验位作校验，被校验的每一位 的海明码位号等于校验它的各校验位的海明码位号之和，以便 使校验的结果能正确反映出错位的位号。 在增大合法码的码距时，尽量使所有码的码距均匀的增大， 以保证对所有码的检错能力平衡提高。 5jlsheng 例18位数据的海明码（能指出并纠正一位错）的编码和校验 编码 数据位k8，按海明不等式算出r4，m = k+r =12 各位对应关系如下： 数据位/校验位 参与校验的校 验位位号 海明码位号H12H11H10H9H8H7H6H5H4H3H2H1 D8D7D
6、6D5P4D4D3D2P3D1P2P1 4, 8 1, 2, 8 2, 8 1, 8 81, 2, 4 2, 4 1, 4 41, 2 21 按Pi的位号等于2i1的关系，校验位P1,P2,P3 ,P4对应的海明码 的位号分别为H1 ，H2，H4，H8 。 12位海明码分成4组进行偶校验。 被校验的每一位的海明码位号等于校验它的各校验位的海明 码位号之和。 2 rkr+1 各校验位与数据位的关系（本例为偶校验）为： 数据位/校验位 参与校验的校 验位位号 海明码位号H12H11H10H9H8H7H6H5H4H3H2H1 D8D7D6D5P4D4D3D2P3D1P2P1 4, 8 1, 2, 8
7、 2, 8 1, 8 81, 2, 4 2, 4 1, 4 41, 2 21 每个小组只有一个校验位。每个校验位校验其自身和45个 数据位，不参与其它校验位的校验。 每个数据位至少出现在两个Pi值的形成关系中。当任一数据 位发生变化时，必将引起二或三个Pi值跟着变化。 不同信息位出现在Pi项中的次数不同。D4和D7出现3次，而D1、D2 、D3、D5、D6、D8仅出现2次，使不同代码的海明码的码距不等。 例如，数据11010011的海明码为 001010011011海明码 P1P2D1P3D2D3D4P4D5D6D7D8 数据位/校验位 H1H2H3H4H5H6H7H8H9H10H11H12海
8、明码位号 偶校验 8jlsheng 如果要求海明码能检测发现2位错并能自动纠正一位错，则推 广海明码的校验位位数r5 。海明码的总位数m = k+r =13。 13位海明码分成4组进行偶校验。各位对应关系如下： 数据位/校验位 参与校验的 校验位位号 海明码位号 H13H12H11H10H9H8 H7H6H5H4H3H2H1 P5D8D7D6D5P4D4D3D2P3D1P2P1 134, 8 1, 2, 8 2, 8 1, 8 81, 2, 4 2, 4 1, 4 41, 2 21 增加的一个校验位P5只能在H13。 每个信息位都均匀地出现在3个Pi值的形成关系中。当任一信 息位发生变化时，必
9、将引起3个Pi值跟着变化。 2 r-1kr 或者 例如，数据11010011的推广海明码为 0010100110110 推广海明码 P1P2D1P3D2D3D4P4D5D6D7D8P5 数据位 / 校验位 H1H2H3H4H5H6H7H8H9H10H11H12H13 海明码位号 10jlsheng 校验 数据接收方按以下关系对收到的海明码进行校验（本例为 偶校验），产生指误字（Syndrome Word）： 校验得到的结果S4 S3 S2S1的值构成指误字，能反映该12位海 明码出错情况： 11jlsheng S4S3S2S1 0000，表明无错误。 S4S3S2S1中只有一位不为0，表明是某
10、一校验位出错，出错 的是该Si对应的Pi位，不需纠正。也可能是3位海明码（包括数 据位和校验位）同时出错，但无法指出是哪3位错。由于多位 代码同时出错的概率比仅一位代码出错的概率小得多，故认为 是一位错。 S4S3S2S1中有两位或三位不为0，表明是一位数据位出错， 出错位的位号由S4S1这4位的编码值指明（例如， S4S1 1011，则H11位出错），因此可将其纠正过来。或者可能是三 个校验位同时出错，但此种出错的概率极小，故认为是一位 错。 当S4S3S2S1中有4位不为0时，表明出错情况严重。 指误字（Syndrome Word） 12jlsheng D8H120011 D7H11110
11、1 D6H100101 D5H91001 P4H80001 D4H71110 D3H60110 D2H51010 P3H40010 D1H31100 P2H20100 P1H11000 0000 数据位/校验位出错位S1S2S3S4 对于推广海明码 S5S1的值构成指误字，反映该13位海明码出错情况： S5S4S3S2S1 00000，表明无错误。 S5S4S3S2S1中只有一位不为0，表明是某一校验位出错，出 错的是该Si对应的Pi位，不需纠正。也可能是3位海明码(包括 数据位和校验位)同时出错，但无法指出是哪3位错。由于多位 代码同时出错的概率比仅一位代码出错的概率小得多，故认为 是一位错
12、。 14jlsheng 对于推广海明码 S5S4S3S2S1 中有两位不为0，表明是2位海明码同时出错，但 不能确定出错位的位号。 S5S4S3S2S1中有三位不为0，表明是一位数据位出错，出错位 的位号由S4S1这4位的编码值指明（例如，S5S1 01011，则 H11位出错），因此可将其纠正过来。或者可能是三个校验位同 时出错，但此种出错的概率极小，故认为是一位错。 S5S4S3S2S1中有4位或5位不为0时，表明出错情况严重。 15jlsheng P5H1300001 D8H1200111 D7H1111010 D6H1001011 D5H910011 P4H800010 D4H7111
13、00 D3H601101 D2H510101 P3H400100 D1H311001 P2H201000 P1H110000 00000 数据位/校验位出错位S1S2S3S4S5 Homework CRCs are not, by themselves, suitable for protecting against intentional alteration of data (for example, in authentication applications for data security), because their convenient mathematical proper
14、ties make it easy to compute the CRC adjustment required to match any given change to the data. All error detection codes (which include all error-detection-and- correction codes) transmit more bits than were in the original data. An error-correcting code (ECC) or forward error correction (FEC) code
15、 is redundant data that is added to the message on the sender side. 3 - 26, 17jlsheng 测验1 请写好自己的姓名、学号、班级 18jlsheng 测验1 一. （10分） 求X补、 X/2补、 X/4补、 2X补=？ X= -43/64 二. （12分） 定点数的表示范围。 32位整数原码。 25位小数原码。 28位整数补码。 27位小数补码。 三 （16分） 定点补码加减法。求X+Y， XY X= -0.5625， Y= +39/64 请不要抄题，只写题号 19 五 （16分） 移码加减法。求X+Y， XY
16、X= -69， Y= +57 四. （8分） 求浮点数表示范围。 尾数12位原码，阶码8位补码。 写出该浮点数能表示的：最大正数，绝对值最大负数，最 小正数，绝对值最小负数。 测验1 请不要抄题，只写题号 三 （16分） 定点补码加减法。求X+Y， XY X= -0.5625， Y= +39/64 20jlsheng 五 （16分） 移码加减法。求X+Y， XY X= -69， Y= +57 六 （23分） 浮点数，尾数8位补码，阶码6位移码（ 都包括符号位）。 X= -4.75， Y= +28.75， (1) 求X和Y的规格化浮点机器数 （2）求X+Y 测验1 请不要抄题，只写题号 21jlsheng 七、 （共7分） 判断题 （请在正确的句子前写T，错误的句子前写F） 请不要抄题，只写题号
