5G移动通信中的信道编码
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人

2.6 卷积码

2.6.1 卷积码的概念与网格图表示

卷积码的编码器是有记忆的,在一定的时间内,编码器的输出不仅取决于该时刻的输入,也与一定数量以前的输入相关。考虑一个码率为R=k/n的卷积编码器。在卷积编码中,信息序列u被划分为长度为k的数据帧,在每一个时刻,一个k比特长的数据帧被作为信息序列送入卷积编码器,相应的输出是n比特的编码序列,kn通常是比较小的整数并且kn。每n-比特的编码输出块不仅依赖于当前时刻的k-比特输入序列,也依赖于m个以前输入的k-比特序列。参数m称为存储级数,ν=m+1称为卷积码的约束长度。该卷积码通常记为(n, k, ν)或(n, k, m)卷积码。

图2.7给出了一个存储级数m=2、码率R=1/2的卷积码编码器。这个编码器有k=1路输入,n=2路输出,称为(2,1,2)卷积码。由于模2和是线性运算,因此编码器是线性系统。它由下面两个生成序列所定义

g(1)=(101), g(2)=(111)

图2.7 存储级数m=2、码率R=1/2的卷积码编码器

根据图2.7所示,信息序列表示为u=(u0, u1, · · ·)。编码器的两个输出序列表示为

由于编码器可以看作线性系统,输出序列可以由输入序列和编码器的两个冲击响应卷积得到,并且g(1)g(2)就是编码器的两个冲激响应,由u=δ=(100 · · ·)得到。冲激响应至多持续m+1个时间单位,且可写为

g(1)g(2)被称为编码器的生成序列,它描述了编码器中移位寄存器的连接关系。令u=(u0, u1, · · ·)是编码器输入信息序列,则两个编码输出序列为

其中“*”表示卷积运算。

t时刻,输入是单个比特ut,相应的输出是两比特组成的一个码组(block)(, ),其中

输出码字是。例如,对于输入u=(1011100 · · ·),码字c=(11,01,00,10,01,10,11, · · ·)。

将生成序列交织,重新排列可得到如下时域生成矩阵。

编码方程可以重写成矩阵的形式:c=uG

描述卷积码的方法有很多,除了上面从生成矩阵方面描述,也可以从卷积码的多项式、状态图和网格图等方面描述。

(1)卷积码的多项式表示:在线性系统中,卷积的时域运算可以以一种更方便的形式表示,即多项式乘法的变换域运算。编码输出的每个序列可以用多项式表示,相应的编码方程为

c(1)(D)=u(D)g(1)(D)

c(2)(D)=u(D)g(2)(D)

其中信息序列为

u(D)=u0+u1D+u2D2· · ·

编码序列为

码的生成多项式为

对于图2.7所示的卷积码,生成矩阵表示为

(2)状态图:因为编码器是一个线性时序电路,所以可以用状态转移图来描述其行为。我们用t时刻记忆单元中存储的消息比特来表示t时刻的编码器状态。上述例子中(2,1,2)卷积编码器有两个记忆单元,因此共有4种可能的状态,其状态转移图如图2.8所示。图中的状态被定义为编码器电路中两个记忆单元的值(从左至右读取),边上的标记为“输入/输出”。

图2.8 (2,1,2)卷积编码器的状态图

(3)网格图:将状态图在时间轴上展开,就会清晰看到卷积编码器随时间的状态转移,这个在时间上扩展开的状态图就称为网格图(trellis diagram)。具体在图示中,网格图是在水平方向上加上离散时间维度的状态图。上述(2,1,2)卷积码的网格图如图2.9所示。

图2.9 (2,1,2)卷积码的网格图及编码路径

编码器从00状态开始,在t≥2时的网格,本质上是状态图的复制。可以看到网格图给出了所有可能的编码路径,消息序列u的编码等价于在网格图上追踪一条路径。网格图是描述卷积码编码器的一种重要方法,它对于描述卷积码的译码算法也是非常方便的。

2.6.2 卷积码的最大似然译码:Viterbi算法

考虑一个卷积编码的数字通信系统,如图2.10所示。

图2.10 卷积编码的通信系统框图

