纠错码Lecture8-卷积码(III)

Lecture8

卷积码(III)2内容大数逻辑译码Fano译码算法ST译码算法3大数逻辑译码例子：设（2,1,6）系统卷积码，子生成元：

对应校验矩阵为：

4大数逻辑译码设错误图样伴随式为式中5大数逻辑译码由以上7个方程知，在s01，s21，s51和s61四个方程中，除e01外，其他码元位至多出现一次，从而组成4个对e01码元位正交的一致校验和式。所以e01位上的错误完全可以由s01，s21，s51和s61确定，而它们的值由H中的第0、2、5、6行的校验关系决定。定义：任一个（n0，k0，m）系统卷积码，若能由H矩阵中的Ji行直接组成对e01（i=1,2，…k0,若为非系统码i=1,2，…n0

）正交的Ji正交校验和式，则称此码为自正交系统卷积码，若码的最小距离dFD=J+1，则称为完备自正交码。6大数逻辑译码例子：构造（3,1,2）和（3,2,2,）码的子正交系统卷积码大数逻辑译码器。

(3,1,2)码有两个校验元，子生成元式：

(3,1,2)码有两个信息元，子生成元式：

7大数逻辑译码故，对（3,1,2）码对（3,1,2）码

显然它们是对偶码8大数逻辑译码

由H(D)容易求出（3,1,2）和其对偶码（3,2,2）的校验矩阵H9大数逻辑译码由H1可组成（3,1,2）码的以下4个对e01正交的校验和式：由H2可得到对e01和e02正交的校验和式：10大数逻辑译码由此可知，该码能纠正连续9个码元的错误，两个码的大数逻辑译码器图为：11大数逻辑译码12大数逻辑译码译码过程：把接收到的R(D)中的每一段信息元送入编码器中求出校验元，与其后面的校验元模2加，若两者一致，则输出的伴随式分量si为0，否则为1；把加得的值送入伴随式寄存器中寄存；当接收完3个码段以后就开始对第0码段纠错，若此时大数逻辑门的输出为1，则说明第0码段的信息元有错，此时正好第0子组的信息元移至编码器的输出端，从而把它们纠正。13大数逻辑译码同时，纠错信号也反馈至伴随式寄存器修正伴随式，以消除此错误的影响。如果大数判决门没有输出，则说明第0子组的信息元没有错误，这时从编码器中直接将信息元输出。译码器每接收一个码段就对此时前m个时刻输入的码段译码，故该类译码器的译码约束度等于编码约束度为m+1。由于伴随式寄存器中一半以上为1时，大数逻辑门才有信号输出，所以每次对伴随式修正总能使伴随式重量减轻，从而不会引起误差传播。14序列译码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要求误码率很低，且译码器计算量可随信道情况变化时，需采用序列译码一个简单的译码算法：逐分支译码15卷积码的树图表示右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为若输入的信息序列M=(11011…)则编码器的输出为16卷积码的树图表示其树图表示为正确路径a/b:a表示由n0个码元构成的子码，b表示k0个信息元初始截段码∞11/100/000/011/111/110/001/100/010/011/000/101/101/010/117卷积码的树图表示编码过程的实质在输入序列的控制下，编码器沿码树通过某一特定路径的过程译码过程的实质根据接收序列以及信道干扰的统计特性，译码器在原码树上寻找正确路径的过程码树中子集的划分18卷积码的距离度量最小汉明距离不同初始截段码字子集之间的最小汉明距离，用于衡量代数译码的性能第0子组为非零的初始截短码字的最小重量如:(2,1,2)码的最小距离为dmin=3自由距离在所有半无限长码序列之间的最小汉明距离定义为卷积码的自由距离，用于衡量概率译码的性能如:(2,1,2)码的最小距离为df=5Remark不同于分组码，在某些码中，非系统码的df比系统码大19逐分支译码举例编码符号为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.120逐分支译码的局限没有利用卷积码的记忆性例：当接收符号为：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因此不是最大似然序列译码21译码特性一个好的译码算法，必须满足以下几点能以很大概率发现当前走在错误路径上能以很大概率回到正确路径运算量和存贮量要适中当在码树中沿正确路径行进时，R与C的l段长码序列之间总的Hamming距离的趋势与l呈线性变化。大数定律,pe为BSC的转移概率当在码树中沿完全错误（随机）路径行进时，Hamming距离的整体趋势也呈线性变化，但斜率要高于正确路径，约为n/2。R与C完全不相关22译码特性正确路径、随机路径以及判决准则23译码特性斜距离由于信道干扰的原因，错误路径并不总是比正确路径的度量低，但一般情况下沿错误路径走下去总会导致度量的下降24局部错误不过由于卷积码的记忆有限，可能会出现一条错误路径最终与正确路径会合的情况，这样就会出现一段局部错误误码两条路径在此有相同状态25错误事件当由于度量的起伏造成将局部错误的路径看成正确路径时，就发生误码。对卷积码来说，一般比较容易出现的错误都是较小的码距，而较小码距的差错图案一般都是集中在一些序列段中，即由一些局部错误组成。序列译码就是要尽早发现这些局部错误，因为过了这些局部错误之后两个序列的内容就相同了，因此后面的斜率也是相同的。局部错误在路径度量变化中的体现应是一段下垂后继续按正确斜率上升。因此要随时调整判断门限。26Fano度量最大似然译码：接收序列码字序列ML判决序列对离散无记忆信道27Fano度量Bayesian公式：若发送序列先验等概，即另外，则有28Fano度量对数似然值Fano度量Fano译码用Fano度量代替斜距离29Fano度量例子R=(10,10,00,01,11,01,00),C5=(11,10,00,01,10,01),C0=(11)，信道转移概率为p=0.1，求和30Fano算法在向前试探时，如果发现度量值大于当前门限，则向前移动到所试探的节点；如果这次试探是第一次，则可将门限作一定的提高；如果不是第一次，说明曾因门限太高而倒退过，因此不提高门限，以便后面的比较。31Fano算法向前试探时，如果发现度量小于当前门限，说明比试探节点还要坏的节点度量更不可能超过门限，因此在此节点上不必再向前试探下去，而应考虑向回作反向试探。如果反向试探结果是也小于门限，说明当前门限太高需要降低门限，再作向前试探；如果反向试探结果大于门限，说明反向试探节点度量>门限>前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。32Fano算法先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限33Fano算法34Fano算法特点译码器每帧的计算次数，随着信道干扰的大小而变化计算次数与每次的门限增量密切相关，门限增量小，则计算次数增加，反之则减少，但门限增量取值过大，译码器不易发现错误路径，影响译码性能。译码器需要一个输入缓冲器，以存储输入的接收序列。若信道干扰很大时，译码器搜索时间很长，可能引起缓存器溢出。35堆栈(ST)算法核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始将堆栈第一行中路径向各分支延伸，计算新度量删去第一行原存贮内容将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行若第一行中的路径已达码树终点，则结束，否则回到步骤2译码完毕，将存储器中第一行的内容送给用户。36堆栈(ST)算法堆栈(ST)算法流程图：37ST算法的本质存贮一组可能路径每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径繁衍出的子路径与其它未繁衍的路径一起排序堆栈满时最坏路径被丢弃38