基于传输性质的可靠性编码

1数字逻辑数字逻辑基于传输性质的可靠性编码可靠性编码2可靠性编码可靠性编码能减少错误，发现错误，甚至纠正错误的编码称为可靠性编码防止传输过程中的错误（虽然数字信号比模拟信号可靠，更容易还原，但也不排除错误可能，绝大多数单错，多错几率很小）3元件故障、噪声干扰等各种因素常常导致计算机在处理信 息过程中出现错误为了防止错误, 可将信号采用专门的逻辑 线路进行编码以检测错误,甚至校正错误通常的方法是：在每个字上添加一些校验位,用来确定字中出 现错误的位置常用方法： 格雷码奇偶校验码 ；海明校验与纠错码 ；循环冗余校验码 1.为什么设置校验码数据校验4一、格雷码一、格雷码又称循环码，有多种形式，共同特点是任意相邻的两个代码之间仅有一位不同格雷码常用在计数器中，以防止多计数或少计数5格 雷 码• 格雷码是一种无权码二进制码 b3b2b1b0格雷码 G3G2G1G00000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 11110000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000• 编码特点是：任何两个相邻代码之间仅有一位不同。

• 该特点常用于模拟量的转换当模拟量发生微小变化，格雷码仅仅改变一位，这与其它码同时改变2位或更多的情况相比，更加可靠,且容易检错6格雷码的单位距离特性可以降低其产生错误的概率，并且能提高其运行速度例如，为完成十进制数7加1的运算， 当采用四位自然二进制码时，计数器应由0111变为1000， 由于计数器中各元件特性不可能完全相同，因而各位数码不可能同时发生变化，可能会瞬间出现过程性的错码变化过程可能为 0111→1111→1011→1001→1000虽然最终结果是正确的，但在运算过程中出现了错码1111，1011，1001，这会造成数字系统的逻辑错误，而且使运算速度降低若采用格雷码，由7变成8，只有一位发生变化，就不会出现上述错码，而且运算速度会明显提高 71、ｎ位码字：由k位数据位和r位校验位组成的n位单元2、码距：任意两个合法编码之间不同的二进数位数为码距 例：若用4位二进制数表示16种状态，16种状态都用，则码距L=1若用4位二进制数表示8种状态，而把另外8种状态作为非法编码，此时的码距L=23、最小码距：指一种编码的任意两个码字中间，对应位置代码变化的最少个数8421BCD码01111001 L=3 而01000101 L=1意思：将其中一个码字改为另一个码字需要修改Ｌ位4、数据校验的实现原理：数据校验码是在合法的数据编码之间，加进一些不允许出现的(非法的)编码，使合法的数据编码出现错误时成为非法编码。

这样就可以通过检测编码的合法性达到发现错误的目的要检查Ｌ位错，编码的码距需要L＋1，一个码字Ｌ位出错就无法成为另外一个合法码字类似地，为纠Ｌ位错，编码的码距需要２Ｌ＋１数据校验码原理82.奇偶校验原理：在 k 位数据码之外增加 1 位校验位，使 k+1 位校验码中取值为 1 的个数保持为偶数（偶校验）或 奇数（奇校验）偶校验奇校验校验位0 0 0 1 0 0 0 1 1 0 0 0 1 00 1 0 1 0 1 0 1 0 0 1 0 1 1原有数据位 两个校验码例如 ：9同理,偶校验位P定义为P＝ x0⊕x1⊕…⊕xn-1即x中包含偶数个1时,才使P＝0设x＝( x0 x1…xn-1 )是一个n位字, 则奇校验位P定义为P ＝ x0⊕x1⊕…⊕xn-1式中⊕代表按位加, 只有当x中包含有奇数个1时,P＝0偶校验 :奇校验 :偶校验检错码:G=0表示数据正常，否则表示出错奇校验检错码:10例 已知下表中左面一栏有5个字节的数据请分别用奇校验和 偶校验进行编码数 据偶校验编码Ｃ奇校验编码Ｃ1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 00 1 0 1 0 1 0 00 0 0 0 0 0 0 00 1 1 1 1 1 1 11 1 1 1 1 1 1 11 0 1 0 1 0 1 00 1 0 1 0 1 0 00 0 0 0 0 0 0 00 1 1 1 1 1 1 11 1 1 1 1 1 1 10 1 01 01 01 0 1特点：奇偶校验可检测奇数个错误，但无法检测偶数个错误,更无法识别错误信息的位置及纠正错误。

11纠错码功能从M位数据中产生一组新的K位校验码与取出的纠错码功能校 验位码作比较： 1、无错误 2、检测到差错，并可以纠正 3、检测到差错，但无法纠正12n奇偶校验n一个校验位n只能检错，无法纠错n海明码n多个奇偶校验组n既能检错，也能纠错海明校验码n分组交叉奇偶校验法n将编码中的数据位分成r个校验组，组内采取奇偶校验，每组一个校 验位，可构成r位检错码r>1n全部检错码为0表示数据正常n不为零时检错码的值表示编码中出错数据位n可检错，也可纠错n每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变化13１００１０１０１０１100１一个数据位参加多个校验组 一个数据位发生错误可在多个检测码中反应 可有效提高检错能力141．原理海明校验码的实现原理是：在数据位中加入几个校验位，将数据代码的码 距均匀地拉大，并把数据的每个二进制位分配在几个奇偶校验组中当某 一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现 错误，还能指出是哪一位出错，为进一步自动纠错提供了依据2．编码规则若海明码的最高位号为m，最低位号为1，即ＨmＨm-1…Ｈ2Ｈ1，则海明码的 编码规则是：（1）校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位 置上，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据 位。