假定使用(n0, k0, m)卷积码C, m为编码器的存储单元个数(存储级数)。输入信息序列长度为L段(K=k0L个比特):

编完信息比特并添加尾比特后,输出码字c的长度为N=n0(L+m)比特:c=(c1, c2, · · ·, cL+m), 。在网格图上,每个码字是从全0状态出发经过不同分支,最后回到全0状态的一条网格路径,称为编码路径。作为一个例子,图2.11所示卷积编码器的网格图及编码路径如图2.12所示。

图2.11 (2,1,2)卷积编码器

图2.12 (2,1,2)卷积编码器的网格图

假定经过编码信道传输,与发送码字c对应的接收序列是r=(r1, r2, · · ·, rL+m)。对于BSC信道,。对于AWGN信道,假定采用BPSK调制,每一编码符号被映射为发送信号,接收信号,其中是独立同分布的高斯噪声序列。这样,软判决译码器的输入序列r=x+n,其中x=M(c)=(-1)c

ML译码器选择使P(r|c)最大的c作为译码输出:

对于无记忆信道,有

在对数域上,用对数似然函数表示为

M(rk|ck)=log P(rk|ck)表示分支度量。一条网格路径的前t个分支的累积度量(或称为部分路径度量)定义为

对于AWGN信道(或BSC),最大似然度量P(r|c)等价于最小Euclidean距离度量||r-M(c)||2(或Hamming距离度量dH(r, c))。因此,AWGN信道下的最佳译码准则简化为

因此,对于软判决译码器,网格图上的状态转移分支度量定义为

对于硬判决译码器,网格分支度量定义为

Viterbi译码算法在网格图上通过递归处理方式寻找最大似然路径。它首先计算k时刻的接收信号rk与进入状态Sk的所有网格分支之间的Hamming(或Euclidean)距离,并将它作为分支度量;然后计算进入状态Sk的所有网格路径的度量并进行比较,存储有最佳度量的那条网格路径及其度量,剪掉其余的(不可能成为ML选择的那些)网格路径。译码器对k时刻的所有状态进行这种选择。这样,在时刻k,对每一状态Sk,确定了一条从时刻0的全0状态出发而到达Sk的最佳路径,称为幸存路径。如图2.13所示,其中Γ(Sk=s)表示k时刻到达状态Sk=s的幸存路径的累积度量(或称为状态度量)。

图2.13 Viterbi译码器路径度量计算

具体地说,k时刻的幸存者按照下列“加―比(较)―选(择)”运算从k-1时刻的幸存者中确定。

(1)对状态转移Sk-1Sk,计算该转移分支的度量M(rk|ck),并与k-1时刻的幸存路径度量Γ(Sk-1)相加,得到k时刻的一个候选路径度量。

(2)对k时刻的每一个状态,比较到达该状态的候选路径度量,选择最小距离(或最大似然)度量所对应的路径作为幸存路径,并存储它的转移路径历史(从时刻k=1开始)及其度量Γ(Sk)。

在最后时刻(L+m),有一个唯一状态,它的幸存路径一定是结尾网格图上的最短路径。

例2.3 考虑图2.11中的(2,1,2)卷积码。发送序列为c=(11,01,01,00,10,11),接收序列为r=(11,11,00,00,10,11)。Viterbi译码器选择幸存路径的过程如图2.14 ~图2.17所示,图中状态转移分支边上的标号为Hamming距离,状态度量Γi等于该状态的幸存路径累积度量。

图2.14 k=5时刻的幸存路径

图2.15 修剪不可能路径后k=5时刻的幸存路径

图2.16 k=6时刻的幸存路径

图2.17 最终选择的幸存路径

2.6.3 卷积码的逐符号MAP译码:BCJR算法

1974年,Bahl、Cocke、Jelinek和Raviv提出了一种最大后验概率(MAP)算法[28],用于估计噪声中一个Markov源的状态转移的后验概率,这个算法后来就被称为BCJR算法。论文中也展示了该算法如何用来译分组码和卷积码。用于译卷积码时,BCJR算法能够最小化误比特率,即BCJR算法在最小化BER意义下是最佳的;而Viterbi算法是最小化码字错误概率(在网格图上译码器选择不正确路径的概率)。另外,BCJR算法不仅能提供比特序列估计值,而且能够给出每个比特被正确译码的概率,这也是Turbo迭代译码的基础。因此,BCJR算法经常用于需要软信息输出的译码器/检测器,如Turbo译码器和Turbo均衡器等。

