海明码校验培训资料

奇偶校验规律(guīlǜ)校验位的取值（0或1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律(guīlǜ)：奇校验──整个校验码（有效信息位和校验位）中“1”的个数为奇数。偶校验──整个校验码中“1”的个数为偶数。第一页，共23页。2.简单(jiǎndān)奇偶校验简单奇偶校验仅实现横向的奇偶校验，下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位，其余8位为信息位。在实际应用中，多采用奇校验，因为奇校验中不存在全“0”代码，在某些场合下更便于(biànyú)判别。有效信息（8位）奇校验码（9位）偶校验码（9位）00000000100000000000000000010101000010101001010101000111111100111111110111111111111111111111111011111111第二页，共23页。2.简单(jiǎndān)奇偶校验（续）⑴校验位形成当要把一个字节的代码D7～D0写入主存时，就同时将它们(tāmen)送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。若D7～D0中有偶数个“1”，则“奇形成”=1，

若D7～D0中有奇数个“1”，则“奇形成”=0。第三页，共23页。奇偶校验(xiàoyàn)位的形成及校验(xiàoyàn)电路图2-2奇偶校验(xiàoyàn)位的形成及校验(xiàoyàn)电路第四页，共23页。2.简单(jiǎndān)奇偶校验（续）⑵校验检测读出时，将读出的9位代码（8位信息位和1位校验位）同时送入奇偶校验电路检测。若读出代码无错，则“奇校验出错”=0；若读出代码中的某一位上出现错误(cuòwù)，则“奇校验出错”=1，从而指示这个9位代码中一定有某一位出现了错误(cuòwù)，但具体的错误(cuòwù)位置是不能确定的。第五页，共23页。3.交叉(jiāochā)奇偶校验计算机在进行大量(dàliàng)字节（数据块）传送时，不仅每一个字节有一个奇偶校验位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。第1字节11001011→1第2字节01011100→0第3字节10011010→0第4字节10010101→0↓↓↓↓↓↓↓↓10011000第六页，共23页。3.交叉(jiāochā)奇偶校验（续）交叉校验可以发现两位同时出错的情况，假设(jiǎshè)第2字节的A6、A4两位均出错，横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。第七页，共23页。海明校验码海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正(jiàozhèng)因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：2r≥k+r+1或2r≥n+1第八页，共23页。海明校验码海明码(HammingCode)编码的关键是使用多余的奇偶校验位来识别一位错误。码字(CodeWord)按如下方法构建：1、把所有2的幂次方的数据位标记为奇偶校验位(编号(biānhào)为1,2,4,8,16,32,64等的位置)2、其他数据位用于待编码数据.(编号(biānhào)为3,5,6,7,9,10,11,12,13,14,15,17等的位置)第九页，共23页。海明校验码3、每个奇偶校验位的值代表了代码字中部分(bùfen)数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。位置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,…)…第十页，共23页。海明校验码采用偶校验，如果全部(quánbù)校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部(quánbù)校验的位置中有偶数个1，把该奇偶校验位置为0.第十一页，共23页。海明校验码举例说明：一个字节的数据：10011010构造(gòuzào)数据字(DataWord),对应的校验位留空__1_001_1010计算每个校验位的奇偶性(?代表要设置的比特位):

第十二页，共23页。海明校验码位置(wèizhi)1检查1,3,5,7,9,11:?_1_001_1010.偶数个1，因此位置(wèizhi)1设为0，即:0_1_001_1010位置(wèizhi)2检查2,3,6,7,10,11:0?1_001_1010.奇数个1，因此位置(wèizhi)2设为1，即:011_001_1010第十三页，共23页。海明校验码位置4检查4,5,6,7,12:011?001_1010.奇数个1，因此(yīncǐ)位置4设为1，即:0111001_1010位置8检查8,9,10,11,12:0111001?1010.偶数个1，因此(yīncǐ)位置8设为0，即:011100101010因此(yīncǐ)码字为:011100101010.第十四页，共23页。海明校验码上例中构建了一个码字011100101010，假定实际接收到的数据011100101110.则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位，可以发现(fāxiàn)校验位2和8的数据不正确.错误校验位2+8=10,则位置10的数据出错。一般说来，对所有校验位进行检查,将所有出错的校验位置相加,得到的就是错误信息所在的位置.第十五页，共23页。海明校验码例1.已知：信息码为："11001100"(r=4代表(dàibiǎo)冗余位数，即校验码位数)求：海明码码字。第十六页，共23页。海明校验码解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码码字:"AB1C100D1100"码位:123456789101112其中(qízhōng)A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。第十七页，共23页。海明校验码2)冗余码A,B,C,D的线性码位是：(相当于监督(jiāndū)关系式)监督(jiāndū)关系式的推导：DCBA100012001030011401005010160110701118100091001101010111011121100根据上面表格得到ABCD第十八页，共23页。海明校验码需要说明的是公式中参与计算的是表格中出现"1"的那个位右边是数据位的二进制数,公式中的"+"表示异或故此(gùcǐ)有如下表达式：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。第十九页，共23页。海明校验码3)把线性码位的值的偶校验作为冗余(rǒnɡyú)码的值(设冗余(rǒnɡyú)码初值为0)：A=∑(0,1,1,0,1,0)=1B=∑(0,1,0,0,1,0)=0C=∑(0,1,0,0,0)=1D=∑(0,1,1,0,0)=04)海明码为:"101110001100"第二十页，共23页。海明校验码例2.已知：接收的码字为："100110001100"(r=4代表冗余(rǒnɡyú)位数，即校验码位数)求：发送端的信息码。第二十一页，共23页。海明校验码解：1)设错误(cuòwù)累加器(err)初值=02)求出冗余码的偶校验和，并按码位累加到err中：A=∑(1,0,1,0,1,0)=1err=err+2^0=1B=∑(0,0,0,0,1,0)=1err=err+2^1=3C=∑(1,1,0,0,0)=0err=err