差错纠正技术

采用检错码技术虽然能够检测出帧在传输过程中是否发生了错误，但由于在检测到错误发生之后，需要发送方重传整个帧，故检错码技术仅适用于光纤灯具有高可靠性的信道上，而不适合于错误发生很频繁的无线信道上，这是因为在错误发生很频繁的信道上，即便重传也还是很可能出错的，因此难以有效保证帧的正确传送。为此，最好的办法是使用纠错码（Error Correcting Code）技术，通过在每一个发送的数据帧中包含足够的冗余信息（校验位），让接收方在收到该数据帧后不但可以检测出其中是否发生了错误，而且一旦发现出错，还可以还原出原始的帧内容，不需要依靠重传来解决问题。目前，最具代表性的检错码方法为海明码（也称为奇偶校验码）。

定义3.1（码字）：假定n=m+r，包含m个数据位和r个校验位（冗余位）的n−位单元，称为n−位码字。

定义3.2（海明距离）：两个码字中不相同的位的个数，即对两个码字进行异或（XOR）运算后，结果中的1的个数，称为海明距离。其中，异或（XOR）运算为：1+1=0+0=0，1+0=0+1=1。例如：

上述定义3.2中给出的海明距离的意义如下：

（1）如果两个码字的海明距离为d，则需要d个1位错误才能将一个码字转变成另一个码字。

（2）如果一个编码方案S中的所有码字的距离均为d+1，则该方案能检测d个错误。因为如果码字a∈S发生d个错误变成了a'，则dist (a', a)=d；如果a'∈S，由于S中的所有码字的距离均为d+1，从而有dist(a', a)=d+1，矛盾！故有a'∈S。因此，可以判定传输过程发生了错误。即该方案能检测d个错误。

（3）如果一个编码方案S中的所有码字的距离均为2d+1，则该方案能纠正d个错误。因为若码字a∈S发生d个错误变成了a'，则dist (a', a)=d，而对于任意码字b∈S，且b≠a，依据距离不等式dist(a, a')+dist(a', b)≥dist(a, b)，有 dist(a', b)≥dist(a, b)-dist(a, a')= 2d+1−d=d+1。故a' 到S中的码字a的距离最近，因此可以判定a' 对应的原始码字为a。即该方案能纠正d个错误。

基于上述海明距离的意义，可给出能纠正单个错误的海明码编码方案如下：

步骤1：码字中的每一位，从最左边位编号1开始，连续编号；

步骤2：编号为2的幂次方的位（1，2，4，8，16，…）为校验位，剩下的位（3，5，6，7，9，…）用m个数据位来填充。

步骤3：每一个校验位都迫使某一组位（包括它自己）的奇偶值为偶数（偶校验）或奇数（奇校验）。

按照上述方法编码的海明码能纠正单个错误，例如：若采用偶校验，假定第11位的数据位出错，则依据第1，2，8位校验位及第11位数据位本身，即可知道这4个位的奇偶值不为偶数，故由此可知第11位的数据位出错，然后通过将第11位的数据位变反，即可纠正该单个错误。

基于以上给出的海明码编码方案，为了更清晰地描述其实现步骤，下面举例加以说明。

例如：假定待传输的数据帧为“1101101”，基于海明码编码方案，若采用偶校验，则数据可按以下方式编码为长11位的码字。其中，第1，2，4，8位为校验位，第3，5，6，7，9，10，11位为数据帧中的数据位，即带校验位的纠错码的编码为X1X21 X4101 X8101。下面需要分别确定X1，X2，X4，X8的值。为此，首先如图3.2所示，计算得到各数据位所对应的校验组位。依据以上海明码的编码方案有：

◆ X1迫使第1组位（包括它自己）的奇偶值为偶数，而第1组位除X1自己之外，包含5个1（即第3，5，7，9，11数据位的值为1，且其展开式中均包含第1组位）。故X1应为1才能使得第1组位的奇偶值为偶数，因此有：X1=1。

◆ X2迫使第2组位（包括它自己）的奇偶值为偶数，而第2组位除X2自己之外，包含3个1（即第3，7，11数据位的值为1，且其展开式中均包含第2组位）。故X2应为1才能使得第2组位的奇偶值为偶数，因此有：X2=1。

◆ X4迫使第4组位（包括它自己）的奇偶值为偶数，而第4组位除X4自己之外，包含2个1（即第5，7数据位的值为1，且其展开式中均包含第4组位）。故X4应为0才能使得第4组位的奇偶值为偶数，因此有：X4=0。

◆ X8迫使第8组位（包括它自己）的奇偶值为偶数，而第8组位除X8自己之外，包含2个1（即第9，11数据位的值为1，且其展开式中均包含第8组位）。故X8应为0才能使得第8组位的奇偶值为偶数，因此有：X8=0。

故最终编码为：11101010101。

纠正单个错误所需要的校验位的数目的下界可由以下方式确定：

假定在编码方案S中，每个n−位码字（n=m+r）包含m个数据位和r个校验位，且能纠正单个错误。显然，存在2m个合法报文，任意一个报文都对应n个与其距离为1的非法n−位码字。因此，要能纠正单个错误，这n个与其距离为1的非法n−位码字均不能放到S中，即每个合法的报文均需要占用n+1个n−位码字。而总共有2n个n−位码字，故必须有：(n+1)*2m≤2n⇒(m+r+1)* 2m≤2m+r⇒(m+r+1)≤2r。该条件给出了用于纠正单个错误所需要的校验位数目的下界。

海明码编码方案可以达到上述下界。仍采用上例，其中，数据帧中的数据位的个数为7，即m=7⇒(7+r+1)≤2r⇒(8+r)≤2r⇒r≥4，故可知纠正单个错误所需要的校验位的数目的下界应为4。而由上例可知，采用海明码编码方案可采用4位校验位将数据编码为长11位的码字，即达到了上述纠正单个错误所需要的校验位的数目的下界。

图3.2　数据位的组位展开示意图