第3讲校验码.ppt

CH 2 数据的表示-2 数据校验码 数据校验码的概念 常用数据校验码的编码方式 教学目的与要求 掌握数据校验码的概念； 理解常用校验码的检验原理和技术实现； 重点掌握编码方式。 一、概念 数据校验码：是一种常用的发现错误或自动改正错误的数据编码方式。 原理： 在合法的数据中加入（数据中不允许）的冗余码，使之成为另一种合法码； 而编码出现某些错误时，就成为非法编码；通过检测数据的合法性判断数据是否出错。 码距：指任意两个合法码之间至少应有的二进制不相同的位数。 4位二进制表示16种状态，码距为1，无查错功能。 4位二进制表示8种状态，码距为2，可以发现错误。 一、概念 通过函数f对数据进行计算，以产生一种代码，代码和数据都被存储，因此如果原来数据字长为K位，校验码长为R位，则实际存储的字长应该是R+K位。 当原先存储的字读出时，这个代码用于检错和纠错，在K位数据中产生一组新的R位代码，与取出的代码进行比较： 结果一致，无差错，取出的数据位传送出去； 检测到差错，并可以纠正，数据位和纠错位一起送入纠正器，然后产生一组正确的K位数据位； 检测到差错，但无法纠正，报告出错。 常用的数据校验码 奇偶校验码、海明校验码、循环冗余校验码。 二、 奇偶校验码 编码方法 不管数据位长度多少，校验位只有一位。 数据位和校验位一起所含“1”的个数，只能是奇数，称为奇校验。 数据位和校验位一起所含“1”的个数，只能是偶数，称为偶校验。 例：数据 奇校验的编码 偶校验的编码 0000 0000 1 0000 0000 0 0000 0000 0101 0100 0 0101 0100 1 0101 0100 0111 1111 0 0111 1111 1 0111 1111 实际存储字长（8+1=9） 校验：对奇校验，如接收端收到是偶码，表示传送有误，因此可发现一位错（奇位错）。 三、海明校验码 要检测并纠正1位错时，海明码（发送端）校验位数要满足以下不等式： 2r ≥ k+r+1 其中：k—数据位的位数；r—校验位的位数。 数据D位数k 校验P位数r 总位数m 1 2 3 2~4 3 5~7 5~11 4 9~15 12~26 5 17~31 27~57 6 33~63 58~120 7 65~127 三、海明校验码 校验位置 校验位r位用Pi表示，数据位k位用Di表示； 海明码共k+r位，用Hi表示； 海明序号：Hk+rHk+r-1 ... H3H2H1； 校验位排列在下标 2i–1 (i =1,2,…,R)的位置上，数据位按照从低到高的顺序排列在其余海明码位上。 例： 有一个BCD码 为D4D3D2D1，k=4，根据公式2r ≥ k+r+1得到r=3， i =1,2,3，由此生成一个7位海明码H7H6H5H4H3H2H1，各位数据分别为： D4D3 D2 P3D1 P2 P1 22 21 20 有一字节的信息需生成海明码 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 8 4 2 1 三、海明校验码 例：已知BCD码为1011，求可以检测并纠正1位错的发送端海明校验码。 K=4，根据公式2R?R+K+1 ，R=3。 校验位Pi在海明码下标2i–1 (i =1~3)上，则：P1=H1、P2=H2、P3=H4。 海明码为7位：H7H6H5H4H3H2H1 D4D3D2 P3D1 P2 P1 采用偶校验 P3= D4⊕D3 ⊕D2 0 = 1 ⊕ 0 ⊕ 1 P2= D4 ⊕D3 ⊕D1 0 = 1 ⊕ 0 ⊕1 P1 = D4⊕D2 ⊕D1 1 = 1 ⊕ 1 ⊕1 海明码为：1010101。 三、海明校验码 例：已知8位信息为1001 1010，求可以检测并纠正1位错的发送端海明码。 解：K=8，根据公式2R?R+K+1 ，R=4。 校验位Pi在海明码下标2i–1 (i =1~4) ，则： P1=H1、P2=H2、P3=H4、P4=H8。 海明码为12位：H12H11H10H9 H8H7H6H5 H4H3H2H1