2.6 卷积码_5G移动通信中的信道编码-QQ阅读男频历史网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.6 卷积码

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

卷积码的编码器是有记忆的，在一定的时间内，编码器的输出不仅取决于该时刻的输入，也与一定数量以前的输入相关。考虑一个码率为R=k/n的卷积编码器。在卷积编码中，信息序列u被划分为长度为k的数据帧，在每一个时刻，一个k比特长的数据帧被作为信息序列送入卷积编码器，相应的输出是n比特的编码序列，k和n通常是比较小的整数并且k ＜n。每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-1→Sk，计算该转移分支的度量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≤k≤N。这里N表示网格图长度，如果没有结尾（termination）处理，则有N=K。然后编码符号和用BPSK调制，得到在信道上传输的发送符号xs和xp。

图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)，其中uk和ck分别是对应状态转移Sk-1→ Sk的信息符号和编码符号。连接状态Sk-1=s′∈S和Sk=s∈S的所有平行分支组成的集合记为Bk(s′, s)。根据贝叶斯准则，后验概率可以表示为

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

概率中的序列y可写为

其中，表示接收序列y在t到ℓ时刻内的子序列。

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

其中

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

② 是后向状态度量。

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

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

图2.20 状态转移与分支度量

定义

为从Sk-1=s′到Sk=s的状态转移概率。如果在网格图中存在从Sk-1=s′到Sk=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-1→ Sk发生的概率，该数值为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的增加，某些状态度量的数值将小到几乎可以忽略不计，这将由于精确性的限制造成错误。考虑如下的求和算式时，该现象就显而易见。