纠错码Lecture8-卷积码(III)

1、信道编码理论信道编码理论邢莉娟、李卓，西安电子科技大学邢莉娟、李卓，西安电子科技大学Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论2大数逻辑译码大数逻辑译码Fano译码算法译码算法ST译码算法译码算法Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论3例子：例子：设（设（2,1,6）系统卷积码，子生成元：）系统卷积码，子生成元： 对应校对应校验矩阵为：验矩阵为： (1,1)()1,D g(1,1)(1000000),g(1,2)(1010011),g(1,2)256()1DDDD g1100 111

2、0 00 1100 10 00 1100 00 10 00 1110 00 00 10 00 1110 10 00 00 10 00 11H =Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论4设错误图样设错误图样伴随式为伴随式为式中式中01 0211 1221 2231 3241 4251 5261 62,e ee ee ee ee ee ee eE =01112131415161,TsssssssS = E H0101021111122101212231113132412141425101315152610111416162+seeseese

3、eeseeeseeeseeeeseeeeeLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论5由以上由以上7个方程知，在个方程知，在s01， s21 ，s51和和s61四个方程中，四个方程中，除除e01外，其他码元位至多出现一次，从而组成外，其他码元位至多出现一次，从而组成4个个对对e01码元位正交的一致校验和式。所以码元位正交的一致校验和式。所以e01位上的错位上的错误完全可以由误完全可以由s01， s21 ，s51和和s61确定，而它们的值由确定，而它们的值由H中的第中的第0、2、5、6行的校验关系决定。行的校验关系决定。定义：定义：任一个（任

4、一个（n0，k0，m）系统卷积码，若能由）系统卷积码，若能由H矩阵中的矩阵中的Ji行直接组成对行直接组成对e01（i=1,2， k0 ,若为非若为非系统码系统码i=1,2， n0 ）正交的）正交的Ji正交校验和式，则称正交校验和式，则称此码为此码为自正交系统卷积码自正交系统卷积码，若码的最小距离，若码的最小距离dFD=J+1，则称为则称为完备自正交码完备自正交码。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论6例子：例子：构造（构造（3,1,2）和（）和（3,2,2,）码的子正交系统卷积码大）码的子正交系统卷积码大数逻辑译码器。数逻辑译码器。

5、(3,1,2)码有两个校验元，子生成元式：码有两个校验元，子生成元式： ( 3,1,2)码有两个信息元，子生成元式：码有两个信息元，子生成元式： (1,2)()1,DD g(1,3)2()1DD g(1,3)()1,DD g(2,3)2()1DD gLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论7故，对（故，对（ 3,1,2 ）码）码对（对（ 3,1,2 ）码）码 显然它们是对偶码显然它们是对偶码221 0 1()()1,1,10 1 1DDDDDDGH2211 0(D) = 1,1,1()10 1DDDDDGHLecture 8 Lectur

6、e 8 卷积码卷积码(III)(III)信道编码理论信道编码理论8 由由H(D)容易求出（容易求出（3,1,2）和其对偶码（）和其对偶码（3,2,2）的校验）的校验矩阵矩阵H12110101111100 110100 111000 101010 100 111000 100 110100 000 101HHLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论9由由H1可组成（可组成（3,1,2）码的以下）码的以下4个对个对e01正交的校验和式：正交的校验和式：由由H2可得到对可得到对e01和和e02正交的校验和式：正交的校验和式：0101020201

7、031101111222012123seeseeseeeseee0010203101111213001020320211212223+seeeseeeeseeeseeeeeLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论10由此可知，该码能纠正连续由此可知，该码能纠正连续9个码元的错误，两个码的大数个码元的错误，两个码的大数逻辑译码器图为：逻辑译码器图为：Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论11Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理

