《信息论与编码》课件1第5章.ppt

1、第第5章章 有噪信道编码有噪信道编码 第第5章章 有噪信道编码有噪信道编码 5.1 最简单的编码方法最简单的编码方法 5.2 联合联合典型序列典型序列 5.3 有噪信道编码与有噪信道编码与Shannon第二编码定理第二编码定理 5.4 Shannon理论对信道编码的指导意义理论对信道编码的指导意义 5.5 线性分组码线性分组码 5.6 卷积码卷积码 5.7 Turbo码码 习题习题5第第5章章 有噪信道编码有噪信道编码 5.1 最简单的编码方法最简单的编码方法本节从最简单的编码方法入手，了解噪声通信中传输的基本原理和方法。由于噪声的存在，当发送方发送信息比特0时，接收方收到的不一定是0。一个最

2、简单的想法是，当发送比特mi时，重复发送n遍，接收方根据接收序列中0和1的个数多少来判定发送方发送的比特，这种编码方式称做重复码。第第5章章 有噪信道编码有噪信道编码【例例5.1】重复码是信息长度k=1的(n,1)码，其中,n是重复发送的长度，称为码长。经过编码后，码字集合中只有两个长度为n的码字（0000）和（1111）。设它们通过二进制对称信道传输，信道的转移概率为P=101，码长n可能取不同的值，进一步简化情况，只考虑n=3、5、7、，下面分别讨论。第第5章章 有噪信道编码有噪信道编码(1)n=3，（3，1）重复码，两个码字是（000）和（111），可能接收到的向量为000，001，01

3、0，011，100，101，110，111。当发送000时：没有出现错误，接收到000，判定为0：出现1比特错误，即可能接收到001、010、100时，仍可以判定为0，可以纠正1比特错误：出现2比特错误，即接收到110、101、011时，判定为1，此时就判错了：出现3比特错误，即接收到111时，只能判定为1，此时也判错了：那么就译错了。此时译码错误概率为Pe=1P(0)P(1)=1(1p)33p(1p)2=2.8102第第5章章 有噪信道编码有噪信道编码 (2)n=5，（5，1）重复码，两个码字是（00000）和（11111），可以纠正2个错，译码错误概率为332445355(1)(1)8.1

4、 10PC ppC ppp第第5章章 有噪信道编码有噪信道编码 (3)n=7，（7，1）重复码，两个码字是（0000000）和（1111111），可以纠正3个错，译码错误概率为对于信源X,P，每个符号的平均信息量为H(X)，则每个码符号的平均信息量为(5.1)4435526673777(1)(1)(1)2.6 10PC ppC ppC ppp()H XHn第第5章章 有噪信道编码有噪信道编码 其单位为信息单位/码符号。例如，当信息单位为比特时，每个码符号的平均信息量的单位为比特/码符号。由例5.1可知，每个信源符号所需要的码元越多，传输效率越低。我们把编码后的信息传输率定义为其中,M为使用的码

5、字的个数，信源符号的个数不会超过M。由于在信源输出和信道之间增加了信道编码器，导致信源符号和信道输入符号集不一致，因此码元符号集和信道输入符号集必须保持一致，以保证码元符号在信道中能顺利传输。(5.2)log MRn比特/码符号第第5章章 有噪信道编码有噪信道编码 在例5.1中，取n=3的重复码，相当于在集合000，001，010，011，100，101，110，111中取出了两个串000和111作为与信源符号0和1对应的码字，故M=2。一般地，信道输入符号集有r个符号，编码长度为n时，可以组成的可用码字个数为rn个。从中选取M(Mrn)个作为与信源符号对应的码字，则选择种类为。同样的个数M，

6、选择不同的码字集合，对应的最小错误概率可能就不一样。若信源符号集的符号个数为m，则应有mM。例5.1中，m=2，信源符号集为0,1。若取该信源符号集的离散无记忆二次扩展信源：nMrC第第5章章 有噪信道编码有噪信道编码 X2=00,01,10,11m=4,仍在000，001，010，011，100，101，110，111中选取M=m=4个码字，则可以有种选择方法。例如000，001，010，100、000，011，100，110和000，010，100，110，每一种选择均可计算出相应的最小错误概率。在信道输入符号集分布未知的情况下，我们假设等概率分布是合理的。对应码字集合000，001，01

