《信道编码理论》PPT课件.ppt

《《信道编码理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《信道编码理论》PPT课件.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十二章第十二章 卷积码的概率译码卷积码的概率译码（I）卷积码的网格图表示卷积码的网格图表示卷积码的概率译码：卷积码的概率译码：Viterbi译码算法译码算法修正的修正的Viterbi译码算法译码算法滑窗滑窗状态缩减状态缩减1卷积码的卷积码的Trellis图表示图表示右图为右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生卷积编码示意图，其生成多项式矩阵和生成矩阵分别为成矩阵分别为:2卷积码的卷积码的Trellis图表示图表示s0s1s2s3s0s1s2s3状态图状态图Trellis图图3Viterbi译码译码若编码信息序列为若编码信息序列为 1011100，则编码过程即为在，则编码过程

2、即为在Trellis图上寻找一条路径。图上寻找一条路径。4Viterbi译码译码译码过程即为在译码过程即为在Trellis图上寻找一条路径，该路图上寻找一条路径，该路径对应的编码序列径对应的编码序列与接收序列之间有最大概率度与接收序列之间有最大概率度量：量：5Viterbi译码译码从第从第1时刻的全零状态开始（零状态初始度量为时刻的全零状态开始（零状态初始度量为0，其它状，其它状态初始度量为态初始度量为负无穷负无穷）；）；在任一时刻在任一时刻t，对每一个状态只记录到达路径中度量最对每一个状态只记录到达路径中度量最小小的的一个（残留路径一个（残留路径，硬判决为汉明距离，软判决为欧氏距离硬判决为汉

3、明距离，软判决为欧氏距离）及其度量（状态度量）及其度量（状态度量）；在向在向t+1时刻前进过程中，对时刻前进过程中，对t时刻的每个状态作延伸，即时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到在状态度量基础上加上分支度量，得到|S|2k条路径条路径；对所得到的对所得到的t+1时刻到达每一个状态的时刻到达每一个状态的2k条路径进行比较，条路径进行比较，找到一个度量最大的作为残留路径找到一个度量最大的作为残留路径；直到码的终点，如果确定终点是一个确定状态，则最终保直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果留的路径就是译码结果。6Viterbi译码译码在在BSC

4、和和BIQO-DMC上，最大概率度量分别等效为最小上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量距离度量和最小欧氏距离度量。距离度量更新公式距离度量更新公式：Theorem：在：在Viterbi译码算法中，留选路径是有最大似然译码算法中，留选路径是有最大似然函数的路径。函数的路径。7Viterbi译码译码第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

5、Viterbi译码译码第3个时刻接收子码00汉明距离d21329Viterbi译码译码第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d3331213310Viterbi译码译码第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d3322331311Viterbi译码译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d3233223,43,43312Viterbi译码译码第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,413Viterbi译码译码保存的保存的幸存路径幸存路径为为：译码结果为：译码结

6、果为：101110014Viterbi译码译码收尾收尾最大似然序列译码要求序列有限，因此对卷积码来说，要最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。求能收尾。收尾的原则收尾的原则在信息序列输入完成后，利用输入一些特定的比特，使在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成就变成只有一条残留路径只有一条残留路径，这就是最大似然序列。，这就是最大似然序列。非递归卷积码非递归卷积码约束长度为约束长度为m+1的卷积码，只要在信息序列输入完成后的卷积码

7、，只要在信息序列输入完成后连续送入连续送入m个个0，即可使任一路径都到达最终的状态，即可使任一路径都到达最终的状态0。递归卷积码递归卷积码可通过将输入值置成反馈值的负值，而使可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达个时钟后的状态到达0。15Viterbi译码译码收尾收尾非系统非递归非系统非递归码码递归系统码递归系统码16Viterbi译码译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example(cont.):M=(10111);M=(1011100)17Viterbi译码译码第7个时刻接收子码11汉明距离d2,518Viterbi译码译码保存的保存的

8、幸存路径幸存路径为为：译码结果为：译码结果为：101110019软判决软判决Viterbi译码译码基本思想：基本思想：为了充分利用信道输出符号的信息，提高译码可靠性，为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行把信道输出的信号进行Q电平量化，然后在输入电平量化，然后在输入Viterbi译码器。能适应这种译码器。能适应这种Q进制输入的进制输入的Viterbi译码器称为译码器称为软软判决判决Viterbi译码器译码器。例子：例子：Q=4电平量化的信道比特度量：电平量化的信道比特度量：001021121120Viterbi译码的复杂度译码的复杂度对信息序列长度为对信息序列长度

