卷积码的译码算法

1 . 第五章 卷积码的译码算法 第五章 卷积码的译码算法 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：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 + D 1 + D 2 1 + D + D 2  （5.1） v (0) u v (1) v (2) （a） 1 Copyright by 周武旸 

2 . 第五章 卷积码的译码算法 S3 001 S3 001 S3 001 S3 110 110 110 110 0 0 0 01 0 01 01 01 S1 S1 S1 S1 S1 10 10 10 10 10 1 1 1 1 1 0 0 0 10 10 10 S2 S2 S2 S2 S2 111 01 01 111 01 01 01 111 111 111 1 1 1 1 1 S0 S0 S0 S0 S0 S0 S0 S0 000 000 000 000 000 000 000 0 1 2 3 4 5 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 态 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 个分支，有 2 K * 个不同路径通过网格图，对应着 2 K * 个码字。 假设长度 K * = kh 的信息序列 u = (u 0 , u1  u h−1 ) 被编码成长度为= N n(h + m) 的码 字 v = ( v 0 , v1  v h + m −1 ) ，在经过一个二进制输入、Q-ary 输出的离散无记忆信道（DMC， Discrete memoryless Channel ） 后 ， 接 收 序 列 为 r = (r0 , r1  rh + m −1 ) 。 也 可 表 示 为 ： u = (u0 , u1  uK *−1 ) ， v = (v0 , v1  v N −1 ) ， r = (r0 , r1  rN −1 ) ，译码器对接收到的序列 r 进 行处理，得到 v 的估计 vˆ 。在离散无记忆信道情况下，最大似然译码器是按照最大化对数 似然函数 log P (r | v ) 作为选择 vˆ 的准则。因为对于 DMC， h + m −1 N −1 = P(r | v ) =l 0=l 0 ∏ = P(rl | v l ) ∏ P(r | v ) l l （5.2） 两边取对数后为： 2 Copyright by 周武旸 

3 . 第五章 卷积码的译码算法 h + m −1 N −1 = log P(r | v ) =l 0=l 0 ∑ = log P(rl | v l ) ∑ log P(r | v ) l l （5.3） 其中 P (rl | vl ) 是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。 对 数 似 然 函 数 log P (r | v ) ， 用 M (r | v ) 表 示 ， 称 为 路 径 度 量 （ path metric ）； log P(rl | v l ) ，称为分支度量（branch metric），用 M (rl | v l ) 表示； log P(rl | vl ) 称为比特 度量（bit metric），用 M (rl | vl ) 表示，这样（5.3）式可写为： h + m −1 N −1 = M (r | v ) =l 0=l 0 ∑ = M (rl | v l ) ∑ M (r | v )l l （5.4） 如果我们只考虑前 t 个分支，则部分路径度量可表示为： t −1 nt −1 = M (r | v ) l l =l 0=l 0 ∑= M (r | v ) ∑ M (r | v ) l l （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ˆ 。 v v 从时间单元 m 到 h，有 2 个幸存路径，每个状态（共有 2 个状态）一个。随后，幸存 路径数就会变少，因为当编码器回到全 0 态时，状态数就会变少。最后，在时间单元 h＋m， 就只有一个状态（即全 0 态） ，因此，也就只有一个幸存路径了，算法中止。 定理 5.1：在 Viterbi 算法中最后的幸存路径 vˆ 是最大似然路径，即 M (r | vˆˆ) ≥ M (r | v ), for v ≠ v （5.6） 从实现的角度看，用正整数度量来表示要比用实际的比特度量表示更方便。比特度量 g(rl | vl ) 可用 c2 [ log P(rl | vl ) + c1 ] 来代替，其中 c1 是任意实数，c2 是任意 M (rl | vl ) = lo P ∑ ∑ N −1 N −1 = 正实数。可证明，如果路径 v 最大化 M (r | v ) = =l 0= M (rl | vl ) l 0 g(rl | vl ) ，则 lo P 3 Copyright by 周武旸 

4 . 第五章 卷积码的译码算法 它也最大化 c2 [ log P (rl | vl ) + c1 ] ，因此可以使用修正的度量，且不影响 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 01 0 1 0. 0.3 0.2 02 0.1 0.2 0.3 12 1 0.4 11 图 5.2 二输入、4-ary 输出 DMC 信道模型 rl rl 11 vl 01 02 12 11 vl 01 02 12 0 -0.4 -0.52 -0.7 -1.0 0 10 8 5 0 1 -1.0 -0.7 -0.52 -0.4 1 0 5 8 10 (a) (b) 图 5.3 度量表 假设图 5.1 中的一个码字在这样的信道中传输，接收到的序列为： r＝（111201，111102，111101，111111，011201，120211，120111） (5.7) 对该序列进行 Viterbi 译码如图 5.4 所示。 4 Copyright by 周武旸 

5 . 第五章 卷积码的译码算法 36 60 70 104 S3 001 S3 001 S 001 S 3 3 110 110 110 110 0 95 0 40 0 01 0 53 76 01 01 18 01 S1 S1 S1 S1 S1 10 10 10 10 10 1 1 1 1 1 33 88 0 66 80 121 0 0 10 10 10 S2 S2 S2 S2 S2 111 01 01 111 111 111 01 01 01 111 1 1 15 43 86 111 124 139 1 1 1 23 S0 S0 S0 S0 S0 S0 S0 S0 000 000 000 000 000 000 000 r＝（111201，111102， 1 11 1 0 1 ， 1 1 1 11 1 ， 0 1 1 2 01 ， 1 2 0 2 1 1 ， 1 2 0 1 1 1 ） 图 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 输出的，此时对数似然函 数为： p log P= (r | v ) d (r, v ) log + N log(1 − p ) （5.9） 1− p p 其中 d (r, v ) 是 r 和 v 之间的 Hamming 距离。由于 log < 0 ，且 N log(1 − p ) 对所有 v 1− p 来说都是一个常数，因此最大似然译码（ max log P (r | v ) ）就是最小化 Hamming 距离 （ min d (r, v ) ）。 h + m −1 N −1 = d (r, v ) =l 0=l 0 ∑ = d (rl , v l ) ∑ d (r , v ) l l （5.10） 因此，当我们将 Viterbi 算法应用到 BSC 信道时， d (rl , v l ) 成为分支度量， d ( rl , vl ) 为 5 Copyright by 周武旸 

6 . 第五章 卷积码的译码算法 比特度量，该算法就是寻找具有最小度量的路径，即与 r 汉明距离最近的路径。该算法运算 仍然相同，只是用 Hamming 距离代替了似然函数作为度量，在每个状态的幸存路径是具有 最小度量的路径。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.2：BSC 信道下的 Viterbi 算法 假设接收到的序列为 r = (110, 110, 110, 111, 010, 101, 101) （5.10） 2 4 6 4 001 001 S3 S3 001 S3 S3 110 110 110 110 0 5 0 3 0 01 0 4 4 01 01 1 01 S1 S1 S1 S1 S1 10 10 10 10 10 1 1 1 1 1 3 7 0 2 5 5 0 0 10 10 10 S2 S2 S2 S2 S2 111 01 01 111 111 111 01 01 01 111 1 1 2 5 3 4 6 7 1 1 1 4 S0 S0 S0 S0 S0 S0 S0 S0 000 000 000 000 000 000 000 r＝（110， 110， 110， 111， 010， 101， 101） 图 5.5 BSC 信道下的 Viterbi 算法 最后的码字判决为： vˆ = (111, 010, 110, 011, 111, 101, 011) （5.11） 它所对应的信息序列为 uˆ = (11001) 。 最后的幸存路径度量值为 7，表示接收序列和判决码字之间有 7 个对应位置不同，而其 他路径所对应的码字和接收序列之间的位置不同数目都要大于 7。在上图中紫色对应的线表 示两条路径度量值相同，此时随便选其中一条就 OK 了。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 现在考虑二进制输入的 AWGN 信道，解调器输出不进行量化，即二值输入、连续输出 2 Es 信道。假设信道输入 0 和 1 用 BPSK 信号 ± cos(2π f 0t ) 表示，其中映射关系 T 1 → + Es ，0 → − Es 。考虑码字 v = (v0 , v1 , , vN −1 ) ，按照映射关系 1 → +1 和 0 → −1 进行取值，即 ±1 ，归一化（用 Es 进行归一化）的接收序列 r = (r0 , r1 , , rN −1 ) 是实际值（未 量化） 。这样在给定发送比特 vl 接收到 rl 的条件概率密度函数（pdf）为： 6 Copyright by 周武旸 