7、0，100的最小错误概率约为2.28102，对应码字集合000，011，100，110的最小错误概率约为2102。4870C 第第5章章 有噪信道编码有噪信道编码 若传输每个码元的平均时间为t秒，则编码后每秒钟传输的信息量为 在简单重复编码方法中，有以下结论（设t=1）：n=1:R=1 比特/码符号Rt=1 比特/秒(5.3)比特/秒log MRnt第第5章章 有噪信道编码有噪信道编码 n=3:比特/码符号比特/秒n=5:比特/码符号比特/秒13R t13R 15R t15R 第第5章章 有噪信道编码有噪信道编码 n=7:比特/码符号比特/秒可见，对于重复扩展编码方法而言，Pe下降时，编码信息

8、传输率R也随之下降。在实际的通信系统中，我们并不希望R下降太多，而是希望在保证R为一定值的前提下，使错误概率下降。显然，重复编码并不是最好的编码方法。17R t17R 第第5章章 有噪信道编码有噪信道编码【例例5.2】信源符号集为0，1，离散无记忆二次扩展信源为00，01，10，11，信道为前述的二进制离散无记忆对称信道，P(0|1)=P(1|0)=p0,n0使得当nn0时，有PxTX(n,)1(5.6)(,)XTn第第5章章 有噪信道编码有噪信道编码 推论推论1（特定典型序列出现的概率）若xTX(n,)，则2nH(x)+P(x)2nH(x)(5.7)证明：由定义式(5.4)有：不等式各项取指

9、数即可得证。该推论说明，所有典型序列出现的概率都在同一范围内，当足够小时，概率几乎为一常量，且当n增大时，该概率随nH(X)指数减少。(5.8)1()log()()H XPH Xn x第第5章章 有噪信道编码有噪信道编码 推论推论2（典型序列的数目）当n足够大时，对于给定的信源和0，典型序列的数目满足：(1)2nH(X)TX(n,)2nH(X)+(5.9)第第5章章 有噪信道编码有噪信道编码 证明：故TX(n,)2nH(X)+()(,)(,)()1()()2 (,)2nXXn H XTnTnXn H XXPPTnxxxxx第第5章章 有噪信道编码有噪信道编码 据式(5.5)和式(5.6)有：故

10、TX(n,)(1)2nH(X)证毕。()()(,)(,)1()2(,)2XXn H Xn H XXTnTnPTnx第第5章章 有噪信道编码有噪信道编码 由式(5.9)可知：TX(n,)2nH(X)(5.10)信源划分定理及其推论说明,一个离散无记忆信源的输出符号序列可分成TX(n,)和两组，有。TX(n,)中各序列出现的概率几乎相等，且每个序列中一个信源符号的平均信息量接近于信源的熵H(X)，所有典型序列的概率和趋向于1。因此，典型序列集又可称为高概率集，非典型序列集称为低概率集，信源的这种划分性质渐近等同于分割性。典型序列又称做渐近等概序列。(,)XTn(,)(,)nXXTnTnX第第5章章

11、 有噪信道编码有噪信道编码 由于典型序列集在整个信源输出序列中占绝对优势，所以在信息论的研究中可以忽略非典型序列集而只考察典型序列集。尽管TX（n,）中元素个数不少，约为2nH(X)个，但与Xn相比，仍是非常少的一部分。事实上，若X=r，则Xn中的元素个数为rn=2n logr个，有：第第5章章 有噪信道编码有噪信道编码 若nlogrH(X)0，即信源非等概分布，则有n时0。若信源等概,H(X)=logr，则由式(5.10)得：TX(n,)2nH(X)，即信源等概分布时几乎所有序列都是典型序列。log()(,)2xnr H XnT nX第第5章章 有噪信道编码有噪信道编码 定义定义5.4 令X

12、、Y是两个概率空间，x=(x1,x2,xN)Xn，y=(y1,y2,yn)Yn。若序列对x和y满足：(1)x是典型序列，即对任意小的正数，存在n，使得：(5.11)1log()()PH Xnx第第5章章 有噪信道编码有噪信道编码(2)y是典型序列，即对任意小的正数，存在n，使得：(5.12)1log()()PH Yny第第5章章 有噪信道编码有噪信道编码(3)(x，y)是典型序列，即对任意小的正数，存在n，使得：(5.13)则称序列对(x，y)是联合典型序列，表示为TXY(n,)。给定y，称集合：TX|Y(n,)=x：xyTXY(n,)(5.14)为条件y下X的典型序列。1log()()PH

