几个检错码和分组码技术详解

摘要:编码技术是保障通信信道顺畅的关键技术。奇偶校验码只能发现奇数个错误,不能发现偶数个错误。奇偶校验适合于单独偶发的错码。对于长度不大于列长的突发错误,我们可以用水平一致校验码。方正码除了可以检测出奇数个错误,也有可能发现偶数个错误。G矩阵或H矩阵可以进行线性分组码的编码和译码。

关键词:奇偶校验码;水平一致校验码;方正码;线性分组码

中图分类号:TP393文献标识码:A 文章编号:1009-3044(2010)02-413-03

Several Error Detection Code and Block Code Technology Explained

LI Ling-ling

(Guangzhou Panyu Polytechnic Institute of Information Engineering,Guangzhou 511483,China)

Abstract: Coding techniques to protect the communication channel is smooth key technologies. Parity-check codes can only be found in odd mistake and can not find even a mistake. Parity for the occasional error in a separate code. For the length of not more than a long burst errors out, we can use the same standard checksum. Founder surprisingly few yards apart can detect an error, but also may find that even a mistake. G matrix or H matrix can be linear block code encoding and decoding.

Key words: parity-check codes; the level of the same checksum; founder yards; linear block codes。

1 奇偶校验码算法简介

为使通信信道顺畅,除了降低误码率,好的编码技术十分重要,数据通信采用的是纠错编码技术,常用的是差错控制技术。当信道干扰不严重时且码长较小时,可以用奇偶校验码。我们知道模2加规则:1+1=00+0=01+0=10+1=1

也就是说:

当 nm Cn+Cm=1

当 n=m Cn+Cm=0

利用此原理:

对于偶数校验:信息元Cn-1Cn-2……C2C1,监督元C0=Ci=Cn-1+Cn-2+…+C1

因为: Cn-1+Cn-2+……+C1+C0=0 Ci +C0=0

Ci +Ci +C0=Ci

而根据模2加规则:Ci +Ci =0

从而得到:C0=Ci =Cn-1+Cn-2+…+C1

对于奇数校验:监督元C0=Ci+1=Cn-1+Cn-2+…+C1

因为: Cn-1+Cn-2+……+C1+C0=1 Ci+C0=1

Ci+Ci+C0=Ci+1

而根据模2加规则:Ci+Ci=0

从而得到:C0=Ci+1=Cn-1+Cn-2+…+C1

对于偶数校验,信息元和监督元之和为1代表有错,而对于奇数校验,信息元和监督元之和为0代表有错。很容易看出,奇偶校验码只能发现奇数个错误,不能发现偶数个错误。(当出现奇数个错误,码元之和原来为奇数的就变成了偶数,原来为偶数的就变成了奇数,这就可以发现错误。而偶数个错码,因为不能改变码元的奇偶性,就不能发现错误。)奇偶校验适合于单独偶发的错码。

2水平一致校验码算法简介

对于长度不大于列长的突发错误,我们可以用水平一致校验码。也就是将码元以适当长度化分成小组,各组按行排列,对各行进行奇偶校验,将各监督元附在各行后。但传送时,按列相传。先传第一列,再传第二列,最后传监督元列。如图1所示(各行以偶数校验为例)。

将信息元1100100101101011110001000加入监督元后按列输出:10110100110111 0000001110010111,假设红色加粗字体表示错码,传输时错码被打散,通过传输信道后复原,应用奇偶校验法判断出有错误的组(在接收端去掉监督元)。这个方法可以发现长度不大于列长的突发错误。

3 方正码算法简介

下面介绍方正码,它在水平一致校验码的基础上,在垂直方向对码元进行奇偶校验,如表1所示。

按列或按行传送均可。以按列传送为例:101101100111011101000000111001101110

这种方法除了可以检测出奇数个错误,也有可能发现偶数个错误。因为每行的监督元检测不出本行的偶数个错误,但却有可能由按列的监督元检测出来。应用奇偶校验法判断出有错误的组,在按列传送时找到有错的列,从而发现错码并纠正。该方法适合于仅在一行或一列有奇数个错误的情况。

还有一种方法是将信息元中”1”的数目用二进制表示,作为监督元附加信息元后一起发送。但为减少冗余,只发送前几位。传送时按列传送:1110111001010100000110 10111001001001100100100,如表2所示。

这种方法有很高的检错能力。

还有一种方法,是在编码时保持1的个数为常数,当1的个数不为常数时,说明有错;以此检查出错码。如表3,5单位码,共有25=32个码组,取其中1的个数为3进行传输,C3 5=10,正好传输10个数字。

该方法检错能力较强,能检查出所有非对称性错误,即1错成0和0错成1的不相等的错误。

4 线性分组码算法分析

对于线性分组码,以(n,k)表示,k为信息元,n为码元,那么n-k就是监督元。以(7,3)码为例:以C6,C5,C4,C3,C2,C1,C0表示码组,C6,C5,C4为信息元,那么C3,C2,C1,C0就是监督元,有如下关系:

C3=C6+C4

C2=C6+C5+C4 (1)

C1=C6+C5

C0=C5+C4

(关系式中只能出现1和0,原因就是因为:1+1=0 0+0=01+0=10+1=1所以:2C6=C6+C6=0 3C6=2C6+C6=C6可见:当n为偶数时,nCm=0 当n为奇数时,nCm=Cm)

3个信息元有以下8种排列:(23=8) 其对应的监督元:

C6C5C4 C3C2C1C0

0 0 0 0 0 0 0

0 0 1 1 1 0 1

0 1 0 0 1 1 1

0 1 1 1 0 1 0

1 0 0 1 1 1 0

1 0 1 0 0 1 1

1 1 0 1 0 0 1

1 1 1 0 1 0 0

由(1)式:因为1+1=00+0=0

有: C6+C4+C3=0

C6+C5+C4+C2= 0

C6+C5+C1=0

C5+C4+C0=0

写成矩阵形式:

定义:

H=称H为一致监督矩阵或一致校验矩阵

H矩阵的行数正好为监督元数,列数为码组元数,是(n-k)×n阶矩阵,H可以表示为:

=[P Ir]

可以写成如下表达式:HCT=CHT=0

(7,3)码是7维矢量空间中的一个3维子空间,该子空间含有a0,a1,…,a7即23=8个矢量:a0=0000000;a1=0011101;a2=0100111;a3=0111010;a4=1001110;a5=1010011;a6=1101001;a7=1110100。

其中a1,a2,a4是三个线性无关的矢量:其余5个矢量是它们的线性组合。

(1)式可以改写成:

C6=C6

C5=C5

C4=C4

C3=C6+C4

C2=C6+C5+C4

C1=C6+C5

C0=C5+C4

写成矩阵形式:

即:

G=[IkQ]=

可以看出:PT=QP=QT

由G矩阵或H矩阵可以进行线性分组码的编码和译码。

设发射序列为C,接收序列为R,错误图样E=C-R, 译码的任务就是找到E。定义接收向量R的伴随式S=RHT=(C+E)HT=CHT+EHT= EHT(CHT=0) 可见根据S是否为0,可以进行码字的检错。

参考文献:

[1] 吴玲达,李国辉,杨冰,等.计算机通信原理与技术无线电波传播――原理与应用[M].北京:国防科技大学出版社,2007.

[2] 张辉.现代通信原理与技术[M].陕西:西安电子科技大学出版社,2006.