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

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

snow_wang13804

9417人浏览 · 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 .$

2、利用公式（7）计算 $\large \alpha _{l+1}^{*}(s),l=0,1,\cdots K-1$

3、利用公式（8）计算 $\large \beta_{l}^{*}(s'),l=K-1,K-2,\cdots 0$

4、利用公式（9）计算 $\large \gamma _l^{*}(s',s),l=0,1,\cdots K-1$

5、利用公式（10）计算 APP L值 $\large L(u_{l})$ ， $\large l=0,1,\cdots h-1$

6、（可选）采用公式（2）计算硬判决 $\large \hat{u _{l}},l=0,1,\cdots h-1$

2、实例分析

假定信息位先验概率是等可能的， $La(u_{l})=0,l=0,1,2$ ,采用公式（9）计算对数域分支度量如下所示：

前向度量计算如下：

后向度量计算如下：

三个信息位的APP L值计算如下：

得到：BCJR译码器对三个信息位的判断为： $\hat{u}=(+1,+1,-1)$

注：本例题取自《差错控制编码（第二版），林舒著》P378；

实际程序可参考：

BCJR matlab仿真算法https://download.csdn.net/download/snowman898/85022570程序解读可参考：

BCJR matlab程序算法梳理https://blog.csdn.net/snowman898/article/details/123665651

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

实验室无人机平台 Pixhawk 2.4.8 / PX4 v1.9.2

实验室无人机平台组成及使用

开放原子开发者工作坊

数据结构的链式存储结构——链表(一) 链表的初始化（C语言）

链式存储结构链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。初始化我的初始化是从键盘输入数据，只要不输入0就能一直创建新的结点，输入0就是链表结束。并且打印一遍链表。代码实现如下：#i