卷积译码之BCJR算法详细介绍

1974年，Bahl，Cocke，Jelinek和Raviv发明BCJR算法。该算法是一种定义在网格图上用来最大化纠错编码的后验概率，对于迭代的纠错译码非常重要。目前Turbo译码和LDPC均以BCJR算法为原型，进行迭代译码。

snow_wang13804

8800人浏览 · 2022-03-12 23:56:41

snow_wang13804 · 2022-03-12 23:56:41 发布

1、算法概述

1974年，Bahl，Cocke，Jelinek和Raviv发明BCJR算法。该算法是一种定义在网格图上用来最大化纠错编码的后验概率，对于迭代的纠错译码非常重要。

目前Turbo译码和LDPC均以BCJR算法为原型，进行迭代译码。

BCJR算法的计算复杂度大于维特比译码，在信息位等可能情况下更倾向于采用维特比算法。但是，迭代译码过程中，每次迭代时的信息位先验概率都发生变化，BCJR算法的优势就会凸显出来。

1.1 算法介绍

BCJR算法计算后验L值，

$L(U_{L})=ln\left\{\frac{P(U_{L}=+1|r)}{P(U_{L}=-1|r} \right\}$ （1）

称为每个信息位的APP L值，且译码器输出由：

${U_{L}}= \left\{\begin{matrix} +1, L(U_{L})>0 \\ -1, L(U_{L})<0 \end{matrix}\right.$ （2）

给出。在迭代译码中，APP L值可以看成是译码器输出。

首先，引入如下对数域度量：

1）前向度量（forward metric） ${\alpha _{l+1}(s)}$ ：

称为状态s在时刻 l+1 的前向度量

${\alpha _{l+1}(s)}=\sum_{s'\in\sigma _{l}}^{ }\gamma _{l}(s',s) \alpha _{l}(s')$ （3）

2）后向度量（backward recursion） ${\beta _{l}(s')}$ ：

称为状态s'在时刻 l 的后向度量

${\beta _{l}(s')}=\sum_{s\in\sigma _{l+1}}^{ }\gamma _{l}(s',s)\beta _{l+1}(s)$ （4）

3）分支量度（branch metric） $\gamma_{l} (s',s)$ ：

${\gamma _{l}(s',s)}= P(u_{l})P(r_{l}|v_{l})=P(u_{l}){(\sqrt{\frac{E_{s}}{\pi N_{0}}})}^{n}\ast e^{-\frac{E_{s}}{N_{0}}}\left\|r_{l}- v_{l} \right\|^{2}$

（5）

其中， $\left\|r_{l}- v_{l} \right\|^{2}$ 是在时刻 l (经过归一化后）接收分支 $r_{l}$ 和发送分支 $v_{l}$ 的平方欧式距离。但是，若 s' → s 不是有效的状态转移， $P(s | s')$ 和 $\gamma_{l} (s',s)$ 都是零。

经过一系列推导（推导过程略），可将（1）式写为：

$L(U_{L})=ln\left\{\frac{\sum_{(s',s)\in \Sigma _{l^+}}^{}P(s_{l}=s', s_{l+1}=s, r)}{\sum_{(s',s)\in \Sigma _{l^-}}^{}P(s_{l}=s', s_{l+1}=s, r)} \right\}$ （6）

其中， $P(s',s,r)= \beta _{l+1}(s) \ast \gamma _{l}(s',s) \ast \alpha _{l}(s')$ （7）

1.2 参数计算

首先，引入简化运算： $max^{*}(x,y)\equiv ln(e^{x}+e^{y}) = max(x,y)+ln(1+e^{-|x-y|})$

用max函数和计算 $ln(1+e^{-|x-y|})$ 的查找表来代替（计算更困难的）运算 $ln(e^{x}+e^{y})$

（1）前向度量计算：

$\alpha _{l+1}^{*}(s)\equiv ln \alpha _{l+1}(s)= ln \sum_{s'\in \sigma _{l}} \gamma _{l}(s',s)\alpha _{l}(s')$ $= ln \sum_{s'\in \sigma _{l}} e^{[\gamma _{l}^{*}(s',s) +\alpha_{l}^{*}(s')]}$

$= max_{s'\in \sigma _{l}}^{*}[\gamma _{l}^{*}(s',s) + \alpha _{l}^{*}(s')], l=0,1,\cdots K-1$ (7)

（2）后向度量计算

$\large {\color{Blue} \beta _{l}^{*}(s')\equiv ln \beta _{l}(s')= ln \sum_{s\in \sigma _{l+1}} \gamma _{l}(s',s)\beta _{l+1}(s)}$ $\large {\color{Blue} =ln \sum_{s\in \sigma _{l+1}} e^{[\gamma _{l}^{*}(s',s) +\beta_{l+1}^{*}(s)]}}$

$\large {\color{Blue} =max_{s\in \sigma _{l+1}}^{*}[\gamma _{l}^{*}(s',s) + \beta_{l+1}^{*}(s)], l=K-1,K-2,\cdots 0}$ (8)

（3）分支度量计算

$\large \mathbf{{\color{Blue} \gamma _{l}(s',s)\equiv ln \gamma _{l}(s',s)= \left\{\begin{matrix} \frac{u _{l}\ast L _{a}(u _{l})}{2} + \frac{L_{c} }{2} r_{l}\ast v_{l}, l=0,1,\cdots K-1\\ \frac{L_{c} }{2} r_{l}\ast v_{l}, l=h,h+1, \cdots ,K-1\end{matrix}\right.}$ （9）

最终得出，公式（10）如下所示：

$\large \mathbf{{\color{Red} L(u _{l})= max^{*}_{s',s \in \Sigma _{l^{+}}}[\beta _{l+1}^{*}(s)+ \gamma _{l}^{*}(s',s)+ \alpha _{l}^{*}(s') ] - max^{*}_{s',s \in \Sigma _{l^{-}}}[\beta _{l+1}^{*}(s)+ \gamma _{l}^{*}(s',s)+ \alpha _{l}^{*}(s') ]}}$

使用公式（10）计算APP L值 $\large L(u_{l})$ ，对数域量度由公式（7）~ （9）给出。 $\large max^{*}$ 函数算法称为

log-MAP算法，或者对数域BCJR算法。log-MAP由于仅仅使用 $\large max(\cdot )$ 函数和查找表，因此相对易于实现，且比MAP算法有更好的数值稳定性。

1.3 对数域BCJR算法步骤概述

1、采用如下公式初始化前向和后向度量 $\large \alpha _0 ^{*}(s)$ 和 $\large \beta _k ^{*}(s)$ :

$\alpha_0 ^{*}(s)\equiv ln \alpha_0 ^{*}(s)=\left\{\begin{matrix} 0, s=0\\-\infty,s\neq 0 \end {matrix} \right .$ $\beta_k ^{*}(s)\equiv ln \beta_k ^{*}(s)=\left\{\begin{matrix} 0, s=0\\-\infty,s\neq 0 \end {matrix} \right .$