黑色海岸线论坛 - Powered by Discuz! Board

标题: [原创]网络错误检测和纠正 [打印本页]

作者: x86 时间: 2005-4-13 21:24 标题: [原创]网络错误检测和纠正

[这个贴子最后由x86在 2005/04/13 11:09pm 第 1 次编辑]

[watermark] 大家都知道数据在网络的传输中会产生各种各样的错误，虽然目前的主干网的传播方式已经基本上由低错误率的光纤取代，但是在用户接入的部分仍然传播的是模拟信号，用的是双绞线。而且，无线网络正在普及中，随之而来的高传输错误率还会在很长一段时间里伴随着我们。
网络设计者已经设计出2种基本的策略用于错误处理：一种是在要传输的数据中加入足够的冗余信息，从而接受方可以根据接受的数据推断出发生了什么错误，确定发送的内容。一般称之为纠错码，典型的纠错码是海明码。第二种也是加入一部分冗余信息，但是只能让对方判断发生了哪些错误，但是并不知道错误发生在什么地方，只是接受方查出错误后返回一个信息要求发送方重发数据。这一策略的应用称为检错码，典型的检错码为多项式编码。
海明码和多项式编码一个明显的区别是一个会检测出错误并计算出原始的数据，而多项式编码则只进行检错，而只要求发送方重传数据。

海明码的工作原理
首先看看海明距离的概念，一个加入了错误控制的数据桢应该包含m个数据位和r个冗余位(校验位)。则桢的总长度为n=m+r。我们称包含m数据位，r个校验位的n位单元为n位码字(codeword).比如2个8位码字11000101和01001101，我们把这两个8位码字中不相同的位的个数称为海明距离(Hamming distance)。事实上我们可以把这两个码字进行异或运算，就得到他们的海明距离了！
11000101
01001101
---------
10001000
即他们的海明距离为2
我们从一个具体的例子来讲讲海明码的原理。
假设我们要发送的数据为10101101，首先我们需要加入冗余位来校验。那我们需要加入多少冗余位呢？一个合理的选择是2r>=k+r+1,其中r为冗余位的位数。因为加入冗余码后的数据长度为k+r+1（注：我们需要用冗余码的组合来求出发生错误的位置）通过上面的公式，我们很快可以找到r=4
求冗余码的位置
一般默认码的位置为2的幂，即第1，2，4，8...位。在这里，码的位置应该为1，2，4，8位，于是我们把他们插入到数据中去：
1  0  1  0  d  1  1  0  c  1  b  a
12 11 10 9  8  7  6  5  4  3  2  1
下面我们要给这些冗余码赋恰当的值，使之能正确地表示出错误的地方。
一般而言，我们的思路是这样的，即用一个码来监督几个位，包括他自己。这也是我们默认码的位置为2的幂的原因，因为我们能很容易用他们来表示多所有的位。
码a对应的监督位为 1 ， 3，  5， 7，    9，  11
                  1 ，1+2，1+4， 1+2+4， 1+8， 1+2+8
码b对应的监督位为 2 ， 3，  6， 7，    10， 11
码c对应的监督位为 4 ,  5, 6,    7,       12
码d对应的监督位为 8，  9，  10， 11，    12，
也许有人问，为什么a的监督位是1，3，5，7，9，11呢，还有其他比如2，4，甚至15呢？首先2=2+0，或者4=1+3，但是第三位并不是一个冗余码，同样8只能用8自己来校验。有人问15=1+2+4+8啊，但是我们总的位数为8+r=12，所以这也是为什么c和d只监督5个位的原因了。
也许会问，怎么去监督呢？不知道大家学过奇偶校验没有？比如一个数11011011其中1的个数为6，即偶数个，那么我们在传输的时候附加一个0在末尾，接受者如果发现受到的数据的前8位的1的个数为奇数个，或者前面为偶数个而最后一个为1，则表明数据发生了错误。但是这种情况只能检测一位的错误，所以由于他的限制，海明码同样也只能检测一位的错误，但是他能检测出是哪一位错了，并修改。
好了，下面把偶校验应用到其中来。我们先看看a的监督位
a->1,3,5,7,9,11
我们先假设a的值为0，然后把监督位的偶校验作为冗余码的值。
1  0  1  0  d  1  1  0  c  1  b  a
12 11 10 9  8  7  6  5  4  3  2  1
a->0,1,0,1,0,0 偶校验为0，则a=0(这里的0和1 为a监督的位的值)
b->0,1,1,1,1,0 偶校验为0，则b=0
c->0,0,1,1,1    偶校验为1，则c=1
d->0,0,1,0,1    偶校验为0，则d=0
好了现在冗余码的值已经确定了，把他们加到数据中去，则要发送的数据为：
1  0  1  0  0  1  1  0  1  1  0  0
         d          c    b  a
好，现在假设传输发生了错误，接受方接受到的是101001111100，即第5位错误了。
在接受方不知道错误的情况下，他首先要找到冗余码（知道m和r）
根据上面的监督关系
码a对应的监督位为 1 ， 3，  5， 7，    9，  11
码b对应的监督位为 2 ， 3，  6， 7，    10， 11
码c对应的监督位为 4 ,  5, 6,    7,       12
码d对应的监督位为 8，  9，  10， 11，    12，
101001111100
再求一次对应的码值
a-》0,1,1,1,0,0 偶校验为1，则a=1
b-》0,1,1,1,1,0 偶校验为0，则b=0
c-》1,1,1,1,1    偶校验为1，则c=1
d-》0,0,1,0,1    偶校验为0，则d=0
则冗余码为0101=5  （注意：0101是按照各个冗余码的位置来排列的dcba）
则第五位发生了错误，（为什么是第5位呢？由监督表可以有下列关系：
0000  0001  0010  0011  0100 0101 0110 0111 1000 1001 1010 1011 1100
无    1 2    3 4 5    6 7 8 9 10  11 12
所以为第5位错误，把他取反为0，则新的数据为101001101100，然后去掉冗余码得到原始数据：10101101
举另外一个例子，不太容易理解，但是有助于编程：
已知：信息码为：" 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分别插于2k位(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"
　2)海明码的接收。
　例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+20=1
　　　　　　B=∑(0,0,0,0,1,0)=1　err=err+21=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)把位于2k位的冗余码删除得信息码："1 1 0 0 1 1 0 0" [/watermark]

作者: x86 时间: 2005-4-13 21:28 标题: [原创]网络错误检测和纠正

[这个贴子最后由x86在 2005/04/13 09:34pm 第 1 次编辑]

有任何错误和疑问请提出，谢谢！
//（下次会把多项式编码（循环冗余校验码）补上）

欢迎光临黑色海岸线论坛 (http://bbs.thysea.com/)