13、XYnxy第第5章章 有噪信道编码有噪信道编码 定理定理5.2 当n足够大时,有：TX|Y(n,)2nH(X|Y)+2(5.15)证明：|TX|Y(n,)|=0，引理显然成立。，有：(,),YTn y(,),YTn y第第5章章 有噪信道编码有噪信道编码/()(,)(,)()(/)2/()(,)(,)(,)21(/)()()()2(,)22nnX YX YX Yn H XYTnTnXXn H XYn H X YX Yn H YTnPPPPPPTnxxxx yx yx yyyy(/)2/(,)2N H X YX YTN第第5章章 有噪信道编码有噪信道编码 同理可证:TY|X(n,)2nH(Y|X

14、)+2(5.16)证毕。第第5章章 有噪信道编码有噪信道编码 定理定理5.3 若对于xXn,yYn,x、y统计独立，(x，y)是联合典型序列，则当n足够大时，有：(5.17)(;)3 (;)3(,)(,)(1)2()()2XYn I X Yn I X YTnPP xyx yxy第第5章章 有噪信道编码有噪信道编码 证明：由于x、y均为典型序列，故有：(5.18)(5.19)(5.20)()()2()2n H Xn H XPx()()2()2n H Yn H YPy()()(1-)2(,)2n H xyn H xyxyTn第第5章章 有噪信道编码有噪信道编码 将上述三个不等式相应项相乘，考虑到：

15、I(X;Y)=H(XY)H(X)H(Y)(5.21)证毕。如前所述，联合典型序列要求(x，y)必须是典型序列，令：L=TX(n,)TY(n,)(5.22)第第5章章 有噪信道编码有噪信道编码 由信源划分定理推论2可得出L的上、下限为(1)22nH(X)+H(Y)-2L2nH(X)+H(Y)+2(5.23)由式(5.20)和式(5.23)可得：(5.24)(;)3 -2(;)3(,)(1)2(1)2n I X Yn I X YXYTnL第第5章章 有噪信道编码有噪信道编码 由于为任意小的正数，因此(1)21，从而TXY(n,)/L和式(5.17)中的量的上、下限保持一致。TXY(n,)/L为联合

16、典型序列的由典型序列x、y构成的空间中的平均密度。(,)(,)()()xyx yTnXYPPxy第第5章章 有噪信道编码有噪信道编码 5.3 有噪信道编码与有噪信道编码与Shannon第二编码定第二编码定在前面的讨论中已经提到,在通信系统中，信道是非常重要的组成部分，且由于信道中随机噪声的存在，信道在传输符号时会产生畸变，从而使接收到的符号序列与发送端的符号序列不一致。为此，需要寻找编码方法，在信道噪声存在的情况下能够检测进而纠正发生错误的符号，以提高通信系统的可靠性。第第5章章 有噪信道编码有噪信道编码 从概率的角度研究噪声通信的问题就是要研究是否存在一种编码方法使得编码信息传输率保持较大，

17、这就是著名的Shannon第二编码定理，也称为有噪信道编码定理。任意给定希望达到的编码信息速率R和错误概率限度，只要R小于信道容量，就可以找到一种编码方法，使得码长足够大时，错误概率达到小于的要求。第第5章章 有噪信道编码有噪信道编码 定义定义5.5 对给定离散无记忆信道和任意0，若有一种编码信息速率为R的码，在码长n足够大时，能使Pe，则称R是可达的。第第5章章 有噪信道编码有噪信道编码 定理定理5.4（Shannon第二编码定理，有噪信道编码定理）给定信道容量为C的离散无记忆信道P(y|x)，若编码信息传输率RC，则R是可达的。等价描述：给定信道容量为C的离散无记忆信道P(y|x)，若编码

18、信息传输率RC，则只要码长n足够长，总可以在输入集合中找到M个码字对应M种可能的信源消息符号，组成一个码集合，M2n(C)，为任意小的正数，在一定的译码规则下，可使信道输出的错误概率任意小。第第5章章 有噪信道编码有噪信道编码 解释解释：设信道容量为C的离散无记忆信道有r个输入符号（从而码符号也有r个）、s个输出符号，则码长为N时，可将信道看成是离散无记忆的n次扩展信道，扩展信道的输出符号集有sn种选择，输入符号集有rn种选择，从rn种选择中选出M种作为码字，对应M种可能的消息符号。为了正确译码，应有Msn。下面我们来证明Shannon第二编码定理。第第5章章 有噪信道编码有噪信道编码 设信道

19、输入序列为x，xXn，x=(x1,x2,xn)，输出为yYn,y=(y1,y2,yn)，转移概率为 若发送消息为xm，接收序列为y，则在发送消息xm的条件下的译码错误概率为Pem=P(xkxm|y)1(|)(/)niiiPP yxy x第第5章章 有噪信道编码有噪信道编码 消息独立、等概时的平均错误率（针对每个XN）为(5.25)其中,M为消息数目。从Xn中独立随机地选择M=2nR个序列作为码字，这相当于每个码字出现的概率为其中,R是要求的编码信息传输率;xXn，x=(x1,x2,xn)，并设X中的所有元素独立、等概地出现。这种编码方法称为随机编码。ee1mmPPM1()()niiPP xx第

