奇偶校验码在数据传输中的实现∗

王 军 刘 曦 罗清龙

1 引言

在信息的传输中，模拟信号的保真度一直受到各方面原因的限制，失真时有发生，而数字信号则用0、1两个数字承载所传输的信息，准确读出数字即可保证信息的准确性。与模拟信号相比，数字信号具有抗噪声，抗干扰强的特点。但是过强的噪声的干扰极有可能将传输的0变为1，1变为0，此时以编码理论为基础的编码纠错技术的存在在数字通信中就显得尤为重要了。

对于通信系统而言，纠错码的出现无疑提高了其通信的可靠性，大大增加了通信成功的概率。在多数实际差错控制系统中都使用线性码作为数据传输过程中的校验纠错码，因此对线性分组码的研究是非常有必要的，不仅在学术方面意义重大，实际应用价值也非常巨大。

本文主要研究一维及二维奇偶校验码编码和译码算法，并使用C语言来实现奇偶校验纠错码的编码译码算法，而这些研究展现了其良好的检错纠错性能。一维奇偶校验码根据其编码位置的不同可分为垂直奇偶校验码和水平奇偶校验码，其中垂直奇偶校验码对随机错误有很好的检测效果，水平奇偶校验码相对于垂直奇偶校验码增加了检测突发错码的能力，二者都没有纠错能力。本文将主要对水平奇偶校验码的检错功能进行实现；二维奇偶检验码，也可以被称为矩阵码或水平垂直一致校验码，检错效果要优于一维奇偶校验码，具有一定的纠错能力，适用于检测成串出现的突发错码，在数据传输网络中应用较多，因此本文将对其检错纠错功能进行实现。

2 一维及二维奇偶校验码概述

奇偶校验码编码的基本原理就是在信息位之前或之后额外增添1个冗余位，使得整个码字中“1”的个数恒为奇数或偶数，而增加1个冗余位可以使码距变为2，这样就可以拥有检测1位错误的能力。奇偶校验应用时一般将一个字节作为最小校验单位。而一个ASCII字符恰好占用一个字节也就是8位，因此也可以说奇偶校验码以字符为最小单位来使用。而在现实的应用中，又可以将其细分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验这三种来使用，三种码可分别应用于不同的信道。此种校验方法的实质其实就是确定一组被传输的二进制代码中“1”的个数的奇偶性。若最终确定信息码组中“1”的个数为奇数的话就称其为奇校验，反之，则称为偶校验。

垂直奇偶校验码和水平奇偶校验码，只在一个方向上添加校验位，因此被称为一维奇偶校验码。

垂直奇偶校验，可以称其为纵向奇偶校验，原则是对所要发送整个信息划分成长度一定的段信息，一般情况下以一个字节为一段，每个段信息后面按“1”的个数的奇偶性来添加一位奇偶位，也叫校验位。垂直奇偶校验码，设每段信息的信息位为n位，那么编码效率就是n/（n+1）。使用垂直奇偶校验码可以检测出每段信息中所有的奇数个错，但是任何偶数个的错都将无法检测出。

水平奇偶校验，又可以称其为横向奇偶校验，原则是对划分出来的所有信息段的相应位来添加一个奇偶位，相当于对所发送的各段信息横向进行奇偶编码。水平奇偶校验码，若所发送的信息块被分为m段，每段n位，则其编码效率为m/（m+1）。其可以检测出各段同一位上所有的奇数个错，而且还能检测出突发长度不多于n（n为码字的定长位数）和突发长度不为n的偶数倍以外的所有突发错误。

二维奇偶校验码，由于其编码的方向，因此可以称为水平垂直奇偶校验。通信系统在对整个以字节为分段单位的数据信息进行传送之前，除了对每个字节添加一个奇偶校验位，还要对所有字节所对应的同一位也添加一个奇偶校验位，即结合两种一维校验的方法。通过这种横向、纵向同时进行校验的方式来对整个信息块进行校验，称这种校验方法称为交叉校验。交叉检验之所以拥有更好的检错性能，就是因为其有可能检测出偶数个错误。很容易理解，尽管每行的校验位无法检测出本行中的偶数个错码，但是按列的方向来进行检测的话检测出来的概率是非常大的。但与此同时某些偶数错码对其来说就是盲区了，比如可以构成矩形的四个错码。尽管如此，与前述的简单奇偶校验相比，其检错性能要更优越。此外，二维奇偶校验码拥有一定的纠错功能，可以纠正部分错码，比如对于码组中的1个随机错误，完全就可以确定错码的位置，从而对其进行纠正。对于一个拥有m段，每段n位的信息块，二维奇偶校验码的编码效率为（m×n）/［（m+1）×（n+1）］。其适用于检测突发错码。除检错外，二维奇偶校验码可以确定某些错误的位置，进而对其进行纠正。

3 一维及二维奇偶校验码的编译码

3.1 编码过程

