第3章线性分组码



目前，几乎所有得到实际应用的纠错码都是线性的。线性分组码是整个纠错码中很重要的一类码，也是讨论各类码的基础。它概念清楚，易于理解，而且能方便地引出各类码中广为采用的一些基本参数和名称的定义，因此本章的内容将涉及整个纠错码的基本知识，重点学习线性分组码的构成理论及其编码译码方法。


3.1线性分组码的定义

将信源的输出序列分成长为k的段u=(uk-1，uk-2，…，u1，u0)，序列中的每一分量都是一随机变量。

为了能够纠错，信道编码器(纠错码编码器)按一定的规则将长为k的段u=(uk-1，uk-2，…，u1，u0)编为长为n的码字(码符号序列)c=(cn-1，cn-2，…，c1，c0)(n>k)。码字共有n位，其中k位为信息位，（n-k）位为校验位(监督位)。假设共有M个消息序列，则对应的M个码字的集合{c1,c2,…，cM}称为一个(n,k)分组码，记为C。

注： 以上文中的u=(uk-1，uk-2，…，u1，u0)和c=(cn-1，cn-2，…，c1，c0)，下标采用的是倒序的形式，如果采用顺序的形式如u=(u0，u1，…，uk-2，uk-1)和c=(c0，c1，…，cn-2，cn-1)也是可以的，一般根据需要和方便性来选择使用。

在分组码中，若u与c的对应关系是线性的(可以用一次线性方程来描述)，则称为线性分组码。

对二进制而言，假设ci和cj是(n,k)二进制分组码中的两个码字(或码矢量)，当且仅当ci+cj也是一个码字时，这个码才是线性的； 特别地，当ci=cj时，ci+cj=0。由此可见，二元分组码是线性分组码的充分条件是两个码字的模2和也是码字； 或者说，一个线性分组码，它的子集以外的矢量不能由该子集内的码字相加产生。

根据上面的定义，分组码的线性只与选用的码字有关，而与消息序列怎样映射到码字无关。

例31有一个(5,2)分组码C={00000,01011,10101,11110}，假设消息序列与码字的映射为00→00000，01→01011，10→10101，11→11110，容易验证它是线性的； 如果映射关系变为00→11110，01→10101，10→01011，11→00000,容易验证它仍是线性的。

同时也容易验证第一种映射关系满足如下关系： 如果消息序列u1映射为码字c1，u2映射为码字c2，则u1+u2映射为码字c1+c2。而第二种映射关系尽管是线性的，却不满足上述的映射关系。

满足u1+u2映射为码字c1+c2的关系为线性分组码的特殊关系。一般来说，在线性分组码中，只要全零的消息序列映射为全零的码字，都能满足这种特殊关系。


3.2生成矩阵和校验矩阵

3.2.1生成矩阵

根据线性分组码的定义，可以得出如下所述的一种构成线性分组码的方法。

在(n,k)线性分组码中，取k个消息序列(序列中只含有一位“1”符号)分别为

U1=(1000…00)
U2=(0100…00)
U3=(0010…00)
︙
Uk-1=(0000…10)
Uk=(0000…01)(31)

这k个消息序列的长度都是k位，其对应的码字分别为g1,g2,g3,…,gk-1,gk，均是长度为n的二进制序列,如g=(g11,g12,…,g1n)，这样，对于任意的消息序列u=(u1,u2,u3,…,uk-1,uk)，都可以用行矩阵表示为

u=∑ki=1uiUi(32)


对应的码字为

C=∑ki=1uigi=(c1,c2,…,cn)(33)

定义

G=g1
g2
︙
gk=g11…g1n
g21…g2n
︙︙
gk1…gkn(34)

为该分组码的生成矩阵，则有

C=uG(35)

对于某(7，3)线性分组码，u=(u2，u1，u0)，C=c6，c5，c4，c3，c2，c1，c0，若c6=u2，c5=u1，c4=u0，按以下的编码规则(校验方程)可得到4个校验元c0、c1、c2和c3。

c3=u2+u0c2=u2+u1+u0c1=u2+u1c0=u1+u0

由此可计算得到该(7，3)线性分组码的8个码字，8个信息组与8个码字的对应关系见表31。由此方程可见，信息元与校验元满足线性关系。


表31(7，3)码字与信息组的对应关系



信息组
码字信息组
码字
00000000001001001110
00100111011011010011
01001001111101101001
01101110101111110100


从表中的8个码字中，挑选k=3个信息组（100）、（010）和（001），其对应的线性无关的码字分别为(1001110)、(0100111)和(0011101)组成G的行，得

G=1001110
0100111
0011101

若信息组为u=(011)，则相应的码字为

C=0111001110
0100111
0011101=0111010

由此可见,生成矩阵G提供了一种简明而有效地表示线性分组码的方法。k×n阶矩阵可以生成2k个码字。因此，我们只需要一个生成矩阵而不需要含2k个码字的查询表。这对大码的储存空间是极大的节省。

实际上，码的生成矩阵还可以由其编码方程直接得出。例如，上述(7，3)线性分组码，c6=u2,c5=u1和c4=u0是三个信息元，按以下的规则(校验方程)可得到4个校验元c0、c1、c2和c3。

c3=u2+u0c2=u2+u1+u0c1=u2+u1c0=u1+u0

可将编码方程改为 

c6=u2c5=u1c4=u0c3=u2+u0c2=u2+u1+u0c1=u2+u1c0=u1+u0

写成矩阵形式为 

c6c5c4c3c2c1c0=c6c5c4c3c2c1c0T=u2
u1
u0
u2+u0
u2+u1+u0
u2+u1
u1+u0T
=u2u1u0100111001001110011101
=u2u1u0·G=u·G

因此生成矩阵为 

G=1001110
0100111
0011101

例32线性分组码为n=7，k=4，记为(7，4)码。

信源符号4位一组为u=(u3,u2,u1,u0),ui∈{0,1},i=0,1,2,3； 

码符号7位一组为c=(c6,c5,c4,c3,c2,c1,c0),cj∈{0,1},j=0,1,2,3,4,5,6； 

若码符号与信源符号的关系为 

c6=u3
c5=u2
c4=u1
c3=u1+u2+u3
c2=u0
c1=u0+u2+u3
c0=u0+u1+u3

式中，c6、c5、c4、c2为信息位，c3、c1、c0为校验位，码符号位是信息位的线性组合，用矩阵表示如下： 

c6c5c4c3c2c1c0=u3u2u1u01001011
0101010
0011001
0000111

G=1001011
0101010
0011001
0000111，即为生成矩阵。

表32列出了按上式生成的16个码字。


表32(7，4)线性分组码



信息组
码字信息组
码字
0000000000010001001011
0001000011110011001100
0010001100110101010010
0011001111010111010101
0100010101011001100001
0101010110111011100110
0110011001111101111000
0111011010011111111111




例33考虑一个生成矩阵G=101
010，信息字为［00］、［01］、［10］、［11］，则有

c1=00101
010=000

c2=01101
010=010

c3=10101
010=101

c4=11101
010=111

因此，这个生成矩阵生成的码为C={000,010,101,111}。

3.2.2校验矩阵

对于前述（7.3）线性分组码，为了更好地说明信息元与校验元的关系，将校验方程重新表述为

c3=u2+u0=c6+c4c2=u2+u1+u0=c6+c5+c4c1=u2+u1=c6+c5c0=u1+u0=c5+c4


变换为

1·c6+0·c5+1·c4+1·c3+0·c2+0·c1+0·c0=0
1·c6+1·c5+1·c4+0·c3+1·c2+0·c1+0·c0=0
1·c6+1·c5+0·c4+0·c3+0·c2+1·c1+0·c0=0
0·c6+1·c5+1·c4+0·c3+0·c2+0·c1+1·c0=0

再用矩阵表示这些线性方程

1011000
1110100
1100010
0110001c6
c5
c4
c3
c2
c1
c0=0
0
0
0=0T

或

c6c5c4c3c2c1c01110
0111
1101
1000
0100
0010
0001=0000=0

将上面的4行7列系数矩阵用H表示

H=1011000
1110100
1100010
0110001

由此可见，若H已知，便可由信息元求出校验元，编码问题迎刃而解； 或者说，要解决编码问题，只要找到H即可。由于(n,k)码的所有码字均按H所确定的规则求出，故称H为它的校验矩阵。
一般而言，对于(n,k)线性码有r=n-k个校验元，则必须有r个校验方程，如果r个校验方程线性独立，此时的校验矩阵称为一致校验矩阵。

(n,k)线性码的H矩阵由r行和n列组成，可表示为

H=h11h12…h1n
h21h22…h2n
︙︙…︙
hr1hr2…hrn

这里hij中，i代表行号，j代表列号。因此H是一个r行n列矩阵。由H矩阵可建立码的r个线性方程，由上可知： 

h11h12…h1n
h21h22…h2n
︙︙…︙
hr1hr2…hrncn-1
cn-2
︙
c1
c0=0T

简写为

HcT=0T

或 

cHT=0(36)

这里c=cn-1，cn-2，…，c1，c0，cT是c的转置，0是一个全为0的r重矩阵。

综上所述，将H矩阵的特点归纳如下：

（1） H矩阵的每一行代表一个线性方程的系数，它表示求一个校验元的线性方程； 

(2) H矩阵的每一列代表此码元与哪几个校验方程有关； 

(3) 由此H矩阵得到的（n,k）分组码的每一码字ci(i=1,2,…,2n)都必须满足由H矩阵行所确定的线性方程； 

(4) (n,k)码须有r=n-k个校验元，故须有r个独立的线性方程。因此，H矩阵必须有r行，且各行之间线性无关； 

(5) 考虑到生成矩阵G中的每一行及其线性组合都是(n,k)码，故有HGT=0T或GHT=0，即生成矩阵G的行与校验矩阵H的行相互正交。由于G是k×n阶矩阵，故H是(n-k)×n阶矩阵，0是一个k×(n-k)阶的全零矩阵。

注： 生成矩阵和校验矩阵是同一个编码方法的不同描述形式。


3.3系统线性分组码

根据对信息元的处理方法不同，可以将纠错码分为分组码与卷积码。

分组码是把信源输出的信息序列，以k个码元划分为一段，通过编码器把这段k个信息元按一定规则产生r个校验(监督)元，输出码长为n=k+r的一个码组。这种编码中每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用(n,k)表示，n表示码长，k表示信息位，如下： 



k个信息码元序列
r个监督码元
r个监督码元
k个信息码元序列

通常称具有上图结构的分组码为系统线性分组码。由图知消息部分可以写在左半边也可以写在右半边，二者的纠错或检错能力是一样的。

系统线性分组码是分组码的一种，其构成应该和分组码一样，但由式c=uG得到的码字是否是上图的结构，将取决于生成矩阵G的结构。

在一般情况下，生成矩阵G是k×n矩阵，可通过初等变换将G变成如下形式： 

G=10…0p11p12…p1(n-k)
01…0p21p22…p2(n-k)
︙︙…︙︙︙…︙
00…1pk1pk2…pk(n-k)=［Ik︙P］(37)

Ik是k×k单位方阵，P是k×(n-k)矩阵(n＞k)，称这种形式的G为标准生成矩阵，因为初等变换不改变矩阵的秩，因此 ［Ik︙P］仍由k个线性无关的行矢量组成。

