«上一篇
文章快速检索     高级检索
下一篇»
  应用科技  2017, Vol. 44 Issue (6): 32-35  DOI: 10.11991/yykj.201608012
0

引用本文  

刘彤, 孟祥雨. 基于BEC故障模型下的极化码SC译码算法研究[J]. 应用科技, 2017, 44(6), 32-35. DOI: 10.11991/yykj.201608012.
LIU Tong, MENG Xiangyu. Research on polar codes SC decoding algorithm based on BEC fault model[J]. Applied Science and Technology, 2017, 44(6), 32-35. DOI: 10.11991/yykj.201608012.

基金项目

国家自然科学基金项目(61301200);中央高校基础研究基金项目(HEUCFD1509)

通信作者

孟祥雨,E-mail:17703646643@163.com

作者简介

刘彤(1978−),男,副教授,博士;
孟祥雨(1991−),男,硕士研究生

文章历史

收稿日期:2016-08-24
网络出版日期:2017-04-01
基于BEC故障模型下的极化码SC译码算法研究
刘彤, 孟祥雨    
哈尔滨工程大学 信息与通信工程学院,黑龙江 哈尔滨 150001
摘要:为减少在实际的硬件实现过程中极化码连续删除(SC)译码由于自身硬件因素引发的译码错误,构造了一个简单的基于二进制删除信道(BEC)的故障模型,在该模型下在任何码元速率下都不可能实现完全可靠的通信。针对此故障模型,提出了一种非均匀错误保护方案,并通过仿真验证,表明该方案在可忽略的硬件开销的情况下,显著地改善了连续删除译码在故障二进制删除模型下的译码性能。
关键词极化码    连续删除    译码    硬件    二进制删除信道    非均匀    错误保护    故障模型    
Research on polar codes SC decoding algorithm based on BEC fault model
LIU Tong, MENG Xiangyu    
College of Information and Communication, Harbin Engineering University, Harbin150001, China
Abstract: In order to reduce the decoding errors caused by hardware factors about polar codes successive cancellation (SC) in the process of actual hardware implementation, a simple fault model based on the binary erasure channel (BEC) was built. In this model, it is impossible to achieve complete and reliable communications at any rate. For this fault module, a non-uniform error protection scheme was proposed, and the simulation shows that the scheme can be ignored in hardware cost, which significantly improves decoding performance of successive cancellation decoding by the fault binary erasure model.
Key words: polar codes    successive cancellation    decoding    hardware    binary erasure channel    non-uniform    error protection    fault model    

目前,集成电路正在迈向纳米时代,保证门电路的动作正确变得越来越困难,硬件问题将会导致数据的处理和存储的故障。传统纠错方法是采用较大的晶体管或电路级的纠错码,但是在空间和功耗上开销较大。目前,许多应用程序本质上在硬件故障时有一定的容错能力,根据数据在噪声信道中已有的概率性, 这些程序很好地应用在了无线通信系统当中[1]

典型的电路级纠错码低密度奇偶校验码(low density parity check code,LDPC)的迭代译码算法最先出现在文献[2]中,文中提出了和−积算法和Gallager(A)算法,在这之后,针对上述算法提出了Gallager(B)[3-4]算法和最小和算法[5-6]。之前的研究均提出了LDPC码在各种译码算法和故障模型下的局限性,得出了当译码本身出现故障时,不能实现完全可靠的通信。

极化码是一种基于信道极化现象并且第一次被证明容量可达的编码方法[7]。极化码不仅具有较低的编码和译码复杂度,还具有规则一致的编译码结构,因此极化码能够以相同的编码器和译码器结构,以1 bit为变化步长,支持不同长度的输入和输出,从而可以获得更高的编码增益。目前已经有学者研究指出极化码能够实现在较低复杂度下的高吞吐率的译码,Claude在文献[8]中指出极化码的译码器的最高吞吐率可以达到237 Gbps。

