信道编码理论

1、信道编码理论第1页，共52页，2022年，5月20日，1点34分，星期一卷积码的Trellis图表示右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为:2第2页，共52页，2022年，5月20日，1点34分，星期一卷积码的Trellis图表示s0s1s2s3s0s1s2s3状态图Trellis图3第3页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码若编码信息序列为 1011100，则编码过程即为在Trellis图上寻找一条路径。4第4页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码译码过程即为在Trellis图上寻找一条路径

2、，该路径对应的编码序列与接收序列之间有最大概率度量：5第5页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）；在任一时刻t，对每一个状态只记录到达路径中度量最小的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）；在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到|S|2k条路径；对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径；直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果。6

3、第6页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码在BSC和BIQO-DMC上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量 。距离度量更新公式 ：Theorem：在Viterbi译码算法中，留选路径是有最大似然函数的路径。7第7页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第1个时刻接收子码10汉明距离d11第2个时刻接收子码10汉明距离dExample: M=(1011100)，初始状态为全0的编码器输出序列为C=(11, 10, 00, 01, 10, 01, 11), 通过有噪信道后，接收序列为R=(10,

4、10, 00, 01, 11, 01, 11)118第8页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第3个时刻接收子码00汉明距离d21329第9页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d3331213310第10页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d3322331311第11页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第6个时刻接收子码

5、01汉明距离d3,42,5汉明距离d3233223,43,43312第12页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,413第13页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码保存的幸存路径为：译码结果为：101110014第14页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码收尾最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。收尾的原则在信息序列输入完成后，利用输入一些特定的比特，使|S|

6、个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。非递归卷积码约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。递归卷积码可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。15第15页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码收尾非系统非递归码递归系统码16第16页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example (cont.): M=(10111

7、); M=(1011100)17第17页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码第7个时刻接收子码11汉明距离d2,518第18页，共52页，2022年，5月20日，1点34分，星期一Viterbi译码保存的幸存路径为：译码结果为：101110019第19页，共52页，2022年，5月20日，1点34分，星期一软判决Viterbi译码基本思想：为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行Q电平量化，然后在输入Viterbi译码器。能适应这种Q进制输入的Viterbi译码器称为软判决Viterbi译码器。例子：Q=4电平量化的信道比特度量：

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

9、；运算量和存贮量都与状态数呈线性关系；状态数随分组大小k及编码存贮m呈指数关系。22第22页，共52页，2022年，5月20日，1点34分，星期一滑窗Viterbi译码算法基本思想：当状态数有限时，给定时刻的各状态残留路径在一定时间（L）之前来自于同一状态的可能性随L的增加而迅速趋近于1。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。23第23页，共52页，2022年，5月20日，1点34分，星期一滑窗Viterbi算法实现在第t时刻，可以将t-L时刻前的路径结果直接输出，而在存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在Lpkm。这里的L就被称做译码深度，不再随码长的增加而增

10、加。因而特别适合信息流的卷积码编译码。在这种情况下甚至不需要对流分段加尾比特。显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的5到10倍，其性能损失就可以忽略不计了。24第24页，共52页，2022年，5月20日，1点34分，星期一缩减状态的Viterbi译码由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m门限前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。40第40页，共52页，2022年，5月20日，1点34分，星期一Fano算法先找一个最佳节点，大

11、于门限，则前进并提高门限；再向前找一个最佳节点，大于门限，则前进并提高门限，再向前找一个最佳节点，小于门限。41第41页，共52页，2022年，5月20日，1点34分，星期一 Fano算法42第42页，共52页，2022年，5月20日，1点34分，星期一堆栈(ST)算法核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始；将堆栈第一行中路径向各分支延伸，计算新度量；删去第一行原存贮内容；将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行；若第一行中的路径已达码树终点，则结束，否则回到步骤2。43第43页，共52页，2022年，5月20

12、日，1点34分，星期一ST算法的本质存贮一组可能路径；每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径；繁衍出的子路径与其它未繁衍的路径一起排序；堆栈满时最坏路径被丢弃。44第44页，共52页，2022年，5月20日，1点34分，星期一序列译码的特点运算量与信道质量有关；需要输入缓冲器，其长度也与信道质量有关，有溢出现象；计算量与约束长度无关。45第45页，共52页，2022年，5月20日，1点34分，星期一TCM encoder46第46页，共52页，2022年，5月20日，1点34分，星期一TCMFor a trellis code C (of length n), the mi

13、nimum 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

14、scheme, and E and E(u) denote the average signal energies of the coded and uncoded schemes, respectively. dB 47第47页，共52页，2022年，5月20日，1点34分，星期一TCM example The 4-state TCM encoder for 8-PSK 48第48页，共52页，2022年，5月20日，1点34分，星期一Set partition of 8PSK49第49页，共52页，2022年，5月20日，1点34分，星期一Trellis diagramThe error

15、event corresponding to 50第50页，共52页，2022年，5月20日，1点34分，星期一Coding 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), C(10), C(11), with minimum squared Euclidean distance In this example, the minimum squared Euclidean distance between any two different sequences of subsets 51第51页，共52页，2022年，5月20日，1点34分，星期一Coding gainThus, the free squared Euclidean di