这样得到的线性分组码的矩阵表示为

c=uG=u［Ik︙P］=(cn-1,cn-2,…,c1,c0)(38)

前面k位cn-1，cn-2，…，cn-k是信息位，后面（n-k）位cn-k-1，cn-k-2，…，c1，c0是校验位，这样的编码即为线性系统分组码。

因为GHT=［Ik︙P］-PT
In-k=0，这时校验矩阵相应地变成

H=［-PT︙In-k］(39)

式中，In-k是(n-k)×(n-k)单位方阵，-PT是矩阵P的逆元转置矩阵，对于模2加运算，0的逆元为0，1的逆元为1，故有-PT=PT，因此

H=［PT︙In-k］(310)

常用的系统码有两种形式： 信息组被排在码字的最左边k位，或信息组被排在码字的最右边k位。

一般来说，系统码的编译码相对非系统码要简单一些，但两者的纠错能力完全等价，因此一般总希望线性分组码采用系统码形式。

例34二元(6，3)线性分组码，下面给出的G1和G2都可以作为它的生成矩阵，即

G1=101011
110101
111000，G2=100110
010011
001101

表33给出了分别由G1和G2所生成的线性码。


表33由不同生成矩阵生成的线性分组码



信息组
由G1生成的(6，3)码
由G2生成的(6，3)码

000
000000
000000
001
111000
001101
010
110101
010011
011
001101
011110
100
101011
100110
101
010011
101011
110
011110
110101
111
100110
111000


从表33可以看出，由G1和G2所生成的线性码对应同一个三维子空间V36，也就是从26个码组中选出23个码组，而且这23个码组相同，只不过信息组与码组之间有着不同的映射关系。

观察由G2所生成的线性码，由

c=uG2
=［u2u1u0］100110
010011
001101
=［u2u1u0u2+u0u2+u1u1+u0］
=［c5c4c3c2c1c0］
得

c5=u2
c4=u1
c3=u0
c2=u2+u0
c1=u2+u1
c0=u1+u0

码组的前3位是信息位，后3位是校验位，因此这样的码是系统码。

例35一个(7，4)线性分组码的生成矩阵为

G=1000101
0100111
0010010
0001010，可知矩阵P=101
111
010
010，它的转置PT=1100
0111
1100。可以得到校验矩阵为

H=［PT︙In-k］=1100100
0111010
1100001

例36对于例32给出的(7，4)线性分组码，生成矩阵

G=1001011
0101010
0011001
0000111初等变换1000111
0100110
0010101
0001011=［Ik︙P］

则校验矩阵为 

H=［PT︙In-k］=1110100
1101010
1011001

生成的码字如表34所示。表中的码字前4位是信息位，后3位是校验位。


表34(7，4)系统码



信息组
码字信息组
码字
0000000000010001000111
0001000101110011001100
0010001010110101010010
0011001111010111011001
0100010011011001100001
0101010110111011101010
0110011001111101110100
0111011100011111111111




3.4对偶码

设原码有k位信息位，其生成矩阵为G，校验矩阵为H，对应的线性码为C。

若用H作为生成矩阵，生成另一码C⊥，则对应的校验矩阵为G，称C⊥为C的对偶码，C⊥有（n-k）位信息位，k位校验位。

因为C⊥=uH，C=uG，C(C⊥)T=uG(uH)T=u(GHT)uT=0,说明互为对偶码的码矢内积为0，即两码矢正交。

例37给定生成矩阵G(7,3)=1001110
0100111
0011101，求由G(7,3)生成的原码C和它的对偶码C⊥。

设u=（u2,u1,u0）,由G（7,3）生成(7，3)线性分组码： 

C=uG(7,3)=u2u1u0·1001110
0100111
0011101
=［u2u1u0u2u0u2u1u0u2u1u1u0］

具体码见表35。


表35由G(7,3)生成(7，3)线性分组码



信息位u2,u1,u0
码矢C信息位u2,u1,u0
码矢C
00000000001001001110
00100111011011010011
01001001111101101001
01101110101111110100


而G(7,3)就是其对偶码C⊥(7,4)的校验矩阵H⊥(7,4)，先将G(7,3)通过初等变换化为校验矩阵的标准形式： 

G(7,3)初等变换1110100
0111010
1101001=［PT︙I3］=H⊥(7,4)

根据H⊥(7,4)可得对偶码的生成矩阵G⊥(7,4)： 

G⊥(7,4)=［I4︙PT］=1000101
0100111
0010110
0001011

设u=（u3,u2,u1,u0）,由G⊥(7,4)生成对偶码： 

C⊥=u·G⊥(7,4)=u3u2u1u0·1000101
0100111
0010110
0001011
=［u3u2u1u0u3u2u1u2u1u0u3u2u0］

具体码见表36。


表36由G⊥(7,4)生成(7，4)线性分组码



信息位u3,u2,u1,u0
码矢C信息位u3,u2,u1,u0
码矢C
0000000000010001000101
0001000101110011001110
0010001011010101010011
0011001110110111011000
0100010011111001100010
0101010110011011101001
0110011000111101110100
0111011101011111111111


可以验证，表35中的任何一个码字与表36中的任何一个码字的内积为0。

若一个码的对偶码就是它自己，则称该码为自对偶码。自对偶码必是（2m，m）形式的分组码。例如(2，1)重复码就是一个自对偶码。


3.5编码的实现

生成矩阵G的行是线性独立的，因此，行的线性组合可以用于生成c中的码字。生成矩阵将是秩为k的k×n阶矩阵，它完整地描述了编码的过程，有了生成矩阵G，编码器的结构就很容易确定，式c=uG事实上给出了编码的实现方法。

当已知(n,k)线性分组码的生成矩阵G或校验矩阵H时，编码问题是容易实现的。

设（n，k）系统码的生成矩阵为

G=10…0p1,n-k-1p1,n-k-2…p1,0
01…0p2,n-k-1p2,n-k-2…p2,0
︙︙︙︙︙︙
00…1pk,n-k-1pk,n-k-2…pk0=［Ik︙P］

若u=(uk-1，uk-2，…，u0)，由于系统码的前k位是信息位，则信息位可表示为u=(un-1，un-2，…，un-k)，相应的码字是

c=cn-1，cn-2，…，c1，c0=uG

于是有，

cj=uj（n-k≤j≤n-1）
cj=un-1p1,j+un-2p2,j+…+un-kpk,j（0≤j≤n-k）(311)

编码实现方法，如果采用硬件实现，电路如图31所示，电路由移位寄存器、模2乘法器和模2加法器等器件组成。在图中，“→□→”表示移位寄存器单元，“→→”表示模2加法器，“→○→”及近旁的P矩阵元素pij表示模2乘法器，对于二元域，pij=1表示该处连通，pij=0表示该处断开。



图31(n,k)线性分组码编码电路


对于例37给出的(7，3)线性分组码，则有，

c=uG(7,3)=u6u5u4·1001110
0100111
0011101
=［u6u5u4u6u4u6u5u4u6u5u5u4］

根据图31的电路，可画出例37给出的(7，3)线性分组码的编码器电路，如图32所示。



图32(7, 3)线性分组码编码电路


在图32中，3位信息u在依次进入移位寄存器的同时也依次进入信道，当3位信息位输入结束后，停止信息输入，同时右边的开关切换到下方，此时图下方的4个模2加法器也已得到了c3，c2，c1和c0，将这4个值存入移位寄存器，然后再依次送入信道，就得到编码c。


3.6线性分组码的译码

3.6.1信息传输系统模型

为了方便研究，将信息传输系统模型简化成图33所示的简化模型。



图33简化的信息传输系统模型


这里信源是指原来的信源和信源编码器，它的输出是二进制信息序列u，纠错编码器按一定的编码规则将u编成码字c送入信道。信道是包括调制器、传输媒质和解调器在内的数字信道(也称编码信道)，它的输入是码字c，输出是接收码字y，纠错译码器根据编码规则对接收码字进行译码，输出估值y^，信宿包括信源译码器和用户，它的输入是经过纠错的估值序列y^。该模型突出了以控制差错为目的的纠错码编码器和译码器，因此也称为差错控制系统。

在译码过程中有两个重要的概念是错误图样和伴随式。

1. 错误图样

定义： e=y-c，称e为错误图样，在二进制中模2加和模2减是相同的，因此有e=y+c和y=e+c。

注： 从发送信息的角度看，错图图样即是噪声（或干扰）图样，因此有y=c+e； 从接收信息的角度看，错图图样即是差错图样e=y-c=y+c。

2. 伴随式

定义： s=HyT(或s=yHT)，称s为y的伴随式。

s=HyT=H(e+c)T=HeT+HcT=HeT

若s=0，根据HcT=0，则y是选用码字，认为传输无误； 若s≠0，则y不是选用码字，说明在传输过程中产生了误码。

从物理意义上看，伴随式s并不反映发送的码字是什么，而只是反映信道对码字造成了怎样的影响。

错误图样e是n重矢量，共有2n个可能的组合，而伴随式s是(n-k) 重矢量，只有2n-k个可能的组合，因此不同的错误图样可能有相同的伴随式。

3.6.2标准阵列
1. 标准阵列定义


线性分组码的n位码符号由k位信息位加上（n-k）位校验位组成，这n位码符号取自符号集a1,a2,…,aq，在整个n维空间Vn中共有qn个矢量(一般q=2)。

线性分组码对应k维子空间Vkn，在k维子空间中，共有2k个矢量，这2k个矢量就是选用码矢或许用码矢，其余（2n-2k）个矢量称为禁用矢量。 

下面将2n个矢量排成标准阵列： 

第1步： 从全零码矢开始，把所有选用码矢{c1,c2,…,cqk}依次写成一行。

第2步： 选一个在第1行中没列出的且重量最轻的禁用矢量y1写在第2行的第1列，其余各列都用y1和第一行对应码矢相加(模2加)。

第3步： 再选一个第1行、第2行没列出的且重量最轻的禁用矢量y2，其余各列都用y2和第一行对应码矢相加(模2加)。

第4步： 如此重复，直至把所有2n个矢量列完。

把这样列出的表格称为标准阵列。取q=2，则2n个矢量列出的标准阵列如表37所示。


表37线性分组码的标准阵列



许用码字
c1（e0）(陪集首)
c2
c3
…
c2k

禁用码字
y1（e1）

y2（e2）

︙

y2n-k-1（e2n-k-1）

y1+c2

y2+c2

︙

y2n-k-1+c2
y1+c3

y2+c3

︙

y2n-k-1+c3
…

…

︙

…

y1+c2k

y2+c2k

︙

y2n-k-1+c2k



例38二元(5,3)码，生成矩阵G=10011
01010
00111，信源有8个消息待发，对应信源编码器的8个输出序列，即{000,001，010,011,100,101,110,111}。根据c=uG编码，得到8个码矢，即

{00000，00111，01010，01101，10011，10100，11001，11110}

按上述方式将25=32个5重矢量排成标准阵列，如表38所示。第一行为8个码矢，其余各行为本行的第一个元素与第一行元素的模2加。


表38将32个5重矢量排成标准阵列



00000
00111
01010
01101
10011
10100
11001
11110
00001
00110
01011
01100
10010
10101
11000
11111
00010
00101
01000
01111
10001
10110
11011
11100
00100
00011
01110
01001
10111
10000
11101
11010


