海明码校验

奇偶校验规律校验位的取值（0或1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律：奇校验──整个校验码（有效信息位和校验位）中“1”的个数为奇数。偶校验──整个校验码中“1”的个数为偶数。2.简单奇偶校验简单奇偶校验仅实现横向的奇偶校验，下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位，其余8位为信息位。在实际应用中，多采用奇校验，因为奇校验中不存在全“0”代码，在某些场合下更便于判别。有效信息（8位）奇校验码（9位）偶校验码（9位）000000001000000000000000000101010000101010010101010001111111001111111101111111111111111111111110111111112.简单奇偶校验（续）⑴校验位形成当要把一个字节的代码D7～D0写入主存时，就同时将它们送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。若D7～D0中有偶数个“1”，则“奇形成”=1，若D7～D0中有奇数个“1”，则“奇形成”=0。奇偶校验位的形成及校验电路D7D6D5D4D3D2D1D0D校奇形成偶校验出错奇校验出错偶形成AB=1=1=1=1=1=1=1=111图2-2奇偶校验位的形成及校验电路2.简单奇偶校验（续）⑵校验检测读出时，将读出的9位代码（8位信息位和1位校验位）同时送入奇偶校验电路检测。若读出代码无错，则“奇校验出错”=0；若读出代码中的某一位上出现错误，则“奇校验出错”=1，从而指示这个9位代码中一定有某一位出现了错误，但具体的错误位置是不能确定的。3.交叉奇偶校验计算机在进行大量字节（数据块）传送时，不仅每一个字节有一个奇偶校验位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。第1字节11001011→1第2字节01011100→0第3字节10011010→0第4字节10010101→0↓↓↓↓↓↓↓↓100110003.交叉奇偶校验（续）交叉校验可以发现两位同时出错的情况，假设第2字节的A6、A4两位均出错，横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。海明校验码海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：2r≥k+r+1或2r≥n+1海明校验码•海明码(HammingCode)编码的关键是使用多余的奇偶校验位来识别一位错误。•码字(CodeWord)按如下方法构建：•1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1,2,4,8,16,32,64等的位置)•2、其他数据位用于待编码数据.(编号为3,5,6,7,9,10,11,12,13,14,15,17等的位置)海明校验码•3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。•位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…)•位置2：校验2位，跳过2位，校验2位，跳过2位(2,3,6,7,10,11,14,15,…)•位置4：校验4位，跳过4位，校验4位，跳过4位(4,5,6,7,12,13,14,15,20,21,22,23,…)•位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,…)•…海明校验码采用偶校验，如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.海明校验码•举例说明：•一个字节的数据：10011010•构造数据字(DataWord),对应的校验位留空__1_001_1010•计算每个校验位的奇偶性(?代表要设置的比特位):海明校验码•位置1检查1,3,5,7,9,11:•?_1_001_1010.偶数个1，因此位置1设为0，即:0_1_001_1010•位置2检查2,3,6,7,10,11:•0?1_001_1010.奇数个1，因此位置2设为1，即:011_001_1010海明校验码•位置4检查4,5,6,7,12:•011?001_1010.奇数个1，因此位置4设为1，即:0111001_1010•位置8检查8,9,10,11,12:•0111001?1010.偶数个1，因此位置8设为0，即:011100101010•因此码字为:011100101010.海明校验码上例中构建了一个码字011100101010，假定实际接收到的数据011100101110.则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位，可以发现校验位2和8的数据不正确.错误校验位2+8=10,则位置10的数据出错。一般说来，对所有校验位进行检查,将所有出错的校验位置相加,得到的就是错误信息所在的位置.海明校验码•例1.已知：信息码为：11001100(r=4代表冗余位数，即校验码位数)•求：海明码码字。海明校验码•解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码•码字:AB1C100D1100•码位:123456789101112•其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。海明校验码•2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)•监督关系式的推导：•DCBA•10001•20010•30011•40100•50101•60110•70111•81000•91001•101010•111011•121100•根据上面表格得到ABCD海明校验码•需要说明的是公式中参与计算的是表格中出现1的那个位右边是数据位的二进制数,公式中的+表示异或•故此有如下表达式：•A-1,3,5,7,9,11；(这里的1357911均为A那一列出现1的位)•B-2,3,6,7,10,11；•C-4,5,6,7,12；(注5=4+1；6=4+2；7=4+2+1；12=8+4)•D-8,9,10,11,12。海明校验码•3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：•A=∑(0,1,1,0,1,0)=1•B=∑(0,1,0,0,1,0)=0•C=∑(0,1,0,0,0)=1•D=∑(0,1,1,0,0)=0•4)海明码为:101110001100海明校验码•例2.已知：接收的码字为：•100110001100(r=4代表冗余位数，即校验码位数)•求：发送端的信息码。海明校验码•解：1)设错误累加器(err)初值=0•2)求出冗余码的偶校验和，并按码位累加到err中：•A=∑(1,0,1,0,1,0)=1err=err+2^0=1•B=∑(0,0,0,0,1,0)=1err=err+2^1=3•C=∑(1,1,0,0,0)=0err=err+0=3•D=∑(0,1,1,0,0)=0err=err+0=3海明校验码•由err≠0可知接收码字有错，•3)码字的错误位置就是错误累加器(err)的值3。•4)纠错--对码字的第3位值取反得正确码字：•101110001100•5)把位于2的k次方位的冗余码删除得信息码：11001100