关于海明码的题目

关于海明码的目 关于海明码的题目 例题3 　　若海明码的监督关系式为： 　　S0=a0+a3+a4+a5 　　S1=a1+a4+a5+a6 　　S2=a2+a3+a5+a6 　　接收端收到的码字为：a6a5a4a3a2a1a0=1010100 　　那最多一位错的情况下发送端的发送信息位是什么? 　　解答：按监督关系式 　　S0=0+0+1+0=1 　　S1=0+1+0+1=0 　　S2=1+0+0+1=0 　　得出S2S1S0=001 根据值与错码位置的对应关系所以a0错误，发送端的发送信息应为1010101。 由于S2 S1 S0=100，则说明S0、S1没有出错 0说明没出错 1说明出错 ●海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： 　　　　　　　　　２^r>=n+1 或 2^r>=k+r+1 海明码的编码效率为： 　　　　　　　　　　　　R=k/(k+r) 　　式中 k为信息位位数 　　　　 r为增加冗余位位数 1、海明码的生成。 　例1.已知：信息码为："0010"。海明码的监督关系式为： 　　　　　　　　S2=a2+a4+a5+a6 　　　　　　　　S1=a1+a3+a5+a6 　　　　　　　　S0=a0+a3+a4+a6 　　　　　　　 　　　　求：海明码码字。 　　解：1)由监督关系式知冗余码为a2a1a0。 　　　　2)冗余码与信息码合成的海明码是："0010a2a1a0"。 　　　　　设S2=S1=S0=0,由监督关系式得： 　　　　　　　　a2=a4+a5+a6=1 　　　　　　　　a1=a3+a5+a6=0 　　　　　　　　a0=a3+a4+a6=1 　　　　　　因此，海明码码字为："0010101" 2、海明码的接收。 　例2.已知：海明码的监督关系式为： 　　　　　　　　S2=a2+a4+a5+a6 　　　　　　　　S1=a1+a3+a5+a6 　　　　　　　　S0=a0+a3+a4+a6 　　　　　　接收码字为："0011101"(n=7) 　　　　求：发送端的信息码。 　　解：1)由海明码的监督关系式计算得S2S1S0=011。 　　　　2)由监督关系式可构造出下面错码位置关系表： S2S1S0 000 001 010 100 011 101 110 111 错码位置 无错 a0 a1 a2 a3 a4 a5 a6 　　　　3)由S2S1S0=011查表得知错码位置是a3。 　　　　4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1" 　　　　5)把冗余码a2a1a0删除得发送端的信息码："0010" 3、海明码的生成（顺序生成法）。 　例3.已知：信息码为：" 1 1 0 0 1 1 0 0 "　(k=8) 　　　　求：海明码码字。 　　解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码 　　　　　　码字:" A B 1 C 1 0 0 D 1 1 0 0 " 　　　　 　码位:　1 2 3 4 5 6 7 8 9 10 11 12 　　　其中A,B,C,D分别插于2^k位(k=0,1,2,3)。码位分别为1,2,4,8。 　　　　2)冗余码A,B,C,D的线性码位是：(相当于监督关系式) 　　　　　　A->1,3,5,7,9,11； 　　　　　　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)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0" 4、海明码的接收。 　例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8) 　　　　求：发送端的信息码。 　　解：1)设错误累加器(err)初值=0 　　　　2)求出冗余码的偶校验和，并按码位累加到err中： 　　　　　　A=∑(1,0,1,0,1,0)=1　err=err+2^0=1 　　　　　　B=∑(0,0,0,0,1,0)=1　err=err+2^1=3 　　　　　　C=∑(1,1,0,0,0)　=0　err=err+0 =3 　　　　　　D=∑(0,1,1,0,0)　=0　err=err+0 =3 　　　　　由err≠0可知接收码字有错， 　　　　3)码字的错误位置就是错误累加器(err)的值3。 　　　　4)纠错--对码字的第3位值取反得正确码字： 　　　　　　"1 0 1 1 1 0 0 0 1 1 0 0" 　　　　5)把位于2^k位的冗余码删除得信息码："1 1 0 0 1 1 0 0" 采用海明码进行差错校验，信息码字为1001011，为纠正一位错，则需要 （19） 比特冗余位。 （19）A．2 B．3 C．4 D．8 试题解析：  海明码纠正X位错误，需要2X+1位冗余位。：（19）B ● 设数据码字为10010011，采用海明码进行校验，则必须加入  （20）  比特冗余位才能纠正一位错。 （20）A．2    B．3    C．4    D．5 试题解析：  n位海明码最多可以校验和纠正 2n-1位的数据中的一位错误，（这些数据包括用户数据和海明码自身）。因此，3位海明码最多可以检验和纠正8-1-3=4位用户数据中的一位错误；4位海明码最多可以检验和纠正16-1-4=11位用户数据中的一位错误。参考答案：C 2003年度网络设计师的第一题中，要检查出d位错，码字之间的海明距离最小值应为（）答案为2d+1,我觉得应该为d+1，要纠正d位错才是2d+1。请老师指教！    答：检测出d个错误，则海明距离至少为d＋1。即一个码字错d＋1个比特才能变成另一个，<=d 只能变成无效码字，能被检测出来。要纠正d个错误，海明距离至少应为2d＋1；