7 . 第五章 卷积码的译码算法  r E −v E ( )  2 exp  −  Es l s l s = p (rl vl ) π N0  N0    （5.12） Es  E 2 = exp  − s ⋅ ( rl − vl )  π N0  N0  其中 N 0 / Es 是噪声的归一化单边 psd。如果信道是无记忆的，发送码字为 v、接收序列为 r 的似然函数为： N −1 N −1 = p (r | v ) ln ∏= M (r v ) ln= p (rl | vl ) l =0 ∑ ln p(r | v ) l =0 l l N −1 E N E = − s N0 ∑ (r − v ) l =0 l l 2 + ln s 2 π N0 N −1 Es N E =− N0 ∑ (r l =0 l 2 − 2rl vl + 1) + ln s 2 π N0 （5.13） (r ) N −1 2 Es Es N E = ∑ (r v ) − N +N + 2 ln s 2 π N0 l l N0 l =0 0 = C1 (r ⋅ v ) + C2 − ( Es / N 0 )(| r |2 + N ) − ( N / 2) ln( Es / π N 0 )  是常数，独立于码 其中 C1 = 2 Es / N 0 和 C2 = 字 v， r ⋅ v 表示接收向量 r 和码字 v 的内积（相关） 。由于 C1 是正数，最大化 r ⋅ v 的网格 路 径（ 码字） 同样也 最大 化对 数似然 函数 ln p (r | v ) 。 对应 于码字 v 的 路径度 量为 M (r | v )= r ⋅ v ， 分 支 度 量 为 M (rl | v l )= rl ⋅ v l= ， l 0,1, , h + m − 1 ， 比 特 度 量 为 M (rl | vl )= = rl ⋅ vl ，l 0,1, , N − 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 都一样，再多的软信息也没用。 7 Copyright by 周武旸 

8 . 第五章 卷积码的译码算法 5.2 卷积码的性能界 我们首先在 BSC 信道中对特定码字分析最大似然（Viterbi）译码的性能，然后再推广 到一般信道。假设发送式（5.1）所示（3，1，2）编码器中的全 0 码字，该编码器的 IOWEF 为： X 7WL3 A(W , X , L) = 1 − XWL(1 + X 2 L) = X 7WL3 1 + XWL(1 + X 2 L) + X 2W 2 L2 (1 + X 2 L2 ) +  （5.14） = X 7WL3 + X 8W 2 L4 + X 9W 3 L5 + X 10 (W 2 L5 + W 4 L6 ) +  即该码包含一个重量为 7 的码字，它经过 3 个分支、由重量为 1 的信息序列产生的，一个重 量为 8 的码字，它经过 4 个分支、由重量为 2 的信息序列产生的，… 如果全 0 路径（正确路径）在 t 时刻与竞争路径（错误路径）的火拼中第一次被删除， 就产生事件错误（第一次） ，如图 5.6 所示。 S1 S2 错误路径 v′ S0 S0 S0 S0 t-3 t-2 t-1 t 时间 正确路径 v 图 5.6 在 t 时刻出现第一次事件错误 错误路径必然是在前面从全 0 态分开、现在又首次回到全 0 态的某个路径，即它必然是码字 WEF A(X)中枚举的一个路径。假设它是重量为 7 的那个路径，则正确路径和错误路径之间 有 7 位比特不同，如果接收序列 r 与错误路径在这 7 个位置处有不少于 4 个是相同的（即在 这 7 个位置至少有 4 个 1） ，就会发生错误事件。如果 BSC 的转移概率为 p，则这个概率为： P7 = P 7个位置至少有个“” 4 1  （5.15） 7 7 = ∑   p e (1 − p )7 −e e=4  e  假设重量为 8 的路径是错误路径，发生第一次事件错误的概率为： 1 8 4 8 8 e =P8   2  4 p (1 − p ) 4 + ∑   p (1 − p ) e =5  e  8− e （5.16） 因为如果正确路径和错误路径的度量值相同，则发生事件错误的概率为 1/2。通常，如 果错误路径的重量为 d，则发生首次错误事件的概率为： 8 Copyright by 周武旸 

