第5章
CHAPTER 5



信道编码理论






第4章描述了信源编码理论，包括无失真信源编码和限失真信源编码。但是一般信道中总存在噪声和干扰，这些干扰和噪声会造成信息损失。那么，如何保证在有噪信道中可靠地进行信息传输，怎样才能使消息通过传输后发生的错误最少，传输可达的最大信息传输率又是多少？这些问题属于通信的可靠性问题，是本章要研究的主要内容。
信道编码包括线路编码和纠错编码。由于信号在信道传输时受到干扰，信号码元波形将发生变形，传输到接收端时可能发生错误判断，因而需采用线路编码使之更适合于信道特性或满足接收端对恢复信号的要求，减少信息的损失。另外，若少量错误已经发生，则可通过纠错编码恢复信息。本章主要研究纠错编码，其过程是通过有选择地在数据中引入冗余，以最小冗余的代价获得最佳抗干扰性能，纠正数据传输过程中出现的错误。通常，我们将用于检测差错的编码称为检错码，将可以检测和校正错误的编码称为纠错码。
5.1最佳译码准则
由于信道中存在噪声，因而在有噪信道中传输消息将发生错误。为了减少错误的发生和提高信息传输的可靠性，首先需要分析这些错误与哪些因素有关，有没有办法控制这些错误的发生，以及能控制到什么程度。
很明显，传输信息错误的多少与信道的特性有关，如信噪比较高的信道产生的错误较少。除此之外，错误的产生还与编译码过程有关。图51给出了通信系统的编译码过程。


图51编译码过程



设有噪离散信道的输入符号集为X={a1,a2,…,an}，输出符号集为Y={b1,b2,…,bm}，信道的传递概率为p(Y|X)={p(bj|ai),i=1,…,n; j=1,…,m}。由于噪声的干扰，信道输入符号ai(i=1,2,…,n)时，信道的输出是ai(i=1,2,…,n)或者是该符号的变形bj(j=1,2,…,m)。因此，为了达到通信的目的，必须制定译码规则，也就是设计函数
F(bj)=ai(i=1,2,…,n; j=1,2,…,m)，使它的每个输出符号有且仅有唯一的输入符号与之相对应，该函数被称为译码函数。由于每个输出符号都可译成输入符号中的任何一个，所以共有nm种译码规则。
如果确定了译码规则，那么，当信道输出符号是bj(j=1,2,…,m)时，则一定可以按译码规则译成相应的符号F(bj)=ai(i=1,2,…,n; j=1,2,…m)。当信道的输入符号是ai时，显然是正确译码；  如果不是ai，则就出现译码错误。由此，在信道输出端收到符号bj(j=1,2,…,m)后，正确译码的概率prj就应该是在信道输出端出现bj(j=1,2,…,m)的前提下，推测信道输入符号为ai的后验概率，即


prj=p{{X=F(bj)=ai}|{Y=bj}}(5.1.1)


同时，在信道输出端收到某符号bj(j=1,2,…,m)后，错误译码的概率是pej就应该是在信道输出端出现bj(j=1,2,…,m)的前提下，推测信道输入符号是除了ai以外的其他任何可能的输入符号的后验概率，即


pej=p{{X=ε}|{Y=bj}}(5.1.2)


其中，ε表示除了F(bj)=ai以外的其他可能的输入，显然，式（5.1.2）可改写为


pej=1-prj=1-p{{F(bj)=ai}|bj}(5.1.3)





图52二元对称信道






【例51】设有一个二元对称信道，如图52所示，其输入符号为等概率分布，求译码差错概率的大小。
解：  针对译码规则一：  接收到符号0，译成发送的符号为0；  接收到符号1，译成发送的符号为1。因此当发送符号0时，正确译码的概率为0.1，译错的概率为0.9；  当发送符号1时，正确译码的概率为0.1，译错的概率为0.9。那么，在输入符号是等概率的情况下，平均错误概率为



pe=12(p0+p1)=12(0.9+0.9)=0.9


针对译码规则二：  接收到符号1，译成发送的符号为0；  接收到符号0，译成发送的符号为1。因此当发送符号0时，正确译码的概率为0.9，译错的概率为0.1；  当发送符号1时，正确译码的概率为0.9，译错的概率为0.1。那么，在输入符号是等概率的情况下，平均错误概率为


pe=12(p0+p1)=12(0.1+0.1)=0.1


由此可见，错误概率既与信道的统计特性有关，也与译码规则有关。在例51中，输入符号有0、1两种，输出符号也有0、1两种，所以可以构成nm=22=4种译码规则,分别如下：  
(1) F(0)=0



F(1)=1
(2) F(0)=1



F(1)=0
(3) F(0)=0



F(1)=0
(4) F(0)=1



F(1)=1
译码规则（1）表示信道输出端出现0，则译为0；  信道输出端出现1，则译为1。 
译码规则（2）表示信道输出端出现0，则译为1；  信道输出端出现1，则译为0。
译码规则（3）表示不论信道输出端出现0还是1，都译为0。
译码规则（4）表示不论信道输出端出现0还是1，都译为1。
很明显，不论采用哪一种译码规则，都有可能将输入端的0码在输出端译成1，或者将1译成0。那么，关键问题是选择哪种译码规则可以使平均错误概率最小。

对于通信系统而言，不仅要描述个别的输出符号的正确或错误译码概率，更需要描述在信道的输出端，每收到一个符号的平均正确译码或平均错误译码的概率，即在信道输出端每收到一个符号时，发生正确译码或错误译码的可能性的大小。
在信道输出端，每收到一个Y符号的平均正确译码概率pr，应该是式（5.1.1）所示的后验概率prj(j=1,2,…,m)在信道输出随机变量Y概率空间中的统计平均值，即


pr=∑mj=1p(bj)prj=∑mj=1p(bj)p{{F(bj)=ai}|bj}（5.1.4）


同样，在信道输出端，每收到一个Y符号的平均错误译码概率pe，应该是式（5.1.3）所示的后验概率pej(j=1,2,…,m)在信道输出随机变量Y概率空间中的统计平均值，即


pe=∑mj=1p(bj)pej=∑mj=1p(bj){1-p［(F(bj)=ai)|bj］}

=∑mj=1p(bj)-∑mj=1p(bj)p［F(bj)=ai|bj］

=1-∑mj=1p(bj)p［F(bj)=ai|bj］（5.1.5）


平均错误译码概率pe表示在信道输出端平均每收到一个符号时，产生错误译码的可能性的大小；  pe越大，表示在信道输出端平均每收到一个符号产生错误译码的可能性越大，也就是通信的可靠性越差。所以，pe可以作为衡量通信可靠性的指标。
综上，平均错误译码概率pe取决于变量Y的概率空间、信道的后验概率分布和预先设定的译码规则。因此，对于给定信道，其信道的转移概率是确定的，当信道的输入符号（即信源的输出符号的概率分布）确定后，不同的译码规则就有不同的平均错误译码概率pe，合适的译码规则可以降低平均错误译码概率，因此，制定合适的译码规则成为提高通信可靠性的一种有效手段。
那么，按什么准则来选择译码规则，可使其平均错误译码概率pe达到最小呢？若给定信道的传递概率p(Y|X)={p(bj|ai)，i=1,2,…,n; j=1,2,…,m}，且有0≤p(bj|ai)≤1，(i=1,2,…，n; j=1,2,…，m)；  ∑mj=1p(bj|ai)=1，i=1,2,…，n。可将给定的n×m个传输概率p(bj|ai)（i=1,2,…,n; j=1,2,…,m）排列成信道矩阵如下：


b1b2…bm

P=a1

a2



anp(b1|a1)p(b2|a1)…p(bm|a1)

p(b1|a2)p(b2|a2)…p(bm|a2)

…

p(b1|an)p(b2|an)…p(bm|an)（5.1.6）


可得


p(ai|bj)=p(ai)p(bj|ai)p(bj)=p(ai)p(bj|ai)∑ni=1p(ai)p(bj|ai)（5.1.7）


由给定的信道输入X的概率分布p(X)={p(a1),p(a2),…,p(an)}和信道的传递概率p(Y|X)={p(bj|ai)，i=1,2,…,n；  j=1,2,…,m}，可以求出信道输出随机变量Y的m个概率分量为


