﻿ 基于BP神经网络的SCL译码研究
 计算机系统应用  2018, Vol. 27 Issue (12): 246-250 PDF

Research on SCL Decoding Based on BP Neural Network
LU Li-Jin, LI Shi-Bao
College of Computer & Communication Engineering, China University of Petroleum, Qingdao 266580, China
Foundation item: Fundamental Research Funds for the Central Universities (18CX06042A)
Abstract: Existing decoding algorithms for polar codes still suffer from very high complexity. To solve this problem, an SCL decoding algorithm based on BP neural network is proposed. In offline, the algorithm builds and trains an appropriate BP neural network by collecting data. With the trained BP neural network, the optimal initial value of list size L is found through on-line operation. On this basis, the complexity is reduced by designing an improved SCL decoding algorithm. Experimental results show that compared with existing algorithms, the proposed algorithm can significantly reduce the average decoding complexity at low SNR.
Key words: polar codes     BP neural network     SCL decoding     list size     complexity

Arikan首次提出极化码(Polar Code), 且极化码是人类已知的第一种能够被严格证明达到信道容量的信道编码方法[1]. 在串行抵消(SC)译码算法下, 极化码的复杂度低、译码结构简单. 然而, SC译码算法在码长为有限长的配置下, 纠错性能不理想.

1 相关原理 1.1 极化编码与极化译码 1.1.1 极化编码

 $I\left( W \right) = \sum {\sum {\frac{1}{2}\beta \log \left( {\frac{{2\beta }}{{{\beta _0} + {\beta _1}}}} \right)} }$ (1)

 $W_N^{\left( i \right)}\left( {y_1^N,u_1^{i - 1}|{u_i}} \right) = \sum\limits_{u_{i + 1}^N \in {X^{N - 1}}} {\frac{1}{{{2^{N - 1}}}}} {W_N}\left( {y_1^N|u_1^N} \right)$ (2)

$v_1^N = u_1^N{F^{ \otimes n}}$ , 其中 $n = {\log _2}N$ , $F = \left[ {\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}} \right]$ , ${F^{ \otimes n}} = F \otimes {F^{ \otimes \left( {n - 1} \right)}}$ , $\otimes n$ 表示 ${{n}}$ 次克罗内克幂, 以及 $u_1^N =$ $\left( {{u_1},{u_2},\cdots,{u_N}} \right)$ 由信息比特与固定比特混合而得到. 通过对 $v_1^N$ 进行比特反序重排, 最终得到编码比特序列 $x_1^N = \left( {{x_1},{x_2},\cdots,{x_N}} \right)$ .

1.1.2 极化译码

 $L({y_i}) = \frac{{2{y_i}}}{{{\sigma ^2}}}$ (3)

 $L_N^{\left( {2i - 1} \right)}\left( {y_1^N,u_1^{2i - 2}} \right) = L_{N/2}^{\left( i \right)}\left( {y_1^{N/2},u_{1,o}^{2i - 2} \oplus u_{1,e}^{2i - 2}} \right) \odot \Phi$ (4)

 $L_N^{\left( {2i} \right)}\left( {y_1^N,u_1^{2i - 1}} \right) = L_{N/2}^{\left( i \right)}\left( {y_1^{N/2},u_{1,o}^{2i - 2} \oplus u_{1,e}^{2i - 2}} \right) + \Phi$ (5)

 $PM\left( {\hat u_{1,l}^{\left( i \right)}} \right) = PM\left( {\hat u_{1,l}^{\left( {i - 1} \right)}} \right) + {c_{i,l}} \cdot \left| {L_{N,l}^{\left( i \right)}} \right|$ (6)

1.2 BP神经网络

2 基于BP神经网络的SCL译码算法

 图 1 基于BP神经网络的极化码算法系统框图

2.1 构建与训练BP神经网络

2.1.1 样本数据的准备及预处理

 ${{\rm{z}}_r} = \frac{{{s_r} - {s_{{\rm{min}}}}}}{{{s_{{\rm{max}}}} - {s_{{\rm{min}}}}}}\;$ (7)