在本节中,我们经常使用贝叶斯(Bayes)规则,它简述为

P(u, v)=P(u|v)P(v)

贝叶斯规则的一个直接结果是

P(u, v|w)=P(u|v, w)P(v|w)

下面具体介绍卷积码的逐符号MAP译码算法。考虑图2.18所示的系统模型。令u=(u1, u2, · · ·, uK), uk∈{0,1},是输入信息序列,它用码率为1/2的(系统或非系统)卷积编码器进行编码,生成编码符号序列c=(c1, c2, · · ·, cN),其中,1≤kN。这里N表示网格图长度,如果没有结尾(termination)处理,则有N=K。然后编码符号用BPSK调制,得到在信道上传输的发送符号xsxp

图2.18 卷积编码通信系统模型

对于图2.18所示的信道模型,接收序列

N个符号对组成,其中

式中,Es为每发送符号的平均能量;为信道衰落因子,对于AWGN信道,;对于Rayleigh衰落信道,为两个Reyleigh随机变量。为两个独立同分布的高斯噪声样值,它们的均值为0,方差

根据逐比特最大后验概率准则,译码器输出由下式得到:

这里P(uk|y)是信息比特uk在接收到序列y的情况下的后验概率。

BCJR算法就是工作在网格图上的一种高效MAP算法。为后面使用算法方便起见,考虑图2.19所示的软输入软输出(SISO)MAP译码器,它能为每一个译码比特提供对数似然比输出。

图2.19 软输入软输出译码器框图

图2.19中MAP译码器的输入La(uk)是关于uk的先验信息,L(uk)是关于uk的对数后验概率(APP)比。它们的定义为

MAP译码器的任务就是求解式(2.44),然后按照下列规则进行判决。

下面利用BCJR算法对式(2.44)的计算方法进行推导。

假定卷积编码器有m个记忆单元(存储级数为m),约束长度ν=m+1。令Sk=(ak, ak-1, · · ·, ak-m+1)是k时刻编码器的状态。编码器的状态集合用S表示,状态数为M=|S|=2m

在网格图上第k时刻的状态转移分支可以表示为bk≜(Sk-1, uk, ck, Sk),其中ukck分别是对应状态转移Sk-1Sk的信息符号和编码符号。连接状态Sk-1=s∈SSk=s∈S的所有平行分支组成的集合记为Bk(s, s)。根据贝叶斯准则,后验概率可以表示为

其中,是由输入uk=i引起的状态转移Sk-1Sk的集合。故式(2.44)可表示为

概率中的序列y可写为

其中,表示接收序列yt时刻内的子序列。

应用贝叶斯准则,对进行分解,可得

其中

称为前向状态度量,由k时刻译码器状态Sk=s和接收序列共同决定。

是后向状态度量。

是输入为uk=i时连接状态Sk-1=sSk=s的分支度量。

式(2.47)遵循译码器的Markov性,即如果已知Sk=s,则时刻k之后发生的事件独立于到达Sk之前的序列

图2.20 状态转移与分支度量

定义

为从Sk-1=sSk=s的状态转移概率。如果在网格图中存在从Sk-1=sSk=s的平行转移分支,则γk(s, s)的数值为所有对应平行分支度量的总和。将式(2.48)代入式(2.46),得到

下面来求αk(s)、βk(s)和γk(s, s)。根据定义,αk(s)项可通过递归计算。

其中初始值为α0(s)=P(S0=s)。

类似地,βk(s)可以通过如下的后向递归计算。

边界条件为βN(s)=P(SN=s)。

分支度量可进一步分解为

其中,P(uk=i)是uk的先验概率,P(Sk=s|Sk-1=s, uk=i)是在输入为uk=i的条件下,状态转移Sk-1Sk发生的概率,该数值为1或0。p(yk|ck) ≜p(yk|Sk=s, Sk-1=s, uk=i)是在给定特定分支的情况下,接收到yk的概率,由信道转移概率确定。对于无记忆AWGN信道,可由下式计算得到