p(bj)=∑ni=1p(ai)p(bj|ai),j=1,2,…，m(5.1.8）


式（5.1.8）表明，对于给定信源和给定信道，后验概率和信道输出随机变量Y的概率分布也都是确定的。

现在，我们来看平均错误译码概率，问题是如何选择译码规则F(bj)=ai，j=1,2,…,m; ai∈{a1,a2,…,an}，使平均错误译码概率达到最小值。不同的译码规则，不会引起p(bj)（j=1,2,…，m）和p(ai|bj)（i=1,2,…,n; j=1,2,…,m）的变化。显然，要使pe最小，必须使式（5.1.9）达到最大，即


max∑mj=1p(bj)p{F(bj)=ai|bj},i=1,2,…,n（5.1.9）


因此，必须有


maxp{F(bj)=ai|bj},j=1,2,…，m; i=1,2,…,n（5.1.10）



它是每一个bj（j=1,2,…，m）所对应的n个后验概率p(a1|bj),p(a2|bj),…,p(an|bj)（j=1,2,…，m）中最大的一个值。如果把最大值所对应的信道输入符号记作a*，则有


p(a*|bj)≥p(ai|bj),i=1,2,…,n; j=1,2,…，m（5.1.11）


这就是说，要使平均错误译码概率达到最小，则有


p{F(bj)=ai|bj}=p(a*|bj)≥p(ai|bj),i=1,2,…,n; j=1,2,…，m

（5.1.12）


意味着，必须选择译码规则


F(bj)=a*，j=1,2,…,m（5.1.13）


而信源符号满足


p(a*|bj)≥p(ai|bj),i=1,2,…n; j=1,2,…，m（5.1.14）


这就是最大后验概率译码准则。该准则指出：  若p(a*|bj)≥p(ai|bj)(i=1,2,…，n； j=1,2,…，m）是信道输出端收到符号bj（j=1,2,…，m）后，推测信道输入符号ai（i=1,2,…,n）的n个后验概率p(ai|bj)（i=1,2,…，n; j=1,2,…，m）中最大的一个，即p(a*|bj)≥p(ai|bj)（i=1,2,…，n; j=1,2,…，m）则把接收符号bj（j=1,2,…，m）译成a*，即F(bj)=a*，j=1,2,…,m。用最大后验概率译码准则选择译码函数F(bj)=a*（j=1,2,…,m）构成的译码规则，一定可以使平均错误译码概率pe达到最小值，这是因为


pe=∑mj=1p(bj){1-p［{F(bj)=ai}|bj］}

≥∑mj=1p(bj){1-p［{F(bj)=a*}|bj］}


=∑mj=1p(bj){1-p(a*|bj)}

=∑mj=1p(bj)-∑mj=1p(bj)p(a*|bj)

=1-∑mj=1p(a*bj)=∑ni=1∑mj=1p(aibj)-∑mj=1p(a*bj)

=∑mj=1∑ni=1,ai≠a*p(aibj)=pemin（5.1.15）


由此可见，最大后验概率译码规则使平均错误译码概率达到最小值。因此当信源和信道给定，采用最大后验概率译码准则时，可使通信的可靠性最大。
通常，最大后验概率准则中后验概率的计算存在困难，且不方便。但是，由式（5.1.7）可得


p(a*|bj)=p(a*)p(bj|a*)p(bj)，j=1,2,…,m（5.1.16）


考虑到p(ai|bj)=p(ai)p(bj|ai)p(bj)，则在信道输入符号（信源输出符号）ai（i=1,2,…,n）的先验概率为


p(a1)=p(a2)=…=p(a*)=…=p(an)=1n(5.1.17)


它们与信道的每个输出符号bj（j=1,2,…，m）的n个后验概率p(ai|bj)（i=1,2,…，n; j=1,2,…，m）的大小相比，可以转化为与信道的每个输出符号bj（j=1,2,…，m）相关的n个前向概率（传递概率）p(bj|ai)之间的大小比较，即由


p(a*|bj)=p(a*)p(bj|a*)p(bj)≥p(ai|bj)=p(ai)p(bj|ai)p(bj)（5.1.18）


则有


p(bj|a*)≥p(bj|ai),i=1,2,…，n; j=1,2,…，m（5.1.19）


所以，在信道输入符号ai（i=1,2,…,n）的先验概率等概的条件下，最大后验概率准则等价于最大似然译码准则。显然，最大似然译码准则是在信道输入符号先验概率等概的特定条件下的最大后验概率准则，其平均错误译码概率同样可以达到最小值。
由此可见，在信道输入符号先验概率等概的特定条件下，采用最大似然准则所得到的最小平均错误译码概率取决于等概信道输入所含符号数n和信道的传递特性p(bj|ai)，i=1,2,…，n; j=1,2,…，m。当信道的输入符号数n固定不变时，最小平均错误译码概率随信道传递特性p(bj|ai)（i=1,2,…，n; j=1,2,…，m）的变动而变动，这就为我们提供了一个继续降低最小平均错误译码概率并提高通信可靠性的方法，即在信道的输入符号先验概率等概的条件下，如果信道输入符号数固定不变，则可以通过改变信道的传输特性，使最小平均错误译码概率pemin进一步下降。实际上，这就是抗干扰信道编码的基本理论依据。

对于无记忆信道情形，码字的似然概率应等于组成该码字的各码元的似然概率的乘积（即联合条件概率等于各符号
概率的乘积）。因此，码字的最大似然概率也就是各码元似然概率乘积的最大化，即



maxp(r|Ci)=max∏Nj=1p(rj|Cij)，i=1,2,…,M(5.1.20)


其中，r是信道输出码字矢量，Ci是信道第i个输入码字矢量，码字矢量的长度为N,M是码集中码字矢量的总个数。
为了使乘法运算简化为加法，取似然概率的对数，称为对数似然概率。由于对数函数的单调性，似然概率最大时，对数似然概率也最大化。于是，码字对数似然概率最大化可等效于对数似然概率之和的最大化，即


maxlogp(r|Ci)=max∑Nj=1logp(rj|Cij)，i=1,2,…，M(5.1.21)


式中的对数可以e为底（自然对数），也可以2或10为底，M是码集中码字矢量的总个数。
下面作为一个特例，证明二进制对称信道(BSC)的最大似然译码准则可以简化为最小汉明距离译码准则。
对于BSC信道，当逐位比较发送码和接收码时，仅存在相同或不同两种可能，且两种可能发生的概率与信道的错误转移概率有关，为


p(rj|Cij)=pCij≠rj



1-pCij=rj(5.1.22)


如果r中有d个码元与Ci的码元不同，r与Ci的汉明距为d。显然，d代表在BSC信道传输过程中码元差错的个数，即


d=dis(r,Ci)=W(rCi)=∑Nj=1rjCij，i=1,2,…,M(5.1.23)


M是码集中码字矢量的总个数。此时的似然概率为


p(r|Ci)=∏Nj=1p(rj|Cij)=pd(1-p)N-d

=p1-pd(1-p)N，i=1,2,…,M


其中，M是码集中码字矢量的总个数，(1-p)N是常数。由于
0≤p≤12，导致
p1-p≤1，d越大时，似然概率越小。因此，最大似然函数maxp(r|Ci)的问题转化为求最小汉明距离dmin的问题。

汉明距离译码是一种硬判决译码。只要在接收端将发送码与接收码的各码元逐一比较，选择汉明距离最小的码字作为译码估值，就可以获得最大似然概率译码。由于BSC信道是对称的，因此，当发送的码字独立且等概率时，汉明距离译码是一种最佳译码。
5.2信道编码的基本概念
图53是简化的通信系统模型，其中信道可以是包括调制、解调和传输媒质在内的有线（含光纤）和无线的数字信道，也可以是包括网桥、路由器、网关、电缆（或光缆）和低层协议等在内的计算机通信网的数字信道。


图53简化的通信系统模型



信道编码器将输入的信息序列，每k个信息符号分成一组，记作m，称为信息组，其中的每一位称为信息元mi,i=1,2，…,k。通过信道编码器，产生一个码字C，长度为N，通常将R＝k/N称为码率。码字C在有噪声的信道中传输，接收到r序列，通过信道译码器，获得译码后的信息m^。

5.2.1错误图样

首先了解在有噪信道中产生差错的特点，数据在信道中传输时受到各种干扰，这些干扰是使数据产生差错的主要原因。差错有两种基本形式：  一是随机错误，即数据序列中前后码元之间是否发生错误彼此无关，将产生随机错误的信道称为随机信道，以高斯白噪声为主体的信道就属于这类信道，如太空信道、卫星信道和同轴电缆信道等； 二是突发性错误，即错误之间有相关性，错误成串出现，将产生突发性错误的信道称为突发差错信道，实际的衰落信道、码间干扰信道均属于这类信道，如短波信道和移动通信信道等。

对于二进制数字通信系统，设信道输入的发送序列为C＝0000…，由于干扰，信道输出的接收序列为r=0010…，表明接收序列的第3位发生错误e，即e=r-C，称为
错误图样。由于二进制数字通信系统中加法运算与减法运算等价，因此，e=rC或者r=Ce。若发送序列为00100000…，而接收序列为10111000…，此时错误图样为e=0010000…10111000…=10011000…，这种错误称为突发错误。突发错误的长度l等于第1个错误与最后一个错误之间的长度，该例中突发错误的长度为5。当然，如果获得错误图样e，由接收序列r可计算出发送的信息序列C^=er。

对于二进制对称信道，若信道的错误传递概率为ε，正确传递概率将为1-ε。N长的码字在这样的信道中传输时，发生一位随机错误的差错图样的概率为p(e1)=(1-ε)N-1ε，发生两位随机错误的差错图样的概率为p(e2)=(1-ε)N-2ε2，以此类推，发生k位随机错误的错误图样的概率为p(ek)=(1-ε)N-kεk。由于信道错误传递概率一般总是远小于1，因此有p(eN)<…<p(ek)<…<p(e2)<p(e1)，即发生一位随机错误、两位随机错误的概率将大于发生多位随机错误的概率。因此，无记忆信道中总是优先纠正发生较少位的随机错误。

5.2.2矢量空间和码矢量
信道编码的任务就是通过构造出以最小冗余度为代价换取最大抗干扰性能的好码。码字可被看作一个矢量或一个矩阵，于是可以采用矢量空间的概念研究码的本质特性。

定义5.1：  对于n重有序元素的集合V，V={Vi}，Vi=(
vi1,vi2,…,vin)，vij∈F,j=1,…,n，F表示码元所在的域，对于二进制码，F代表二元域，常用GF(2)表示。若集合V满足以下条件：  
（1） V中的矢量元素在矢量加运算下构成加群；  
（2） V中的矢量元素与数域F元素的标乘封闭在V中；  
（3） 分配律和结合律成立。


则称集合V是数域F上的n维矢量空间，或称n维线性空间。n维矢量也称为n重(ntuples)矢量。
另外,GF(q)域，又称伽罗华域（Galois Field），是由符合上述运算规则的δ个元素构成的q元有限域，其域元素为{0,1,…,q-1}。与q元域对应的加、乘运算为模q运算。如果q=pm(p是素数，m是任意正整数)，则有可能将GF(q)域扩展成GF(qm)，称为GF(q)的扩域。扩域中元素的乘、加运算也是基于模q运算。
值得注意的是，域里面的乘法和加法不一定是我们平常使用的乘法和加法。
对于域F上的若干矢量V1,V2,…,Vi及Vk∈V，若满足Vk=a1V1+a2V2+…+aiVi(ai∈F)，则称Vk是V1,V2,…,Vi的线性组合。
对于域F上的若干矢量V1,V2,…,Vi∈V，若满足a1V1+a2V2+…+aiVi=0，其中ai∈F不全为零，则称V1,V2,…,Vi是线性相关的；  如果上述条件不成立，则称这些矢量是线性无关或线性独立的。
定义5.2：  如果存在一组线性无关的矢量V1,V2,…,VK，这些矢量的线性组合的集合可构成一个矢量空间，则称这组矢量为该矢量空间的基底。n维矢量空间应有n个基底，也可以说，n个基底张成n维矢量空间。

以n个线性无关的矢量为基底，它们的全部线性组合可构成一个n维n重矢量空间S，这里n重指n个GF(q)域元素的有序排列。如果从n个基底中选出k(k<n)个基底，则它们的所有线性组合也构成一个集合，这个集合是S的一个k维子集，称为k维n重子空间，记作SC。

【例52】二元域GF(2)上三维矢量空间V的3个自然基底为(100)，（010），（001），求它的一维三重子空间和二维三重子空间。

解：  由于三维矢量空间有3个基底，任取其中一个基底，可以张成一维三重子空间。例如，取基底(100)，则可张成一个子空间，含有21=2个元素，即V1={(000),(100)}。以(010)(001)为基底，可以张成一个二维三重子空间，共有22=4个元素，即V1={(000),(001),(010),(011)}。

【例53】求二元扩域GF(23)上的域元素。
解：  扩域GF(23)上的域元素可表示成多项式
f2x2+f1x+f0，f2,f1,f0∈GF(2)，其可对应到三维矢量(f2,f1,f0)，其自然基底是(100)，(010)和（001）。由于每个系数只有{0，1}两种选择，自然基底只能组合出8个矢量，构成GF(2)上的三维矢量空间。

每个矢量可对应一个码字，所以也可把矢量说成是码矢、码字，或一个n重矢量。如果两矢量的内积为零，则称为矢量正交。如果一矢量空间中的任一矢量都与另一矢量空间正交，则两个空间称为对偶空间，其中一个空间是另一个空间的零空间(又称零化空间)。
n维n重空间S中含有2n(二进制分组码)个长度为n的矢量，其中至少存在一组n个矢量B1,B2,…,Bn可用作基底，n维n重空间的所有矢量都是这些基底的线性组合，α1B1+α2B2+…+αnBn，

图54信道编码方法
αi∈{0,1}，i=1,2,…,n。若n个基底相互正交，将n个基底分成k个和n-k个两组，则可分别张成k维n重和(n-k)维n重的两个对偶空间，若将k维n重空间作为码空间C，则(n-k)维n重空间
可用作检验空间H。纠错编码过程就是将k维k重空间通过一定的映射法则，映射到n维n重空间的一个k维n重子空间上，其过程如图54所示，它的核心是：  ①确定码空间，选择k个正交基底B1，B2，…，Bk张成码空间；  ②确定映射法则。


分组码由一组固定长度为N的码矢量构成。每个矢量元素就是一个码元，其值选自GF(q)域中的元素。长度为N的二进制分组码有2N种可能的组合，选择其中的2k种(k<N)构成一个许用码的码集C称为分组码。因此，分组码的编码就是将k位的信息组一一对应地映射到许用码码集，不同的编码算法对应不同的映射方法，这样的分组码又称为(N，k)分组码，并定义k/N=R为码率。

假设Ci和Cj是某(N，k)分组码的两个码字，a1和a2是码元字符集里的任意两个元素，那么，当且仅当a1Ci+a2Cj也是码字时，
该码称为线性码。因为a1=0,a2=0,a1Ci+a2Cj=0。因此，线性码必须包含全零码字。
5.2.3码距与纠检错能力

假设一个码字C=(C1,C2,…,CN)（i=1,2,…,M，M为码集中码字总个数）可以被看作一个N重矢量，每个码字与N维矢量空间2N中的一个点对应（二进制码字），全部码字所对应的点的集合构成矢量空间里的一个子集，即k维N重子空间。若Ci和Cj是码集上的任意两个有效码字，则它们间的汉明距离定义为两码字中不相同元素的个数，即D(Ci,Cj)=∑Nk=1CikCjk（i,j=1,2,…,M,M为码集中码字总个数），所有码集中汉明距离的最小值称为最小码距，记作dmin。当传输没有差错时，接收到的N重矢量对应到该子集相应的有效码字（许用码集的有效点）上。但当出现差错时，接收到的N重矢量会有两种可能性：  一种是不再对应到该子集，而是对应到另外一个空间；  
另一种仍然是对应到该子集，却对应到该子集另外的有效点上。
通过前一种情况
能够判断出该码字出现了差错，而后一种情况将无法做出判断。若码集的最小距离为dmin，那么一个能使码字矢量空间点偏移dmin的差错组合（称为重量为dmin的
错误图样），会将码字矢量的空间点位置从子集的一个有效点偏移到另一个有效点上，从而产生一个“不可检测的差错”。但是，如果差错数小于dmin，就不可能将码字矢量空间点从子集的一个有效点偏移到子集的另一个有效点上，也就可以检测出差错的存在。因此，对于(N，k)分组码来说，最多能够检测出dmin-1个错误。

码的纠错能力同样也取决于码的最小距离。为了确定（N，k）分组码的纠错能力，一种简单的办法是将2k个码字看作位于n维空间上的点。如果以子集中每个有效码字为球心，以汉明距离t为半径做2k个球体，那么它们之中任意一对球体两两不相交（包括不相切）的t的最大取值为t=dmin-12，其中·表示向下取整。那么，在每一个球内（含有与该码字之间的距离小于t的所有可能）的接收码字，被译成位于球心的那个有效码字。最小距离为dmin的分组码的纠错能力为t=dmin-12，且纠错能力总是小于检错能力。

如上所述，分组码如果单独考虑检错或单独考虑纠错，则可以检测dmin-1个错误或纠正t=dmin-12个错误。然而，如果将两种能力放在一起考虑，情况就有所变化。能纠正t个错误显然能够检测t个错误，但如果想检测dmin-1个错误就必须对纠错能力有所抑制。例如，假设两个码字A、B的码距为7，即dmin为7，若码字A发生3个错误时能够纠正过来，若发生4个错误，按照前面的方法应译成码字B。这是因为译码器认为接收点是由码字B发生3个错误而来的，而不认为是码字A发生了4个错误所导致。换言之，此时译码器的检错能力仅是3。如果要有4个错误的检测能力，只能把球的半径从3减到2。这样，错误数不大于2的接收码可以纠正，错误数为3个或4个时可以检测，而4个以上的错误可能是接收点落在别的球内，将变成不可检测错误。同理，保持dmin＝7不变，也可以检测5个错误、纠正1个错误。一般性的结论是：  如果最小距离为dmin的码字能同时检测e个错误，纠正t个错误，
则dmin≥e+t+1，e≥t。
对于线性码而言，码距特性就是码的重量特性。如果有2k个码字，就存在2k(2k-1)/2个距离，这些距离是大小不一的，码的总体性能取决于这些距离的分布特性，而纠错能力取决于其中的最小值dmin。正如各符号等概率时熵最大一样，当所有的码距相等时，码的性能将是最好的。
5.3离散信道编码定理
1948年，香农在他的论文中给出了有关信息传输的基本定理，称为有噪信道编码定理。尽管他没有给出定理的严格证明过程，但他引入的随机编码方法在后来的信道编码定理的严格证明中一直被采用，因而，下面首先介绍随机编码的概念。

按照分组码的编码方法，编码器要对每一消息m（m=1,2,…,M）给以相应长为N的码字Cm=Cm1Cm2…CmN。随机编码的思想就是按照信道输入符号的概率分布完全随机地选取码字母表中的字母作为码字的符号，从码字C1的第1个码符号C11开始直到码字CM的最后一个码符号CMN为止，以这种方式得到全部M=2NR的有效码字，组成一个码集C={C1,C2,…,CM}。于是，随机编码产生某一特定码字C的概率p(C)是


p(C)=∏Mm=1∏Nl=1p(Cml)（5.3.1）


所有可能产生的码的总数应是|A|MN，其中|A|表示码字母表A的大小。例如，当|A|=2,N=16,M=28时，码集中码字的总数为216×28=24096≈101233，这是一个很大的数。当然，在这些码集中有一部分是无法使用的，例如，码集中有若干码字相同，但由于码集中码字数为M=2NR只占全部可能序列数2N的很小的一部分，因此同一码集中码字相同的概率很小，大部分码集中的码字各不相同。
5.3.1有噪信道编码定理

定理5.1：  有噪信道编码定理：  设离散无记忆信道的容量为C容量，信道的信息传输率为R。只要R<C容量，总存在码长为N、码字数M=2NR的分组码和相应的译码规则，使译码的平均错误概率e<ε，ε是大于零的任意小量。

证明：  按照随机编码的方法，随机地产生M=2NR个码字，记为Cm=Cm1Cm2…CmN，m=1,2,…,M，其概率分布为p(Cm)=∏Nl=1p(Cml)。若将这M个码字排在一起，构成如下矩阵：  


C=C1

C2



CM=C11……C1N





CM1……CMN（5.3.2）


从而产生一个特定码字C的概率是p(C)=∏Mm=1∏Nl=1p(cml)。令输入消息等概率分布，即p(Cm)=1M,m=1,2,…,M，则特定码字C的平均错误概率是


pe(C)=∑Mm=1p(Cm)p(e|Cm)=1M∑Mm=1p(e|Cm)（5.3.3）


在全体码集{C}上对pe(C)取平均，得到全码集{C}上的平均错误概率为


p-e=∑|C|p(C)pe(C)=1M∑Mm=1∑|C|p(C)p(e|Cm)（5.3.4）


其中，|C|表示全码集中码总数。在随机编码中，不同Cm产生的方法完全一样，因此p(e|Cm)在对码集{C}取平均后将得到一个与m无关的值，即∑|C|p(C)p(e|Cm)的值与m无关,且设m=1，得到


p-e=∑|C|p(C)p(e|C1)（5.3.5）


设y是发送C1码字时经信道输出后接收到的序列，定义y与Cm构成联合典型序列事件Em，即Em={(Cm,y)∈TXY(N,ε)}，m=1,2,…,M，TXY（N，ε）为输入输出联合典型序列。X表示输入，Y表示输出。按照联合典型译码法则，译码错误将使y不与C1成为联合典型，或y与C1以外的其他码字产生联合典型序列的概率，故


p-e=p(EC1∪E2∪…∪EM)≤p(EC1)+∑Mm=2p(Em)（5.3.6）


由于y是对应输入C1时的信道输出，所以它与C2,C3,…,CM相互独立，故可得


p-e≤ε1+∑Mm=22-N［I(X: Y)-3ε1］

=ε1+(M-1)2-N［I(X: Y)-3ε1］

≤ε1+2NR2-N［I(X: Y)-3ε1］

=ε1+2-N［I(X: Y)-R-3ε1］（5.3.7）


当I(X: Y)-R-3ε1>0，即I(X: Y)>R时，存在充分大的N，使2-N［I(X: Y)-R-3ε1］<ε1，从而


p-e<ε1+ε1=2ε1（5.3.8）


如果取输入分布p(ak)是达到信道容量C容量的分布，则此时I(X; Y)=C容量，于是当R<C容量时，对任意的ε=ε12>0，总存在充分大的N，使p-e<ε。由于{C}是随机码集合，因此至少存在一个码C∈{C}，使其平均错误概率满足p-e<ε。

香农只是证明了满足这种特性码的存在性，还不能按照他的证明方法得到很好的编码方法。由于随机编码所得到的码集很大，通过搜索得到好码的方法在实际中很难实现；  而且即使找到其中的好码，这种好的码字也是毫无结构的，这意味着译码时只能用查表的方式，在N很大的情况下，这一译码表所需要的存储量是难以接受的。因此，真正实用的信道编码还需要通过各种数学工具来构造，使码具有很好的结构以便于更好地译码。

5.3.2有噪信道编码逆定理

我们知道平均错误概率p-e与译码规则有关，而译码规则又由信道特性决定。由于信道中存在噪声，导致信道输出端出现错误，所以接收到输出符号后，对发送的是什么符号仍存在不确定性。因此，平均错误概率p-e与条件熵H(X|Y)之间有一定关系，这就是费诺（Fano）不等式，该不等式也是有噪信道编码逆定理证明的基础。

设离散无记忆信道的输入随机变量X取值于符号集A={a1,a2,…,ar}，输出随机变量Y取值于符号集B={b1,b2,…,bs}，p-e为某一译码规则的平均错误概率，则


H(X|Y)≤H(p-e,1-p-e)+p-elog(r-1)（5.3.9）


称为费诺不等式，其中H（·）为信息熵。此处p-e可以同pe。
证明：  由式（5.1.15）得


pe=∑sj=1∑rk=1,ak≠a*p(akbj)

1-pe=∑sj=1p(a*bj)


因此,


H(pe,1-pe)+pelog(r-1)=pelog1pe+(1-pe)log11-pe+pelog(r-1)

=∑sj=1∑rk=1,ak≠a*p(akbj)logr-1pe+∑sj=1p(a*bj)log11-pe


而


H(X|Y)=∑rk=1∑sj=1p(akbj)log1p(ak|bj)

=∑sj=1∑rk=1,ak≠a*p(akbj)log1p(ak|bj)+∑sj=1p(a*bj)log1p(a*|bj)


则


H(X|Y)-H(pe,1-pe)-pelog(r-1)

=∑sj=1∑rk=1,ak≠a*p(akbj)logpe(r-1)p(ak|bj)+∑sj=1p(a*bj)log1-pep(a*|bj)

≤∑sj=1∑rk=1,ak≠a*p(akbj)pe(r-1)p(ak|bj)-1loge+∑sj=1p(a*bj)1-pep(a*|bj)-1loge

=per-1∑sj=1∑rk=1,ak≠a*p(bj)-∑sj=1∑rk=1,ak≠a*p(ak,bj)+(1-pe)∑sj=1p(bj)-


∑sj=1p(a*bj)loge

=per-1(r-1)-pe+(1-pe)-(1-pe)loge

=0



其中用到了不等式lnx≤x-1。由此证得费诺不等式：  H(X|Y)≤H(pe,1-pe)+pelog(r-1)。
下面给出有噪信道编码逆定理。

定理5.2：  有噪信道编码逆定理：  设离散无记忆信道的容量为C容量，R是消息传输率，则当R>C容量时，无论码长N有多长，必存在某一常数δ>0，使在码字等概率分布下平均错误概率p-e(N)≥δ。
证明：   对于任意ε>0，设M=2N(R+ε)，X=X1X2…XN为输入随机序列，因为码字等概率分布，故H(X)=logM，因此I(X; Y)=H(X)-H(X|Y)=logM-H(X|Y)。又由于I(X; Y)≤NC容量，故logM-H(X|Y)≤NC容量。由费诺不等式得


logM-NC容量≤H(X|Y)

≤H(p-e(N),1-p-e(N))+p-e(N)log(M-1)

≤1+p-e(N)log(M-1)

<1+p-e(N)logM


于是


logM-NC容量-1logM<p-e(N)


即


p-e(N)>1-NC容量+1logM>1-NC容量+1N(R+ε)

>1-NC容量+1N(C容量+ε)=Nε-1N(C容量+ε)

=ε-1NC容量+ε



由于εC容量+ε>0，故存在δ1>0和N0>0，当N>N0时，有p-e(N)≥δ1>0。又若对某一个固定的N，有p-e(N)=0，则logM-NC容量<0，即M=2N(R+ε)≤2NC容量与R>C容量矛盾，从而对任给N，有p-e(N)>0。因此，只需取δ=min{δ1,p-e(1),p-e(2),…,p-e(N0)}，则对所有的N，都有p-e(N)>δ。当选用码字数（或消息数）M=2N(C容量+ε)时，信道的消息输出率为R=logMN=C容量+ε。这表明，信道消息传输率R已超过了信道容量，这是不可能的，既要使消息传输率大于信道容量而又无错误地传输消息是不可能的。

5.4信道编码方法
在通信中，由于码字序列是一种随机序列，接收端无法预知码元的取值，因而也无法识别其中有无错误。因此，可以在发送端的信息序列中增加一些差错控制元，由它们来校验是否出错，称为监督码元。这些监督码元和信息序列之间有确定的关系。信息序列和监督码元之间的关系不同，形成码的类型也不同，大体上分为两类：  分组码和卷积码。其中，分组码是把信息序列以每k个码元分组，编码器将每个信息组按照一定规律产生r个多余的码元（有时也称为校验元），形成一个长为n=k+r的码字。当分组码的信息序列与监督码元之间是线性关系时，即可用信息的线性方程组表示监督码元，这种分组码就称为线性分组码，如汉明码和循环码。卷积码则不仅考虑信息序列与监督码元之间的关联，还需考虑信息序列间的相关信息。码长越长，性能越好，但是译码复杂度越大。卷积码给出了一种利用分组间前后相关信息等效增加码长的方法。
5.4.1线性分组码

线性分组码建立在代数群论基础上，各个许用码字的集合构成了代数学中的群，它们具有以下的主要性质：  
（1） 任意两个许用码字之和（对于二进制码这个和的含义是模二加）仍为一个许用码字，即线性分组码具有封闭性；  
（2） 码字间的最小码距等于非零码的最小码重。

对于长度为n的二进制线性分组码，它有2n种可能的码组。从2n种码组中，可以选择M=2k个码组（k<n）组成一种码集。这样，一个k比特信息的线性分组码可以映射到一个长度为n的码组上。该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。
1. 线性分组码的编码

线性分组码的码空间C是由k个线性无关的基底张成的k维n重子空间，码空间的所有元素都可以写成k个基底的线性组合，即



C=
mk-1gk-1+…+
m1g1+m0g0
（5.4.1）


因而，线性分组码的关键是基底、子空间和映射规则。若对于每个信息矢量
m=
［mk-1,…,m1，m0］，其对应的码字为C=
［Cn-1,…,C1，C0］，那么式（5.4.1）可以写成如下矩阵形式：  


［Cn-1…C1C0］=
［mk-1…m1m0］
g(k-1)(n-1)…g(k-1)1g(k-1)0



g1(n-1)…g11g10

g0(n-1)…g01g00

(5.4.2)


即C=mG，其中G为该码的生成矩阵，是由k个基底矢量组成，即G=
gk-1



g1

g0
。如果要保证(n,k)线性分组码能够构成k维n重子空间，G的k行矢量必须是线性无关的。因此，k个基底gi也是码字。

原则上，(n,k)线性分组码的任何生成矩阵都可以通过行运算或者列置换简化成“系统矩阵”形式：  


G=(IkP)=10…0

01…0



00…1|
p(k-1)(n-k-1)…p(k-1)1p(k-1)0



p1(n-k-1)…P11P10

p0(n-k-1)…P01P00
(5.4.3)



这样在生成码字时，码字的前k位一定与信息码元相同，而其余的n-k位冗余比特称为一致校验位，是前k个信息位的线性组合，这样的码称为系统码。每个(n,k)线性组合码都可以和一个系统的(n,k)线性码等效。不具备“系统”特性的码也称为非系统码。非系统码与系统码并无本质的区别，系统码不改变码集，只改变映射规则。

另一方面，与任何一个(n,k)线性码的码空间C相对应，一定存在一个对偶空间H。将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。
由于校验矩阵是(n,n-k)对偶码的生成矩阵，它的每一行是一基底，也是一个码字。因此，(n,k)码的任一个码字均正交于校验矩阵的任一行矢量，即


CHT=0(1×(n-k)全零行矢量)

GHT=0(k×(n-k)全零行矢量)(5.4.4)


如果(n,k)线性码是系统码，G=
［IkP］，根据式(5.4.4)和GF（2）域的特性，可得到校验矩阵为H=［-PTIn-k］，负号在二进制情况下可省略，因为模2减法和模2加法是等同的。
【例54】考虑一(7,4)线性码，其生成矩阵G=1000101

0100111

0010110

0001011。

（1） 对于信息序列m=［1011］，求其对应码字；  
（2） 根据给定的系统码生成矩阵，画出编码器原理图；  
（3） 确定r=［1001101］是否是码字。
解：  （1） 由编码公式得


［C6C5C4…C0］=［m3m2m1m0］G

得C2=0,C1=0,C0=0

所以C=［1011000］


（2） 二进制(n,k)的编码器可用k级移存器和连接列移存器适当位置的n-k个模2加法器组成，加法器生成校验位后按顺序暂存在另一个n-k的移存器中。原理图如图55所示。



图55例54编码器原理图


（3） 判断rHT是否为0。
由生成矩阵可得到校验矩阵为


H=［PTIn-k］=1110100

0111010

1101001


于是计算rHT，得


［1001101］101

111

110

011

100

010

001=［011］≠0



所以，r=［1001101］不是码字。
校验矩阵除了校验码字的作用外，还可用来计算最小码距。这是因为，校验矩阵H可以写成n个列矢量的组合，即


H=
h(n-k-1)(n-1)…h(n-k-1)1h(n-k-1)0



h1(n-1)…h11h10

h0(n-1)…h01h00
=
［hn-1…h1h0］(5.4.5)


其中，hj(
j=n-1，…，1，0)是(n-k)×1列矢量。
由


CHT=
［Cn-1…C1C0］
［hn-1…h1h0］T


=Cn-1hTn-1+…+
C1hT1+
C0hT0=0(5.4.6)


其中，CHT代表n个1×(n-k)矢量hTj的线性组合。

由前面分析可知，分组码的最小距离等于dmin，说明码集里重量最小的码字有dmin个非零码元。若将该最小重量的码字代入式(5.4.6)，那么将有dmin个hTj项。由此可以断言：  H矩阵的列矢量至少要有dmin个才能线性相关，dmin-1个列矢量必定是线性无关的。另外，H是(n-k)×n矩阵，其秩至多是n-k，即最多有n-k个列矢量线性无关，综上可以得到，dmin-1≤n-k，
即


dmin≤n-k+1(5.4.7)


那么，如何用校验矩阵计算最小码距呢？现通过定理5.3给出。
定理5.3：  设H是线性码C的校验矩阵，则码C的最小码间距离(或最小非零码字重量)等于H中和为0的最小列数。
证明略。
【例55】已知某线性分组码的校验矩阵为H=1001011

0101110

0010111，求其最小码距。
解：  根据式(5.4.7)有


dmin≤n-k+1=4


再根据定理5.3，H中的所有列均不为0，而且没有两列是相同的，码C的最小距离至少为3，例如，0列、2列、6列之和为0，因此dmin=3。
定义5.3：  极大最小距离码(Maximized Minimum Distance Code，MDC)：  如果(n,k)线性码的dmin达到了n-k+1，则称该(n,k)线性分组码为极大最小距离码。
显然，当n、k确定之后，MDC码达到了纠错能力的极限，是给定条件下纠错能力最强的码，所以也是纠错码的设计目标。然而在二进制码中，除了将一位信息位重复n次的(n，1)码外，不存在其他的二进制的MDC码。但如果是非二进制码，则是存在极大最小距离码的，如RS（ReedSolomon）码就是MDC码。
2. 线性分组码译码

码字C=
［Cn-1,Cn-2,…,C1,C0］在传输过程中受到各种干扰，接收端的接收码R=
［rn-1,rn-2,…,r1,r0］不一定等于发送码，两者间的差异为差错图样
，即错误图样。差错图样E=
［en-1，en-2，…，e1,e0］=R-C=
［rn-1-cn-1,…,r0-c0］
。由于二进制模2加与模2减是等同的，因而有E=R+C或R=E+C。

同时，由于CHT=0，所以RHT=(C+E)HT=CHT+EHT=EHT。当无误码时，即E=0，所以RHT=0；  反之，当有误码时，E≠0，可以得到RHT=EHT≠0。因此，在HT固定的前提下，RHT与E有关，而与发送码C无关。于是，我们可以获得线性分组码的译码方法，如图56所示。先利用收到的码字R和已知的校验矩阵H计算出RHT；  再利用RHT计算出差错图样E；  由E和收到的码字R可以得到发送码的估计C^。


图56译码过程示意图



定义5.4：  伴随式S=
［sn-k-1…s1s0］是接收码R与校验矩阵H的转置HT的乘积，S=RHT=(E+C)HT=EHT+CHT=EHT。

由于


S=［sn-k-1…s1s0］=EHT


=［en-1…e1e0］

h(n-k-1)(n-1)…h0(n-1)



h(n-k-1)0…h00



为了求解该方程组，可以进一步展开如下：  



sn-k-1=en-1h(n-k-1)(n-1)+…+e0h(n-k-1)0




s1=en-1h1(n-1)+…+e0h10

s0=en-1h0(n-1)+…+e0h00



这是一线性欠定方程组，其中变元个数为n，方程数为n-k。在二元域中，少一个方程将导致两个解，少两个方程将导致4个解，以此类推，共少了n-(n-k)=k个方程，于是每个未知数有2k个解。因此，对于每一个确定的S，错误图样E有2k个解，那么取哪一个作为解呢？这里采用概率译码的处理方法，即把所有2k个解的重量(错误图案E中1的个数)
做比较，选择其中错误图样重量最小者作为E的估值。它的理论依据如下：  对于BSC信道，若错误概率为p，则长度n的码中错1位的概率为p(1-p)n-1，错两位的概率为p2(1-p)n-2，以此类推，
错n位的概率为pn。因为p<<1，必有p(1-p)n-1>p2(1-p)n-2>…>pn，所以S对应最小重量错误图案E的可能性最大。

由于E=R+C，E的重量最小等同于R、C间的汉明距离最小，所以二进制的概率译码体现最小距离译码法则，也是最大似然译码法则。
上述的概率译码，每接收一个码字需要解一次线性方程，运算量非常大。由于伴随式的数目是有限的，共2n-k个。如果n-k不太大，可以换一种思路来考虑问题。预先对不同S取值的错误图样E求解方程组，再按最大概率译码从2k个解中取出一个最可能的错误图样E。将S取值与错误图样E相对应，再把发码与错误图样的组合作为可能接收到的码字列表出来，译码时就不必去解方程，而是在上述表格中查找发送码的码矢量，这个表称为标准阵列译码表。

在标准阵列译码表中，将没有任何差错时的收码R放在第1行，差错图案为全零，伴随式也为全零。由于对于(n，k)线性分组码有2k个码字，所有码表有2k列；  由于(n，k)线性分组码有2n-k个伴随式，所以从第2行至n+1行为差错重量是1的图样，以及由该差错图样导致的接收码，接下来C2n行为差错重量为2的图案，以此类推，直到全部2n-k个伴随式有解为止。

【例56】某(5,2)系统线性码的生成矩阵是G=10111

01101，设接收的码是R=
［10101］，试构造出标准译码阵列表，并译码发送码的估值C^。

解：  由于该码是(5,2)系统线性码，所有码字的信息序列应该是
m=
［00］,［01］,［10］,［11］，这样通过生成矩阵获得的有效码字是



C1=［00000］，C2=［10111］，C3=
［01101］，C4=［11010］


由生成矩阵，可得校验矩阵为


H=［PTI3］=11100

10010

11001



因此伴随式有2n-k=25-2=8种。差错图样中除了代表无差错的全零图样外，有1个差错的图样有5种，2个差错的图样有C25=10种，以此类推。根据概率译码准则，8种伴随式将对应于差错重量最轻的图样，所以应选一种0个差错的图样，5种1个差错图样和2种2个差错的图样。由此，对于5种1个差错的图样，可通过S=EHT求出其对应的伴随式；  再通过求解剩余伴随式方程组，获得2种2个差错的图样。值得注意的是，对于伴随式(011)，将有22个解［00011］、［10100］、［01110］和［11001］，重量为2的差错图样有两种，可以任意选择其中一种为伴随式［011］的解。因为对于该码来说，它的纠错能力t仅为1，两个差错是纠正不了的。对应的标准阵列译码表如表51所示。


表51(5，2)线性码的标准阵列译码



S1＝000
E1+C1＝00000
C2＝10111
C3＝01101
C4＝11010
S2＝111
E2＝10000
00111
11101
01010
S3＝101
E3＝01000
11111
00101
10010
S4＝100
E4＝00100
10011
01001
11110
S5＝010
E5＝00010
10101
01111
11000
S6＝001
E6＝00001
10110
01100
11011
S7＝011
E7＝00011
10100
01110
11001
S8＝110
E8＝10001
10001
01011
11100

对于接收码［10101］，直接查表可得它的子集头是［10111］，因此译码输出为［10111］。

实际上，获得发码估值C^的方案有3种：  (1)直接搜索码表；  (2)先求伴随式找到行数；  (3)先求伴随式，在表中查出对应的差错图案，由C=R+E5得到结果。

任意一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力为t，则对于任何一个重量小于t的差错图案，都应有一个伴随式与之对应，所以伴随式的数目应满足条件



2n-k≥n

0+n

1+…+n

t=∑ti=0n

i（5.4.8）


上式称为汉明限（Hamming Bound），任何一种纠错能力为t的线性码都应满足以上条件。
定义5.5：  若某二元(n,k)线性分组码使式（5.4.8）成立，即2n-k=∑ti=0n

i，则将(n,k)线性分组码称为完备码。

迄今为止，完备码并不多见。t=1的汉明码，t=3的高莱码,长度n为奇数、由两个码字组成、满足dmin=n的任何二进制码，以及三进制的t=3的（11，6）码都属于完备码。

汉明码不是指一个码，而是指一类码，它是纠错能力t=1(既有二进制，又有非二进制)的完备的线性分组码的一类码的统称。二进制码长为n和信息位为k的汉明码服从如下规律：  (n,k)=(2m-1,2m-1-m)，其中，m=n-k。当m=3,4,5,6,7,8时，对应的汉明码分别为(7,4)、(15,11)、(31,26)、(63,57)、(127,120)和(255,247)。值得注意的是汉明码是一种完备码。
除此之外，汉明码的校验矩阵H具有特殊的性质。一个(n,k)的线性码校验矩阵有n-k行n列。而二进制n-k个码元能组合的列矢量的总数(全零矢量除外)是2n-k-1，恰好与二进制汉明码校验矩阵的列数n=2m-1相等。因此，对于汉明码，只要排列所有n-k个码元组成的所有列矢量(全零矢量除外)，可构成一个汉明码校验矩阵，再通过初等操作可以获得系统形式校验矩阵H，从而得到生成矩阵。

高莱码是二进制(23,12)线性码，其最小距离dmin=7，纠错能力t=3。由于满足223-12=2048=1+23

1+23

2+23

3，因此它也是完备码。
定义5.6：  如果给每个码字添加奇偶校验位Ci(n+1)来对码字的所有比特进行校验，使满足Ci1+Ci2+…+Ci(n+1)等于0或1，就构成了一个二进制(n+1,k)线性码，称为扩展码。
在偶校验的情况下，若原来码字中1的个数为偶数，则添加的校验位为0；  若原码1的个数为奇数，则添加的检验位为1。于是，扩展码校验矩阵He可表示为


He=|0

0

H

 - 0

11…11(5.4.9)


其中，reHTe=0。这时，偶校验后最小距离将增加1，检错能力也增加1。例如，在(23，12)高莱码上添加一位奇偶位即可获得（24，12）扩展高莱码，其最小码距dmin=8。
若把一定数量的信息设为零，(n,k)系统码可以缩短。把码的前e位设为0，从而将码(n,k)缩短成码(n-e,k-e)。

定义5.7：  在生成矩阵一定的条件下，由于信息组中的0和1结构对称、奇偶对称，因此码字的第1位m1=0的概率将为0.5。把第1位为1的所有码字去掉，剩下另一半第1位为0的码字舍去第1位后组成的新的(n-1,k-1)系统码，称为缩短码。

缩短码与原码具有相同的最小码距dmin。若(n,k)线性码的编码运算为C=mG，由于缩短码信息组的前一位是0，因此缩短码的编码运算为


Cs=msGs(5.4.10)



其中，Gs是G(k×n)去掉最左边l列及最上面l行后剩下的(n-l)×(k-l)矩阵。
另一方面，原码的校验矩阵H(n-k)×n缩短后为(n-k)×(n-l)的Hs，可见校验矩阵H与缩短后的校验矩阵Hs的行数是一致的，将H最左边的l列去掉得Hs。由于(k-i)/(n-i)<k/n，因此，缩短码的码率总是小于原码。
【例57】构造一个m=3的二元(7,4)汉明码。
解：  


H=0001111

0110011

10101011110100

0111010

1101001

G=［I4P］=1000101

0100111

0010110

0001011


扩展汉明码：  给(n,k)汉明码添加一位奇偶校验位，可得到一个dmin=4的(n+1,k)扩展汉明码； 反之，在生成矩阵G中删除l行l列，或等效在H中删除l列，可以得到缩短汉明码(n-l,k-l)。
5.4.2循环码
循环码是线性分组码的一个子集，它满足如下循环移位特性：  码集C中任何一个码字的循环移位仍是码字。
由于循环码的k个基底可以由同一个基底循环k次得到，因此用一个基底就足以表示一个码的特性。于是，可以把码字C=［cn-1cn-2…c1c0］与一个不大于n-1次的多项式联系起来，称为码多项式C(x)，其定义为


C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0（5.4.11）


其中，ci∈{0,1}，i=0,1,…,n-1。
根据循环码的定义，码循环移一位后可表示为
［cn-1,cn-2,…,c1,c0］→［cn-2,…,c1,c0,cn-1］，其对应的码多项式应为C1(x)=cn-2xn-1+cn-3xn-2+…+c0x+cn-1。比较循环移位的前后，可用如下的多项式运算来表示循环移1位：  C1(x)=xC0(x) mod (xn+1)。
于是，以此类推，可以得到移2位至移n-1位的码多项式分别为

移2位：  C2(x)=xC1(x)=x2C0(x) mod (xn+1)

移n-1位：  Cn-1(x)=xCn-2(x)=xn-1C0(x) mod (xn+1)
码字C0(x)移n位后又回到码字C0(x)，一个码字的移位最多能得到n个码字，再根据码空间的封闭性，得到码字的线性组合仍是码字，即



C(x)=a0C0(x)+a1xC0(x)+…+an-1xn-1C0(x)

=(a0+a1x+…+an-1xn-1)C0(x)

=A(x)C0(x) mod (xn+1)（5.4.12）


式中，C0(x)是一个码多项式，A(x)是次数不大于n-1的任意多项式，ai∈{0,1}，i=0,1,…,n-1（对于二进制编码）。作为特殊情形，若选择C0(x)是n-k次多项式，A(x)是k-1次任意多项式。那么，在C0(x)不变情况下，A(x)系数有2k种组合，它恰好对应于2k个码字。此时C0(x)起到了生成多项式的作用，且C0(x)是C(x)的一个因式。
从近世代数的观点来看，GF(2)域次数小于n的多项式在模2加、模(xn+1)乘法运算下构成了一个交换环。多项式交换环的一个主理想子环一定可以产生一个循环码，且所有码多项式都可以由其中一个元素的倍式组成，这个元素称为该主理想子环的生成元。从交换环的性质中，可以找到构造(n,k)循环码的步骤：  
（1） 对xn+1做因式分解，找出其(n-k)次因式；  
（2） 以该(n-k)次因式作为生成多项式g(x)，与不高于(k-1)次的信息多项式m(x)相乘，即得到码多项式C(x)=m(x)g(x)，其中，C(x)的次数不高于(k-1)+(n-k)=n-1。
可以验证所得码的循环性。令C1(x)=xC(x)=xm(x)g(x) mod (xn+1)，由于g(x)本身也是码多项式，而xm(x)是不高于k次的多项式，由式（5.4.12）得到C1(x)一定是码字，即码字的循环移位也是码字，所以是循环码。
【例58】构造n=7的循环码。
解：  x7+1=(x+1)(x3+x2+1)(x3+x+1)
一次因式1种：  x+1
三次因式2种：  (x3+x2+1),(x3+x+1)
四次因式2种：  (x3+x2+1)(x+1)=x4+x2+x+1
(x3+x+1)(x+1)=x4+x3+x2+1
六次因式1种：  (x3+x2+1)(x3+x+1)=x6+x5+x4+x3+x2+x+1
以g(x)=x3+x+1为生成多项式可以生成(7，4)循环码。当信息位为
［0110］时，得到信息多项式为m(x)=x2+x，所以对应的码多项式为C(x)=m(x)g(x)=(x2+x)(x3+x+1)=x5+x4+x3+x→［0111010］。
多项式xn+1因式分解为g(x)h(x)，去除生成多项式g(x)外，剩下的因式组成h(x)，称为校验多项式。因为任何码多项式C(x)与h(x)的模（xn+1）的乘积一定等于0，而非码字与h(x)的模（xn+1）的乘积必不为0。


C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1) mod (xn+1)=0（5.4.13）


在xn+1=g(x)h(x)分解中，g(x)和h(x)处于同等地位。由g(x)生成的(n,k)循环码和由h(x)生成的(n,n-k)循环码互为对偶码。(n,n-k)对偶码构成(n,k)循环码的零空间。
以上方法获得的循环码并非是系统码。如果希望所获得的循环码同时是系统码，可通过系统码的定义形式直接获得系统循环码的构造方法。
对于系统码而言，其码字的前k位应是信息位，后面n-k位为校验位。因此其码字多项式应为


C(x)=xn-km(x)+r(x)（5.4.14）


其中，r(x)是校验多项式，它的最高次应为n-k-1次码多项式。对上式两边同取模g(x)，左边C(x) mod g(x)=m(x)g(x) mod g(x)=0；  右边也必是0，即xn-km(x)+r(x) mod g(x)=xn-km(x) mod g(x)+r(x) mod g(x)=0，因此可得xn-km(x) mod g(x)=r(x) mod g(x)。
所以，校验多项式应为


r(x)=xn-km(x) mod g(x)（5.4.15）


于是获得了直接产生系统循环码的方法，其步骤如下：  
（1） 将消息多项式m(x)乘以xn-k；  
（2） 将xn-km(x)除余g(x)得校验多项式r(x)； 
（3） 将r(x)加在xn-km(x)后面得到系统循环码多项式。
【例59】(7，4)循环码的生成多项式为g(x)=x3+x+1，求： 
(1) 该循环码系统形式的生成矩阵； 
(2) ［1001］的系统循环码字。
解：  
（1） G=x3g(x)

x2g(x)

xg(x)

g(x)=1011000

0101100

0010110

0001011系统化1000101

0100111

0010110

0001011
（2） m(x)=m3x3+m2x2+m1x+m0=x3+1
xn-km(x)=x6+x3
r(x)=x2+x
C(x)=xn-km(x)+r(x)=x6+x3+x2+x［1001110］

循环码是线性分组码的子集。从(n，k)循环码生成多项式也可获得生成矩阵的方法：  取g(x)本身加上移位k-1次所得的k-1个码字作为k个基底。
若循环码生成多项式为g(x)=xn-k+gn-k-1xn-k-1+…+g2x2+g1x+1，则生成矩阵是


G=xk-1g(x)

xk-2g(x)



xg(x)

g(x)=1gn-k-1…g2g1100…

1gn-k-1…g2g110…

…0

00…1gn-k-1…g2g11（5.4.16）


除此之外，也可以直接获得系统生成矩阵，其思路与求系统循环码类似。对于系统生成矩阵G=［IkP］，它的第l行可写成码多项式为xn-l+rl(x)，每行多项式xn-l+rl(x)也一定是循环码的一个码字，即xn-l+rl(x)=θl(x)g(x)，且各行的码字不相关。因此，如果能计算获取rl(x)，则可直接获得系统生成矩阵。
当对xn-l+rl(x)=θl(x)g(x)两边同除余生成多项式g(x)时，可以得到


rl(x)=xn-l mod g(x)（5.4.17）


其中，l=1,2,…，k-1。
【例510】计算(7，4)系统循环汉明码最小重量的可纠
错误图样和对应的伴随式。

解：  对于(7，4)系统循环汉明码，其最小重量的可纠错误图样码多项式为0，1，x，x2，x3，x4，x5，x6。由s(x)=E(x) mod g(x)，可得8个对应的伴随式：  0，1，x，x2，x+1，x2+x，x2+x+1，x2+1。

5.4.3卷积码

前面研究过的分组码是将输入序列分割成一定长度的信息组后各自孤立地进行编译码，分组与分组之间没有考虑任何联系。从信息论的角度，它忽略了各分组间的相关性，必将损失一部分信息。
当码长n有限时，能否将有限个分组间的相关信息添加到码字中从而等效地增加码长？译码时能否利用前后码字的相关性将前面的译码信息反馈到后面译码中，作为译码参考？这些想法导致了卷积码的产生。

卷积码于1955年由麻省理工学院Elias首次提出，随后Wozencraft和Renffen提出了序贯译码方法(对具有较大约束长度的卷积码非常有效)。1963年，Massey提出了一种效率不高、但易于实现的译码方法，称为门限译码，这使得卷积码被大量应用于卫星和无线信道的数字传输中。到了1967年，Viterbi又提出了最大似然概率译码方法，它可应用于较小约束长度的卷积码。再配合序贯译码的软判决，卷积码在深空和卫星通信系统中也得到广泛应用； 1974年，Bahl、Cocke、Jelinek和Raviv提出最大后验概率译码方法，称为BCJR算法，它可对不等先验概率的信息比特进行卷积码译码。卷积码是一种常见的信道编码方法，下面对卷积码的编译码方法进行简要阐述。
1) 卷积码编码