对于同一个信息块，垂直奇偶校验是将其分为定长n位的m段，设为Iij（i=1，…，n；j=1，…，m），每段后面按“1”的个数为奇数或偶数的规律加上一位校验位ri（i=1，2，3，…，m）。水平奇偶校验码则是对n位m段信息的相应位横向进行编码，每段后面按“1”的个数为奇数或偶数的规律加上一位校验位ri（i=1，2，3，…，n）。

对于一个信息块，将其分为定长为n位的m段后，二维奇偶校验码不仅对每段信息进行奇偶校验编码，而且同时对m段信息的相应位进行奇偶校验编码。

三者的编码规则是一致的，以垂直奇偶校验码为例，具体的编码规则为

奇校验的校验位可由式（1）求得。

偶校验的校验位可由式（2）求得。

在各种实际应用情况中，一般都是采用奇校验，原因是使用奇校验可以使码字中不存在全“0”代码，在一些场合中就会更加便于判别。

3.2 译码过程

奇偶校验码的译码也非常简单，对于垂直奇偶校验码而言，若经检验该段无差错，我们只需要在接收端将该段的最后一位校验位去掉即可。而对于水平奇偶校验码而言，译码则需等到整个信息块到达且确认无误后进行。若发现信息出错，对一维奇偶校验码而言则需要重传。

二维奇偶校验码译码时也需等到整个信息块到达，然后分别检查各行、各列的校验关系，判断是否有错，若无错则可提取整个信息。若判断有错，在某些情况下可以进行纠错，若无法纠错，则信息块就要重传。

4 奇偶校验码的实现及结果

4.1 一维奇偶校验码的算法

由于水平奇偶校验码的检错能力相对垂直奇偶校验码更优，而且二者编译码方法一致，所以在此我们仅对水平奇偶校验码的实现算法进行设计。

具体的实现过程如下：

1）信息矩阵中暂存所传信息；

2）对m段信息的对应位增加奇校验位；

3）发送信息位；

4）接收端接收整个信息块后，判断信息是否出现误码，如果有误码，转到3），否则继续；

5）删去校验位得到的信息。

4.2 二维奇偶校验码的算法

二维奇偶校验码的检错效果很好，尤其是对突发错误的检查，在一定情况下还可以对这些错误实现纠正，比如在整个信息块中仅发生1个随机错误时是肯定可以纠正的，因此对二维奇偶校验码的实现过程如下：

1）信息矩阵中暂存所传信息；

2）对m段信息的对应位增加奇校验位；

3）发送信息位；

4）接收端接收整个信息块后，判断信息是否出现误码，如果没有误码，则继续执行，如果有误码，再判断误码是否为极少个，如果为否，则转到3），否则对误码进行纠正；

5）删去校验位得到的信息。

4.3 水平奇偶校验码的实现及实现结果

1）水平奇偶校验码的编码实现及实现结果

水平奇偶校验码的编码就是对m段信息的对应位添加校验位，此处选择奇校验，假设有8个字节，具体实现代码如下：

int i=0，j=0；//i代表列，j代表行

while（i＜8）

｛

c=0；

while（j＜8）

｛

if（I［j］［i］==1）

c++；

j++；

｝

if（c%2==0）

R［i］=1；

else

R［i］=0；

i++；

｝

编码实现结果如图1所示，发送时只需将信息块按段发出，校验位一般位于最高位，应当首先发送。

2）水平奇偶校验码的检错功能实现及实现结果

水平奇偶校验码的检错功能优于垂直奇偶校验码的原因就是其可以对突发错误的进行检测。接收端可完成水平奇偶检验码的检测功能，具体实现如下：

int i=0，j=0；//i代表列，j代表行

while（i＜=7）

｛

c=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c++；

j++；

｝

if（c%2==0）

temp=1；

else

temp=0；

if（R［i］==temp）

printf（“段信息对应第%d位无差错 ”，n）；

else

printf（“段信息对应第%d位出错 ”，n）；

i++；

｝

图1 水平奇偶校验码编码实现结果

在不出现错误的情况下，也就是不添加模拟信道出错的代码，则可得到如图2的结果。

图2 水平奇偶校验码的检错结果1

若添加模拟信道随机出现突发错误的代码，即如下代码：

srand（（unsigned）time（NULL））；

rand_row=rand（）%8；

rand_col=rand（）%8；

error_c=8-rand_col；

printf（“从%d行%d列开始将连续出现%d个错误 ”，rand_row，rand_col，error_c）；

while（error_c＞0）

｛

if（I［rand_row］［rand_col］==‘1’）

I［rand_row］［rand_col］=‘0’；

else

I［rand_row］［rand_col］=‘1’；

rand_col++；

error_c--；

｝

运行便可以得到如图3的检错结果。

图3 水平奇偶校验码的检错结果2

令信息矩阵随机出现突发错误，最终的检验结果与其出现误码的位置是相同的。

4.4 二维奇偶校验码的实现及实现结果

1）二维奇偶奇偶校验码的编码实现及实现结果

二维奇偶校验码的编码原理与一维奇偶校验码相同，同样假设有8个字节的信息，具体的实现过程如下：

