Turbo码forstudent.ppt

第9章Turbo码简介,2,Turbo码,Turbo码基础Turbo码编码器并行级联结构反馈系统卷积码交织器Turbo码译码器软输入软输出译码器迭代译码算法,3,9.1Tubor码基础,9.1.1Shannon信道编码定理（第二定理）1948年，美国Bell实验室的C.E.Shannon在贝尔技术杂志上发表了题为通信的数学理论（Amathematicaltheoryofcommunication）的论文。Shannon指出：任何一个通信道都有确定的信道容量C，如果通信系统所要求的传输速率R小于C，则存在一种编码方式，当码长n充分大并应用最大似然译码（MLD）时，信息的错误概率可以达到任意小。这就是著名的Shannon有躁信道编码定理。,4,分析：,实现信道编码定理的条件采用随机编、译码方式编译码长度L，即码长无限译码采用最大似然译码方法长期以来，信道编码的设计一直是沿着后两个方向发展,5,信道编码定理分析(1),采用随机编、译码方式编译码长度L，即码长无限译码采用最大似然译码方法,6,信道编码定理分析(2),采用随机编、译码方式编译码长度L，即码长无限译码采用最大似然译码方法,7,信道编码定理分析(3),采用随机编、译码方式编译码长度L，即码长无限译码采用最大似然译码方法,8,9.1.2纠错编码方法的发展过程分组码：20世纪40年代，R.Hamming提出了第一个差错控制码(7，4)，后来被命名为汉明码；汉明码的效率较低，M.Golay研究了汉明码的缺点，提出了两个以自己名字命名的高性能码：二元Golay码和三元Golay码；Muller于1954年提出了一类新的分组码Reed-Muller码，即RM码。RM码在汉明码和Golay码的基础上进了一大步，在码长和纠错能力方面有更强的适应性；RM码之后，人们提出了循环码的概念；重要的子集是1960年提出的BCH码和RS码。但是直到1967年，Berlekamp给出了一个非常有效的译码算法之后，RS码才得到了广泛的应用。,9,卷积码1955年由Elias等人提出。卷积码的信息块长度和码字长度都比分组码小，相应的译码复杂性也要小一些。卷积码常用算法：Wozencraft和Reiffen在1961年、Fano和Jelinek分别在1963年和1969年提出了改进的序列译码算法；由Messey在1963年提出的门限译码算法，类似于大数逻辑译码算法；由Viterbi在1967年提出的Viterbi算法，是一种最优的译码算法。,10,9.1.3串行级联码编码方案Forney在1966年提出；基本思想：将编制长码的过程分级完成，从而通过用短码级联的方法来提高纠错码的纠错能力；目标：利用两个短码串接构造一个长码；级联码结构：由外编码器和内编码器构成；在级联码中，内编码器可以看成一个噪声滤波器，它不仅可以改变噪声的分布，还可以有效地提高接收信号的信噪比。,11,串行级联码器,连接信息源的叫外编码器；外码是（N,K）分组码；码率为Ro；连接信道的叫内编码器；内码是（n,k）分组码，码率为Ri；两者合起来有：码长Nn、信息位Kk、码率Rc=RiRo,12,9.1.4硬判决和软判决传统的最佳接收机中解调器和译码器是独立的两个部分；解调器首先对调制器输入符号做最佳判决，然后将硬判决的结果送给译码器，译码器再根据输入的信息做最佳判决，纠正解调器可能发生的错误判决，这是硬判决；经过解调器的硬判决，丢失了许多有利于译码的信息。为了提高编码通信系统的性能，人们从信息论的角度，对接收机中解调器与信道译码器的功能划分和接口重新审视，提出软判决的方法。,13,软判决：解调器对输出不进行判决，送到译码器的判决信号:可能的概率值或者未量化的输出，而不是硬判决的值；译码器可以利用这些信息作出综合的判决。采用软判决可以得到2dB左右的附加编码增益；针对解调器的输出是“软判决”输出；而对于内译码器，则是进行“软输入”译码。,14,9.1.5用卷积码做内编码器由于软判决维特比最大似然译码算法适合于约束长度较小的卷积码，因此级联码的内码常用卷积码，外码用分组码，如RS、BCH等。卷积码译码是根据序列的相似性来译码，一旦出错就是一个序列的差错（发生突发错误）。卷积码的本质是纠随机错误而不是突发错误误，适用于高斯白噪声信道。对于衰落信道，最有效且简单的方法：采用交织器。,15,级联码用于突发差错信道交织器与扰码器的区别交织器：数据顺序的随机化扰码器：数据形式（0、1幅度）的随机化,16,由于RS码没有简单的软判决译码算法，所以人们发明了一种卷积码+卷积码的级联方式，并采用软输入、软输出译码算法。这种码被看作是Turbo码的一种，被称为串行级联卷积码（SCCC，SerialConcatenatedConvolutionalcode）。,17,乘积码假设信息比特先经过（n，k）分组编码；先再作一次“行”进“列”出的交织后送入信道；交织器起到了噪声均化的作用，对突发差错的随机化非常有效。如果作进一步的研究，发现“行”进“列”出，交织器将“行”的顺序转化成了“列”的顺序。但是原先“行”的顺序是（n，k）分组码的码字，改成了“列”的顺序之后就不是码字了。改进：将码块的行和列都进行编码。由于行和列都有了冗余度，纠错能力一定能够提高，这样做产生的就是乘积码。,18,乘积码码阵图整个码阵可分割成4块:信息块、行校验块、列校验块、校验之校验块。,19,级联码的迭代译码乘积码可以看成是一个中间插入了行列交织器的级联码，是级联码的子类。当接收出现差错时，行译码和列译码对差错的反应不同。,20,同一行有2个错误,同一列有2个错误,假设：行、列的译码能力都是t=1；对于（a）先列译码、再行译码；对于（b）先行译码，再列译码。,21,既然行、列译码含有不同的信息，能否将列译码信息提供给行呢?图中，列译码器的结果经过去交织还原成行信息送入行译码器作为译码的参考（软信息）。然而，行译码的结果并没有被送到列译码器作为参考。,接收信号,软信息,22,迭代译码：行、列译码器的输出可以反复地被对方使用。迭代译码的软输出译码及其他次最优译码算法的复杂性相对于最大似然译码减小了，但是这是以系统的性能为代价的。,23,迭代译码随着Turbo码的问世，迭代译码的概念引起了人们的重视；计算机仿真表明：通过级联码或乘积码的多个软输出译码器之间的进行迭代，系统的渐进性能可以逼近最大似然译码算法的性能；以前，人们将Shannon定理看作是理论上最高界限，是不能达到的；迭代译码技术的在译码方案中的成功应用，使人们看到了达到Shannon理论极限目标的可能性；同时，Turbo迭代译码思想也已经广泛地用于编码调制、信道均衡和多用户检测等领域。,24,结构简单、性能优越的好码：乘积码；代数几何码；低密度校验码（LDPC，LowDensityParityCode）；分组-卷积级联码方法和序列译码；逐组最佳译码；软判决译码；网格编码调制。,25,9.2Turbo码虽然软判决、级联码和编码调制技术对信道码的设计和发展产生了重大的影响，但是其增益与Shannon理论极限始终都存在2-3个dB的差距。Turbo码很好地运用了Shannon信道编码定理中的随机性编、译码条件；,26,仿真结果表明：采用长度为65536的随机交织器在译码迭代18次的情况下采用BPSK调制信噪比Eb/N00.7dB时，码率为1/2的Turbo码在加性高斯白噪声的信道上误比特率为BER10-5，达到了与Shannon极限仅差0.7dB的优异性能；,27,Turbo码：又称为并行级联卷积码（PCCC，ParallelConcatenatedConvolutionalCode）。它巧妙地将卷积码和随机交织器结合在一起，在实现随机编码思想的同时，通过交织器实现了用短码构造长码的方法，并采用软输出迭代译码来逼近最大似然译码。Turbo码充分利用了Shannon信道编码定理的基本条件。Turbo码被看作是1982年TCM技术问世以来，信道编码理论与技术研究上所取得的最伟大的技术成就，具有里程碑式的意义。,28,在1993年ICC国际会议上，法国高等电信学校Bretagne分校的CloudBerrou等提出了Turbo码的概念，它与香农限只差0.7dB。由于并行级联码的反馈译码机制有点类似涡轮机（turbo）的反馈工作原理，所以将这种编译码结构称为turbocode。,Turbo码的诞生,29,Turbo编码器结构,Turbo码（并行级联卷积码），由两到多个带反馈的系统卷积码RSC级联而成，每个子码编码器的输入由随机交织器分开,30,删余(Puncture),通过删除冗余的校验码来调整码率；Turbo码由于采用两个编码器，产生的冗余比特比一般的情况多一倍；但是又不能排斥两个编码器中的任何一个，于是折衷的办法就是按一定的规律轮流选用两个编码器的校验比特。,31,删余(Puncture)举例,采用码率为1/R的系统卷积码如果不删余，信息位加上两个编码器的各一个校验位，将产生码率为1/3的码流。如果令编码器1的校验流乘以一个删余矩阵P1=10T，编码器2乘以一个删余矩阵P2=01T，就产生了在编码器1、2间轮流取值的效果。发送到信道上的只是1位信息位和1位轮流取值的校验位，使码率调整为1/2。,32,假设两个编码器的生成矩阵分别为G1和G2，交织前、后的信息位分别为m和m。两个编码器的输出矩阵：mG1和mG2分别是1N矢量删余矩阵为N2矩阵P1P2，由0、1组成，分别表示两个编码器的校验位选择情况。,33,递归型系统卷积码（RSC）,Turbo码中级联的两个编码器必须是系统码。Forney已证明：对于经典的前馈型卷积码，在同样约束长度和较大信噪比的情况下，非系统卷积码（NSC，NonSystematicconvolutional）比系统码有更大的自由距离和更低的误比特率BER。因此目前使用的实用的前馈型卷积码都是非系统码。,34,C.Berrou等在1993年提出Turbo码的同时，提出了一类新的递归型系统卷积码（RSC，RecursiveSystematicConvolutional），该码在高码率时比最好的NSC还要好。一些文献已经证明：在删余码形式下，递归型系统卷积码RSC比非递归的NSC具有更好的重量谱分布和更佳的误码率特性，且码率越高、信噪比越低时其优势越明显。实用的RSC可由实用的NSC码转换而得到。,35,NSC到递归型RSC的转化过程,转化方法：将NSC码生成函数矩阵的各项都除以首项而使之归一；其余项为分子，其分母体现了递归。,36,例查表得到(2,1,4)NSC卷积码的生成矩阵是（37，21），试找出相应的RSC码。,将八进制表示的生成函数矩阵表示成二进制系数：生成函数矩阵为,37,为了系统化，可对矩阵实施运算以造就一个单位阵。用G(D)的第一列归一化，有：于是，NSC编码器就成了RSC编码器。,38,NSC码和RSC码各自的电路如下图所示：,mk,mk,NSC,RSC,39,NSC编码电路图RSC编码电路图,D,D,D,D,mk,40,子编码器反馈系统卷积码(RSC),对于子编码器的码率为1/2，约束长度为K，寄存器个数为N=K-1的反馈系统卷积码,41,3GPP中的Turbo编码器结构,Turbo编码器结构,假设输入序列为：U=(10101101)第一个子码的校验序列为v1=(11000111)假设交织后的第二个子码的输入序列为：U=(11011001)第二个子码的校验序列为：v2=(10011011)Turbo码的输出序列为：V=（111，010，100，001，101，110，011，111）,42,Turbo码交织器,在Turbo码中，信息数据经交织处理后再送入第二个子编码器。通常,交织器尺寸n远远大于编码器存储级数N，而且交织向量的元素是随机选择的,43,Turbo内交织器的作用,最主要的功能便是利用随机化的思想将两个相互独立的短码组合而成一个长的随机码，因为长码的性能可以逼近香农极限。其次，交织器可以用来分散突发错误。交织器还可以用来打破低重量的输入序列模式，从而增大输出码字的最小汉明距离或者说减少低重量输出码字的数量。,两个子译码器的输入之间的相关性可以在很大程度上得到削弱。一种基于在两个子译码器之间相互传递“不相关”信息的次优迭代译码算法得以应用.,44,交织器对Turbo码性能的影响,交织器交织尺寸对Turbo码的性能基本上起决定作用当Turbo码采用反馈卷积码作子码时，Turbo码的性能基本上和交织长度成反比交织规则对Turbo码的误差底限起决定作用误差底限误比特率在一定情况下不能随着信噪比的增加而陡峭下降,45,误差底限(ErrorFloor),对于固定交织长度的Turbo码，其误差底限可根据不同的交织规则在10-4到10-9或更低之间变化存在误差底限的主要原因Turbo码的设计并不是绝对的长随机码，对于中等交织长度的情况，交织后的序列与交织前的序列相关性越小则Turbo码越接近随机码，对应的误差底限就越低。子码的次最优译码算法也会引入一定的误差底限。,46,9.3Turbo码译码器,Turbo码的迭代译码方案，与其并行级联编码方案相配合，无论从编码结构还是译码思路上都将Turbo码看作一个整体的长随机码，因此明显提高了译码性能。迭代译码通过将外码译码器的输出信息反馈回内译码器，从而使得两个相互独立的译码器充分利用彼此的信息，也因此才将各个子码连成一个真正意义下的长码。,47,Turbo译码器结构,48,对数似然比（LLR,LogarithmLikelihoodRatio）,Turbo码要求一种软输入、软输出的译码算法。软输出译码器的输出不仅包含硬判决值，而且包括做出这种判断的可信度信息，这样必须先找到一种软输出的表示方法，最常用的就是对数表示法。如果接收码字为r，则定义为：,49,常见的软输入、软输出(SISO)算法,标准MAP算法通过除以先验分布（前次软输出）来消除正反馈的算法。对于约束长度为M+1的卷积码，其运算量：每比特需要62M次乘法和52M次加法。由于乘法的运算量大，限制了译码的规模和速度。对数MAP算法（log-MAP）实际上把标准算法中的似然函数全部用对数似然度来表示。这样，乘法运算变成了加法运算。总运算量162M次加法、52M次求最大运算、52M次查表。,50,最大值(max-log-MAP)算法对上述对数域的运算，将似然值加法表示中的对数分量忽略，使似然加法完全变成求最大值运算。这样可以省去大部分加法运算外，最大的好处是省去了对信噪比的估计，使算法更稳健。软输出维特比译码（SOVA）其运算量为标准的维特比算法的两倍，是最大似然估计。由于它每一步都要删除一些低似然路径，为每一状态只保留一条最优路径，因此无法提供软输出。为了保留可信度，需要在删除低似然路径时作一些修正，以保留必要的信息。,51,几种译码算法的比较,最大值算法比标准算法略差；SOVA的性能损失最大，约为1dB左右。,52,Turbo迭代译码算法,迭代译码算法最大后验概率(MAP)译码Log-MAPMax-Log-MAP软输出维特比(SOVA)译码滑动窗SOVA双向SOVA,53,MAP算法,MAP算法MAP算法首先由Bahl等人提出，它适用于线性分组码和卷积码的译码，通过计算每一信息比特的后验概率的对数似然比来最小化译码的误比特率。,54,MAX-LOG-MAP算法,由于MAP算法的译码复杂度很高，并要求很大的存储空间，所以MAP算法并不适合于实时性要求很高的通信系统。因此，在其基础上作了很大简化的MAX-Log-MAP得到了广泛的应用。基于MAP算法中存在大量的指数和乘法运算的特点，MAX-Log-MAP算法将路径度量的计算放在对数域上进行，从而将大量的乘法运算转化为加法运算，大大降低了运算复杂度,55,LOG-MAP算法,MAX-Log-MAP算法虽然在很大程度上降低了译码时延，但同时也损失了一定的编码增益。在Log-MAP算法中使用Jacobian算法,56,SOVA算法,SOVA维特比算法是1967年由维特比提出的，它是针对可以用栅格图表示的离散时间有限状态马尔可夫过程的一种最大似然译码算法，在过去的几十年中被广泛应用到实际系统的卷积码的译码中。对信源等概的情况，最大后验概率算法等效于最大似然算法。SOVA是VA的改进，输出为对数似然比。,