码字c=(c4,c3,c2,c1,c0)，通过有噪信道传输，信道输出y=(y4,y3,y2,y1,y0)，由于信道干扰，y序列中的某些码元可能与c序列中对应码元的值不同，即传输产生了错误。在二进制序列中，错误无非是1错成0或0错成1，因此，信道中的干扰可用二进制序列e=(e4,e3,e2,e1,e0)表示，有错的各位ei取值为1，无错的各位ei取值为0，则有y=c+e，e即为信道的错误图样。

显然，当e=0时，y=c，表示接收序列y无错； 当e≠0时，y≠c，表示接收序列y有错。当c序列长为n时，信道可能产生的错误图样e的数目共有2n种。在此例中n=5，信道可能产生的错误图样e的数目共有25=32种，即表38列出的32个5重矢量都是可能的错误图样。从另一个角度来说，表38列出的32个5重矢量也都是可能的信道输出矢量y。

译码器的任务就是要从收到的y中得到c^，或者说由y中解出错误图样e，然后得到c^=y+e。这里c^是对码字c的估值，若c^=c，则译码正确，否则译码错误。

2. 陪集分解

由标准阵列的构成法，有以下结论： 

(1) 第1行是2k个选用码矢，以后每行都是第1行的陪集，每行的第一个元素称为陪集首，分别记为 e0,e1,e2,…,e2n-k-1，如表37所示； 一个陪集中具有最小重量的向量作为陪集首，如果有多于一个向量具有最小重量，则从中随机选择一个作为陪集首。


(2) 陪集首是前面列出的元素中没有出现过的，从而该陪集中的元素也是前面没有出现过的。

(3) 如果选的陪集首是该行中的另一个元素，则该行中的元素还是原来的2k个元素，只不过排列顺序变了，这说明该行中的每个元素都可以作为陪集首。

(4) 根据(1)和(2)，最后把所有2n个元素全列完(2n-k行×2k列=2n个元素)。

(5) 同一陪集中所有元素的伴随式相同，不同陪集的元素的伴随式不同。

上述(1)、(2)、(3)、(4)条是不言而喻的，下面证明第(5)条。

证明： 
取第i个陪集中的第j个元素ei+cj，根据伴随式的定义，它的伴随式s=H(ei+cj)T=HeTi，可见，s仅与第i个陪集首有关，而与j的取值无关，故同一陪集的元素的伴随式相同。

下面证明不同陪集的元素的伴随式不同，用反证法。

反证法设第i个陪集与第k个陪集的伴随式相同，即HeTi=HeTk，则H(ei+ek)T=0。该式说明ei+ek是一个码矢，即ei+ek=c∈C，则ei=ek+c。

该式表明第k个陪集中有一个元素ek+c与第i个陪集首相同，根据标准阵列的排法，这是不可能的，故不同陪集的元素的伴随式不同。

例39设C为一个二元(3，2)码，其生成矩阵如下： 

G=101
010

即C={000,010,101,111}。C的陪集为 

000+C={000,010,101,111}

001+C={001,011,100,110}

注意所有8个向量都被这两个陪集覆盖了。随便列出一种情况，则

100+C={100,110,001,011}

可以看到这4个向量已在8个向量之中了。

例310考虑某（4，2）码C={0000,1011,0101,1110}。相应的标准阵列为 

码字→0000,1011,0101,1110

1000,0011,1101,0110

0100,1111,0001,1010

0010,1001,0111,1100

↑

陪集首

例311在例38的表38所列的标准阵列中，每行的第一个元素为该行的陪集首，有e0=（00000），e1=（00001），e2=（00010），e3=（00100）。

由矩阵G可得H=11110
10101，根据伴随式的定义，s=HeTi，计算出4个伴随式，即s0=(00)，s1=(01)，s2=(10)，s3=(11)。 

从s=HyT=H(ei+cj)T=HeTi来看，若e=0，则s=0； 若e≠0，则s≠0，伴随式s只由错误图样e决定，即伴随式s是否全为零矢量可以作为判断一个码字传送是否出错的依据。s≠0时，译码器要做的就是如何从伴随式s中找到错误图样e，从而译出发送的码字c^=y+e。

3.6.3译码及纠错能力
1. 用标准阵列译码


由标准阵列的构成可知，第一行为码矢，从第二行开始，每一列与本列的第一行元素都只相差一个陪集首。在标准阵列中出现的2n个矢量都是可能的错误图案，而陪集首选的是本行中重量最轻的矢量，所以y^=y+e就是最小距离译码，即最小错误概率译码。

接收到y后，到标准阵列中去找(因为2n个矢量全部列在其中，总可以找到)，如果接收到的码字是个合法码字，那么可以下结论说没有错误发生(这个结论可能是错的，因为噪声也可能把一个合法码字改变成另一个合法码字，但这种错误发生概率很低)。如果接收到的码字是一个禁用码字，则推测发生了错误。译码器则声明陪集首就是错误图样e，然后译码为y+e，这就是在y同一列中第一行的那个码字。因此，标准阵列译码就是把接收到的码字译为包含该码字的列的第一行的那个码字。

例312考虑码C={0000,1011,0101,1110}，若接收到的码字为y=（1101），因为它不是一个合法的码字，则推测发生了错误。因此要估计4个可能的码字中哪一个是实际被传送的。标准阵列为

码字→0000,1011,0101,1110

1000,0011,1101,0110

0100,1111,0001,1010

0010,1001,0111,1100

可以发现1101在第三列，该列第一行的码字为0101，于是估计码字为0101。进一步可观察到
d(1101,0000)=3，d(1101,1011)=2，d(1101,0101)=1，d(1101,1110)=2。

错误图样e=（1000），即陪集首。说明满足最大似然译码方法。

例313仍考虑例38所述的二元(5，3)码，假设接收矢量为y=（10110），在表38列出的标准阵列中，找到y位于第6列，相应地译成y^=（10100）。错误图样是y=（10110）所在行的陪集首e2=(00010)。

具有较大分组长度的码是可取的，因为大的码在码率方面更接近香农限。但当取越来越大的码长时(大的k值和n值),采用标准阵列方法越来越不实际，因为大小为2n-k×2k的标准阵列将大到不可操作。编码理论的基本目标之一就是要设计有效的译码方法。那么，能不能缩减标准阵列呢？

2. 伴随式与错误位数

伴随式译码与标准阵列的译码相似，伴随式译码的一般步骤如下： 

(1) 计算接收矢量的伴随式。 

(2) 由伴随式找到对应于它的陪集首(即寻找与该伴随式相同的陪集首)。 

(3) 纠正错误y^=y+e，y^即为译码输出的码字。

设(n,k)码的一致校验矩阵为

H=h0,n-1h0,n-2…h0,0
h1,n-1h1,n-2…h1,0
︙︙…︙
hn-k-1,n-1hn-k-1,n-2…hn-k-1,0=［hn-1hn-2…h0］(312)

式中，hn-j（j=0,1,…,n）是H矩阵的第j列，它是一个n-k重列矢量。

设码字传送发生t位错误，为不失一般性，设码字的第j1,j2,…,jt位有错，则错误图样可表示成

e=(0…ej1…0…ej2…ejt…0…0)(313)

在二进制情况下，ej1，ej2，…，ejt为1，那么伴随式

s=eHT
=(0…ej1…0…ej2…ejt…0…0)·hn-1hn-2︙h0
=ej1·hn-j1+ej2·hn-j2+…+ejt·hn-jt
=hn-j1+hn-j2+…+hn-jt(314)

上式说明，s是H矩阵中对应于ej1,ej2,…,ejt为1的那几列hn-j的线性组合，因hn-j是n-k重列矢量，则s也是一个n-k重列矢量。

值得注意的是，若e本身就是一个码字，计算得s等于0。此时的错误不能被发现，也无法纠正，称之为不可检错误图样。

3. 译码表译码

在标准阵列中，每个陪集全部2k个矢量都有相同的伴随式，而不同陪集的矢量有不同的伴随式。这就表明陪集首和伴随式有一一对应的关系，而这些陪集首实际上也就代表着可纠正的错误图样。根据这一关系可把上述标准阵列表进行简化，得到一个简化译码表。

将标准阵列译码和伴随式译码结合起来简化成更为实用的译码表，译码表保留了标准阵列中的2n-k个可纠正错误图样ej(陪集首)与其伴随式s=HeTj之间的一一对应关系，译码器存储该表后，在译码时就可以查表实现从伴随式到错误图样的转换。表39就是表38所列(5，3)线性分组码标准阵列的译码表。


表39(5，3)线性分组码标准阵列的译码表



伴随式s
错误图样(陪集首)e伴随式s
错误图样(陪集首)e
00000001000010
01000011100100


例314仍考虑例38所述的二元(5，3)码，假设接收矢量为y=（10110），计算伴随式

s=HyT=11110
101011
0
1
1
0=1
0

从表39中找到对应陪集首e2为(00010)，则

y^=y+e=1011000010=10100

从表38可知y^就是y所在列的第一个矢量。

用译码表译码，译码正确的概率与陪集首的选择有关。根据最大后验概率译码准则，重量最轻的错误图样产生的可能性最大，所以应该优先选择重量小的n重矢量作为陪集首。这样构造的译码表，使得ej+ci与ci之间的距离最小，从而使译码器能以更大的正确概率译码，这就是最小距离译码。

4. 纠错能力分析

线性分组码的纠错能力t和码字的最小d0有关，一般t是由通信系统提出的，那么寻找满足纠正t个错误码元的码字就是编码技术的任务，为此还需进一步研究d0和码字结构的关系。线性分组码码字的结构是由其生成矩阵决定的，当然也可由一致校验矩阵决定。实际上，所谓检验就是利用H矩阵去鉴别接收矢量y的结构。若已知H矩阵，该码的结构也就知道了。那么从研究码纠错能力的角度来看，d0与H有什么关系呢？

首先，我们来看一个利用伴随式对码字译码的例子。

例315已知(7，3)线性分组码的一致校验矩阵为

H=1011000
1110100
1100010
0110001

对两个码字进行译码c1=(1110100)，c2=(0111010)。我们假设有以下几种传输可能： 

(1) 发送码字在传输中没有发生错误。

即e=(0000000)，此时伴随式为

sT1=HyT1=HcT1=0T

sT2=HyT2=HcT2=0T

(2) 发送码字在传输中发生一位错误。

若e=(1000000)，即传输中码字的第1位出错，则y1=(0110100)，y2=(1111010)，则可根据接收矢量分别计算伴随式，得

sT1=HyT1=1011000
1110100
1100010
01100010
1
1
0
1
0
0=1
1
1
0

sT2=HyT2=1011000
1110100
1100010
01100011
1
1
1
0
1
0=1
1
1
0

若e=(0100000)，即传输中码字的第2位出错，则y1=(1010100)，y2=(0011010)，则同样计算出伴随式，得

sT1=HyT1=0
1
1
1，sT2=HyT2=0
1
1
1

这说明，s的确仅与e有关，而与发送码字无关。此外，对于该(7，3)码，若发生一位错误，计算得到的sT正好与H中的某一列矢量相同。也就是说，如果sT正好与H中的第i列相同，则接收码字的第i位出错。对于第一对接收码字，sT均为H矩阵的第一列，因此有e=(1000000)； 对于第二对接收码字，sT均为H矩阵的第二列，因此有e=(0100000)。这正好与假设的错误图样一致。