其中Ak是独立于编码比特的常数。如前所述,令

为信道的可靠性度量。则式(2.54)可写为

因此

至此,如果将式(2.50)分子、分母中的约掉,L(uk)的求解已基本完成。然而,由于式(2.56)是从连续随机变量的概率密度计算得到,γk(s, s)的值可能大于1,这会使得式(2.51)、式(2.52)产生上溢出,导致整个算法不稳定。另外,由于下列原因,也可能导致下溢出:随着k的增加,某些状态度量的数值将小到几乎可以忽略不计,这将由于精确性的限制造成错误。考虑如下的求和算式时,该现象就显而易见。

接收到特定序列的概率,将随着时刻k的增加而变得非常小。

因此,有必要对αk(s)和βk(s)进行归一化处理。令

因为,所以

将式(2.51)代入式(2.60),并且分子分母同除以,得到

对于,考虑到,于是有

合并式(2.48)和式(2.59)得

将上式代入式(2.46),并且分子分母同乘以因子,便得最终计算公式为

这样就完成了分量码的MAP译码算法的推导。的递推运算示意图如图2.21所示,其中αk(0)=αk-1(0)γk(0,0)+αk-1(1)γk(1,0), βk(0)=βk+1(0)γk+1(0,0)+βk+1(2)γk+1(0,2)。的初始条件为(假定RSC编码器的初始状态为零状态)

图2.21 的递推计算示意图

如果编码器在每帧编码完成之后通过结尾(termination)处理也回到零状态,那么递推的初始条件为

否则,应设定为

注意:MAP算法也通常被称为BCJR算法或前后向递归算法,与隐马尔可夫模型(hidden Markov models)中的Baum-Welch算法等价。

MAP算法可归结如下。

(1)初始化:

α0(0)=1, α0(∀s=0)=0;

βN(0)=1, βN(∀s=0)=0。

(2)前向递归:对于k=1到N,做如下操作。

①对i=0、1,参照式(2.57)计算并存储分支度量

②对sS,参照式(2.61)计算并存储前向度量αk(s)。

(3)后向递归:对于k=N-1到0,做如下操作。

参照式(2.62),使用前向递归中计算得到的分支度量值,计算并存储后向度量βk(s), ∀sS

(4)输出:对于k=1到K,参照式(2.63)计算并输出软信息L(uk)。

2.6.4 Max-Log-MAP译码算法

1.对数域上的简化运算

如果译码器运行在对数域上,则上述最大后验概率(MAP)算法中涉及的计算将会得到简化。定义

如果xy,可将其写为

max*(x, y)=ln[ex(1+ey-x)]=x+ln(1+ey-x)

考虑一般情况,有

其中,fc(|x-y|)=ln(1+e-|x-y|)是一个修正函数。实际应用时,可以通过查表实现。

这可以推广到多个变量的情况。例如,对于一个实数集合{δ1, δ2, · · ·, δq},有

这表明ln(eδ1+eδ2+· · ·+eδq)可以通过递归计算得到,记为

max*(δ1, δ2, · · ·, δq)=max*(max*((max*(max*(δ1, δ2), δ3), · · ·), δq-1), δq)

2.Max-Log-MAP算法

Max-Log-MAP算法是基于前文所述MAP算法的次优简化算法,旨在误码率和译码计算复杂度上取得有效的折中。

Max-Log-MAP算法使用了以下的Max-Log近似。

在该近似下,有下面的推导。对于式(2.61),可得

这里

以及

由此,式(2.61)的前向递归在对数域可以表示为

或者

类似地,式(2.62)后向状态度量可以表示为

等效地

显然,该前后向状态度量可以通过递归计算得到,初始条件为

A0(0)=0, A0(s)=-∞,s=0

BN(0)=0, BN(s)=-∞,s=0

类似地,式(2.63)的最终对数后验概率比可以近似为

这意味着通过执行“加―比(较)―选(择)―减”操作便可实现译码功能。

从上述讨论可以看出,Max-Log-MAP算法与双向Viterbi算法等价。如果将max函数用max*代替,就可得到Log-MAP算法。