信道编码理论

信道编码理论第1页，课件共52页，创作于2023年2月卷积码的Trellis图表示右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为:2第2页，课件共52页，创作于2023年2月卷积码的Trellis图表示s0s1s2s3s0s1s2s3状态图Trellis图3第3页，课件共52页，创作于2023年2月Viterbi译码若编码信息序列为1011100，则编码过程即为在Trellis图上寻找一条路径。4第4页，课件共52页，创作于2023年2月Viterbi译码译码过程即为在Trellis图上寻找一条路径，该路径对应的编码序列与接收序列之间有最大概率度量：5第5页，课件共52页，创作于2023年2月Viterbi译码从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）；在任一时刻t，对每一个状态只记录到达路径中度量最小的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）；在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到|S|×2k条路径；对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径；直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果。6第6页，课件共52页，创作于2023年2月Viterbi译码在BSC和BIQO-DMC上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量。距离度量更新公式：Theorem：在Viterbi译码算法中，留选路径是有最大似然函数的路径。7第7页，课件共52页，创作于2023年2月Viterbi译码第1个时刻接收子码10汉明距离d11第2个时刻接收子码10汉明距离dExample:M=(1011100)，初始状态为全0的编码器输出序列为C=(11,10,00,01,10,01,11),通过有噪信道后，接收序列为R=(10,10,00,01,11,01,11)118第8页，课件共52页，创作于2023年2月Viterbi译码第3个时刻接收子码00汉明距离d21329第9页，课件共52页，创作于2023年2月Viterbi译码第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d3331213310第10页，课件共52页，创作于2023年2月Viterbi译码第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d3322331311第11页，课件共52页，创作于2023年2月Viterbi译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d3233223,43,43312第12页，课件共52页，创作于2023年2月Viterbi译码第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,413第13页，课件共52页，创作于2023年2月Viterbi译码保存的幸存路径为：译码结果为：101110014第14页，课件共52页，创作于2023年2月Viterbi译码——收尾最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。收尾的原则在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。非递归卷积码约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。递归卷积码可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。15第15页，课件共52页，创作于2023年2月Viterbi译码——收尾非系统非递归码递归系统码16第16页，课件共52页，创作于2023年2月Viterbi译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example(cont.):M=(10111);M’=(1011100)17第17页，课件共52页，创作于2023年2月Viterbi译码第7个时刻接收子码11汉明距离d2,518第18页，课件共52页，创作于2023年2月Viterbi译码保存的幸存路径为：译码结果为：101110019第19页，课件共52页，创作于2023年2月软判决Viterbi译码基本思想：为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行Q电平量化，然后在输入Viterbi译码器。能适应这种Q进制输入的Viterbi译码器称为软判决Viterbi译码器。例子：Q=4电平量化的信道比特度量：001021121120第20页，课件共52页，创作于2023年2月Viterbi译码的复杂度对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径；每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选；同时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。21第21页，课件共52页，创作于2023年2月Viterbi译码的特点维特比算法是最大似然的序列译码算法；译码复杂度与信道质量无关；运算量与码长呈线性关系；存贮量与码长呈线性关系；运算量和存贮量都与状态数呈线性关系；状态数随分组大小k及编码存贮m呈指数关系。22第22页，课件共52页，创作于2023年2月滑窗Viterbi译码算法基本思想：当状态数有限时，给定时刻的各状态残留路径在一定时间（L）之前来自于同一状态的可能性随L的增加而迅速趋近于1。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。23第23页，课件共52页，创作于2023年2月滑窗Viterbi算法实现在第t时刻，可以将t-L时刻前的路径结果直接输出，而在存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在Lpkm。这里的L就被称做译码深度，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至不需要对流分段加尾比特。显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的5到10倍，其性能损失就可以忽略不计了。24第24页，课件共52页，创作于2023年2月缩减状态的Viterbi译码由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m<10。对状态数很大的卷积码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。25第25页，课件共52页，创作于2023年2月第十二章卷积码的概率译码（II）序列译码Fano译码算法ST译码算法调制与编码的结合(TCM技术)26第26页，课件共52页，创作于2023年2月序列译码Viterbi译码算法存在的问题:对m值很大的情况不适用——误码率很难做的很低;译每一个分支的计算量不变;Viterbi译码中路径度量计算方法不适用于比较不同长度的路径，如:R=(10,10,00,01,11,01,00)

C5=(11,10,00,01,10,01)