2）海明码的每一位位码Hi（包括数据位和校验位）由多个校验位校验，其 关系是被校验的每一位位号要等于校验它的各校验位的位号之和153．增添校验位设海明码N位，其中数据位k位，校验位r位假设欲检测的有效信息为k位，需增加的校验位为r位，则 校验码的长度为n=k+r位应满足以下关系式：2r≥k+r+1这个关系式称为海明不等式，校验位r位表示共r个校验组确定校验位后，就可以与信息位组成海明校验位假设数据位 是7位，据上所述，校验位的位数k为4,故海明码的总位数为11 它们的排列关系可表示为：海明码位号：H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明码： D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1164．校验位校验任务的分配根据海明码的编码规则，每一位海明码都有多个校验位校验 ，且被校验的每一位的位号等于参与校验它的几个校验位的位号 之和 占据各权位上的校验位按权组成的8421码，正好等于海明 码的位号，即海明码的位号Hi正好等于要校验它的校验位所占权 位权值之和例如：H11＝P4×23＋P2×22＋P1×21这说明了H11位将由 P4、P2、P1进行校验。

校验位P1可以校验：H1 、H3、H5 、 H7 、H9、 H11、H13、H15校验位P2可以校验：H2 、H3、 H6、 H7 、H10、H11、H14 、H15校验位P3可以校验：H4 、H5、 H6、 H7 、H12、H13、H14 、H15校验位P4可以校验：H8、 H9、 H10、H11、H12、H13、H14 、H15根据偶校验，可以写出相应的校验方程17例：设有一个7位信息码位0110001，求它的海明码 解： 此例中，信息位k=7，根据海明不等式，可求得校验位最 短长度r=4 其海明码表示如下：海明码位号： H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明码： 0 1 1 P4 0 0 0 P3 1 P2 P1按偶校验写出校验方程为： H1 H3H5 H7 H9H11＝0 （P1＝H1） H2 H3 H6H7 H10H11＝0 （P2＝H2） H4H5 H6H7＝0 （P3＝H4） H8H9 H10H11＝0 （P4＝H8） 由此可得：P1＝0、P2＝0、P3＝0、P4＝0，所以0110001的 海明码为01100000100。

18方法：将收到的码字重新代入校验方程校验即可假设上面 例子中的海明码01100000100传送后，若H6位发生了错误 ，变成了01100100100，这时把它们代入上面的偶校验校 验方程，如下：G1=H1H3H5H7H9H11＝0  1  0010 = 0 G2=H2 H3 H6H7 H10H11＝0  11010= 1 G3=H4H5 H6 H7＝0  0  1  0 = 1 G4=H8H9 H10H11＝0  1  1  0 = 0 可以把G4G3G2G1= 0110看成一个“指误字”，因为其二 进制码为0110，说明H6出了错，是H6错成了1，所以要纠错 ，纠错时将H6位取反值，即让它恢复到正确值0这样纠错 后即可得到正确的海明码011000001005．检错与纠错19两位同时出错？引入总校验位 P5=H1⊕H2⊕H3⊕H4⊕H5⊕H6⊕H7⊕H8⊕H9⊕H10⊕H11G5=P5⊕H1⊕H2⊕H3⊕H4⊕H5⊕H6⊕H7⊕H8⊕H9⊕H10⊕H11G5判断是一位错还是两位错任何偶数个数出错， G5一定为0。

1）如果G5~ G1=00000,表明无错误2）如果G5~ G1=1xxxx,表明一位错误，位置为xxxx3）如果G5~ G1=0xxxx,表明两位错误海明码01100000100P5 =1无错误H6错 01100100100 G5~ G1=10110H6 H3错 01100100000 G5~ G1=00101G5~ G1=000000201．CRC的编码方法任何一个二进制序列中的各位看成一个多项式的系数如：11011×X3+1×X2+0×X1+1×X0设：n是有效数据信息位位数，r是校验位位数总长k=n+r位，称（k，n）码设待编码的有效信息以多项式M(x)表示，将M(x)左移r位 得到多项式M(x)*Xr，使低r位二进制位全为零，以便与r位校 验位拼接使用多项式M(x)*Xr除以生成多项式G(x)，求得的 余数即为校验位为了得到r位余数(校验位)，G(X)必须是 r+1位的循环冗余校验码G(X)最高项的指数决定了r的位数21这时将余数R(X)与M(x)*Xr相加，就得到n+r位CRC编码：M(x)*Xr+R(x)= Q(x)*G(x) + R(x) + R(x) 因为“两个相同数据的模2和为零”，即R(x) + R(x) = 0，所以M(x)*Xr+R(x) = Q(x)*G(x) CRC编码是可被G(X)表示的编码整除。

假设M(x)*Xr除以生成多项式G(x) ，求得的余数用表达式 R(x)表示，商的表达式用Q(x)表示，它们之间的关系如下 ：22例 设四位有效信息位是1100，选用生成多项式 G(X)=1011， 试求有效信息位1100的CRC编码解：(1)将有效信息位1100表示为多项式M(x)M(X) = X3 + X2 = 1100(2)M(X)左移r=3位，得M(x)*X3。