卷积码可看作一个有限记忆系统，它将信息序列分割成长度为k的一个个分组，与分组码不同的是，在某一个分组编码时，卷积码的码字不仅与本时刻的分组信息相关，而且与本时刻以前的L个分组的信息也相关，其中，L+1称为卷积码的约束长度。于是，卷积码常用3个参量描述，如(n，k，L)，其中，n代表卷积码输出码字的长度，k为每次输入卷积编码器的信息组长度，L+1为约束长度。因此，卷积码中相互关联的码字母长度为n×(L+1)，它的纠错性能随L的增加而增大，译码的差错率将随着n的增加而指数下降。在相同编码效率情况下，卷积码的性能明显优于分组码，至少不低于分组码。如图57所示是卷积编码器示意图，信息序列被分割成一个个分组，通过卷积编码器进行线性组合，最后获得输出码字。


图57卷积码编码器示意图


卷积码编码的一般过程可用图58表示。卷积码编码器将信息序列通过串并转换后，存入k个长度为L+1的移存器中，构成输入信息阵列； 编码器按照一定的规则对信息阵列中数据进行组成，获得输出码字信息，并通过
串并转换后得到编码输出。由于卷积码码字中每个元素都是k×(L+1)个数据的线性组合，编出当前i时刻的码元(码字母)Cij，j=0，1，…，n-1，需要有k×(L+1)个系数来描述组合规则，且每一个码字需用n×k×(L+1)个系数才能描述。


