通信原理电子版讲义--信道编码（8）

1卷积码的译码•卷积码的译码方法主要有两种：代数译码、概率译码•代数译码：根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性。•概率译码：这种译码在计算时要考虑信道的统计特性。典型的算法如：Viterbi译码、序列译码等。20011abcd10接收序列k010011100120130011010101(3)(3)(1)(2)4567890010011010011111(2)(2)(3)(2)(3)(3)(2)(2)(3)(3)(3)(2)(4)(4)(3)(2)(4)(4)(2)(4)(2)(4)(5)(5)判决结果1101111003Viterbi算法的一些说明•未特殊说明，均假设从全0状态开始译码（即缺省假设编码的初始状态为全0）•卷积码的判决可以在译码10~20N之后，（译码时延）•由于每时刻每状态只保留一条“幸存”路径，判决时只要比较各状态的“幸存”路径度量值，即可确定最小路径。4尾比特•当输入信息是分组时，如的语音帧，则存在如下的问题：–设编码器初态为0，第一帧编完后状态不一定为0，如果未加处理继续编第二帧，则初态不一定是全0状态…–译码时，设初态为0，开始译第一帧，如果第一帧译码正确，则可以知道正确的第二帧初态，否则差错就传播给第二帧…•为了避免上述情况，则在每帧后添加若干尾比特使编码器编码后状态回0•加入尾比特后，译码到最后时刻时可以不需要比较各状态的路径度量，而只需要输出全0状态所保存的路径即可。5Viterbi译码算法的具体步骤•对于(n,1,m)卷积码，格图上有2m个不同的状态。对应每个状态，译码器设置了个路径度量存储器M(1)、M(2)、M(3)、……和路径存储器P(1)、P(2)、P(3)、……。P(i)记录到达状态i的幸存路径（用输入信息表示），M(i)记录到达状态i的幸存路径的累积度量。6Sl-1aABbcSl第l－1步第l步CDaMCl1aMAl1aclBMbclBMbMBl1bMDl1………………Sl-27•在第0步，进行初始化•M的初始化方式表示路径从全0状态开始。f代表空集。•在第l步（l0），度量新存储做完第L＋M步后，即为译码结果。0始0终的卷积码截短码的概念miiiM23,210fiPijlijlBMjMBMjMiM,2,121,miniMiMijdjPiP,0P8硬判决与软判决•译码器的输入是信道输出的硬判决结果叫硬判决译码。•如果用判决前的r来译码就是软译码。•上述例为硬判决的例子（计算距离时用汉明距）•软判决时，计算距离时使用欧式距离•通常采用软判决比硬判决性能好1～2dB92PSK下的信道模型编码器±1硬译码ucsE软译码Qyruˆuˆ1,01,01sE1,01,01,02,00NN噪声～xx10软判决时，计算距离时使用欧式距离其中：xk=Es或－Es(最佳接收），nk是均值为0，方差为N0/2的高斯随机变量kkkrxn•最大似然译码–设采用BPSK调制方式，则接收端接收到信号为•译码时假设码字同步（即接收端已知码字的起始），则接收端以120(...)nnrrr作为判决120(...)nnxxx的依据。11最大似然译码•最大似然译码的结果为120120120120120120...120120...21...000...0argmax(...)|...argmax...|...1argmaxexp1argmaxexpkknnnnnnnnkkIIIInnnnXxxxniiXxxxinXxxxfrrrIIIfrrrxxxrxNNN12001niiirxN12最大似然译码•软判决1220niiidrx欧式距离最小的码字X对应的信息码字作为判决结果。•硬判决（如BSC信道时）•此时rk被判决成＋Es或－Es，因此1222204niisidrxErx与不相同的位置欧式距离的平方退化成两个码字间的码距d(r,X)即可判决13最大似然译码示例•若(4,2)码的许用码字为{(0000)(0101)(1010)(1111)}，•经过信道传输，接收到信号r=(-0.3,-0.7,1.5,0.4),•则接收点与各许用码字间的欧式距离为：–d(r,0)=(-0.3+1)2+(-0.7+1)2+(1.5+1)2+(0.4+1)2=8.79–d(r,1)=(-0.3+1)2+(-0.7-1)2+(1.5+1)2+(0.4-1)2=9.99–d(r,2)=(-0.3-1)2+(-0.7+1)2+(1.5-1)2+(0.4+1)2=3.99–d(r,3)=(-0.3-1)2+(-0.7-1)2+(1.5-1)2+(0.4-1)2=5.19–最大似然判决结果为1010对应的信息码字2•上例，如接收到的信号经过硬判决得到(-1,-1,1,1)，•则：–d(r,0)=2d(r,1)=2,d(r,2)=2,d(r,3)=2–判决结果可以是四个码字中的任意一个。14译码原理----维特比译码（续）例111223213322332322233300100111基于硬判决的Viterbi译码Trellis图15译码原理----维特比译码（例）•Viterbi译码举例–设对于编码前信息比特为(0,0,0,0,0,0)的接收序列为则硬判结果为基于软判决时，采用如下路径度量9.0,2.15.0,2.06.0,5.03.1,5.09.0,1.03.0,1.1~r0,01,10,00,00,11,0~r)1()1(,)0()0(,,),(jpijpipijrxrxxr16译码原理----维特比译码（续）111223213322332322233300100111基于硬判决的Viterbi译码Trellis图17译码原理----维特比译码（续）0.80.201.6-1.83.42.00.8-0.83.85.22.22.64.52.32.11.95.94.34.95.500100111-0.8基于软判决的Viterbi译码Trellis图18译码原理----维特比译码（续）•Viterbi译码的特点–维特比算法是最大似然的序列译码算法–译码复杂度与信道质量无关–运算量和存贮量都与码长呈线性关系–运算量和存贮量都与状态数呈线性关系–状态数随k及m呈指数关系信道编码的任务•检错和纠错•充分利用资源，达到信道容量•长期以来，达到信道容量的作用被忽视了–总体而言，目前的各种单一的构造性很强的编译码方法，其性能都很有限，与信道容量之间的差距是很大的，这也就是为什么信息论提出半个世纪了，但人们关心的容量仍不是信息论意义上的容量。20卷积码的码距特性*•卷积码的流图0011011011010010abcdabcdeIDw2wDwIDwIDIDDw2wD21说明•W的幂次表示编码后码字的码重（1的个数）•D的幂次表示码字的路径段数•I的幂次表示输入的码重22cedbddbccabDXwXwIDXwIDXXwDXwDXXIDXIDXwX22aaeXDDIwDwIDIDwXwIDwIDIDwX...)1()1(1122223523523系统传输函数*532222(,,)/1(1)(1)...eaTwIDXXwIDwIDDwIDD24卷积码的自由距dfree•自由距：任意卷码编码后序列之间的最小码距由传输函数可以得到自由距w的最小幂次即为自由距25卷码的性能界*02()freebwwdEwRPAwQN|||weePEPPPccccccc0e0通过随机编码达到信道容量•从信息论的角度看，不论是什么信道，只要用随机编码，长度足够长，就可以无限逼近信道容量。•而实际的编码长度是很有限的，前面提到的各种编码码都谈不上随机，其码长更不能做得太大，否则根本没法译出来。现有编码的应用•随机编码难以设计和分析•现在能做的，只是将现有的各种编译码方法在实际工程环境中用好。•在工程应用上，或从系统的角度出发，在应用编码时需要考虑许多实际的因素，如效率、性能、延时等等。特别要注意的是要与信道特性相适应。有突发错误的信道•干扰、衰落、均衡等等都会引入突发错。•经过信道编译码后，其译码输出的错误也将呈现突发性，无论是分组码，还是卷积码都是如此。–信道编译码的门限效应现有编码的纠突发错能力•卷积码抗突发错能力很差–卷积码是靠相邻符号间的相关性提供保护的，而此相关性的维系时间一般较短•分组码对突发错和随机错的纠错能力基本相当，但码长较短，稍长一些的突发也无能为力•也有专门针对突发错设计的分组码，但纠随机错的能力相应降低抗突发错的有效手段——交织•交织（interleaving）就是一种将数据序列的顺序进行变换的一种处理方法。又可称为置换（permutation）。•交织器的一般表示方法–交织表：交织器的三个重要参数•交织延迟•交织前相邻的符号在交织后的最小距离称为交织深度•交织后相邻的符号在交织前的最小距离称为交织宽度交织宽度和交织深度对抗突发错编码的影响•交织宽度应不小于编码的约束长度，或相应的参数，否则突发错仍不能彻底打散•交织深度应不小于信道上可能的突发错长度，否则解交织后仍可能存在一定的突发错误块交织（blockinterleaver）•将数据流分成长度为W*L的块，将数据逐行写入一个L行W列的矩阵形缓冲区，写满后再逐列读出。•深度为L，宽度为W，延时为WL。交织和解交织的延时总和为2WL。34信道编码•交织码在CDMA系统中的功能：–重排序，把连续的比特打乱成不连续的比特–交织举例：MRCU原始信息：MOTOROLACELLULAR…OOELTLLAOALRMOTOROLACELLULARMOTOROLACELLULAR空中信息：MRCUOOELTLLAOALR…交织编码交织解码解码信息：MOTOROLACELLULAR…MRCUOOELTLLAOALR级联码•我们也可将编码、信道、译码整体看成一个广义的信道。这个信道也存在错误，因此对它还可作进一步的纠错编译码。•对于有多次编码的系统，对各级编码，看成一个整体编码，就是级联码。•级联码的最初想法是为了进一步降低残余误码率（改善渐近性能），但事实上它同样可以提高较低信噪比下的性能。•这是由较好构造的短码进一步构造性能更好的长码（近随机码）的一种途径。内码、外码和码距•当由两个编码串联起来构成一个级联码时–作为广义信道中的编码称为内码–以广义信道为信道的信道编码称为外码–由于内码译码结果不可避免地会产生突发错误。因此内外码之间一般都要有一层交织器。常见的级联方式•卷积码为内码，RS码为外码。这主要是为了充分利用卷积码可以进行最优的维特比译码，而且可以用软判决译码。而RS码又有较好的纠突发错误能力。•内码和外码均采用卷积码，特别是当内码译码可以输出软信息时，更为有效级联码的问题•性能的代价就是效率•离容量极限还有相当距离•译码算法远未最优：硬判、信息利用不充分译码算法上的潜力•迭代以充分利用信息外码编码内码编码交织器信息数据编码输出编码器内码译码外码译码解交织接收信号译码输出译码器Turbo码41产生背景•交织–块交织：行写入，列读出–卷积交织：LLLLLLLLLLLLLLL0123W-2W-1入出42产生背景（续）•串行级联码•优点：性能较一般短码有很大改善•缺点：编码效率低；当R/C→1时性能迅速恶化外码编码内码编码交织器信息数据编码输出编码器内码译码外码译码解交织接收信号译码输出译码器43产生背景（续）•软输入软输出和迭代译码对数似然比LLR)()()()()()()()()()|()1()1(