资源描述
精选优质文档-倾情为你奉上卷积码的维特比译码卷积编码器自身具有网格结构,基于此结构我们给出两种译码算法: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 年提出的。为了理解 Viterbi 译码算法,我们需要将编码器状态图按时间展开(因为状态图不能反映出时间变化情况),即在每个时间单元用一个分隔开的状态图来表示。例如(3,1,2)非系统前馈编码器,其生成矩阵为: GD=1+D1+D21+D+D2 (1)图1 (a)(3,1,2)编码器 (b)网格图(h5) 假定信息序列长度为 h5,则网格图包含有 hm18 个时间单元,用 0 到 hm 7 来标识,如图1(b)所示。假设编码器总是从全 0 态 S0 开始,又回到全 0 态,前 m2 个时间单元对应于编码器开始从 S0“启程”,最后 m2 个时间单元对应于向 S0 “返航”。从图中我们也可以看到,在前 m 个时间单元或最后 m 个时间单元,并不是所有状态都会出现,但在网格图的中央部分,在每个时间单元都会包含所有状态,且在每个状态都有 2k2 个分支离开和到达。离开每个状态的上面分支表示输入比特为 1(即 ui1,i 表示第 i 个时间单元),下面的分支表示输入比特为 0。每个分支的输出vi 由 n 个比特组成,共有 2h32 个码字,每个码字都可用网格图中的唯一路径表示,码字长度 Nn(hm)21。例如当信息序列为u(11101)时,对应的码字如图1(b)中红线所示,v(111,010,001, 110,100,101,011)。在一般的(n,k,v)编码器情况下,信息序列长度 K*=kh,离开和进入每个状态都有 2k 个分支,有2K* 个不同路径通过网格图,对应着2K* 个码字。假设长度K*=kh的信息序列u=(u0,u1 uh-1) 被编码成长度为 N=n(h+m) 的码字v=(v0, v1 vh+m+1) ,在经过一个二进制输入、Q-ary 输出的离散无记忆信道(DMC, Discrete Memoryless Channel )后,接收序列为r=(r0 ,r1 rh+m+1)。也可表示为: u=(u0 ,u1 uK*-1) ,v=(v0 ,v1 vN-1),r=(r0,r1 rN-1),译码器对接收到的序列r进行处理,得到 v 的估计v。在离散无记忆信道情况下,最大似然译码器是按照最大化对数似然函数log P(r | v) 作为选择v的准则。因为对于 DMC, Prv=l=0h+m-1Prlvl=l=0N-1Prlvl (2)两边取对数后为: logPrv=l=0h+m-1logPrlvl=l=0N-1logPrlvl (3)其中P(rl | vl )是信道转移概率,当所有码字等概时,这是个最小错误概率译码准则。对数似然函数 log P(r | v) ,用 M(r |v )表示,称为路径度量(path metric);log P(rl | vl ) ,称为分支度量(branch metric),用M(rl | vl ) 表示;log P(rl | vl ) 称为比特度量(bit metric),用M(rl | vl )表示,这样(3)式可写为: M(r|v)=l=0h+m-1M(rl | vl )=l=0N-1M(rl | vl ) (4)如果我们只考虑前 t 个分支,则部分路径度量可表示为: M(r|v)=l=0t-1M(rl | vl )=l=0nt-1M(rl | vl ) (5)对于接收序列r,Viterbi 算法就是通过网格图找到具有最大度量的路径,即最大似然路径(码字)。在每个时间单元的每个状态,都增加2k个分支度量到以前存储的路径度量中(加);然后对进入每个状态的所有 2k 个路径度量进行比较(比),选择具有最大度量的路径(选),最后存储每个状态的幸存路径及其度量。 Viterbi 算法: Step 1: 在 tm 时间单元开始,计算进入每个状态的单个路径的部分度量,存储每个状态的路径(幸存)及其度量; Step 2: tt1,对进入每个状态的所有 2k 个路径计算部分度量,并加上前一时间单元的度量。对于每个状态,比较进入该状态的所有 2k 个路径度量,选择具有最大度量的路径,存储其度量,并删掉其他路径。 Step 3: 如果 th+m,返回 step 2;否则,就停止。 Viterbi 算法的基本计算“加、比、选”体现在 step 2。注:实际工程中,在每个状态存储(在 step 1 和 step 2)的是对应于幸存路径的信息序列,而不是幸存路径自身,这样当算法结束时,就无需再通过估计码字v 来恢复信息序列u 。从时间单元 m 到 h,有2v 个幸存路径,每个状态(共有 2v 个状态)一个。随后,幸存路径数就会变少,因为当编码器回到全 0 态时,状态数就会变少。最后,在时间单元 hm,就只有一个状态(即全 0 态),因此,也就只有一个幸存路径了,算法中止。定理1:在 Viterbi 算法中最后的幸存路径v 是最大似然路径,即 MrvMrv, for vv (6)从实现的角度看,用正整数度量来表示要比用实际的比特度量表示更方便。比特度量M(rl | vl )=log P(rl | vl )可用c2log P(rl | vl )+c1来代替,其中 c1 是任意实数,c2 是任意正实数。可证明,如果路径 v 最大化M(r|v)=l=0N-1M(rl | vl )=l=0N-1logPrlvl,则它也最大化c2log P(rl | vl )+c1,因此可以使用修正的度量,且不影响 Viterbi 算法的性能。如果选择 c1 使最小度量为 0,则 c2 可选择为使所有度量近似为整数。这样,由于用整数来近似表示度量,Viterbi 算法的性能变成了次最优算法,但通过选择 c1 和 c2 可使得这种性能降低非常小。 例1:对于二输入、4-ary 输出的 DMC 信道下的 Viterbi 算法 二输入、4-ary 输出的 DMC 如图2 所示。该信道的比特度量如图3(a)所示(按照底为 10 的对数计算),选择 c11,c217.3,得到整数度量表如图3(b)所示。 0.40.40.20.30.10.30.2 0.1 0 1 01 02 11 12 图2 二输入、4-ary 输出 DMC 信道模型 l rl v 01021211l r l v010212110-0.4-0.52-0.7-1.001085011.0-0.7-0.52-0.4105810(a) (b) 图3 度量表 假设图1 中的一个码字在这样的信道中传输,接收到的序列为: r(,) (7)对该序列进行 Viterbi 译码如图4 所示。每个状态上的数字表示幸存路径的度量,另一个路径就将被删除(绿线部分)。这样最后的码字(红线部分的输出)判决为: v=(111,010,110,011,000,000,000) (5.8)它对应的输入序列为u=(11000)。注意:网格图中最后的 m2 个分支是清空寄存器的,不能算作为输入信息序列。图4 DMC 信道下的 Viterbi 算法在 BSC 信道情况下,转移概率为 p1/2,接收序列r是 2-ary 输出的,此时对数似然函数为:log P(r | v) = d(r, v) log p/(1-p) + N log(1-p) (9)其中d(r, v) 是r和v之间的 Hamming 距离。由于log p/(1-p)0,且N log(1 - p) 对所有v来说都是一个常数,因此最大似然译码( max log P(r | v) )就是最小化 Hamming 距离( min d(r, v) )。 d(r|v)=l=0h+m-1d(rl | vl )=l=0N-1d(rl | vl ) (10)因此,当我们将 Viterbi 算法应用到 BSC 信道时,d(rl , vl ) 成为分支度量,d(rl ,vl )为比特度量,该算法就是寻找具有最小度量的路径,即与r汉明距离最近的路径。该算法运算仍然相同,只是用 Hamming 距离代替了似然函数作为度量,在每个状态的幸存路径是具有最小度量的路径。专心-专注-专业
展开阅读全文