《信道编码理论》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，m门限前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。,41,Fano算法,先找一个最佳节点，大于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。,42,Fano算法,43,堆栈(ST)算法,核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始；将堆栈第一行中路径向各分支延伸，计算新度量；删去第一行原存贮内容；将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行；若第一行中的路径已达码树终点，则结束，否则回到步骤2。,44,ST算法的本质,存贮一组可能路径；每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径；繁衍出的子路径与其它未繁衍的路径一起排序；堆栈满时最坏路径被丢弃。,45,序列译码的特点,运算量与信道质量有关；需要输入缓冲器，其长度也与信道质量有关，有溢出现象；计算量与约束长度无关。,46,TCMencoder,47,TCM,ForatrelliscodeC(oflengthn),theminimumsquaredEuclideandistancebetweentwodifferentsequencesofsignalpointsisreferredtoasitsfreesquaredEuclideandistance;i.e.,Theasymptoticcodinggain(includingshapinggain)isdefinedtobewheredenotetheminimumsquaredEuclideandistancebetweensignalpointsintheuncodedscheme,andEandE(u)denotetheaveragesignalenergiesofthecodedanduncodedschemes,respectively.,dB,48,TCMexample,The4-stateTCMencoderfor8-PSK,49,Setpartitionof8PSK,50,Trellisdiagram,Theerroreventcorrespondingto,51,Codinggain,Theintra-subsetminimumsquaredEuclideandistanceisgivenbyInthisexample,theparalleltransitionsareassociatedwithsignalsfromoneofthefoursubsets,C(00),C(01),C(10),C(11),withminimumsquaredEuclideandistanceInthisexample,theminimumsquaredEuclideandistancebetweenanytwodifferentsequencesofsubsets,52,Codinggain,Thus,thefreesquaredEu