第五章卷积码的译码算法 001 001 001 010 S 100 100 /000 So 000 /000 0000 2* /000 S 7000 000 0 2 3 6 7 时间单元一 (b) 图5.1(a)(3,1,2)编码器(b)网格图(h=5) 假定信息序列长度为h=5,则网格图包含有h十m+1=8个时间单元，用0到h十m= 7来标识，如图5.1(b)所示。假设编码器总是从全0态S,开始，又回到全0态，前=2 个时间单元对应于编码器开始从S。“启程”，最后m=2个时间单元对应于向S。“返航”。 从图中我们也可以看到，在前m个时间单元或最后m个时间单元，并不是所有状态都会出 现，但在网格图的中央部分，在每个时间单元都会包含所有状态，且在每个状态都有2=2 个分支离开和到达。离开每个状态的上面分支表示输入比特为1（即山=1,1表示第i个时 间单元)，下面的分支表示输入比特为0。每个分支的输出V,由个比特组成，共有2=32 个码字，每个码字都可用网格图中的唯一路径表示，码字长度N=n(h十m)=21。例如当信 息序列为u=(11101)时，对应的码字如图5.1(b)中红线所示，v=(111,010,001, 110,100,101,011)。在一般的(n,k,v)编码器情况下，信息序列长度K*=h,离开和 进入每个状态都有2个分支，有2个不同路径通过网格图，对应着2个码字。 假设长度K*=h的信息序列u=(uo,u1…uh-)被编码成长度为N=n(h+m)的码 字V=(Vo,V1Vh+m-),在经过一个二进制输入、Q-ary输出的离散无记忆信道(DMC, Discrete memoryless Channel)后，接收序列为r=(,…ra+m-i)。也可表示为： u=(4o,4…4x-i),V=(Vo,…Vw-1),r=(,片…w-i),译码器对接收到的序列r进 行处理，得到V的估计氵。在离散无记忆信道情况下，最大似然译码器是按照最大化对数 似然函数logP(rv)作为选择ⅴ的准则。因为对于DMC, rl-)) (5.2) 两边取对数后为： 2 Copyright by周武旸第五章 卷积码的译码算法 2 Copyright by 周武旸 0 S 2 S 3 S 000 0 1 2 3 4 5 6 7 1 S 0 S 0 S 0 S 0 S 000 0 S 0 S 0 S 000 000 000 000 000 1 S 3 S 001 3 S 3 S 001 1 S 1 S 1 S 2 S 2 S 2 S 2 S 001 111 111 111 111 111 011 011 011 011 011 100 100 100 010 010 010 010 110 110 110 110 101 101 101 101 101 时间单元 （b） 图 5.1 （a）（3，1，2）编码器 （b）网格图（h＝5） 假定信息序列长度为 h＝5，则网格图包含有 h＋m＋1＝8 个时间单元，用 0 到 h＋m＝ 7 来标识，如图 5.1（b）所示。假设编码器总是从全 0 态 S0开始，又回到全 0 态，前 m＝2 个时间单元对应于编码器开始从 S0“启程”，最后 m＝2 个时间单元对应于向 S0 “返航”。 从图中我们也可以看到，在前 m 个时间单元或最后 m 个时间单元，并不是所有状态都会出 现，但在网格图的中央部分，在每个时间单元都会包含所有状态，且在每个状态都有 2k ＝2 个分支离开和到达。离开每个状态的上面分支表示输入比特为 1（即 ui＝1，i 表示第 i 个时 间单元），下面的分支表示输入比特为 0。每个分支的输出 vi由 n 个比特组成，共有 2h ＝32 个码字，每个码字都可用网格图中的唯一路径表示，码字长度 N＝n(h＋m)＝21。例如当信 息序列为 u＝（11101）时，对应的码字如图 5.1（b）中红线所示，v＝（111，010，001， 110，100，101，011）。在一般的（n，k，v）编码器情况下，信息序列长度 K*=kh，离开和 进入每个状态都有 2k 个分支，有 * 2K 个不同路径通过网格图，对应着 * 2K 个码字。 假设长度 K kh * = 的信息序列 01 1 (, ) u uu u =  h− 被编码成长度为 N nh m = + ( ) 的码 字 01 1 (, ) = h m+ − v vv v  ，在经过一个二进制输入、Q-ary 输出的离散无记忆信道（DMC， Discrete memoryless Channel ）后， 接 收序列为 01 1 (, ) = h m+ − r rr r  。也可表示为： 0 1 *1 (, ) K uu u u =  − ， 01 1 (, ) N v v = − v v  ， 01 1 (, ) N rr r = − r  ，译码器对接收到的序列 r 进 行处理，得到 v 的估计 vˆ 。在离散无记忆信道情况下，最大似然译码器是按照最大化对数 似然函数log ( | ) P r v 作为选择 vˆ 的准则。因为对于 DMC， 1 1 0 0 (|) ( | ) ( | ) h m N l l l l l l P P Pr v + − − = = rv r v = ∏ ∏= （5.2） 两边取对数后为：