卷积码的维特比译码.docx

卷积码的维特比译码卷积编码器自身具有网格结构,基于此结构我们给出两种译码算法:Viterbi译码算法和BCJR译码算法。基于某种准则,这两种算法都是最优的。1967年,Viterbi提出了卷积码的Viterbi译码算法,后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路径问题的一个动态规划(DynamicProgramming)解决方案,随后,Forney证明它实际上是最大似然(ML,MaximumLikelihood)译码算法,即译码器选择输出的码字通常使接收序列的条件概率最大化。BCJR算法是1974年提出的,它实际上是最大后验概率(MAP,MaximumAPosterioriprobability)译码算法。这两种算法的最优化目标略有不同:在MAP译码算法中,信息比特错误概率是最小的,而在ML译码算法中,码字错误概率是最小的,但两种译码算法的性能在本质上是相同的。由于Viterbi算法实现更简单,因此在实际应用比较广泛,但在迭代译码应用中,例如逼近Shannon限的Turbo码,常使用BCJR算法。另外,在迭代译码应用中,还有一种Viterbi算法的变种:软输出Viterbi算法(SOVA,Soft-OutputViterbiAlgorithm),它是Hagenauer和Hoeher在1989年提出的。为了理解Viterbi译码算法,我们需要将编码器状态图按时间展开(因为状态图不能反映出时间变化情况),即在每个时间单元用一个分隔开的状态图来表示。例如(3,1,2)非系统前馈编码器,其生成矩阵为:GD=[1+D1+D21+D+D2](1)图1(a)(3,1,2)编码器(b)网格图(h=5)假定信息序列长度为h=5,则网格图包含有h+m+1=8个时间单元,用0到h+m=7来标识,如图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)时,对应的码字如图1(b)中红线所示,v=(111,010,001,110,100,101,011)。在一般的(n,k,v)编码器情况下,信息序列长度K*=kh,离开和进入每个状态都有2k个分支,有2K*个不同路径通过网格图,对应着2K*个码字。假设长度K*=kh的信息序列u=(u0,u1uh-1)被编码成长度为N=n(h+m)的码字v=(v0,v1vh+m+1),在经过一个二进制输入、Q-ary输出的离散无记忆信道(DMC,DiscreteMemorylessChannel)后,接收序列为r=(r0,r1rh+m+1)。也可表示为:u=(u0,u1uK*-1),v=(v0,v1vN-1),r=(r0,r1rN-1),译码器对接收到的序列r进行处理,得到v的估计v。在离散