int i=0，j=0；//i代表列，j代表行

while（i＜=7）

｛

c_col=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_col++；

j++；

｝

if（c_col%2==0）

R_col［i］=1；

else

R_col［i］=0；

i++；

｝

printf（“列校验位为： ”）；

while（i＜=7）

｛

printf（“%2d”，R_col［i］）；

i++；

｝

printf（“ ”）；

while（j＜=7）

｛

c_row=0；

while（i＜=7）

｛

if（I［j］［i］==1）

c_row++；

i++；

｝

if（c_row%2==0）

R_row［j］=1；

else

R_row［j］=0；

j++；

｝

printf（“行校验位为： ”）；

while（j＜=7）

｛

printf（“%2d ”，R_row［j］）；

j++；

｝

编码的实现结果如图4所示。

图4 二维奇偶校验码的编码结果

2）二维奇偶校验码的检错纠错实现及实现结果

二维奇偶校验码拥有一定的纠错能力，若发送8个字节的信息，当发生极少数的随机错误，比如1个随机错误，我们就可以确定错误发生的位置，从而进行纠错。检错纠错代码如下：

int i=0，j=0；

while（i＜=7）

｛

c_col=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_col++；

j++；

｝

if（c_col%2==0）

temp=1；

else

temp=0；

if（R_col［i］！=temp）

printf（“%d列出错 ”，i）；

i++；

｝

printf（“ ”）；

while（j＜=7）

｛

c_row=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_row++；

j++；

｝

if（c_row%2==0）

temp=1；

else

temp=0；

if（R_row［j］！=temp）

printf（“%d行出错 ”，j）；

j++；

｝

若发生1个随机错误，可得到如图5的结果。可以看出随机产生1个错误的话，二维奇偶校验码可以得到误码在哪行哪列，从而进行纠正。

图5 二维奇偶校验码的检错纠错结果

5 结语

文章对一维、二维奇偶校验码原理及编译码方法进行了研究，提供了一维及二维奇偶校验码检错能力的算法设计。利用了C语言实现了一维、二维奇偶校验码的检错、纠错功能，得到了比较理想的结果，设计的程序简单有效，易于理解应用，给以后更深入的研究奠定了基础。

［1］韩天荣.奇偶校验码的产生和检验方法［J］.集宁师专学报，2004，26（3）：30-31.

HAN Tianrong.The method of produce and check parity code［J］.Journal of Jining Normal College，2004，26（3）：30-31.

［2］Luděk Dud ácˇek，Ivo Veˇrtát.Multidimensional Parity Check codes with short block lengths［J］.24th Telecommunications forum TELFOR，2016：1-3.

［3］杨鸿文.通信原理［M］.北京：北京邮电大学出版社，2008：467-475.

YANG Hongwen.Communication Fundamentals［M］.Beijing：Beijing University of Posts and Telecommunication Press，2008：467-475.

［4］葛林富.多维奇偶校验码的纠错效果分析［J］.西南交通大学学报，1998（1）：80-83.

GEFulin.Analysis of error correction effect of multidimensional parity codes［J］.Journal of Southwest Jiaotong University，1998（1）：80-83.

［5］唐朔飞.计算机组成原理［M］.北京：高等教育出版社，2006：53-57.

TANG Shuofei.Principles of Computer Composition［M］.Beijing：Higher Education Press，2006：53-57.

［6］严蔚敏，等.数据结构教程（C语言版）［M］.北京：清华大学出版社，2009：103-108.

YAN Weimin.Data structure course（C language version）［M］.Beijing：Tsinghua University Press，2009：103-108.

［7］钱建发.纠错码理论及应用研究［D］.西安：西安电子科技大学，2010：7-9.

QIAN Jianfa.Research on Error-correcting Code and Its Application［D］.Xi'an：Xidian University，2010：7-9.

［8］谭浩强.C程序设计［M］.北京：清华大学出版社，2010，148-152.

TAN Haoqiang.C Program Design［M］.Beijing：Tsinghua University Press，2010，148-152.

［9］邵朝，于凯云.联合迭代均衡译码算法［J］.西安邮电大学学报，2016，21（4）：23-25.

SHAO Chao，YU Kaiyun.Joint Iterative Equalization Decoding Algorithm［J］.Journal of Xi'an Institute of Posts and Telecommunications，2016，21（4）：23-25.

［10］李高和，殷娟娟，程建国.一种新型的随机奇偶校验码［J］.经营者管理，2015（15）：420-420.

LI Gaohe，YIN Juanjuan，CHENG Jianguo.A new Random Parity Code［J］.Manager'Journal，2015（15）：420-420.

［11］曹德胜.纠错码在计算机科学中的应用：离散数学与纠错码［J］.华北矿业高等专科学校学报，2000，2（1）：25-28.

CAO Desheng.The application of error correcting codes in Computer Science：Discrete Mathematics and error correcting codes［J］.Journal of North China Mining College，2000，2（1）：25-28.