(3) 发送码字在传输中发生两位错误。

若e1=(1100000)，则y1=(0010100)，若e2=(0010100)，则y2=(0101110)，根据接收矢量分别计算伴随式，得

sT1=HyT1=1
0
0
1，sT2=HyT2=1
0
0
1

由于s≠0，说明传送的码字有错，但sT与H中任何一列均不相同，说明是不可纠的错误，即无法由s得到e。因为e1=(1100000)，e2=(0010100)，表明这两个接收码字都有两位错误，但各自的错误位置不同。然而，sT1和sT2却相同，这也说明无法由sT确定e。

虽然无法由sT确定e，但是sT与e是有关系的。 e1=(1100000)，表明接收码字第一位和第二位出错，而sT1正好是H中第一列与第二列之和。同样，sT2正好是H中第三列与第五列之和。这即表明sT与e有关系，同时也验证了式（314）。

(4) 发送码字在传输中发生三位错误。

若y1=(0000100)，可判知e=(1110000)，计算伴随式，得

sT1=HyT1=0
1
0
0

由于s≠0，说明传送的码字有错，但此时sT1与H中第五列相等，是否说明是第五位出错呢？显然不是。因为该编码的最小距离为4，由纠错性能与码距的关系可知，该码的纠错能力为纠正一位错误，检测两位或三位错误。同时，也可以分析出sT1是H中第一、第二、第三列之和。

综上所述，一个(n,k)码要能纠正所有单个错误，则由所有单个错误的错误图样确定的s均不相同且不等于0。那么，一个(n,k)码怎样才能纠正小于或等于t个错误呢？这就必须要求所有小于或等于t个错误的所有可能组合的错误图样，都必须有不同的伴随式与之对应。

任一(n,k)线性分组码若要纠正小于或等于t个错误，其充要条件是H矩阵中任何2t列线性无关。

例316以表34给出的(7，4)线性分组码为例。已知该码的校验矩阵H为

H=1110100
1101010
1011001

(1) 若传送时发生一位错误。

设e1=(1000000)，计算伴随式得

s1=HeT1=1
1
1

s1正好就是矩阵H的第一列，在一般情况下，若传送时发生一位错码，如果错的是第j列，则伴随式s恰好就等于矩阵H的第j列。

(2) 若传送时发生两位错误。

设e2=(0001001)，第四位和第七位出错，计算伴随式得

s2=HeT2=0
1
0

又设e3=(1000001)，第一位和第七位出错，计算伴随式得

s3=HeT3=1
1
0

经观察可以发现，s2是H矩阵中第四列与第七列之和，s3是H矩阵中第一列与第七列之和。

(3) 若传送时发生三位错误。

e4=(0111000)，第二位、第三位和第四位出错，计算伴随式得

s4=HeT4=0
0
0

这种情况说明伴随式s4=0，表明无错，但实际情况是发生了错误，这说明三位(及其以上)的错误检测不出来，注意观察可以发现，s4是H矩阵中第二位、第三位和第四位之和。验证了伴随式s是H矩阵中码字出错位置所对应的列矢量的线性组合。

5. 译码后的错误概率

假设有M个码字(长度为n)，它们被使用的概率相同。假设译码用标准阵列。记αi为重量i的陪集首的个数。我们假定信道为二元对称信道（BSC），符号错误概率为p。如果错误图样e不是一个陪集首，则译码出错。因此正确译码概率为


译码后的
错误概率



Pc=∑ni=0αipi(1-p)n-i(315)

故错误概率为

Pe=1-Pc=1-∑ni=0αipi(1-p)n-i(316)

例317考虑码C={0000,1011,0101,1110}，相应的标准阵列为

码字→0000,1011,0101,1110

1000,0011,1101,0110

0100,1111,0001,1010

0010,1001,0111,1100

↑

陪集首

陪集首为0000、1000、0100、0010，可知α0=1(只有一个重量等于零的陪集首)，α1=3(有3个重量等于1的陪集首)，而且所有其余的αi=0（i≥2）。因此，在编码的情况下，错误概率为


Pe=1-Pc=1-∑ni=0αipi(1-p)n-i=1-［α0p0(1-p)4+α1p1(1-p)3］
=1-［p0(1-p)4+3p1(1-p)3］

该码有4个码字，且可用来每次发送两比特。如果不采用编码，n=2，陪集首为00， α0=1(只有一个重量等于零的陪集首)，而所有其余的αi=0（i≥1）。

因此，无编码情况下的错误概率为

Pe=1-Pc=1-∑ni=0αipi(1-p)n-i=1-(1-p)2

若p=0.01，则在编码的情况下，码字出错的概率为Pe=0.01030，而对于无编码的情况Pe=0.0199。因此编码几乎把码字出错概率减小了一半。如图34对有编码和无编码情况下的Pe进行了比较。可以看出，当p=0.5时，编码和无编码的误码率相同，此时任何编码方法都不能降低误码率； 当p<0.5时编码性能优于无编码性能，当p>0.5时编码性能反而劣于有编码性能，出现这种情况的原因与1.5节的译码规则有关。注意编码带来的改进是以信息传输速率的减小为代价的，由于我们对任意两个信息比特都要发送两个校验比特，因此信息传输速率被降低为原来的一半。



图34消息有编码和无编码的误码率比较


例318考虑一个符号出错概率为p=10-7的BSC信道。假设10bit长的码字未经编码就被传输了。设发送端的比特速率为107bit/s，这表明每秒可以发送106个码字。一个码字不能被正确接收的概率为 

10
1(1-p)9p+10
2(1-p)8p2+10
3(1-p)7p3…≈10
1(1-p)9p≈10-6

因此一秒将有10-6×106=1个码字出错!这意味着每秒都有一个错误而且它未被检测到。

下面我们在未编码的码字中加进一个奇偶校验比特使它们变为11bit。该奇偶校验比特使所有码字为偶校验，这样可以确保单个错误被检测到。仅当两个或更多比特有错时译码后的码字才会有错，即至少有两个比特有错。单个比特有错的情况可以以概率1被检测出来。因此码字错误概率将为

1-(1-p)11-11
1(1-p)10p≈1-(1-11p)-11(1-10p)p=110p2=11×10-13

新的码率为每秒107/11个码字，因为每个码字有11bit而比特速率与以前相同。因此1秒将有(107/11)×(11×10-13)=10-6个码字出错。这表明编码后每106秒即大约11.6天将有一个错误码字未被检测而被错误地接收!

可以看出，仅仅把字长从10bit(未编码)增加到11bit(编码)，就能使码字出错概率惊人地减小。


3.7汉明码

汉明码是1951年由汉明提出的能纠正单个错误的线性分组码。它性能良好，既具有较高的可靠性，又具有较高的传输效率，而且编译码电路较为简单，易于工程实现，因此汉明码在发现后不久，就得到了广泛的应用。


3.7.1汉明码的构造

汉明码是一个能纠正单个错误，且信息传输率(码率R=k/n)最大的线性分组码。我们已经知道，具有纠正单个错误能力的线性分组码的最小距离应为3，即要求其H矩阵中至少任意两列线性无关。要做到这一点，只要H矩阵满足“两无”——无相同的列，无全零列就可以了。

一个(n,k)线性分组码的H矩阵是一个(n-k)×n=r×n阶矩阵，这里r=n-k是校验元的数目。显然，r个校验元能组成2r列互不相同的r重矢量，其中非全零矢量有2r-1个。如果用这2r-1个非全零矢量作为H矩阵的全部列，即令H矩阵的列数n=2r-1，则此H矩阵的各列均不相同，且无全零列，由此可构造一个能纠正单个错误的(n,k)线性分组码。

同时，2r-1是n所能取的最大值，因为如果n＞2r-1，那么H矩阵的n列中必会出现相同的两列，这样就不能满足对H矩阵的要求。而由于n=2r-1是n所能取的最大值，也就意味着码率R取得了最大值，即

R=kn=n-rn=1-rn=1-r2r-1(317)

这样设计出来的码是符合要求的，这样的码就是汉明码。

定义31若H矩阵的列是由非全零且互不相同的所有二进制r重矢量组成，则由此得到的线性分组码，称为GF(2)上的(2r-1，2r-1-r)汉明码。 

表310列出了几种r取不同值时汉明码的(n=2r-1，k=2r-1-r)值。


表310几种汉明码的(n，k)值



r
n=2r-1
k=2r-1-r

1
1
0
2
3
1
3
7
4
4
15
11
5
31
26
6
63
57



例319二元(7，4)汉明码的生成矩阵为

G=1101000
0110100
0011010
0001101

相应的校验矩阵为

H=1011100
0101110
0010111

观察到该校验矩阵的列由(100)，(010)，(101)，(110)，(111)，(011)和(001) 构成，这7个是所有长为3的非零二元向量，很容易可以得到一个系统汉明码。该校验矩阵H可以被安排成如下的系统型： 

H=1110100
0111010
1101001=［-PT︙I］=［PT︙I］

于是该二元汉明码的生成矩阵的系统型为

G=I︙P=1000101
0100111
0010110
0001011

例320取r=3，构造GF(2)上的(7，4)汉明码。

当r=3时，有7个非全零的三重矢量

(100),(010),(101),(110),(111),(011),(001)

构成矩阵

H=0001111
0110011
1010101

由此得到一个能纠正单个错误的(7，4)汉明码。若码字传输中左边第一位出错，则相应的伴随式s=(001)就是H矩阵的第一列，也正好是“1”的二进制表示。同理可知，无论哪一位出错，它对应的伴随式就是该位的二进制表示，故译码十分方便，特别适用于计算机内部运算和记忆系统中的纠错。

如果要得到系统码形式的H矩阵，只需对上述矩阵进行初等变换交换列即可，则

H=1110100
1101010
1011001

相应地，生成矩阵G为 

G=1000111
0100110
0010101
0001011

由此构成的(7，4)汉明码如表34所示。


3.7.2汉明限与完备码

一个二进制(n,k)线性分组码，若要纠正t个错误，则应使小于或等于t个错误所组成的所有错误图样，都必须有不同的伴随式与之对应，即不等式成立

2n-k≥n
0+n
1+…+n
t=∑ti=0n
i(318)

式中，2n-k为全部r=n-k重矢量数目，即伴随式数目； ∑ti=0n
i为所有错误个数小于或等于t的错误图样数。

式（318）称为汉明限。该限是构造任何二进制码所必须满足的，也就是构造码的必要条件。

如果某一(n,k)线性分组码能使式(318)等号成立，即错误图样总数正好等于伴随式数目，则称这种码为完备码。完备码相当于在标准阵列中，能将重量小于等于t的所有错误图样作为陪集首，而大于t的错误图样都不作为陪集首，其校验元得到充分的利用。显然无论r取何值，汉明码都是可纠正t=1位错误的完备码。

如果一个(n,k)线性分组码，除了能将重量小于或等于t的所有错误图样作为陪集首外，还有部分(但不是全部)重量大于t的错误图样作为陪集首，则称这种码为准完备码。

表38列出的二元(5，3)码，就不是一个完备码，由它的生成矩阵

