计算机系统应用  2019, Vol. 28 Issue (4): 247-251   PDF    
基于深度学习的实用HDPC码译码方法研究
郭军军, 白硕栋, 王乐     
西安工业大学 计算机科学与工程学院, 西安 710021
摘要:针对现有高密度校验码量化译码性能问题, 本文提出了一种基于深度学习的量化最小和译码算法-QMSND. 借助深度神经网络, 通过对神经最小和译码信道输入向量和每轮迭代过程中节点更新信息进行非均匀间隔量化, 动态调整Tanner图边的权重参数, 改善消息传播效能. 计算机仿真实验结果表明, 本文提出的方法在对BCH码进行译码时仅需要8比特表示信息即可接近未经量化的浮点译码性能. 因此, 所提出的QMSND译码方法便于硬件实现, 具有一定的实用性.
关键词: 深度学习    信道译码    加性高斯白噪声    BCH码    
Research on Practical Method for Decoding to HDPC Codes via Deep Learning
GUO Jun-Jun, BAI Shuo-Dong, WANG Le     
School of Computer Science and Engineering, Xi’an Technological University, Xi’an 710021, China
Foundation item: Key Research and Development Program of Shaanxi Province (2018GY-023); President Fund of Xi’an Technological University (XAGDXJJ16016)
Abstract: Aiming at the problem of quantitative decoding performance of high-density parity-check codes, this study proposes a quantitative min-sum decoding approach based on deep learning, referenced as QMSND. In order to improve the decoding performance and efficiency, the proposed decoder can adjust the weight parameters of a Tanner graph dynamically, and quantize the input vector and the message of nodes at every iteration in nonuniform fashion via deep neural network. Computer simulation results show that the performance of proposed QMSND decoding with 8-bits presentation is very close to that of the float neural min-sum decoding without quantization. Therefore, the proposed decoding approach is easy to implement by hardware and has some practicability.
Key words: deep learning     channel decoding     AWGN     BCH codes    

深度学习是机器学习的重要分支之一, 近年来由于其突出的性能而备受工业界和学术界的广泛关注[1]. 深度学习的基本原理是模仿人脑中多层神经节点堆叠在一起构成的深度神经网络完成认知学习. 基于数据驱动, 深度学习技术能够自动抽取特征进行由浅入深学习, 试图求解难以用传统机器学习方法解决的复杂问题, 例如游戏竞赛[2]、图像分类[3]、语音识别[4]和机器翻译[5]等.

最近, 国内外专家学者纷纷将深度学习引入到信道译码领域. 借助深度神经网络, 一些中短长度的高密度校验码(High-Density Parity-Check, HDPC)译码性能大幅提高, 且译码复杂度相对较低[611]. 鉴于构造译码训练集的困难性, Eliya等利用译码概率的独立性特点, 通过训练HDPC码对应Tanner图中消息交换边的权重, 分别提出了前馈神经网络译码算法和循环神经网络译码算法[9,10]. 中科大梁飞等提出了一种基于迭代的置信传播与卷积神经网络的组合译码方法, 该译码方法便于并行实现, 可广泛用于各类线性分组码[11].但是, 目前所提出的深度神经网络译码器由于时间和空间开销较大, 从而制约了在一些诸如空间受限、低延时、低功耗的物联网和存储芯片电路系统等领域的应用.

针对现有译码方法的不足, 受到文献[12]启发, 提出了针对加性高斯白噪声信道下HDPC码的基于深度神经网络的量化最小和译码算法—QMSND. 仿真实验结果表明, 所提出的方法仅需要256个量化阶(8比特表示)即可达到与现有浮点型神经网络译码器相同的译码性能, 因此便于硬件实现, 具有一定的实用价值.

1 基于深度神经网络的最小和译码 1.1 深度神经网络模型

