第五章卷积码的译码算法 第五章卷积码的译码算法 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi译码算法和 BCJR译码算法。基于某种准则，这两种算法都是最优的。1967年，Viterbi提出了卷积码的 Viterbi译码算法，后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路径问题的 一个动态规划(Dynamic Programming)解决方案，随后，Forney证明它实际上是最大似然 (ML,Maximum Likelihood)译码算法，即译码器选择输出的码字通常使接收序列的条件 概率最大化。BCJR算法是1974年提出的，它实际上是最大后验概率(MAP,Maximum A Posteriori probability)译码算法。这两种算法的最优化目标略有不同：在MAP译码算法中， 信息比特错误概率是最小的，而在ML译码算法中，码字错误概率是最小的，但两种译码算 法的性能在本质上是相同的。由于Viterbi算法实现更简单，因此在实际应用比较广泛，但 在迭代译码应用中，例如逼近Shannon限的Turbo码，常使用BCJR算法。另外，在迭代译 码应用中，还有一种Viterbi算法的变种：软输出Viterbi算法(SOVA,Soft-Output Viterbi Algorithm),它是Hagenauer和Hoeher在1989年提出的。 5.1 Viterbi算法 为了理解Viterbi译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反 映出时间变化情况)，即在每个时间单元用一个分隔开的状态图来表示。例如(3,1,2)非 系统前馈编码器，其生成矩阵为： G(D)=1+D1+D21+D+D2] (5.1) (a) 1 Copyright by周武旸
第五章 卷积码的译码算法 1 Copyright by 周武旸 第五章 卷积码的译码算法 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi 译码算法和 BCJR 译码算法。基于某种准则，这两种算法都是最优的。1967 年，Viterbi 提出了卷积码的 Viterbi 译码算法，后来 Omura 证明 Viterbi 译码算法等效于在加权图中寻找最优路径问题的 一个动态规划（Dynamic Programming）解决方案，随后，Forney 证明它实际上是最大似然 （ML，Maximum Likelihood）译码算法，即译码器选择输出的码字通常使接收序列的条件 概率最大化。BCJR 算法是 1974 年提出的，它实际上是最大后验概率（MAP，Maximum A Posteriori probability）译码算法。这两种算法的最优化目标略有不同：在 MAP 译码算法中， 信息比特错误概率是最小的，而在 ML 译码算法中，码字错误概率是最小的，但两种译码算 法的性能在本质上是相同的。由于 Viterbi 算法实现更简单，因此在实际应用比较广泛，但 在迭代译码应用中，例如逼近 Shannon 限的 Turbo 码，常使用 BCJR 算法。另外，在迭代译 码应用中，还有一种 Viterbi 算法的变种：软输出 Viterbi 算法（SOVA，Soft-Output Viterbi Algorithm），它是 Hagenauer 和 Hoeher 在 1989 年提出的。 5.1 Viterbi 算法 为了理解 Viterbi 译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反 映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非 系统前馈编码器，其生成矩阵为： 2 2 () 1 1 1 D D D DD =+ + ++ G （5.1） (0) v (1) u v (2) v （a）
第五章卷积码的译码算法 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） 两边取对数后为：
第五章卷积码的译码算法 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: tt＋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 = ∑ ∑= ，则
第五章卷积码的译码算法 它也最大化c2[logP(GIy,)+c],因此可以使用修正的度量，且不影响Viterbi算法的性能。 如果选择©1使最小度量为0，则c2可选择为使所有度量近似为整数。这样，由于用整数来 近似表示度量，Viterbi算法的性能变成了次最优算法，但通过选择c1和c2可使得这种性能 降低非常小。 例5.1：对于二输入、4-ary输出的DMC信道下的Viterbi算法 二输入、4-ary输出的DMC如图5.2所示。该信道的比特度量如图5.3(a)所示（按照 底为10的对数计算)，选择c1=1,c2=17.3,得到整数度量表如图5.3(b)所示。 0.4 01 0 0.3 0 11 图5.2二输入、4-ary输出DMC信道模型 01 02 12 11 01 02 12 11 0 -0.4 -0.52 -0.7 -1.0 0 10 5 0 -1.0 -0.7 -0.52 -0.4 1 0 5 8 10 (a) (b) 图5.3度量表 假设图5.1中的一个码字在这样的信道中传输，接收到的序列为： r=(11l201,1102,11101,111l1,011201,120211,120111) (5.7 对该序列进行Viterbi译码如图5.4所示。 4 Copyright by周武肠
第五章 卷积码的译码算法 4 Copyright by 周武旸 它也最大化c Pr v c 2 1 [log ( | ) l l + ]，因此可以使用修正的度量，且不影响 Viterbi 算法的性能。 如果选择 c1 使最小度量为 0，则 c2 可选择为使所有度量近似为整数。这样，由于用整数来 近似表示度量，Viterbi 算法的性能变成了次最优算法，但通过选择 c1 和 c2可使得这种性能 降低非常小。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.1：对于二输入、4-ary 输出的 DMC 信道下的 Viterbi 算法 二输入、4-ary 输出的 DMC 如图 5.2 所示。该信道的比特度量如图 5.3（a）所示（按照 底为 10 的对数计算），选择 c1＝1，c2＝17.3，得到整数度量表如图 5.3（b）所示。 0.4 0.4 0.2 0.3 0.1 0.3 0.2 0.1 0 1 01 02 11 12 图 5.2 二输入、4-ary 输出 DMC 信道模型 lr l v 01 02 12 11 0 -0.4 1 -0.52 -0.7 -1.0 -1.0 -0.7 -0.52 -0.4 lr l v 01 02 12 11 0 10 1 8 5 0 (a) (b) 0 5 8 10 图 5.3 度量表 假设图 5.1 中的一个码字在这样的信道中传输，接收到的序列为： r＝（111201，111102，111101，111111，011201，120211，120111） (5.7) 对该序列进行 Viterbi 译码如图 5.4 所示
第五章卷积码的译码算法 36 60 70 104 S 001 S 001 001 010 18 4 010 5 010 76 010 95 S S S 0 3 100 6100 8000 88 121 S2 23 43 86 139 000 000 000 000 000 0 000 000 So (11201,11102, 11101,11111, 011201, 120211,1230111) 图5.4DMC信道下的Viterbi算法 每个状态上的数字表示幸存路径的度量，另一个路径就将被删除（绿线部分）。这样最 后的码字（红线部分的输出）判决为： =(111,010,110,011,000,000,000) (5.8) 它对应的输入序列为ù=(11000)。注意：网格图中最后的m=2个分支是清空寄存器 的，不能算作为输入信息序列。 在BSC信道情况下，转移概率为p<12,接收序列r是2-ay输出的，此时对数似然函 数为： log P(r v)=d(r.v)log+N log(1-p) (5.9) 其中dc,)是r和v之间的Hamming距离。由于log P<0,且NIog(1-p)对所有V 来说都是一个常数，因此最大似然译码(max log P(r|v))就是最小化Hamming距离 (mind(r,v))。 N-1 d(r,v)= (5.10) =0 1=0 因此，当我们将Viterbi算法应用到BSC信道时，d(c,V,)成为分支度量，d(,y)为 5 Copyright by周武肠
第五章 卷积码的译码算法 5 Copyright by 周武旸 0 S 2 S 3 S 000 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 r＝（111201，111102， 111101， 111111， 011201， 120211， 120111） 18 36 60 70 104 40 33 15 23 43 86 111 124 139 53 66 76 80 88 95 121 图 5.4 DMC 信道下的 Viterbi 算法 每个状态上的数字表示幸存路径的度量，另一个路径就将被删除（绿线部分）。这样最 后的码字（红线部分的输出）判决为： vˆ = (111,010,110,011,000,000,000) （5.8） 它对应的输入序列为uˆ = (11000)。注意：网格图中最后的 m＝2 个分支是清空寄存器 的，不能算作为输入信息序列。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 在 BSC 信道情况下，转移概率为 p<1/2，接收序列 r 是 2-ary 输出的，此时对数似然函 数为： log ( | ) ( , )log log(1 ) 1 p P d Np p = +− − r v rv （5.9） 其中d(, ) r v 是 r 和 v 之间的 Hamming 距离。由于log 0 1 p p < − ，且 N p log(1 ) − 对所有 v 来说都是一个常数，因此最大似然译码（ max log ( | ) P r v ）就是最小化 Hamming 距离 （ min ( , ) d r v ）。 1 1 0 0 (, ) ( , ) ( , ) h m N l l l l l l d d drv + − − = = rv r v = ∑ ∑= （5.10） 因此，当我们将 Viterbi 算法应用到 BSC 信道时， (, ) l l d r v 成为分支度量， (, ) l l drv 为
第五章卷积码的译码算法 比特度量，该算法就是寻找具有最小度量的路径，即与「汉明距离最近的路径。该算法运算 仍然相同，只是用Hamming距离代替了似然函数作为度量，在每个状态的幸存路径是具有 最小度量的路径。 例5.2：BSC信道下的Viterbi算法 假设接收到的序列为 r=(110,110,110,111,010,101,101) (5.10) 2 4 6 4 001 001 S 001 S 010 3 010 100 00 5 100 5 S2 3 000 000 0 000 S.) 000 000 000 000 r=(110, 110, 110, 111, 010, 101, 101) 图5.5BSC信道下的Viterbi算法 最后的码字判决为： =(111,010,110,011,111,101,011) (5.11) 它所对应的信息序列为ù=(11001)。 最后的幸存路径度量值为7，表示接收序列和判决码字之间有7个对应位置不同，而其 他路径所对应的码字和接收序列之间的位置不同数目都要大于7。在上图中紫色对应的线表 示两条路径度量值相同，此时随便选其中一条就OK了。 现在考虑二进制输入的AWGN信道，解调器输出不进行量化，即二值输入、连续输出 2E, 信道。假设信道输入0和1用BPSK信号± os(2πft)表示，其中映射关系 1→+√E,0→-√E,。考虑码字v=(,,…,yw-),按照映射关系1→+1和0→-1 进行取值，即±1，归化（用√E,进行归一化）的接收序列r=(,,…,-)是实际值（未 量化)。这样在给定发送比特y,接收到n的条件概率密度函数(pdf)为： 6 Copyright by周武旸
第五章 卷积码的译码算法 6 Copyright by 周武旸 比特度量，该算法就是寻找具有最小度量的路径，即与 r 汉明距离最近的路径。该算法运算 仍然相同，只是用 Hamming 距离代替了似然函数作为度量，在每个状态的幸存路径是具有 最小度量的路径。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.2：BSC 信道下的 Viterbi 算法 假设接收到的序列为 r = (110,110,110,111, 010,101,101) （5.10） 0 S 2 S 3 S 000 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 r＝（110， 110， 110， 111， 010， 101， 101） 1 2 4 6 4 3 3 2 4 5 3 4 6 7 4 2 4 5 7 5 5 图 5.5 BSC 信道下的 Viterbi 算法 最后的码字判决为： vˆ = (111, 010,110, 011,111,101, 011) （5.11） 它所对应的信息序列为uˆ = (11001)。 最后的幸存路径度量值为 7，表示接收序列和判决码字之间有 7 个对应位置不同，而其 他路径所对应的码字和接收序列之间的位置不同数目都要大于 7。在上图中紫色对应的线表 示两条路径度量值相同，此时随便选其中一条就 OK 了。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 现在考虑二进制输入的 AWGN 信道，解调器输出不进行量化，即二值输入、连续输出 信道。假设信道输入 0 和 1 用 BPSK 信号 0 2 cos(2 ) Es f t T ± π 表示，其中映射关系 1→ + Es ，0 → − Es 。考虑码字 01 1 (,, , ) N vv v = − v ，按照映射关系1 1 → + 和0 1 → − 进行取值，即±1，归一化（用 Es 进行归一化）的接收序列 01 1 (,, , ) N rr r = − r 是实际值（未 量化）。这样在给定发送比特 vl 接收到 rl 的条件概率密度函数（pdf）为：
第五章卷积码的译码算法 (√E,-E No (5.12) 其中N。/E是噪声的归一化单边psd。如果信道是无记忆的，发送码字为V、接收序列为「 的似然函数为： N- N M(rlv)=Inp(rlv)=In]p(rly)=mp(lv) =0 No 1=0 (5.13) 恶艺m克++是 No T=0 =C(r.v)+C2 其中C,-2E,/N和C2=-[(E,/N)MrP+N)-(N/2)ln(E,/πNo)]是常数，独立于码 字V,rV表示接收向量r和码字V的内积（相关）。由于C,是正数，最大化r·V的网格 路径（码字）同样也最大化对数似然函数np(r|v)。对应于码字v的路径度量为 M(r|v)=rV,分支度量为M(|v,)=rv,,1=0,l,…,h+m-1,比特度量为 M(|)=iy,1=0,1,…,N-1,Viterbi算法就是要找到与接收序列相关值最大的那条 路径（码字）。 对于连续输出AWGN信道，最大化对数似然函数等效为找到与接收序列r欧拉距离最 近的那个码字V,而在B$C信道，最大化对数似然函数等效为找到与接收序列”汉明距离 最近的那个码字V。前面也讨论了，软解调器判决(Q>2)相比硬判决(Q=2)会有性能的 提高，如果将前面例子中的0和02都变为0,1，和12都变为1，则软判决的DMC就变为硬 判决BSC信道（转移概率p=0.3),但经过Viterbi译码后，产生的信息序列不同，对软判 决情况(Q=4),信息序列u=(11000),最后度量值是139：硬判决情况(Q=2),信息 序列u=(11001),而这样的路径在四输出信道中的度量值为135，很显然在软判决情况下 并不是最大似然路径，因为在硬判决情况下它掩盖了软输出的区别，即对硬判决译码器来说， 01和02都一样，再多的软信息也没用。 7 Copyright by周武旸
第五章 卷积码的译码算法 7 Copyright by 周武旸 ( ) ( ) 2 0 0 2 0 0 ( ) exp exp lsls s l l s s l l rE vE E prv N N E E r v N N π π − = − = − ⋅− （5.12） 其中 0 / N Es 是噪声的归一化单边 psd。如果信道是无记忆的，发送码字为 v、接收序列为 r 的似然函数为： ( ) 1 1 0 0 1 2 0 0 0 1 2 0 0 0 1 2 0 0 0 0 1 2 ( ) ln ( | ) ln ( | ) ln ( | ) ( ) ln 2 ( 2 1) ln 2 2 ( ) ln 2 ( ) N N l l l l l l N s s l l l N s s l ll l N s s s l l l M p pr v pr v E E N r v N N E E N r rv N N EE E N rv N NN N C C π π π − − = = − = − = − = = = = =− − + =− − + + = − ++ = ⋅+ ∏ ∑ ∑ ∑ ∑ rv r v r r v （5.13） 其中 1 0 2 / C EN = s 和 2 2 0 0 ( / )(| | ) ( / 2) ln( / ) C EN N N E N =− + − s s π r 是常数，独立于码 字 v，r v⋅ 表示接收向量 r 和码字 v 的内积（相关）。由于 C1是正数，最大化r v⋅ 的网格 路径（码字）同样也最大化对数似然函数 ln ( | ) p r v 。对应于码字 v 的路径度量为 M (|) rv rv = ⋅ ，分支度量为 (| ) M rv rv ll ll = ⋅ ， l hm = +− 0,1, , 1 ，比特度量为 (| ) Mr v r v ll ll = ⋅ ，l N = − 0,1, , 1 ，Viterbi 算法就是要找到与接收序列相关值最大的那条 路径（码字）。 对于连续输出 AWGN 信道，最大化对数似然函数等效为找到与接收序列 r 欧拉距离最 近的那个码字 v，而在 BSC 信道，最大化对数似然函数等效为找到与接收序列 r 汉明距离 最近的那个码字 v。前面也讨论了，软解调器判决（Q>2）相比硬判决（Q＝2）会有性能的 提高，如果将前面例子中的 01和 02都变为 0，11和 12 都变为 1，则软判决的 DMC 就变为硬 判决 BSC 信道（转移概率 p＝0.3），但经过 Viterbi 译码后，产生的信息序列不同，对软判 决情况（Q＝4），信息序列 u＝（11000），最后度量值是 139；硬判决情况（Q＝2），信 息 序列 u＝（11001），而这样的路径在四输出信道中的度量值为 135，很显然在软判决情况下 并不是最大似然路径，因为在硬判决情况下它掩盖了软输出的区别，即对硬判决译码器来说， 01 和 02 都一样，再多的软信息也没用
第五章卷积码的译码算法 5.2卷积码的性能界 我们首先在BSC信道中对特定码字分析最大似然(Viterbi)译码的性能，然后再推广 到一般信道。假设发送式(5.1)所示(3,1,2)编码器中的全0码字，该编码器的IOWEF 为： XWL A(W,X,L)= 1-XWL(1+X2L) =XWr[1+XW(1+X2L)+X2W2L(1+X2L)+…] (5.14) =XWL+x8W2+xW3+XW2+W4L)+... 即该码包含一个重量为7的码字，它经过3个分支、由重量为1的信息序列产生的，一个重 量为8的码字，它经过4个分支、由重量为2的信息序列产生的，… 如果全0路径（正确路径）在t时刻与竞争路径（错误路径）的火拼中第一次被删除， 就产生事件错误（第一次），如图5.6所示。 S 错误路径v S t-3 t-2 t-l 时间》 正确路径V 图5.6在t时刻出现第一次事件错误 错误路径必然是在前面从全0态分开、现在又首次回到全0态的某个路径，即它必然是码字 NEF A(X)中枚举的一个路径。假设它是重量为7的那个路径，则正确路径和错误路径之间 有7位比特不同，如果接收序列与错误路径在这7个位置处有不少于4个是相同的（即在 这7个位置至少有4个1)，就会发生错误事件。如果B$C的转移概率为P,则这个概率为： D=P[7个位置至少有介“1] (5.15) p(1-p)7- 假设重量为8的路径是错误路径，发生第一次事件错误的概率为： p'-p'+ 78 p(1-p)8- (5.16) 因为如果正确路径和错误路径的度量值相同，则发生事件错误的概率为12。通常，如 果错误路径的重量为d,则发生首次错误事件的概率为： 8 Copyright by周武肠
第五章 卷积码的译码算法 8 Copyright by 周武旸 5.2 卷积码的性能界 我们首先在 BSC 信道中对特定码字分析最大似然（Viterbi）译码的性能，然后再推广 到一般信道。假设发送式（5.1）所示（3，1，2）编码器中的全 0 码字，该编码器的 IOWEF 为： 7 3 2 7 3 2 2 22 22 7 3 8 2 4 9 3 5 10 2 5 4 6 ( , ,) 1 (1 ) 1 (1 ) (1 ) ( ) X WL AW X L XWL X L X WL XWL X L X W L X L X WL X W L X W L X W L W L = − + = + ++ + + = + + + ++ （5.14） 即该码包含一个重量为 7 的码字，它经过 3 个分支、由重量为 1 的信息序列产生的，一个重 量为 8 的码字，它经过 4 个分支、由重量为 2 的信息序列产生的，… 如果全 0 路径（正确路径）在 t 时刻与竞争路径（错误路径）的火拼中第一次被删除， 就产生事件错误（第一次），如图 5.6 所示。 0 S 2 S 1 S 0 S 0 S 0 S t-3 t-2 t-1 t 时间 错误路径v′ 正确路径 v 图 5.6 在 t 时刻出现第一次事件错误 错误路径必然是在前面从全 0 态分开、现在又首次回到全 0 态的某个路径，即它必然是码字 WEF A(X)中枚举的一个路径。假设它是重量为 7 的那个路径，则正确路径和错误路径之间 有 7 位比特不同，如果接收序列 r 与错误路径在这 7 个位置处有不少于 4 个是相同的（即在 这 7 个位置至少有 4 个 1），就会发生错误事件。如果 BSC 的转移概率为 p，则这个概率为： 7 7 7 4 7 41 7 (1 ) e e e P P p p e − = = = − ∑ 个位置至少有个“” （5.15） 假设重量为 8 的路径是错误路径，发生第一次事件错误的概率为： 8 4 4 8 8 5 1 8 8 (1 ) (1 ) 2 4 e e e P pp pp e − = = −+ − ∑ （5.16） 因为如果正确路径和错误路径的度量值相同，则发生事件错误的概率为 1/2。通常，如 果错误路径的重量为 d，则发生首次错误事件的概率为：
第五章卷积码的译码算法 d e) p1-p)-e, d是奇数 P1= (5.17) {2-p2p0-是数 这样，在t时刻发生首次事件错误的概率P(E,)可用一个界来表示，即为所有这些路径的 错误概率之和，如果将超过t个分支的错误路径也包括在内，则这个界（较松）可表示为： P(E,)<∑4B (5.18) 其中Aa是重量为d的码字数目（即码字WEFA(X)中重量为d的那一项的因子）。由于这个 界与t无关（在所有时刻都成立)，上式可写为： (5.19) 对上式还可进一步简化，当d是奇数时， -2[8p0-pr -p-p-p (5.20) p0-p =2p2-pn =24】 同样可证明，当d是偶数时，仍会得到相同的结果。 因此， PO2A-可 (5.21) 对于卷积码，其码字WEF4(X)=∑1.AX，有 P,(E)<A(X)儿x=2N- (5.21) 最后的译码路径可以和正确路径分开和合并多次，即它可能会包含多个错误事件，如图 5.7所示。在发生一次或多次错误事件后，在全0态进行比较的两条路径都是错误路径，因 为每个路径都至少包含一个以前的错误事件。 9 Copyright by周武旸
第五章 卷积码的译码算法 9 Copyright by 周武旸 1 2 / 2 / 2 1 2 (1 ) , 1 (1 ) (1 ) 2 / 2 d e de d e d d d d e de d e d p p d e P d d p p pp d d e − + = − = + − = −+ − ∑ ∑ 是奇数 ，是偶数 （5.17） 这样，在 t 时刻发生首次事件错误的概率 ( ,) P Et f 可用一个界来表示，即为所有这些路径的 错误概率之和，如果将超过 t 个分支的错误路径也包括在内，则这个界（较松）可表示为： ( ,) free f d d d d P Et AP ∞ = < ∑ （5.18） 其中 Ad 是重量为 d 的码字数目（即码字 WEF A(X)中重量为 d 的那一项的因子）。由于这个 界与 t 无关（在所有时刻都成立），上式可写为： ( ) free f d d d d P E AP ∞ = < ∑ （5.19） 对上式还可进一步简化，当 d 是奇数时， 1 2 / 2 /2 /2 / 2 1 1 2 2 / 2 / 2 / 2 / 2 0 (1 ) (1 ) (1 ) (1 ) 2 (1 ) d e de d d e d d d dd d d d e e d d d dd d e d P pp e d d pppp e e d pp pp e − + = + + = = = = − < −=− <− = − ∑ ∑ ∑ ∑ （5.20） 【 0 2 d d e d = e = ∑ 】 同样可证明，当 d 是偶数时，仍会得到相同的结果。 因此， ( ) 2 (1 free d f d d d PE A p p ∞ = < − ∑ （5.21） 对于卷积码，其码字 WEF ( ) free d d d d AX AX ∞ = = ∑ ，有 2 (1 ) ( ) ( )| f X pp P E AX = − < （5.21） 最后的译码路径可以和正确路径分开和合并多次，即它可能会包含多个错误事件，如图 5.7 所示。在发生一次或多次错误事件后，在全 0 态进行比较的两条路径都是错误路径，因 为每个路径都至少包含一个以前的错误事件
第五章卷积码的译码算法 错误路径 正确路径 图5.7多个错误事件 这样，在t时刻发生错误事件的概率P(E,t)≤P(E,),由于它在所有时刻都成立，因 此可写为： PE)<∑A4,B<∑A,[2VPI-p]=A(X)x-m (5.22) =d d=ds 由于p很小，这个界主要是由其第一项决定的，即自由距离项，因此上式可近似为： P(E)A 2p-pp (5.23) 例5.3：对于式(5.1)所示的(3,1,2)编码器，de=7,A=1,当p=102时， 有：P(E)≈2p2=1.28x10- 对式(522)表示的事件错误概率界进行修改，就可得到比特错误概率P,(E)的界。每 个事件错误概率都会造成多个信息比特错误（错误路径的非0比特数），因此，如果每个事 件错误概率项P用重量为d的路径上的非0信息比特数进行加权（注意：重量为d的路径 可能不止一条)，我们就可得到信息比特错误数的界，这个界再除以k(每个时间单元的信 息比特数)，就可得到P(E)的界，为： F.(E)<B,P (5.24) d=d pree 其中B是所有重量为d的路径上的非0信息比特总数除以每个时间单元的信息比特数k(即 为比特WEFB(X)=∑1dB,X中重量为d的那一项的因子)。这样，利用式(520) 和式(5.24)，可得： E2B<2a[a0-可=0m (525) 10 Copyright by周武肠
第五章 卷积码的译码算法 10 Copyright by 周武旸 错误路径 正确路径 图 5.7 多个错误事件 这样，在 t 时刻发生错误事件的概率 ( ,) ( ,) PEt P Et ≤ f ，由于它在所有时刻都成立，因 此可写为： 2 (1 ) ( ) 2 (1 ( ) | free free d d d d X pp d d d d PE AP A p p AX ∞ ∞ = − = = < < −= ∑ ∑ （5.22） 由于 p 很小，这个界主要是由其第一项决定的，即自由距离项，因此上式可近似为： / 2 ( ) 2 (1 2 free free free free free d d d PE A p p A p d d ≈ −≈ （5.23） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.3：对于式（5.1）所示的（3，1，2）编码器， 7 free d = ， 1 free Ad = ，当 2 p 10− = 时， 有： 7 7/2 5 PE p ( ) 2 1.28 10− ≈ =× ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 对式（5.22）表示的事件错误概率界进行修改，就可得到比特错误概率 ( ) P E b 的界。每 个事件错误概率都会造成多个信息比特错误（错误路径的非 0 比特数），因此，如果每个事 件错误概率项 Pd 用重量为 d 的路径上的非 0 信息比特数进行加权（注意：重量为 d 的路径 可能不止一条），我们就可得到信息比特错误数的界，这个界再除以 k（每个时间单元的信 息比特数），就可得到 ( ) P E b 的界，为： ( ) free b d d d d P E BP ∞ = < ∑ （5.24） 其中 Bd是所有重量为 d 的路径上的非 0 信息比特总数除以每个时间单元的信息比特数 k（即 为比特 WEF ( ) free d d d d BX BX ∞ = = ∑ 中重量为 d 的那一项的因子）。这样，利用式（5.20） 和式（5.24），可得： 2 (1 ) ( ) 2 (1 ( ) | free free d b d d d X pp d d d d P E BP B p p BX ∞ ∞ = − = = < < −= ∑ ∑ （5.25）
