吉大《数字逻辑电路》第二章数制与编码拓展资源.docx

吉大数字逻辑电路第二章数制与编码拓展资源常用校验码计算机系统运行时，各个部之间要进行数据交换.为确保数据在传送过程正确无误，常使用检验码.我们 常使用的检验码有三种.分别是奇偶校验码、海明校验码和循环冗余校验码(CRC)。奇偶校验码奇偶校验码最简单，但只能检测出奇数位出错.如果发生偶数位错误就无法检测.但经研究是奇数位 发生错误的概率大很多.而且奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码。奇偶校睑码 是奇校验码和偶校验码的统称.它们都是通过在要校验的编码上加一位校验位组成.如果是奇校验加上校验 位后，编码中1的个数为奇数个。如果是偶校验加上校验位后，编码中1的个数为偶数个。例：原编码奇校验偶校验()0000000 10000 000100010 00010 111001100 11100 010101010 11010 0海明校验码海明码也是利用奇偶性来校验数据的.它是一种多重奇偶校验检错系统，它通过在数据位之间插入k个校 验位，来扩大码距，从而实现检错和纠错.设原来数据有n位，要加入k位校验码.怎么确定k的大小呢？ k个校验位可以有pow(2,k)(代表2的 k次方)个编码，其中有一个代表是否出错.剩下pow(2,k)-l个编码则用来表示到底是哪一位出错.因为n个 数据位和k个校验位都可能出错，所以k满足pow(2,k)-1 >= n+k。设k个校验码为P1.P2. .Pk, n个数据位为DO,DL.Dn产生的海明码为H1,H2. H(n+k)。如有8 个数据位，根据pow(2,k)T >= n+k可以知道k最小是4。循环冗余校验码CRC码利用生成多项式为k个数据位产生r个校验位进行编码，其编码长度为0=1<+1'所以又称(n,k)码.CRC 码广泛应用于数据通信领域和磁介质存储系统中.CRC理论非常复杂，一般书就给个例题，讲讲方法.现在简单 介绍下它的原理：在k位信息码后接r位校验码，对于一个给定的(n,k)码。可以证明(数学高手自己琢磨证明过程)存在 一个最高次嘉为n-k=r的多项式g(x),根据g(x)可以生成k位信息的校验码,g(x)被称为生成多项式用C(x)=C(kT)C(k-2).C0表示k个信息位，把C(x)左移I位，就是相当于C(x)*Pow(2,r)给校验 位空出r个位来了.给定一个生成多项式g(x),可以求出一个校验位表达式r(x) oC(x)*pow(2,r)/g(x) =q(x) + r(x)/g(x)用 C(x)*pow(2,r)去除生成多项式 g(x)商为 q(x)余数是 r(x)。所以有 C(x)*pow(2,r) = q(x)*g(x) + r(x)C(x)*pow(2,r) + r(x)就是所求的n位CRC码，由上式可以看出它是生成多项式g(x)的倍式.所以如果用得 到的n位CRC码去除g(x)如果余数是0,就证明数据正确.否则可以根据余数知道出错位.