第五章卷积码的译码算法 第五章卷积码的译码算法 卷积编码器自身具有网格结构,基于此结构我们给出两种译码算法: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)