图58卷积码编码过程一般示意图


与分组码不同，卷积码在任意给定单元时刻其输出的n个码元中，每一个码元不仅与此时刻输入的k个信息元有关，而且还与前连续L个时刻输入的信息元有关。但是，卷积码也可以用生成矩阵形式描述。下面以(3，2，1)卷积码为例，说明卷积码的编码过程。
【例511】二进制(3，2，1)卷积码编码器的结构如图59所示，若本时刻i=0的输入信息是m0=［m00，m01］=［01］，上一时刻m1=［m10，m11］=［10］(用上标正整数1表示1个时延)，试用生成矩阵表示该编码器，并计算输出码字。


图59二进制(3，2，1)卷积码编码器


解： 假设用glkj表示记忆序列第k行(k=0，1)、第l列(l=0，1)对第j个(j=0，1，2)码元的影响。令参与组合者(有连线接到模2加法器)相应的系数glkj=1，否则glkj=0。

由图中接线可知，共需n×k×(L+1)=3×2×(1+1)=12个系数，分别是


g000=1，g001=0，g002=1，g100=1，g101=1，g102=1，

g010=0，g011=1，g012=1，g110=1，g111=0，g112=0


本时刻输入信息m0=［m00，m01］=［01］与上时刻输入信息m1=［m10，m11］=［10］，用矩阵G0=
g000g001g002
g010g011g012=101
011，
G1=g100g101g102
g110g111g112=111
100分别描述本时刻和上一时刻输入对码字的影响，从而得出本时刻编码的输出为


C0=［C00，C01，C02］=
m0G0+m1G1

=［01］101
011+［10］
111
100=［011］+［111］=［100］


上例中，系数矩阵G0和G1的设定具有一般性。对于(n，k，L)卷积码，把i以前的第l个信息比特组ml=(mi-l0，mi-l1，…，mi-lk-1)对线性组合的影响用一个k×n的生成子矩阵Gl来表示，则



Gl=gl00gl01…gl0(n-1)

gl(k-1)0gl(k-1)0…gl(k-1)(n-1)
(5.4.18)


其中，用glkj表示记忆序列第k行(k=0，1，…，k-1)、第l列(l=0，1，…，L)对第j个(j=0，1，2，…，n-1)输出码元的影响，且glkj∈{0，1}。设编码器初始状态为0(记忆阵列全体清0)，则随着一个个k比特信息组(m0，m1，…，mL，mL+1，…)的输入，编码器源源不断地输出码字(C0，C1，…，CL，CL+1，…)，即
在时刻i=0时，C0=m0G0
在时刻i=1时，C1=m1G0+m0G1
在时刻i=2时，C2=m2G0+m1G1+m0G2
以此类推，在时刻i=L时，CL=mLG0+mL-1G1+…+m0GL，
其等效矩阵形式为


C=［C0，C1，…，CL+1］=mG

=［m0，m1，m2…］G0G1…GL……

0G0G1…GL…
(5.4.19)


其中，G定义为卷积码的生成矩阵，它是个半无限矩阵。时刻i的输出码字为


Ci=∑Ll=0mi-lGl
(5.4.20)


即码字为无限长输入序列与有限长矩阵元素的卷积运算获得，这也就是卷积码名称的由来。

其中，L+1个子矩阵Gl，(l=0，1，…，L)实质上是G在时间轴上的展开。考虑子矩阵Gl和Gl+1同一位置上的两系数glkj和gl+1kj都表示记忆阵列第k行对第j输出码元的影响，两者之间仅差一列(即一个时延D)，因此，也可以用多项式形式来表示卷积码的编码过程，其中，D为一个时间的延迟。第k行输入到第j个输出之间的转移函数gkj(D)表示为



gkj(D)=g0kj+g1kjD+g2kjD2+…+gLkjDL=∑Ll=0glkjDl(5.4.21)


由转移函数构成的矩阵G(D)={gkj(D)}称为转移函数矩阵，它是k行n列矩阵。一旦卷积码器结构图给定，转移函数矩阵G(D)也就确定。同样，当转移函数矩阵G(D)给定，卷积码器的结构图也是确定的。转移函数矩阵同样可以描述卷积码的编码。

