海明码奇偶校验的基础问题~~求助!!!

发布网友发布时间：2022-04-22 06:18

共1个回答

热心网友时间：2022-04-22 07:48

1．校验原理：在数据中加入几个校验位（奇偶校验位），将数据代码的码距比较均匀地拉大，并把数据的每个二进制位分配在几个奇偶校验位组中。当某一位出错时，就会引起有关若干校验位的值发生变化，在不但可以发现出错，还能找出哪一位出错，为进一步自动纠错提供依据。2．编码规则：设对N位数据用K位校验位校验，则其海明码为：HmHm-1....H2H1其中最高位位号m，最低位位号为1。（1）校验位与数据位之和m（m=K+N）；（2）每个校验位Pi分配在海明码的2i-1位置上；（3）海明码中除校验位，其它为数据位。被校验数据从低到高顺序分配到海明码中；（4）海码的每一位码Hi由多个校验位校验，且被校验的每一位位号要等于校验它的个校验位的位号之和；（5）在增大合法码的码距时，使码距均匀地增大，保证检错平均。3．发现两位错、纠正一位错的海明码为表示N位数据、K位校验位中某一位出错以及无错，共有N+k+1种情况，另考虑到要发现两位同时出错，则应满足2K-1≥N+K+1按此关系计算所得K与N对应值如教材所示。例如，对N=8（一字节数据D8D7D6D5D4D3D2D1），需校验位K应为5，海明码为H13H12....H2H1其中5个校验位P5、P4、P3、P2、P1分别为H13、H8、H4、H2、H1，其余为数据位，即海码H13H12....H2H1为： P5D8D7D6D5P4D4D3D2P3D1P2P1根据“被校验位的海码位号==校验位号之和”关系，校验位Pi校验所有位号中带有i的海码位（方法同奇偶校验）：S1=P1⊕D1⊕D2⊕D4⊕D5⊕D7S2=P2⊕D1⊕D3⊕D4⊕D6⊕D7S3=P3⊕D2⊕D3⊕D4⊕D8S4=P4⊕D5⊕D6⊕D7⊕D8在上述关系中D4和D7分别由三个校验位校验，其余均只被两位校验，为此用P5对D1、D2、D3、D5、D6、D8再进行校验：若采用奇校验，则S1 S2 S3 S4 S5应为11111；若采用偶校验，则S1 S2 S3 S4 S5应为00000。现假设采用偶校验，则有：P1=D1⊕D2⊕D4⊕D5⊕D7P2=D1⊕D3⊕D4⊕D6⊕D7P3=D2⊕D3⊕D4⊕D8P4=D5⊕D6⊕D7⊕D8P5=D1⊕D2⊕D3⊕D5⊕D6⊕D8生成海明码，就是计算上述五个校验位；而校验过程就是计算前面所述的S1 S2 S3 S4 S5，它们反映了13 位海明码出错情况。当采用偶校验时，有教材所示判无错或发生一、二位出错及出错位号的结论。4．发现一位错、纠正一位错的海明码对N位数据位、K位校验位，要发现一位错、纠正一位错，则应满足2K≥N+K+1例如K=4，则N≤24-4-1=11，即最多只能校验11位数据。若对一字节（N=8）数据编码，则也需校验位4位，其海明码H12....H2H1为：D8D7D6D5P4D4D3D2P3D1P2P1校验关系式为：S1=P1⊕D1⊕D2⊕D4⊕D5⊕D7S2=P2⊕D1⊕D3⊕D4⊕D6⊕D7S3=P3⊕D2⊕D3⊕D4⊕D8S4=P4⊕D5⊕D6⊕D7⊕D8若假设采用偶校验，则有：P1=D1⊕D2⊕D4⊕D5⊕D7P2=D1⊕D3⊕D4⊕D6⊕D7P3=D2⊕D3⊕D4⊕D8P4=D5⊕D6⊕D7⊕D8举例：数据10101010采用偶校验方法可计算出4个校验位P4P3P2P1=0100，则求出数据10101010的海码为101001011000，把8位数据和4位校验位组成的海码一起存储、传送处理，当再次使用时，计算S1 S2 S3 S4，判是否均为0，若某一组S值不为0，则说明该组S所对应的位有错产生。如S4S3=11，则这两个S组中公有的一位出错---D8错。可通过对该位数据进行取反而得到纠正。