20、第5章章 有噪信道编码有噪信道编码 取译码规则：对给定的接收序列y，若存在唯一的k1,2nR，使(xk,y)TXY(n,)则将y译为xk，即F(y)=xk第第5章章 有噪信道编码有噪信道编码 若实际发送的为xm，则当km或两个以上(含两个)的k与y构成联合典型序列时就认为出现译码错误。由于随机码具有对称性，因此译码错误概率与送出消息的标号无关，即随机码集合的平均错误概率就是任一特定消息被错误译码的概率。不失一般性，设发送的是第一个消息，令事件：Em=(xm,y)TXY(n,)m1,2nR第第5章章 有噪信道编码有噪信道编码 则发送消息x1时，译码错误概率为ee1111111/()|(|)kkk

21、kkPPPPEP Exxxxx而111(|)(,)(,)(/)1nYkmXYjjP EPTnPkxxyyx又(,)(,)(,)(,)mXYkXYPTnPTnxyxy第第5章章 有噪信道编码有噪信道编码 与j无关，故 由定理5.2得:P(Ek)2nI(X;Y)3(5.26)1(|)(,)(,)1kmXYP EPTnkxxy所以(;)3(;)3 1()222nRn I X Yn R I X YkkP E第第5章章 有噪信道编码有噪信道编码 为了使R大，故使I(X;Y)极大化，即取I(X;Y)=C。若RC3，则n时，上式趋向于。由于错误概率非负，因此错误概率趋向于。由于当RC3时，随机码集合的平均译