2.1.2 神经网络的训练

 ${E_n} = \frac{1}{2}{\sum\limits_{r \in outputs} {\left( {{g_r} - {z_r}} \right)} ^2}$ (8)

 ${\delta _r} = {z_r}\left( {1 - {z_r}} \right)\left( {{g_r} - {z_r}} \right)$ (9)

 ${\delta _r} = {a_r}\left( {1 - {a_r}} \right)\sum\limits_{k \in outputs} {{\omega _{kr}}{\delta _k}}$ (10)

 ${\omega _{jr}} \leftarrow {\omega _{jr}} + \eta {\delta _j}{s_{jr}}$ (11)

 ${\omega _{rb}} \leftarrow {\omega _{rb}} + \eta {\delta _r}$ (12)

2.2 基于BP神经网络的SCL译码算法

1) 对L进行初始化, 将L初始化为L的最优初始值;

2) 执行SCL译码算法, 并对其译码候选路径进行CRC校验;

3) 如果有一条或多于一条的候选路径通过CRC校验, 则输出一条最有可能的路径, 并退出译码; 否则, 跳到4).

4) 将L更新为2L, 并判断更新之后的L是否大于 ${L_{\max }}$ . 若不大于 ${L_{\max }}$ , 则跳回2); 否则, 退出译码.

 图 2 BNN-SCL译码算法在译码端的流程图

3 实验结果与分析

 图 3 不同译码算法下的BER性能比较

 图 4 不同译码算法下的平均复杂度比较

4 结语

 [1] Arikan E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 2009, 55(7): 3051-3073. DOI:10.1109/TIT.2009.2021379 [2] Yuan B, Parhi KK. Early stopping criteria for energy-efficient low-latency belief-propagation polar code decoders. IEEE Transactions on Signal Processing, 2014, 62(24): 6496-6506. DOI:10.1109/TSP.2014.2366712 [3] Guo J, Qin MH, Fàbregas AGI, et al. Enhanced belief propagation decoding of polar codes through concatenation. Proceedings of 2014 IEEE International Symposium on Information Theory. Honolulu, HI, USA. 2014. 2987–2991. [4] Goela N, Korada SB, Gastpar M. On LP decoding of polar codes. Proceedings of 2010 IEEE Information Theory Workshop. Dublin, Ireland. 2010. 1–5. [5] Tal I, Vardy A. List decoding of polar codes. Proceedings of 2011 IEEE International Symposium on Information Theory. St. Petersburg, Russia. 2011. 1–5. [6] Tal I, Vardy A. List decoding of polar codes. IEEE Transactions on Information Theory, 2015, 61(5): 2213-2226. DOI:10.1109/TIT.2015.2410251 [7] 陈凯. 极化编码理论与实用方案研究[博士学位论文]. 北京: 北京邮电大学, 2014. [8] Niu K, Chen K. CRC-aided decoding of polar codes. IEEE Communications Letters, 2012, 16(10): 1668-1671. DOI:10.1109/LCOMM.2012.090312.121501 [9] Li SB, Lu LJ, Deng YQ, et al. A reused-public-path successive cancellation list decoding for polar codes with CRC. IEEE Communications Letters, 2017, 21(12): 2566-2569. DOI:10.1109/LCOMM.2017.2756642 [10] Li B, Shen H, Tse D. An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check. IEEE Communications Letters, 2012, 16(12): 2044-2047. DOI:10.1109/LCOMM.2012.111612.121898 [11] Haykin S. Neural Networks and Learning Machines. 3rd ed. Upper Saddle River: Pearson, 2008. [12] 高鹏毅. BP神经网络分类器优化技术研究[博士学位论文]. 武汉: 华中科技大学, 2012. [13] Balatsoukas-Stimming A, Parizi MB, Burg A. LLR-based successive cancellation list decoding of polar codes. IEEE Transactions on Signal Processing, 2015, 63(19): 5165-5179. DOI:10.1109/TSP.2015.2439211 [14] 焦李成, 杨淑媛, 刘芳, 等. 神经网络七十年: 回顾与展望. 计算机学报, 2016, 39(8): 1697-1716. [15] Tal I, Vardy A. How to construct polar codes. IEEE Transactions on Information Theory, 2013, 59(10): 6562-6582. DOI:10.1109/TIT.2013.2272694