【例512】某二元(3，1，2)卷积码的转移函数矩阵为
G(D)=［11+D1+D+D2］，试画出编码器结构图。
解： 根据转移函数矩阵定义，得到


g00(D)=g000+g100D+g200D2=1，所以g000=1g100=0g200=0

g01(D)=g001+g101D+g201D2=1+D，所以g001=1g101=1
g201=0

g02(D)=g002+g102D+g202D2=1+D+D2，所以g002=1g102=1g202=1


根据glkj值，得到卷积码的编码器结构图如图510所示。


图510二进制(3，1，2)卷积码编码器



由于编码器是一个线性系统，mi(D)表示第i个输入序列，Cj(D)表示第j个输出序列，转移函数gkj(D)可以表示从输入i到输出j的转移。对于有k个输入、n个输出的线性系统，共有kn个转移函数，可用k×n矩阵表示，转移函数生成矩阵表示为


G(D)=g00(D)g01(D)…g0(n-1)(D)

g(k-1)0(D)g(k-1)0(D)…g(k-1)(n-1)(D)
(5.4.22)


其中，gij(D)由(5.4.21)式所得。

基于转移函数生成矩阵，(n，k，L)编码器的编码过程也可用多项式形式表示。因此，要首先获取信息多项式，对于信息序列
m=［m0，m1，…，mk，mk+1，…，m2k，m2k+1，…］，其信息多项式为


m(D)=m0+m1D+…+mkDk+mk+1Dk+1+…+m2kD2k+m2k+1D2k+1+…


串/并变换后得到


m0(D)=m0+mkDk+m2kD2k+…
m1(D)=m1+mk+1Dk+1+m2k+1D2k+1+…
m2(D)=m2+mk+2Dk+2+m2k+2D2k+2+…



卷积编码器可视作一个k端口入、n端口出的线性多端口网络，基于转移函数矩阵的编码过程
如图511所示，其中，
G(D)是k×n矩阵，每矩阵元素是L次多项式，m(D)、C(D)则是无限高次。


图511卷积码的转移函数矩阵


定义输入、输出多项式矩阵mP(D)、CP(D)为



m(D)串/并mP(D)=［m0(D)， m1(D)，…mk-1(D)］

C(D)串/并CP(D)=［C0(D)， C1(D)，…Cn-1(D)］


这里，mP(D)、CP(D)的下标P表示“并行”。虽然m(D)和mP(D)数量上有对应关系，然而在数学上有不同含义，m(D)、C(D)是多项式，而mP(D)、CP(D)分别是(1×k)、(1×n)的矩阵，且输入、输出多项式矩阵间的关系为


CP(D)=mP(D)·G(D)(5.4.23)


同时，第j个支路的输出是所有输入支路对它影响的总和，即


Cj(D)=∑k-1i=0mi(D)gij(D)(5.4.24)


最后，利用并/串变换公式将n个输出多项式合并成一个多项式



C(D)=∑n-1j=0DjCj(Dn)(5.4.25)


【例513】某二元(2，1，3)卷积码编码器，其转移函数矩阵为G(D)=［1+D+D31+D+D2+D3］，若输入的比特信息为10111，即输入序列的m(D)=1+D2+D3+D4，求输出码字序列。

解： 二元(2，1，3)卷积码的转移函数矩阵为G(D)=［1+D+D31+D+D2+D3］，则输出码字为


Cp(D)=mp(D)·G(D)=(1+D2+D3+D4)［
1+D+D31+D+D2+D3］

=［1+D71+D+D3+D4+D5+D7］


那么，经过并/串变换后的输出为


C(D)=∑n-1j=0DjCj(Dn)=1+(D2)7+D［1+(D2)+(D2)3+(D2)4+(D2)5+(D2)7］

=1+D+D3+D7+D9+D11+D14+D15


即输出码字为1101000101010011。
【例514】某二元(3，2，1)卷积码如图59所示，当输入序列m=［110110］时，试计算输出码字。
解： 针对图59所示卷积码编码器，其转移函数矩阵可表示为


G(D)=1+DD1+D
D11


对于输入序列m=［110110］，则m0(D)=1+D2，m1(D)=1+D，于是


Cp(D)=mp(D)·G(D)=［1+D21+D］
1+DD1+D
D11

=［1+D31+D3D2+D3］

C(D)=∑n-1j=0DjCj(Dn)=C0(D3)+DC1(D3)+D2C2(D3)

=1+D+D8+D9+D10+D11


即输入码字序列为c=［110000001111］。
另一方面，状态图和网格图给出了卷积码内存结构的描述，又称为卷积码的图形表示。由图58卷积码结构一般结构示意图可知，卷积编码器在i时刻编出的码字不仅取决于本时刻的输入信息组mi，而且取决于i之前存储在记忆阵列的L个信息组，即取决于记忆阵列的内容。我们把卷积码编码器的记忆阵列中任一时刻所存储的信息称为卷积码编码器的一个状态。对于(n，k，L)卷积码，共有2(k*L)个状态，每次输入k比特只有2k种状态变化，所以，每个状态只能转移到全部状态的某个子集(2k个状态)中去。当然，每个状态也只能由全部状态的某个子集(2k个状态)转移而来。下面，以图512所示的(2，1，2)卷积码编码器为例，讨论卷积码的图形表示法。


图512(2，1，2)卷积码编码器



图512所示的(2，1，2)卷积码包含2个记忆单元(移位寄存器)和2个模2加法器。2级移位寄存器共有22种不同状态，定义为
S0(00)、S1(01)、S2(10)和S3(11)共4种状态。在每个时刻，输入的1个比特信息，当前状态将转为4种状态中的任何一种。例如，若当前移存器状态为00，当输入为1时，移位寄存器的状态变为10，输出为c0=100=1，c1=10=1，即输出11。表52描述了该编码器所有状态间转移情况。


表52卷积码的状态间转移情况



输入
当 前 状 态
下 个 状 态
输出1
输出2
0
00
00
0
0
0
01
00
1
1
0
10
01
1
0
0
11
01
0
1
1
00
10
1
1
1
01
10
0
0
1
10
11
0
1
1
11
11
1
0


状态表类似查找表，即根据当前的输入和当前的状态，可以从表中查得输出信息。比表更为简单和直观的方法是状态流图。下面，进一步研究编码器(2，1，2)的状态流图，又称状态图，
如图513所示图中状态转移信息用“输入输出1输出2”表示。


图513编码器(2，1，2)的状态流图



设输入信息序列m=［10111000…］，按照输入数据可以得到以下不同情况： 

(1) 首先对所有移位寄存器进行归0处理，此时寄存器的初始化状态为00。

(2) 输入信息1，移位寄存器的状态改为10； 输出两个支路分别为c10=100=1，c20=10=1，最后输出码组
c0=［c10c20］=［11］。

(3) 输入的第2个信息比特为0，则寄存器状态转为01，输出码组c11=1，c21=0，输出码组c1=［c11c21］=［10］。

(4) 输入的第3个信息比特为1，则寄存器状态转为10，输出码组c12=0，c22=0，故c2=［00］。
(5) 输入的第4个信息比特为1，则寄存器状态转为11，输出码组c13=0，c23=1，故c3=［01］。
(6) 输入的第5个信息比特为1 ，则寄存器状态转为11，输出码组c14=1，c24=0，故c4=［10］。
(7) 输入的第6个信息比特为0，则寄存器状态转为01，输出码组c15=0，c25=1，故c5=［01］。

(8) 输入的第7个信息比特为0，则寄存器状态转为00，输出码组c16=1，c26=1，故c6=［11］。
(9) 输入的第8个信息比特为0，则寄存器状态转为00，输出码组c17=0，c27=0，故c3=［00］。

以此类推，就可以得到所有情况编码情况，一个完整的(2，1，2)卷积码编码器状态转移图如图513所示，图中圆圈代表状态，共有S0(00)、S1(01)、S2(10)和S3(11)共4种状态，箭头代表转移，与箭头对应的标注，如0/10表示输入信息0时输出码字10。每个状态都有两个箭头发出，对应于输入是0或1的两种情况下的转移路径。假如输入信息序列是m=［10111000…］，从状态流图可以容易地找到输入/输出和状态的转移。可从状态S0出发，根据输入找到相应箭头，随箭头在状态流图上移动，得到编码输出C=［1110000110011100…］，具体过程如图514所示。


图514卷积码状态及输入输出关系图


由此可见，状态图可为利用信号流图的数学工具奠定基础，但是状态图缺少时间轴，不能记录下状态转移的轨迹。
网格图(也称为格栅图、格子图、篱笆图)弥补了这一个缺点，它以状态为纵轴，以时间(单位为码字周期T)为横轴，将状态转移沿时间轴展开，从而使编码过程一目了然。网格图有助于发现卷积码的性能特征，在卷积码的概率译码中，特别是维特比(Viterbi)译码算法中特别有用，是借助计算机分析研究卷积码的最得力工具之一。

网格图分成两部分： 一部分是对编码器的描述，告诉人们从本时刻的各状态可以转移到下一时刻的哪些状态，伴随转移的输入信息/输出码字是什么； 另一部分是对编码过程的记录，一根半无限的水平线(纵轴上的常数)标志某一个状态，一个箭头代表一次转移，每隔时间T(相当于移存器中的一位时延D)转移一次，转移的轨迹称为路径。两部分可以合画在一起，也可单独画，如在描述卷积编码器本身而并不涉及具体编码时，只需第一部分网格图就够了。下面仍以
(2，1，2)卷积码为例，当节点级数为j=L+1=2+1=3时，状态S0(00)、S1(01)、S2(10)和S3(11)将呈现重复，利用这一重复，就可得到纵深宽带(或称高度)为2km=21×2=4的格状图，如图515所示，图中实线表示输入1时所走的支路，虚线表示输入0时所走的分支，从第3级节点开始，从同一状态出发所延伸的结构是完全一样的，所以网格图能更为简洁地表示卷积码。


图515编码器(2，1，2)的网格图


任意给定的一个输入信息序列，在网格图中都存在一条特定的路径，
如m=［10111］，则其输出码字序列为C=
［1110000110］，
图515中带三角和方块的线显示每位信息输入时的状态转移和码字输出过程。又如，当输入信息序列为m=［01100］，输出码字则为C=［
0011010111］，由图515中带正方块线显示每位信息输入时的状态转移和码字输出过程。因此，不同信息序列将由网格图中不相重合的路径区分。


卷积码的4种描述方法，生成矩阵、转移函数矩阵、状态流图和网格图
从不同侧面描述卷积码，其中，生成矩阵和转移函数矩阵属同一大类，它们沿用了分组码的描述方法，建立了代数与编码器的关联，特点是物理意义清楚，代数量(多项式系数，矩阵元素)与编码电路连接线之间的对应关系十分明确，非常利于用VHDL等硬件描述语言来表达以及用FPGA、DSP等来物理实现。状态流图和网格图属于图形表示法，状态流图可借助信号流图等图论工具或理论来分析卷积码的特性，网格图则特别适合用于计算机的穷举搜索，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似然序列译码最得力的工具。
2) 卷积码的译码
卷积码的性能取决于卷积码的距离特性和译码算法，其中，距离特性是卷积码自身本质的属性，它决定了该卷积码潜在的纠错能力，而译码方法只是研究如何将这种潜在的纠错能力转化为现实的纠错能力。

表述距离特性的最好方法是利用网格图。对于二元码，序列距离d(C′，C″)指的是汉明距离，即d(C′，C″)=w(C′C″)，其中，w(·)为码的重量。当然，序列距离与序列的长度相关，同一序列对在不同长度时它们间的距离也不相同。为此，我们将长度l 的任意两序列对间的最小距离定义为l 阶列距离，又称为列距离函数，用d
c(l)来表示，其定义为


dc(l)=min{d(［C′］l，［C″］l):
［m′］0≠［m″］0}
(5.4.26)


其中，［m′］0≠［m″］0表示两个不同信息序列，且在网格图上从零时刻其轨迹开始分叉。由于早期卷积码译码方法与约束长度(L+1)有关，于是把(L+1)阶列距离称为最小距离


dmin=min{w(［C］L+1):［m］0≠0}
(5.4.27)


而把由零状态零时刻分叉的无限长的两个序列之间的最小距离定义为自由距离： 


df=min{w(［C］∞):［m］0≠0}
(5.4.28)


自由距离df在网格图上就是零时刻从零状态与全零路径分叉(C≠0)，经若干分支后又回到全零路径(与全零序列距离不再继续增大)的所有路径中，重量最轻(与全零序列距离最近)的那条路径的重量。列距离、最小距离和自由距离三者之间的关系
如下



dmin=dc(l)|l=L+1

df= liml→∞dc(l)
(5.4.29)


【例515】二进制(3，1，2)卷积码网格图如图
516所示，试求该码1~6阶列距离、最小距离和自由距离。


图516二进制（3，1，2）卷积码网格图



解： 最轻码字序列列距离函数dc(l)
l＝1S0→S2dc(1)=3
l＝2S0→S2→S3dc(2)=4
l＝3S0→S2→S3→S1dc(3)=5 (最小距离dmin)
l＝4S0→S2→S3→S1→S0dc(4)=6
或S0→S2→S1→S0→S0 
l＝5S0→S2→S1→S0→S0→S0dc(5)=6
l＝6S0→S2→S1→S0→S0→S0→S0dc(6)=6
由此可见


dmin=dc(l)|l=L+1=dc(3)=5
df=6


对于如上简单的卷积码，我们可以直接从网格图中找出df。但是，随着限制长度的增加，状态数将以指数级增长，网格图将变得非常复杂和庞大，直接找出df往往变得不可能了。因此，各种计算方法应运而生。最常见的是采用解析法，借助信号流图来求自由距离。当状态数较大时，只能依靠计算机的搜索法来寻找df，而当状态数非常大时，
如超过220，那么用现有计算机搜索也难以胜任。下面对如何用信号流图来计算自由距离进行说明。

信号流图由美国麻省理工学院的Mason于20世纪50年代首先提出。信号流图中的网络是由一些定向线段将一些节点连接起来组成的，包括节点和支路： 节点即变量或信号，其值等于所有进入该节点的信号之和，有输入节点(也称源点)、输出节点(也称汇点)和混和节点； 支路即连续两个节点的定向线段。信号在分支上只能沿着其上的箭头单向传递。原则上，可以利用信号流图计算任一以支路为基础的线性增益量。若干支路的串联构成一条路径，路径增益则是组成此路径的各支路增益的乘积(其指数是各支路增益指数之和)。两个节点之间可能有不止一条的路径，所以路径增益称为两节点之间的生成函数，用T(D)表示。

卷积码的信号流图与卷积码的状态流图之间具有拓扑等效性。将信号流图法用于自由距离计算时，状态对应于节点，
有趣的是不同转移间的距离(当与全零转移相比时就是重量)。因此，
以各转移所对应的码字重量Wj为指数，定义支路增益为DWj和路径增益为D∑jWj。由于自由距离是由零状态出发又回到零状态的最轻序列的重量，
所以可以将零状态拆开成两个节点，一个源点和一个汇点，这样，沿着任一条由源点到汇点的路径都有一个路径增益，其中指数最小者就是最轻路径。

从生成函数T(D)的角度看，如果将所有指数相同的路径增益合并，各路径增益的可表示为


T(D)=∑∞d=0AdDd(5.4.30)



式中，系数Ad是路径增益指数为d的不同路径的条数。因此，T(D)中最低次非零项的指数就是最轻序列的重量，即自由距离df。 

【例516】二进制(3，1，2)卷积码结构如图510所示。试给出其状态流图，并用信号流图法求该码自由距离df。
解： 根据(3，1，2)卷积码结构，可以画出其状态流图如下：






将卷积码状态图的零状态S0拆成一个源点和一个汇点，状态的自环是全零码，在信号流图中不画出，得到零状态拆分后的状态流图如下： 




令各支路的增益为Dj(这里j是与相应转移对应的码字重量，如码字011的重量为2，对应的支路增益是D2)，可得信号流图如下： 




再根据信号流图的一些初等变换规则，如图517所示，将上图简化，最后得到生成函数，T(D)=2D6-D81-D2-2D4+D6。运用多项式除法(长除法)，可进一步得到T(D)=2D6+D8+5D10+…，自由距离等于其中最轻者即次数最低的第1项，即df＝6。



图517信号流图的一些初等变换规则