G=10011
01010
00111

可得到校验矩阵

H=11110
10101

由此算出l=1(l是H中线性无关的列数)，d=2(d是码的最小距离，d=l+1)，
t=d-12=2-12=0(纠错能力的计算方法)，纠错能力为t=0，除全零码外，标准阵列中还有部分重量等于1的矢量作为陪集首。

例321(7，4)系统码生成矩阵为

G=1000111
0100110
0010101
0001011

校验矩阵为

H=1110100
1101010
1011001

由此算出l=2，d=3，t=d-12=3-12=1，列出它的标准阵列如表311所示。



从表311可看出，上述(7，4)码是完备汉明码。



表311(7，4)系统码的标准阵列



0000000
0001011
0010101
001110
0100110
0101101
0110011
0111000
1000111
1001100
1010010
1011001
1100001
1101010
1110100
1111111

0000001
0001010
0010100
0011111
0100111
0101100
0110010
0111001
1000110
1001101
1010011
1011000
1100000
1101011
1110101
1111110
0000010
0001001
0010111
0011100
0100100
0101111
0110001
0111010
1000101
1001110
1010000
1011011
1100011
1101000
1110110
1111101
0000100
0001111
0010001
0011010
0100010
0101001
0110111
0111100
1000011
1001000
1010110
1011101
1100101
1101110
1110000
1111011
0001000
0000011
0011101
0010110
0101110
0100101
0111011
0110000
1001111
1000100
1011010
1010001
1101001
1100010
1111100
1110111
0010000
0011011
0000101
0001110
0110110
0111101
0100011
0101000
1010111
1011100
1000010
1001001
1110001
1111010
1100100
1101111
0100000
0101011
0110101
0111110
0000110
0001101
0100011
0011000
1100111
1101100
1110010
1111001
1000001
1001010
1010100
1011111
1000000
1001011
1010101
1011110
1100110
1101101
1110011
1111000
0000111
0001100
0010010
0011001
0100001
0101010
0110100
0111111




3.8线性分组码的实现与仿真

利用MATLAB来实现线性分组码的生成矩阵、校验矩阵、编码、译码，可以进一步加深对线性分组码的概念以及实现原理的理解； 通过编程和Simulink对通信过程进行仿真，可以对通信系统的组成及各组成模块之间的关系有较好的掌握； 同时通过仿真可以理解纠错编码在整个通信过程中的重要性。


3.8.1生成矩阵与校验矩阵
1. 从码元符号与信息符号的关系得到生成矩阵


在进行编码时，有时候并不知道编码的生成矩阵，而只知道码元符号与信源符号之间的线性关系，由这些线性关系可以求出生成矩阵。

对于例32，已知码元符号与信源符号的关系，获得生成矩阵的方法如下：

程序3_1(program3_1.m)

%由已知的线性关系得出生成矩阵

%信源符号u=(u3,u2,u1,u0),码符号c=(c6,c5，c4,c3,c2,c1,c0)

%码符号与信源符号的关系为
c6=u3,c5=u2,c4=u1,c3=u3+u2+u1,c2=u0,c1=u3+u2+u0,

%c0=u3+u1+u0

%将码符号的每一位用4位信源符号来表示

c6=［1 0 0 0］； %c6=u3，只与u3有关，对应系数为1，与u2,u1,u0无关，则对应系数为0

c5=［0 1 0 0］； %c5=u2

c4=［0 0 1 0］； %c4=u1

c3=［1 1 1 0］； %c3=u3+u2+u1

c2=［0 0 0 1］； %c2=u0

c1=［1 1 0 1］； %c1=u3+u2+u0

c0=［1 0 1 1］； %c0=u3+u1+u0

G=［(c6)',(c5)',(c4)',(c3)',(c2)'(c1)',(c0)'］； 

运行该程序后，在MATLAB命令窗口(COMMAND WINDOW)输入G，结果如下： 

G =

1001011

0101010

0011001

0000111

2. 从码元符号与信息符号的关系得到校验矩阵

在进行编码时，有时候并不知道编码的校验矩阵，而只知道校验位与信源符号之间的线性关系，由这些线性关系可以求出校验矩阵。

对于3.2.2节内容，已知信息元与校验元的关系，获得校验矩阵的方法如下： 

程序3_2(program3_2.m)

%由已知的线性关系得出校验矩阵

%信源符号u=(u2,u1,u0),码符号c=(c6,c5,c4,c3,c2,c1,c0)

%码符号与信源符号的关系为
c6=u2,c5=u1,c4=u0,c3=u2+u0,c2=u2+u1+u0,c1=u2+u1,

%c0=u1+u0

%则信息元与校验元的关系为
c3=c6+c4,c2=c6+c5+c4,c1=c6+c5,c0=c5+c4

%因二进制数自身相加为0，则有c6+c4+c3=0,c6+c5+c4+c2=0,c6+c5+c1=0,c5+c4+c0=0

%将等式用码符号的7位符号来表示

%c6+c4+c3=0，与c6,c4,c3有关，对应系数为1，与c5,c2,c1,c0无关，则对应系数为0

%1×c6+0×c5+1×c4+1×c3+0×c2+0×c1+0×c0=0

%［1 0 1 1 0 0 0］·［c6 c5 c4 c3 c2 c1 c0］'=0

r3=［1 0 1 1 0 0 0］； 

%c6+c5+c4+c2=0，则1×c6+1×c5+1×c4+0×c3+1×c2+0×c1+0×c0=0

%［1 1 1 0 1 0 0］·［c6 c5 c4 c3 c2 c1 c0］'=0

r2=［1 1 1 0 1 0 0］； 

%c6+c5+c1=0，则1×c6+1×c5+0×c4+0×c3+0×c2+1×c1+0×c0=0

%［1 1 0 0 0 1 0］·［c6 c5 c4 c3 c2 c1 c0］'=0

r1=［1 1 0 0 0 1 0］； 

%c5+c4+c0=0,则0×c6+1×c5+1×c4+0×c3+0×c2+0×c1+1×c0=0

%［0 1 1 0 0 0 1］·［c6 c5 c4 c3 c2 c1 c0］'=0

r0=［0 1 1 0 0 0 1］； 

H=［r3;r2;r1;r0］； 

运行该程序后，在MATLAB命令窗口(COMMAND WINDOW)输入H，结果如下： 

H=

1011000

1110100

1100010

0110001

3. 利用hammgen（）函数产生生成矩阵和校验矩阵

MATLAB有大量的库函数，很方便编程。可以利用MATLAB的hammgen（）函数产生生成矩阵和校验矩阵。

hammgen函数的功能： 产生汉明码生成矩阵和校验矩阵。

语法： H=hammgen(r)； 

［H,G］=hammgen(…)； 

［H,G,n,k］=hammgen(…)；  

说明： 用H=hammgen(r)产生r×n汉明校验矩阵(r为校验位数，n是码长)。

用［H,G］= hammgen(…)产生生成矩阵G和校验矩阵H。

用［H,G,n,k］= hammgen(r)产生生成矩阵G和校验矩阵H，码长n以及信息位长度k。

例如，若r=3，［H,G,n,k］= hammgen(3)。

代码［H,G,n,k］=hammgen(3)运行结果为

H =

1001011

0101110

0010111

G =

1101000

0110100

1110010

1010001

n =

7

k =

4

4. 生成矩阵与校验矩阵的相互转换

如果知道生成矩阵，根据生成矩阵与校验矩阵之间的关系可以求出校验矩阵。同样，如果知道校验矩阵，根据生成矩阵与校验矩阵之间的关系可以求出生成矩阵。

(1) 标准形式的生成矩阵转化为校验矩阵。

实现方法如下：

%标准形式的生成矩阵转化为校验矩阵

G=［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 0 1 0； 0 0 0 1 0 1 0］； %标准形式的生成矩阵

H=gen2par(G)；  %该函数用来将标准形式的生成矩阵转换为校验矩阵

运行结果如下： 

H =

1100100

0111010

1100001

(2) 标准形式的校验矩阵转化为生成矩阵。

实现方法如下：

%标准形式的校验矩阵转化为生成矩阵

H=［1 0 1 1 0 0 0； 1 1 1 0 1 0 0； 1 1 0 0 0 1 0； 0 1 1 0 0 0 1］；  %标准形式的校验矩阵

G=gen2par(H)；  %该函数用来将标准形式的校验矩阵转换为生成矩阵

运行结果如下： 

G =

1001110

0100111

0011101

3.8.2编码

利用MATLAB实现线性分组码编码的方法比较多，我们对其中的几种方法加以介绍。

1. 利用encode函数来实现编码

语法： code=encode(msg,n,k)； 

code=encode(msg,n,k,method,opt)； 

［code,added］=encode(…)； 

说明： 这个函数可完成三种主要的差错控制编码，汉明码、线性分组码、循环码。

code=encode(msg, n, k)对二进制信息msg进行汉明编码。信息位为kbit，码字长为nbit。生成矩阵是系统默认的msg可用一个矢量形式或k列矩阵的形式表达。汉明码是一种可纠正单个错误的线性分组码。

code=encode(msg,n,k,method, opt)是使用这一函数的通用形式。式中，msg是信息； method是编码方式； n是码字长度； k是信息位长度； opt是有些编码方式需要的参数，具体含义如表312所示。


表312encode函数的参数用法



method
含义
opt

'hamming'
汉明编码
可用来指定一个原始多项式，如省略，则使用默认多项式

'linear'
线性分组码
opt必须指定一个校验矩阵
'cyclic'
循环码
必须指定一个生成多项式


在所有编码的方式中，信息位必须以二进制矢量方式或列矩阵的形式表示。

在［code,added］=encode(…)中，输出函数为使输入信息位数达到k时所需添加的列数，添加的信息位是“0”。

code=encode(［1 0 0 1］,7,4)；  %产生（7,4）汉明码，生成矩阵是系统默认的，这里输入的k=4

运行结果如下： 

code =

 0111001

［code,added］=encode(［1 0 0］,7,4)； %这里输入的k=3,编码时添加了1位"0"

运行结果如下： 

code =

 1 101000

added =

 1

下面以线性分组码为例，看看如何使用encode函数。

已知(7，4)线性分组码，其生成矩阵为G=1001011
0101010
0011001
0000111，根据不同的情况分别求编码。

(1) 如果信息序列已知，如m=［1 0 0 1］，采用线性分组码编码，则编码的语句如下：

msg=［1 0 0 1］；  %已知的信息序列

code=encode(msg,7,4,'linear', ［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］)； 

%已知生成矩阵G，调用encode函数进行(7，4)线性分组码的编码

运行结果如下： 

code =

1001100

(2) 如果信息序列是随机产生的，则编码的语句如下：

msg=randi(［0,1］,1,4); %随机产生长度为4的信息序列

code=encode(msg,7,4,'linear', ［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］)；  

%已知生成矩阵G，调用encode函数进行(7，4)线性分组码的编码

运行结果如下： 

msg =

0010(每次运行产生的信息序列不同)

code =

0011001

(3) 如果要随机产生长串的信息序列，则编码的语句如下：

msg=randi(［0,1］,1,1000)； %随机产生长度为1000的信息序列

code=encode(msg,7,4,'linear', ［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］)；  

%已知生成矩阵G，调用encode函数进行(7，4)线性分组码的编码