一个人工神经网络是由多个相连的神经元组成的.每个神经元就是一个最小的计算单元, 通过累加其输入权重和可选的偏置量并利用非线性激活函数将结果直接输出或传递给其它神经元. 这些神经元分层排列构成了输入层、隐层和输出层. 如果神经网络包括多个隐层, 如卷积层、池化层、循环层和激活层等, 则称这类神经网络为深度神经网络(Deep Neural Network, DNN)[1].

$r$ $s$ 分别表示DNN的输入和输出, $L$ 为层数或深度, $\rho $ 为相关参数, 则深度神经网络的计算模型可用式(1)来表示.

$r = f(s,\rho ) = {f^{(L - 1)}}\left( {{f^{(L - 2)}}\left( {\cdots\left( {{f^{(0)}}(s)} \right)} \right)} \right)$ (1)

从式(1)中可知, 每一层神经网络的功能都是将上一次产生的结果作为输入, 函数经逐级复合, 将问题化繁为简. 使用大量测试数据, 在损失函数的约束下, 对目标函数进行最优化处理, 最终训练出合适的深度神经网络模型.

1.2 HDPC码神经最小和译码

设一个二元HDPC码的校验矩阵对应Tanner图模型为 $G = (VUC,E)$ , 图 $G$ 中变量节点集 ${V} = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ , 校验节点集 ${C} = \{ {c_1},{c_2},\; \cdots ,{c_r}\} $ , $n$ $r$ 分别表示校验矩阵的列数(码长)和行数, $E$ 是变量节点与校验节点之间相连的边集, $E = V \times C$ . 如果校验矩阵的第 $i$ 列第 $j$ 行元素是非零的, 则Tanner图 $G$ 的节点 ${v_i}$ ${c_{{j}}}$ 之间存在一条边 ${{{v}}_{{i}}}{{,}}{c_{{j}}} > \in E$ . 在不产生歧义的情况下, 本文后面表示变量节点和校验节点时省略其下标值. 在加性高斯白噪声信道下, 变量节点 $v$ 的对数似然比LLR的计算见式(2).

${{{l}}_v} = \log \frac{{\Pr ({c_v} = 1|{y_v})}}{{\Pr ({c_v} = 0|{y_v})}}{{ = }}\frac{{2{{{y}}_v}}}{{{\sigma ^2}}}$ (2)

式(2)中 ${{{y}}_v}$ 为码字位 ${c_v}$ 对应的信道接收值, $\sigma $ 信道噪声方差. 在HDPC码最小和译码算法中, 消息沿着变量节点和校验节点之间的边进行迭代传递. 令 $m_{c \to v}^{(l)}$ 表示在第 $l$ 次迭代中由变量节点v传递到校验节点c的消息, 同理可定义 $m_{c \to v}^{(l)}$ 为第 $l$ 次迭代中由校验节点c传递到变量节点v的消息. 在第0次迭代中, $m_{v \to c}^{(0)}$ 为变量节点v在其信道观察值对应的消息, 与校验节点c无关, 用 ${m_v}$ 来表示. 当 $l > 0$ 时, 变量节点的消息更新规则如下所示:

$m_{v \to c}^{(l)} = {m_v} + \displaystyle\sum\nolimits_{c' \in N(v)\backslash \{ c\} } {m_{c' \to v}^{(l)}} $ (3)

校验节点的消息更新是由上一次进入校验节点消息的函数决定的.

$m_{c \to v}^{(l)} = \left( {\prod\limits_{v' \in N(c)\backslash \{ v\} } {{\rm{sign}}(m_{v' \to c}^{(l - 1)})} } \right)\mathop {\min }\limits_{v' \in N(c)\backslash \{ v\} } \left| {m_{v' \to c}^{(l - 1)}} \right|$ (4)

在式(3)和(4)中, $N(v)$ 是Tanner图中变量节点v的邻居校验节点集合, $N(c)$ 是校验节点c的邻居变量节点集合. 若 ${{x > }}0$ , 符号函数 ${\rm{sign}}({{x}}){{ = }}1$ , 否则 ${\rm{sign}}({{x}}){{ = - }}1$ .

