信息论与编码理论ch6信道编码卷积码2的课件

1、 我们必须有恒心，尤其要有自信力！我们必须相信我们的天赋是要用来作某种事情的，无论代价多么大，这种事情必须作到。 居里夫人 2022/8/1616.4.1 卷积码的基本概念6.4.2 卷积码的编码6.4.3 卷积码的矩阵描述6.4.4 卷积码的译码6.4.5 卷积码的状态转移图与栅格描述6.4.6 维特比译码的基本原理6.4.7 软判决维特比译码6.4.8 维特比译码的性能6.4.9 维特比译码的应用6.4 卷积码2022/8/162(1) 卷积码译码的种类：卷积码的译码可分为代数译码和概率译码。(2) 代数译码：从码的代数结构出发，以一个约束度的接收序列为单位，对该接收序列的信息码组进行译码

2、。大数逻辑译码是代数译码的主要方法。 代数译码中，用矩阵描述比较方便。(3) 概率译码：从信道的统计特性出发，以远大于约束度的接收序列为单位，对信息码组进行最大似然的判决。维特比译码和序列译码是其最主要的方法。 在维特比译码中，用篱笆图来描述码的译码更为方便。 6.4.4 卷积码的译码2022/8/163代数译码和概率译码：代数译码沿用分组码代数译码的思路，先由接收序列R(D)=C(D)+E(D)求伴随式S(D)，再由S(D)估算差错图案(D)，并令译码估值(D)=R(D)-(D), 最后将(D)乘以转移函数逆矩阵G-1(D) 得信息序列M(D)。受逆矩阵G-1(D)和差错图案(D)计算上的限

3、制，代数译码一般仅用于简单的卷积码。其优点是译码电路简单，时延小，适合于高速译码。其不足之处在于：适合代数译码的卷积码的编码增益一般都不大，且仅适合于硬判决译码。现代通信使用代数译码的场合较少。6.4.4 卷积码的译码2022/8/164卷积码本质上是一个有限状态机，它的码字前后相关。对于编码器编出的任何码字序列，在网格图上一定可以找到一条连续的路径与之对应，这种连续性正是卷积码码字前后相关的体现。但在译码端，一旦传输、存储过程中出现差错，输入到译码器的接收码字流在网格图上就找不出一条对应的连续路径，而只有若干不确定、断续的路径供作译码参考。而从译码器译出的码字序列必须与编码器一样，也是对应一

4、条连续路径，否则肯定是译码出了差错。在编码理论发展进程中出现了多种以序列为基础的译码方法，如序列译码算法、修改后的Fano算法以及堆栈算法等，但这些都不是最佳译码或最大似然译码。 6.4.4 卷积码的译码2022/8/165卷积码概率译码的基本思路是：以断续的接收码流为基础，逐个计算它与其它所有可能出现的、连续的网格图路径的距离，选出其中可能性（概率）最大的一条作为译码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。在二进制硬判决译码情况下，最大似然就是最小汉明距离；而在二维调制（PSK、QAM）和软判决情况下， 最小距离一般是指最小欧氏（Euclid

5、ean）距离。6.4.4 卷积码的译码2022/8/166当前最实用的卷积码译码算法是维特比(VB) 算法(Viterbi,1967)。小村(Omura，1969)两年后指出：维特比算法等价于在一个加权图上求取最短路径。1973年福尼(Forney)最终证明了维特比算法实质上就是卷积码的最大似然译码。后来Forney又指出，维特比算法不但可用于卷积码译码，也可用于带宽有限、存在严重码间干扰的信道的信号接收，因为码间干扰可看成是由于信道记忆造成的，这种记忆类似于卷积编码器中的寄存器，因而采用维特比算法可以实现信号的最大似然接收。由于最优的特性和相对适中的复杂度，维特比算法在L10的卷积码译码中已