C0=(11)d(R0…R5,C5)=2d(R0,C0)=1要求误码率很低，且译码器计算量可随信道情况变化时，需采用序列译码:一个简单的译码算法：逐分支译码。27第27页，课件共52页，创作于2023年2月逐分支译码举例编码符号为1时发+1，编码符号为0时发-1。当接收符号为：0.8,0.7,-0.2,-0.3,0.5,-0.3时，尽管第二次分支为两个负数，但更象分支“1”，因此判信息序列为110。第二次分支：110:d=|1-(-0.2)|+|-1-(-0.3)|=1.9001:d=|-1-(-0.2)|+|1-(-0.3)|=2.128第28页，课件共52页，创作于2023年2月逐分支译码的局限没有利用卷积码的记忆性；例：当接收符号为：0.8,0.7,-0.2,0.1,0.5,-0.3时，判信息序列为101。但从整体序列来看，更像110101110100:d=0.2+0.3+0.8+0.9+1.5+0.7=4.4110111010:d=0.2+0.3+1.2+1.1+0.5+0.7=4.0因此不是最大似然序列译码。29第29页，课件共52页，创作于2023年2月译码特性一个好的译码算法，必须满足以下几点：能以很大概率发现当前走在错误路径上；能以很大概率回到正确路径；运算量和存贮量要适中。当在码树中沿正确路径行进时，R与C的l段长码序列之间总的Hamming距离的趋势与l呈线性变化。大数定律,pe为BSC的转移概率。当在码树中沿完全错误（随机）路径行进时，Hamming距离的整体趋势也呈线性变化，但斜率要高于正确路径，约为n0/2。R与C完全不相关。30第30页，课件共52页，创作于2023年2月译码特性正确路径、随机路径以及判决准则:31第31页，课件共52页，创作于2023年2月译码特性斜距离:由于信道干扰的原因，错误路径并不总是比正确路径的度量低，但一般情况下沿错误路径走下去总会导致度量的下降。32第32页，课件共52页，创作于2023年2月局部错误不过由于卷积码的记忆有限，可能会出现一条错误路径最终与正确路径会合的情况，这样就会出现一段局部错误。误码两条路径在此有相同状态33第33页，课件共52页，创作于2023年2月错误事件当由于度量的起伏造成将局部错误的路径看成正确路径时，就发生误码。对卷积码来说，一般比较容易出现的错误都是较小的码距，而较小码距的差错图案一般都是集中在一些序列段中，即由一些局部错误组成。序列译码就是要尽早发现这些局部错误，因为过了这些局部错误之后两个序列的内容就相同了，因此后面的斜率也是相同的。局部错误在路径度量变化中的体现应是一段下垂后继续按正确斜率上升。因此要随时调整判断门限。34第34页，课件共52页，创作于2023年2月Fano度量最大似然译码：接收序列：码字序列：ML判决序列：对离散无记忆信道：35第35页，课件共52页，创作于2023年2月Fano度量Bayesian公式：若发送序列先验等概，即另外，则有36第36页，课件共52页，创作于2023年2月Fano度量对数似然值：Fano度量：Fano译码：用Fano度量代替斜距离：37第37页，课件共52页，创作于2023年2月Fano度量例子：R=(10,10,00,01,11,01,00),C5=(11,10,00,01,10,01),C0=(11)，信道转移概率为p=0.1，求和38第38页，课件共52页，创作于2023年2月Fano算法在向前试探时，如果发现度量值大于当前门限，则向前移动到所试探的节点；如果这次试探是第一次，则可将门限作一定的提高；如果不是第一次，说明曾因门限太高而倒退过，因此不提高门限，以便后面的比较。39第39页，课件共52页，创作于2023年2月Fano算法向前试探时，如果发现度量小于当前门限，说明比试探节点还要坏的节点度量更不可能超过门限，因此在此节点上不必再向前试探下去，而应考虑向回作反向试探。如果反向试探结果是也小于门限，说明当前门限太高需要降低门限，再作向前试探；如果反向试探结果大于门限，说明反向试探节点度量>门限>前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。40第40页，课件共52页，创作于2023年2月Fano算法先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。41第41页，课件共52页，创作于2023年2月

Fano算法42第42页，课件共52页，创作于2023年2月堆栈(ST)算法核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始；将堆栈第一行中路径向各分支延伸，计算新度量；删去第一行原存贮内容；将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行；若第一行中的路径已达码树终点，则结束，否则回到步骤2。43第43页，课件共52页，创作于2023年2月ST算法的本质存贮一组可能路径；每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径；繁衍出的子路径与其它未繁衍的路径一起排序；堆栈满时最坏路径被丢弃。44第44页，课件共52页，创作于2023年2月序列译码的特点运算量与信道质量有关；需要输入缓冲器，其长度也与信道质量有关，有溢出现象；计算量与约束长度无关。45第45页，课件共52页，创作于2023年2月TCMencoder46第46页，课件共52页，创作于2023年2月TCMForatrelliscodeC(oflengthn),theminimumsquaredEuclideandistancebetweentwodifferentsequencesofsignalpointsisreferredtoasitsfreesquaredEuclideandistance;i.e.,Theasymptoticcodinggain(includingshapinggain)isdefinedtobe

wheredenotetheminimumsquaredEuclideandistancebetweensignalpointsintheuncodedscheme,andEandE(u)denotetheaveragesignalenergiesofthecodedanduncodedschemes,respectively.

dB

47第47页，课件共52页，创作于2023年2月TCMexample

The4-stateTCMencoderfor8-PSK48第48页，课件共52页，创作于2023年2月Setpartitionof8PSK49第49页，课件共52页，创作于2023年2月Trellisdiagram