22、码错误概率趋向于，所以必然存在一种码，当n足够大时，其译码错误概率任意小。证毕。第第5章章 有噪信道编码有噪信道编码 码的个数为2nR，由于为任意小的正数，因此=3仍为任意小的正数，故码字数目满足M=2nR2n(C)，为任意小的正数，从而等价描述成立。借助于典型序列的概念，我们证明了离散无记忆信道编码定理，指出只要RC时情况如何呢？信道编码逆定理给出了答案。第第5章章 有噪信道编码有噪信道编码 定理定理5.5（信道编码逆定理）设离散无记忆信道的信道容量为C，当信息传输速率RC(选用码字个数M=2n(C+)时，无论n多大也不能找到一种编码，使译码错误概率任意小。第第5章章 有噪信道编码有噪信道编

23、码 证明：假设选用M=2n(C+)码字组成的一个码，每个码字的概率是1/M，则离散无记忆信道的n次扩展信道的平均互信息为H（Xn）H(Xn|Yn)nC(5.27)则log2n(C+)H(Xn|Yn)nC(5.28)即nH(Xn|Yn)第第5章章 有噪信道编码有噪信道编码 由Fano不等式有：nH(Xn|Yn)H(Pe)+Pe log(M1)1+Pe log(M1)所以n1+Pelog(M1)1+PelogM=1+Pe(nC+n)求得：当n时，从而Pe为非零值。证毕。e1nPnCn10nnCnC第第5章章 有噪信道编码有噪信道编码 以上只是在离散无记忆信道的情况下对定理做了证明，事实上，Shan

24、non第二编码定理和逆定理对连续信道、有记忆信道同样成立。现已证明离散无记忆信道中译码错误概率Pe趋于零的速度与n（码长）成指数关系，即当RC时，译码错误概率为(5.29)式中,Er(R)为随机编码指数，又称做可靠性函数，其表达式为()eernERP第第5章章 有噪信道编码有噪信道编码 其中,为人为定义的修正系数，01。可见，可靠性函数又与输入概率分布有关。一般Er(R)与R的关系曲线如图5-2所示，是一条下凸函数。从图5-2中可以看出，R0，所以式(5.29)表明Pe随着n的增大以指数趋于零。Shannon第二编码定理只是一个存在性定理，它说明错误概率趋于零的好码是存在的，但是并没有给出怎么

25、构造，尽管如此，它对信道编码的发展仍具有重大的指导意义。(5.30)001()()maxmax,()rP xE REP xR 第第5章章 有噪信道编码有噪信道编码 图5-2 Er(R)与R的关系曲线 第第5章章 有噪信道编码有噪信道编码 5.4 Shannon理论对信道编码的指导意义理论对信道编码的指导意义信息传输的可靠性是所有通信系统努力追求的首要目标。要实现高可靠性的传输，可采取诸如增大发射功率、增加信道带宽、提高天线增益等传统方法，但这些方法往往难度比较大，有些场合甚至无法实现。Shannon信息论指出：对信息序列进行适当的编码后同样可以提高信道的传输可靠性，这种编码即为信道编码。信道编

26、码是在著名的信道编码定理的指导下发展起来的，几十年来已取得了丰硕的成果。第第5章章 有噪信道编码有噪信道编码 5.4.1 二进制离散无记忆信道下的极限二进制离散无记忆信道下的极限二进制对称信道的信道容量为C=1+plogp+(1p)log(1p)比特/码元(5.31)采用相干PSK信号发送和接收码字比特，有(5.32)sbc002EE RpQQNN第第5章章 有噪信道编码有噪信道编码 令式(5.31)中的C=Rc，求出满足式(5.32)的Eb/N0值。假如采用码率Rc=1/2的编码方式，则为了获得硬判决译码时该码的容量，要求每比特最小信噪比约为1.6 dB。当码率渐近于零时，我们关心的是最小信

27、噪比极限。在Rc较小时，概率p近似为(5.33)bc012E RPN第第5章章 有噪信道编码有噪信道编码 把p的表达式代入式(5.31)，并利用式:可把信道容量公式简化为(5.34)22log(1)ln2xxxbc02ln2ECRN第第5章章 有噪信道编码有噪信道编码 再令C=Rc，在Rc趋近于零的极限情况下，可得:（0.37dB）(5.35)也就是说，在二进制离散信道下，只要传输每比特信息的信噪比不低于0.37 dB，就可能实现完全无差错的传输。b01ln22EN第第5章章 有噪信道编码有噪信道编码 5.4.2 AWGN信道下的理论极限信道下的理论极限由信息论中对波形信道的分析可知，当信道中

28、的噪声为加性高斯白噪声时，其信道容量为(5.36)其中,Ps是信号的平均功率，W为信道带宽。st0log 1PCWN W第第5章章 有噪信道编码有噪信道编码 令Ps=RtEb，Rt为信息传输速率（比特/秒），Eb为传输每一比特信息所需的平均功率，则式(5.36)可化为(5.37)tbt0log 1NR ECWW第第5章章 有噪信道编码有噪信道编码 式中,Eb/N0可理解为每赫兹带宽传输每比特信息所需的信噪功率比。式(5.37)表明了通信系统中带宽W、信道容量Ct、信噪比Eb/N0之间的定量关系。显然，增加带宽和提高信噪比都能使信道容量得到增加，从而使一定的信息传输率Rt下的错误概率减小。在信道

29、带宽不受限的情况下，信道容量仅取决于信噪比，进而此时传输可靠性主要由信噪比决定。由式(5.37)可得：(5.38)tbt021CWERNW第第5章章 有噪信道编码有噪信道编码 令式(5.38)中W，且RtC，则可得到可靠传输时所需的最小信噪比为(5.39)式(5.39)表示在带宽不受限的高斯白噪声信道中，只要传输每比特信息的信噪比不低于1.6 dB，就可能实现完全无差错的传输。这是高斯信道中传送信息的极限能力，这一信噪比的极限值称为Shannon限。tb0min21limln21.6 dBCWWECNW 第第5章章 有噪信道编码有噪信道编码 通过前面的分析可以知道，在二进制对称信道下，达到信道

30、容量所需要的信噪比为0.37 dB，所以在实际的译码过程中建议采用波形信道模型，可获得大约2 dB的增益。当信道带宽有限，且信道输入为二元输入时，需将式(5.37)中的Ct和Rt按通带归一化，令tn,22RCCRWW第第5章章 有噪信道编码有噪信道编码 即得:(5.40)或(5.41)bn01log 122ECRNn2b0212CENR第第5章章 有噪信道编码有噪信道编码 令RCn，则可得带限信道中二元信息可靠传输时所需的信噪比为(5.42)令码率，则得：(5.43)2b01212RENR12R b01EN第第5章章 有噪信道编码有噪信道编码 这是带限高斯信道以1/2的码率可靠传输每比特二元信

31、息所需的最小信噪比，是Shannon限的另一种表述。实际上不采取任何编码措施的传输系统是不可能以这么低的信噪比实现可靠传输的。采取信道编码后，在某一误码率指标下，经过仿真计算，所需信噪比可比不编码时有明显减少。编码的分析设计有两条基本途径。一是不涉及具体的编码，运用概率统计的方法，在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下边界，这就是本章前半部分的内容。第第5章章 有噪信道编码有噪信道编码 这种方法不能得知最优码是如何编出来的，却能得出最优码可以好到什么程度，对指导编码技术具有特别重要的理论价值。另一条途径是数学解析途径，将代数、集合、数论等理论运用到编译码中来设计某种码

32、，比如分组码、卷积码、Turbo码等。本章后面几节将简单介绍这几种编码方式，主要目的是了解Shannon定理对编码的指导意义。信道编码更深、更系统的知识请参照相关的专业书籍。第第5章章 有噪信道编码有噪信道编码 5.5 线性分组码线性分组码本节讨论纠错码中最基本的一类码，即线性分组码。这类码有明显的数学结构，它虽然简单，但却是各类码的基础，且许多已知的好码都属于线性分组码。5.5.1 线性分组码的编码线性分组码的编码为了引入线性分组码的概念，首先看下面的例子。第第5章章 有噪信道编码有噪信道编码【例例5.3】任给一个由k=3位信息组成的信息组m=(m2,m1,m0)，由它生成的(6，3)线性分

33、组码的码字v=(v5,v4,v3,v2,v1,v0)由下列关系式确定：3221120010 0,1,2,iivmivmm vmm vmm第第5章章 有噪信道编码有噪信道编码 由于每个信息组共有k=3位信息码元，信息组集合共由23=8个不同的信息组构成，因此上述关系生成的(6，3)线性分组码共有8个码字。对于任意信息组m=(m2,m1,m0)，生成的码字:v=(m2,m1,m0,m2+m1,m2+m0,m1+m0)(5.44)第第5章章 有噪信道编码有噪信道编码 若用向量与矩阵的乘积表示式(5.44)，则可写成：v=(m2,m1,m0)G其中:称为该(6，3)码的生成矩阵。有了生成矩阵G，不难将

34、23=8个信息组变换成表5-1所示的(6，3)码的8个码字。100110010101001011G从生成的码字可以看出，前k=3位是原信息组，而后nk=3位是由式(5.44)确定的监督元，因此我们称(6，3)码为系统码。第第5章章 有噪信道编码有噪信道编码 表5-1 (6，3)码的码字 第第5章章 有噪信道编码有噪信道编码 定义定义5.6 信息组以不变的形式，在码字的任意k位中出现的码称为系统码，否则，称为非系统码。一般地，我们把信息组排在码的前k位，分析(n，k)系统码的生成矩阵可以看出，它的左边必然是一个kk阶单位矩阵，因此矩阵G的秩为k。若分别用Ik和P表示G的两个矩阵块，则生成矩阵G可

35、表示成G=IkP(5.45)第第5章章 有噪信道编码有噪信道编码 通常把上式表示的生成矩阵G称为标准型生成矩阵，G的k行是线性无关的。事实上，G的每一行都是码集合中的一个码字，展开来写就是：1,11,21,02,12,22,0,1,2,0100010001rrrrk rk rkvvvvvvvvvG第第5章章 有噪信道编码有噪信道编码 因此可归纳出一般(n,k)系统线性分组码的结构形式如下：一般地，如果码元vn1,vn2,vnk也是mk1,mk2,m0的线性组合，则可得到非系统线性分组码，即1,11,21,02,12,22,010,1,2,0nnnnkkk nk nkggggggmmmgggCm

36、 G第第5章章 有噪信道编码有噪信道编码 其中:是一个秩为k的kn阶矩阵。当G是式(5.45)表示的标准型生成矩阵时，它才生成系统码，这时它生成的码字前k位是原信息组，后r=nk位是监督元。1,11,21,02,12,22,0,1,2,0nnnnk nk nkgggggggggG第第5章章 有噪信道编码有噪信道编码 对于一般情况，如果不给出信息组和码字的对应码表，而只给出一个码集合，如000000，001011，010101，011110，100110，101101，110011，111000此时我们无法知道该码字对应哪个信息组。实际上，k个线性无关的码向量的一切线性组合共有2k个可能，它恰好

37、是V的2k个码字，因此任意两个码字的和仍是码字，而全零n维向量0=(000)是由信息组m=(000)生成的码字，对于任意lF2，vV，则lV仍是V中的码字，即(n,k)线性分组码V是n维线性空间Vn(2n)的一个k维子空间。既然(n,k)分组码的2k个码字组成了一个k维子空间，那么这2k个码字完全可由k个独立向量所组成的基底而生成。第第5章章 有噪信道编码有噪信道编码 设基底为11,11,21,022,12,22,0,1,2,0(,)(,)(,)nnnnkk nk nkgggggggggCCC第第5章章 有噪信道编码有噪信道编码 若把这组基底写成矩阵形式，则有1,11,21,02,12,22,

38、0,1,2,0nnnnk nk nkgggggggggG第第5章章 有噪信道编码有噪信道编码(n,k)码的任何码字都可由这组基底的线性组合而生成，即1,11,21,02,12,22,010,1,2,0nnnnkkk nk nkggggggmmmgggCm G第第5章章 有噪信道编码有噪信道编码 若已知信息组m，通过上式可求得相应的码字，称上式中的G为(n,k)码的生成矩阵。例如表5-1中的(6,3)码，可从它的8个码字中任意挑选出k=3个线性无关的码字，作为码的生成矩阵的行，则1100110010101001011G第第5章章 有噪信道编码有噪信道编码 也可以是 下面介绍一下描述分组码的几个参

39、数。2101101110011111000G第第5章章 有噪信道编码有噪信道编码 定义定义5.7 码率R=k/n表示(n，k)分组码中，信息位在码字中所占的比重。定义定义5.8 汉明距离d(a,b)表示向量a与b不相等的对应分量的个数，简称距离。第第5章章 有噪信道编码有噪信道编码 定义定义5.9 n重向量v中非零码元的个数称为汉明重量，用W(v)来表示。(n，k)分组码中，任两个码字之间距离的最小值称为该分组码的最小汉明距离dmin，简称最小距离，即dmin=mind(vi,vj)|vi,vjv,ij R和dmin是(n，k)分组码的两个重要的参数。纠错编码的基本任务之一就是构造出R一定、d

40、min尽可能大的码字，或dmin一定、R尽可能高的码字。第第5章章 有噪信道编码有噪信道编码 5.5.2 最小距离译码最小距离译码译码器接收到一个二进制序列，而译码器输出的是信息序列m的估值序列。译码器的基本任务就是根据某种译码规则，由接收序列R给出与发送的信息序列m最接近（最好是相同）的估值序列。由于m与码字v之间存在一一对应的关系，所以这等价于译码器根据R产生一个v的估值序列。显然，当且仅当=v时，=m，这时译码器正确译码。m m v m v第第5章章 有噪信道编码有噪信道编码 当给定接收序列R时，译码器的条件译码错误概率定义为(5.46)所以，译码器的错误译码概率:(5.47)()()P

41、 E RPRvv()()()RP EP E R P R第第5章章 有噪信道编码有噪信道编码 P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使(5.48)因此，如果译码器对输入的R，能在2k个码字中选择一个使min()min()min()min()max()RRP EP E RPRPRPRvvvvvv()(1,2,2)kiPRivv第第5章章 有噪信道编码有噪信道编码 最大的码字vi作为v的估值序列，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译码。由贝叶斯公式得到:v()()()()PP RPRP Rvvv第第5章章 有噪信道编码有噪信

42、道编码 若发端V中每个码字等概率发送，即假设先验概率P(v)相等，则P(v）=1/2k，且由于P(R)与译码方法无关，所以后验概率P(v|R)最大等价于条件概率P(R|v)最大，P(R|v)称为似然函数，这种译码准则称为最大似然译码，记为MLD。显然，最大似然译码等价于最大后验概率译码。当r与vj的距离最小时，认为发方发送vj、收到r的概率最大，可以据此译码。其依据是下面的定理。第第5章章 有噪信道编码有噪信道编码 定理定理5.6 如果BSC信道的转移概率p是一个很小的数，则当接收到的r与V中的码字vj的距离最小，即d(r,vj)P(r|vi)i=1,2,qk;ij第第5章章 有噪信道编码有噪

43、信道编码 证明：设d(r,vj)=d，对于V中任意一个码字vivj，令d(r,vi)=d，由定理条件知dd，于是发送vj、收到r的条件概率为P(r|vj)=pd(1p)ndpd发送vi、收到r的条件概率为P(r|vi)=pd(1p)ndpd由于dpd，P(r|vj)P(r|vi)由此可见，对于硬判决译码，在先验等概的情况下，最大似然译码等价于最小距离译码。第第5章章 有噪信道编码有噪信道编码【例例5.4】一个数字通信系统的误码率为P=104，因而收到一个7位码元的码字有一位码元有错的概率为同理，有27位码元有错的概率分别为144 647(1)10(1 10)7 10PC第第5章章 有噪信道编码

44、有噪信道编码 22577(2)(1)2.1 10PC pp334117(3)(1)3.5 10PC pp443157(4)(1)3.5 10PC pp552197(5)(1)2.1 10PC pp66247(6)(1)7 10PC pp77287(7)10PC p第第5章章 有噪信道编码有噪信道编码 如果不发生错误的概率为P(0)，则P(0)=(1p)70.9993由以上结果可以看出：P(0)P(1)P(7)即发生t个错误的概率远远大于发生t+1个错误的概率。因此，当我们收到一个r时，若它不属于码集V，则可将r与V中所有码字作比较。当r与vj的距离最小时，发送vj、收到r的条件概率最大，因而可

45、将r判决为vj。第第5章章 有噪信道编码有噪信道编码 实现最小距离译码有一种直观的方法，即计算接收到的码字与所有可能发送的码字之间的距离，取距离最小的码字为译码结果，也就是将收到的码字与码集合当中所有可能的码字进行比较，与哪个码字的距离最小，就判决输出。这种方法固然实现了最小距离译码的思想，但事实上，当码长较长时，计算量相当大，无法实现。下面介绍一种最简单的译码方法，称为陪集译码。第第5章章 有噪信道编码有噪信道编码 构造译码表的方法如下：（1）表的第一行为2k个码字，全0码字放在最左边。（2）将所有可能的n维向量中重量最小的，且在前面行中没有出现过的向量放在此行的第一列中，将此向量与码向量相

46、加，放到此行相应的列上。(3)重复第(2)步，直到2n个向量完全分到表中。例如，例5.3中的（6，3）码的陪集译码表如表5-2所示。第第5章章 有噪信道编码有噪信道编码 表5-2 例5.3中的（6，3）码的陪集译码表 第第5章章 有噪信道编码有噪信道编码 表5-2中第一列称为陪集首。通过译码表的构造过程可以知道，每个码字所在列上其他向量都是距离正确码字距离最小的向量（陪集首的重量最小）。如果接收到向量出现了错误，则将它译成所在列的码字（即第一行上的向量）。若接收到向量011101，则译成010101。第第5章章 有噪信道编码有噪信道编码 5.5.3 伴随式译码伴随式译码下面首先引入校验矩阵的概

47、念。从例5.3中很容易得到：(5.49)542531430000vvvvvvvvv第第5章章 有噪信道编码有噪信道编码 若V=(v5,v4,v0)是该(6，3)码的一个码字，则V的6个码元一定满足式(5.49)的三个方程。反之，若有一个r=(r5,r4,r0)不完全满足式(5.49)中的三个方程，则它一定不是该(6，3)码的码字，因此式(5.49)中的三个方程对码字起监督作用，我们称这三个方程为监督方程。若用矩阵表示，则有5401101001010100011001vvv第第5章章 有噪信道编码有噪信道编码 若令则H称为码的一致监督矩阵，简称监督矩阵。该码的任一个码字v都应满足HvT=0。11

48、0100101010011001H第第5章章 有噪信道编码有噪信道编码 事实上，监督方程也可以用更一般的形式表示，即监督方程可以写成如下形式：若用矩阵表示，即得:1112121 0121222201122000 0nnnnnnrnrnnrh vh vh vh vh vh vh vh vh v1121111222221200nnnnrrnrhhhvhhhvhhhv第第5章章 有噪信道编码有噪信道编码 或者HvT=0，这里仍旧称为该码的监督矩阵，它的r行是线性无关的。从监督矩阵的推导过程知道，它的每一行表示求一个监督元的监督方程，因为每个码字共有r=nk个监督元，所以任何一个(n,k)线性分组码的

49、监督矩阵H至少有r=nk行，且有r行是线性无关的。112111222212nnrrnrhhhhhhhhhH第第5章章 有噪信道编码有噪信道编码 我们知道，线性分组码的纠错能力与它的最小距离dmin有着密切的关系，dmin越大,它的纠错能力越强，因此讨论H与dmin的关系就是讨论H与码的纠错能力的关系。第第5章章 有噪信道编码有噪信道编码 定理定理5.7 一个(n，k)线性分组码的最小距离为dmin的充分必要条件是它的监督矩阵H的任意dmin1列线性无关，而有dmin列线性相关。第第5章章 有噪信道编码有噪信道编码 证明：先证必要性。如果(n，k)码的最小距离为dmin，则由分组码的性质可知，最

50、小码重Wmin=dmin，于是存在一个码字v=(vn1,vn2,v0)，它的重量为dmin，即v有d=dmin个码元不为0，不妨设不为0，其余码元为0，设码的监督矩阵为H=n1n20其中ni表示H矩阵的第i个列向量，于是由HvT=0得到即H中有d=dmin列线性相关。12dn in in ivvv、11220ddTn in in in in in ivvvH Hv v第第5章章 有噪信道编码有噪信道编码 11220ddnpnpnpnpnpnpvvv如果H中有dmin1=d列也线性相关，不妨设于是存在一个码字v，它的码元不为0，其余码元为0，使12dn pn pn pvvv、T11220 00n