译码算法是将潜在的纠错能力转化为实际纠错能力的手段，其中较有名的卷积码译码算法称为维特比(Veterbi)译码算法。它采用概率译码的思想，将已接收序列与所有可能的发送序列做比较，计算出各自码距，并选择码间距离最小的序列作为发送码序列的估计。如果接收到m组、每个信息组包含k个比特，接收到码字序列将与2mk条路径结果进行比较，其中码距最小的那一条路径被选择为最有可能的路径，对应的输出码字序列即为发送码序列的估计。然而，当m较大时，概率译码将难以实现。随后，维特比对概率译码算法进行了简化，它并不是在网格图上一次比较所有可能的2mk条路径(序列)，而是接收一段
，计算和比较一段，选择出最大似然可能的一段序列作为估计，进而达到整个估计序列为最大似然序列的目的。

由于编码序列经过有噪信道传输之后会受到干扰，使得其值可能不再是0或1这样的整数，因此在进入译码器前，需要对接收序列中每个比特进行处理，卷积码译码可分为硬译码算法(Hard Decision Decoding，HDD)和软译码(Soft Decision Decoding，SDD)算法两种，前者先将所采样的信号做判别再进行译码，搜寻与接收序列的汉明距离最小的序列作为对编码序列的估计值； 后者则直接用被采样信号进行译码运算。下面以硬译码算法为例，并结合图格图，详细描述维特比译码过程。


由于在二进制对称信道中最大似然概率译码准则等效于最小汉明距离的译码准则，因此具有最小码距
d(r，c)累积值的路径就是对数似然概率
logp(r|c)的最大路径，其中，r为信道接收序列，c为发送到信道的码序列，该路径被称为幸存路径。定义分支量度
BM (Branch Metric)，BM=d(rj，cj)是第j时刻接收码rj相对于预测码的相似度。在软判决情况下，BM一般指欧氏距离，而在硬判决情况下，BM为汉明距离。路径度量PM(path metric)与网格中的状态相关联，在硬判决中，对应于网格中从初始状态到当前状态的最可能路径与接收码序列间的汉明距离。维特比算法的核心是接收机可以使用分支度量和先前计算的状态路径度量递推地计算当前状态的路径度量。由于译码过程也建立在网格图中，并且从全零状态开始到全零状态结束。所以，在每个符合输入的分支中，都可以计算出分支度量值。
维特比译码算法步骤可概括如下： 
(1) 在j=L+1（L+1为卷积码约束长度）个时刻前，计算每一个状态单个路径分支度量，并存储每一状态下的幸存路径及其度量值。
(2) j增加1，即从j=L+1开始到N-1时刻结束(N为输入信息序列的长度)，对进入每一个状态的部分路径进行计算，这样的路径应有2k条(k为卷积码信息位长度)，从中挑选具有最大值的部分路径为幸存路径，删除进入该状态的其他路径，然后幸存路径向前延长一个时间段。若进入某个状态的部分路径中，有两条部分路径值相等，则可以任选其一作为幸存路径。

(3) 重复步骤(2)的计算、比较和判决过程。若接收序列长为(N+L+1)k，其中，后L+1是人为加入的全0值，则译码将至(N+L+1)时刻为止。

下面以(2，1，2)卷积码为例说明维特比译码过程，输入数据： m=［1 1 0 1 1］，输入信道的编码序列为c=［11 01 01 00 01］，信道接收端获取的接收码字为r=［11 01 01 10 01］。译码参数值分别是： N=5，L=2，k=1。由于系统是有记忆的，j将从0开始，到j=N+L+1=5+2+1=8为止。

若假设编码器总是起始于状态S0(00)，则前j=L=2个时刻对应于编码器从状态S0出发，而最后的两个时间段则相当于编码器返回到S0状态。因此，在前两个与后两个时间段内不可能达到所有可能的状态，但在网格图中，其中心部分所有状态都是可以达到的。每一个状态都有2k=21=2个分支的离去和进入。在时间段j，离开每一个状态的虚线分支表示输入是0，而实线分支表示输入是1。维特比算法的基本思想是依次在不同时刻j=L+1，L+2，…，L+N+1，对图中相应列的每个点(对应于编码器中该时刻的一个状态)，按最大似然准则(或最小汉明距准则)比较所有以它为终点的路径，保留一条具有最大似然值(或最小汉明距值)的路径为幸存路径，而将其他路径弃之不用。因此，下一时刻只需对幸存路径延伸出来的路径继续比较，即接收一段，比较一段，保留幸存路径，按此过程一直到最后，即N+L+1时刻，所保留下的路径就是所要求的最大似然译码结果。下面以二进制(2，1，2)卷积码为例，讲述上述过程。

(1) 在j=0，1，2这3个时刻，执行步骤（1），计算出每个路径的分支度量值，即汉明距离，
如图518所示，并在图中以数字标记该分支路径的最小汉明距离，
如接收序列r中的第1个序列是11，与第一时刻网络图中的两条路径00、11的汉明距分别为2和0，因而这些数字被标注在对应路径的下方或附近。


图518解码步骤（1）



(2) 接下来选择下一时刻的幸存路径。由于在j=3时刻进入状态S0的两条路径的PM值分别为3和4，所以选择PM为3的路径为幸存路径，在图中用带三角线段表示，并去除到达S0状态的其他路径。

同理，分别获取进入S1、S2、S3状态的幸存路径，如图519所示。至此，j=2+1＝3时刻的幸存路径选择完成，并将接下来的路径的分支度量值都标注在图中，如图520所示。


图519进入S0 S1S2S3的幸存路径选择




图520剩余译码路径的分支度量值计算


在图520中，每个节点(状态)进行分支度量值比较，分支度量值较小的被标注在状态节点的上方。按此过程不断进行，获得最后一个接收符号所对应一条分支度量值最小的路径，如图521所示，即为接收序列的最佳路径。


图521(2，1，2)卷积码对应于接收序列的译码最佳路径


根据最佳路径，获得对应的输入序列为［1 1 0 1 1］，且在译码过程中纠正一个比特错误。

维特比译码是按最大似然准则进行的译码，是卷积码的一种最佳译码方法，它的性能由信道质量决定，然而这种译码方法存在着两个主要缺点： 一是要等全部接收的数据进入译码器以后才能最后译出结果，所以译码时延长； 二是需要存储2kL条幸存路径的全部历史数据，所以存储量大。

【例517】对于图510所示(3，1，2)卷积码。设发送的码字序列是c=［000，111，011，001，000，000，…］，传输时发生两位差错，接收的码字序列为r=［110，111，011，001，000，000，…］，试用维特比算法进行其译码。
解： 利用维特比译码，可以获得其译码过程如下，其中带三角路径是接收序列的最佳路径，具体步骤介绍如下：




(1) 为了便于编程实现，现给出计算过程。首先是网格图，其基本结构如下





其中，假设4个状态用1、2、3、4表示。定义p(m，n)表示到达m状态的第n个前状态(predecessors)是什么，而c(m，n)表示第n个前状态转移到达m状态时对应的码字。例如，p(4，1)=3，p(4，2)=4表示到达4状态的第1、第2个前状态分别是状态3和4，对应的码字分别是c(4，1)=100和c(4，2)=101，于是，以上网格图可用数组描述如下： 


p(1，1)=1，c(1，1)=000，p(1，2)=2，c(1，2)=001，

p(2，1)=3，c(2，1)=011，p(2，2)=4，c(2，2)=010，

p(3，1)=1，c(3，1)=111，p(3，2)=2，c(3，2)=110，

p(4，1)=3，c(4，1)=100，p(4，2)=4，c(4，2)=101。


(2) 计算第j时刻接收码rj相对于各码字的分支量度BM。在二进制硬判决情况下，BM即为汉明距离，因此其计算表达式为


BMj(m，n)=W（c(m，n)rj）(5.4.31)


其中，W（·）是码字重量，BMj(m，n)表示第j时刻接收码rj与到达第m状态的第n个转移所对应的码字的距离。本题中r1=110，r2=111，r3=011，r4=001，r5=000…，因此，时刻3的BM值分别是BM3(1，1)=W
（c(1，1)r3）=W（000011）=2，同理，可以计算出： BM3(1，2)=1，BM3(2，1)=0，BM3(2，2)=1，BM3(3，1)=1，BM3(3，2)=2，BM3(4，1)=3，BM3(4，2)=2。

(3) 计算第j时刻到达状态m的路径量度PMj(m)，它是将上一时刻的路径量度PMj-1与本时刻分支量度BM累加后选择其中汉明距离最小的一个，即


PMj= minm{PMj-1［p(m，n)］+BMj(m，n)}(5.4.32)


初始时，除全零状态的PM0(1)=0外，其余状态的PM0(i)，i≠0均置为∞。因此，时刻3中到达状态1的路径可以来自状态1和状态2两处，这两处前时刻的路径量度分别是PM2(1)=5和PM2(2)=2，本时刻的分支量度分别是BM3(1，1)=2和BM3(1，2)=1，因此，时刻3状态1的路径量度 PM3(1)=min{PM2［p(1，1)］+BM3(1，1) ，PM2［p(1，2)］+BM3(1，2)}=min{5+2，2+1}=3。以上计算路径量度的过程实际上就是挑选到达状态1的最大似然路径的过程。
看到有两条路径可达，一条与接收码汉明距离5+2，另一条的汉明距离2+1，距离越小则似然度越大，所以取PM3(1)=3隐含了选择路径S1→S3→S2→S1为到达状态1的幸存路径，同理，可获得到达状态2、3、4的幸存路径。


(4) 译码输出以及更新第j时刻、状态m对应的留存路径(Survivor)Sj(m)。留存路径是与最大似然路径对应的码字序列，每状态一个，长度为D。留存路径每时刻按以下步骤更新一次： ①设到达状态m的最大似然路径的前状态是n，则令n状态前时刻的留存路径作为本时刻本状态m的留存路径，即Sj(m)=Sj-1(n)。②选择具有最小(最似然)PM那个状态的留存路径最左边的码字作为译码输出。③将各状态留存路径最左边的码字从各移存器移出，再将到达各状态的最大似然路径在时刻j所对应的码字从右面移入留存路径Sj(m)。时刻j=3到达状态2的最大似然路径来自状态3，而前时刻状态3的留存路径是S2(3)=000，000，000，111(长度D=4)。比较各状态的PM3(i)，发现状态2是最大似然路径，其前时刻在状态3，于是取S2(3)最左边的码字000作为译码输出。接着，将S2(2)最左边(最旧)的码字000移出，将时刻3到达状态2的转移所对应的码字011从右边移入，得更新后状态2的留存路径S3(2)=000，000，111，011。同理可得S3(1)、S3(3)、S3(4)。重复步骤②~④，将维特比算法持续下去，获得译码结果如下图中带三角线段所示。





5.5信道编码MATLAB计算实现
与信源编码理论一样，信道编码理论仅指出了在传输率小于信道容量的条件下，可以实现可靠性通信的信道编码是存在的，并没有给出具体构造好码的方法。5.4节从最基本的线性分组码开始，介绍了信道编码的编译码过程。现进一步给出几种常用信道编码方法，以及它们的MATLAB实现。

5.5.1RS码
RS码是由Reed和Solomon提出的一类具有很强纠错能力的多进制循环纠错码，它是循环BCH码的一个重要子类。RS码的译码是按符号进行的，因此RS码特别适用于纠正突发错误。例如，在硬盘驱动器、CD和DVD等数据存储系统及消费电子设备中常采用卷积码作为内码、RS码作为外码的串行级联码；  除此之外，RS码也在众多的数字通信系统（如卫星通信、深空探测、美国数字电视国家标准、数字音频广播和数字视频广播等）中得到应用。
对于定义在GF(qm)域上的RS码，其分组长度为n=qm-1，获得码距为δ的RS码的基本步骤如下：  
（1） 选取一个次数为m的既约生成多项式并构造GF(qm)域；  
（2） 依据αi,i=1,2，…，δ-1构造生成多项式g(x)=∏δ-1i=1(x-αi)；  
（3） 依照循环码的编码方法和编码电路进行编码（所有加法运算和乘法运算都在GF(qm)上进行）。
现以定义在本原多项式为p(x)=x3+x+1的GF(23)上的RS码为例说明构造过程，其中，RS码的码长n=23-1=7，码距δ=5。

首先，假设α为GF(23)的本原元，由于要求设计距离为δ=5，所以该RS码以α,α2,α3,α4为根，因此生成多项式为g(x)=(x-α)(x-α2)(x-α3)(x-α4)=x4+α3x3+x2+αx+α3。
由于α为p(x)=x3+x+1＝0的根，即α3+α+1=0或α3=α+1，那么GF(23)中的元素可按表53计算。


表53各元素计算结果



0
mod(α3+α+1)=0
α0
mod(α3+α+1)=α0=1
α1
mod(α3+α+1)=α
α2
mod(α3+α+1)=α2
α3
mod(α3+α+1)=α＋1
α4
mod(α3+α+1)=α2+α
α5
mod(α3+α+1)=α2+α+1
α6
mod(α3+α+1)=α2+1
α7
mod(α3+α+1)=α2
α8
mod(α3+α+1)=α
…
…


值得注意的是，对于GF(23)域运算，“+”运算与“-”运算等价。由此生成GF(23)上的（7，3）RS码，其系统码生成多项式矩阵G为


G=100α41α4α5

010α21α6α6

001α31αα3


由于该RS码是定义在GF(23)上的，因此每个编码信息符号由
3个信息比特组成，假设输入信息符号组为m=［2,4,6］，转换为GF(23)上的元素
m=［α,α2,α4］，编码码字为


C=mG=αα2α4100α41α4α5

010α21α6α6

001α31αα3

=［αα2α400αα4］


即编码输出为C=［2460026］，转换为二进制为C=［010100110000000010110］。

MATLAB代码如下：  

clear all

close all

M=8; %调制阶数

bps=log2(M);     %每个符号所含比特数

N=7;            %RS码长

K=3;            %RS信息位长度

mod=comm.PSKModulator('ModulationOrder'，M，'BitInput'，false);  

% 创建调制器(8PSK调制方式)

demod=comm.PSKDemodulator('ModulationOrder'，M，'BitOutput'，false);  

% 创建解调器

chan=comm.AWGNChannel('BitsPerSymbol'，bps);  %创建AWGN信道

err=comm.ErrorRate;  

enc=comm.RSEncoder('BitInput'，false，'CodewordLength'，N，'MessageLength'，K);  

% 创建编码器

dec=comm.RSDecoder('BitInput'，false，'CodewordLength'，N，'MessageLength'，K);  

% 创建译码器

ebnoVec = (3:0.5:8)';  %信噪比

errorStats = zeros(length(ebnoVec)，3); 

for n=1:length(ebnoVec)

chan.EbNo=ebnoVec(n); 

reset(err)

while errorStats(n，2) < 100 && errorStats(n，3) < 1e7

data = randi(［0 2］，1500，1);              %生成随机数据

encData = step(enc，data);               %RS编码

modData = step(mod，encData);          %调制

rxSig = step(chan，modData);            %通过AWGN信道

rxData = step(demod，rxSig);            %解调

decData = step(dec，rxData);             %RS译码

errorStats(n，:) = step(err，data，decData);    %错误统计

end

end

berCurveFit = berfit(ebnoVec，errorStats(:，1));  %曲线拟合

berNoCoding = berawgn(ebnoVec，'psk'，8，'nondiff');  % 未编码

semilogy(ebnoVec，errorStats(:，1)，'b*'，ebnoVec，berCurveFit，'c-'，ebnoVec，berNoCoding，'r')

ylabel('错误率')

xlabel('Eb/N0 (dB)')

legend('RS编码的仿真数据'，'拟合曲线'，'未编码')

grid

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


图522RS编码结果



