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

1,第十二章 卷积码的概率译码 （I）,卷积码的网格图表示 卷积码的概率译码：Viterbi译码算法 修正的Viterbi译码算法 滑窗 状态缩减,2,卷积码的Trellis图表示,右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为:,3,卷积码的Trellis图表示,s0,s1,s2,s3,s0,s1,s2,s3,状态图Trellis图,4,Viterbi译码,若编码信息序列为 1011100，则编码过程即为在Trellis图上寻找一条路径。,5,Viterbi译码,译码过程即为在Trellis图上寻找一条路径，该路径对应的编码序列与接收序列之间有最大概率度量：,6,Viterbi译码,从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）； 在任一时刻t，对每一个状态只记录到达路径中度量最小的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）； 在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到|S|2k条路径； 对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径； 直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果。,7,Viterbi译码,在BSC和BIQO-DMC上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量 。 距离度量更新公式 ： Theorem：在Viterbi译码算法中，留选路径是有最大似然函数的路径。,8,Viterbi译码,第1个时刻接收子码10,汉明距离d,1,1,第2个时刻接收子码10,汉明距离d,Example: M=(1011100)，初始状态为全0的编码器输出序列为C=(11, 10, 00, 01, 10, 01, 11), 通过有噪信道后，接收序列为R=(10, 10, 00, 01, 11, 01, 11),1,1,9,Viterbi译码,第3个时刻接收子码00,汉明距离d,2,1,3,2,10,Viterbi译码,第4个时刻接收子码01,汉明距离d,3,4,3,4,3,3,1,5,汉明距离d,3,3,3,1,2,1,3,3,11,Viterbi译码,第5个时刻接收子码11,汉明距离d,3,5,3,5,2,4,2,4,汉明距离d,3,3,2,2,3,3,1,3,12,Viterbi译码,第6个时刻接收子码01,汉明距离d,3,4,2,5,汉明距离d,3,2,3,3,2,2,3,4,3,4,3,3,13,Viterbi译码,第7个时刻接收子码11,汉明距离d,2,5,3,2,3,3,01/0,00/1,01/1,10/1,10/0,11/1,4,4,4,4,3,4,14,Viterbi译码,保存的幸存路径为：,译码结果为：1011100,15,Viterbi译码收尾,最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。 收尾的原则 在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。 非递归卷积码 约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。 递归卷积码 可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。,16,Viterbi译码收尾,非系统非递归码,递归系统码,17,Viterbi译码,第6个时刻接收子码01,汉明距离d,3,4,2,5,汉明距离d,3,2,3,3,2,2,Example (cont.): M=(10111); M=(1011100),18,Viterbi译码,第7个时刻接收子码11,汉明距离d,2,5,19,Viterbi译码,保存的幸存路径为：,译码结果为：1011100,20,软判决Viterbi译码,基本思想： 为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行Q电平量化，然后在输入Viterbi译码器。能适应这种Q进制输入的Viterbi译码器称为软判决Viterbi译码器。 例子：Q=4电平量化的信道比特度量：,0,01,02,1,12,11,21,Viterbi译码的复杂度,对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm 因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径； 每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选； 同时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。,22,Viterbi译码的特点,维特比算法是最大似然的序列译码算法； 译码复杂度与信道质量无关； 运算量与码长呈线性关系； 存贮量与码长呈线性关系； 运算量和存贮量都与状态数呈线性关系； 状态数随分组大小k及编码存贮m呈指数关系。,23,滑窗Viterbi译码算法,基本思想： 当状态数有限时，给定时刻的各状态残留路径在一定时间（L）之前来自于同一状态的可能性随L的增加而迅速趋近于1。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。,24,滑窗Viterbi算法实现,在第t时刻，可以将t-L时刻前的路径结果直接输出，而在存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在Lpkm。这里的L就被称做译码深度，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至不需要对流分段加尾比特。 显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的5到10倍，其性能损失就可以忽略不计了。,25,缩减状态的Viterbi译码,由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m10。 对状态数很大的卷积码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。,26,第十二章 卷积码的概率译码 （II）,序列译码 Fano译码算法 ST译码算法 调制与编码的结合(TCM技术),27,序列译码,Viterbi译码算法存在的问题: 对m值很大的情况不适用误码率很难做的很低; 译每一个分支的计算量不变; Viterbi译码中路径度量计算方法不适用于比较不同长度的路径，如: 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 要求误码率很低，且译码器计算量可随信道情况变化时，需采用序列译码: 一个简单的译码算法：逐分支译码。,28,逐分支译码举例,编码符号为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.9 001: d =|-1-(-0.2)|+|1-(-0.3)|=2.1,29,逐分支译码的局限,没有利用卷积码的记忆性； 例：当接收符号为：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.5+0.7=4.0 因此不是最大似然序列译码。,30,译码特性,一个好的译码算法，必须满足以下几点： 能以很大概率发现当前走在错误路径上； 能以很大概率回到正确路径； 运算量和存贮量要适中。 当在码树中沿正确路径行进时，R与C的l段长码序列之间总的Hamming距离的趋势与l呈线性变化。 大数定律, pe为BSC的转移概率。 当在码树中沿完全错误（随机）路径行进时， Hamming距离的整体趋势也呈线性变化，但斜率要高于正确路径，约为n0/2。 R与C完全不相关。,31,译码特性,正确路径、随机路径以及判决准则:,32,译码特性,斜距离: 由于信道干扰的原因，错误路径并不总是比正确路径的度量低，但一般情况下沿错误路径走下去总会导致度量的下降。,33,局部错误,不过由于卷积码的记忆有限，可能会出现一条错误路径最终与正确路径会合的情况，这样就会出现一段局部错误。,误码,两条路径在此有相同状态,34,错误事件,当由于度量的起伏造成将局部错误的路径看成正确路径时，就发生误码。 对卷积码来说，一般比较容易出现的错误都是较小的码距，而较小码距的差错图案一般都是集中在一些序列段中，即由一些局部错误组成。序列译码就是要尽早发现这些局部错误，因为过了这些局部错误之后两个序列的内容就相同了，因此后面的斜率也是相同的。 局部错误在路径度量变化中的体现应是一段下垂后继续按正确斜率上升。因此要随时调整判断门限。,35,Fano度量,最大似然译码： 接收序列： 码字序列： ML判决序列： 对离散无记忆信道：,36,Fano度量,Bayesian公式： 若发送序列先验等概，即 另外 ，则有,37,Fano度量,对数似然值： Fano度量： Fano译码： 用Fano度量代替斜距离：,38,Fano度量,例子： R=(10,10,00,01,11,01,00), C5=(11,10,00,01,10,01), C0=(11)，信道转移概率为p=0.1，求 和,39,Fano算法,在向前试探时，如果发现度量值大于当前门限，则向前移动到所试探的节点；如果这次试探是第一次，则可将门限作一定的提高；如果不是第一次，说明曾因门限太高而倒退过，因此不提高门限，以便后面的比较。,40,Fano算法,向前试探时，如果发现度量小于当前门限，说明比试探节点还要坏的节点度量更不可能超过门限，因此在此节点上不必再向前试探下去，而应考虑向回作反向试探。如果反向试探结果是也小于门限，说明当前门限太高需要降低门限，再作向前试探；如果反向试探结果大于门限，说明反向试探节点度量门限前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。,41,Fano算法,先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。,42,Fano算法,43,堆栈(ST)算法,核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。 从码树图起始节点开始； 将堆栈第一行中路径向各分支延伸，计算新度量； 删去第一行原存贮内容； 将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行； 若第一行中的路径已达码树终点，则结束，否则回到步骤2。,44,ST算法的本质,存贮一组可能路径； 每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径； 繁衍出的子路径与其它未繁衍的路径一起排序； 堆栈满时最坏路径被丢弃。,45,序列译码的特点,运算量与信道质量有关； 需要输入缓冲器，其长度也与信道质量有关，有溢出现象； 计算量与约束长度无关。,46,TCM encoder,47,TCM,For 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 squared 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,48,TCM example,The 4-state TCM encoder for 8-PSK,49,Set partition of 8PSK,50,Trellis diagram,The error event corresponding to,51,Coding gain,The 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), C(10), C(11), with minimum squared Euclidean distance In this example, the minimum squared Euclidean distance between any two dif