9 . 第五章 卷积码的译码算法  d d  e  ∑   p (1 − p ) , d −e d 是奇数 d +1  e  e = Pd =  2 （5.17）  1  d  p d / 2 (1 − p) d / 2 + d  e d  2  d / 2  ∑ d e d −e   p (1 − p) ，是偶数d  = e 2 +1 这样，在 t 时刻发生首次事件错误的概率 Pf ( E , t ) 可用一个界来表示，即为所有这些路径的 错误概率之和，如果将超过 t 个分支的错误路径也包括在内，则这个界（较松）可表示为： ∞ Pf ( E , t ) < ∑ d = d free Ad Pd （5.18） 其中 Ad 是重量为 d 的码字数目（即码字 WEF A(X)中重量为 d 的那一项的因子） 。由于这个 界与 t 无关（在所有时刻都成立） ，上式可写为： ∞ Pf ( E ) < ∑ d = d free Ad Pd （5.19） 对上式还可进一步简化，当 d 是奇数时， d d  =Pd ∑  e  p (1 − p) e d −e e= d +1   2 d  d  d /2 d d  < ∑d +1  e  p (1 − p ) d /2 = p d /2 (1 − p ) d /2 ∑d +1  e  （5.20） e =   e   2 2 d d  < p d / 2 (1 − p ) d / 2 ∑   = 2d p d / 2 (1 − p ) d / 2 e=0  e  d d  【 ∑ e  = 2d 】 e=0   同样可证明，当 d 是偶数时，仍会得到相同的结果。 因此， ∞ ∑ d Pf ( E ) < Ad  2 p (1 − p  （5.21） d = d free ∑ ∞ 对于卷积码，其码字 WEF A( X ) = d = d free Ad X d ，有 Pf ( E ) < A( X = ) |X 2 p (1− p ) （5.21） 最后的译码路径可以和正确路径分开和合并多次，即它可能会包含多个错误事件，如图 5.7 所示。在发生一次或多次错误事件后，在全 0 态进行比较的两条路径都是错误路径，因 为每个路径都至少包含一个以前的错误事件。 9 Copyright by 周武旸 

10 . 第五章 卷积码的译码算法 错误路径 正确路径 图 5.7 多个错误事件 这样，在 t 时刻发生错误事件的概率 P ( E , t ) ≤ Pf ( E , t ) ，由于它在所有时刻都成立，因 此可写为： ∞ ∞ ∑ ∑ d P( E ) < Ad Pd < Ad  2 p (1 − p  = A( X = ) |X 2 p (1− p ) （5.22） =d d= free d d free 由于 p 很小，这个界主要是由其第一项决定的，即自由距离项，因此上式可近似为： d free P( E ) ≈ Ad free  2 p (1 − p  ≈ Ad free 2 d free d free / 2 p （5.23） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.3：对于式（5.1）所示的（3，1，2）编码器， d free = 7 ， Ad free = 1 ，当 p = 10−2 时， 1.28 ×10−5 有： P ( E ) ≈ 27 p 7 / 2 = ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 对式（5.22）表示的事件错误概率界进行修改，就可得到比特错误概率 Pb ( E ) 的界。每 个事件错误概率都会造成多个信息比特错误（错误路径的非 0 比特数） ，因此，如果每个事 件错误概率项 Pd 用重量为 d 的路径上的非 0 信息比特数进行加权（注意：重量为 d 的路径 可能不止一条），我们就可得到信息比特错误数的界，这个界再除以 k（每个时间单元的信 息比特数） ，就可得到 Pb ( E ) 的界，为： ∞ Pb ( E ) < ∑ d = d free Bd Pd （5.24） 其中 Bd 是所有重量为 d 的路径上的非 0 信息比特总数除以每个时间单元的信息比特数 k（即 ∑ ∞ 为比特 WEF B ( X ) = d = d free Bd X d 中重量为 d 的那一项的因子）。这样，利用式（5.20） 和式（5.24），可得： ∞ ∞ ∑ ∑ d Pb ( E ) < Bd Pd < Bd  2 p (1 − p  = B( X = ) |X 2 p (1− p ) （5.25） =d d= free d d free 10 Copyright by 周武旸 

11 . 第五章 卷积码的译码算法 同样，当 p 很小时，上式近似为： d free Pb ( E ) ≈ Bd free  2 p (1 − p  ≈ Bd free 2 d free d free / 2 p （5.26） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.4：对于式（5.1）所示的（3，1，2）编码器， d free = 7 ， Bd free = 1 ，当 p = 10−2 时， 有： Pb ( E ) ≈ 2 p 7 7/2 1.28 ×10−5 ，与事件错误概率相同。这就是说，当 p 很小时，最可能 = 出错的事件是译码成重量为 7 的路径，因此引起一个信息比特错误。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 如果 BSC 是从 AWGN 信道、BPSK 调制、最优相干检测、2-ary 输出量化（硬判决）推 导的，则  2 Es  1 − Es / N 0 =p Q   ≈ e （5.27）  N0  2 1 − x2 / 2 【 Q( x) ≤ e , x ≥ 0】 2 这样【当 p 很小时，信道 SNR 就很大】 − ( d free / 2)( Es / N 0 ) Pb ( E ) ≈ Bd free 2 d free / 2 e （5.28） Es 由于每比特能量 Eb  ，R 是编码速率，这样上式改写为（对于较大 Eb/N0）： R − ( Rd free / 2)( Eb / N 0 ) Pb ( E ) ≈ Bd free 2 d free / 2 e , ( with coding ) （5.29） 如果不使用编码，即 R＝1，Es＝Eb，BSC 转移概率 p 是误比特率 Pb(E)：  2 Eb  1 − Eb / N0 = Pb ( E ) Q   ≈ e , ( without coding ) （5.30）  N0  2 比较式（5.29）和式（5.30），我们可看到，对于给定的 Eb/N0，指数部分相差一个因子 Rd free / 2 ，由于当 Eb/N0 较大时，指数项占主导地位，这个因子（dB 值）称为渐近编码增 11 Copyright by 周武旸 

12 . 第五章 卷积码的译码算法 益（asymptotic coding gain） γ （硬判决情况下） ：  Rd free  γ  10 log10   dB （5.31）  2  注意：当 SNR 变小时，编码增益也变小。实际上，如果 SNR（Eb/N0）降低到编码速率 R 大于信道容量 C 的那个点时，可靠通信已经不可能了，此时未编码系统反而会有更好的性 能。 对于二值输入、Q-ary 输出的 DMC 信道，性能界为： P( E ) < A( X ) | X = D0 （5.32a） Pb ( E ) < B( X ) | X = D0 （5.32b） Q −1 其中 D0  ∑ j =0 P( j | 0 P)( j |1) 是信道转移概率的函数，称为 Bhattacharyya 参数，当 Q＝2 = 时， D0 2 p (1 − p ) ，就是 BSC 信道。 在 二 值 输 入 、 连 续 输 出 的 AWGN 信 道 情 况 下 ， 假 设 发 送 码 字 是 全 0 码 字 v =(−1, −1, , −1)【映射关系 1 → +1 和 0 → −1 】，现在来计算正确路径 v 在 t 时刻首次被 删除的概率 Pd，其中 v 是在与错误路径 v′ （与 v 的 Hamming 距离是 d）的 PK 中“牺牲” 的。因为 Viterbi 算法选择具有最大似然函数值的路径，在 t 时刻首次事件错误概率为： P= d { ( ) Pr M [r | v′]t > M [r | v ]t ( )} = { Pr [r ⋅ v′]t > [r ⋅ v ]t }  t −1 t −1  { } = Pr [r ⋅ v′]t − [r ⋅ v ]t > 0 = Pr ∑ rl ⋅ v′l − ∑ rl ⋅ v l > 0  （5.33） =  l 0=l 0   nt −1 nt −1  = Pr ∑ rl ⋅ vl′ − ∑ rl ⋅ vl > 0  =  l 0=l 0  其中 [r ⋅ v ]t 表示 r 和 v 在前 t 个分支的内积。很显然，上式中只有 d 个位置不为 0，假设 l = 1, 2, , d 表示这些位置，因为 vl′ ≠ vl ， vl′ = +1 ， vl = −1 ，式（5.33）可表示为： d d   d  d  Pd Pr ∑ (+ rl ) − ∑ (−rl ) > = = 0  Pr 2∑ rl > = 0  Pr ∑ rl > 0  （5.34） =  l 1 =l 1 =  l1 = l 1  上式表示如果接收信元的值在 vl′ ≠ vl 的 d 个位置上的累积和为正数，就会在 t 时刻发生首次 错误事件。 由于信道是无记忆的，发送码字 v =(−1, −1, , −1) ， ρ  ∑ d r 是 d 个独立高斯随机 l =1 l 变量的和，每个 rl 是均值为－1、方差为 N0/2Es 的高斯随机变量（见式 5.12） ，这样 ρ 是均 12 Copyright by 周武旸 

13 . 第五章 卷积码的译码算法 值为－d、方差为 N0/2Es 的高斯随机变量，则式（5.34）可写为： Es ( ρ + d ) 2  Es  ∞ − Pd= Pr{ρ > 0}=   ∫0 e dρ dN 0 （5.35）  π dN 0  2 Es y (ρ + d ) 进行变量代换 = ，上式变为： dN 0 2 y y2 1 ∞ − 1 ∞ − =Pd = ∫ 2π + d 2 Es / dN0 e 2 dy 2π ∫ + 2 dEs / N 0 e 2 dy （5.36）  2dEs   2dREb  = Q=   Q    N0   N0  将式（5.36）代入式（5.22）和式（5.25）的界，得到二值输入、连续输出 AWGN 信道 下的事件错误概率和比特错误概率的界，为： ∞  2dREb  P( E ) < ∑ Ad Q  N0  （5.37a） d = d free   ∞  2dREb  Pb ( E ) < ∑ Bd Q  N0  （5.37b） d = d free   1 − x2 / 2 如果用更松的界 Q ( x) ≤ < e− x / 2 , x ≥ 0 ，可得： 2 e 2 ∞ dREb − P( E ) < ∑ d = d free Ad e N0 = A( X ) =X exp( − REb / N0 ) （5.38a） ∞ dREb − Pb ( E ) < ∑ d = d free Bd e N0 = B( X ) =X exp( − REb / N0 ) （5.38b） 比较式（5.38）和式（5.32），我们可知，对于连续输出 AWGN 信道，Bhattacharyya 参 数= D0 exp(− REb / N 0 ) 。 当 Eb / N 0 较大时，在比特 WEF 中的第一项决定了式（5.38b）的界， Pb ( E ) 近似为： − Rd free Eb / N 0 Pb ( E ) ≈ Bd free e （5.39） 此时渐近编码增益（软判决）为： γ  10 log10 ( Rd free ) dB （5.40） 比较式（5.39）、 （5.40）和式（5.29）、（5.31），我们可看到软判决情况比硬判决情况多 出 3dB 增益，这也就意味着为了得到相同的错误概率，在 BSC 信道上传输的发射机的发射 功率是 AWGN 信道下发射功率的 2 倍。 （注：前面的分析是基于对特定码字的性能界，且只 当 Eb / N 0 较大时才有效，当用随机码进行分析且 SNR 较小时，编码增益只有 2dB 左右，所 13 Copyright by 周武旸 

14 . 第五章 卷积码的译码算法 以软判决相对硬判决有 2～3dB 的增益，代价是译码的复杂度增加）。 这个界通过下面的不等式还可以更紧， ( ) ( y )e z − Q y+z ≤Q 2 , ( y > 0, z ≥ 0 ) （5.41） 设 y = 2d free REb / N 0 ， = z 2(d − d free ) REb / N 0 ，式（5.36）可写为：  2dREb  =Pd Q  N =  Q ( y+z )  0   −( ) d − d free REb  2d free REb ≤ Q e N0 （5.42）  N0     2d free REb  d freeNREb − dREb = Q  e 0 e N0  N0    现在定义函数 f ( x) = Q ( ) 2x ex （5.43） 式（5.42）可写为：  d free REb  − dREb Pd ≤ f  e N0 （5.44）  N0  最后，将式（5.44）代入式（5.22）和式（5.25）的界，得到二值输入、连续输出 AWGN 信 道下的事件错误概率和比特错误概率的界，为：  d free REb  − ∞ dREb P( E ) < ∑ Ad f  e N0 d = d free  N0  （5.45a）  d RE  = f  free b  A( X ) =X exp( − REb / N 0 )  N0   d free REb  − ∞ dREb Pb ( E ) < ∑ Bd f  e N0 d = d free  N0  （5.45b）  d RE  = f  free b  B( X ) =X exp( − REb / N 0 )  N0   d free REb  我们从式（5.45）表示的紧界和式（5.38）表示的界可知，紧界有一个因子 f  ，  N 0  该因子只依赖于码字的自由距。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 5.5：计算 AWGN 信道的误比特率界 14 Copyright by 周武旸 

15 . 第五章 卷积码的译码算法 考虑式（5.1）所示（3，1，2）编码器，其 IOWEF A(W, X, L)见式（5.14） ，其比 特 WEF 可计算为： 1 ∂A(W , X ) ∂  X 7W (1 − XW − X 3W )  B( X ) = ⋅ = k ∂W W =1 ∂W W =1 （5.46） X7 = =X 7 + 2 X 8 + 3 X 9 + 6 X 10 +  1− 2X + X 2 − 2X 3 + 2X 4 + X 6 可知，该码的自由距 d free = 7 ，利用上式可直接得到（5.38b）和（5.45b）所示的界， 如图 5.8 所示。 软判决、硬判决时的界以及未编码、编码后的性能比较 0 10 硬判决时的界 软判决时的松界 软判决时的紧界 未编码 -2 10 Viterbi译 码 仿 真 误比特率 -4 10 -6 10 -8 10 0 2 4 6 8 10 12 Eb/N0 (dB) 图 5.8 卷积码的性能界 从上图我们可看出，式（5.45b）表示的紧界和 viterbi 译码仿真非常拟合（SNR>4dB） ，而式 （5.38b）表示的界一直追随着仿真曲线，但不是很靠近。 该码的渐近编码增益（软判决）为： =γ 10 log = 10 ( Rd free ) = 10 log10 ( 7 / 3) 3.68 dB （5.47） 这是与未编码 BPSK 系统性能相比的增益，从上图我们可以看出这一点。 从上面的讨论我们可知，P(E)和 Pb(E)随 dfree 的增加指数下降，随 Ad free 和 Bd free 的增加线性增 加，因此首要准则是最大化自由距离 dfree，第二个准则是最小化 Ad free 和 Bd free 。通常来说， 在高 SNR 时，dfree 起决定作用，在低 SNR 时， Ad free 和 Bd free 起决定作用。 表 5.1 列出了一些最优码： 15 Copyright by 周武旸 

16 . 第五章 卷积码的译码算法 表 5.1(a) R＝1/4 的卷积码 v G(0) g(1) g(2) g(3) dfree Ad free γ (dB) 1 1 1 3 3 6 1 1.76 2 5 5 7 7 10 1 3.98 3 13 13 15 17 13 2 5.12 4 25 27 33 37 16 4 6.02 5 45 53 67 77 18 3 6.53 6 117 127 155 171 20 2 6.99 7 257 311 337 355 22 1 7.40 8 533 575 647 711 24 1 7.78 9 1173 1325 1467 1751 27 3 8.29 表 5.1(b) R＝1/3 的卷积码 v G(0) g(1) g(2) dfree Ad free γ (dB) 1 1 3 3 5 1 2.22 2 5 7 7 8 2 4.26 3 13 15 17 10 3 5.22 4 25 33 37 12 5 6.02 5 47 53 75 13 1 6.36 6 117 127 155 15 3 6.99 7 225 331 367 16 1 7.27 8 575 623 727 18 1 7.78 9 1167 1375 1545 20 3 8.23 10 2325 2731 3747 22 7 8.65 11 5745 6471 7553 24 13 9.03 12 2371 13725 14733 24 5 9.03 表 5.1(c) R＝1/2 的卷积码 v G(0) g(1) dfree Ad free γ (dB) 1 3 1 3 1 1.76 2 5 7 5 1 3.98 3 13 17 6 1 4.77 4 27 31 7 2 5.44 5 53 75 8 1 6.02 6 117 155 10 11 6.99 7 247 371 10 1 6.99 8 561 753 12 11 7.78 9 1131 1537 12 1 7.78 10 2473 3217 14 14 8.45 11 4325 6747 15 14 8.75 12 10627 16765 16 14 9.03 13 27251 37363 16 1 9.03 16 Copyright by 周武旸 

17 . 第五章 卷积码的译码算法 5.3 软输出 Viterbi 算法（SOVA） 5.3.1 SOVA 基本原理 对于卷积码，Viterbi 算法是最优的最大似然译码方法，译码输出为卷积码的最优估计序列。 但对于属于级联卷积码的 Turbo 码而言，传统的 Viterbi 算法存在两个缺陷：首先，一个分 量译码器输出中存在的突发错误会影响另一个分量译码器的译码性能，从而使级联码的性能 下降。其次，无论是软判决 Viterbi 算法还是硬判决 Viterbi 算法，其译码输出均为硬判决信 息，若一个分量码采用 Viterbi 算法译码，则另一个分量译码器只能以硬判决结果作为输入， 无法实现软判决译码，从而性能会有所下降。因此，如果 Viterbi 译码器能够提供软信息输 出，则可以弥补上述两个缺陷，并且可以通过在分量译码器之间软信息的交换使级联码的性 能大大提高。为此，需要在传统的 Viterbi 算法上进行修正，使之提供软信息输出，相应的 算法就称为软输出 Viterbi 算法，记做 SOVA（Soft Output Viterbi Algorithm）。 下面通过具体的实例来说明软输出 Viterbi 算法的软信息的生成。图 5.9 给出了在一个 4 状态网格图实现 SOVA 译码的计算输出软信息的示意图。 S3,t 1 1 11 S3 S3 S3 S3 S3 S3 S3 1 0 M s ( S1,t ) S 1,t 10 S1 S1 S1 S1 S1 S1 S1 0 0 1 1 S 2,t M C ( S1,t ) 1 01 S2 S2 S2 S2 S2 S2 S2 0 1 S0,t 00 S0 S0 S0 S0 S0 S0 S0 t-6 t-5 t-4 t-3 t-2 t-1 t 图 5.9 实现竞争路径和幸存路径可靠性估计的格图 图 5.9 中的实线表示 t 时刻状态结点 S1,t 处的幸存路径(这里假设为最终的最大似然路径的— 部分)，虚线表示 t 时刻状态结点 S1,t 处的竞争路径。为使图看上去清楚一些，就没有画出其 他结点的幸存路径和竞争路径。标记 S1,t 代表 t 时刻的状态 1，标记(0, 1)表示每个分支路径 对应的二元判决值，当前结点时刻的幸存路径对应的累计度量值记为 M S ( S1,t ) ，当前结点 时刻的竞争路径对应的累计度量值记为 M C ( S1,t ) 。指定结点 S1,t 的幸存路径的可靠性度量值 ∆ t ( S1 ) 为上述两个累计度量值之差的绝对值，即 ∆ t ( S= 1) M S ( S1,t ) − M C ( S1,t ) ，这个值越 大，幸存路径是最大似然路径的可能性就越大，判决也越可靠。这里假设幸存路径累计度量 总是优于竞争路径累计度量。后面就将 ∆ t ( S1 ) 称为 t 时刻的 SOVA 译码输出的可靠性值。 17 Copyright by 周武旸 

18 . 第五章 卷积码的译码算法 显然，根据 ∆ t ( S= 1) M S ( S1,t ) − M C ( S1,t ) 计算得到的值可以作为先验信息，辅助下一个分 量译码器进行译码判决。 此外，为降低复杂性，只需要计算最大似然幸存路径的可靠性值(这里假设己知)。而其 他幸存路径没有必要计算可靠性值，随着译码的进行，这些路径逐个被丢弃了。 为说明可靠性的概念，下面给出两个例子。在这些例子中，Viterbi 算法选择累计度量值 小的路径作为幸存路径。 在第一个例子中，状态结点 S1,t 处幸存路径累计度量值为 M S ( S1,t ) = 50 ，竞争路径累计 度量值 M C ( S1,t ) = 100 ，选择这个幸存路径时相应的可靠性值为 ∆ t ( S1 ) =M S ( S1,t ) − M C ( S1,t ) =50 − 100 =50 在第二个例子中，状态结点 S1,t 处幸存路径累计度量值 M S ( S1,t ) = 50 ；竞争路径累计度 量值 M C ( S1,t ) = 75 ，选择这个幸存路径时相应的可靠性值为 ∆ t ( S1 ) = M S ( S1,t ) − M C ( S1,t ) = 50 − 75 = 25 尽管在这两个例子中幸存路径的累计度量值相同，但幸存路径的可靠程度并不同。根据 可靠性度量值的大小可以判定：第一个例子中提供的幸存路径比第二个例子中提供的幸存路 径更可信一些。 图 5.10 说明了使用幸存路径累计度量值与竞争路径累计度量值之差的绝对值作为可靠 性时的示意图。 M s ( S1,t − 4 ) = 10 M s ( S1,t − 2 ) = 50 M C ( S1,t − 4 ) = 20 M C ( S1,t − 2 ) = 75 ∆ t − 4 ( S1 ) =10 ∆ t − 2 ( S1 ) = 25 S3,t 1 1 11 S3 S3 S3 S3 S3 S3 S3 M s ( S1,t ) = 100 1 0 M C ( S1,t ) = 100 S1,t ∆ t ( S1 ) = 0 10 S1 S1 S1 S1 S1 S1 S1 0 0 1 1 S 2,t 1 01 S2 S2 S2 S2 S2 S2 S2 0 1 S0,t 00 S0 S0 S0 S0 S0 S0 S0 t-6 t-5 t-4 t-3 t-2 t-1 t 图 5.10 不同幸存路径和竞争路径外部信息的比较 18 Copyright by 周武旸 

19 . 第五章 卷积码的译码算法 在图 5.10 中，状态的幸存路径和竞争路径在 t－5 时刻的状态结点 S1,t-5 处开始分离，在 t－2 和 t－4 时刻幸存路径和竞争路径得到的比特判决值完全相反，如图中红色所示。为方 便说明，假设在状态结点 S1,t 处竞争路径累计度量值和幸存路径累计度量值相等，且 = M S ( S1,t ) = M C ( S1,t ) 100 。这意味着幸存路径和竞争路径成为最终的最大似然路径的概率 是相等的。此外，类似于图 5.9，还假设在 t－2 和 t－4 时刻幸存路径累计度量值优于竞争 路径的累计度量值。为使图看上去清楚一些，这些时刻的竞争路径没有画出。 从图 5.10 可以看出，t 时刻幸存路径相应的可靠性值为 ∆ t ( S1 ) = 0 。这意味着选择该路 径作为幸存路径没有任何可靠性。在 t－2 和 t－4 时刻，幸存路径相应的可靠性值均大于 0 （ ∆ t − 2 ( S1 ) = 25 ， ∆ t − 4 ( S1 ) = 10 ），这也意味着幸存路径的累计度量值较好。但在 t 时刻， 由于幸存路径和竞争路径具有相同的度量，因此竞争路径也可以是幸存路径。这样，在不降 低幸存路径的相关可靠性情况下，在 t－2 和 t－4 时刻存在完全相反的二元判决。 为改善幸存路径的可靠性值， Hagenauer 等人提出了通过后向跟踪更新可靠性值的方法。 这个更新过程嵌入到 Viterbi 算法中，得到的算法描述如下。 对于格图中的状态结点 Sk,t（相应于 t 时刻的状态 k） ： ①存储可靠性 ∆ t ( S= k) M S ( S k ,t ) − M C ( S k ,t ) ，如果存在不止一条竞争路径对应的可靠 性值，就将最小的一个存储到 ∆ t ( S k ) 。 ②初始化状态 Sk,t 的可靠性值为+∞。 ③比较状态 Sk,t 的幸存路径和竞争路径，并存储反映两个路径的二元判决不同的相对时 刻值到 MEM，即与当前时刻的差值； ④按照下面的步骤更新这些 MEM 处的可靠性值。 ● 找到可靠性值没有更新过、满足 MEM＞0 且值最小的 MEM．记做 MEMlow。 ● 用 MEM＝0 和 MEM＝MEMlow 之间最小的可靠性值来更新 MEMlow 的可靠性值。 继续前面的例子，状态结点 S1,t 处幸存路径和竞争路径之间比特判决相反的位置存储为 MEM＝{2，4}，根据这个 MEM 信息，在图 5.11 和图 5.12 中给出了更新可靠性值的过程。 图 5.11 中给出了第一个可靠性度量值的更新过程。MEM＞0 且未更新可靠性值的最小 MEMlow＝2，在 MEM＝0 和 MEM＝MEMlow＝2 之间最小的可靠性值为 ∆ t ( S1 ) = 0 ，这样相 应的可靠性值就由 ∆ t − 2 ( S1 ) = 25 更新为 ∆ t − 2 ( S1 ) = ∆ t ( S1 ) = 0 。下一个 MEM＞0 且未更新 可靠性值的最小 MEMlow＝4，在 MEM＝0 和 MEM＝MEMlow＝4 之间最小的可靠性值为 ∆ t ( S1 ) = 0 ，这样相应的可靠性值就更新为 ∆ t − 4 ( S1 ) = ∆ t ( S1 ) = 0 。图 5.12 给出了第二个可 靠性值更新的过程。 研究表明，最后的可靠性值在送入下一个分量译码器之前应该经过归一化或者对数化处 理，以减小由于可靠性值更新带来的影响。 19 Copyright by 周武旸 

20 . 第五章 卷积码的译码算法 ∆ t − 4 ( S1 ) = 10 25 更新为∆ t − 2 ( S1 ) = ∆ t − 2 ( S1 ) = 0 ∆ t −3 ( S1 ) S 3,t 1 1 11 S3 S3 S3 S3 S3 S3 S3 ∆ t −5 ( S1 ) 1 0 S1,t ∆ t ( S1 ) = 0 10 S1 S1 S1 S1 S1 S1 S1 0 0 1 1 S 2,t 1 1 01 S2 S2 S2 S2 S2 S2 S2 ∆ t −1 ( S1 ) 0 S0,t 00 S0 S0 S0 S0 S0 S0 S0 t t-6 t-5 t-4 t-3 t-2 t-1 t MEM 6 5 4 3 2 1 0 图 5.11 t－2 时刻路径度量更新过程 10 更新为∆ t − 4 ( S1 ) = ∆ t − 4 ( S1 ) = 0 ∆ t − 2 ( S1 ) = 0 ∆ t −3 ( S1 ) S3,t 1 1 11 S3 S3 S3 S3 S3 S3 S3 ∆ t −5 ( S1 ) 1 0 S1,t ∆ t ( S1 ) = 0 10 S1 S1 S1 S1 S1 S1 S1 0 0 1 1 S 2,t 1 1 01 S2 S2 S2 S2 S2 S2 S2 ∆ t −1 ( S1 ) 0 S0,t 00 S0 S0 S0 S0 S0 S0 S0 t t-6 t-5 t-4 t-3 t-2 t-1 t MEM 6 5 4 3 2 1 0 图 5.12 t－4 时刻路径度量更新过程 5.3.2 SOVA 在级联译码系统，通常一个译码器会将其译码输出的可靠度信息（软输出）传递给第二 个译码器，这样第二个译码器就可以使用软判决译码。能够处理从信道（或另一个译码器） 20 Copyright by 周武旸 

21 . 第五章 卷积码的译码算法 传来的软输入值，并将软输入值传递给另一个译码器，象这种译码器称为软输入软输出 （SISO，Soft-In, Soft-Out）译码器。 软输出 Viterbi 算法（SOVA）是 Hagenauer 和 Hoeher 在 1989 年提出的，我们主要讲解 在二值输入、连续输出 AWGN 信道下编码速率为 R＝1/n 的卷积码的 SOVA。SOVA 的基本 运算与 Viterbi 算法相同，唯一的区别在于对每个信息比特的硬判决输出附加一个可靠度的 指示，这两者（硬判决输出和可靠度指示）组合在一起就是软输出。假设信息比特的先验概 率 为 p= = (ul ), l 0,1, , h − 1 ， 在 t 时 刻 ， 部 分 接 收 序 = 列 为 [r ]t (r0 , r1 , rt −1 ) (r0 (0) , r0(1) , r0( n −1) ; r1(0) , r1(1) , r1( n −1) ; rt (0) ( n −1) −1 , rt −1 , rt −1 (1) ) ，部分路径度量必须最大化（应用 Viterbi 算法）： ( ) { ( M [r | v ]t = ln p [r | v ]t p [ v ]t ) ( )} （5.48） 式（5.48）和式（5.13）的区别就在于包含了先验路径概率 p ([ v ] ) 【因为当信息比特的先 t 验概率不是等概时，先验路径概率也是不等概的】，注意：先验路径概率 p ([ v ] ) 就是相关 t 的信息序列 [u ]t 的先验概率，我们可以将部分路径度量按照 l＝t 时刻和 l < t 时刻分开：   t −1   ( ) M [r | v ]t = ln  ∏ p (rl | v l ) p (ul )  p (rt | v t ) p (ut )    l =0    t −1   n −1  = ln ∏ p (rl | v l ) p (ul )  + ln ∏ p (rt ( j ) | vt( j ) ) p (ut )  （5.49） =  l 0=  j 0   t −1   n −1  = ln ∏ p (rl | v l ) p (ul )  + ∑ ln  p (rt ( j ) | vt( j ) )  + ln [ p (ut )]  l =0   j =0  ( j) 对上式进行修正：将和式中的每一项乘以 2，并引入常数 Cr 和 Cu ，为：  n −1  ∑  2 ln  p (rt | vt )  − Cr  +  2 ln [ p (ut ) ] − Cu   ( j) ( j) ( j) （5.50）  j =0  其中常数 Cr( j ) ≡ ln  p (rt ( j ) | vt( j ) = +1)  + ln  p (rt ( j ) | vt( j ) = −1)  , j = 0,1, n − 1 （5.51a） Cu ≡ ln [ p (ut =+1) ] + ln [ p (ut =−1) ] （5.51b） 是独立于路径 [ v ]t ，这里的映射为 1 → +1 和 0 → −1 。类似地，对式（5.49）中 l < t 时刻的 【注意：这种修正不会影响路径 [ v ]t 的最大化】 每一项也进行修正， ，修正后的度量为： 21 Copyright by 周武旸 

22 . 第五章 卷积码的译码算法 n −1 ( M * [= r | v ]t ) ( ) { } M * [r | v ]t −1 + ∑ 2 ln  p (rt ( j ) | vt( j ) )  − Cr( j ) + {2 ln [ p (ut ) ] − Cu } j =0 （5.52） n −1  p(r ( j ) | v ( j ) = +1)   p (ut ) = +1  =+ ( ) M * [r | v ]t −1 ∑ vt( j ) ln  t ( j ) t( j )  + ut ln   j =0  p (rt | vt = −1)   p (ut ) = −1  我 们 可 以 通 过 定 义 在 二 进 制 输 入 v = ±1 、 未 量 化 信 道 的 输 出 为 r 的 对 数 似 然 率 （Log-likelihood ratio）或 L 值对上式进行简化。  p (r | v = +1)  L(r ) = ln   （5.53）  p (r | v = −1)  类似地，信息比特 u 的 L 值为：  p (u = +1)  L(u ) = ln   （5.54）  p (u = −1)  L 值可解释为对一个二进制随机变量的可靠度测量。例如，假设码比特 v 的先验（未传输前） 概率是等概的，即 p (v =+1) =p (v =−1) =1/ 2 ，【在信息比特是等概的，且码是线性的情 况下，这种假设是成立的】 ，利用 Bayes 准则，式（5.53）可写为：  p(r | v = +1)   p (v = +1| r )  =L(r ) ln=  p(r | v =  ln  （5.55）  −1)  −1| r )   p (v = 从上式可以看出，给定接收信元 r，如果 L(r)是一个大的正值，表示 v = +1 的可靠性较大， 如果 L(r)是一个大的负值，表示 v = −1 的可靠性较大，如果 L(r)是一个接近于 0 的值，表示 只根据 r 来判决 v 值是非常不可靠的。类似地，L(u)也满足这个特性。 对 AWGN 信道，接收到的信元为 r ′ ，二进制输入信元 v′ = ± Es ，SNR 为 Es/N0，可得到： L(r ′) = (4 Es / N 0 )r ′ （5.56a） 将上式重写为： L(r ) = (4 Es / N 0 )r （5.56b） 其中归一化值 r ≡ r ′ Es 对应于输入是 v = ±1 时接收到的信元。式（5.56b）阐明了接收到 的信元 r 的可靠度，它随信道 SNR Es/N0 线性增加。定义 Lc ≡ 4 Es / N 0 为信道可靠度因子， 则 SOVA 译码算法中的修正度量可表示为： n −1 ( ) ( ) M * [r | v ]t = M * [r | v ]t −1 + ∑ Lc vt( j ) rt ( j ) + ut L(ut ) （5.57） j =0 ，而 ut L(ut ) 项在式（5.13）中并没有出现，这是因为前 其中上式中的前 2 项就是式（5.13） 面假设信息比特序列是等概的。由式（5.57）可看出，SOVA 度量中结合了当前时刻之前的 度量值、信道可靠度信息以及先验信息。 22 Copyright by 周武旸 

23 . 第五章 卷积码的译码算法 图 5.13 给出了 SOVA 度量计算中用到的先验信息。 添加 + L(ut ) Sa Sa 添加 − L(ut ) Sb Sb 添加 + L(ut ) t-1时刻 t时刻 图 5.13 SOVA 度量中计算的信息值 在上图中包含了两个状态 Sa 和 Sb 在 t－1 时刻到 t 时刻的状态转移格图，红实线表示输入 ut = +1 时的状态转移分支路径，蓝虚线表示输入 ut = −1 时的状态转移分支路径。先验信息 L(ut ) 可以是正值，也可以是负值，来自于另一个分量译码器，该先验信息结合在 SOVA 度 量中以提供对估计信息比特更可靠的判决度量。 图 5.14 描述了 SOVA 度量的加权特性。 前一时刻的路径度量 信道信息 先验信息 当前时刻的路径度量 图 5.14 SOVA 度量加权示意图 信道可靠性值与先验信息之间的平衡对于 SOVA 度量非常重要，如果信道条件非常好，则 Lc 大于 | L(ut ) | ，这时译码应该主要根据接收的信道值进行；但如果信道条件很差，译码应 该主要根据先验信息 L(ut ) 进行。 前面已经提到 SOVA 算法与 Viterbi 算法非常类似，只是对每个硬判决输出附加了一个 = 可靠度测量因子。假设在状态 Si , i 0,1, 2v − 1 对最大似然路径 [ v ]t 和一个错误路径 [ v′]t 在 l＝t 时刻进行一次比较，定义度量差为： = ∆ t ( Si ) 1 2 { ( ) ( M * [r | v ]t − M * [r | v′]t )} （5.58） 最大似然路径被正确选择的概率 P(C)为： 23 Copyright by 周武旸 

24 . 第五章 卷积码的译码算法 P(C ) = ( p [ v | r ]t ) （5.59） ( ) p [ v | r ]t + p [ v′ | r ]t ( ) 其中 ( p [r | v ]t p [ v ]t ) ( ) 根据式（） ( M [r| v ]t ) ( ) p [ v | r ]t = p (r ) 9.48 e p (r ) （5.60a） ( p [r | v′]t p [ v′]t M ([r| v ′]t ) ) ( ) = ( p [ v′ | r ]t = ) p (r ) e p(r ) （5.60b） 根据式（5.50）中所用的修正方法，我们可写为： = M * ( ) [r | v ]t 2M [r | v ]t − c ( ) （5.61a） = M * ( ) [r | v′]t 2M [r | v′]t − c ( ) （5.61b） 其中 c 是一个不依赖于 [ v ]t 和 [ v′]t 的常数。 利用式（5.60）和式（5.61），式 （5.59）可重写为： ( ) M * [r| v ]t + c ( ) M [r| v ]t 2 e e =P(C ) = M ([r| v ]t ) M ([r| v ′]t ) ( M * [r| v ]t + c ) ( ) M * [r| v ′]t + c e +e e 2 +e 2 （5.62） M * ([r| v ]t ) / 2 e e ∆ t ( Si ) = = M * ([r| v ]t ) / 2 M * ([r| v ′]t ) / 2 e +e 1 + e ∆ t ( Si ) 最后，这个路径判决的对数似然率（可靠度）为：  P(C )  ln   = ∆ t ( Si ) （5.63）  1 − P(C )  现在我们来看看一个路径的可靠度是如何与 Viterbi 译码器的硬判决输出这两者之间有 效联系的。t 时刻某个给定结点的幸存路径可靠度为 ∆ t − MEM ( Si ) ，其中 MEM＝0，1，…，t。 对于 t 时刻的这个状态结点，如果在 MEM＝k 处（相当于 t－MEM 时刻）幸存路径上对应 的信息比特与同时刻竞争路径上的信息比特相同，则选择竞争路径也不会发生比特判决错 误，因此，这个比特位置的可靠度保持不变；但如果在 MEM＝k 处幸存路径和竞争路径相 应的信息比特不同，则会发生比特判决错误，这样就必须用前面讲述的更新过程来更新这个 比特位置的可靠度，如图 5.15 所示，对于 MEM＝2 和 MEM＝4，需要更新可靠度。 可靠度更新过程用于改善译码器软输出值或者似然值，比特判决的软输出或者似然比值 为： MEM L= (uˆˆt − MEM ) ut − MEM ∑∆ k =0 t −k ( Si ) （5.64） 为简化计算，上式可近似为： 24 Copyright by 周武旸 

25 . 第五章 卷积码的译码算法 L(uˆˆt − MEM ) ≈ ut − MEM min k = 0,1,..., MEM {∆t −k ( Si )} （5.65） ∆ t − 4 ( S1 ) ∆ t − 2 ( S1 ) ∆ t −3 ( S1 ) 1 1 11 S3 S3 S3 S3 S3 S3 S3 ∆ t −5 ( S1 ) 1 需要更新 0 M * ([r | v ] ) S t 1,t ∆ t ( S1 ) 10 S1 S1 S1 S1 S1 S1 S1 0 0 1 1 1 ( M * [r | v′]t ) 1 01 S2 S2 S2 S2 S2 S2 S2 ∆ t −1 ( S1 ) 0 00 S0 S0 S0 S0 S0 S0 S0 t t-6 t-5 t-4 t-3 t-2 t-1 t MEM 6 5 4 3 2 1 0 图 5.15 SOVA 的幸存路径和竞争路径度量 综上所述，递归 SOVA 译码器的译码过程（包括可靠度更新过程）如下： （1）（a）初始化时刻 t＝0； （b）对 0 状态初始化度量值为 0，其他状态初始化为∞（算法不同，也可为－∞） 。 （2）（a）tt＋1； （b）对格图中的每个状态按照式（5.57）计算正确路径度量和错误路径度量； （3）为每个状态搜索最小度量值（或最大度量值）。 （4）存储正确路径度量及相应的幸存比特和状态路径； （5）按照式（5.58）计算度量差； （6）比较 t 时刻每个状态处的幸存路径和竞争路径，并存储两条路径上的比特判决不同的 相对时刻值 MEM。 （7）更新所有 MEM 对应的度量值。 （8）返回到步骤（2） ，直到接收到整个传输序列。 （9）输出估计的比特序列 uˆ 和相应的软输出值 L(uˆˆ)= u ⋅ ∆ ，其中 ∆ 为最后更新的可靠度序 列，作为先验信息用于下一轮译码。 5.4 BCJR 算法 给定一个接收序列 r，Viterbi 算法是寻找能够使对数似然函数最大化的码字 v。在 BSC 信道下，这等效为找到一个在 Hamming 距离上与（二进制）接收序列 r 最靠近的（二进制） 码字 v，对于更一般的连续输出的 AWGN 信道，这等效为找到与（实值）接收序列 r 在 25 Copyright by 周武旸 

26 . 第五章 卷积码的译码算法 Euclidean 距离最靠近的（二进制）码字 v，一旦 ML 码字 v 确定了，它所对应的信息序列 u 就是译码输出。 由于 Viterbi 算法是寻找最相似的码字，即最小化 WER Pw ( E ) ，使译码（ML）后的码 字 vˆ 不等于发送码字 v 的概率 p ( vˆ ≠ v | r ) 最小。但在很多情况下，我们希望最小化 BER Pb ( E ) ， 即 在 l 时 刻 译 码 信 息 比 特 uˆl 不 等 于 发 送 比 特 ul 的 概 率 p (uˆl ≠ ul | r ) 最 小 ， =l 0,1, , K * − 1 。 为 了 最 小 化 BER ， 则 一 个 信 息 比 特 ul 被 正 确 译 码 的 后 验 概 率 p (uˆl = ul | r ) 必须最大化。最大化 p (uˆl = ul | r ) 的算法称为最大后验概率（MAP，Maximum A Posteriori）译码器。当信息比特等概时，Viterbi 算法（ML）最大化 p ( vˆ = v | r ) ，虽然它 不能保证 p (uˆl = ul | r ) 也最大化，但 p ( vˆ = v | r ) 和 p (uˆl = ul | r ) 密切相关，Viterbi 算法也 可得到近最优的 BER 性能。 Viterbi 算法最大化 p= ( vˆˆ v = | r) p= (u u | r ) ，其中 uˆ 和 u 是信息序列，分别对应于码 字 vˆ 和 v。这等效为最小化 p (uˆ ≠ u | r ) ，BER 为：  d (uˆ , u)  p (uˆˆl ≠ ul |= r)   p (u ≠ u | r ),=l 0,1, , K * − 1 （5.66）   * K 从上式可看出，BER 依赖于 uˆ 和 u 序列之间的 Hamming 距离【这点与计算 p (uˆ ≠ u | r ) 类 ，因此最小化 p (uˆl ≠ ul | r ) 也涉及到选择编码器具有以下特性：低重量码字对应于低重 似】 量信息序列。这样能够保证最大似然码字错误导致尽量少的比特错误，从而 BER 也就最小 化了。 1974 年，Bahl, Cocke, Jelinek 及 Raviv 引入了 MAP 译码器，称为 BCJR 算法，它能够 应用于任何线性分组码或卷积码，BCJR 的计算复杂度比 Viterbi 算法要高的多，因此在等概 信息比特情况下一般选择 Viterbi 算法。但当信息比特不等概时，MAP 译码能够获得更好的 性能，而且，当使用迭代译码时，每次迭代信息比特的先验概率都会发生改变，此时 MAP 译码器更适合。 我们主要描述编码速率 R＝1/n 的卷积码在二值输入、连续输出 AWGN 信道和 DMC 下的 BCJR 算法（仍然基于前面讲到的对数似然率或 L 值）。译码器输入是接收到的序列 r，信息 比特的先验 L 值为 L= a (ul ), l 0,1, , h − 1 。象在 SOVA 一样，我们不假设信息比特是等概 的。该算法计算后验 L 值为：  p (ul = +1| r )  L(ul ) ≡ ln   （5.67）  p (ul = −1| r )  称为每个信息比特的 APP L 值，译码器输出为： 26 Copyright by 周武旸 

27 . 第五章 卷积码的译码算法 +1 if L(ul ) > 0 =uˆl  = , l 0,1, , h − 1 （5.68）  −1 if L(ul ) < 0 在迭代译码中，APP L 值可作为译码器输出，形成 SISO 译码算法。 我们知道 p (u = +1, r ) ∑ u∈Ul+ p (r | v ) p (u) p (ul = +1| r ) = l = （5.69） p (r ) ∑ u p(r | v) p(u) + 其中 U l 是 ul = +1 的所有信息序列集合，v 是发送的码字对应于信息序列 u， p (r | v ) 是给 定 v 接收序列 r 的 pdf，同样我们可写出 p (ul = −1| r ) 的表达式，这样式（5.67）可写为：  ∑ u∈U+ p (r | v ) p (u)  L(ul ) ≡ ln  l  （5.70）  ∑ u∈Ul− p (r | v ) p (u)  − 其中 U l 是 ul = −1 的所有信息序列集合。MAP 译码可通过式（5.70）计算 APP L 值 L= (ul ), l 0,1, , h − 1 ，然后应用式（5.68）来实现。但这样的计算量非常大。对于具有网 格结构和有限状态的码，如短约束长度的卷积码，利用基于网格图的递归计算能够大大简化 处理过程。 首先，利用码的网格图结构，我们可以将式（5.69）重写为： p (u = +1, r ) ∑ ( s′, s )∈Σl+= p ( sl s= ′, sl +1 s, r ) p (ul = +1| r ) = l = （5.71） p (r ) p (r ) 其中 Σl 表示在 l 时刻状态为 sl = s′ ，l＋1 时刻状态为 sl +1 = s ，这种状态转移是由输入比特 + ul = +1 所引起的，所有这些状态对的集合就构成 Σl+ 。同样我们可写出 p (ul = −1| r ) 的表 达式，这样式（5.67）可写为：  ∑ ( s′, s )∈Σ+= ′, sl +1 s, r )  p ( sl s= L(ul ) = ln  l  （5.72）  ∑ ( s′, s )∈Σl−= ′, sl +1 s, r )  p ( sl s=  − 其中 Σl 表示状态转移对应于输入比特 ul = −1 的集合。 式（5.70）和式（5.72）对 APP L 值 L(ul ) 是等效的，但式（5.70）中的加项涉及到 2h-1 个 信息序列的集合，而式（5.72）中的加项只涉及 2v 个状态对的集合，因此，对较大的 block 长度 h，式（5.72）要简单的多。 现在我们通过递归的方法来推导式（5.72）中的联合 pdf p ( s′, s, r ) ： p ( s′, s, r ) = p ( s′, s, rt <l , rl , rt >l ) （5.73） 其中 rt <l 表示在 l 时刻之前接收到的信息序列 r，rt >l 表示在 l 时刻之后接收到的信息序列 r， 27 Copyright by 周武旸 

28 . 第五章 卷积码的译码算法 应用 Bayes 准则，有 p ( s′, s, r ) = p (rt >l | s′, s, rt <l , rl ) p ( s′, s, rt <l , rl ) = p (rt >l | s′, s, rt <l , rl ) p ( s, rl | s′, rt <l ) p ( s′, rt <l ) （5.74） = p (rt >l | s ) p ( s, rl | s′) p ( s′, rt <l ) 其中最后一个等式是因为在 l 时刻接收到的分支的概率只依赖于 l 时刻的状态和 l 时刻的输 入。 定义： α l ( s′) ≡ p ( s′, rt <l ) （5.75a） γ l ( s′, s ) ≡ p( s, rl | s′) （5.75b） βl +1 ( s ) ≡ p(rt >l | s ) （5.75c） 这样，式（5.74）可写为： p ( s′, s, r ) = βl +1 ( s )γ l ( s′, s )α l ( s′) （5.76） 对于概率 α l +1 ( s ) ，我们可重新将表达式写为： α l +1 ( s ) p= = ( s, rt <l +1 ) ∑ p(s′, s, r s ′∈σ l t <l +1 ) = ∑ p(s, r | s′, r s ′∈σ l l t <l ) p ( s′, rt <l ) （5.77） = ∑ s ′∈σ l p ( s, rl | s′) p ( s′, rt <l ) = ∑ γ (s, s′)α (s′) s ′∈σ l l l 其中 σ l 是在 l 时刻的所有状态的集合。因此，利用前向递归（5.77） ，我们可计算出在 l＋1 时刻、每个状态 s 的前向度量 α l +1 ( s ) 。类似地，我们可写出概率 β l ( s′) 的表达式： βl ( s′) = ∑ γ (s′, s)β s∈σ l +1 l l +1 ( s) （5.78） 其中 σ l +1 式在 l＋1 时刻的所有状态的集合。利用后向递归（5.78） ，我们可计算出在 l 时刻、 每个状态 s′ 的后向度量 β l ( s′) 。在 l＝0 时刻开始的前向递归初始条件为： 1, s = 0 α 0 (s) =  （5.79） 0, s ≠ 0 因 为 编 码 器 是 在 全 0 态 S0 = 0 开 始 的 ， 这 样 可 用 式 （ 5.77 ） 来 递 归 计 算 α l +1 ( s ) ， 28 Copyright by 周武旸 

29 . 第五章 卷积码的译码算法 =l 0,1, , K − 1 ，其中 K＝h＋m 是输入序列长度。类似地，在 l＝K 时刻开始的后向递归， 初始条件为： 1, s = 0 β K (s) =  （5.80） 0, s ≠ 0 因 为 编 码 器 终 止 于 全 0 态 S0 = 0 ， 这 样 可 用 式 （ 5.78 ） 来 递 归 计 算 β l ( s ) ， l =K − 1, K − 2, , 0 。 分支度量 γ l ( s′, s ) 可写为： p ( s′, s, rl ) γ l ( s′, s ) p= = ( s, rl | s′) p ( s′)  p ( s′, s )   p ( s′, s, rl )  =   （5.81）  p ( s′)   p ( s′, s )  ( s | s′) p (rl | s′, s ) p (ul ) p (rl | v l ) = p= 其中 ul 是输入比特， v l 对应于 l 时刻状态转移 s′ → s 的输出比特。对一个连续输出 AWGN 信道，如果 s′ → s 是一个有效的状态转移，则 n  Es  − Ns0 rl − vl 2 E γ l ( s′, s ) p= = (ul ) p (rl | v l ) p (ul )   e （5.82）  π N0  其中 rl − v l 2 表示（用 Es 归一化的）接收分支 rl 和 l 时刻的发送分支 v l 之间的平方欧拉 距离，但如果 s′ → s 不是一个有效的状态转移， p ( s | s′) 和 γ l ( s′, s ) 都为 0。用式（5.72） 、 、以及式（5.77）～（5.80）和（5.82）所定义的度量来计算 APP L 值 L(ul ) 的 式（5.76） 算法，就称为 MAP 算法。 n  Es  对算法进行修改，可大大减少计算复杂度。首先，注意到式（5.82）中有常数项   ，  πN  0  从式（5.76）～（5.78）可知，在概率密度函数 p ( s′, s, r ) 的表达式中该常数项的指数部分增 nh  Es  加了 h 倍，即在式（5.72）的分子和分母中的每一项都有   这个因子，其影响可忽  πN  0  略，因此，简化的分支度量为： Es 2 − rl − vl γ l ( s′, s ) = p(ul )e N0 （5.83） 其次，先验概率 p (ul = ±1) 可写为： 29 Copyright by 周武旸