第五章卷积码的译码算法 log P(r,v,)=log P(r lv N-1 logP(rlv)=】 (5.3) 其中P(:y)是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。 对数似然函数logP(r|v),用M(r|v)表示，称为路径度量(path metric): logP(r,Iv,),称为分支度量(branch metric),用M(cv,)表示：logP(yIy)称为比特 度量(bit metric),用M(yly)表示，这样(5.3)式可写为： V-I (5.4) 如果我们只考虑前t个分支，则部分路径度量可表示为： MrI)=MGIV)=M,I） (5.5) 1-0 1-0 对于接收序列r,Viterbi算法就是通过网格图找到具有最大度量的路径，即最大似然路 径（码字）。在每个时间单元的每个状态，都增加2个分支度量到以前存储的路径度量中（加）： 然后对进入每个状态的所有2个路径度量进行比较（比），选择具有最大度量的路径（选）， 最后存储每个状态的幸存路径及其度量。 Viterbi算法： Stp1:在t=m时间单元开始，计算进入每个状态的单个路径的部分度量，存储每个状 态的路径（幸存）及其度量： Step 2: t←t十1，对进入每个状态的所有2个路径计算部分度量，并加上前一时间单元 的度量。对于每个状态，比较进入该状态的所有2个路径度量，选择具有最大 度量的路径，存储其度量，并删掉其他路径。 Step 3: 如果th+m,返回step2:否则，就停止。 Viterbi算法的基本计算“加、比、选”体现在step2。注：实际工程中，在每个状态存 储（在step1和step2)的是对应于幸存路径的信息序列，而不是幸存路径自身，这样当算 法结束时，就无需再通过估计码字氵来恢复信息序列ǜ。 从时间单元m到h,有2"个幸存路径，每个状态（共有2"个状态）一个。随后，幸存 路径数就会变少，因为当编码器回到全0态时，状态数就会变少。最后，在时间单元h十m, 就只有一个状态（即全0态），因此，也就只有一个幸存路径了，算法中止。 定理5.1：在Viterbi算法中最后的幸存路径是最大似然路径，即 M(r|)≥M(rlv),forv≠v (5.6) 从实现的角度看，用正整数度量来表示要比用实际的比特度量表示更方便。比特度量 M(G|y)=lo(;Iy)可用c2logP(G|y,)+c]来代替，其中c是任意实数，c2是任意 正实数。可证明，如果路径V最大化M(v)=∑MG,)=∑01oG),则 Copyright by周武肠第五章 卷积码的译码算法 3 Copyright by 周武旸 1 1 0 0 log ( | ) log ( | ) log ( | ) h m N l l l l l l P P Pr v + − − = = rv r v = ∑ ∑= （5.3） 其中 (| ) Pr v l l 是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。 对数似然函数 log ( | ) P r v ，用 M (|) r v 表示，称为 路径度量（ path metric ）； log ( | ) P l l r v ，称为分支度量（branch metric），用 (| ) M l l r v 表示；log ( | ) Pr v l l 称为比特 度量（bit metric），用 (| ) Mr v l l 表示，这样（5.3）式可写为： 1 1 0 0 (|) ( | ) ( | ) h m N l l l l l l M M Mr v + − − = = rv r v = ∑ ∑= （5.4） 如果我们只考虑前 t 个分支，则部分路径度量可表示为： 1 1 0 0 (|) ( | ) ( | ) t nt l l l l l l M M Mr v − − = = rv r v = ∑ ∑= （5.5） 对于接收序列 r，Viterbi 算法就是通过网格图找到具有最大度量的路径，即最大似然路 径（码字）。在每个时间单元的每个状态，都增加 2k 个分支度量到以前存储的路径度量中（加）； 然后对进入每个状态的所有 2k个路径度量进行比较（比），选择具有最大度量的路径（选）， 最后存储每个状态的幸存路径及其度量。 Viterbi 算法： Step 1: 在 t＝m 时间单元开始，计算进入每个状态的单个路径的部分度量，存储每个状 态的路径（幸存）及其度量； Step 2: tt＋1，对进入每个状态的所有 2k 个路径计算部分度量，并加上前一时间单元 的度量。对于每个状态，比较进入该状态的所有 2k 个路径度量，选择具有最大 度量的路径，存储其度量，并删掉其他路径。 Step 3: 如果 t<h+m，返回 step 2；否则，就停止。 Viterbi 算法的基本计算“加、比、选”体现在 step 2。注：实际工程中，在每个状态存 储（在 step 1 和 step 2）的是对应于幸存路径的信息序列，而不是幸存路径自身，这样当算 法结束时，就无需再通过估计码字 vˆ 来恢复信息序列uˆ 。 从时间单元 m 到 h，有2v 个幸存路径，每个状态（共有 2v 个状态）一个。随后，幸存 路径数就会变少，因为当编码器回到全 0 态时，状态数就会变少。最后，在时间单元 h＋m， 就只有一个状态（即全 0 态），因此，也就只有一个幸存路径了，算法中止。 定理 5.1：在 Viterbi 算法中最后的幸存路径 vˆ 是最大似然路径，即 M M for ( | ) ( | ), rv rv v v ˆˆ ≥ ≠ （5.6） 从实现的角度看，用正整数度量来表示要比用实际的比特度量表示更方便。比特度量 ( | ) lo g( | ) M r v Pr v l l = l l 可用c Pr v c 2 1 [log ( | ) l l + ]来代替，其中 c1 是任意实数，c2 是任意 正实数。可证明，如果路径 v 最大化 1 1 0 0 ( | ) ( | ) lo g( | ) N N l l l l M l l M r v Pr v − − = = r v = ∑ ∑= ，则