5.5.2Turbo码
1993年，法国科学家C.Berrou和A.Glavieux等人于瑞士日内瓦召开的ICC会议上提出了Turbo码的概念。由于Turbo码很好地应用了香农信道编码定理中的随机性编译码条件，从而获得了几乎接近香农理论极限的译码性能。仿真结果显示：  在高斯白噪声信道下，码率为1/2的Turbo码在达到误比特率（BER)小于或等于10-5时，Eb/N0只有约0.7dB（这种情况下达到信道容量的理想Eb/N0值为0dB），远远超过了其他的编码方式。Turbo码不仅在信道信噪比很低的环境下性能优越，而且还具有很强的抗衰落能力，因此它在信道条件差的移动通信系统中得到了广泛应用，如在第三代移动通信系统(IMT2000）中已经将Turbo码作为其传输高速数据的信道编码标准。

Turbo码是一种并行级联卷积码(Parallel Concatenated Convolutional Codes)。编码器通过交织器把两个分量编码器进行并行级联，两个分量编码器分别输出相应的校验位比特；  译码器在两个分量译码器之间进行迭代译码，分量译码器之间传递可去掉正反馈的外信息，这样整个译码过程类似涡轮（Turbo）式工作。因此，这个编码方法又被形象地称为Turbo码。

图523所示为Turbo码编码器的结构示意图。信息序列U={u1,u2，…，uN}经过交织器形成一个新序列U′={u′1,u′2，…，u′N}(长度与内容没有改变，但比特位经过重新排列)，U和U′分别传送到两个编码器(编码器1与编码器2)，一般情况下，这两个编码器结构相同，生成序列Xp1和Xp2。为了提高码率，序列Xp1和Xp2需要经过删除器，采用删除(Puncturing)技术从这两个校验序列中周期地删除一些校验位，形成校验序列Xp，Xp与未编码序列X′经过复用调制后，生成了Turbo码序列X。


图523Turbo码编码器的结构示意图



Turbo码通过在编码器中引入交织器使得码字具有近似随机的特点，通过分量码的并行级联实现了长码构造，Turbo码充分考虑了香农信道编码定理证明时假设的条件，从而获得了接近香农理论极限的性能。

Turbo码的译码算法采用了最大后验概率算法(MAP)。在译码的结构上又进行了改进，再次引入反馈的概念，取得了性能和复杂度之间的折中。同时，Turbo码采用的是迭代译码，这与经典的代数译码是完全不同的。Turbo码的译码算法是在BCJR算法的基础上改进的，称为MAP算法，后来又形成LogMAP算法、MaxLogMAP以及软输出维特比译码(SOVA)算法。
Turbo码的译码器结构如图524所示，由两个成员码对应的译码单元和交织器与解交织器组成，一个译码单元的软输出信

图524Turbo码译码器的结构示意图
息将作为另一个译码单元的输入，且将此过程不断迭代以提高译码性能。其中，Xk是接收到的信息比特序列，Y1k是编码器1的校验比特，Y2k是编码器2的校验比特。



Turbo码译码器为串行结构，两个编码器所产生的校验信息通过串并转换被分开，分别送到对应的译码器输入端，即Y1k和Y2k。首先，第1级译码器根据接收到的码序列Xk和第1级编码器的校验位信息Y1k得到输出信息(此时译码器2的外信息为0)，其输出信息包含两部分：  一部分是由译码器根据码字相关性提取出来的外信息； 另一部分是来自于接收码序列对应的输出，该输出在传递给下一级译码器之前被减去。外信息在交织之后被送到译码器2作为先验信息，译码器2根据校验位信息Y2k、接收码元序列Xk和外信息这三者共同做出估计，得到输出信息，同时得到译码器2的外信息，该信息在解交织之后，反馈给第1级译码器作为先验信息；  结合该外信息，译码器1重新做出译码估计，得到改善的外信息。而此时的外信息又可以传递到译码器2，如此往复，形成迭代过程。最终，当达到预先设定的迭代次数或满足迭代结束条件时，译码结束，取输出的符号作为最终硬判决结果。


译码时首先对接收信息进行处理，两个译码器之间外部信息的传递就形成了一个循环迭代的结构。由于外信息的使用，一定信噪比下的误比特率将随着循环次数的增加而降低。同时，外信息与接收码元序列间的相关性也随着译码次数的增加而逐渐增加，外信息所提供的纠错能力也随之减弱，在一定的循环次数之后，译码性能将不再提高。以下是Turbo码的MATLAB程序实现。
MATLAB代码如下：  

clear all

close all

M=16; %调制阶数

EbN0=-5:-1;  %信噪比范围

frmLen=500;  %帧长

ber=zeros(size(EbN0)); 

enc=comm.TurboEncoder('InterleaverIndicesSource'，'Input port');  %创建编码器

dec=comm.TurboDecoder('InterleaverIndicesSource'，'Input port'， ...

'NumIterations'，4);  %创建译码器

mod=comm.RectangularQAMModulator('ModulationOrder'，M， ...

'BitInput'，true，'NormalizationMethod'，'Average power');  %创建QAM调码器

demod=comm.RectangularQAMDemodulator('ModulationOrder'，M， ...

'BitOutput'，true，'NormalizationMethod'，'Average power'， ...

'DecisionMethod'，'Log-likelihood ratio'， ...

'VarianceSource'，'Input port');  %创建QAM译码器

chan=comm.AWGNChannel('EbNo'，EbNo，'BitsPerSymbol'，log2(M));  

% 创建AWGN信道

errorRate = comm.ErrorRate; 

for k = 1:length(EbNo)

errorStats = zeros(1，3);  

noiseVar = 10^(-EbNo(k)/10)*(1/log2(M)); 

chan.EbN0 = EbN0(k); 

while errorStats(2) < 100 && errorStats(3) < 1e7

data = randi(［0 1］，frmLen，1);  %创建二进制随机数据

intrlvrInd = randperm(frmLen);  %交织

encodedData = step(enc，data，intrlvrInd);  %Turbo编码

modSignal = step(mod，encodedData);  %调制

receivedSignal = step(chan，modSignal);  %AWGN信道

demodSignal = step(demod，receivedSignal，noiseVar);  %解调

receivedBits = step(dec，-demodSignal，intrlvrInd);  %译码

errorStats = step(errorRate，data，receivedBits);  %统计差错

end

ber(k) = errorStats(1); 

reset(errorRate)

end

semilogy(EbN0，ber，'r-o')

grid

xlabel('Eb/N0 (dB)')

ylabel('误比特率')

uncodedBER = berawgn(EbNo，'qam'，M);  %未编码的BER

hold on

semilogy(EbN0，uncodedBER，'b-')

legend('Turbo编码'，'未编码')

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


图525Turbo编码结果


5.5.3LDPC码

低密度奇偶校验（Lowdensity Partycheck Code，LDPC）码是一种性能接近香农极限的好码，也叫Gallager码，现被3GPP RAN1会议确定为5G中移动宽带业务的长码块编码方案。LDPC码由Gallager于1962年首先提出，在很长一段时间里并没受到人们的重视，直到1996年，Mackay和Neal等人再次提出，LDPC码的研究才进入一个崭新阶段。随着编码矩阵构造、解码算法优化等关键技术的突破，LDPC码被各种通信所采纳，如卫星数字广播系统、地面数字视频广播系统和无线接入网络中IEEE 802.11n等。
LDPC码性能优于Turbo码，具有较大的灵活性和较低的差错平底特性(Error Floors)。它描述简单，对严格的理论分析具有可验证性，译码复杂度低于Turbo码，可实现完全的并行操作且硬件复杂度低，具有高速译码潜力。目前，LDPC码已在深空通信、光纤通信、卫星数字视频和声频广播、磁/光等存储、移动和固定无线通信、电缆调制/解调器和数字用户线（DSL）中得到广泛应用。
LDPC码是一类特殊的线性分组码，它的校验矩阵是稀疏矩阵，即校验矩阵中只有很少一部分的1元素，绝大多数都是0元素。LDPC码分为规则LDPC码和非规则LDPC码。对于规则LDPC码，Gallager给出如下的定义：  (n，j，k)LDPC码是长为n的码字，在它的奇偶校验矩阵中，每一行和每一列中1的个数是固定的，其中每一列有j(j≥3)个1，每一行有k(k>j)个1；   列之间1的重叠数目小于或等于1。如式(5.5.1)是按定义构造的（12，3，4）LDPC码的校验矩阵H。在校验矩阵中，每行和每列的1元素的个数都是固定的。


H=
001001110000

110010000001

000100001110

010001100100

101000010010

000110001001

100110100000

000001010011

011000001100（5.5.1）





图526（12，3，4）规则LDPC

码Tanner图


除此之外，LDPC码还可以用Tanner图表示。上式（12，3，4）对应的Tanner图如图526所示。

在Tanner图中，左边的节点称为变量节点，右边的节点称为校验节点。每个变量节点对应LDPC码的一个码元，其个数等于码长n，即等于校验矩阵的列数。校验节点与校验方程对应，其个数等于校验方程的个数，即校验矩阵的行数。所以，Tanner图中的线与校验矩阵中的元素1是对应的。在Tanner图中与某节点相连的边的个数称为该节点的度。规则LDPC码中相同类型的节点度数应该是相同的，即所有变量节点的度也相同，所有校验节点的度也相同；  而非规则LDPC码的变量节点/校验节点的度是不同的。

LDPC码的译码算法主要是基于Tanner图结构的消息传递(Message Passing，MP)算法，该算法的性能随着量化阶数的增加而提高，同时复杂度也随之增加。其中性能最好的是置信传播算法(Belief Propagation，BP)，当编码Tanner图中没有环时，它的性能可等效于最大似然算法。
BP算法可以由初始化过程和迭代过程两个步骤完成，具体如下。


（1） 初始化：  在进行迭代过程之前首先要给参数赋初值。令p0l=p(xl=0)（比特xl取0的先验概率），p1l=
p(xl=1)=1-p0l。对于每个满足Hml=1的(l,m)，变量q0ml和q1ml分别被初始化为p0l和p1l。

（2） 迭代： 
① 对每一个校验约束m和对应的每一个l∈L(m)计算两个概率，其中一个是r0ml，当xl=0，且其他比特{xl: l′≠l}对应于相互独立的概率分布时，{q0ml′,q1ml′}校验约束m得到满足的概率，即


r0ml=∑{xl′: l′∈L(m)|l}p∑l′∈L(m)|lx′l=0|xl=0×∏l′∈L(m)|lqxl′ml′（5.5.2）


另一个概率是r1ml，当xl=1时，校验约束得到的概率定义为


r1ml=∑{xl′: l′∈L(m)|l}p∑l′∈L(m)|lx′l=1|xl=1×∏l′∈L(m)|lqxl′ml′（5.5.3）


式中，概率内的求和为模2求和，条件概率的取值为0或1，取决于假设的x′l的值是否满足模2求和式
，L（m）|l是L（m）集合中去掉l后的其他元素。

上面这个复杂的计算可以根据前后向递归算法适当简化。定义


δqml=q0ml-q1ml（5.5.4）


可以得到


δrml=r0ml-r1ml=∏l′∈L(m)|lδqml′（5.5.5）


利用数学归纳法可以得到rxml（x=0或1）的计算式如下：  


rxml=1+(-1)xδrml2（5.5.6）


经过简化后，rxml的计算量极大减少。
② 利用步骤①计算所得到r0ml的r1ml和更新概率值q0ml和q1ml。对于每个l计算下式：  


q0ml=αmlp0l∏m′∈M(l)|mr0m′l（5.5.7）

q1ml=αmlp1l∏m′∈M(l)|mr1m′l（5.5.8）


其中，αml为归一化系数，使得q0ml+q1ml=1。
同时，计算出比特l取值为0和1的伪后验概率q0l和q1l,如下：  


q0l=αlp0l∏m∈M(l)r0ml（5.5.9）

q1l=αlp1l∏m∈M(l)r1ml（5.5.10）



③ 当q1l>0.5时，令x^=1，反之令x^=0。如果校验方程Hx^=0 mod 2成立，则译码成功并结束，x=x^；  否则，若迭代次数少于预先设定的最大迭代次数T，则重复该迭代过程；  如果迭代次数已经超过所设定的最大迭代次数还是没有得到正确的译码，则译码失败。此时，部分译码的x^可以作为其他译码算法的有效译码起点。

BP算法的复杂度为码长的线性函数，并行实现可极大提高译码速度。BP算法的译码误码率随信噪比的增加而减少，没有误码率下降急速的差错平底特性的现象。无论是在理论上还是在实际应用中，BP译码都能够在高斯白噪声环境下达到接近信道限的性能。
MATLAB代码如下：  

clear all

close all

enc = comm.LDPCEncoder;  %创建LDPC编码器

dec = comm.LDPCDecoder;  %创建LDPC译码器

mod = comm.QPSKModulator('BitInput'，true);  %创建调制器

chan = comm.AWGNChannel('NoiseMethod'，'Signal to noise ratio (SNR)');  

% AWGN信道

demod = comm.QPSKDemodulator('BitOutput'，true，...

'DecisionMethod'，'Approximate log-likelihood ratio'， ...

'VarianceSource'，'Input port');  %创建解调器

err = comm.ErrorRate; 

snrVec = ［0 0.2 0.4 0.6 0.65 0.7 0.75 0.8］;  %信噪比范围

ber = zeros(length(snrVec)，1); 

for k = 1:length(snrVec)

chan.SNR = snrVec(k); 

noiseVar = 1/10^(snrVec(k)/10); 

errorStats = zeros(1，3); 

while errorStats(2) <= 200 && errorStats(3) < 5e6

data = logical(randi(［0 1］，32400，1));      %产生二进制数据

encData = step(enc，data);               %LDPC编码

modSig = step(mod，encData);           %调制

rxSig = step(chan，modSig);             %AWGN信道

demodSig = step(demod，rxSig，noiseVar);  %解调

rxData = step(dec，demodSig);           %LDPC译码

errorStats = step(err，data，rxData);        %统计错误

end

ber(k) = errorStats(1); 

reset(err)

end

semilogy(snrVec，ber，'-o')

grid

xlabel('SNR (dB)')

ylabel('误比特率')

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


图527LDPC编码结果


5.5.4Polar码

Polar码是一种唯一被严格证明能够达到香农限的信道编码方法，现已成为5G中的中短码长纠错编码标准。2007年，E.Arikan基于信道极化理论首次提出Polar码。经过信道极化后，比特信道(bitchannel)被分为好与坏两种，而好比特信道通过Polar码的编码被选用于信息传输，极大地提升了信息传输的可靠性。

信道极化分为信道组合和信道分裂两个过程。其中，信道组合就是对二进制离散无记忆信道(BDMC)
W进行独立复

图528信道W到W2的组合图
制，通过一定的递归规则得到矢量信道。例如，在n=0时，对于N＝2n＝1信道，则是一个
BDMC信道，也就是W1ΔW； 当n=1,N=2n=2时，两个W1的独立信道可组合成一个W2信道，即W2:X2→Y2，其组合过程如图528所示，信道W2的转移概率可表达为： W2(y1,y2|u1,u2)=W(y1|u1u2)W(y2|u2)，其中，为模2加。

当n=2，N＝4时，由两个W2的独立信道可组合成一个W4信道X4→Y4，如图529所示，其转移概率为W4
(y41|u41)=W2(y21|u1u2,u3u4)W2(y43|u2,u4)，其中y41=(y1y2y3y4),u41=(u1u2u3u4)，R4是一置换矩阵，将(v1v2v3v4)置换为(v1v3v2v4)。于是，W4的输入(u1u2u3u4)与输入(x1x2x3x4)间关系可表示为x41=u41G4，其中G4=1000
1100
1010
1111。因此W4信道的转移概率可改写成


W4(y41|u41)=W4(y41|u41G4)（5.5.11）


该组合过程可以类推，即信道WN可以由两个WN/2的独立信道组合得到，并且WN的转移概率为


WN(yN1|uN1)=WN(yN1|uN1GN),yN1∈YN,uN1∈XN
（5.5.12）


其中，GN=BNFn，BN为置换矩阵，F=10
11。

信道分裂则是将组合后的信道WN映射成为N个比特信道，第i个比特信道的转移概率为


W(i)N(yN1,ui-11|ui)Δ∑
uNi+1∈XN-i12N-1WN(yN1|uN1)（5.5.13）


其中，(yN1,ui-11)是W(i)N的输出，ui是W(i)N的输入，i=1,2,…,N。图530展示了N=4时从信道W的4个拷贝到W(i)4的过程。最右端是4个独立信道W，通过蝶形运算得到两个矢量信道(W(1)2,W(2)2)，对两个矢量信道(W(1)2,W(2)2)再一次蝶形运算得到W(i)4的每个比特信道。其中，蝶形结构右边两个结点代表相同且独立的信道，左边即是信道组合后分裂的结果，此过程可以不断进行。


图529信道W2到W4的组合图




图530从W到W4的变换过程示意图


根据信道极化理论，随着N逐渐增大，信道分裂得到的每一个比特信道的信道容量呈现出两极分化的趋势，即有一些比特信道的容量逐渐接近于1，而另一些比特信道的容量逐渐接近于0。因此，在实际的通信过程中，选择那些容量接近1的比特信道来传输信息，称为信息比特，而将容量接近0的比特信道赋予固定值（通常为全0），称为冻结比特，冻结比特这部分信息是已知的。信息比特和冻结比特所在位的集合分别被称为信息位和冻结位。

在Polar码中，比特信道的好与坏一般可用巴氏(Bhattacharyya)参数来衡量。巴氏参数Z(W)代表的是信道输入为0或1时，信息被错误判决的概率上界，其定义为


Z(W(i)N)=∑yN1∈YN∑ui-11∈Xi-1W(i)N(yN1,ui-11|0)W(i)N(yN1,ui-11|1)
（5.5.14）


1） Polar码的构造
Polar码的构造就是比特信道选择的过程，即选择那些好的比特信道来传输信息，这里好指的是巴氏参数趋近于0，或信道容量趋近于1。

对于BDMC信道，Polar码可表现为三元组参数(
W,N,K)，其中，W表示BDMC信道，N为Polar码的码长，K是Polar码信息位的长度，信息位集合为
A{1,2,…,N}。Polar码构造的目标是使
∑i∈AZ(W(i)N)最小，即计算各比特信道巴氏参数{Z(W(i)N):1≤i≤N}，并使信息位集合中的巴氏参数之和为最小，其中，Z(W(i)N)为第i比特信道的巴氏参数。从实现角度来讲，Polar码的构造问题转化
为判决问题，即在给定了信道下标的索引号i，i∈{1,2,…N}和门限值γ的情况下(γ∈［0,1］)，依据AγΔ{i∈{1,2，…,N}:Z(W(i)N)<γ}来判决下标i对应的比特信道是否用来传输信息。

总的来说，Polar码的构造就是K个信息位索引号的选取。因此，通常，首先计算出各个比特信道巴氏参数的值，然后对计算出的巴氏参数值从小到大排序，最后挑选出前K个较小的巴氏参数值的比特信道索引组合成信息位，剩余的比特信道则为冻结位。常见的构造方法有基于Polar码的蒙特卡罗构造方法、基于BEC的构造方法、密度进化构造方法、TalVardy方法和高斯近似法等。

作为一种线性分组码，Polar码也可用生成矩阵来描述。给定长度为
N的Polar码，其中N=2n，其编码xN1=uN1GN，其中，xN1是编码码字，uN1为信息序列，GN为N×N的生成矩阵，且
GN=BNFn，BN为置换矩阵，F=10
11。通常情况下，信息位集合用A表示，冻结位集合则用Ac表示。若uA表示信息位信息，ucA表示冻结位信息，则编码过程可表示为


xN1=uAGN(A)uACGN(Ac)（5.5.15）


其中，GN(A)由矩阵GN中对应于集合A中各元素的行构成，GN(Ac)由矩阵GN中对应于集合Ac中各元素的行构成，且冻结位的取值对译码性能没有影响，常将置为0。于是，Polar码这种线性分组码编码用4个参数(N,K,A,uAC)表示，其中N为码长，K为信息位的个数，A和AC分别是信息位和冻结位，uAC是冻结位信息。
2） Polar的译码
Polar码的译码是将接收到的yN1恢复成发送信息序列uN1的过程，一般来说，译码方法会与其编码方法相适应。针对Polar码的结构，Arikan提出了连续删除（Successive Cancellation，SC）译码和置信传播(Belief Propagation，BP)译码算法，下面简单介绍SC译码。
SC译码是Polar码的核心译码算法，该算法是基于比特信道的概率似然比通过硬判决值进行译码，一个比特一个比特地译码，直到最后一个比特译码结束后才得到译码输出。

对于参数为(N,K,A,uAc)的Polar码，当要传输的信息序列与生成矩阵相乘后得到编码，再通过信道传输，在接收端获得接收序列yN1，其中，信息序列包括信息位uA和冻结位uAc。由于冻结位在编译码过程中保持不变，是已知的，所以在译码时如果是冻结位则直接译码，其估计值即为冻结位信息，
u^Ac=uAc； 如果是信息位，则通过
下式判别当前比特的估计值


hi(yN1,u^i-11)=0W(i)N(yN1,u^i-11|0)W(i)N(yN1,u^i-11|1)≥1

1其他
(5.5.16)


在译码过程中，通常把转移概率的比值定义为似然比(Likelihood Ratio，LR)



L(i)N(yN1|u^i-11)=W(i)N(yN1,u^i-11|0)W(i)N(yN1,u^i-11|1)(5.5.17)


将式（5.5.16）代入式（5.5.17）中，得到当前信息位的估值为


u^i=
0L(i)N(yN1,u^i-11)≥1



1其他(5.5.18)


SC译码算法的计算复杂度主要取决于译码过程中似然比的计算，而对于似然比的计算，Arikan给出了一种递归迭代计算方法


L(2i-1)N(yN1,u^2i-21)=L(i)N/2(yN/21,u^2i-21,ou^2i-21,e)L(i)N/2(yNN/2+1,u^2i-21,e)+1L(i)N/2(yN/21,u^2i-21,ou^2i-21,e)+L(i)N/2(yNN/2+1,u^2i-21,e)(5.5.19)

L(2i)N(yN1,u^2i-11)= ［L(i)N/2(yN/21,u^2i-21,ou^2i-21,e)］1-2u^2i-1·L(i)N/2(yNN/2+1,u^2i-21,e)(5.5.20)


其中，L(2i-1)N表示N长序列中第(2i-1)比特标号(奇数)的似然比，L(2i)N是N长序列中第(2i)比特标号(偶数)的似然比，u^2i-21,o是u^2i-21序列中奇数位构成的序列，u^2i-21,e是u^2i-21序列中偶数位构成的序列。从上式可以看出，计算长度为N的似然比可以转化为计算两个长度为N/2的LR，即似然对(L(2i-1)N(yN1,u^2i-21)，L2iN(yN1,u^2i-11)可以转换为计算似然对(L(i)N/2(yN/21,u^2i-21,ou^2i-21,e),L(i)N/2(yNN/2+1,u^2i-21,e))，当然N/2的LR继续利用式(5.5.19)和式(5.5.20)，由N/4的LR似然对(L(i)N/4(yN/41,u^2i-21,ou^2i-21,e)，L(i)N/4(yN/2N/4+1,u^2i-21,e))得到，以此类推，直到码长为1时终止。当码长为1时，LR的值由公式L(i)(yi)=W(yi|0)/W(yi|1)直
接计算得到。

图531显示了码长为8的Polar码的SC译码的因子图结构，其中，编码器参数为(8,5,{4,5,6,7,8},(0,0,0))。在该过程中，每个负责计算的节点会

图531Polar码的SC译码过程
向下发起一个LR的请求，从最左边到最右边依次进行。在最左边的第1列节点对应码长为8的LR请求，相应的第2列对应码长为4的LR请求，第3列对应码长为2的LR请求，第4列对应码长为1的LR请求。在图中每一个节点都对应两个标签，例如，第2列第2个节点带有22和(y41,u^41,eu^41,o)两个标签，其中，第1个标签指的是译码过程中该节点第22个被激活，第2个标签指的是要计算且保存的LR值，其中，数字1~32表明一共需要计算32个LR值。

译码时先从第1个节点开始激活，首先计算L(1)8(y81)，但是L(1)8(y81)的值并不能直接得到，而是触发节点2和节点9，在触发这两个节点之后，节点1开始等待节点2和节点9返回的LR的值； 先激活节点2进行L(1)4(y41)的计算，同样节点2继续传递，触发节点3，节点3再触发节点4，到节点4时已经到了最右边一列，通过给定的信道信息可直接计算出L(1)1(y1)，于是可将计算结果返回给触发节点3和节点23。对于节点3，除了获得节点4返回值
外，还需要继续向右侧传递，触发节点5获得L(1)1(y2)的值。对节点4和节点5的返回信息计算可得到节点3的LR值L(1)2(y21)，并将其LR值返回给节点2。同前面的过程一样，节点2还需向右依次触发节点6、节点7和节点8，获得节点2的LR值L(1)4(y41)，并将结果返回给节点1。同理，节点1还需要节点9的返回值，节点9的LR值计算过程如上类似。当节点9的LR值L(1)8(y85)返回给节点1后，节点1整合计算出L(1)8(y81)，得到了第1个比特的似然值，由于u1是冻结位，因此直接置为0，并将其似然值传递给下一个信息比特，即触发节点16。

同第1个比特激活的过程一样，节点16触发后向右侧传递，需要节点2和节点9的值，而这两个节点的LR值已经保存，因此直接将已经获得的L(1)4(y41)和L(1)8(y85)两个LR值计算得到L(2)8(y81，u^1)，由于u2是冻结位，因此也直接置u2=0，并传递给下一个信息比特。

计算下一个比特时，需激活节点17，计算节点17的值需要节点18和节点19的LR值，而节点18和节点19的LR值在前面的过程中已经被保存下来，因此可以直接计算得到L(3)8(y81，u^21)。由于u3是信息比特，因此需要根据得到的LR值来估计u3，当L(3)8(y81,u^21)≥1时，估值为0，否则估值为1。得到估计值后继续传递到下一比特的计算，直到依次得到u81的所有估值。

通过上面SC译码过程可以看到，译码器由蝶形组成，例如，节点2、3、18、6构成一个蝶形，以节点2和节点18为根的计算子树又可以继续分裂后得到以节点3和节点6为根的译码子树。显然，在一个以4个节点构成的蝶形进行译码时，最先被激活的是最左上方的节点，最后被激活的是左下方的节点。

因此，蝶形图在LR的计算上有时间约束，任何一个蝶形图，计算左下方的节点需要提供左上方节点的LR值，而只有得到右侧节点的LR值才能计算出左上方节点的LR值。因此，可以说SC译码算法是一种串行迭代过程，计算LR值的等待时间将造成译码的较大时延，且SC译码是一种顺序译码，前面的译码结果会对后续的译码产生影响。

若Pe(N,K,A,uAc)表示Polar码译码差错率，则其表达式为


Pe(N,K,A,uAc)=∑uA∈XK12K∑yN1∈YN:u^N1(yN1)≠uN1WN(yN1|uN1)
(5.5.21)


可以获得它与信息位巴氏参数之间的关系为


Pe(N,K,A,uAc)≤∑i∈AZ(W(i)N)(5.5.22)


因此，当信息位的选择使得∑i∈AZ(W(i)N)足够小时，如趋于0，则译码的差错概率也趋于0。

SC译码MATLAB代码如下： 

function u_finish = decode(n,y,frozen_positions,frozen_bits)

%(阶数 接收值 冻结位序号 冻结位数字)

global sigma r_value r_flag max_number min_number

N=2^n;  %N为码长，n为阶数

r_value(:,n+1)=exp(-2*y'./(sigma^2)); %根据信道接收值和信噪比计算LR

r_flag(:,n+1)=ones(N,1);   %定义因子图的矩阵

u_finish=［］;

t=1;

for i=1:1:N

likelihood_ratio=ww(n,(1:N),i,u_finish);

%(当前阶数 初始接收值序号 信道序号 译完比特位)

if ismember(i,frozen_positions)  %判断是否为冻结位

u_finish(i)=frozen_bits(t);   %冻结位信息发送双方已知，直接赋值

t=t+1;

else if likelihood_ratio>1   %如果不是冻结位，根据最左端的节点信息来判决译码结果

u_finish(i)=0;      %如果 ifL(i)N(yN1，u^(i-1)1)≥1，译码结果为0

else u_finish(i)=1;   %否则译码结果为1

end

end

end

end



function likelihood_ratio=ww(n,y,i,u)

% 计算似然比(阶数 接收值序号 信道序号 译完比特位)

global  r_value r_flag nn max_number min_number

row=y(1)+ bit_reverse(i,n)-1;%对应在大矩阵中的行号

col=nn+1-n;%row是实际在大矩阵中的列号

if  r_flag(row,col)==1

likelihood_ratio=r_value(row,col);  

else

k=2^n;

y1=y(1:k/2);

y2=y(k/2+1:k);

kk=round(i/2);%向上取整

uue=u(2:2:2*kk-2);

uuo=u(1:2:2*kk-2);

uu=mod(uue+uuo,2);

if mod(i,2)==0

likelihood_ratio=feven(ww(n-1,y1,kk,uu),ww(n-1,y2,kk,uue),u(2*kk-1));%递归

if  likelihood_ratio> max_number

likelihood_ratio = max_number;

end       

else likelihood_ratio=fodd(ww(n-1,y1,kk,uu),ww(n-1,y2,kk,uue)); 

if  likelihood_ratio> max_number

likelihood_ratio = max_number;

end       

end

r_value(row,col)=likelihood_ratio;

r_flag(row,col)=1;

end

end



function likelihood_ratio=fodd(a,b)   %奇数节点似然信息计算

likelihood_ratio=(a*b+1)/(a+b);

end

function likelihood_ratio=feven(a,b,c)  %偶数节点似然信息计算

likelihood_ratio=a^(1-2*c)*b;

end

function num=bit_reverse(i,n)

num=1;

for k=n:-1:1

num=num+mod(i-1,2)*2^(k-1);

i=round(i/2);

end

end

码长1024、码率0.5的Polar码在高斯白噪声信道下的运行结果如图532所示。


图532Polar码编码结果



习题5
51设一个离散无记忆信道，其信道矩阵为


1212000

0121200

0012120

0001212

1200012



（1） 计算信道容量C。
（2） 找出一个长度为2的码，其信息传输率为（log5）/2（5个码字），如果按最大似然译码准则设计译码器，计算其译码器输出端平均错误译码概率Pe（设输入码字等概）。
（3） 有没有可能存在一个长度为2的码，使得每个码字的平均错误译码概率P(i)e=0(i=1,2,3,4,5)，即对所有码字有pe=0？如果存在，请找出来。
52设离散无记忆信道的输入符号集X∈{0,1}，输出符号集Y∈{0,1,2}，信道矩阵为［pji］=121414

141214。若某信源输出两个等概消息s1和s2，现用信道输入符号集中的符号对s1和s2进行信道编码，以ω1=00代表s1，用ω2=11代表s2，试写出能使平均错误译码概率pe=pemin的译码规则，并计算
平均错误译码概率。
53设有一离散无记忆信道，其信道矩阵为

P=1/21/31/6

1/61/21/3

1/31/61/2


若p(x1)=1/2，p(x2)=p(x3)=1/4，试求最佳译码时的平均错误概率。
54写出构成二元域上4维4重矢量空间的全部矢量元素，并找出其中一个三维子空间及其相应的对偶子空间。
55一个线性分组码的监督矩阵为


H=100100110

101010010

011100001

101011101


求其生成矩阵以及码的最小距离dmin，并画出该编码器硬件逻辑连接图。
56将本章例59的(7，4)系统码缩短为(5，2)码，写出缩短码的生成矩阵、校验矩阵，及所有码字。
57列出本章例59的(7，4)汉明码的标准阵列译码表。若收码R=(0010100，0111000，1110010)，由标准阵列译码表判断发码是什么。
58某线性二进码的生成矩阵为


G=0011101

0100111

1001110


（1） 用系统码 ［IP］ 的形式表示G。
（2） 计算该码的校验矩阵H。
（3） 列出该码的伴随式表。
（4） 计算该码的最小距离。
（5） 证明：  与信息序列101相对应的码字正交于H。

59设一个（15，4）循环码的生成多项式为g(x)=1+x+x5+x6+x10+x11。试求。
（1） 此码的监督多项式h(x)。
（2） 此码的生成矩阵（非系统码和系统码形式）。
（3） 此码的监督矩阵。

510设计一个(15，11)系统汉明码的生成矩阵G，以及由g(x)=1+x+x4生成的系统 (15，11)循环汉明码的编码器。
511计算(7，4)系统循环汉明码最小重量的可纠差错图案和对应的伴随式。
512某帧所含信息是(0000110101100010101100)， 循环冗余校验码的生成多项式是CRCITUT规定的g(x)=x16+x12+x5+1。问附加在信息位后的CRC校验码是什么？

513某卷积码(2，1，3)的转移函数矩阵是G(D)=［1+D2，1+D+D2+D3］，试
(1) 画出编码器结构图。
(2) 画出编码器的状态图。
(3) 求该码的自由距离df。

514某(2，1，4)卷积码，其两脉冲冲激响应（当输入信息为100…时所观察到的输出序列值）为g1=(11101)，g2=(10011)，试
(1) 画出该编码器结构图。
(2) 写出该码的生成矩阵。
(3) 若输入信息序列m=［11010001］，求相应的码序列。

515某码率为1/2、约束长度K=3的二进制卷积码，其编码器如图533所示。
(1) 画出状态图和网格图。
(2) 求转移函数T(D)，据此指出自由距离。 


图533习题515图


516某卷积码G0=［100］，G1=［101］，G2=［111］，
(1) 画出该码的编码器。
(2) 画出该码的状态图和网格图。
(3) 求出该码的转移函数和自由距离。
517某卷积码如图534所示。
(1) 画出该码的状态图。
(2) 求转移函数T(D)。
(3) 求该码的自由距离df，在格栅图上画出相应路径(与全0码字相距df的路径)。
(4) 当利用BSC信道进行数据传输时，接收序列为 10 01 00 11 10 00 00，试用维特比算法对接收序列进行译码的最可能原始信息序列。


图534习题517图