8、论12译码过程：译码过程：1. 把接收到的把接收到的R(D)中的每一段信息元送入编码器中求出校中的每一段信息元送入编码器中求出校验元，与其后面的校验元模验元，与其后面的校验元模2加，若两者一致，则输出的加，若两者一致，则输出的伴随式分量伴随式分量si为为0，否则为，否则为1；2. 把加得的值送入伴随式寄存器中寄存；把加得的值送入伴随式寄存器中寄存；3. 当接收完当接收完3个码段以后就开始对第个码段以后就开始对第0码段纠错，若此时大码段纠错，若此时大数逻辑门的输出为数逻辑门的输出为1，则说明第，则说明第0码段的信息元有错，此码段的信息元有错，此时正好第时正好第0子组的信息元移至编码器的输出端，从

9、而把它子组的信息元移至编码器的输出端，从而把它们纠正。们纠正。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论134.同时，纠错信号也反馈至伴随式寄存器修正伴随式，以同时，纠错信号也反馈至伴随式寄存器修正伴随式，以消除此错误的影响。如果大数判决门没有输出，则说明消除此错误的影响。如果大数判决门没有输出，则说明第第0子组的信息元没有错误，这时从编码器中直接将信息子组的信息元没有错误，这时从编码器中直接将信息元输出。元输出。 译码器每接收一个码段就对此时前译码器每接收一个码段就对此时前m个时刻输入的码个时刻输入的码段译码，故该类译码器的译码约束度等于

10、编码约束度为段译码，故该类译码器的译码约束度等于编码约束度为m+1。 由于伴随式寄存器中一半以上为由于伴随式寄存器中一半以上为1时，大数逻辑门才时，大数逻辑门才有信号输出，所以每次对伴随式修正总能使伴随式重量有信号输出，所以每次对伴随式修正总能使伴随式重量减轻，从而不会引起误差传播。减轻，从而不会引起误差传播。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论14Viterbi译码算法存在的问题译码算法存在的问题 对对m值很大的情况不适用值很大的情况不适用误码率很难做的很低误码率很难做的很低 译每一个分支的计算量不变译每一个分支的计算量不变 Vit

11、erbi译码中路径度量计算方法不适用于比较不同长度的路径，译码中路径度量计算方法不适用于比较不同长度的路径，如如 R =(10,10,00,01,11,01,00) C5=(11,10,00,01,10,01) C0=(11) d(R0R5, C5)=2 d(R0, C0)=1要求误码率很低，且译码器计算量可随信道情况变化时，要求误码率很低，且译码器计算量可随信道情况变化时，需采用需采用序列译码序列译码 一个简单的译码算法：一个简单的译码算法：逐分支译码逐分支译码Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论15右图为右图为(2,1,2)卷积编

12、码示意图，其生成多项式矩阵和卷积编码示意图，其生成多项式矩阵和生成矩阵分别为生成矩阵分别为若输入的信息序列若输入的信息序列M=(1 1 0 1 1 )则编码器的输出为则编码器的输出为22( )1, 1DDDDG11 101111 101111 1011G11, 01, 01, 00, 01, 01,CMGLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论16其树图表示为其树图表示为正确路径正确路径a/b: a表示由表示由n0个个码元构成的子码，码元构成的子码，b表示表示k0个信息元个信息元11/100/000/011/111/110/001/100

13、/010/011/000/101/101/010/1Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论17编码过程的实质编码过程的实质 在输入序列的控制下，编码器沿码树通过某一特定路径的过程在输入序列的控制下，编码器沿码树通过某一特定路径的过程译码过程的实质译码过程的实质 根据接收序列以及信道干扰的统计特性，译码器在原码树上寻根据接收序列以及信道干扰的统计特性，译码器在原码树上寻找正确路径的过程找正确路径的过程码树中子集的划分码树中子集的划分m0m1m1010011s0c0=00s1c0=11s00c1=00s01c1=11s10c0=10s11c