为了在未来的通信中达到对移动互联网体验的突破性进展,并支持物联网发展,这就需要具有高吞吐率、低复杂度和低误码率的信道编码技术,而极化码具有这些优势,对极化码的研究能够有力地推动未来通信技术的发展。在正在研究的5G通信技术中,华为通信公司已经将极化码作为一项关键的信道编码技术展开研究,并且已经取得了重要的进展[9]

文中首先对极化码基本理论进行了分析,然后构造了一个简单的二进制删除信道(binary erasure channel,BEC)故障模型,并在该模型下对极化码连续删除译码算法进行深入的研究。最后研究了非均匀错误保护方案。仿真结果表明该方案能有效地克服硬件因素导致的连续删除(successive cancellation,SC)译码错误,同时当码长足够长时,译码结果无限接近无错误理想SC译码器。

1 极化码 1.1 极化码的构造

W表示一个二进制输入离散无记忆信道,输入 $u \in \left\{ {0,1} \right\}$ ,输出 $y \in \gamma $ ,信道转移概率表示为 $W\left( {y|u} \right)$ 。极化码的构造首先是N个独立的二进制离散信道W联合生成信道WN(其中N=2nn为大于0的整数),然后再进行信道分裂,把WN分裂回N个二进制输入信道 $W_N^{\left( i \right)}$ (其中 $1 \leqslant i \leqslant N$ ),经过联合分裂操作后,子信道与原来信道相比,在总的信道容量不变情况下,子信道的信道容量会出现变化:一部分子信道的对称信道容量增大,另一部分子信道的对称信道容量减小。当N趋近于无穷时,一部分信道的容量将会趋近于1(通过该部分子信道传输的信息比特一定会被正确接收,即为无噪信道);而其余信道将会趋近于0(这种信道不适合传递信息,即纯噪信道),这一现象称作信道极化现象。在信道极化的基础之上,选择一部分信道容量趋近于1的信道去传输信息比特ui $i = 1,2, \cdots ,N$ ,而剩下的信道上用以传送收双方已知的冻结比特[10]

1.2 极化码连续删除译码算法

SC译码算法对于通信系统来说至关重要,直接影响着整个系统的通信质量。SC译码算法是Arikan最早提出来的译码算法,是极化码最为经典和最适合极化码特性的译码方法。

冻结信道标记为 $ A^C$ ,非冻结信道集合定义为A。译码器通过设置 ${u_{{A^c}}}$ 产生一个矢量 $\mathit{\boldsymbol{u}}_1^N$ 等于已知的冻结比特的值,uA自由选择。一个码字由 $x_1^N = \mathit{\boldsymbol{u}}_1^N{\mathit{\boldsymbol{G}}_N}$ ( ${\mathit{\boldsymbol{G}}_N}$ 是生成矩阵)。SC译码算法根据 $y_1^N$ 估算u1,记做 ${u_1}^\prime $ 。同样的u2 $(y_1^N,{u_1}^\prime )$ 估算等,取 $W_N^{(i)}(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.)$ 的对数似然比为

$L(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.) \buildrel \Delta \over = \displaystyle\frac{{W_N^{(i)}(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right. = 0)}}{{W_N^{(i)}(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i} = 1} \right.)}}$

估计值根据