注： 如果产生的信息序列的长度不是4的整数倍，则编码时会自动在序列的末尾补零。

2. 利用生成矩阵来实现编码

利用encode函数编码，编码过程隐含在encode函数内部，为了加深对编码原理的理解，下面根据编码原理的编码步骤来实现译码。

例322如果生成矩阵为G=1001011
0101010
0011001
0000111，根据不同情况分别求编码结果。

(1) 信息序列m=［1 0 1 1］，求编码后的序列c。则编码的语句如下：

G=［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］； %生成矩阵

m=［1 0 1 1］； %信息码字

c=rem(m*G,2)； %生成码字

disp(c) %显示编码结果

运行结果如下:

1010101

(2) 如果自己设置信息序列，并显示编码结果，则语句如下：

G=［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］；  %生成矩阵

m=input('请输入信息码字： ')；  % 从命令窗口输入参数的函数

c=rem(m*G,2)；  % m与G相乘后进行模2运算

fprintf('编码为： c='） % 输出字符

disp(c)； 

注： 输入的序列必须是矩阵形式的，如［1 0 1 0］，而不能为1010或1 0 1 0。

运行结果如下:

请输入信息码字： ［1 0 1 0］

编码为c=1010010

(3) 如果要得到所有的编码序列，并显示编码结果，则语句如下：

G=［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］；%生成矩阵

%利用循环语句产生所有可能的信息序列

for i=0： 1： 15

a=dec2bin(i,4)；  %将十进制的整数转换为二进制序列

c=mod(a*G,2)； 

disp(a)； 

disp('对应的码字为： ')；  

disp(c)； 

end

运行结果如下： 

0000对应的码字为

0000000

0001对应的码字为

0000111

0010对应的码字为

0011001

0011对应的码字为

0011110

0100对应的码字为

0101010

0101对应的码字为

0101101

0110对应的码字为

0110011

0111对应的码字为

0110100

1000对应的码字为

1001011

1001对应的码字为

1001100

1010对应的码字为

1010010

1011对应的码字为

1010101

1100对应的码字为

1100001

1101对应的码字为

1100110

1110对应的码字为

1111000

1111对应的码字为

1111111

也可以用下面的方法得到所有的码字。

(7,4)分组码，已知校验矩阵，由校验矩阵求出生成矩阵，列出所有的信息码字，求出所有的编码码字。

H = ［1 1 1 0 1 0 0； 0 1 1 1 0 1 0； 1 1 0 1 0 0 1］； %已知校验矩阵

G = gen2par(H)； %调用MATLAB函数求与H对应的生成矩阵

msg = ［0 0 0 0； 0 0 0 1； 0 0 1 0； 0 0 1 1； 0 1 0 0； 0 1 0 1； 0 1 1 0； 0 1 1 1； …

1 0 0 0； 1 0 0 1； 1 0 1 0； 1 0 1 1； 1 1 0 0； 1 1 0 1； 1 1 1 0； 1 1 1 1］； %列出所有信息序列

C = rem(msg*G,2)； 

运行结果如下： 

C =

0000000

0001011

0010110

0011101

0100111

0101100

0110001

0111010

1000101

1001110

1010011

1011000

1100010

1101001

1110100

1111111

3. 利用自定义函数来实现编码

为了方便编码，在已知生成矩阵的情况下可以利用自定义函数来实现编码。

对于(7，4)汉明码，若G=1000101
0100111
0010110
0001011，求编码码字。

方法一
如果给定k位信息，求出相应的n位码字，对应(7，4)汉明编码，实现的方法如下： 

自定义函数：  hmencode74_1.m，即

function bitcoded=hmencode74_1(m)

对输入的任意4位信息序列进行汉明编码，并输出编码序列

G=［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 1 1 0； 0 0 0 1 0 1 1］； %(7,4)汉明码的生成矩阵

bitcoded=mod(msg*G,2)； %编码的码字

disp('编码后序列为： ')； 

disp(bitcoded)； 

程序3_3(program3_3.m)

%该程序调用hmencode74_1.m函数文件，得到编码结果

msg=［1 0 0 1］； %给定的4位信息

bitcoded=hmencode74_1(msg)； %调用编码函数hmencode74_1，得到编码码字

运行结果如下： 

编码后序列为： 

1001110

对于其他的编码方式改变相应的参数和生成矩阵就可以得到相应的编码结果。

方法二
如果给定或随机产生的长串输入信息序列，要求出相应的编码序列，实现方法如下： 

自定义的函数： hmencode74_2.m，即

function bitcoded=hmencode74_2(msg,G,k)

A=vec2mat(msg,k)； %输入的序列转换为矩阵，矩阵的列为k

U=A*G； 

U=mod(U,2)； 

bitcoded=reshape(U',1,［］)； %重新构造为行矩阵输出

disp(bitcoded)； %显示编码结果

程序3_4(program3_4.m)

%该程序调用hmencode74_2.m函数文件，得到编码序列

msg=randi(［0,1］,1,40)； %随机产生的信息序列

G= ［1 0 0 1 0 1 1； 0 1 0 1 0 1 0； 0 0 1 1 0 0 1； 0 0 0 0 1 1 1］； %生成矩阵

k=4； %信息元长度

bitcoded=hmencode74_2 (msg,G,k)； %调用编码函数hmencode74_2，得到编码序列

运行结果如下： 

Columns 1 through 27

010110111000010101

101000000

Columns 28 through 54

011110001100110000

000000000

Columns 55 through 70

0011000010101010

注： 每次运行结果均不相同，因为序列是随机产生的。

方法一和方法二的区别有： 
方法一只能对单个长度为k的信息求编码码字。
方法二不限信息的长度，对输入的任意长串序列进行编码。方法二将生成矩阵、信息长度和编码长度参数都放在程序3_4中，这样更具有通用性，在不用修改函数文件的情况下，只要改变程序3_4中相应的参数，就可以进行其他方式的编码； 如果将生成矩阵、信息长度和编码长度参数都放在encode74_2.m函数文件中，要进行其他的编码，则必须修改函数文件。

3.8.3译码
1. 利用库函数(decode)来实现译码

语法： msg=decode(code,n,k)； 

msg=decode(code,n,k,method,opt1,opt2,opt3,opt4)； 

［msg,err］=decode(…)； 

［msg,err,ccode］=decode(…)； 

［msg,err,ccode,cerr］=decode(…)； 

说明： 这个函数对接收到的码字进行译码，恢复出原始的信息，译码参数和方式必须和编码时采用的严格相同。

msg=decode(code,n,k)是对码长为n，信息位长度为k的汉明码进行译码。

msg=decode(code,n,k,method,opt1,opt2,opt3,opt4)对接收到的码字，按method指定的方式进行译码。opt1，opt2，opt3和opt4是可选项参数，它们的用法如表313所示。

表313decode函数的参数用法



method
含义
opt

'hamming'
汉明译码
opt1可用来指定一个原始多项式，也可省略不用，opt2不用

'linear'
线性分组码译码
opt1必须指定一个校验矩阵，opt2用来指定一个检错逻辑电路，如果省略，则默认单个错纠正逻辑
'cyclic'
循环码译码
opt1是必须指定的生成多项式，可使用cycpoly函数选择一个合适的循环多项式，opt2用来指定一个检错逻辑电路，如果省略，则默认单个错纠正逻辑


译码器输出msg与码字code的格式匹配，当码字是一个n列矩阵时，输出msg信息以k列矩阵表示。当decode函数输入的码字与encode函数的格式不一样时，这个函数停止工作。

用［msg,err］=decode(…)可输出译码过程检测出的错误数。当err为复数时，它表示纠错逻辑对差错控制无能为力了。

［msg,err,ccode］=decode(…)输出纠正的码字。

［msg,err,ccode,cerr］=decode(…)输出ccode每行的错误数。在'convol'方式下，cerr表示输出译码判决的计算尺度，而不是纠错个数。

下面以线性分组码为例，看看如何使用decode函数。

已知(7，4)线性分组码，生成矩阵为G=1000101
0100111
0010010
0001010，在不同的情况下分别求译码结果。

(1) 如果接收到的序列为已知，若r=［1 0 0 1 0 1 1］，进行线性分组码译码，则译码的语句如下：

r=［1 0 0 1 0 1 1］；  %接收到的序列

msg=decode(r,7,4,'linear', ［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 0 1 0； 0 0 0 1 0 1 0］)； %线性分

%组码译码，生成矩阵必须是标准形式的

运行结果如下:

msg =

1001

若r=［1 0 0 1 0 1 0］，则译码的语句如下:

r=［1 0 0 1 0 1 0］；  %接收到的序列

msg=decode(r,7,4,'linear', ［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 0 1 0； 0 0 0 1 0 1 0］)； %线性分

%组码译码，生成矩阵必须是标准形式的

运行结果如下： 

msg =

0001

(2) 如果接收到的码字是随机产生的，则译码的语句如下：

r=randi(［0,1］,1,7)； %随机产生长度为7的接收序列

msg=decode(r,7,4,'linear', ［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 0 1 0； 0 0 0 1 0 1 0］)； %线性分

%组码译码，生成矩阵必须是标准形式的

运行结果如下： 

r =

1111101(每次运行产生的码不同)

msg =

1011

(3) 如果接收到的是随机产生的长串序列，则译码的语句如下：

r=randi(［0,1］,1,1000)； %随机产生长度为1000的信息序列

msg=decode(r,7,4,'linear', ［1 0 0 0 1 0 1； 0 1 0 0 1 1 1； 0 0 1 0 0 1 0； 0 0 0 1 0 1 0］)； %线性分

%组码译码，生成矩阵必须是标准形式的

注： 如果产生的接收序列的长度不是7的整数倍，则译码时会自动在序列的末尾补零。

2. 利用校验矩阵实现译码

利用decode函数译码，译码过程隐含在decode函数内部，为了加深对译码原理的理解，下面根据译码原理的译码步骤来实现译码。

已知校验矩阵H=1110100
1101010
1011001，求接收到码字的译码。

(1) 利用错误图样译码。

程序3_5(program3_5.m)


%(7，4)线性码的译码

% r为接收到的码元，H为监督矩阵

% S为校正子，code为纠错后的码元

r=input('请输入接收到的码元(矩阵形式7位)： ')； %从命令窗口输入接收码字

H=［ 1 1 1 0 1 0 0； 1 1 0 1 0 1 0； 1 0 1 1 0 0 1］；  %校验矩阵

S0=rem(［0 0 0 0 0 0 0］*H',2)； %求错误图样的校正子

S1=rem(［0 0 0 0 0 0 1］*H',2)； 

S2=rem(［0 0 0 0 0 1 0］*H',2)； 

S3=rem(［0 0 0 0 1 0 0］*H',2)； 

S4=rem(［0 0 0 1 0 0 0］*H',2)； 

S5=rem(［0 0 1 0 0 0 0］*H',2)； 

S6=rem(［0 1 0 0 0 0 0］*H',2)； 

S7=rem(［1 0 0 0 0 0 0］*H',2)； 

S=rem(r*H',2)； %模2加

if S==S0

code=bitxor(r,［0 0 0 0 0 0 0］)； %由接收码字和对应的错误图样求码字

end

if S==S1

code=bitxor(r,［0 0 0 0 0 0 1］)；  

end

if S==S2

y1=bitxor(r,［0 0 0 0 0 1 0］)； 

end

if S==S3

code=bitxor(r,［0 0 0 0 1 0 0］)；  

end

if S==S4

code=bitxor(r,［0 0 0 1 0 0 0］)；  

end

if S==S5

y1=bitxor(r,［0 0 1 0 0 0 0］)； 

end

if S==S6

code=bitxor(r,［0 1 0 0 0 0 0］)；  

end

if S==S7

code=bitxor(r,［1 0 0 0 0 0 0］)； 

end

disp('纠错后的码元为： ')； 

disp(code)； 

u=zeros(1,4)； 

u=［code(： ,1),code(： ,2),code(： ,3),code(： ,4)］； %因是系统码，因此原信息码是编码的前4位

disp('原信息码元为： ')； 

disp(u)； 

运行结果如下: 

请输入接收到的码元(矩阵形式7位)： ［1 0 1 0 1 0 1］

纠错后的码元为： 

0010101



原信息码元为： 

0010

(2) 利用校正子和校验矩阵的关系译码。

程序3_6(program3_6.m)

%对接收到的序列进行译码，得到译码后的码字

H =［1 1 1 0 1 0 0； 0 1 1 1 0 1 0； 1 1 0 1 0 0 1］； %校验矩阵

r=input('请输入接收到的码元(矩阵形式7位)： ')； %接收到的码字

S=mod(r*(H'),2)； %S为校正子

E=［1 1 1 1 1 1 1］； %初始化错误图样

%----------------------------------

for i=1： 7%用该for循环取出H中的每一列，然后与S相加

T=H(： ,［i］)； 

%----------------------------------

B1=S+T'； 

B=mod(B1,2)； %S与H的第i列之和

if (all(B(： )==0)) %若S与H的第i列之和B为零矩阵，则表示r中第i个码字有误

fprintf('r序列中错误码位是第： ')； 

disp(i) 

else %如果S与H的第i列之和B不为零矩阵，则表示r中第i个码字无误。

E(1,i)=0； %错误图样第i列为0

end；  

end； 

%----------------------------------

C=mod((r+E),2)； %求出纠错后码字

fprintf('纠错后的码字应该为： C=')； 

disp(C)； 

%----------------------------------

% 显示编码前的原码字

u=zeros(1,4)； 

u=［C(： ,1),C(： ,2),C(： ,3),C(： ,4)］； %因为是系统码，因此原信息码是编码的前4位

disp('原信息码元为： ')； 

disp(u)； 

运行结果如下： 

请输入接收到的码元(矩阵形式7位)： ［1 0 1 0 1 0 1］

r序列中错误码位是第： 3

纠错后的码字应该为： C=1000101

原信息码元为： 

1000

注： 以上两种译码方法对于同样的接收码字［1 0 1 0 1 0 1］，得到的信息码字分别是［0 0 1 0］和［1 0 0 0］，不同的原因是两种编码使用的生成矩阵不同(校验矩阵不同)。

3.8.4通信过程的编程仿真 

纠错编码的目的是提高通信的可靠性，而衡量可靠性的一个重要指标是误码率，误码率越小，系统的可靠性越高。下面就利用MATLAB对通信过程进行仿真，以此来说明线性分组码对通信系统性能的改善。

1. 采用encode、decode函数进行编译码

程序3_7(program3_7.m)


%(7，4)汉明编码性能(纠错后还原为信息序列，与原信息序列进行比较)

bits=100000； %符号数

msg=randi(［0,1］,bits,1)； %随机产生的信息序列

%----------------------------------

SNR=0： 1： 12；  %信噪比

L=length(SNR)； 

BER1=zeros(1,L)； 

BER2=zeros(1,L)； 

%----------------------------------

modbit1=pskmod(msg,2)；  %PSK调制

%----------------------------------

for k=1： L%未编码的序列，调制后经过高斯白噪声信道，再解调制，求误码

y1=awgn(modbit1,SNR(k),'measured')； %在传输序列中加入AWGN噪声

demmsg1=pskdemod(y1,2)； %PSK解调

recode=reshape(demmsg1',1,［］)； %重新构造为行矩阵

error1=(recode~=msg')； 

errornum=sum(error1)； 

BER1(k)=errornum/length(msg)； 

end

%----------------------------------

code=encode(msg,7,4,'hamming')； %(7，4)汉明编码

modbit2=pskmod(code,2)； %PSK调制

%----------------------------------

for k=1： L%编码的序列，调制后经过高斯白噪声信道，再解调制，再纠错后求误码

y2=awgn(modbit2,SNR(k),'measured')； %在传输序列中加入AWGN噪声

demmsg2=pskdemod(y2,2)； %PSK解调

recode=reshape(demmsg2',1,［］)； 

bitdecoded=decode(recode,7,4,'hamming')； %汉明译码

%----------------------------------

%计算误码率

error2=(bitdecoded~=msg')； 

errorbits=sum(error2)； 

BER2(k)=errorbits/length(msg)； 

end

%----------------------------------

semilogy(SNR,(BER1),'b-*') %画图

hold on

semilogy(SNR,(BER2),'r-o')

grid on

legend('未编码','(7，4)汉明编码')； 

xlabel('SNR/dB')； 

ylabel('BER')； 

title('(7，4)汉明编码性能')； 

运行结果如图35所示。



图35(7，4)汉明编码性能


由图35可见，采用(7，4)汉明编码后，通信系统的误码率大大降低。误码率的大小与多种因素有关，如编码方法、信道噪声、调制方式等，改变编码过程中相应的参数，则误码率也跟着发生改变。

2.  编程实现编译码

程序3_8(program3_8.m)

%(7，4)汉明编码性能(包含编码和译码的过程)

bits=100000； %符号数

msg=randi(［0，1］,bits,1)； %随机产生的信息序列

%----------------------------------

G=［1 1 1 1 0 0 0； 1 0 1 0 1 0 0； 0 1 1 0 0 1 0； 1 1 0 0 0 0 1］； %生成矩阵

H=［1 0 0 1 1 0 1； 0 1 0 1 0 1 1； 0 0 1 1 1 1 0］；  %监督矩阵

Et=［0 0 0 0 0 0 0； 

0 0 0 0 0 0 1； 

0 0 0 0 0 1 0； 

0 0 0 0 1 0 0； 

0 0 0 1 0 0 0； 

0 0 1 0 0 0 0； 

0 1 0 0 0 0 0； 

1 0 0 0 0 0 0］； %错误图样

Sm=Et*H'； %对应的伴随式

%----------------------------------

SNR=0： 1： 12；  %信噪比

L=length(SNR)

BER1=zeros(1,L)； 

BER2=zeros(1,L)； 

%----------------------------------

modbit1=pskmod(msg,2)； %调制

for k=1： L%未编码的序列，调制后经过高斯白噪声信道，再解调制，求误码

y1=awgn(modbit1,SNR(k),'measured')； %在传输序列中加入AWGN噪声

demmsg1=pskdemod(y1,2)； %解调

recode=reshape(demmsg1',1,［］)； 

error1=(recode~=msg')； 

errornum=sum(error1)； 

BER1(k)=errornum/length(msg)； 

end

%----------------------------------

%编码

A=vec2mat(msg,4)； %序列转换为矩阵

U=A*G； 

U=mod(U,2)； 

bitcoded=reshape(U',1,［］)； 

%----------------------------------

modbit2=pskmod(bitcoded,2)； %调制

%----------------------------------

for k=1： L%编码的序列，调制后经过高斯白噪声信道，再解调制，再纠错后求误码

y2=awgn(modbit2,SNR(k),'measured')； %在传输序列中加入AWGN噪声

demmsg2=pskdemod(y2,2)； %解调

recode=reshape(demmsg2',1,［］)； 

%----------------------------------

%译码

row=length(recode)/7；%行数

E=zeros(row,7)； %错误图样

RM=zeros(row,7)； %纠错之后的矩阵

R=vec2mat(recode,7)； 

S=R*H'； %伴随矩阵

S=mod(S,2)； 

RU=zeros(row,4)； 

for i=1： row

for j=1： 2^(7-4)%查表纠错

if(S(i,： )==Sm(j,： ))

E(i,： )=Et(j,： )； 

RM(i,： )=R(i,： )+E(i,： )； 

RM(i,： )=mod(RM(i,： ),2)； 

%根据生成矩阵知码的后4位是信息码

RU(i,： )=［RM(i,4),RM(i,5),RM(i,6),RM(i,7)］；%得到原信息码

break； 

end

end

end

bitdecoded=reshape(RU',1,［］)； %转换为比特流

%----------------------------------

%计算误码率

error2=(bitdecoded~=msg')； 

errorbits=sum(error2)； 

BER2(k)=errorbits/length(msg)； 

end

%----------------------------------

%画图

semilogy(SNR,(BER1),'b-*') 

hold on

semilogy(SNR,(BER2),'r-o')

grid on

legend('未编码'，（7，4）编码)

xlabel('SNR/dB')； 

ylabel('BER')； 

title('(7，4)编码性能')； 

运行结果如图36所示。



图36(7，4)汉明编码性能


比较图35和图36可知，这两个仿真图基本上是一模一样的，因为二者仿真条件相同，采用的都是(7，4)码，因此结果一致。不同之处是程序3_7隐藏了编译码的具体过程，由编译码函数实现，而程序3_8将具体的编译码过程写在了程序中。

3.8.5Simulink仿真 

Simulink是实现动态系统建模、仿真的一个集成环境。它的存在使MATLAB的功能得到进一步的扩展。这种扩展的意义表现在以下3方面:

(1) 实现了可视化建模，用户通过简单的鼠标操作就可建立起直观的系统模型，并进行仿真； 

(2) 实现了多工作环境间文件互用和数据交换； 

(3) 把理论研究和工程实现有机地结合在一起。

Simulink为用户提供了用方框图进行建模的图形接口，具有直观、方便、灵活的优点。下面就采用Simulink对通信系统的性能进行仿真。

1. 二进制对称信道中采用线性分组码或汉明码

(1) 利用Display模块显示仿真结果。

在二进制对称信道(BSC)中，采用线性分组码，系统仿真模型(fzm_bsc_1.slx)如图37 所示。



图37BSC信道线性分组码系统仿真模型1




fzm_bsc_1_V


图37中各模块的参数设置如图38~图313所示。


图37中信号源是伯努利随机二进制信号发生器，产生采样时间为1的二进制信号，信息中“0”“1”等价出现，传输环境是差错率为0.01的二进制对称信道。

在发射端和接收端分别设置线性分组码编码器和线性分组码译码器，线性分组码的生成矩阵为

G=1101000
0110100
1110010
1010001


接收端还设置了差错率计算模块，并利用Display模块显示仿真结果。



图38Bernoulli Binary Generator1模块参数




图39BSC模块参数




图310Binary Linear Encoder模块参数





图311Binary Linear Decoder模块参数




图312Error Rate Calculation模块参数





图313Display 模块参数



设置仿真结束时间（Simulation stop time）为1000000，运行图37的仿真模型，结果由显示器（Display）给出。显示器的第一行显示误码率，第二行显示错误符号数，第三行显示总符号数。如果需要缩短仿真时间，则Simulation stop time值可以适当减小，但对于求误码率来说，取值不要小于10000。另外，改变此参数后仿真结果会有微小变化。

虽然因为信道编码的结果使得传输效率变为4/7，即发送7个码元中仅传递了4个码元的有效信息，但使得差错率由0.01降为0.000838。由仿真结果可见，采用线性分组码编码后，通信系统的性能有所改善。

注： 图38和图39中都有参数Initial seed，是产生随机数的初始种子。Initial seed的值可以任意设置，若设置参数改变，产生的随机数跟着改变。对于数量巨大的信息序列来说，不同的序列对仿真的结果几乎没有影响，图38采用了Auto值。图39中的Initial seed设置对仿真结果还是有一定的影响，但影响甚微。

(2) 利用曲线显示仿真结果。

图37仿真模型中利用Display模块显示仿真结果，只能看到当信道差错概率取某个值时的信号误码率。如果想要得到线性分组码的信号误码率与BSC信道差错概率之间的关系曲线，则系统仿真模型如图314(fzm_bsc_2.slx)所示。



fzm_bsc_2_V




图314BSC信道线性分组码系统仿真模型2



图314中主要模块的参数设置如图315和图316所示。其余模块参数设置同前。



图315BSC模块参数





图316To Workspace模块参数



运行程序3_9就可以得到二进制对称信道差错概率与编码后错误率的关系。


程序3_9(program3_9.m)

%二进制对称信道差错概率与编码后错误率的关系

er=0:0.005:0.05;%二进制对称信道信道差错概率的取值范围

%------------------------------------------------------------------

%利用循环语句求错误率

for n=1:length(er)

errB=er(n);

sim('fzm_bsc_2'); %fzm_bsc_2是被调用的仿真模型名

S(n)=［mean(fzm_bsc)］';% fzm_bsc是to Workspace模块变量名

EN(n)=［er(n)］';

end

%------------------------------------------------------------------

plot(EN,S,'b-*');%画图

grid

xlabel('信道差错概率');

ylabel('编码后错误率');

title('二进制对称信道中分组码性能');

运行结果如图317所示。 



图317BSC信道线性分组码性能1


由图317可见，在给定信道差错概率的情况下，线性分组码对通信系统的性能有一定的改善。图314在仿真结束后示波器上显示的数值是信道差错概率取最后一个值时的误码率。

若改变程序3_9中二进制对称信道差错概率的取值范围，则运行结果相应地发生改变。

将程序3_9中的语句“er=0:0.005:0.05;”改为“er=0:0.05:1；”即为程序3_10(program3_10.m)（程序略），运行结果如图318所示。



图318BSC信道线性分组码性能2


由图318可见，尽管采用了线性分组码，但是当信道的差错概率不同时，系统的性能也不同，这是因为误码性能不但与信道的差错概率有关，与编码方式有关，也与译码方式有关。
其实图317是图318中信道差错概率在0~0.05曲线放大。图318也说明，当信道差错概率在0.1~0.9时，编码几乎不起任何作用。
当信道差错概率为0.5时，编码后错误率仍是0.5，此时没有办法判别接收信息的错与对，所以任何编码方式都无能为力。一般情况下，二元对称信道的正确传递概率远大于错误传递概率，仿真结果如图317所示。在后面其他的仿真程序中信道的差错概率的取值也同程序3_9。

注： 程序文件和模型文件必须在同一个文件夹中。

(3) 编码和未编码的性能比较。

为了清楚、直观地表明编码对通信系统性能的改善，我们可以将编码前后的系统性能进行比较。系统仿真模型如图319所示(hm_bsc_bj.slx)。



图319BSC信道汉明码编码前后比较




hm_bsc_bj_V


在BSC信道中，将信道的错误符号概率设为0.01，采用(7，4)汉明编码。由运行结果图319可以看出，编码后的错误率为0.000838； 未编码的错误率为0.01013。编码后误码率大约下降到了一个量级。

如果采用其他的编码方式，改变相应的模块或只改变模块的参数即可。

2. 高斯白噪声信道中采用汉明码

(1) 利用Display模块显示仿真结果。

考虑到实际信道几乎不可能是BSC信道，所以下面在仿真中采用跟实际信道模型更接近的高斯白噪声信道(AWGN)。采用AWGN信道时，在通信系统的发送端必须增加调制模块，同时在接收端必须增加解调模块，如图320所示(hm_awgn_1.slx)。



hm_awgn_1_V




图320AWGN汉明码系统仿真模型1


图320仿真模型中增加了BPSK基带调制和解调两个模块，采用AWGN信道。AWGN信道参数设置如图321所示。



图321AWGN Channel模块参数



仿真模型采用(7，4)汉明编码，AWGN信道的信噪比设置为4，Initial seed为50000运行后的误码率为0.001453，见图320。只改变Initial seed的设置，也会影响运行结果，但影响甚微。

(2) 利用曲线显示仿真结果。

如果想要得到汉明编码的误码率与信道信噪比之间的关系，则仿真模型如图322(hm_awgn_2.slx)所示。



图322AWGN汉明码系统仿真模型2



图322中主要模块的参数设置如图323和图324所示。



图323AWGN Channel模块参数



程序3_11(program3_11.m)

%高斯白噪声信道汉明码性能

SNR=-1:1:8;%信噪比

%------------------------------------------------------------------

for n=1:length(SNR)%误码率计算

snr=SNR(n);




hm_awgn_2_V




图324To Workspace模块参数



sim('hm_awgn_2')

S2(n)=［mean(hm_awgn)］';

S3(n)=S2(n)+eps;

EN(n)=［SNR(n)］';

end

%------------------------------------------------------------------

semilogy(EN,S3,'b-*')%画图

axis(［-1,8,1e-5,1］);grid

xlabel('高斯白噪声信道信噪比SNR(dB)');

ylabel('误码率');

title('高斯白噪声信道汉明码性能');

运行程序program3_11.m，结果如图325所示。




图325AWGN信道汉明码性能


由图325可以看出，误码率随着AWGN信道信噪比的增大而降低。仿真图322中显示的数值是信道信噪比取最后一个值时的误码率。

(3) 编码和未编码的性能比较。

为了清楚、直观地说明高斯白噪声信道中汉明编码对通信系统性能的改善，可以将编码前后的系统性能进行比较。系统仿真模型如图326所示(hm_awgn_bj_1.slx)。



图326AWGN信道汉明码编码前后比较1


图326中，两个AWGN信道的信噪比均设置为4，采用（7,4）汉明编码。由运行结果图326可以看出，未编码的误码率为0.01252，而编码后的误码率为0.001453，采用编码后误码率大约下降了一个量级。

如果要考虑不同信噪比情况下编码对系统性能的改善，仿真模型如图327所示（hm_awgn_bj_2.slx）。



hm_awgn_
bj_1_V




hm_awgn_bj_2




图327AWGN信道汉明码编码前后比较2


程序3_12（program3_12.m）

%高斯白噪声信道汉明码性能

SNR=-1:1:12;%信噪比

%------------------------------------------------------------------

for n=1:length(SNR)%误码率计算  

snr1=SNR(n);

snr2=SNR(n);

sim('hm_awgn_bj_2')

S21(n)=［mean(hm_awgn1)］';

S22(n)=［mean(hm_awgn2)］';

S31(n)=S21(n)+eps;

S32(n)=S22(n)+eps;

EN(n)=［SNR(n)］';   

end

%------------------------------------------------------------------

semilogy(EN,S31,'b-*',EN,S32,'r-o');%画图

axis(［-1,12,1e-5,1］);grid

legend('未编码','(7,4)汉明编码');

xlabel('高斯白噪声信道信噪比SNR(dB)');

ylabel('误码率');

title('高斯白噪声信道汉明码性能');

运行程序program3_12.m，结果如图328所示。



图328AWGN信道汉明编码前后比较


由图328可见，汉明编码对系统的性能有明显的改善。如果采用其他的编码方式，改变相应的模块，或只改变模块的参数即可。

另外，图328和图35都是汉明码对高斯白噪声信道的通信性能的改善，两个图也基本上是一致的，只是二者采用的仿真方法不同。

3.8.6线性分组码电路仿真

对于图32的（7,3）线性分组码的编码电路，其对应的Simulink仿真模型如图329所示（xxfzmdl.slx）。



xxfzmdl_V




图329（7，3）线性分组码的编码电路


图329中采用了多个NSample Switch开关模块，输入端开关参数设置如图330所示，其余略。移位寄存器采用Unit Delay模块，模2加法器采用Logical Operator模块，用Scope模块和To Workspace模块来查看编码序列。



图330输入端的开关设置


输入信息序列采用Repeating Sequence Stair模块，目的是为了得到确定的输入信息，如这里输入信息序列为100，则参数设置如图331所示。




图331Repeating Sequence Stair1模块参数


运行仿真模型，查看示波器的显示和c，可以看出编码结果为1001110，改变输入的信息序列，可以得到相应的编码结果，最终的编码结果与表35一致。

注： 此处的仿真模型只是针对前面讲的线性分组码编码电路的原理进行仿真，与实际通信系统的编码还是有区别的。


习题

1. 某分组码的校验矩阵H=011100
101010
110001，求： 

(1) n=?k=?该码的码字有多少？

(2) 该码的生成矩阵。

(3) 矢量010111和100011是否是码字？

2. 某二元(n,k)系统线性分组码的全部码字为00000，01011，10110，11101,求： 

(1) n=?k=?

(2) 码的生成矩阵G和校验矩阵H。

3. 已知一个线性分组码的校验矩阵H=0111100
1011010
1101001，试求其生成矩阵G。当输入信息序列为1001， 1100， 1101时，求编码器输出的码字序列。

4. 某(5,2)线性分组码的校验矩阵H=11100
10010
11001，求： 

(1) 该码的G矩阵。

(2) 码的标准阵列。

(3) 码的简化译码表。

(4) 该码是否是完备码？

5. 试构造GF(2)上的(15,11)汉明码，求出其系统码形式的H矩阵和G矩阵。

6. 设一个(7,4)分组码的生成矩阵G=1000111
0100101
0010011
0001110，求： 

(1) 该码的全部码字。

(2) 码的标准阵列。

(3) 码的简化译码表。

7. 信源的4个消息{a1,a2,a3,a4}被编成4个码长为5的二元码字00000，01101，10111，11010发送。

(1) 试给出码的生成矩阵G和校验矩阵H； 

(2) 若上述码字通过固有误码率为p<0.5的二进制对称信道传输，请列出其标准矩阵，并计算错误概率Pe。

8. 设二元(6,3)的生成矩阵G=100011
010001
001110，给出它的校验矩阵H，并计算该码的最小距离。

9. 一个(8,4)系统码的编码规则如下： 

c0=u0,c1=u1,c2=u2,c3=u3,c4=u1u2u3
c5=u0u1u2,c6=u0u1u3,
c7=u0u2u3


(1) 写出此码的生成矩阵G和校验矩阵H； 

(2) 计算该码的最小距离d。

10. 设有一个长度为n=15的汉明码，试问其监督位r应该等于多少？其码率等于多少？其最小码距等于多少？试写出其监督位和信息位之间的关系。

11. 利用MATLAB编程实现(3，1)汉明编码。

12. 利用Simulink搭建仿真模型，得到(15，11)汉明码在AWGN信道信噪比为3时的误码率。