5.1-信道编码基础

复习•平均功率受限可加高斯信道容量最佳输入分布N(0,S)•平均功率受限可加非高斯信道容量)1log(212σSC+=222222111log()log()log()222SSSCσσσσσσ+++≤≤≤复习•并行可加高斯噪声（AWGN）信道的组合信道的容量∑∑σ=σ=σ+=BnnNnnnnBSC2:212log21)1log(21()2nnSBσ+=−221...NSBNσσ+++=复习•若令，可得，即当带宽不受限制时，传送1bit信息，信噪比最低只需，这就是香农限，这是加性高斯白噪声信道信息传输率的极限值，是一切编码方式所能达到的理论极限。要获得可靠的通信实际值往往都比这个值大好多。•Shannon公式sbitC/1→∞dBeSNR6.1log1−==dB6.1−)1log(0WNSWC+=10Singnalpower10logNoisepowerSNRdb=信道信源信源编码加密信道编码干扰源信宿信源译码解密信道译码加密密钥解密密钥数字通信系统模型单个的字无法检错：扪→？词汇能够检错：我扪的→我扪的词汇能够纠错：我扪的→我们的，我等的，我辈的，我班的，…结论：加入冗余后，根据词汇的概率分布稀疏性可以用来检错和纠错。信道编码信道编码（纠错编码）的任务是将输入的信息数字序列变换成另一个数字序列送入有扰离散信道。人为的按一定规则增加多余度，以便纠正传送过程中可能出现的错误，以尽可能小的错误概率恢复原来的信源序列。0001101110101100100111011111r=1011010010LmU∈uNmX∈xNmY∈yLmU∈uˆ信道编码器模型sτcτscττ每个信息数字持续时间为秒按一定运算规则计算出编码数字，持续时间为秒信道编码基本参数称L为信息数字的编码约束长度，它是纠错码的一个重要参数。编码约束长度编码器通常对数字进行分段，例如分成长为k0的段，称作信息段。在时间段内，编码器计算出n0个编码数字送给信道，称作码段。n0，k0都是编码的重要参数。信息段与码段skτ00001101110101100100111011111编码jm1−jm110111111100101101jm1−jm2−jm⊕⊕1jX2jX11010100实例分组码(5,2)卷积码(2,1,3)信道编码分类，即每时间段编码器接收L个信息数字，并计算出个编码数字（称作一个码字），通常选为整数。这种码称为分组编码。Lk=00nN=csLNττ=/，一般选，其中，m是正整数。在时，每秒输出n0长的码段中各数字的取值不仅与当前输入的k0位信息数字有关，而且与在此之前的m个信息段上的信息数字有关，即总共与个信息数字有关。这样输出的各码段之间不再彼此独立。这种依赖关系要一直递推下去，称这样的编码法为卷积编码。Lk00)1(kmL+=0≠m0)1(kmL+=skτ00001101110101100100111011111编码jm1−jm110111111100101101jm1−jm2−jm⊕⊕1jX2jX11010100实例分组码(5,2)卷积码(2,1,3)它表征了纠错所付出的代价。显然，若给定L或k0，要求纠错能力愈强，所需的多余度愈大，编码速率R也就愈低，即所付出的代价愈大。信息率（编码速率）区别：信源编码的编码速率信源编码后平均描述每个信源符号的信息量。若给定L，编码速率R愈低，即所需编码长度N愈小，相应的系统有效性愈高。NLR=00nkR=或DLNRlog=信道编码分类分组码的编码长为L的二元信息序列的总数个，而长为N的二元数字序列为个。分组编码就是从个长为N的数字序列选出M个，用来代表M个不同的信息序列。任何一种指定方案就给定一种编码方法（编码规则）。LM2=N2分组码的性能指标令是信道输入相应的信道输出。纠错译码器的作用就是根据接收到的y和编码规则，对发送的是M个可能序列中的哪一个做出判决。),,,(21Nyyy=y),,,(21Nmxxx=x设译码器在收到y后将它译为。若，就出现了错误。这种事件出现的概率是误组率。'mx'mm≠epelp其中是第l位出现错误的概率一个码字发生错误意味着N长二元数字序列中至少有一位错，误比特率是译码后码字中发生错误的比特数与总比特数之比∑==NlelbpLp11)|(max)|'(yupympNuN跑遍所有码字=分组码的译码准则译码准则就是猜测规则，即当信道的输出值为y时，将其译为哪个码字m最合理？最大后验概率准则对特定接收序列y，)'(1)'()(yyymmpmmppNNe=−=≠=译码时要求最小)(yep若有一个以上的m，使取同样的最大值时，我们可从其中任选一个，而不会影响平均错误概率)'(ympN最小错误概率译码准则)|(max)'|(uypmypNuN跑遍所有码字=分组码的译码准则最大似然译码准则)()()()(yxyywpmQmpmNN=最大后验概率若所有可能消息序列的先验概率相等，则最大后验概率准则可进一步简化为)|(max)'|(uypmypNuN跑遍所有码字=最大后验概率译码)(ln)(ln)(ln)'(ln'mNmNpmQpmQxyxy+≥+'mm≠∀最大似然译码（当消息先验概率相等时）)(ln)(ln'mNmNppxyxy≥'mm≠∀译码准则的对数形式)()()()(yxyywpmQmpmNN=后验概率【注2】在消息先验等概条件下，它等价于最大后验概率译码，因而也是最佳的。但若消息先验概率不确知时，采用最大似然译码就不一定保证译码错误概率最小。【注1】它并不要求消息的先验概率。【注3】实际系统中，信源发出的序列传送到信道之前都已进行信源编码，经过有效的信源编码，输出码元的概率分布会均匀化，所以信道的输入近似为等概，因此在工程应用中采用最大似然译码尽管不会使错误概率达到最小，但也接近最小。最大似然译码准则例题设有一个离散信道，其转移概率矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=4.03.03.05.03.02.02.03.05.0P并设，，，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的译码错误概率？41)(1=xp41)(2=xp21)(3=xp解(a)最大后验概率译码(最小错误概率准则)由Bayes公式p(x1/y1)=5/13,p(x2/y1)=2/13,p(x3/y1)=6/13.y1→x3.同理,y2→x3,y3→x3。判决空间Y3={y1,y2,y3},Y2=Y1=φ。pe1=pe2=1,pe3=0.pe=1/2⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=4.03.03.05.03.02.02.03.05.0P123111(),(),()442pxpxpx===∑∈=cmYmNemppyxy)(∑==MmemepmQp1)((b)最大似然译码比较p(y1/x1),p(y1/x2),p(y1/x3)大小，y1→x1。p(y2/x1),p(y2/x2),p(y2/x3),y2→x2.y3→x2.pe1=p(y2/x1)+p(y3/x1)=0.5,pe2=p(y1/x2)=0.2,pe3=1pe=p(x1)pe1+p(x2)pe2+p(x3)pe3∑∈=cmYmNemppyxy)(∑==MmemepmQp1)(分组码的译码分组码编码：消息空间UL到输出空间YN的一种映射译码规则可以看成是YN到UL的一种映射，即将空间YN按译码准则划分成不相交的判决空间。MYY,,1最大后验概率译码最大似然译码{})(ln)(ln)(ln)'(ln:''mNmNmpmQpmQYYxyxy++='mm≠∀{})(ln)(ln:''mNmNmppYYxyxy='mm≠∀其中Φ=kiYY∩ik≠∪11+==MiNiYY若接收矢量，就将y判为消息m。若，就将y作为删除或检错处理。mY∈y1+∈MYy令cmY表示mY的补集，当发送消息为m，而接收y落入中就会产生译码错误。因此，给定m时的译码错误概率为∑∈=cmYmNemppyxy)(若消息m的先验概率为Q(m)，则平均译码错误概率为∑==MmemepmQp1)(cmY分组码的译码例题设M=2且两个消息等概，令，。通过转移概率为p1/2的BSC信道传送。(1)若采用完备译码，试根据最大后验概率准则划分译码区间并给出相应的译码错误概率。(2)若可以划分三个区间，试确定译码规则并给出译码错误概率和有错不能判决的概率？)0000(1=x)1111(2=x解BSC最大似然译码等价于最小汉明距离译码Y1={0000,1000,0100,0010,0001,0011,1100,1001}Y2={1111,1110,1101,1011,0111,1010,0101,0110}错误概率pe=pe1=pe2=p4+4p3(1-p)+3p2(1-p)2或者Y3={0011,1100,1001,1010,0101,0110}Y1={0000,1000,0100,0010,0001}Y2={1111,1110,1101,1011,0111}错误概率pe=pe1=pe2=p4+4p3(1-p)有错不能判决pd=q(x1)pd1+q(x2)pd2=6p2(1-p)2∑∈=cmYmNemppyxy)(∑==MmemepmQp1)(作业5.1设有一DMC，其转移概率矩阵如下。若Q(x1)＝l/2，Q(x2)＝Q(x3)＝1/4，试求（1）最佳译码判决时的译码规则以及误码率。（2）最大似然译码判决时的译码规则以及误码率。1/21/31/61/61/21/31/31/61/2⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦本节小结（本节内容见课本139-146页）信道编码基本概念信道编码（分组码）编译码–分组码编码–分组码译码–编码约束长度、信息段与码段、编码速率–分组码、卷积码最小错误概率译码准则最大后验概率译码准则最大似然译码准则