${u_i}^\prime = \left\{ \begin{aligned}\,\,& 0, \quad {\rm{ }}L(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.) > 0\;\;{\rm{and}}\;i \in A\\\,\,&1, \quad {\rm{ }}L(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.) > 0\;\;\;{\rm{and}}\;i \in A\\\,\,&{u_i}, \quad \quad \quad i \in {A^C}\end{aligned} \right.$

如果 $L(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.) = 0$ ,则译码器失败。为了估算每一个 $L(y_1^N,{u^\prime }_1^{i - 1}\left| {{u_i}} \right.)$ ,信道的似然比信息:

${\rm{LLRs = }}\log \frac{{W\left( {{y_i}|{x_i} = 0} \right)}}{{W\left( {{y_i}|{x_i} = 1} \right)}}$

每个节点有2个输入LLRs即m1m2,一个输出的LLR即m

对于第一部分的节点有

$m = {m_1} + {( - 1)^{{u_s}^\prime }}{m_2}$

式中 ${u_S}^\prime $ 是一个部分和,通常是一些已经译码出的码字和。

对于第二部分节点有

$m = 2{\tanh ^{ - 1}}(\tanh ({m_1}/2)\tanh ({m_2}/2))$

称第一部分节点为变量节点,第二部分节点为校验节点。SC译码能大大地简化二进制擦除信道。全部信息属于下面3种情况 $\left\{ { - \infty ,0,{\rm{ + }}\infty } \right\}$ ,符号0标识擦除。对于校验节点,更新规则包含收到消息的标识;对于变量节点,更新规则变成简单的加法即 ${\rm{ + }}\infty {\rm{ - }}\infty {\rm{ = - }}\infty {\rm{ + }}\infty {\rm{ = }}0$

2 故障SC译码 2.1 信息传递

根据文献[11]可知,当2个擦除概率为ε的独立的信息发送到初始变量节点时,输出的信息为

${T^ + }(\varepsilon ) \buildrel \Delta \over = {\varepsilon ^2}$ (1)

同理,校验节点的输出信息为

${T^ - }(\varepsilon ) \buildrel \Delta \over = 1 - {(1 - \varepsilon )^2} = 2\varepsilon - {\varepsilon ^2}$ (2)

由式(1)、(2)得译码过程中各节点间传递的擦除概率 ${\varepsilon _{j + 1}}$ 过程为

${\varepsilon _{j + 1}} = \left\{ \begin{array}{l}{T^ + }({\varepsilon _j})\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2,\\{T^ - }({\varepsilon _j})\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2.\end{array} \right.$

式中:译码的初始层 ${\varepsilon _{(0)}}$ 等于BEC的擦除概率p ${\varepsilon _{(\infty )}} \in \left\{ {0,1} \right\}$

2.2 故障模型与信息传递

假设的故障模型中的译码错误是由于译码器中加性擦除造成的,这可能是由错误的信息处理或者不正确的信息存储造成的,并且这种现象只可能发生在信息尚未完全擦除之前。消息的值等于+∞和−∞是独立等概率发生的,发生概率 $\delta \in \left\{ {0,1} \right\}$ ,因此对于变量节点全部的擦除概率为

$T_\delta ^ + (\varepsilon ){\rm{ = }}{\varepsilon ^2} + (1 - {\varepsilon ^2})\delta $ (3)

校验节点的擦除概率为

$T_\delta ^ - (\varepsilon ){\rm{ = }}2\varepsilon - {\varepsilon ^2} + (1 - 2\varepsilon + {\varepsilon ^2})\delta $ (4)

由式(3)、(4)可得故障模型下译码过程中各节点间传递的擦除概率 ${\varepsilon _{j + 1}}$ 过程为

${\varepsilon _{j + 1}} = \left\{ \begin{array}{l}T_\delta ^ + ({\varepsilon _j})\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;{\rm{1/2}}\\T_\delta ^ - ({\varepsilon _j})\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;{\rm{1/2}}{\rm{}}\end{array} \right.$

式中:译码的初始层 ${\varepsilon _{(0)}}$ 等于BEC的擦除概率p ${\varepsilon _{(\infty )}} \! \in\! \left\{ {0,1} \right\}$ 。由于 ${\varepsilon _j}$ 有界,所以 ${\rm E}\left( {\left| {{\varepsilon _j}} \right|} \right)\! <\! \infty $ ,进一步得出

$\begin{split}& {\rm E}({\varepsilon _{j + 1}}|{\varepsilon _j}){\rm{ }} = \frac{1}{2}(T_\delta ^ + ({\varepsilon _j}) + T_\delta ^ - ({\varepsilon _j})) = \\& \frac{1}{2}((1 - \varepsilon _j^2)\delta + 2{\varepsilon _j} + (1 - 2{\varepsilon _j} + \varepsilon _j^2)\delta ) = \\& {\varepsilon _j} + (1 - {\varepsilon _j})\delta \geqslant {\varepsilon _j}{\rm{ }}\end{split}$ (5)

由于在故障的BEC模型下实现完全正确的SC译码是不可能的,并且在实际的通信过程中完全可靠的信息传输是不必要的,因此我们只关注在故障模型下的SC译码并探究在何种情况下可以实现SC译码器尽可能正确的译码。

3 非均匀错误保护方案

SC译码过程可以看成是基于深度优先的一种树搜索过程,每一层代表一位的译码估值,每个节点通过上层节点发送的信息计算当前节点的似然信息并发送到下层节点。硬件中SC译码器译码深度为n,包含n+1层译码节点,因此一个译码器共包含的译码节点为

${N_{PE}} = \sum\limits_{j = 0}^n {{2^{n - j}}} = {2^{n + 1}} - 1 = 2N - 1$

正如之前所提到的,传统的译码器使用大规模的晶体管或者电路级纠错码来提高电路的容错性,但是在大规模的电路中这种方法会消耗巨大的空间和功率。研究发现同一层节点中并非所有的节点都是同样重要的。这意味着可以采用对节点的一部分进行保护的方法克服硬件错误。

np表示被保护层的序号,nu表示未被保护的层号。我们假设np层经过保护处理后δ=0,Np表示被保护的节点总数,有

${N_P} = \left\{ {\begin{aligned}& {\displaystyle\sum\nolimits_{j = 0}^{{n_p} - 1} {{2^j} = {2^{{n_p}}} - 1} ,\;\;\;{n_p}}{>0}\\& {0,\;\;\;{n_p} = 0}& {}\end{aligned}} \right.$

综上可以得到,在该种方案译码过程中各节点间传递的擦除概率 ${\varepsilon _{j + 1}}$ 过程为

${\varepsilon _{j + 1}} = \left\{ \begin{aligned}& T_\delta ^ + ({\varepsilon _j}),\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2,\;\;\;\;\;{\rm{ }}j{\rm{ }} = {\rm{ }}0,1, \cdots ,{n_u} - 1\\& T_\delta ^ - ({\varepsilon _j}),\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2,\\& {T^ + }({\varepsilon _j}),\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2,\;\;\;\;\;j{\rm{ }} = {\rm{ }}{n_u},\;\;{n_u} - 1, \cdots ,n\\& {T^ - }({\varepsilon _j}),\;\;{\rm{w}}{\rm{.p}}{\rm{.}}\;\;1/2,\end{aligned} \right.$
4 仿真结果

N分别为1 024、2 048、4 096;信道擦除概率0.5;故障模型下加性擦除概率δ=10−6情况下,SC译码器的帧擦除率如图1所示。

图 1 故障模型与无故障模型极化码的帧擦除率

通过图1可以发现故障模型与非故障模型的误帧率FER都随着码率的增加而增加,但是可以看出当码率小于0.3时,故障模型下的误帧率明显高于非故障模型的误帧率,且故障模型下当码率小于0.15时不同码长的误帧率接近同一值。

图2给出了在δ分别为10−3、10−4、10−5时,BEC(0.5)的情况下, ${n_u} = 1,2, \cdots ,10$ 时的码率损失 $\Delta R(\delta ,\varepsilon ,{n_u})$

图 2 码率损失 $\Delta R(\delta ,\varepsilon ,{n_u})$

由式(5)可知,当保护层确定时,ε收敛,下界为εj。未保护的码率损失为 $\Delta R(\delta ,\varepsilon ,{n_u})$ 。如图2所示,可看出被保护节点所占的比例越大码率损失越小,由此推出 $P({\varepsilon _{(\infty )}} = 0) = 1 - \varepsilon - \Delta R(\delta ,\varepsilon ,{n_u})$ 。因此可以得到当采用了部分保护方案时,极化码虽然不能达到信道容量,但是当 $R < 1 - \varepsilon - \Delta R(\delta ,\varepsilon ,{n_u})$ 时仍然可以实现可靠通信。

一个有限码长的部分保护效果如图3所示。图3给出了码长N=1 024情况下,δ=10−6、BEC(0.5)、 ${n_p} = 0,1, \cdots ,5$ 时,SC译码在故障模型下的误帧率曲线。

图3表明只在初始节点添加保护时已经明显地改善了SC译码器的误帧率,尤其在码率较低时。当np=5时,故障模型下SC译码的误帧率几乎与非故障下SC译码的误帧率相同,此时被保护节点占节点总数的1.5%。

图 3 SC译码在故障模型下的误帧率曲线

图4给出了N=1 024,2 048,4 096情况下,δ=10−6、BEC(0.5)、np=n−5(被保护节点约占节点总数的1.5%)时的误帧率。综合以上可知,无论何种码长被保护方案的SC译码的误帧率曲线都近似理想无加性擦除概率模型SC译码的误帧率。

图 4 故障模型与无故障模型误帧率
5 结论

本文研究了BEC信道下SC译码器由于自身错误引起的加性擦除概率,建立了故障模型,通过对故障模型的研究得出:1)在该模型下不可能实现完全无错误的可靠通信。2)针对研究结果1)发现的问题提出了一种非均匀保护方案。通过仿真证明在BEC故障模型下,采用非均匀保护方案可以使故障模型下的SC译码误帧率曲线近似理想无加性擦除概率模型SC译码的误帧率,可以实现无差错传输。

参考文献
[1] BALATSOUKAS-STIMMING A, RAYMOND A J, GROSS W J, et al. Hardware architecture for list successive cancellation decoding of polar codes[J]. IEEE transactions on circuits & systems ii express briefs, 2014, 61(8): 609-613. (0)
[2] VARSHNEY L R. Performance of LDPC codes under faulty iterative decoding[J]. IEEE transactions on information theory, 2011, 57(7): 4427-4444. (0)
[3] YAZDI S M S T, CHO H, DOLECEK L. Gallager B decoder on noisy hardware[J]. IEEE transactions on communications, 2013, 61(5): 1660-1673. (0)
[4] LEDUC-PRIMEAU F, GROSS W J. Faulty Gallager-B decoding with optimal message repetition[C]// Allerton Conference on Communication, Control, and Computing. Monticello, USA, 2012: 549-556. (0)
[5] NGASSA C K, SAVIN V, DECLERCQ D. Min-Sum-based decoders running on noisy hardware[M]. Atlanta: IEEE, 2013. (0)
[6] BALATSOUKAS-STIMMING A, BURG A. Density evolution for min-sum decoding of LDPC codes under unreliable message storage[J]. IEEE communications letters, 2014, 18(5): 849-852. (0)
[7] ARIKAN E. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE transactions on information theory, 2008, 55(7): 3051-3073. (0)
[8] GIARD P, SARKIS G, THIBEAULT C, et al. A 237 Gbps unrolled hardware polar decoder[J]. Electronics letters, 2014, 51(10). (0)
[9] 陈凯. 极化编码理论与实用方案研究[D]. 北京: 北京邮电大学, 2014. (0)
[10] 黄志亮. 极化码的编译码方法研究[D]. 广州: 华南理工大学, 2015. (0)
[11] BALATSOUKAS-STIMMING A, BURG A. Faulty successive cancellation decoding of polar codes for the binary erasure channel[C]//International Symposium on Information Theory and its Applications. Melbourne: Australia, 2014: 448-452. (0)