若采用基于深度学习的最小和译码时, 校验节点的消息更新如式(5)所示.

$m_{c \to v}^{(l)} = {\rm{ReLU}} \left( {\mathop {\min }\limits_{v' \in N(c)\backslash \{ v\} } \beta _{v' \to c}^{(l)}\left| {m_{v' \to c}^{(l - 1)}} \right|} \right)\prod\limits_{v' \in N(c)\backslash \{ v\} } \!\!\!{{\rm{sign}}(m_{v' \to c}^{(l - 1)})} $ (5)

式(5)中, 激活函数 ${\rm{ReLU}} (x) = max(x,0)$ , 调优参数 $\beta _{v' \to c}^{(l)}$ 是通过小批次随机梯度下降法学习得到的非负实数.

2 量化神经最小和译码 2.1 量化方法

为了便于硬件电路实现, 本文提出了一种基于多阶量化的HDPC码最小和译码算法. 由于采用了事先训练好的深度神经网络进行一次性译码, 因此译码速度大幅提高. 信道噪声和译码消息经非均匀量化器过滤, 采用有限比特表示量化阶, 可以有效节约存储空间. 量化激活函数 ${\rm{QReLU}} (x) = \max ({Q} (x),0)$ , 其中量化函数 ${Q} (x)$ 见式(6).

$Q(x) = \left\{ \begin{array}{l} {L_i},\;{T_i} \le x < {T_{i + 1}}\\ 0,\;\;{\text{其它情况}} \end{array} \right.$ (6)

式(6)中, 门限集合 $T = \{ {{T}_1},{{T}_2}, \cdots ,{{T}_{M}}\} $ , 量化阶 ${L_i}$ 是正整数, 量化阶的数量为 $M{{ + }}1$ . 量化阶的选择会影响译码的性能, 且与门限之间存在着非线性关系, 因此需要针对不同的码通过学习来确定量化阶及其门限值的大小.

2.2 译码框架

假设码长为 $n$ 的二元高密度BCH码 $\mathbb{C} \in {\{ 0,1\} ^n}$ ,一个码字 ${\bf{c}} \in \mathbb{C}$ 经无记忆信道传输后, 其对应的信道接收向量 ${\bf{y}} = ({y_1},{y_2}, \cdots ,{y_n})$ , 译码器输出的估计码字向量 ${\hat{\bf c}} = ({\hat c_1},{\hat c_2}, \cdots ,{\hat c_n})$ , 所提出的基于深度学习的量化最小和译码QMSND算法描述如下:

(1) 变量节点更新

通过式(3)计算由校验节点(除本节点外)传入到变量节点的消息. 当 $l{{ = }}0$ 时, $m_{v \to c}^{(0)} = {m_v}$ .

(2) 校验节点更新

由变量节点(除本节点外)进入到变量节点的消息由式(7)计算.

$\begin{array}{l}m_{c \to v}^{(l)} = {\rm{QReLU}} \left( {\mathop {\min }\limits_{v' \in N(c)\backslash \{ v\} } {Q} \left( {\beta _{v' \to c}^{(l)}\left| {m_{v' \to c}^{(l - 1)}} \right|} \right)} \right) \\ \quad\quad\quad\prod\limits_{v' \in N(c)\backslash \{ v\} } {{\rm{sign}}(m_{v' \to c}^{(l - 1)})} \end{array}$ (7)

由于每次计算参数 $\beta _{v' \to c}^{(l)}$ 值不尽相同, 一般采用离线方式事先进行基于小批量随机梯度下降的学习训练.

(3) 译码判决

$m_{v \to c}^{(l)} = {m_v} + \sum\nolimits_{c \in N(v)} {m_{c \to v}^{(l)}} $ (8)

如果 $m_{v \to c}^{(l)} > 0$ , 则对应码位的判决值 ${\hat c_v} = 0$ ; 否则 ${\hat c_v} = 1$ .

(4) 停止条件

${\widehat {\bf{c}}^{\rm{T}} }{\bf{H}} = 0$ 或超过最大迭代次数宣告译码结束,否则跳转到(1)继续执行.

QMSND译码算法的最大迭代次数与码长、码的结构以及信道噪声大小有关. 一般而言, 码字结构越复杂、码长越长或信道质量越差, 译码最大迭代次数的设值也越大. 通常, 为了平衡译码性能和速度, 对于中短长度的HDPC码, 如BCH或Polar码的最大迭代次数设置在5~30之间.

3 实验结果及分析 3.1 实验环境

本文实验所采用的深度神经网络是构建在基于TensorFlow的Keras框架之上. 使用Python语言编写仿真程序, 操作系统平台为Windows 10专业版, 采用蒙特卡洛法进行试验并比较高密度BCH码在不同信噪比下的性能. 为了加快训练速度, 应用了英伟达公司的GeForce GTX 1080 Ti系列图形加速GPU.

3.2 网络模型训练

本文所采用的深度神经网络译码器是对Tanner图边的权重和量化阶进行训练. 交叉熵函数定义为:

${L} ({{o}},y) = - \frac{1}{n}\sum\limits_{v = 1}^n {{y_v}\log ({o_v}) + (1 - {y_v})\log (1 - {o_v})} $ (9)

式(9)中, ${o_v}$ 是深度神经网络的非线性输出sigmoid函数, 定义为 ${o_v}(x) = \dfrac{1}{{1 + {e^{ - x}}}}$ .

所构建的量化最小和神经译码器QMSND是基于深度循环神经网络(Recurrent Neural Network, RNN)的, 包括1个输入层、4个循环层和1个输出层. 其中输入层又细化为调制层、噪声层和LLR层, 每个循环层对应一次完整的量化最小和译码迭代过程, 循环层内进一步细化为变量节点计算层、校验节点计算层(QReLU量化激活层). 变量节点计算层完成式(3)的计算任务, 校验节点计算层对进入节点的信息进行量化激活, 上次校验节点的计算结果作为下一次循环变量节点的输入, 循环层的训练目标是最小化交叉熵函数式(9). 循环层最后输出经式(7)计算后得到译码的最终结果.

训练数据来自于BCH码的全零码字在加性高斯白噪声信道的随机构造的数据集, 信噪比范围从1 dB到8 dB. 在不同信噪比下, 采用小批量随机梯度下降方式, 每次训练批次提交20个码字, 共使用1600个训练样例. 量化阶采用非均匀间隔, 间隔大小基本服从正态分布, 通过学习确定不同间隔大小. 由于循环神经网络前后层之间的存在相关性约束, 每层学习时的参数都会发生变化, 从而使得训练速度减慢. 因此, 在训练过程中学习率 ${{r}}$ 设置较小. 本次训练中, 我们将 ${{r}}$ 设置为0.001.

3.3 实验结果分析

为了验证本文提出方法的正确性和有效性, 选取了三个典型的BCH码作为测试码, 分别是BCH(63, 36), BCH(63, 45)和BCH(127, 99). 本次实验中量化阶数选择了128和256两种, 不同BCH码的译码性能比较分别见图1图2图3.

图1是采用传统和积译码SPA、文献[12]提出的DNNMS和本文提出的7比特量化QMSND-128以及8比特量化QMSND-256译码算法对BCH(63, 36)码的误比特率BER进行数值仿真结果比较. 从图1中可以看出, 当信噪比大于3 dB, QMSND译码性能逐步改善, QMSNND-256译码器性能逼近未经量化处理的DNNMS译码器; 在信噪比为7 dB时, SPA误码率为9.7×10–4, DNNMS误码率是1.2×10–4, QMSNND-128和QMSNND-256译码器的误码率分别是6.8×10–4和2×10–4.

图 1 BCH(63, 36)性能仿真图

图2是对BCH(63, 45)码进行性能数值比较. 在误码率为2.5×10–4时, SPA译码器信噪比是8 dB, QMSND-256译码器的信噪比为6.45 dB, 本文提出的8比特量化译码性能提高1.55 dB, 与DNNMS性能差距仅0.18 dB.

图 2 BCH(63, 45)性能仿真图

图3是对BCH(127, 99)长码进行仿真试验得到的译码性能比较, 其仿真结果与前两个码类似. 但QMSND量化译码性能改进没有前两个码那样显著, 这是因为随着码长增加, 样本训练复杂度急剧上升导致量化精度降低.

图 3 BCH(127, 99)性能仿真图

从以上三个译码性能比较图中可以看出, 在低信噪比区域, 传统的和积译码SPA、基于深度神经网络的最小和译码DNNMS以及本文提出的128和256阶量化神经最小和译码QMSND的译码性能差距很小, 但在中到高信噪比区域, SPA译码性能明显较差, DNNMS性能至少比SPA高1 dB, 而QMSND-128虽然没有DNNMS的译码性能优异, 但总体而言比SPA要好, 特别是QMSND-256译码性能与DNNMS十分接近.

4 结论

为了提高加性高斯白噪声信道下高密度BCH码译码的高效性和实用性, 本文提出了基于深度神经网络的量化最小和译码方法—QMSND. 仿真实验结果表明, 所提出的方法仅需要256个量化阶(8比特)即可达到与现有浮点型神经网络译码器相近的译码性能. 所提出的方法译码性能好, 便于硬件实现, 具有一定的应用前景. 今后将对进一步优化译码算法, 研究单轮迭代时能够自适应量化阶区间的学习方法, 提高译码性能和硬件实现效率.

参考文献
[1]
孙志军, 薛磊, 许阳明, 等. 深度学习研究综述. 计算机应用研究, 2012, 29(8): 2806-2810. DOI:10.3969/j.issn.1001-3695.2012.08.002
[2]
郭潇逍, 李程, 梅俏竹. 深度学习在游戏中的应用. 自动化学报, 2016, 42(5): 676-684.
[3]
胡二雷, 冯瑞. 基于深度学习的图像检索系统. 计算机系统应用, 2017, 26(3): 8-19.
[4]
侯一民, 周慧琼, 王政一. 深度学习在语音识别中的研究进展综述. 计算机应用研究, 2017, 34(8): 2241-2246. DOI:10.3969/j.issn.1001-3695.2017.08.001
[5]
Luong MT, Pham H, Manning CD. Effective approaches to attention-based neural machine translation. eprint arXiv:1508.04025, 2015.
[6]
Völker M, Hammer J, Schirrmeister RT, et al. Intracranial error detection via deep learning. eprint arXiv:1805.01667, 2018.
[7]
Ye H, Li GY. Initial results on deep learning for joint channel equalization and decoding. 2017 IEEE 86th Vehicular Technology Conference. Toronto, ON, Canada. 2018. 1–5.
[8]
Cammerer S, Gruber T, Hoydis J, et al. Scaling deep learning-based decoding of polar codes via partitioning. eprint arXiv:1702.06901, 2017.
[9]
Nachmani E, Beery Y, Burshtein D. Learning to decode linear codes using deep learning. eprint arXiv:1607.04793, 2016: 341–346.
[10]
Nachmani E, Marciano E, Lugosch L, et al. Deep learning methods for improved decoding of linear codes. IEEE Journal of Selected Topics in Signal Processing, 2018, 12(1): 119-131. DOI:10.1109/JSTSP.2017.2788405
[11]
Liang F, Shen C, Wu F. An iterative BP-CNN architecture for channel decoding. IEEE Journal of Selected Topics in Signal Processing, 2018, 12(1): 144-159. DOI:10.1109/JSTSP.2018.2794062
[12]
Lugosch L, Gross WJ. Neural offset min-sum decoding. eprint arXiv:1701.05931, 2017: 1361–1365.