6、成为首选、最普遍采用的算法。6.4.4 卷积码的译码2022/8/167(1) 卷积码的状态定义：卷积码编码器要存储 m 段消息，这些消息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。有效存储单元 M：Mk m状态向量(l)/：(l)=(M(l), M1(l), 2(l),1(l)二元 (n,k,m) 卷积码共有 2M 个不同的状态，记为新的状态(l+1)/转移分支 (l),(l+1)/(, )输入段 U(l)/U输出段 V(l)/V状态转移方程：=(,U)输出方程： V =(,U)6.4.5 卷积码的状态转移图与栅格描述202

7、2/8/168例6.4.10 (2,1,2)码的状态向量为=(21)，共有4种状态S0,S1,S2,S3，如图6.4.13所示。g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111g(1,2)=g0(1,2) g1(1,2) g2(1,2) =1016.4.5 卷积码的状态转移图与栅格描述2022/8/169其状态变化表如表6.4.1所示。 该码的状态转移方程和输出方程分别为 1=U 2=1 V1=U +1+2 V2=U +2 6.4.5 卷积码的状态转移图与栅格描述2022/8/1610其状态转移图如图6.4.14和图5.4.15所示。6.4.5 卷积码的状态转移图与栅格描

8、述2022/8/16116.4.5 卷积码的状态转移图与栅格描述2022/8/1612(2) 卷积码的状态转移图闭合型的状转移态图：直接地描述了卷积编码器在任一时刻的工作状况；开放型的状态转移图：更适合去描述一个特定输入序列的编码过程。6.4.5 卷积码的状态转移图与栅格描述2022/8/1613例6.4.11 (3,2,1)码的状态向量为=(21)，共有4种状态S0,S1,S2,S3，如图6.4.13所示。g(1,1)=g0(1,1) g1(1,1)=11g(1,2)=g0(1,2) g1(1,2)=01g(1,3)=g0(1,3) g1(1,3)=11g(2,1)=g0(2,1) g1(2

9、,1)=01g(2,2)=g0(2,2) g1(2,2)=10g(2,3)=g0(2,3) g1(2,3)=10其状态为 S=(21) S0=(00),S1 =(01),S2 =(10),S3 =(11) V=(V1V2V3) U=(U1U2)6.4.5 卷积码的状态转移图与栅格描述2022/8/1614状态转移方程和输出方程为 1=U1 2= U2 V1=U1+1+2 V2=U2+1 V2=U1+U2+16.4.5 卷积码的状态转移图与栅格描述2022/8/16156.4.5 卷积码的状态转移图与栅格描述2022/8/1616(3) 卷积码的栅格图(篱笆图)状态图不能反映出状态转移与时间的关

10、系栅格图/篱笆图：将开放型的状态转移图按时间顺序级联形成一个栅格图。编码路径：状态序列在栅格图中形成的一条有向路径。当有向路径始于全“0”状态S0，又终于S0时，表明此时编码器又回到全“0”状态，这条始于S0又首次终于S0的路径是一个卷积码码字。6.4.5 卷积码的状态转移图与栅格描述2022/8/1617红实线表示U=0时输入产生的转移分支；黄虚线表示U=1时输入产生的转移分支。6.4.5 卷积码的状态转移图与栅格描述2022/8/16186.4.5 卷积码的状态转移图与栅格描述2022/8/1619(1) 维特比译码的度量(2) 维特比译码和篱笆图(3) 码参数和篱笆图的关系(4) 最大似

11、然译码/最小距离译码(5) 举例说明维特比译码工作原理(6) 总结维特比算法的步骤6.4.6 维特比译码的基本原理2022/8/1620(1) 维特比译码的度量待编码的信息序列M：M=M0, M1, ML1；编码器输入序列的总长度：k(L+m)；后mk个码元全为0编码器输出的码序列C：C=C0, C1,CL1，其中每个子码Ci含有n个码元；经离散无记忆信道(DMC)传输后，译码器接收的序列 R：R=R0, R1,RL1；对于DMC信道：码序列 C 的路径度量 M(R/C)：计算第 l 时刻到达状态 i 的最大似然路径的相似度log p(R/C)；子码 Ci 度量M(Ri/Ci) ：计算第 l

12、时刻接收子码 Ri 相对于各码字的相似度 log p(Ri/Ci)，也称为分支度量。6.4.6 维特比译码的基本原理2022/8/1621(2) 维特比译码和篱笆图在维特比译码中，用状态图和篱笆图描述码的译码比较方便。以(2,1,2)码为例说明 g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111 g(1,2)=g0(1,2) g1(1,2) g2(1,2) =101图6.4.20所示的是(2.1.2)码的篱笆图：它由结点和分支构成。共有8个结点（单元时刻），在图中的上方以0,1,2,7标号，0结点表示第0个时刻。编码器的工作过程：6.4.6 维特比译码的基本原理2022/8

13、/16226.4.6 维特比译码的基本原理2022/8/1623在起始的第0个到第2个时刻内，编码器根据输入的信息元不同从S0状态向四个可能的状态之一行进；本例假定信息序列长为L=5个信息组，最后 m 个信息组是全0，所以在篱笆图上的最后两个时刻向 S0 状态返回；篱笆图上各连续分支组成了可能的路径，它们代表了各种可能的码序列；由于可能的输入信息序列有 2kL=25=32 个，可能的路径有32条；每个分支上的数字表示输出的子码。6.4.6 维特比译码的基本原理2022/8/1624(3) 码参数和篱笆图的关系 对(n,k,m)码而言，编码器的可能状态数目为2km个，进入每个状态的分支数为 2k

14、 个，从每个状态输出的分支数 2k 个，若输入信息序列长为 k(L+m)（后mk个码元全为0），则篱笆图上共有 2kL 条不同的路径，相应于编码器输出的 2kL 个码序列。6.4.6 维特比译码的基本原理2022/8/1625(4) 最大似然译码/最小距离译码译码器接收到 R 序列后，按最大似然法则力图寻找编码器在篱笆图上原来走过的路径，也就是寻找具有最大度量的路径；因此，译码器必须计算 maxM(R/Cj)，j=1,2,2Lk，对BSC信道，就是寻找与 R 有最小距离的路径，即计算和寻找 mind(R, Cj)。译码的实现：6.4.6 维特比译码的基本原理2022/8/1626最大似然译码方

15、法只是提供了一个译码准则，实现起来尚有一定困难。因为它是考虑了长度为 (L+m)n 的接收序列来译码的，这样的序列可能有 2Lk 条；若实际接收序列中，L=50，k=2，则可能的路径有 2100 条。译码器每接收一个序列 R，就要计算 1030 个似然函数才能做出译码判决。若 kL 再大一些，译码器按最大似然译码准则译码将是很困难的。6.4.6 维特比译码的基本原理2022/8/1627(5) 举例说明维特比译码工作原理维特比提出了一种算法：译码器不是在篱笆图上一次就计算和比较 2Lk 条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。维特比译码的基本思想

16、：将接收序列 R 与篱笆图上的路径逐分支地比较，比较的长度一般取 (56)mn，然后留下与 R 距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。幸存路径的数目等于状态数：2km 以 (2,1,2) 非系统码为例说明维特比译码的基本思想：设发送序列 C 为全0；接收序列 R=10,00,01,00,00,00,00,6.4.6 维特比译码的基本原理2022/8/1628假设译码器的初始状态为全0；第0个时刻：接收序列的第0个分支 R0=10 进入译码器。从 S0 状态有两个分支，它们是 00 和 11，R0与这两个分支比较，比较的结果和到达的状态如表

17、6.4.2 所示：每个状态/节点都有两个存储器：路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值 (累加距离)。6.4.6 维特比译码的基本原理2022/8/1629第一个时刻：进入译码器的接收码组 R1=00 和此时刻出发的四条分支比较，比较结果和达到状态如表6.4.3所示：从第一个时刻到第二个时刻：共有四条路径，到达S0, S1, S2和S3。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器存储了此时刻到达该状态的幸存路径累加值 (累加距离)。6.4.6 维特比译码

18、的基本原理2022/8/1630从第二个时刻起：第二个接收码组 R2=01 进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组 R2 与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：6.4.6 维特比译码的基本原理2022/8/1631经过比较后选择：部分路径 000000为到达 S0 状态的幸存路径；部分路径 000011为到达 S1 状态的幸存路径；部分路径 110101为到达 S2 状态的幸存路

19、径；部分路径 001101为到达 S3 状态的幸存路径。按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选择一条幸存路径。在每个状态上进行判决时，可能出现进入这一状态的两条路径的距离值相同，这时可以任选其一，因为对以后的判决而言，无论选择那一条路径，累加距离是相同的。6.4.6 维特比译码的基本原理2022/8/1632对本例而言，按上述算法进行到第十一个分支后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为 (56)mn，所以，维特比译码的延时可达 (56)m 个单位时刻（每个

20、单位时刻为 n 个码元长度）就可以对第0个接收码组的信息元进行判决。依此类推，对接收序列中的诸码组进行译码。维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。篱笆图中共有 2km 个状态，因此，维特比译码的计算量与编码存储 m 成指数关系变化，所以采用维特比算法译码的卷积码，其 m 不能选的太大。6.4.6 维特比译码的基本原理2022/8/16336.4.6 维特比译码的基本原理每个状态以实线表示一条可能的分支，虚线表示另一条可能的分支，括号外为实线分支连接的路径的累积路径值，括号内为虚线分支连接的路径的累积路径值。2022/

21、8/16346.4.6 维特比译码的基本原理2022/8/16356.4.6 维特比译码的基本原理2022/8/16366.4.6 维特比译码的基本原理2022/8/16376.4.6 维特比译码的基本原理2022/8/1638(6) 总结维特比算法的步骤在第 j(j=m)个时刻以前，译码器计算所有的长为 m 个分支的部分路径值，对进入 2km 个状态的每一条部分路径都保留。第 m 个时刻开始，对进入每一个状态的部分路径进行计算，这样的路径有 2k 条，挑选具有最小部分路径值的部分路径为幸存路径，删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。重复第二步的计算、比较和判决过程。若输入

22、接收序列长为 (L+m)k，其中，后 m 段是人为加入的全0段，则译码一直进行到 (L+m) 个时刻为止。若进入某个状态的部分路径中，有两条的部分路径值相等，则可任选其一作为幸存路径。6.4.6 维特比译码的基本原理2022/8/1639硬判决译码器：以最小距离为度量的译码器。它适用于 BSC 信道。软判决译码器：把信道解调器输出的信号进行 Q 电平量化，其中 Q 2，然后再输入到维特比译码器进行译码。充分利用了信道输出信号的有关信息，提高译码的可靠性。它适用于DMC信道。软判决译码器比硬判决译码器可以改进码的性能。在一定信道条件下，用软判决译码器可以获得更小的误码率；或者在同等误码率条件下，获得较高的编码增益。注：离散无记忆信道DMC（Disperse Memory channel） 二进制对称信道BSC（Binary Symmetry Channel），BSC是 DMC的一种特殊情况。6.4.7 软