14、0=01Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论18最小汉明距离最小汉明距离 不同初始截段码字子集之间的最小汉明距离，用于衡量代数译码不同初始截段码字子集之间的最小汉明距离，用于衡量代数译码的性能的性能 第第0子组为非零子组为非零的初始截短码字的最小重量的初始截短码字的最小重量 如如: (2, 1, 2)码的最小距离为码的最小距离为dmin=3自由距离自由距离 在所有半无限长码序列之间的最小汉明距离定义为卷积码的自由在所有半无限长码序列之间的最小汉明距离定义为卷积码的自由距离，用于衡量概率译码的性能距离，用于衡量概率译码的性能 如如: (

15、2, 1, 2)码的最小距离为码的最小距离为df =5Remark 不同于分组码，在某些码中，非系统码的不同于分组码，在某些码中，非系统码的df比系统码大比系统码大Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论19编码符号为编码符号为1时发时发+1，编，编码符号为码符号为0时发时发-1当接收符号为：当接收符号为：0.8, 0.7, -0.2, -0.3, 0.5, -0.3时，尽管时，尽管第二次分支为两个负数，第二次分支为两个负数，但更象分支但更象分支“1”，因此，因此判信息序列为判信息序列为110第二次分支第二次分支110: d = |1-(

16、-0.2)|+|-1-(-0.3)|=1.9 001: d =|-1-(-0.2)|+|1-(-0.3)|=2.1Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论20没有利用卷积码的记忆性没有利用卷积码的记忆性例：当接收符号为：例：当接收符号为：0.8, 0.7, -0.2, 0.1, 0.5, -0.3时，时，判信息序列为判信息序列为101但从整体序列来看，更像但从整体序列来看，更像110 101110100: d = 0.2+0.3+ 0.8+0.9+1.5+0.7=4.4 110111010: d = 0.2+0.3+ 1.2+1.1+0.

17、5+0.7=4.0因此因此不是最大似然序列译不是最大似然序列译码码Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论21一个好的译码算法，必须满足以下几点一个好的译码算法，必须满足以下几点 能以很大概率发现当前走在错误路径上能以很大概率发现当前走在错误路径上 能以很大概率回到正确路径能以很大概率回到正确路径 运算量和存贮量要适中运算量和存贮量要适中当在码树中沿正确路径行进时，当在码树中沿正确路径行进时，R与与C的的l段长码序列之间段长码序列之间总的总的Hamming距离的趋势与距离的趋势与l呈线性变化。呈线性变化。 大数定律大数定律, pe为为BS

18、C的转移概率的转移概率当在码树中沿完全错误（随机）路径行进时，当在码树中沿完全错误（随机）路径行进时， Hamming距离的整体趋势也呈线性变化，但斜率要高于正确路径，距离的整体趋势也呈线性变化，但斜率要高于正确路径，约为约为n/2。 R与与C完全不相关完全不相关0,llleddn lpR CLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论22正确路径、随机路径以及判决准则正确路径、随机路径以及判决准则Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论230,lllpn ldC R12epp斜距离斜距

19、离由于信道干扰的原因，由于信道干扰的原因，错误路径并不总是比错误路径并不总是比正确路径的度量低，正确路径的度量低，但一般情况下沿错误但一般情况下沿错误路径走下去总会导致路径走下去总会导致度量的下降度量的下降Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论24不过由于卷积码的不过由于卷积码的记忆有限，可能会记忆有限，可能会出现一条错误路径出现一条错误路径最终与正确路径会最终与正确路径会合的情况，这样就合的情况，这样就会出现一段局部错会出现一段局部错误误ll误码误码两条路径在此有相两条路径在此有相同状态同状态Lecture 8 Lecture 8 卷

20、积码卷积码(III)(III)信道编码理论信道编码理论25当由于度量的起伏造成将局部错误的路径看成正确路径时，当由于度量的起伏造成将局部错误的路径看成正确路径时，就发生误码。就发生误码。对卷积码来说，一般比较容易出现的错误都是较小的码距，对卷积码来说，一般比较容易出现的错误都是较小的码距，而较小码距的差错图案一般都是集中在一些序列段中，即而较小码距的差错图案一般都是集中在一些序列段中，即由一些由一些局部错误局部错误组成。序列译码就是要尽早发现这些局部组成。序列译码就是要尽早发现这些局部错误，因为过了这些局部错误之后两个序列的内容就相同错误，因为过了这些局部错误之后两个序列的内容就相同了，因此后

