第五章卷积码的译码算法 比特度量，该算法就是寻找具有最小度量的路径，即与「汉明距离最近的路径。该算法运算 仍然相同，只是用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）