9、为L，信息符号取自信息符号取自GF(p)，R=k/n，约束长度为约束长度为m+1的卷积码。状态数为的卷积码。状态数为pkm因此对每个时刻要做因此对每个时刻要做pkm次次加比选加比选得到得到pkm个状态的残留个状态的残留路径；路径；每次加比选包括每次加比选包括pk次加法和次加法和pk-1次比较次比较。因此总运算量。因此总运算量约为约为Lpkm次加比选；次加比选；同时要能保存同时要能保存pkm条残留路径，因此需要条残留路径，因此需要Lpkm个存贮单个存贮单元。元。21Viterbi译码的特点译码的特点维特比算法是最大似然的序列译码算法；维特比算法是最大似然的序列译码算法；译码复杂度与信道质量无关；

10、译码复杂度与信道质量无关；运算量与码长呈线性关系；运算量与码长呈线性关系；存贮量与码长呈线性关系；存贮量与码长呈线性关系；运算量和存贮量都与状态数呈线性关系；运算量和存贮量都与状态数呈线性关系；状态数随分组大小状态数随分组大小k及编码存贮及编码存贮m呈呈指数指数关系。关系。22滑窗滑窗Viterbi译码算法译码算法基本思想：基本思想：当状态数有限时，给定时刻的各状态残留路径在一定当状态数有限时，给定时刻的各状态残留路径在一定时间（时间（L）之前来自于同一状态的可能性随之前来自于同一状态的可能性随L的增加而的增加而迅速趋近于迅速趋近于1。因此当前时刻各残留路径很可能来自于。因此当前时刻各残留路径

11、很可能来自于L时刻前的同一路径。时刻前的同一路径。23滑窗滑窗Viterbi算法实现算法实现在第在第t时刻，可以将时刻，可以将t-L时刻前的路径结果直接输出，而在时刻前的路径结果直接输出，而在存贮空间中不再保存存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在时刻前的内容。因此存贮量控制在Lpkm。这里的这里的L就被称做就被称做译码深度译码深度，不再随码长的增加而，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情况增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至下甚至不需要对流分段加尾比特不需要对流分段加尾比特。显然，滑动窗算法是一种准最优算法。但通常译码深度只显

12、然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的要有编码约束长度的5到到10倍，其性能损失就可以忽略不倍，其性能损失就可以忽略不计了。计了。24缩减状态的缩减状态的Viterbi译码译码由于运算量与由于运算量与k和和m呈指数关系，因此维特比译码呈指数关系，因此维特比译码算法一般只适合于算法一般只适合于k和和m较小的场合。大多数情况较小的场合。大多数情况下下k=1，m门限门限前向试探节前向试探节点，因此应考虑从反向试探节点另一个方向衍点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点

13、。以便向前观察下一个最佳节点。40Fano算法算法先找一个最佳节点，大于门限，则前进并提高门先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。并提高门限，再向前找一个最佳节点，小于门限。41 Fano算法算法42堆栈堆栈(ST)算法算法核心：存贮一组可能的路径，但每次只对当时认为核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始；从码树图起始节点开始；将堆栈第一行中路径向各分支延伸，计算新度

14、量；将堆栈第一行中路径向各分支延伸，计算新度量；删去第一行原存贮内容；删去第一行原存贮内容；将延伸后的各路径在堆栈中重新排序，找出度量量大的将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行；路径放在第一行；若第一行中的路径已达码树终点，则结束，否则回到步若第一行中的路径已达码树终点，则结束，否则回到步骤骤2。43ST算法的本质算法的本质存贮一组可能路径；存贮一组可能路径；每次只有最可能的（度量最大的）路径可以繁衍，每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径；同时删去父路径；繁衍出的子路径与其它未繁衍的路径一起排序；繁衍出的子路径与其它未繁衍的路径一起排序；堆栈满时

15、最坏路径被丢弃。堆栈满时最坏路径被丢弃。44序列译码的特点序列译码的特点运算量与信道质量有关；运算量与信道质量有关；需要输入缓冲器，其长度也与信道质量有关，有需要输入缓冲器，其长度也与信道质量有关，有溢出现象；溢出现象；计算量与约束长度无关。计算量与约束长度无关。45TCM encoder46TCMFor a trellis code C(of length n),the minimum squared Euclidean distance between two different sequences of signal points is referred to as its free s

16、quared Euclidean distance;i.e.,The asymptotic coding gain(including shaping gain)is defined to be where denote the minimum squared Euclidean distance between signal points in the uncoded scheme,and E and E(u)denote the average signal energies of the coded and uncoded schemes,respectively.dB 47TCM ex

17、ample The 4-state TCM encoder for 8-PSK 48Set partition of 8PSK49Trellis diagramThe error event corresponding to 50Coding gainThe intra-subset minimum squared Euclidean distance is given by In this example,the parallel transitions are associated with signals from one of the four subsets,C(00),C(01),

18、C(10),C(11),with minimum squared Euclidean distance In this example,the minimum squared Euclidean distance between any two different sequences of subsets 51Coding gainThus,the free squared Euclidean distance of this TCM code isCompared with an uncoded QPSK scheme with the minimum squared Euclidean distance 2Es between signal points,this TCM scheme can provide an asymptotic coding gain of (dB)QPSK constellation52