21、面的斜率也是相同的。了，因此后面的斜率也是相同的。局部错误在路径度量变化中的体现应是局部错误在路径度量变化中的体现应是一段下垂后继续按一段下垂后继续按正确斜率上升正确斜率上升。因此要。因此要随时调整判断门限随时调整判断门限。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论26argmax PCCR CC01-1LcccC1-L10RRRR1010LniiiLiii0crPPPCRCR最大似然译码：最大似然译码：接收序列接收序列码字序列码字序列ML判决序列判决序列对离散无记忆信道对离散无记忆信道Lecture 8 Lecture 8 卷积码卷积码(

22、III)(III)信道编码理论信道编码理论27 RCRCRCPPPPmax Pmax PR CC R 1010002LniiLniiiLRnrPcrPPC0RC C0LRnP 2C QrPi1Bayesian公式：公式：若发送序列先验等概，即若发送序列先验等概，即另外另外 ，则有，则有Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论28 10210200loglogLniCiiiLniiiiC02RrPcrPrPcrPLRnPlogRC CiiiiiFRrPcrPcrM2log ClniiiilniiiFlFlRnrPcrPcrMM0102100

23、0logCR对数似然值对数似然值Fano度量度量Fano译码译码用用Fano度量代替斜距离度量代替斜距离lFlMR CLecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论295FMCR0FMCR 1022loglogLniiiiC05F0rPcrPLRnMCR26. 221log12log21log102112222pp 1022loglogLniiiiC00F0rPcrPLRnMCR49. 221log2log1log212222pp例子例子R=(10,10,00,01,11,01,00), C5=(11,10,00,01,10,01), C0=(

24、11)，信道转移概率为，信道转移概率为p=0.1，求，求 和和Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论30在向前试探时，如果发现在向前试探时，如果发现度量值大于当前门限度量值大于当前门限，则向前移动到所试探的节点；如果这次试探是第则向前移动到所试探的节点；如果这次试探是第一次，则可将门限作一定的提高；如果不是第一一次，则可将门限作一定的提高；如果不是第一次，说明曾因门限太高而倒退过，因此不提高门次，说明曾因门限太高而倒退过，因此不提高门限，以便后面的比较。限，以便后面的比较。Lecture 8 Lecture 8 卷积码卷积码(III)(

25、III)信道编码理论信道编码理论31向前试探时，如果发现向前试探时，如果发现度量小于当前门限度量小于当前门限，说，说明比试探节点还要坏的节点度量更不可能超过明比试探节点还要坏的节点度量更不可能超过门限，因此在此节点上不必再向前试探下去，门限，因此在此节点上不必再向前试探下去，而应考虑向回作反向试探。如果反向试探结果而应考虑向回作反向试探。如果反向试探结果是也小于门限，说明当前门限太高需要降低门是也小于门限，说明当前门限太高需要降低门限，再作向前试探；如果反向试探结果大于门限，再作向前试探；如果反向试探结果大于门限，说明反向试探节点度量限，说明反向试探节点度量门限门限前向试探节前向试探节点，因此

26、应考虑从反向试探节点另一个方向衍点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。以便向前观察下一个最佳节点。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论32先找一个最佳节点，大于门限，则前进并提高门先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限并提高门限，再向前找一个最佳节点，小于门限Lecture 8 Lecture 8

27、卷积码卷积码(III)(III)信道编码理论信道编码理论33Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论34 译码器每帧的计算次数，随着信道干扰的大小译码器每帧的计算次数，随着信道干扰的大小而变化而变化计算次数与每次的门限增量密切相关，门限增量计算次数与每次的门限增量密切相关，门限增量小，则计算次数增加，反之则减少，但门限增量小，则计算次数增加，反之则减少，但门限增量取值过大，译码器不易发现错误路径，影响译码取值过大，译码器不易发现错误路径，影响译码性能。性能。译码器需要一个输入缓冲器，以存储输入的接收译码器需要一个输入缓冲器，以存储输入的接收序列。若信道干扰很大时，译码器搜索时间很长，序列。若信道干扰很大时，译码器搜索时间很长，可能引起缓存器溢出。可能引起缓存器溢出。Lecture 8 Lecture 8 卷积码卷积码(III)(III)信道编码理论信道编码理论35核心：存贮一组可能的路径，但每次只对当时认为核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。的最佳路径进行延伸，然后再重新排序