哈工大信息论讲义第7-8章

第七章卷积码过失控制编码系统中除了使用分组码之外，另一类广泛应用的称为卷积码，在分组码的编码和译码过程中，每个码字的监督元只与本码字的信息元有关，而与其它码字的信息元无关，即分组码的编码器是一个无记忆的逻辑电路。但是，卷积码的编码过程中，本码字的监督元不仅与本码字的信息元有关，而且与前m个码字的信息元有关，因此卷积码的编码器是一个有记忆的时序电路。卷积码由于更充分地利用码字之间的相关性，可以减少码字长度，简化编译码电路，并得到较好的过失控制性能，因此卷积码在通信领域，特别是卫星通信，空间通信领域得到广泛的应用。7.1卷积码的根本原理7.1.1卷积码的根本概念[例子]：通过一个例子说明卷积码的一些根本概念；图7-1给出了一个(3,2,2)卷积码编码器的原理图，图7-1(3,2,2)卷积码编码器原理图当某一时刻，编码器输入并行一个信息码字为mi=[mi(1),mi(2)]，编码器并行输出由三个码元组成的卷积码的码字，[ci]=[ci(1),ci(2),ci(3)]=[mi(1),mi(2),pi]。[ci]称为一个码字。mi为信息元，pi为监督元。可以看出卷积码的输入输出关系为：ci(1)=mi(1)ci(2)=mi(2)ci(3)=mi(1)+mi(2)+mi-1(2)+mi-2(1)可见，卷积码当前输出的码字的监督元不仅与当前输入的信息元有关而且还与前2个码元有关。这时编码器由2级移位存放器构成。定义：卷积码字中码元的个数为n0，码字中信息元个数为k0，由m级移位存放器构成的编码器称m为编码码字约束长度。有的教材称m’=m+1为约束长度，(m+1)n0为编码码元约束长度。卷积码记为(n0,k0,m)。定义：R=k0/n0为码率(Coderate)。它是表示卷积码的编码效率。卷积码的编码器的一般形式为：图7-2卷积码编码器一般形式看以下卷积码的约束关系图：图7-3卷积码的约束关系在译码过程中，译码字ci时要利用到ci-1,ci-2，同时译码字ci+1,ci+2时还要利用到ci。因此译码约束长度一般要大于编码约束长度，因为：虽然一般理解译码字ci时只利用ci-1,ci-2但实际上这时译出的ci可能译错，当译ci+2时同样是对ci的一种校验。还可以对cI的译码进行修改。这是卷积码的特别之处。如果卷积码编码器的输入端输入有头无尾的一个半无限序列，即信息码字序列为[m]=m0,m1,m2,…mi…，那么编码器的输出也将是一个半无限序列，[C]=c0,c1,c2,…ci,…，称为卷积码的码字序列。卷积码同样有系统卷积码和非系统卷积码之分。系统卷积码的码字中明显的包含着k0位信息码元，而非系统卷积码的信息码元是隐含在码字中的。图7-4(2,1,2)卷积码编码器原理图如下图，为一个(2,1,2)非系统卷积码的编码器；约束关系为：ci(1)=mi-2+mi-1+mici(2)=mi-2+mi如果输入的信息序列为：[m]=(m0,m1,m2,……)=(1,1,1,……)那么输出的码字序列为：[C]=(11,01,10,……)。7.1.2卷积码的监督矩阵描述同分组码一样，卷积码也可以用生成矩阵和监督矩阵来描述。[截短卷积码的根本监督矩阵]：通过一个例子说明：看一个(3,1,2)系统卷积码，其编码电路为：图7-5(3,1,2)系统卷积码编码器原理图n0=3,k0=1,m=2,m’=m+1=3输入信息序列：m={……mi+1,mi,mi-1,mi-2,……}输出码字为：[ci]={mi,pi1,pi2}可以看出其监督关系为：pi1=mi+mi-1pi2=mi+mi-2下面看一下在编码器一个约束长度的监督关系：0mi-2+0pi-2,1+0pi-2,2+1mi-1+0pi-1,1+0pi-1,2+1mi+1pi,1+0pi,2=01mi-2+0pi-2,1+0pi-2,2+0mi-1+0pi-1,1+0pi-1,2+1mi+0pi,1+1pi,2=0写成方程的矩阵形式：000100110[Ci]T=[0]100000101其中码字序列[Ci]为截短卷积码；[Ci]=[ci-2,ci-1,ci]=[mi-2,pi-2,1,pi-2,2,mi-1,pi-1,1,pi-1,2,mI,pi,1,pi,2]定义其系数矩阵为：[h]=000100110=[P20P10P0I2]=[h2h1h0]100000101称为截短卷积码的根本监督矩阵。[P2]=0[P1]=1[P0]=1[0]=0[I2]=10101001根本监督矩阵的一般形式为：[h]=[Pm0Pm-10……P10P0Ir0]=[hmhm-1……h1h0]hm=Pm0;hm-1=Pm-10……h1=P10;h0=P0Ir0;根本监督关系为：[h][Ci]T=[0][h]矩阵为n0-k0=r0行，(m+1)×n0列矩阵；Ir0矩阵为(n0-k0)×(n0-k0)单位阵；0矩阵为(n0-k0)×(n0-k0)零矩阵；Pm矩阵为(n0-k0)×k0阶矩阵；例如上面介绍的(3,2,2)系统卷积码的根本监督矩阵为：[h]=[100010111]r0=3-2=1行;(m+1)×n0=3×3=9列矩阵；P2=[10];P1=[01];P0=[11]。h2=100;h1=010;h0=111;[初始截短卷积码的监督矩阵]：初始截短卷积码定义为：在编码器初始状态为零时，初始输入m+1个信息码字编码器输出的卷积码。即：[C]初=[c0c1…cm]，根据根本监督矩阵的定义，可以很方便地得到初始截短卷积码的监督关系为：[H]初[C]初=[0]，而监督矩阵为：[H]初=P0Ir0=h0P10P0Ir0h1h0……Pm0Pm-10……P10P0Ir0hmhm-1……h1h0[H]初矩阵为(m+1)×r0行；(m+1)×n0列；(3,1,2)卷积码的[H]初为：[H]初=h0=110101h1h0100110000101h2h1h0000100110100000101(3,2,2)卷积码的[H]初为：[H]初=h0=111h1h0010111h2h1h0100010111[卷积码的监督矩阵]；上面介绍的是初始截短卷积码的监督矩阵，实际上卷积码的监督矩阵应当是一个有头无尾的矩阵，它对应的根本监督关系为：[H][C]T=[0]其中：[C]=[C0,C1,C2,……Cm,Cm+1,……][H]=P0Ir0=h0P10P0Ir0h1h0…………Pm0Pm-10……P10P0Ir0hmhm-1……h1h0Pm0Pm-10……P10P0Ir0hmhm-1……h1h0Pm0Pm-10……P10P0Ir0hmhm-1……h1h0….….……例如(3,2,2)卷积码的监督矩阵为：[H]=h0=111h1h0010111h2h1h0100010111…h2h1h0100010111…h2h1h01000101117.1.3卷积码的生成矩阵描述卷积码同样也可以用生成矩阵来描述，[卷积码的生成矩阵]：同分组码一样，卷积码的生成矩阵与监督矩阵同样也有相互正交的关系：因此，可以很方便的得到：截短卷积码的根本生成矩阵的一般形式为：[g]=[g0g1……gm]=[Ik0P0T0P1T……0PmT]初始截短卷积码的生成矩阵的一般形式为：[G]初=g0g1……gm=Ik0P0T0P1T……0PmTg0……gm-1Ik0P0T……0Pm-1T…………g0Ik0P0T卷积码的无穷生成矩阵的一般形式为：[G]=g0g1……gm=Ik0P0T0P1T……0PmTg0g1……gmIk0P0T0P1T……0PmT…………g0g1……gmIk0P0T0P1T……0PmTg0g1……gmIk0P0T0P1T……0PmT…………例如：(3,1,2)卷积码的这几种矩阵分别为：[h]=000100110=[P20P10P0I2]=[h2h1h0]100000101[g]=[111010001]=[I1P0T0P1T0P2T][G]初=g0g1g2=I1P0T0P1T0P2T=111010001g0g1Ik0P0T0P1T000111010g0Ik0P0T000000111[G]=g0g1g2=111010001g0g1g2111010001…………g0g1g2111010001g0g1g2111010001…………[卷积码生成矩阵的多项式描述]：通过前面的(3,1,2)系统卷积码的例子的编码电路可以看出：编码器的三个输出支路可以由三个生成多项式来确定。g(1)(x)=1g(2)(x)=1+xg(3)(x)=1+x2一个(n0,k0,m)卷积码的支路生成多项式的一般形式为：g(1)(x)=g0(1)+g1(1)x+…+gm(1)xmg(2)(x)=g0(2)+g1(2)x+…+gm(2)xm……g(n0)(x)=g0(n0)+g1(n0)x+…+gm(n0)xm如果用向量表示支路的生成多项式为：g(i)=[g0(i)g1(i)g2(i)……gm(i)]这时，卷积码的根本生成矩阵为：[g]=[g0g1……gm]=[g0(1)g0(2)…g0(n0)g1(1)g1(2)…g1(n0)……gm(1)gm(2)…gm(n0)]g0=[g0(1)g0(2)…g0(n0)]g1=[g1(1)g1(2)…g1(n0)]……gm=[gm(1)gm(2)…gm(n0)]由这个根本生成矩阵可以得到卷积码的生成矩阵和初始截短卷积码的生成矩阵等。例如：(3,1,2)系统卷积码的生成矩阵为：g(1)=[g0(1)g1(1)g2(1)]=[100]g(2)=[g0(2)g1(2)g2(2)]=[110]g(3)=[g0(3)g1(3)g2(3)]=[101]g0=[111]g1=[010]g2=[001][G]=111010001111010001……111010001111010001……[非系统卷积码的描述]：利用这种生成多项式表示的生成矩阵特别适合描述非系统卷积码。例如，前面介绍的(2,1,2)非系统卷积码的支路生成多项式为：g(1)(x)=1+x+x2g(2)(x)=1+x2g(1)=[g0(1)g1(1)g2(1)]=[111]g(2)=[g0(2)g1(2)g2(2)]=[101]其根本生成矩阵为：[g]=[111011]生成矩阵为：[G]=111011111011……111011111011……非系统卷积码的监督矩阵从电路图中很难得到，较好的方法是先得到生成矩阵，然后再由生成矩阵求监督矩阵，〔作练习〕。7.1.4卷积码的编码举例看以下(2,1,3)非系统卷积码的例子：图7-6(2,1,3)非系统卷积码编码器原理图其两个支路的生成多项式分别为：g(1)(x)=1+x2+x3g(2)(x)=1+x+x2+x3g(1)=[g0(1)g1(1)g2(1)g3(1)]=[1011]g(2)=[g0(2)g1(2)g2(2)g3(2)]=[1111]当输入的码字序列为[m]=[10111]时，求输出的卷积码？[生成矩阵方法]：由生成多项式可以得到其生成矩阵为：g0=[g0(1)g0(2)]=[11];g1=[g1(1)g1(2)]=[01];g2=[g2(1)g2(2)]=[11];g3=[g3(1)g3(2)]=[11];[G]=g0g1g2g3=11011111g0g1g2g311011111g0g1g2g311011111g0g1g2g311011111g0g1g2g311011111由[C]=[m][G]=[10111][G]=[1101000101010011]在计算矩阵乘法时，实际上假设信息序列的后续为零状态〔三个0〕即认为：[m]=[10111000]。[时域卷积方法]：利用时域卷积的方法可以分别得到编码器两个支路的输出序列，然后将两个支路的序列交织后可以得到编码器的输出序列。[C(1)]=[m]*[g(1)]=[10111]*[1011]=[10000001][C(2)]=[m]*[g(2)]=[10111]*[1111]=[11011101]注：时域卷积方法：(反转-交错-乘积和)101110001011100010111000101110001101110111011101100(1+1)0(1+1)1011100010111000101110001011100011011101110111010001即：[10111]*[1011]=[10000001]101110001011100010111000101110001111111111111111110(1+1)1(1+1+1)1011100010111000101110001011100011111111111111111101即：[10111]*[1011]=[11011101]由此可以得到输出序列为：[C]=[C0,C1,C2,C3,C4…]=[C0(1)C0(2),C1(1)C1(2),C2(1)C2(2),C3(1)C3(2),C4(1)C4(2),…]=[1101000101010011][多项式计算方法]：对于线性系统来说，时域上的卷积可以用域上多项式的乘法运算来代替。对于(2,1,3)非系统卷积码：g(1)(x)=1+x2+x3g(2)(x)=1+x+x2+x3当输入序列为[m]=[10111]时，m(x)=1+x2+x3+x4C(1)(x)=m(x)g(1)(x)=(1+x2+x3+x4)(1+x2+x3)=1+x7C(2)(x)=m(x)g(2)(x)=(1+x2+x3+x4)(1+x+x2+x3)=1+x+x3+x4+x5+x7将两个支路的序列交织合成为一个输出序列为：C(x)=C(1)(x2)+xC(2)(x2)=1+x14+x(1+x2+x6+x8+x10+x14)=1+x+x3+x7+x9+x11+x14+x15对应序列为：[C]=[1101000101010011]如果对于一个一般的(n0,k0,m)卷积码编码器，其支路生成多项式为：g(1)(x)=g0(1)+g1(1)x+…+gm(1)xmg(2)(x)=g0(2)+g1(2)x+…+gm(2)xm……g(n0)(x)=g0(n0)+g1(n0)x+…+gm(n0)xm支路输出序列为：C(1)(x)=m(x)g(1)(x)C(2)(x)=m(x)g(2)(x)……C(n0)(x)=m(x)g(n0)(x)合路输出序列为：C(x)=C(1)(xn0)+xC(2)(xn0)+x2C(3)(xn0)+……+xn0-1C(n0)(xn0)另外还有一种利用多项式计算输出序列的方法：首先得到一个复合生成多项式，g(x)=g(1)(x2)+xg(2)(x2)=(1+x4+x6)+x(1+x2+x4+x6)=1+x+x3+x4+x5+x6+x7C(x)=m(x2)g(x)=(1+x4+x6+x8)(1+x+x3+x4+x5+x6+x7)=1+x+x3+x7+x9+x11+x14+x15如果对于一个一般的(n0,1,m)卷积码编码器，其复合生成多项式为：g(x)=g(1)(xn0)+xg(2)(xn0)+x2g(3)(xn0)+……+xn0-1g(n0)(xn0)下面给出几种典型的卷积码的编码电路和生成多项式，通过练习掌握计算：根本生成矩阵，初始截短码生成矩阵，复合生成多项式，及各种方法计算输出序列等。7.2卷积码的维特比译码7.2.1卷积码的状态图描述卷积码的编码器是一个时序网络，其工作过程可以用一个状态图来描述。编码器的状态由它的移位存放器的内容确定。例如(2,1,3)非系统卷积码，有k0个信息位，m位移位存放器，共有2m=23=8个不同状态。其状态可以表示为：Si=[D2,D1,D0]，分别为：S0=[000]，S1=[001]，S2=[010]，……S7=[111]。根据(2,1,3)卷积码的生成多项式或生成矩阵，可以确定它的唯一的状态图为：图7-7(2,1,3)非系统卷积码状态图其中状态转移线上的数字表示，某一时刻编码器输入某一信息位后，编码器输出的码元序列。例如：1/10表示编码器输入为1时，输出为10。如果，编码器输入为m=[10111]，那么输出为[C]=[1101000101010011]，与上一节中例子相同。M序列后面补三个0，这时编码器状态变化路经为：S0—S1—S2—S5—S3—S7—S6—S4—S0。例如：(3,1,2)非系统卷积码。三个支路的生成多项式分别为：g(1)(x)=1+xg(2)(x)=1+x2g(3)(x)=1+x+x2电路原理图为：图7-8(3,1,2)非系统卷积码编码器原理图其编码器的状态为Si=[D1,D0]其状态图如下：当输入为m=[11101]时，输出为：[C]=[111，010，001，110，100，101，011]状态变化路径为：S0—S1—S3—S3—S2—S1—S2—S0。图7-9(3,1,2)非系统卷积码状态图7.2.2卷积码的格子图〔篱笆图〕卷积码的格子图是将编码器的状态图按时间展开形式。(3,1,2)非系统卷积码的格子图例子如下，只画出信息序列长度L=5。图7-10(3,1,2)非系统卷积码格子图说明：对于L=5的格子图，图中含有L+m+1级。格子0到格子L+m，本例中L=5,m=2,L+m=7，为0-7级。除了初始状态后面m=2个状态假设为0状态输入外，格子图的中间状态均为两个输入分支和两个输出分支。对于每个状态的输出分支，上分支表示输入信息位为mi=0，下分支表示输入的信息位为mi=1，每个分支上的n0个序列表示输出码序列。长度为L+m的2L个码字，每个码字都对应于格子图上的唯一一条路径。7.2.3译码量度假设：长度为L的信息码序列m=[m0,m1,m2,m3,m4]=[m0,m1,……mL-1]；编成长度为N=n0(L+m)的卷积码，C=[C0,C1,C2,……CL-1]；其中Ci=[ci0,ci1,…cino-1]；接收码字序列为C’=[C’0,C’1,C’2,……C’L+m-1]；或者将发送码字和接收码字写成：C=[c0,c1,c2,……cN-1]；如果m=2；L=5；n0=3；那么N=3〔5+2〕=21；C’=[c’0,c’1,c’2,……c’N-1]；译码的过程就是根据接收码字C’来产生发送码字C的估计值C’’。维特比译码实际上是一种最大似然译码。最大似然译码就是根据似然函数为最大的一种估计准那么。似然函数表示为：根据：；可得根据最大似然准那么的分析，当信源状态的先验概率相等时，它是一种最小错误译码概率准那么。其中的p(ci’/ci)就是信道转移概率。可以看出，这个对数似然函数是一个与卷积码格子图上的路径有关的度量。在维特比译码算法中定义它为译码路径量度。记为：其中：分别称为路径量度、分支量度和比特量度。定义：一条译码路径的前j个分支的局部路径量度为：在卷积码的维特比译码过程中，就是根据接收到的码字序列C’，在格子图上找到具有最大量度的路径，实际上就是找到最大似然路径。对于信道转移概率p<0.5的BSC信道，可以证明似然函数有：其中：d(C’,C)为C’与C之间的汉明距离，由于对于所有的C’，，并且为常数。因此，只要d(C’,C)最小，就可以使似然函数最大。因此，维特比算法对于BSC信道来说，就可以使用汉明距离作为译码量度，即选择最小汉明距离的路径作为幸存路径。(Suiviver)7.2.4维特比算法由初始状态经过m个时间单位〔定时〕，从时间j=m开始，计算进入每一个状态的每一条路径的局部路径量度。对于每一个状态，比拟进入它的各条路径的局部量度，其中量度最大〔汉明距离最小〕的路径及其量度被保存下来，这个路径称为进入这个状态的幸存路径。进入下一个单位时间j+1，计算进入某一个状态的分支量度，并与前一个时间的有关幸存路径的量度相加。比拟此时的局部量度，选出最大者，作为进入此状态的幸存路径，存储其路径和量度，删除其它路径和量度。如果一个状态的两个路径量度相等，可以都保存〔也可以删除一个〕。如果j<L+m，那么重复〔2〕步，否那么就停止计算。对于(n0,k0,m)卷积码，如果发送的码字为L个，即Ln0个码元，那么译码算法到L+m个时间单位后，应当进入到一个全零状态，这时只有一个幸存路径。这时译码算法结束。[译码举例]：(3,1,2)非系统卷积码的维特比译码。假设：发送码字为：C=[111，010，110，011，111，101，011]接收码字为：C’=[110，110，110，111，010，101，101]有7个码元错误。维特比算法：第一步：计算j=m=2级分支以前的各个状态的各路径的量度。利用接收码字序列与格子图上的序列进行比拟。S0=(4);S1=(3);S2=(3);S3=(2)括号里面的数字就是进入该状态的汉明距离。第二步：计算从j=2到j=3的局部路径，与原路径量度相加，并删除一个汉明距离较大的路径。如下表：S0S1=(5)S0-S0=(6)×汉明距离大，删除S0=(6)S2-S0=(5)√汉明距离小，保存S1S3=(4)S0-S1=(5)×汉明距离大，删除S2=(5)S2-S1=(4)√汉明距离小，保存S2S1=(4)S1-S2=(5)×汉明距离大，删除S0=(5)S3-S2=(2)√汉明距离小，保存S3S3=(5)S1-S3=(4)√汉明距离小，保存S2=(2)S3-S3=(5)×汉明距离大，删除第三步：计算从j=3到j=4的局部路径，与原路径量度相加，并删除一个路径。S0S1=(5)S0-S0=(8)×汉明距离大，删除S0=(8)S2-S0=(3)√汉明距离小，保存S1S3=(6)S0-S1=(5)×汉明距离大，删除S2=(5)S2-S1=(4)√汉明距离小，保存S2S1=(4)S1-S2=(5)√汉明距离相等，保存S0=(3)S3-S2=(5)√汉明距离相等，保存S3S3=(6)S1-S3=(6)√汉明距离相等，保存S2=(5)S3-S3=(6)√汉明距离相等，保存第四步：计算从j=4到j=5的局部路径，与原路径量度相加，并删除一个路径。S0S1=(5)S0-S0=(4)√汉明距离小，保存S0=(4)S2-S0=(6)×汉明距离大，删除S1S3=(4)S0-S1=(5)√汉明距离小，保存S2=(7)S2-S1=(7)×汉明距离大，删除S2S1=(7)S1-S2=(7)√汉明距离相等，保存S0=(6)S3-S2=(7)√汉明距离相等，保存S3S3=(8)S1-S3=(4)√汉明距离相等，保存S2=(7)S3-S3=(8)×汉明距离大，删除第五步：计算从j=5到j=6的局部路径，与原路径量度相加，并删除一个路径。S0-S0=(6)√汉明距离小，保存S2-S0=(9)×汉明距离大，删除S1-S2=(5)√汉明距离小，保存S3-S2=(6)×汉明距离大，删除第六步：计算从j=6到j=7的局部路径，与原路径量度相加，并删除一个路径。S0-S0=(8)×汉明距离大，删除S2-S0=(7)√汉明距离小，保存最后得到的译码路径为S0—S1—S3—S2—S0—S1—S2—S0。相应的译码序列为：C=[111，010，110，011，111，101，011]可见这种译码算法具有很强的纠错能力。如下图。图7-11卷积码的维特比译码举例第八章信息率失真理论限失真信源编码前面我们介绍了无失真信源编码和有噪声信道编码的问题。概括地讲，无论是有噪声信道还是无噪声信道，只要传信率小于信道容量，总能找到一种编码方法，使误码率任意小，同时使传信率任意接近信道容量。另外，在实际系统中，人们一般并不要求完全无失真地恢复消息，而是允许一定的失真或过失。即在一定的保真度条件下的传输信息。例如语音信号为20Hz-8kHz的范围，但其主要能量集中在300Hz-3400Hz范围内。如果是无失真信源编码，描述信源的最少比特数为信源的熵H(S)。那么在限失真条件下，描述信源的最少比特数为多少那？.1失真度与平均失真函数我们看下列图8-1的通信系统模型，由于这里我们只考虑信源编码问题，因此我们将新到编码和译码都看成信道的一局部。同时把这个信道看成没有干扰的无噪声信道。这时接收消息的失真是产生于信源编码，而不是新到干扰。从直观的感觉知道，允许失真越大，传信率就越大，允许失真越小，传信率就越小。另外，我们信源编码产生的失真等价看成由信道干扰造成的，也就是用信道转移概率描述信源编码造成的失真。我们这种信道称为试验信道，如图8-2所示。图8-1通信系统的信道模型图8-2试验信道模型[1]失真度〔失真函数〕定义设离散无记忆信源的状态空间为U={u1,u2,……ur}，概率空间为P(U)={p(u1),p(u2),……p(ur)}。接收的离散随机变量为V={v1,v2,……vs}。对应每一对(u,v)，我们定义一个非负函数；称为编码信源单个符号的失真度。它表示由发送符号到接收符号产生的失真。它的值越小表示失真越小，=0表示无失真。可以用一个矩阵表示每个符号对产生的全部失真。我们称为失真矩阵。例如：二元对称信源，U={0，1}，V={0，1}。用所谓汉明失真定义的失真矩阵为：可以看到：失真矩阵就类似于信道转移概率矩阵。[2]平均失真度由于U和V都是随机变量，因此也是一个随机变量。因此，编码信源的平均失真度为：设离散无记忆信源的状态空间为U={u1,u2,……ur}，概率空间为P(U)={p(u1),p(u2),……p(ur)}。接收的离散随机变量为V={v1,v2,……vs}。那么：平均失真度描述了一个信源和信道的整体失真特性，即一个信源在一个试验信道上传输的失真大小。[3]随机序列〔N维随机向量〕信源的失真度〕如果不是单符号信源，而是N维随机向量信源，；。Ui取值于{u1,u2,……ur}，Vi取值于{v1,v2,……vs}。因此，U共有rN个不同的符号序列，V共有sN个不同的符号序列。这时，单个序列的失真度为：这时的N维序列信源的平均失真度为：也可以写成：根据这个结果可以看出，信源平均失真度〔单个信源符号的平均失真度〕为：如果N维向量的多符号信源为离散无记忆信源，信道为离散无记忆信道，那么N维序列信源的平均失真度为：而信源的平均失真度为：如果信源为离散平稳无记忆N维信源，在无记忆信到上，那么：即N维序列的平均失真度等于单个符号平均失真度的N倍。当信源固定，单个符号失真度固定，选择不同的试验信道，相当于不同的编码方法，得到不同的平均失真度。但凡满足失真度准那么的这些信道称为D失真允许试验信道。所有D失真允许试验信道组成一个集合，用符号BD表示，即:.2信息率失真函数对于给定的信源，又确定了失真函数后，我们总是希望在满足失真的情况下，使传信率尽量小。这一点与信道容量的问题相反。实际上就是满足平均失真度条件下求平均交互信息量I(U,V)的最小值。设BD是所有满足保真度条件的试验信道的集合，因而可以在这个集合中找到一个信道，使量I(U,V)取最小值。平均交互信息量I(U,V)是信道转移概率的下凸函数，所以这个最小值是存在的。由此定义信源的率失真函数为：其单位为比特/信源符号。对于N维随机向量信源，信源的率失真函数定义为在保真度条件下，平均交互信息量的最小值，即它是在所有满足失真度的N维试验信道集合中，找到一个信道使平均交互信息量取最小值。对于离散无记忆平稳信源，可以证明应当说明：在讨论信源率失真函数时引入的信道转移概率并没有实际信道的意义。只是为了求交互信息量的最小值而引入的、假想的试验信道。实际上它只是反映了不同的信源编码方法。也就是说找到一种编码方法使平均交互信息量到达最小值。8.1.3率失真函数与信道容量的对偶性从信道容量和信源率失真函数的定义我们可以看到：信道容量和率失真函数存在着对偶关系。信道容量是在信道一定的条件下，选择试验信源的先验概率，使平均交互信息量到达最大值。信道容量反映信道的传信能力，信道容量与信源无关，不同的信道就有不同的信道容量。解决的是信道编码问题。信源率失真函数R(D)是在信源和失真度一定的条件下，选择试验信道的转移概率〔实际上选择信源编码方法〕，使平均交互信息量到达最小值，R(D)是接收机在满足一定失真条件下，恢复信源状态所需要的最小平均信息量。率失真函数R(D)反映信源的可压缩能力，率失真函数R(D)与信道无关，不同的信源就有不同的率失真函数。解决的是信源编码问题。信道容量与率失真函数的对应关系可以由下表表示。信息传输理论率失真理论信道固定信源固定试验信源可变试验信道可变平均误码概率为参量平均失真度为参量信道容量率失真函数信道编码定理信源编码定理.4最小失真度和最大失真度率失真函数R(D)是允许失真D的函数。下面给出R(D)的性质。[1]最小平均失真度根据平均失真度的定义：它是一个非负实函数的数学期望，因此它也是一个非负实函数，所以它的下限一定为零，所以允许失真度D的下限的也一定是零，这就是不允许任何失真的情况。对于给定的信源[U,P(U)]，及给定的失真矩阵D，信源的最小平均失真度定义为：由上式可知，如果选择适当的试验信道〔即信道转移概率〕，使对于每一个ui，其求和为最小，那么总和就是最小。当固定一个ui值，对于不同的vj，其不同〔即在失真矩阵中D第i行的元素不同〕，其中必然有一个最小值，也可能有多个相同的最小值。我们可以选择这样的试验信道，它满足：(i=1,2,……n)那么可以使信源的最小平均失真度为：因此，允许失真度是否能到达零，取决于失真矩阵中每行元素中是否至少有一个零元素。如果至少有一个零元素，那么可以使。当时，表示信源不允许有任何失真。在这里讨论的问题，如果要求信源无失真的传输，就相当于信息传输率〔熵速率〕就等于信源的熵，〔相当于无噪声信道〕相当于这个等式的条件是失真矩阵的每一行至少有一个零，而每一列最多有一个零元素。否那么：它表示这时的信源符号集中有些符号可以压缩，而不带来失真。[例题]：对于一个信源U=(0,1)，信宿V={0,1,2}，失真矩阵〔失真度〕为：这时的最小失真度为：即满足最小允许失真度的信道是一个无噪声试验信道，信道矩阵为：可以看出，如果我们选取允许失真度，那么在信道集合中BD就只有唯一可取的试验信道，实际上是说明信源编码方法只有一种就是一一对应的无失真编码，不允许压缩。根据交互信息量的原理，在这个试验信道中，因此：如果最小允许失真要求不为零，那么信道不要求为无噪声信道，那么说明可能存在压缩编码方法。[2]最大平均失真度平均失真度也存在一个上界，率失真函数R(D)是一定条件下，平均交互信息量I(U,V)的最小值。I(U,V)是非负函数，R(D)也是非负函数，其下限为零。当R(D)为零时对应的平均失真度就是平均失真度的最大值。如下图。图8-3平均失真度的最大值平均失真度的最大值说明允许失真到达最大，已经使交互信息量为0，没有什么实际意义，理论上讲，存在多种试验信道，即多种信源压缩方法，压缩率很大以至于使平均交互信息量为零，即接收的符号已经不包含信源发出的信息量。.5二元对称信源的率失真函数信源的率失真函数的计算和信道容量的计算一样都是复杂的问题，二元对称信源是一种简单情况，通过它的计算可以了解率失真函数的概念。设二元对称信源U={0,1}，概率空间为p(u)={p(0)=ω;p(1)=1-ω}，接收变量V={0,1}。失真度矩阵为：因为最小失真度。计算可知满足这个最小失真度要求的试验信道是一个无噪声信道〔无损信道〕，信道转移矩阵为：根据率失真函数的定义，这时的最大允许失真度为：其中假设。通过计算可知，要到达这个最大允许失真度的试验信道，信道转移概率矩阵为：这个矩阵说明：当信道传送信源符号u=1时，可以正确接收，而当信道传送信源符号u=0时必然出现错误。信源u=0的概率为，所以信道的平均失真度为。在这个试验信道下，可以计算最大失真度条件下的率失真函数为：而在一般情况下，时，平均失真度为：为信道平均错误概率。此时，如果选择一个信道，使，得到平均交互信息量为：根据费诺不等式：当n=2时：所以得：这是平均交互信息量的下限值。根据信息率失真函数的定义，当时，平均交互信息量的下限值就是信息率失真函数的值。如何找到这样的试验信道，使其得到率失真函数的这个结果那？这是比拟麻烦的。对于二元对称信道有一个简单方法，“反向信道〞设计法。在原来的信道模型下假设考虑反向传输问题，如图8-4所示。图8-4二元对称信道的反向信道这主要是一种寻找试验信道的手段，假设一种信道正好以失真度D为转移概率传输。其转移概率矩阵P(U/V)为：根据的条件{p(u),p(u/v)}可以求出p(v)的概率分布。同时考虑：得到：因为，所以。说明这个反向信道是存在的。利用这个所谓的反向信道作为正向的试验信道，其平均失真度为：可以看到这种利用反向信道寻找试验信道的方法是可行的。计算得到：那么在该试验信道上的交互信息量为：这样我们就找到了满足失真度D，同时率失真函数为R(D)的实验信道。如图8-5。图8-5二元对称信道的试验信道图8-6给出了不同情况下的率失真函数的曲线。可以看出：对于一定的平均失真度，信源分布越均匀，信源率失真函数就越大；信源分布越不均匀，率失真函数就越小，说明信源剩余度越大，压缩的可能性就越大。率失真函数和实验信道的求法还有正规的参量计算法和迭代计算法，就象信道容量的计算一样，当然也相对复杂一些，这里介绍的只是对于BSC的一种简单方法。同样还有连续信源的率失真函数的定义和计算方法，这里不在详述。图8-6不同信源分布下的率失真函数.6限失真离散无记忆信源编码定理率失真函数R(D)的物理意义是在一定的允许失真D条件下，每个信源符号可以被压缩的最小信息量值，也就是最低信息传输速率。这里我们给出离散平稳无记忆信源的限失真编码定理，只介绍其物理含义。同样可以推广到连续信源和有记忆信源的情况。[定理]：〔山农第三编码定理〕设R(D)为一个离散平稳无记忆信源的率失真函数，对于任意的以及足够长的码字长度n，总可以找到一种信源编码方法C，使编码后的码字符号的平均失真度为：而码字的个数为：对于二元编码，R(D)单位为比特，那么码字个数为：反之，平均失真度为，且的编码方法是不存在的。[定理的含义]：①定理说明：对于任何的失真度，只要码长足够长，总可以找到一种编码方法C，使编码后每个信源符号〔码元〕的信息速率为：即；同时。②定理说明：在允许失真D的条件下，信源最小的可以到达的信息传输率为R(D)。③限失真信源编码的熵速率就是所谓率失真函数R(D)，在给定的允许失真D条件下，熵速率一般小于信源熵，即。而无失真信源编码定理指出，其极限熵速率等于信源熵，即。④山农第三定理也只是一个存在性定理，即定理没有给出如何寻找最正确的编码方法，使编码后的熵速率到达。在实际应用中该理论存在两类问题：第一是实际信源的R(D)的计算相当复杂，信源的数学描述就很困难；信源的失真度很难明确〔主观和客观评价难以数学描述〕；R(D)的计算太麻烦。第二是即使得到了符合实际的R(D)，还需要找到最正确的实用的信源压缩编码方法；这一点也很困难。例如：目前静止图象压缩标准JPEG；运动图象压缩标准MPEG2、MPEG4；会议电视图象压缩标准H.261、H.263；会议电视语音压缩标准G.711、G.722，G.723等。8.1.7限失真信源编码举例通过一个简单例子说明限失真信源编码的原理。[例题]：设一个二元无记忆信源，U={0,1}；P(U)={1/2,1/2}。该信源的熵为H(U)=1bit。根据山农编码第一定理，对这个信源进行无失真编码，其平均码长等于1，这时熵速率R=H(U)=1。如果进行限失真编码，定义失真函数为汉明失真〔0/1失真〕为：即失真矩阵为：现在设计一种限失真信源压缩编码方法，就是把重复码的反响用。做信源U的三次扩展信源，。这时我们把用表示，把用表示。然后再用0代表；用1代表。这样就使原来的三个二进制信源符号压缩成一个二进制信源符号。因此，这种编码后的信息传输率为：比特/符号在接收端，当收到0和1，就分别译码成和。例如，发送序列、传输序列、接收序列和译码序列表示如下表。发送序列：000101100110011111001…编码序列：000111000111111111000…传输序列：0101110…接收序列：0101110…译码序列：000111000111111111000…可以计算：；；；；这样的简单压缩编码的平均失真度为：其中可以看到，经过这种编码方法压缩后信息率为R’=